(2025年)数据结构图练习试题附答案

(2025年)数据结构图练习试题附答案一、单项选择题（每题2分，共20分）1.以下关于线性表的描述中，正确的是（）。A.顺序表的插入操作时间复杂度一定为O(n)B.单链表的删除操作时间复杂度一定为O(1)（已知待删节点指针）C.静态链表使用数组存储，因此插入时无需移动元素D.循环链表的尾节点指针指向头节点，因此无法通过尾指针快速访问头节点2.若一个栈的输入序列为1,2,3,4,5，不可能的输出序列是（）。A.5,4,3,2,1B.3,2,5,1,4C.2,3,1,5,4D.1,5,4,3,23.已知一棵完全二叉树有768个节点，该树的叶子节点数为（）。A.384B.385C.383D.3864.对于无向图的邻接矩阵存储，以下说法错误的是（）。A.邻接矩阵的空间复杂度为O(n²)，适用于稠密图B.第i行非零元素的个数等于顶点i的度C.邻接矩阵的对称性可用于优化存储（仅存下三角）D.从邻接矩阵中无法直接获取边的权值（若为带权图）5.对长度为n的有序表进行二分查找，最坏情况下的时间复杂度为（）。A.O(n)B.O(nlogn)C.O(logn)D.O(n²)6.以下排序算法中，不稳定的是（）。A.冒泡排序B.归并排序C.快速排序D.插入排序7.若哈希表的装填因子α=0.8，表长m=100，则平均查找长度主要取决于（）。A.哈希函数的设计B.处理冲突的方法C.表长m的大小D.关键字的分布8.线索二叉树中，某节点的右线索指向（）。A.中序遍历的前驱节点B.中序遍历的后继节点C.先序遍历的前驱节点D.后序遍历的后继节点9.以下关于拓扑排序的描述，正确的是（）。A.拓扑排序适用于所有有向图B.拓扑排序的结果唯一C.拓扑排序中每个顶点仅出现一次D.存在环的图也能提供拓扑序列10.对于n个节点的平衡二叉树（AVL树），其最小高度h满足（）。A.h≈log₂nB.h≈1.44log₂(n+2)C.h≈nD.h≈2log₂n二、填空题（每空2分，共20分）1.双端队列允许在两端进行插入和删除操作，若初始队列为空，依次执行操作：addFront(1),addRear(2),addFront(3),deleteFront(),addRear(4),deleteRear()，最终队列中的元素为（）（从队头到队尾）。2.已知一棵二叉树的先序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，则后序遍历序列为（）。3.对于有向图的邻接表存储，若要计算某个顶点的出度，需统计（）；若要计算入度，需遍历（）。4.希尔排序的核心思想是（），其时间复杂度与（）的选取密切相关。5.若用链式地址法处理哈希冲突，哈希表的平均查找长度主要与（）有关；若用开放定址法，平均查找长度还与（）有关。6.一个包含n个节点的无向连通图，其提供树的边数为（）；若该图有m条边，则提供树需删除（）条边。三、应用题（每题10分，共40分）1.已知单链表L的头节点指针为head（无头结点），设计一个算法将L反转（如1→2→3→4反转为4→3→2→1），要求空间复杂度为O(1)，并说明关键步骤。2.用栈实现中缀表达式“3+5(6-2)/4-1”的后缀转换过程，要求写出每一步栈和输出的状态（运算符优先级：、/高于+、-，同级左结合）。3.给定带权无向图G（顶点为A、B、C、D、E，边权如下：A-B:2，A-C:5，B-C:1，B-D:4，C-D:3，C-E:6，D-E:2），用Dijkstra算法求顶点A到其他各顶点的最短路径，要求写出每一步的距离更新过程。4.构造一个哈希表存储关键字序列{18,37,46,10,62,25,55}，哈希函数为H(key)=keymod7，采用线性探测法处理冲突（探测序列为i,i+1,...,m-1,0,1,...，m为表长），表长m=11。要求：（1）画出哈希表的存储结构；（2）计算查找成功时的平均查找长度（ASL）。四、算法设计题（每题10分，共20分）1.设计一个算法，在双向链表（每个节点含prior和next指针）中，将值为x的节点插入到值为y的节点之前（若y不存在则插入到表尾）。要求用伪代码描述，并说明关键步骤。2.已知平衡二叉树（AVL树）中某节点A发生了LL型失衡（左孩子的左子树插入导致失衡），设计算法对该树进行调整，要求画出调整前后的结构示意图，并给出旋转操作的具体步骤。答案一、单项选择题1.C（顺序表若在表尾插入，时间复杂度为O(1)，A错误；单链表删除已知节点需修改前驱指针，若无前驱指针则无法O(1)，B错误；循环链表尾指针可直接访问头节点，D错误）2.B（3,2出栈后，栈内剩1，此时下一个出栈只能是1或继续入栈4、5。若出5，则栈内应为1、4，此时出1需先出4，因此B中“5,1”顺序不可能）3.A（完全二叉树节点数n=768，最后一个分支节点为⌊n/2⌋=384，故叶子节点数为n-384=384）4.D（带权图的邻接矩阵中，非零元素可直接表示边权，D错误）5.C（二分查找最坏情况为O(logn)）6.C（快速排序可能交换相同元素的相对顺序，不稳定）7.B（装填因子固定时，处理冲突的方法决定了平均查找长度）8.B（线索二叉树的右线索指向中序后继）9.C（拓扑排序仅适用于有向无环图，结果可能不唯一，C正确）10.B（AVL树最小高度近似为1.44log₂(n+2)）二、填空题1.[3,2]（操作步骤：addFront(1)→[1]；addRear(2)→[1,2]；addFront(3)→[3,1,2]；deleteFront()→[1,2]；addRear(4)→[1,2,4]；deleteRear()→[1,2]。注意双端队列队头为前端，队尾为后端）2.DEBFGCA（先序根为A，中序分割左子树D、B、E，右子树F、C、G；递归构建后序）3.该顶点邻接表中的边数；所有顶点的邻接表（统计指向该顶点的边）4.先将整个序列分成若干子序列分别排序，再逐步合并；增量序列（步长序列）5.装填因子；冲突的探测顺序（或开放定址的方法）6.n-1；m-(n-1)三、应用题1.算法步骤：初始化三个指针：prev=NULL，curr=head，next=NULL。遍历链表，每次保存curr的下一个节点（next=curr→next）。将curr的next指向prev（反转指针）。移动prev和curr（prev=curr，curr=next）。当curr为NULL时，prev即为新头节点。关键：通过三个指针迭代反转每个节点的next指针，无需额外空间。2.转换过程：初始栈空，输出空。扫描'3'→输出[3]，栈[]。扫描'+'→栈空，入栈，栈[+]，输出[3]。扫描'5'→输出[3,5]，栈[+]。扫描''→优先级高于栈顶'+'，入栈，栈[+,]，输出[3,5]。扫描'('→入栈，栈[+,,(]，输出[3,5]。扫描'6'→输出[3,5,6]，栈[+,,(]。扫描'-'→栈顶为'(',入栈，栈[+,,(,-]，输出[3,5,6]。扫描'2'→输出[3,5,6,2]，栈[+,,(,-]。扫描')'→弹出栈内元素直到'('：弹出'-'→输出[3,5,6,2,-]，弹出'('（不输出），栈[+,]。扫描'/'→优先级等于栈顶''（左结合），弹出''→输出[3,5,6,2,-,]，入栈'/'，栈[+,/]。扫描'4'→输出[3,5,6,2,-,,4]，栈[+,/]。扫描'-'→优先级低于栈顶'/'，弹出'/'→输出[3,5,6,2,-,,4,/]，再比较栈顶'+'（优先级相同），弹出'+'→输出[3,5,6,2,-,,4,/,+]，入栈'-'，栈[-]。扫描'1'→输出[3,5,6,2,-,,4,/,+,1]。扫描结束，弹出栈中剩余'-'→输出[3,5,6,2,-,,4,/,+,1,-]。最终后缀表达式：35624/+1-。3.Dijkstra算法步骤（初始距离数组：A→A=0，其他为∞）：第1步：选A（距离0），更新邻接点：B(2)、C(5)，距离数组：B=2，C=5，D=∞，E=∞。第2步：选B（最小距离2），更新邻接点：A(已处理)、C(1+2=3<5→更新为3)、D(4+2=6)，距离数组：C=3，D=6，E=∞。第3步：选C（最小距离3），更新邻接点：A(已处理)、B(已处理)、D(3+3=6，不小于当前6)、E(3+6=9)，距离数组：D=6，E=9。第4步：选D（最小距离6），更新邻接点：B(已处理)、C(已处理)、E(6+2=8<9→更新为8)，距离数组：E=8。第5步：选E（最小距离8），无未处理邻接点。最终最短路径：A→B=2，A→B→C=3，A→B→D=6，A→B→D→E=8。4.（1）哈希表存储结构（下标0-10）：H(18)=18mod7=4→下标4（空，存入）。H(37)=37mod7=2→下标2（空，存入）。H(46)=46mod7=4（冲突），探测4+1=5→下标5（空，存入）。H(10)=10mod7=3→下标3（空，存入）。H(62)=62mod7=62-78=62-56=6→下标6（空，存入）。H(25)=25mod7=4（冲突），探测4→已占，5→已占，6→已占，7→下标7（空，存入）。H(55)=55mod7=55-77=55-49=6（冲突），探测6→已占，7→已占，8→下标8（空，存入）。哈希表：下标：012345678910关键字：37101846622555（2）ASL计算（查找次数：18→1次，37→1次，46→2次，10→1次，62→1次，25→4次，55→3次）：ASL=(1+1+2+1+1+4+3)/7=13/7≈1.86。四、算法设计题1.伪代码：functioninsertBeforeX(head,x,y):newNode=createNode(x)ifheadisnull:head=newNodereturnheadcurrent=headprev=null//查找y的位置whilecurrentisnotnullandcurrent.data!=y:prev=currentcurrent=current.nextifcurrentisnull://y不存在，插入表尾prev.next=newNodenewNode.prior=prevnewNode.next=nullelse://y存在，插入到current之前newNode.next=currentnewNode.prior=current.priorifcurrent.priorisnotnull:current.prior.next=newNodeelse://current是头节点head=newNodecurrent.prior=newNodereturnhead关键步骤：（1）遍历查找y的位置；（2）处理y不存在时插入表尾（修改前一个节点的next和新节点的prior）；（3）处理y存在时插入到其前（修改前驱节点的next、当前节点的prior及新节点的前后指针）。2.调整步骤（LL型失衡：节点A的左孩子B的左子树插入新节点导致A的平衡因子≥2）：