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

年西京学院计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

1表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e
的运算是（）。

A.head（tail（LS））B.tail（head（LS））

C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））

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

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

3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，
则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表

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

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

5、在下列表述中，正确的是（）

A.含有一个或多个空格字符的串称为空格串

B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树

C.选择排序算法是不稳定的

D.平衡二叉树的左右子树的结点数之差的绝对值不超过l

6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字
3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19
程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序
方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序．快速排序Ⅳ．堆排Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ

8、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1

B.log（n+1）+1
2

C.log（n+1）
2

D.log（n-l）
2

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

A.CBEFDAB.FEDCBAC.CBEDFA不定D.

10、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是：

A.05，46，13，55，94，17，42

B.05，13，17，42，46，55.94

C.42，13，94，05，55，46，17

D.05，13，46，55，17，42，94

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排
序树检索时，平均比较次数为______。

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

①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②（6，4）=______。

13、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，
right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，
right指向其右孩子，rflag=1，right指向其后继。

14、文件由______组成；记录由______组成。
VSAM（虚存储存取方法）文件的优点是：动态地______，不需要文件进行______，并
能较快地______进行查找。

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

17、阅读下列程序说明和程序，填充程序中的______。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者
略）。

本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针
为tp。交换左、右子树的算法为：

（1）把根结点放入堆栈。

（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入
栈。

（3）重复（2）直到堆栈为空时为止。

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

19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）
磁带机而言，ISAM是一种方便的文件组织方法（