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

博观而约取，厚积而薄发。——苏轼

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

期末试卷A（有答案）

一、选择题

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

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

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

2、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次

B.遍历的基本方法有两种：深度遍历和广度遍历

C.图的深度遍历不适用于有向图

D.图的深度遍历是一个递归过程

3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，

则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表

4、已知有向图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

5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.234156

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

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

A．只有eB．有e、bC．有e、cD．无法确定

8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩

子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

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

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

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

C.其中只有一个叶结点

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

10、就平均性能而言，目前最好的内排序方法是（）排序法。

A.起泡B.希尔插入C.交换D.快速

二、填空题

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

12、无用单元是指______，例______

13、按LSD进行关键字排序，除最次