药大学计算机科学与技术专业《数据结构与算法》科目期末试卷A.pdf

2022年江西中医药大学计算机科学与技术专业《数据结构与算法》科

目期末试卷A（有答案）

一、选择题

1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组
表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.33

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

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

3、静态链表中指针表示的是（）。

A.下一元素的地址

B.内存储器的地址

C.下一元素在数组中的位置

D.左链或右链指向的元素的地址

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

A.仅修改队头指针

B.仅修改队尾指针

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

D.队头、队尾指针都要修改

5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.234156

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

A．只有eB．有e、b．C有e、c．无D法确定

7、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180．B500，450，200，180

C．180，500，200，450．D180，200，500，450

8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结
果为（）。

A.CBEFDAB.FEDCBAC.CBEDFA不定D.

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

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

10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两
趟排序后的结果。

A.选择排序B.起泡排序C.插入排序D.堆排序

二、填空题

11、在有n个顶点的有向图中，每个顶点的度最大可达______。

12、设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）=______。

13、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点
中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该
结点中原有的关键字的个数是______。

14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，
free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；
delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别
进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A
的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查
找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。

15、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后
者，n至少为______。

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

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

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

三、判断题

19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）
20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）

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

22、在链队列中，即使不设置尾指针也能进行入队操作。（）

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

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

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

26、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（）

27、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加
闲置空间的碎片。（）

28、对大小均为n的有序