2025年数据结构期末考试题附答案.docxVIP

2025年数据结构期末考试题附答案

一、单项选择题（每题2分，共20分）

1.已知某算法的时间复杂度递推式为T(n)=2T(n/2)+n2，且T(1)=1，则该算法的时间复杂度为（）

A.O(n)B.O(nlogn)C.O(n2)D.O(n3)

2.若一个长度为n的顺序表的表尾插入操作的时间复杂度为O(1)，则该操作（）

A.必须移动所有元素B.不需要移动任何元素

C.移动元素的次数为n-1D.移动元素的次数为1

3.设循环队列的存储空间为Q(1:m)，初始时front=rear=m。经过一系列入队和出队操作后，front=2，rear=1。此时队列中的元素个数为（）

A.m-1B.mC.1D.0

4.一棵完全二叉树有100个节点，其中叶子节点的个数为（）

A.49B.50C.51D.52

5.对图G进行广度优先有哪些信誉好的足球投注网站（BFS）时，若使用队列存储待访问节点，则同一层的节点被访问的顺序是（）

A.任意顺序B.从左到右C.先进先出D.后进先出

6.下列排序算法中，空间复杂度为O(1)且不稳定的是（）

A.冒泡排序B.快速排序C.归并排序D.堆排序

7.哈希表中解决冲突的链地址法（拉链法）本质上是将哈希表的每个单元转换为一个（）

A.顺序表B.链表C.二叉树D.哈希表

8.若在平衡二叉树（AVL树）中插入一个节点导致失衡，且失衡节点的左孩子的右子树高度更高，则应进行（）

A.LL型旋转B.RR型旋转C.LR型旋转D.RL型旋转

9.对关键字序列{23,14,35,42,10,5}进行直接插入排序，第三趟排序后的序列为（）

A.{14,23,35,42,10,5}B.{10,14,23,35,42,5}

C.{14,23,10,35,42,5}D.{10,14,23,42,35,5}

10.若有向图的邻接矩阵中主对角线元素均为0，其余元素为1，则该图（）

A.是完全图B.存在环C.所有节点入度等于出度D.是强连通图

二、填空题（每空2分，共20分）

1.对于n个元素的线性表，顺序表的随机访问时间复杂度为______，单链表的随机访问时间复杂度为______。

2.一个栈的输入序列为1,2,3,4,5，若输出序列的第一个元素是3，则最后一个输出元素可能是______（写出一个即可）。

3.一棵二叉树的中序遍历序列为D,B,A,E,C,F，后序遍历序列为D,B,E,F,C,A，则其根节点为______，左子树的中序遍历序列为______。

4.无向图G有10个顶点，若其边数为15，则G的补图有______条边（完全图边数公式：n(n-1)/2）。

5.对长度为n的有序表进行二分查找，最坏情况下的时间复杂度为______；若表中元素存储在单链表中，则二分查找______（填“可行”或“不可行”）。

6.堆排序的建堆过程时间复杂度为______，堆排序的总时间复杂度为______。

三、判断题（每题2分，共10分。正确打√，错误打×）

1.线性表的顺序存储结构比链式存储结构更节省存储空间。（）

2.队列的“假溢出”现象可以通过循环队列解决。（）

3.哈夫曼树中权值最小的两个节点一定是兄弟节点。（）

4.拓扑排序只能用于有向无环图（DAG）。（）

5.基数排序的时间复杂度与关键字的位数无关。（）

四、应用题（共40分）

1.（8分）已知单链表L的头节点为head（带头节点），其元素为整数。设计一个算法，删除L中所有值为偶数的节点，并返回修改后的链表头节点。要求：用文字描述算法步骤，并用C语言伪代码实现。

2.（10分）给定二叉树的前序遍历序列为A,B,D,G,C,E,F，中序遍历序列为D,B,G,A,E,C,F。

（1）画出该二叉树的逻辑结构；

（2）写出该二叉树的后序遍历序列；

（3）计算该二叉树的高度（根节点为第1层）。

3.（10分）图G的邻接表表示如下（边权均为正整数）：

节点0：→1(3)→2(5)

节点1：→0(3)→3(2)→4(4)

节点2：→0(5)→3(6)

节点3：→1(2)→2(6)→4(1)

节点4：→1(4)→3(1)

（1）画出图G的逻辑结构（用节点0-4表示，边权标注）；

（2）使用Dijkstra算法求节点0到其他所有节点的最短路径，写出每一步的距离数