2025年大学试题(计算机科学)-数据结构考试近5年真题荟萃附答案.docx

（图片大小可自由调整）

2025年大学试题(计算机科学)-数据结构考试近5年真题荟萃附答案

第I卷

一.参考题库(共80题)

1.在一棵二叉树中，第5层上的结点数最多为（）。

2.广义表（f?，h?，（a?，b，d，c），d?，e?，（（i?，j），k?））的长度是（）。

3.栈和队列的存储方式既可是顺序方式，也可是链接方式。

4.栈和队列的共同点是什么？（）

A、都是先进后出

B、都是先进先出

C、只允许在端点处插入和删除元素

D、没有共同点

5.向一个循环队列中插入元素时，需要首先移动（），然后再向所指位置（）新插入的元素。

6.设有一稠密图G，则G采用（）存储较省空间。

7.一组记录的关键字序列为（80，57，41，39，46，47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）

A、39，46，41，57，80，47

B、39，47，46，80，41，57

C、41，39，46，47，57，80

D、39，80，46，47，41，57

8.数据的逻辑结构有四种基本形态，分别是（）

9.设有一稀疏图G，则G采用（）存储较省空间。

10.假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20的散列表，每个散列地址的单链表的长度平均为（）。

11.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为（）和（）

12.下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。

A、希尔排序

B、快速排序

C、冒泡排序

D、堆排序

13.数据结构里，栈是操作受限的线性表，插入和删除都在（）完成。

A、栈顶

B、栈底

C、栈中

D、栈外

14.一棵度为2的树与一棵二叉树有何区别？

15.链表的每个结点中只包含一个指针域，该链表称为（）或（）。

16.下列哪组序列是堆：（）

A、（79，40，46，56，38，84）

B、（84，56，79，46，38，40）

C、（40，38，46，56，79，84）

D、（84，38，46，40，56，79）

17.在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。

A、ph=p；p-＞next=ph

B、p-＞next=Ph；p=ph

C、p-＞next=ph-＞next；ph=p

D、p-＞next=ph-＞next；ph-＞next=p

18.二维数组是其数组元素为线性表的线性表。

19.矩阵中的行列数往往是不相等的。

20.在哈夫曼树中，权值最小的结点离根结点最近

21.有向图顶点V的度等于其（）之和。

22.具有12个关键字的有序表，折半查找的平均查找长度（）。

A、3.1

B、4

C、2.5

D、5

23.数据结构里，存储结构是指：数据的逻辑结构在计算机中的（）。

A、存储形式

B、逻辑关系

C、不确定

D、都不对

24.设二维数组A[1?m，1?n]按行存储在数组B中，则二维数组元素A[i，j]在一维数组B中的下标为（）。

A、n*（i－1）＋j

B、n*（i－1）＋j－1

C、i*（j－1）

D、j*m＋i－1

25.下面关于B树和B＋树的叙述中，不正确的结论是（）。

A、B树和B＋树都能有效的支持顺序查找

B、B树和B＋树都能有效的支持随机查找

C、B树和B＋树都是平衡的多叉树

D、B树和B＋树都可用于文件索引结构

26.（）线性表中结点的集合是（）的，结点间的关系是（）的。

27.在具有n个单元的循环队列中，队满时共有（）个元素。

28.若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（）

A、LOC（a00）+[j*m+i]

B、LOC（a00）+[j*n+i]

C、LOC（a00）+[（j-1）*n+i-1]

D、LOC（a00）+[（j-1）*m+i-1]

29.已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度