成都锦城学院《数据结构与算法分析》2022-2023学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页成都锦城学院《数据结构与算法分析》

2022-2023学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的双向链表中，若要删除尾结点，需要修改几个指针？（）A.1B.2C.3D.42、对于一个栈，进行入栈和出栈操作时，若栈顶指针top初始值为-1，当进行5次入栈和3次出栈操作后，top的值为多少？（）A.1B.2C.3D.43、在一个具有n个顶点的有向强连通图中，至少需要多少条边？（）A.n-1B.nC.n(n-1)/2D.n(n-1)4、在图的最小生成树算法中，Kruskal算法和Prim算法都能得到最小生成树，以下关于这两个算法的比较，错误的是（）A.Kruskal算法基于边，Prim算法基于节点B.Kruskal算法需要使用并查集C.Prim算法的时间复杂度通常比Kruskal算法低D.对于稀疏图，Kruskal算法更优5、对于一个具有n个元素的堆，进行删除操作并调整堆的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、以下哪种数据结构在查找、插入和删除操作的综合性能上表现较好？（）A.二叉搜索树B.红黑树C.B树D.哈希表7、在一个具有n个顶点的有向图中，若存在环，则使用拓扑排序算法会？A.正常排序B.无法排序C.部分排序D.排序结果不确定8、设有一个20阶的下三角矩阵A，采用压缩存储方式，以行序为主存储其非零元素，第一个非零元素A[1,1]存储在数组B[0]中，若A[10,5]在数组B中的存储位置为k，则A[8,5]在数组B中的存储位置为（）。A.k-18B.k-17C.k-16D.k-159、栈是一种特殊的线性表，遵循先进后出的原则。当一个栈已满，再进行入栈操作时，通常会发生什么情况？A.覆盖栈顶元素B.产生溢出错误C.新建一个更大的栈D.自动扩展栈的容量10、在一个m行n列的二维数组中，元素存储的地址计算公式为LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d为每个元素所占的存储单元数。若按行优先存储，则a23的地址为？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d11、对于一个具有n个元素的哈希表，负载因子（loadfactor）为0.7，当表中元素数量超过一定阈值时需要进行扩容。以下关于扩容操作的时间复杂度的描述，哪一个是恰当的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)12、数组是一种常见的数据结构，它具有固定的大小和连续的存储位置。以下关于数组的说法中，错误的是？（）A.数组可以通过下标快速访问其中的元素。B.数组的插入和删除操作比较耗时，因为需要移动大量的元素。C.数组可以存储不同类型的数据元素。D.数组的长度在创建后不能改变。13、在一个具有n个元素的顺序表中，若要在第i个位置（1<=i<=n+1）插入一个新元素，需要移动的元素个数最少为（）。A.0B.i-1C.n-iD.n-i+114、在一个具有n个顶点的无向图中，使用广度优先遍历算法。以下关于遍历过程中使用的辅助队列的空间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(n^2)15、在一个堆排序中，最大堆用于升序排序，最小堆用于降序排序。那么对于一个初始无序的数组，构建最大堆的时间复杂度是多少？（）A.O(n)B.O(log₂n)C.O(nlog₂n)D.O(n²)16、在一个具有n个元素的链表中，访问第i个元素的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、对于一个具有n个顶点的无向图，若其所有顶点的度之和为20，则该图的边数为（）。A.5B.10C.15D.2018、已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEABC，则其先序遍历序列为？（）A.CEDBAB.CEABDC.ABCDED.EACDB19、对于一个具有n个元素的有序链表，进行折半查找，其时间复杂度为？A.O(logn)B.O(nlogn)C.O(n)D.不能进行折半查找20、在一棵二叉搜索树中，删除一个有两个子节点的节点时，通常采用的方法是：A.用左子树的最大值替代该节点B.用右子树的最小值替代该节点C.随机选择左子树或右子树的节点替代D.不进行替代，直接删除二、简答题（本大题共4个小题，共40分)1、（本题10分）论述在一个具有n个顶点的无向图中，如何使用广度优先搜索算法来生成连通分量。2、（本题10分）数组的排序算法中，计数排序的实现过程是怎样的？时间复杂度和空间复杂度分别是多少？适用于哪些情况？3、（本题10分）阐述并查集中如何快速判断两个集合是否相交。4、（本题10分）在一个双向链表中，如何在指