湖南财政经济学院《数据结构课程设计》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页湖南财政经济学院

《数据结构课程设计》2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的顺序表中，删除第i个元素（1<=i<=n），需要移动的元素个数最多为（）。A.i-1B.n-iC.n-i+1D.n-12、在一个哈希表中，负载因子越大，说明什么？A.哈希冲突越少B.存储空间利用率越高C.查找效率越高D.以上都不对3、在一个具有n个元素的二叉排序树中，查找一个不存在的元素，其时间复杂度最坏情况下为？（）A.O(1)B.O(log₂n)C.O(n)D.O(n²)4、在一个具有n个顶点的无向图中，若采用邻接矩阵存储，则矩阵中非零元素的个数至少为？（）A.nB.n-1C.2(n-1)D.n(n-1)/25、对于一个具有n个元素的冒泡排序，若元素基本有序，其时间复杂度接近？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)6、在一个具有n个元素的顺序存储的循环队列中，队满的条件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front7、设有一个长度为n的顺序表，要在第i个元素之前插入一个新元素，并且移动元素的平均次数为n/2，则插入算法的平均时间复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)8、在一个具有n个元素的队列中，若要获取队头元素的前一个元素但不删除，以下操作不可行的是？（）A.遍历整个队列B.使用辅助数据结构C.直接获取D.以上都不可行9、以下哪种数据结构可以高效地支持集合的并、交、差等操作？A.二叉搜索树B.哈希表C.并查集D.平衡二叉树10、若一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBDAEGF，则其后序遍历序列为？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF11、在一个具有n个元素的顺序存储的线性表中，删除第i个元素（1<=i<=n），需要移动多少个元素？（）A.n-iB.iC.n-i+1D.n-i-112、在一个具有n个元素的最小堆中，插入一个新元素后，为了重新调整为最小堆，最坏情况下需要比较多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、对于一个具有n个节点的红黑树，插入一个新节点后，调整树的结构以保持红黑树性质，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一个带头结点的单链表中，若要删除表中所有值为x的结点，最优的算法时间复杂度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)15、已知一个图的邻接表存储结构，若要判断任意两个顶点之间是否存在边，哪种方法最有效？（）A.遍历邻接表B.建立逆邻接表C.建立邻接矩阵D.深度优先搜索16、在一棵度为4的树中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个叶子节点，那么这棵树的总节点数是多少？A.82B.81C.79D.7817、栈和队列的操作可以用栈和队列的基本操作来实现，以下关于它们的操作实现的说法中，错误的是？（）A.可以用两个栈实现一个队列，也可以用两个队列实现一个栈。B.用栈实现队列时，需要考虑队列的先进先出特性，可能需要使用辅助栈。C.用队列实现栈时，需要考虑栈的后进先出特性，可能需要使用辅助队列。D.栈和队列的操作只能用栈和队列的基本操作来实现，不能用其他数据结构来辅助实现。18、以下哪种数据结构常用于实现图的广度优先遍历的辅助队列？A.循环队列B.链队列C.优先队列D.双端队列19、对于一个具有n个元素的堆，若要将其所有元素从小到大排序，最好的方法是？A.每次删除堆顶元素并调整B.直接使用快速排序C.先构建大顶堆再调整D.以上方法效率相同20、图的存储方式和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.图的邻接矩阵可以用于表示网络中的连接关系，适用于社交网络分析和交通网络规划等。B.图的邻接表可以用于表示稀疏图，适用于地图绘制和电路图设计等。C.图的遍历方式可以用于解决路径规划、网络流问题和最小生成树问题等，适用于物流配送和通信网络优化等。D.图的存储方式和遍历方式只适用于理论研究，在实际应用中没有实际价值。二、简答题（本大题共4个小题，共40分)1、（本题10分）论述AVL树在空间利用效率方面的特点和优化方法。2、（本题10分）论述哈希表的冲突解决方法，如线性探测法、二次探测法和链地址法，并分析它们的优缺点。3、（本题10分）详细说明如何对一个二叉搜索树进行中序遍历的非递归实现，分析其时间和空间复杂度。4、（本题10分）对于一个用邻接矩阵存储的有向图，说明如何判断图是否强连通，给出一种有效的算法并分析其时间复