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

2022年大理大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）

一、选择题

1、下述文件中适合于磁带存储的是（）。

A.顺序文件

B.索引文件

C.哈希文件

D.多关键字文件

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

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

3、以下与数据的存储结构无关的术语是（）。

A.循环队列B.链表C.哈希表D.栈

4、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动若提前完成，那么整个工程将会提前完成

5、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.4

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。

A．只有eB．有e、bC．有e、cD．无法确定

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

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

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

8、有关二叉树下列说法正确的是（）。

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。

A.1B.4C.3D.2

二、填空题

11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

②执行程序，f（6，4）=______。

12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

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

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

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

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

16、模式串P=‘abaabcac’的next函数值序列为______。

17、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。

18、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。

三、判断题

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

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

21、广义表（（（a，b，c），d，e，f））的长度是4。（）

22、串是一种数据对象和操作都特殊的线性表。（）

23、树形结构中元素之间存在一对多的关系。（）

24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）

25、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（）

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

27、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（）

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

四、简答题

29、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。

30、