2022年武昌首义学院计算机科学与技术专业《数据结构与算法》科目期末试.pdfVIP

2022年武昌首义学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.9

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、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有Ⅰ．只B有ⅡC．Ⅰ和Ⅱ．DⅠ和Ⅲ

7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树．所B有叶结点都在同一层上

C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接

8、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

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

其关键字有序（）。

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

10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第

一个记录为基准得到的一次划分结果为（）。

A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）

C.（40，38，46，56，79，84）D.（40，38，46，84，56，79）

二、填空题

11、属于不稳定排序的有______。

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

成321。请填空：

13、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。

也可以按______检索；按______检索又可以有______检索和______检索。

14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从

左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，

指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使

用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。

试填充算法中的空格，使算法完整。

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

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

16、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）

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

______；深度是______。

18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a