吉林大学《数据结构与算法》2023-2024学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页吉林大学《数据结构与算法》

2023-2024学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个元素的归并排序，其时间复杂度为？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)2、在一个字符串中，要查找某个子串首次出现的位置，通常可以使用哪种算法？（）A.冒泡排序B.快速排序C.顺序查找D.二分查找3、在一个具有n个元素的有序数组中，使用二分查找算法查找一个特定元素，其时间复杂度为？（）A.O(n)B.O(log₂n)C.O(n²)D.O(nlog₂n)4、在一个具有n个元素的大根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)5、已知一个有序表为{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值为35的元素，需要比较的次数是（）。A.1B.2C.3D.46、在一个用数组实现的最大堆中，若要增加一个元素并调整堆，以下操作正确的是？（）A.将元素放在堆尾，然后从堆尾向上调整B.将元素放在堆顶，然后从堆顶向下调整C.将元素插入任意位置，然后重新构建堆D.以上都不对7、对于一个具有n个元素的有序数组，若要查找某个元素是否存在，以下哪种查找算法效率最高？（）A.顺序查找B.二分查找C.分块查找D.以上算法效率相同8、在一个具有n个元素的无序数组中，使用选择排序进行排序。以下关于选择排序的时间复杂度的描述，哪一项是正确的？A.最好情况为O(n)，最坏情况为O(n^2)B.最好情况和最坏情况均为O(n)C.最好情况为O(nlogn)，最坏情况为O(n^2)D.最好情况和最坏情况均为O(n^2)9、以下关于二叉排序树的描述，错误的是：A.左子树上所有结点的值均小于根结点的值B.右子树上所有结点的值均大于根结点的值C.中序遍历二叉排序树可得到一个有序序列D.二叉排序树的查找效率总是最高的10、若要对n个元素进行快速排序，在最坏情况下，其时间复杂度为？（）A.O(n)B.O(log₂n)C.O(nlog₂n)D.O(n²)11、在数据结构中，树的遍历可以采用递归和非递归方式。以下关于非递归中序遍历二叉树的说法，错误的是（）A.可以使用栈来辅助实现B.比递归方式更复杂C.时间复杂度与递归方式相同D.空间复杂度一定比递归方式低12、在数据结构中，伸展树（SplayTree）通过自调整保持较好的性能，以下关于伸展树的操作，不正确的是（）A.查找操作会将被查找的节点旋转到根节点B.插入操作可能会引起多次旋转C.伸展树的平均性能较好D.伸展树的空间复杂度较高13、设有一个循环队列，存储空间为Q[0..m-1]，初始时front=rear=m。现经过一系列入队与退队操作后，front=20，rear=15，则此时队列中的元素个数为（）。A.5B.6C.m-5D.m+514、对于一个具有n个元素的无序数组，使用冒泡排序进行排序，最坏情况下的比较次数为？A.n(n-1)/2B.nlognC.n^2D.2^n15、在一个具有n个顶点的无向图中，若每个顶点的度均为k，则该图的边数为（）。A.nkB.nk/2C.(n-1)k/2D.(n+1)k/216、在一个具有n个节点的二叉树中，若先序遍历序列为ABC，中序遍历序列为BAC，则后序遍历序列是什么？A.BCAB.CBAC.ACBD.无法确定17、若要在一个具有n个元素的有序链表中插入一个新元素，使其仍然有序，平均时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)18、设有一个20阶的下三角矩阵A，采用压缩存储方式，以行序为主存储其非零元素，第一个非零元素A[1,1]存储在数组B[0]中，若A[10,5]在数组B中的存储位置为k，则A[8,5]在数组B中的存储位置为（）。A.k-18B.k-17C.k-16D.k-1519、在一个具有n个元素的有序双向链表中，若要在指定位置插入一个新元素，以下关于插入操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、以下关于并查集的描述，错误的是：A.并查集可以用于判断两个元素是否在同一个集合中B.并查集的查找操作时间复杂度较低C.并查集的合并操作时间复杂度较高D.并查集通常采用树形结构存储二、简答题（本大题共4个小题，共40分)1、（本题10分）解释线段树在处理区间相交问题时的思路和算法。2、（本题10分）详细阐述在图的最短路径算法中，如何处理动态的边权值变化。3、（本题10分）详细说明如何在一个带权有向图中计算源点到所有顶点的最短路径的平均长度。4、（本题10分）详细说明如何在一个图中进行最短路径的更新操作（如增加新的边或修改边的权值），给出算法步骤和实现代码，并分析其时间复杂度。三、设计题（本大题共2个小题，