2022年南京晓庄学院计算机科学与技术专业《数据结构与算法》科目期末试.pdfVIP

2022年南京晓庄学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

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

链移动的操作为（）。

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

2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，

其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.40

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、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，

则根结点的孩子结点（）。

A．只有eB．有e、b．C有e、c．无D法确定

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

A．根结点最多有m棵子树．所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、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按

其关键字有序（）。

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

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，

4，8，20，9，7}则该次采用的增量是（）。

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

二、填空题

11、在有n个顶点的有向图中，每个顶点的度最大可达______。

12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则

其伙伴块的起始地址为______。

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

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

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

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

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

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

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

15、外排序的基本操作过程是______和______。

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

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

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

18、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]

与top[2]，则当栈1空时，top[1]为_