2022年上海第二工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).docxVIP

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.log2nB.（n－1）/2C.log2n+1D.（n＋1）/2

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入队的操作序列是______。

18、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。

三、判断题

19、倒排文件的目的是为了多关键字查找。（）

20、直接访问文件也能顺序访问，只是一般效率不高。（）

21、循环队列也存在空间溢出问题。（）

22、一个广义表可以为其他广义表所共享。（）

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

24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）

25、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（）

26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（）

27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）

28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）

四、简答题

29、三维数组A[1..10，-2..6