全国2006年1月高等教育自学考试
数据结构导论试题
课程代码:02142
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.数据结构中所定义的数据元素,是用于表示数据的( )
A.最小单位 B.最大单位
C.基本单位 D.不可分割的单位
2.数据的四种基本存储结构是指( )
A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
3.对于长度为n的顺序表执行删除操作,则其结点的移动次数( )
A.最少为0,最多为n
B.最少为1,最多为n
C.最少为0,最多为n-1
D.最少为1,最多为n-1
4.在一个单链表中,若p所指结点是q所指结点的前驱结点,则删除结点q的正确操作是
( )
A. p->next=q B. p->next=q->next
C. p=q->next D. p->next=q->next->next
5.有关栈的描述,正确的是( )
A.栈是一种先进先出的特殊的线性表
B.只能从栈顶执行插入、删除操作
C.只能从栈顶执行插入、栈底执行删除
D.栈顶和栈底均可执行插入、删除操作
6.二维数组A[10][20]采用按行为主序的存储方式,每个元素占4个存储单元,若A[0][0]的存储地址为300,则A[10][10]的地址为( )
A.700 B.1120
C.1180 D.1140
7.关于二叉树性质的描述,正确的是( )
A.二叉树结点的个数可以为0
B.二叉树至少含有一个根结点
C.二叉树若存在两个结点,则必有一个为根,另一个为左孩子
D.二叉树若存在三个结点,则必有一个为根,另两个分别为左、右孩子
8.具有4个结点的二叉树可有( )
A.4种形态 B.7种形态
C.10种形态 D.11种形态
9.若采用邻接表存储结构,则图的深度优先搜索类似于二叉树的( )
A.先根遍历 B.中根遍历
C.后根遍历 D.层次遍历
10.具有n个顶点的无向图,若要连通全部顶点,至少需要( )
A.(n-1)条边 B. n条边
C. n(n-1)条边 D. n(n-1)/2条边
11.下列四种基本的逻辑结构中,结构结点间不存在任何逻辑联系的是( )
A.集合 B.线性结构
C.树形结构 D.图形结构
12.闭散列表中由于散列到同一个地址而引起的“堆积”现象,是由( )
A.同义词之间发生冲突引起的
B.非同义词之间发生冲突引起的
C.同义词与非同义词之间发生冲突引起的
D.散列地址“溢出”引起的
13.ISAM文件组织方式是一种( )
A.专门适用于磁带的存取方法
B.专门适用于磁盘的存取方法
C.专门适用于光盘的存取方法
D.可适用于磁带、磁盘、光盘等多用途的存取方法
14.当待排序序列中记录数较多时,速度最快的排序方法是( )
A.冒泡排序法 B.快速排序法
C.堆排序法 D.归并排序法
15.若对序列(15,30,26,22,69,50,53,87)采用二路归并法排序,则进行一趟归并后产生的序列为( )
A.15,22,26,30,50,53,69,87 B.15,30,22,26,50,69,53,87
C.15,26,30,22,50,69,53,87 D.15,26,22,30,50,53,69,87
二、填空题(本大题共13小题,每小题2分,共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.数据表示和________________是程序设计者所要考虑的两项基本任务。
17.一个算法通常可从正确性、易读性、健壮性和________________等四个方面评价、分析。
18.对长度为n的顺序表执行删除操作,其删除算法在最坏情况下的时间复杂性为________________。
19.串是一种特殊的线性表,串常见的存储结构有顺序存储和________________两种方式。
20.我们通常把队列中允许插入的一端称为________________。
21.二维数组在机器级的具体实现,通常均采用________________存储结构。
22.深度为k的满二叉树其叶子结点个数共有________________个。
23.二叉树通常采用________________两种存储结构表示。
24.若一个完全无向图具有n条边,则该图的顶点个数为________________。
25.查找表的逻辑组织结构实际上是________________结构。
26.对于具有n个元素的数据序列,采用顺序查找法,其平均查找长度为________________。
27.若构成索引文件的索引表有序而主文件无序,则该索引文件称为________________文件。
28.对于具有n个元素的有序序列,若采用冒泡排序,最多需要进行________________趟起泡。
三、应用题(本大题共5小题,每小题6分,共30分)
29.试采用类C语言,给出二叉树的二叉链表结构描述。
30.试用Prim算法构造题30图的最小生成树,要求分步给出构造过程。
题30图
31.请按照数列{28,45,33,12,37,20,18,55}的先后插入次序,生成一棵二叉排序树。
32.已知一组键值序列(33,37,26,43,55,67,42,38),试采用堆排序法对该组序列作升序排序,给出建立的初始堆,以及第一次输出堆元素后筛选调整的堆。
33.已知一组键值序列(22,24,26,25,27,29,21,28),试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。
四、设计题(本大题共2小题,每小题7分,共14分)
34.试编写一个函数,以读取单链表的第i个元素。
35.若二叉树采用二叉链表表示,试给出二叉树先根遍历的非递归算法描述。
试题word文档下载: