2022年山东交通学院计算机科学与技术专业《数据结构与算法》科目期末试.pdf

2022年山东交通学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，
e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是
（）。

A.a，b，e，c，d，f，B.ac，f,e，b，d

C.a，e，b，c，f,d，eD.a，d，f，c，b

2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，
其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.40

3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采
用的存储方式（）。

A.单链表B.双向链表单C.循环链表顺D.序表

4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=s

B.s->next=h

C.s->next=h;h->next=s

D.s->next=h-next;h->next=s

5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，
则在进行出队操作时（）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改
6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字
3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

7、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有Ⅰ．只有BⅡ．CⅠ和Ⅱ．DⅠ和Ⅲ

8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩
子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按
其关键字有序（）。

A.二叉排序树哈夫曼B.树树C.AVL堆D.

10、下列二叉排序树中查找效率最高的是（）。

A.平衡二叉树

B.二叉查找树

C.没有左子树的二叉排序树

D.没有右子树的二叉排序树

二、填空题

11、在哈希函数H（key）=key%p中，p值最好取______。
12、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。

13、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。
也可以按______检索；按______检索又可以有______检索和______检索。

14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、
______、______、______。

15、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，
试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

16、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85
的地址为______。

17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。

18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为，l2，3，4，5，
经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶
指针值是______。设栈为顺序栈，每个元素占4个字节。

三、判断题

19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）

20、直接访问文件也能顺序访问，只是一般效率不高。（）
21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）

22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴
素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）

23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）

24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）

25、在待排数据基本有序