ACM数据结构试题与答案解析

ACM数据结构试题与答案解析考试时间：______分钟总分：______分姓名：______选择题1.下列关于顺序表和链表的描述，正确的是（）A.顺序表的插入和删除操作时间复杂度均为O(1)B.链表的随机访问时间复杂度为O(1)C.顺序表需要预分配存储空间，链表按需分配D.链表相比顺序表，更适合频繁插入但访问较少的场景2.在包含n个节点的平衡二叉树（AVL树）中，插入一个新节点可能导致失衡，最坏情况下需要旋转的次数是（）A.1次B.2次C.O(logn)次D.O(n)次3.下列排序算法中，时间复杂度与初始序列无关的是（）A.快速排序B.冒泡排序C.堆排序D.插入排序4.在栈的应用中，表达式求值通常使用（）A.前缀表达式B.中缀表达式C.后缀表达式D.逆波兰表达式5.队列的循环队列实现中，判队满的条件是（）A.rear==frontB.rear==front-1C.rear==maxsize-1D.rear==front&&rear!=06.在二叉树的层序遍历中，使用的数据结构是（）A.栈B.队列C.哈希表D.优先队列7.图的邻接表存储中，查找一个顶点的所有邻接顶点的时间复杂度是（）A.O(1)B.O(n)C.O(e)D.O(n^2)8.哈希表的负载因子α增大时，平均查找长度（）A.减小B.增大C.不变D.不确定9.在快速排序的partition过程中，基准元素的选择影响算法效率，最坏情况下时间复杂度为（）A.O(n)B.O(nlogn)C.O(n^2)D.O(2^n)10.下列数据结构中，支持动态扩容的是（）A.顺序表B.链表C.静态数组D.栈填空题1.快速排序的partition过程中，选取最后一个元素为基准，将小于基准的元素移到左侧，大于基准的移到右侧。若初始序列为`[3,1,4,1,5,9,2,6]`，第一趟partition后的结果为______，基准的最终位置为______。2.已知一棵二叉树的前序遍历为`ABDEHCFIG`，中序遍历为`DBHEAFICG`，其后序遍历结果为______。3.在包含n个顶点的带权无向图中，使用Prim算法求最小生成树的时间复杂度为______（用邻接矩阵存储）______（用邻接表存储）。4.哈希表的负载因子α=______，当α增大时，链地址法查找成功的平均查找长度为______。5.在Dijkstra算法中，若使用优先队列优化，时间复杂度为______（e为边数）。编程题1.二叉树的直径给定一棵二叉树的根节点`root`，计算树的直径。二叉树的直径是树中任意两个节点路径长度中的最大值。该路径可能经过根节点，也可能不经过根节点。路径长度=边数（即节点数-1）。示例：输入：`root=[1,2,3,4,5]`输出：3解释：最长路径为`4-2-1-3`或`5-2-1-3`，长度为3（边数）。2.Dijkstra算法求单源最短路径给定一个带权有向图`graph`，其中`graph[i][j]`表示顶点`i`到顶点`j`的边的权值（若不存在边，权值为-1）。给定源顶点`src`，计算从`src`到其他所有顶点的最短路径，返回一个数组`dist`，其中`dist[i]`表示`src`到`i`的最短路径长度，若不可达则返回-1。示例：输入：`graph=[[0,2,1,-1],[1,0,3,4],[1,1,0,1],[-1,-1,-1,0]]`，`src=0`输出：`[0,2,1,2]`解释：0→2→3（长度1+1=2），0→1（长度2），0→2（长度1）。试卷答案选择题1.D解析：顺序表在中间插入删除需移动元素，时间复杂度O(n)；链表随机访问需遍历，O(n)；顺序表需预分配空间，链表动态分配但需额外存储指针；链表插入只需修改指针，适合频繁插入，故D正确。2.B解析：AVL树插入节点后最多失衡2层，每次失衡需1-2次旋转，最坏2次，与n无关，故选B。3.C解析：快速排序最坏O(n²)，冒泡和插入排序最坏O(n²)，堆排序无论初始序列均为O(nlogn)，故选C。4.C解析：表达式求值通常使用后缀表达式（逆波兰表达式），因为它不需要括号且易于用栈处理。5.D解析：循环队列判队满条件为rear==front且rear!=0（牺牲一个空间），故选D。6.B解析：层序遍历按层次从上到下、从左到右，需队列实现，故选B。7.C解析：邻接表中每个顶点对应一个链表，查找邻接顶点需遍历链表，时间复杂度与该顶点的度数相关，平均为O(e/n)，但最坏为O(n)（若一个顶点连接所有顶点），但通常认为O(e)（e为边数）。8.B解析：负载因子α=表中元素数/表长度，α增大意味着冲突增多，平均查找长度增大（链地址法为1+α/2）。9.C解析：快速排序最坏情况（如初始序列有序或逆序）每次partition只能划分一个元素，时间复杂度O(n²)。10.B解析：顺序表和静态数组需要预分配空间，栈通常基于顺序表实现（静态扩容），但链表本身支持动态扩容（插入时动态分配节点），故选B。填空题1.[3,1,4,1,5,2,6,9]，6（索引6）解析：基准为最后一个元素6，partition过程将小于6的移到左侧，大于6的移到右侧，最终基准位置在索引6。2.DHEBIFGCA解析：根据前序和中序遍历递归重建二叉树，后序遍历为左右根，重建过程为：根A，左子树DBHE（根B，左D，右HE（根E，左H）），右子树FICG（根F，左I，右CG（根G，左C）），后序为左子树DHEB，右子树IFGC，根A，组合为DHEBIFGCA。3.O(n²)，O(e+nlogn)解析：邻接矩阵需遍历所有顶点找最小权值，O(n²)；邻接表用优先队列，每次操作O(logn)，共e条边，O(e+nlogn)。4.表中记录数/表长度，1+α/2解析：负载因子α=表中记录数/表长度，链地址法查找成功的平均查找长度为1+α/2。5.O(elogn)解析：使用优先队列优化Dijkstra算法，每条边最多入队一次，每次堆操作O(logn)，共e条边，O(elogn)。编程题1.二叉树的直径代码：classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightclassSolution:defdiameterOfBinaryTree(self,root:TreeNode)->int:self.max_diameter=0defdepth(node):ifnotnode:return0left_depth=depth(node.left)right_depth=depth(node.right)self.max_diameter=max(self.max_diameter,left_depth+right_depth)returnmax(left_depth,right_depth)+1depth(root)returnself.max_diameter解析：递归计算每个节点的左右子树深度，同时更新最大直径（左右深度之和），返回最大值。2.Dijkstra算法求单源最短路径代码：importheapqdefdijkstra(graph,src):n=len(graph)dist=[float('inf')]*ndist[src]=0heap=[(0,src)]visited=set()whileheap:current_dist,u=heapq.heappop(heap)ifuinvisited:continuevisited.add(u)forvinrange(n):ifgraph[u][v]!=-1andvnotinvisited:new_dist=current_dist+graph[u][v]ifnew_dist<dist[v]:dist[v]=new_distheapq.hea