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

期末试卷A（有答案）

一、选择题

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

2、下列排序算法中，占用辅助空间最多的是（ ）。 A.归并排序 B.快速排序 C.希尔排序D.堆排序 3、算法的计算量的大小称为计算的（ ）。 A.效率 B.复杂性 C.现实性 D.难度

4、在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。 A.O(n) B.O(n+e) C.O(n*n) D.O(n*n*n)

5、向一个栈顶指针为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

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

7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（ ）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2

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

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

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点

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

10、下列二叉排序树中查找效率最高的是（ ）。 A.平衡二叉树 B.二叉查找树

C.没有左子树的二叉排序树 D.没有右子树的二叉排序树

二、填空题

11、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。

12、在哈希函数H（key）=key%p中，p值最好取______。

13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。

14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；

delete_subtree（T，A），首先在二叉排序树 T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。

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

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

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

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

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

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

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

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

三、判断题

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

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

21、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（ ）

22、稀疏矩阵压缩存储后，必会失去随机存取功能。（ ） 23、对于有n个结点的二叉树，其高度为log2n。（ ）

24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ） 25、在待排数据基本有序的情况下，快速排序效果最好。（ ）

26、快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。（ ）

27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ ）

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

四、简答题

29、下面程序段的时间复杂度是什么？

30、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为\"abcabaa\"，说明下列程序的功能及执行结果。

31、用单链表保存m个整数，节点的结构为（data，link），且|data|＜n（n为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。例如若给定的单链表head如下

删除节点后的head为

要求

（1）给出算法的基本思想

（2）使用C或C＋＋语言，给出单链表节点的数据类型定义。

（3）根据设计思想，采用C或C＋＋语言描述算法，关键之处给出注释。说明所涉及算法的时间复杂度和空间复杂度。

五、算法设计题

32、设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为O（n）。

33、试将下列递归过程改写为非递归过程。

34、输入一个字符串，内有数字和非数字字符，如： ak123x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a中，例如123放入a[0]，456放入a[1]，……。编程统计其共有多少个整数，并输出这些数。

35、叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（306，55，859，984，9，271，33）

179，208，93，参

一、选择题

1、【答案】A 2、【答案】A 3、【答案】B 4、【答案】B 5、【答案】D 6、【答案】A 7、【答案】C 8、【答案】D 9、【答案】C 10、【答案】A

二、填空题

11、【答案】

（1）L->next=NULL //置空链表，然后将原链表结点逐个插入到有序表中 （1） p!=NULL //当链表尚未到尾，p为工作指针

（2） q!=NULL //查P结点在链表中的插入位置，这时q是工作指针 （4）p->next=r->next //将P结点链入链表中

（5）r->next=p //r是q的前驱，u是下个待插入结点的指针

12、【答案】小于等于表长的最大素数或不包含小于20的质因子的合数 13、【答案】稳定

14、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null 15、【答案】15

16、【答案】（）；（（））；2；2

17、【答案】stack[tp]=t；p=stack[tp--]；p；++tp

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。 18、【答案】++a*b3*4-cd；18

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

三、判断题

19、【答案】× 20、【答案】× 21、【答案】× 22、【答案】√ 23、【答案】× 24、【答案】√ 25、【答案】× 26、【答案】× 27、【答案】√ 28、【答案】√

四、简答题

29、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。 30、答：本程序的功能是求字符串的nextval函数，程序执行结果是0110132。 31、答：（1）算法思想：

算法的核心思想是用空间换时间。定义一个大小为n的布尔数组flag，初始时所有的元素都赋值为false，用来标识遍历过程中是否出现元素绝对值为flag的节点。然后遍历链表，遍历过程中，每一个当前结点data域的绝对值所对应的flag位：若为真，则删除该结点；若为假（false），则将flag位置为（true）。 （2）节点的数据结构定义如下：

（3）

（4）只遍历一次链表，所以时间复杂度为O（m）（m为单链表中元素的个数），申请大小为n的数组，所以空间复杂度为O（n）（n为节点绝对值的最大值）。

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：算法如下：