汕 头 职 业 技 术 学 院

2007-2009学年第二学期期末试卷（B）

课程名称数据结构 学分_____ 拟题人 何汉阳 审题人___________ 系(校区) 计算机系 班级_____________ __ 学号_____ 姓名_ _________

题 号 得 分 一 二 三 四 五 六 七 八 总 分 评卷人 一、判断题（每小题1分，共15分）

1、数据的物理结构是指数据在计算机内的实际存储形式。（ ） 2、分配给单链表的内存地址必须是连续的。（ ）

3、在有n个元素的顺序表中，删除任意一个元素所需移动结点的平局次数为n-1。（ ） 4、对于单循环链表，从表中任一结点都能扫描表中的全部结点。（ ） 5、栈是一种对进栈、出栈操作总次数做了限制的线性表。（ ）

6、无论是顺序队列还是链接队列，插入和删除元素运算的时间复杂度都是O(1）。（ ） 7、表示稀疏矩阵的三元组顺序中，各元素的排列顺序与矩阵元素值的大小有关。（ ） 8、完全二叉树中只有度为0和度为2的结点。（ ）

9、已知二叉树的先序序列和后序序列，并不能唯一确定这棵二叉树。（ ） 10、哈夫曼树中，权值较大的叶结点一般都离根结点较远。（ ）

11、如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图。（ ） 12、有向图的遍历不可采用广度优先搜索方法。（ ）

13、顺序表和单链表表示的有序表均可使用二分查找法来提高查找速度。（ ）

14、只有在记录的关键字的初始状态为逆序排列的情况下，直接选择排序过程中元素的移动次数才会达到最大值。（ ）

15、内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。（ ） 二、选择题（每小题2分，共40分）

1．___________中任何两个结点之间都没有逻辑关系。 A)集合 B)图状结构 C)树型结构D)线性结构 2．计算机算法指的是__________。

A)计算方法 B)调度方法

C)排序方法 D)解决某一问题的有限运算序列 3．下面____________的时间复杂性最好，即执行时间最短。

3

A)O(n) B)O(nlog2n) C)O(log2n) D)O(n)

4．在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素。

A)n-i B)i C)n-i-1 D)n-i+l

5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，插入一个元素时

- 1 - / 4

平均移动表中的_______个元素。

A) n/2 B)(n-1)／2 C)(n+1)／2 D)n 6．单链表要求内存中可用存储单元的地址 。 A)必须是连续的 B)一定是不连续的

C)部分地址必须是连续的 D)可以是连续的，也可以是不连续的

7．在一个单链表中，若要删除p指针所指向结点的后继结点，则执行________。 A)p->next=p B)p=p->next->next

C)p->next=p->next->next D)p=p->next；p->next=p->next->next

8．若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用______存储方式最节省时间。

A)单链表 B)双链表 C)单循环链表 D)带头结点的双循环链表 9．采用链接方式存储线性表的优点是_________。 A)便于随机存取 B)花费的存储空间较顺序存储少

C)便于插入和删除操作 D)数据元素的物理顺序和逻辑顺序相同 10．在下面栈的基本运算中，不是加工型运算的是_______。 A)初始化 B)进栈 C)退栈 D)判栈空 11．在顺序栈中进行退栈操作时，___________。

A)谁先谁后都可以 B)先移动栈顶指针，后取出元素 C)不分先后，同时进行 D)先取出元素，后移动栈顶指针

12．假设一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是_______。 A)B，C，D，A，E B)E，D，A，C，B C)B，C，A，D，E D)A，E，D，C，B

13．在由n个单元组成的顺序存储的循环队列sq中，假定f和r分别为队头指针和队尾指针，则判断队满的条件是_______。

A)f==(r十1)％n B)(r-1)％n==f C)f==r D)(f+1)％n==r 14．树最适合于表示__________。

A)有序数据元素 B)无序数据元素

C)元素之间无联系的数据 D)元素之间具有分支层次关系的数据 15．在一棵深度为k的完全二叉树中，所含结点个数不小于_________。

kkkk-1

A)2 B)2+1 C)2-1 D)2

16．在下列存储形式中，_______不是树的存储形式。 A)双亲表示法 B)顺序存储表示

C)孩子兄弟表示法 D)孩子链表表示法

17．对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为__________的值除以8。

A)17 B)19 C)21 D)20

18．若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为_______。 A)1 B)i-1 C)i D)i+l 19．在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行_______。 对相邻元素之间的交换。 A)n／2 B)n-1 C)n D)n+l

20．以下四种排序方法中，需要附加的内存空间最大的是________。 A)插入排序 B)选择排序 C)快度排序 D)归并排序 三、列表说明用Prim算法求解下图最小生成树的生成过程。（15分）

- 2 - / 4

四、试编写在带头结点的单链表中删除（一个）最小值结点的“高效”算法。（10分）

五、关键码序列为 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 21，哈希函数为H(k)=k % 11，画出其开散列表处理冲突示意图，并计算查找成功的平均查找长度。（10分）。 六、写出顺序表上将监视哨设在高端的顺序查找算法子程序，并要写出在main()主函数中调用的过程语句。查找表的结构定义同课本一致，查找表的元素值和长度通过键盘输入。（10分）。

2007-2009学年第二学期期末试卷（B）答案

课程名称数据结构 拟题人 何汉阳

一、判断题（每小题1分，共15分）

1～5、√××√×6～10、×××√× 11～15、×××√×

二、选择题（每小题2分，共40分）

1～5、ADCDA 6～10、DCDCD 11～15、DBADD 16～20、DBCBD

三、解：（15分） 设从顶点0出发 U={0}, V-U={1, 2, 3, 4, 5, 6} Adjvex / 0 0 0 0 0 0 k=5 Lowcost 0 28 ∞ ∞ ∞ 10 ∞ (0, 5) U={0, 5}, V-U={1, 2, 3, 4, 6}Adjvex / 0 0 0 5 0 0 k=4 Lowcost 0 28 ∞ ∞ 25 0 ∞ (5, 4) U={0, 5, 4}, V-U={1, 2, 3, 6}Adjvex / 0 0 4 5 0 4 k=3 Lowcost Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost 0 28 ∞ 22 0 0 24 (4, 3) U={0, 5, 4, 3}, V-U={1, 2, 6}/ 0 3 4 5 0 3 k=2 0 28 12 0 0 0 18 (3, 2) U={0, 5, 4, 3, 2}, V-U={1, 6}/ 2 3 4 5 0 3 k=1 0 16 0 0 0 0 18 (2, 1) U={0, 5, 4, 3, 2, 1}, V-U={ 6}/ 0 2 3 4 5 0 1 k=6 0 0 0 0 0 14 (1, 6) U={0, 5, 4, 3, 2, 1, 6}, V-U={ }四、解：（10分） void DelMinNode(LINKLIST *head)

{ LINKLIST *p,*q,*r; //r为指向最小值结点的前一个结点

- 3 - / 4