2025年大学数据结构期末试卷及答案.docxVIP

2025年大学数据结构期末试卷及答案

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

1.已知算法中某段代码的执行次数为T(n)=n+2nlog?n+3n2，则其时间复杂度为（）

A.O(n)B.O(nlog?n)C.O(n2)D.O(n3)

2.若进栈序列为1,2,3,4,5，且进栈和出栈操作可交替进行，则不可能的出栈序列是（）

A.5,4,3,2,1B.3,2,5,4,1C.2,3,5,1,4D.1,2,3,4,5

3.一棵完全二叉树有100个结点，其中叶子结点的个数是（）

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

4.对于无向图的邻接矩阵存储，以下说法正确的是（）

A.邻接矩阵的空间复杂度为O(n+e)

B.邻接矩阵中第i行非零元素个数等于顶点i的入度

C.邻接矩阵的对角线元素一定为0

D.邻接矩阵适用于稀疏图

5.对序列{3,1,4,1,5,9,2,6}进行快速排序，以第一个元素为枢轴，一次划分后的结果是（）

A.{1,1,2,3,5,9,4,6}B.{2,1,1,3,5,9,4,6}

C.{1,1,3,2,5,9,4,6}D.{1,1,2,3,4,9,5,6}

6.若某哈希表的装填因子α=0.8，表长m=10，则哈希表中元素个数为（）

A.6B.8C.10D.12

7.以下排序算法中，不稳定的是（）

A.冒泡排序B.归并排序C.直接插入排序D.快速排序

8.线索二叉树中，某结点的右线索指向其（）

A.右孩子B.前驱C.后继D.父结点

9.一个有向图的邻接表中有5个边结点，其中顶点A的邻接表包含2个边结点，则顶点A的出度为（）

A.2B.3C.5D.不确定

10.对长度为n的有序表进行二分查找，最坏情况下的时间复杂度为（）

A.O(n)B.O(n2)C.O(log?n)D.O(nlog?n)

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

1.一个栈的输入序列为a,b,c,d，若输出序列的第一个元素是c，则第四个输出元素可能是______（写出一个即可）。

2.一棵深度为5的满二叉树，其叶子结点数为______。

3.已知某二叉树的后序遍历序列为d,e,b,f,c,a，中序遍历序列为d,b,e,a,f,c，则前序遍历序列为______。

4.对于图的邻接表存储，若要删除边(u,v)，需要在u的邻接表中删除v的结点，并在______的邻接表中删除u的结点（无向图）。

5.对序列{5,3,8,6,7,2,1,4}进行希尔排序，取增量序列为4,2,1，第一趟（增量4）排序后的序列为______。

6.一个带权无向图的最小提供树可能不唯一，但其______一定唯一。

7.若用循环队列存储元素，队列长度为m，队头指针为front，队尾指针为rear（指向队尾元素的下一个位置），则队列中元素个数为______。

8.已知哈希函数H(key)=key%7，采用线性探测法处理冲突，将关键字序列{15,23,37,42,55}依次插入初始为空的哈希表（表长7），则关键字55的存储地址为______。

9.高度为h的平衡二叉树（根结点高度为1），最少结点数为______（用斐波那契数列表示）。

10.对n个元素进行堆排序，构建初始堆的时间复杂度为______。

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

1.顺序表的插入操作时间复杂度一定为O(n)。（）

2.队列的链式存储不会出现假溢出。（）

3.二叉树的前序遍历序列和后序遍历序列可以唯一确定一棵二叉树。（）

4.图的深度优先有哪些信誉好的足球投注网站遍历序列是唯一的。（）

5.快速排序的枢轴选择会影响其时间复杂度。（）

6.哈希表的查找效率主要取决于哈希函数的设计。（）

7.堆是一种完全二叉树。（）

8.中序线索二叉树中，左线索一定指向当前结点的前驱。（）

9.稀疏矩阵的压缩存储会丢失原矩阵的信息。（）

10.归并排序是一种稳定的排序算法。（）

四、算法设计题（每题10分，共30分）

1.设计一个算法，将带头结点的单链表L逆置（要求空间复杂度为O(1)）。

2.编写一个非递归算法，实现二叉树的中序遍历。

3.已知无向图G采用邻接表存储，设计一个递归算法，判断G是否为连通图。

五、综合应用题（每题10分，共20分）

1.用栈实现中缀表达式“3+