东北大学2025年学年《数据结构》期末考试试卷(A卷)附参考答案

东北大学2025年学年《数据结构》期末考试试卷(A卷)附参考答案一、单项选择题（每题2分，共20分）1.若某线性表最常用的操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用（）存储结构最节省时间。A.单链表B.双链表C.顺序表D.循环链表2.设一个栈的输入序列为1,2,3,4,5，则不可能的输出序列是（）。A.5,4,3,2,1B.4,5,3,2,1C.3,4,1,5,2D.2,3,1,5,43.已知循环队列的存储空间为数组data[0..m1]，队头指针为front，队尾指针为rear（指向队尾元素的下一个位置），则队列中元素个数为（）。A.(rearfront+m)%mB.rearfront+1C.rearfrontD.(rearfront)%m4.一棵完全二叉树有100个结点，其中叶子结点的个数是（）。A.49B.50C.51D.525.对于图的存储结构，邻接矩阵与邻接表相比，（）的描述是错误的。A.邻接矩阵的空间复杂度为O(n²)，适用于稠密图B.邻接表的空间复杂度为O(n+e)，适用于稀疏图C.邻接矩阵可以快速判断两顶点是否相邻D.邻接表更便于进行图的广度优先遍历6.对关键字序列{28,15,37,42,12,56,23}进行快速排序，以第一个元素为枢轴，一次划分后的结果是（）。A.{12,15,23,28,37,42,56}B.{15,12,23,28,42,56,37}C.{12,15,23,28,56,42,37}D.{12,15,23,28,42,56,37}7.哈希表中解决冲突的链地址法（拉链法）本质上是将哈希表的每个单元扩展为一个（）。A.顺序表B.链表C.栈D.队列8.若对n个元素进行归并排序，则其时间复杂度为（）。A.O(n)B.O(n²)C.O(nlogn)D.O(n²logn)9.设有向图G的邻接表中，每个顶点的出边表长度为d₁,d₂,…,dₙ，则图中边的总数为（）。A.d₁+d₂+…+dₙB.(d₁+d₂+…+dₙ)/2C.max(d₁,d₂,…,dₙ)D.min(d₁,d₂,…,dₙ)10.已知二叉树的先序序列为ABDCE，中序序列为BDAEC，则后序序列为（）。A.DBEACB.DEBCAC.DBECAD.DBEAC（注：原题可能存在排版问题，正确后序为DBECA）二、填空题（每空2分，共20分）1.线性表的顺序存储结构是一种（）存储结构，链表是一种（）存储结构。2.一个栈的输入序列为1,2,3，则可能的输出序列有（）种。3.深度为5的完全二叉树至少有（）个结点（根结点深度为1）。4.无向图的邻接矩阵是（）对称矩阵（填“一定”或“不一定”）。5.对长度为n的有序表进行二分查找，其最大比较次数为（）（用对数形式表示）。6.堆排序的时间复杂度为（），且是（）排序（填“稳定”或“不稳定”）。7.哈夫曼树中权值最小的两个结点一定是（）（填“兄弟结点”或“父子结点”）。8.若哈希函数为H(key)=key%11，采用线性探测法处理冲突，关键字序列{14,23,35,47,52}的哈希表中，关键字52的存储地址是（）。三、判断题（每题1分，共10分）1.循环队列的队满条件是(rear+1)%maxsize==front。（）2.二叉树的中序遍历序列中，任意一个结点的左子树结点都在其左侧，右子树结点都在其右侧。（）3.图的广度优先遍历需要使用栈作为辅助数据结构。（）4.快速排序在最坏情况下的时间复杂度为O(n²)。（）5.顺序查找适用于有序表和无序表。（）6.完全二叉树一定是满二叉树。（）7.拓扑排序只能用于有向无环图（DAG）。（）8.归并排序的空间复杂度为O(n)。（）9.哈希表的查找效率主要取决于哈希函数的设计，与处理冲突的方法无关。（）10.链表的删除操作不需要移动元素，因此时间复杂度一定为O(1)。（）四、应用题（共30分）1.（8分）已知单链表L的头结点指针为head（带头结点），试编写算法将L逆置（要求不额外申请结点空间）。2.（8分）给定二叉树的中序序列为BDAEC，后序序列为DBECA，画出该二叉树的逻辑结构，并写出其先序序列。3.（7分）图G的邻接矩阵如下，画出其邻接表表示（顶点编号为04），并写出从顶点0出发的深度优先遍历序列（假设邻接表中顶点按编号升序排列）。\[\begin{bmatrix}0&1&0&1&0\\1&0&1&0&1\\0&1&0&1&0\\1&0&1&0&1\\0&1&0&1&0\\\end{bmatrix}\]4.（7分）对关键字序列{45,38,66,90,88,10,25,45}进行基数排序（最低位优先，十进制），写出每一趟分配和收集后的结果。五、综合题（共20分）1.（12分）设计一个算法，判断一个二叉树是否为平衡二叉树（平衡二叉树的定义：任意结点的左右子树高度差的绝对值不超过1，且左右子树均为平衡二叉树）。要求给出算法的基本思路、关键步骤描述，并写出伪代码（或C语言函数）。2.（8分）某系统需要频繁在有序数组中插入新元素，同时要求插入操作的时间复杂度尽可能低。现有两种方案：方案一：使用顺序表存储，每次插入时用二分查找找到插入位置，然后移动元素完成插入；方案二：使用二叉排序树存储，每次插入时按二叉排序树规则插入新结点。分析两种方案的优缺点，并结合实际应用场景说明哪种方案更优。参考答案一、单项选择题1.C2.C3.A4.B5.D6.D7.B8.C9.A10.D（正确后序为DBECA）二、填空题1.随机；链式2.53.164.一定5.⌈log₂(n+1)⌉6.O(nlogn)；不稳定7.兄弟结点8.5（计算：52%11=8，地址8未冲突？原序列14%11=3，23%11=1，35%11=2，47%11=3（冲突，线性探测到4），52%11=8，无冲突，故地址8？需重新计算：假设哈希表初始为空，依次插入14（地址3）、23（地址1）、35（地址2）、47（地址3冲突，探测4）、52（地址8无冲突），故52地址为8。可能原题计算有误，正确应为8）三、判断题1.√2.√3.×（使用队列）4.√5.√6.×7.√8.√9.×（与处理冲突有关）10.×（需找到结点，时间复杂度O(n)）四、应用题1.逆置算法思路：从头结点后第一个结点开始，依次将当前结点插入到头结点之后。伪代码：```cvoidReverseList(LinkListhead){LNodep=head>next;//p指向第一个数据结点head>next=NULL;//原链表置空while(p!=NULL){LNodeq=p>next;//保存下一个结点p>next=head>next;//插入到头结点后head>next=p;p=q;//移动p到下一个结点}}```2.二叉树结构：根为A，左子树中序BD，后序DB→左子树根为B，右子树为D；右子树中序EC，后序EC→右子树根为C，左子树为E。先序序列：ABDCE。3.邻接表：顶点0的邻接点1、3；顶点1的邻接点0、2、4；顶点2的邻接点1、3；顶点3的邻接点0、2、4；顶点4的邻接点1、3。深度优先遍历序列（从0出发）：0→1→2→3→4（或0→3→2→1→4，取决于邻接表顺序，按升序则为01234）。4.基数排序过程：第一趟（个位）：分配：桶0:10；桶5:无；桶8:38；桶5:无；桶6:66；桶0:无；桶0:无；桶5:25；桶8:88；桶5:45（个位为5的有25、45，个位8的有38、88，个位6的66，个位0的10，个位0的90？原序列{45,38,66,90,88,10,25,45}个位分别为5,8,6,0,8,0,5,5。分配后桶0:90,10；桶5:45,25,45；桶6:66；桶8:38,88。收集后：90,10,45,25,45,66,38,88。第二趟（十位）：十位分别为9,1,4,2,4,6,3,8。分配后桶1:10；桶2:25；桶3:38；桶4:45,45；桶6:66；桶8:88；桶9:90。收集后：10,25,38,45,45,66,88,90。五、综合题1.算法思路：递归计算每个结点的左右子树高度，若高度差超过1则标记为不平衡。关键步骤：递归函数返回结点高度，若子树不平衡则返回1；对当前结点，计算左子树高度h_left和右子树高度h_right；若h_left或h_right为1，或|h_lefth_right|>1，返回1（不平衡）；否则返回max(h_left,h_right)+1（当前结点高度）。伪代码：```cintIsBalanced(BiTreeT){if(T==NULL)return0;//空树高度为0intleft_h=IsBalanced(T>lchild);if(left_h==1)return1;//左子树不平衡intright_h=IsBalanced(T>rchild);if(right_h==1)return1;//右子树不平衡if(abs(left_hright_h)>1)return1;//当前结点不平衡returnmax(left_h,right_h)+1;//返回当前结点高度}//主函数调用：若返回值≠1则平衡```2.方案分析：方案一（顺序表）：优点：二分查找定位O(log