湖南城市学院《数据结构A》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页湖南城市学院

《数据结构A》2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的单链表中，若要在第i个位置（1<=i<=n）插入一个新元素，平均需要遍历多少个节点？（）A.i-1B.iC.(i-1)/2D.i/22、对于一个具有n个节点的平衡二叉树，插入一个新节点并调整平衡，其平均时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在一个具有n个顶点的有向无环图中，使用拓扑排序算法，其结果的唯一性如何？A.一定唯一B.可能不唯一C.取决于顶点的编号D.以上都不对4、以下哪种数据结构能够在O(1)的时间复杂度内实现元素的随机访问？（）A.链表B.队列C.栈D.数组5、对于一个用数组实现的最小堆，若要删除堆顶元素并调整堆，以下操作正确的是？（）A.将堆尾元素移到堆顶，然后从堆顶向下调整B.将堆顶元素与堆尾元素交换，然后从堆顶向下调整C.将堆顶元素删除，然后重新构建堆D.以上都不对6、在一个m行n列的二维数组中，按列优先存储时，元素aij的存储地址为？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d7、栈和队列的应用场景非常广泛，以下关于它们的应用的说法中，错误的是？（）A.栈可以用于实现函数调用、表达式求值和括号匹配等。B.队列可以用于实现任务调度、消息队列和广度优先搜索等。C.栈和队列可以用于实现图的深度优先搜索和广度优先搜索。D.栈和队列只适用于计算机科学领域，在其他领域没有实际价值。8、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则存储空间的复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)9、对于一个具有n个节点的红黑树，插入一个新节点后，调整树的结构以保持红黑树性质，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一个字符串中，要查找某个子串首次出现的位置，通常可以使用哪种算法？（）A.冒泡排序B.快速排序C.顺序查找D.二分查找11、对于一个具有n个元素的有序链表，若要在其中查找一个特定元素，其平均时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)12、对于一个循环队列，若队头指针为front，队尾指针为rear，队列最大容量为MAX_SIZE，那么判断队空的条件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-113、在图的最小生成树算法中，Kruskal算法和Prim算法都能得到最小生成树，以下关于这两个算法的比较，错误的是（）A.Kruskal算法基于边，Prim算法基于节点B.Kruskal算法需要使用并查集C.Prim算法的时间复杂度通常比Kruskal算法低D.对于稀疏图，Kruskal算法更优14、在一个具有n个顶点和e条边的无向图中，使用邻接矩阵存储，进行深度优先遍历，其时间复杂度为？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)15、在一棵度为4的树中，度为4的节点个数为1，度为3的节点个数为2，度为2的节点个数为3，度为1的节点个数为4，叶子节点个数为（）。A.15B.16C.17D.1816、以下哪种数据结构适合用于实现一个可以快速查找最大值和最小值的数据集合？A.链表B.栈C.队列D.堆17、对于一个具有n个元素的大顶堆，若要获取堆中的第k大元素（1<=k<=n），以下哪种方法效率较高？A.先排序再获取B.每次删除堆顶元素k-1次C.构建一个大小为k的小顶堆，然后逐步替换D.以上方法效率相同18、对于一个具有n个顶点和e条边的无向图，采用邻接表存储时，其空间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)19、在一个具有n个元素的双向链表中，若要删除尾结点，需要修改几个指针？（）A.1B.2C.3D.420、已知一个具有n个顶点的无向图采用邻接矩阵存储，若要删除所有的边，时间复杂度为？（）A.O(n)B.O(n²)C.O(nlogn)D.O(e)二、简答题（本大题共4个小题，共40分)1、（本题10分）链表的插入和删除操作与数组相比有哪些优势？请举例说明。2、（本题10分）解释在平衡二叉搜索树中，如何通过平衡调整操作减少节点的移动次数。3、（本题10分）比较快速排序和冒泡排序在最好情况下的性能表现。4、（本题10分）比较计数排序和冒泡排序在处理大量重