2025年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

丹青不知老将至，贫贱于我如浮云。——杜甫

2025年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

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

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

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

2、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e

的运算是（）。

A.head（tail（LS））B.tail（head（LS））

C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））

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

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

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

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

5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h-next=s

B.s-next=h

C.s-next=h;h-next=s

D.s-next=h-next;h-next=s

6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序

方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ

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

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

天行健，君子以自强不息。地势坤，君子以厚德载物。——《周易》

A．只有Ⅰ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、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结

果为（）。

A.CBEFDAB.FEDCBAC.CBEDFA不定D.

10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。

A.直接插入排序B.起泡排序C.简单选择排序D.快速排序

二、填空题

11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。

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

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

14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，

试按如下格式给出在构造最小生