2022年上海第二工业大学计算机科学与技术专业《数据结构与算法》科目期.pdfVIP

2022年上海第二工业大学计算机科学与技术专业《数据结构与算法》

科目期末试卷A（有答案）

一、选择题

1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-1

2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，

其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

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

3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。

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.1B.2C.3D.4

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

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

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

7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三

次进行退栈操作，则不可能得到的出栈序列是（）。

8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩

子，下列结论正确的是（）。

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

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

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

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

9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中

有（）个叶子。

A.lognB.（n－1）/2C.logn+1D.（n＋1）/2

22

10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

A.（100，80，90，60，120，110，130）

B.（100，120，110，130，80，60，90）

C.（100，60，80，90，20，110，130）

D.（100，80，60，90，120，130，110）

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排

序树检索时，平均比较次数为______。

12、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。

13、VSAM系统是由______、______、______构成的。

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

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

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

15、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。

注：(1)图的顶点号从0开始计。

(2)indegree是有n个分量的一维数组，放顶点的入度，

(3)函数crein用于计算顶点入度。

(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空

(不空返回l，否则0)。

16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。

17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。