2025年高等教育工学类自考-02331数据结构笔试考试历年典型考题及考点含含答案.docx

2025年高等教育工学类自考-02331数据结构笔试考试历年典型考题及考点含含答案

第1卷

一.参考题库(共100题)

1.数据结构里，栈具有后进先出的特性，用途广泛，下列选项中用到栈的有（）。

A、链表的合并

B、表达式求值

C、进制转换

D、括号匹配

2.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。

3.试用权集合{12，4，5，6，1，2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

4.在有向图中每个顶点的度等于该顶点的（）。

A、入度

B、出度

C、入度与出度之和

D、入度与出度之差

5.在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。

6.一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结点及左右结点编号为（）。

7.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。

8.广义表运算式HEAD（TAIL（（a，b，c），（x，y，z）））的结果是：（）。

9.（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

10.在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n）。

11.假定一棵度为3的树中结点数为50，则其最小高度应为（）。

A、3

B、4

C、5

D、6

12.设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

13.使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间。

14.一个队列的入队序列是1，2，3，4，则队列的出队序列是（）。

A、1，2，3，4

B、4，3，2，1

C、1，4，3，2

D、3，4，1，2

15.设要将序列（q，h，c，y，p，a，m，s，r，d，f，x）中的关键码按字母升序重新排序，回答。（）是初始步长为4的shell排序一趟扫描的结果。

A、f，h，c，d，p，a，m，q，r，s，y，x

B、p，a，c，s，q，d，f，x，r，h，m，y

C、a，d，c，r，f，q，m，s，y，p，h，x

D、h，c，q，p，a，m，s，r，d，f，x，y

E、h，q，c，y，a，p，m，s，d，r，f，x

16.循环队列的优点是什么？在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解决这个问题，常用的两种方法是什么？

17.链表的指针域可以有（）。

A、只能有一个

B、可以有多个

C、不可以有两个

D、可以没有指针域

18.设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构最佳

A、顺序表

B、栈

C、队列

D、链表

19.简述二叉树的常用操作及各操作的含义。

20.为什么在内存中使用的B—树通常是3阶的，而不使用更高阶的B—树？

21.在时间复杂度为O（nlog2n）的所有排序方法中，（）排序方法是稳定的。

22.图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

23.若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。

24.对任何二叉树的后序线索树进行后序遍历时都必需用栈。

25.对于二叉树来说，第i层上至多有（）个结点。

26.以下四种排序方法中，需要附加的内存空间最大的是（）

A、插入排序

B、选择排序

C、快度排序

D、归并排序

27.算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

28.排序的平均时间复杂度为O（n?logn）的算法是（），为O（n?n）的算法是（）

29.在非空线性表中除第一个元素外，集合中每个数据元素只有一个（）；除最后一个元素之外，集合中每个数据元素均只有一个（）。

30.稀疏矩阵的三元组有（）列。

31.循环队列的引入是为了克服（）。

32.数组元素的下标值越大，存取时间越长

33.有一个表长为m的散列表，初始状态为空，现将n（nm）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是（）。（而任一元素查找次数≤n-1）

34.