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（n0）个顶点的网，求出权最小的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（n0）个分支结点的满二叉树的深度是（）。

A.n-1

2

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，