2022年青岛科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

2022年青岛科技大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈

2、无向图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，fB.a，c，f,e，b，d

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

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、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛V1，V2，

V1，V3，V1，V4，V2，V5，V3，V5，V3，V6，V4，V6，V5，V7，

V6，V7｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7

C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7

6、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180B．500，450，200，180

C．180，500，200，450D．180，200，500，450

7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树B．所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接

8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间

9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码

字。

A.107B.108C.214D.215

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

A.平衡二叉树

B.二叉查找树

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

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

二、填空题

11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。

12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用a，b，d三元组表示弧a，

b及弧上的权d。E(G)为E(G)=｛0，5，100，0，2，10，1，2，5，0，4，30，

4，5，60，3，5，10，2，3，50，4，3，20｝，则从源点0到顶点3的最短

路径长度是______，经过的中间顶点是______。

13、文件由______组成；记录由______组成。

14、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并

能较快地______进行查找。

15、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，

试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

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

16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为

______。