2022年浙江农林大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdf

2022年浙江农林大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，
其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

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

2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放
在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并

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

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

4、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动若提前完成，那么整个工程将会提前完成

5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，
<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，
<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7

C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7

6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三
次进行退栈操作，则不可能得到的出栈序列是（）。

7、已知关键字序列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

8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

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

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

A.二叉树的度为2

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

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

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

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，
4，8，20，9，7}则该次采用的增量是（）。

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

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排
序树检索时，平均比较次数为______。

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

13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并
能较快地______进行查找。

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

15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则
删除一个元素平均需要移动元素的个数是______。

16、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。
17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85
的地址为______。

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

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

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

（1）把根结点放入堆栈。

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

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

三、判断题

19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）

20、倒排文件是对次关键字建立索引。（）

21、在链队列中，即使不设置尾指针也能进行入队操作。（）

22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法
的时间复杂性为O（i）。（）
23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）

24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）

25、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（）

26、抽象数据类型与