南京工程学院《数据结构》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页南京工程学院

《数据结构》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一棵AVL树中，进行插入操作后，可能导致树失去平衡，此时需要进行的旋转操作最多为（）A.1次B.2次C.logn次D.n次2、线段树是一种用于处理区间查询和更新的数据结构。对于线段树的应用，以下说法错误的是（）A.可以快速计算给定区间内元素的和B.可以用于查找区间内的最大值和最小值C.构建线段树的时间复杂度为O(n)D.线段树的空间复杂度与节点数量成正比3、在一个具有n个元素的顺序表中，若要在第i个位置（1<=i<=n+1）插入一个新元素，需要移动的元素个数最少为（）。A.0B.i-1C.n-iD.n-i+14、设有一个20阶的下三角矩阵A，采用压缩存储方式，以行序为主存储其非零元素，第一个非零元素A[1,1]存储在数组B[0]中，若A[10,5]在数组B中的存储位置为k，则A[8,5]在数组B中的存储位置为（）。A.k-18B.k-17C.k-16D.k-155、AVL树是一种高度平衡的二叉搜索树，以下关于AVL树的旋转操作，描述不正确的是（）A.旋转操作用于保持树的平衡B.包括单旋转和双旋转两种类型C.旋转操作不会改变二叉搜索树的性质D.每次插入或删除节点都需要进行旋转操作6、在一个具有n个元素的顺序存储的循环队列中，队满的条件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front7、以下关于图的最短路径算法的描述，哪一项是正确的？（）A.Dijkstra算法不能处理负权边B.Floyd算法的时间复杂度低于Dijkstra算法C.所有最短路径算法都能在有向图和无向图中使用D.最短路径一定是唯一的8、以下关于哈希冲突解决方法中二次探测法的描述，哪一项是不正确的？（）A.可以减少聚集现象B.探测的位置是连续的C.可能会出现找不到空闲位置的情况D.相比线性探测法，性能更优9、哈希表是一种用于快速查找的数据结构，通过哈希函数将关键字映射到存储位置。关于哈希冲突的解决方法，错误的是（）A.开放定址法通过寻找空闲位置来解决冲突B.链地址法将冲突的元素存储在链表中C.再哈希法通过更换哈希函数来解决冲突D.哈希冲突无法避免，且对查找效率没有影响10、对于一个具有n个元素的哈希表，负载因子（loadfactor）为0.7，当表中元素数量超过一定阈值时需要进行扩容。以下关于扩容操作的时间复杂度的描述，哪一个是恰当的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)11、以下哪种数据结构常用于实现LRU（最近最少使用）缓存淘汰策略？（）A.队列B.栈C.哈希表D.双向链表12、设有一个循环队列，存储空间为Q[0..m-1]，初始时front=rear=m。现经过一系列入队与退队操作后，front=20，rear=15，则此时队列中的元素个数为（）。A.5B.6C.m-5D.m+513、在一个循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，队列最大容量为MAXSIZE，若当前队列长度为n，则判断队满的条件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE14、以下关于树的存储结构的描述，哪一项是不正确的？（）A.孩子兄弟表示法可以方便地实现树的遍历B.双亲表示法便于查找一个节点的双亲节点C.孩子链表表示法在处理多叉树时空间利用率较高D.以上存储结构在时间复杂度上没有明显差异15、以下哪种数据结构能够高效地支持区间查询操作？（）A.线段树B.二叉搜索树C.堆D.链表16、对于一个具有n个顶点和e条边的无向图，采用邻接表存储时，其空间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)17、对于一个具有n个顶点和e条边的有向完全图，其弧的条数为（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/218、在数据结构中，双向循环链表相较于单向链表，以下优势描述错误的是（）A.可以方便地反向遍历B.插入和删除节点的操作更简单C.查找前一个节点的时间复杂度更低D.空间复杂度更低19、在一个具有n个顶点的有向图中，若存在环，则使用拓扑排序算法会？A.正常排序B.无法排序C.部分排序D.排序结果不确定20、在一个有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比较的次数是：A.1B.2C.3D.4二、简答题（本大题共4个小题，共40分)1、（本题10分）深入分析在一个具有n个元素的顺序表中，如何进行桶排序。2、（本题10分）解释什么是字典树，并说明其在单词查找和统计中的应用。3、（本题10分）阐述如何在一个具有n个元素的无序数组中，使用冒泡排序算法进行排序，并分析其时间复杂度和空间复杂度。4、（本题10分）解释什么是后缀数组数据结构，说明其构建过程和应用场景，并阐述如何进行