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

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

目期末试卷A（有答案）

一、选择题

1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿

链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j-nextD.j=r[j]-next

2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序

3、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈

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

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

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

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

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

5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)

6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三

次进行退栈操作，则不可能得到的出栈序列是（）。

7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，

下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modM

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）

C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modM

D．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）

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

其关键字有序（）。

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

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

A.二叉树的度为2

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

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

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

10、下面关于B和B+树的叙述中，不正确的是（）

A.B树和B+树都是平衡的多叉树B.B树和B+树都可用于文件的索引结构

C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索

二、填空题

11、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间

的是______算法，最费时间的是______算法。

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

成321。请填空：

13、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，

free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；

delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别

进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A

的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查

找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。

14、建立索引文件的目的是______。

15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则

删除一个元素平均需要移动元素的个数是______。

16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层