衡阳师范学院《数据结构》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页衡阳师范学院《数据结构》

2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个B树中，每个节点的关键字数量最少为多少？（）A.1B.2C.⌈m/2⌉-1D.m-12、对于一个具有n个元素的顺序存储的循环队列，队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，若队列非空，则队列中元素的个数为？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+13、对于一个有向无环图，进行拓扑排序可以得到一个线性的序列。以下关于拓扑排序的说法，错误的是？（）A.可以使用深度优先搜索来实现B.结果可能不唯一C.若存在回路则无法进行拓扑排序D.其时间复杂度为O(n²)4、在一个链式存储的栈中，若栈顶指针为top，要判断栈是否为空，应判断？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL5、对于一个具有n个元素的堆，进行插入操作的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一个有向图中，所有顶点的入度之和与出度之和的关系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.没有确定的关系7、对于一个具有n个节点的红黑树，插入一个新节点后，调整树的结构以保持红黑树性质，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一个具有n个顶点的有向强连通图中，至少需要多少条边？（）A.n-1B.nC.n(n-1)/2D.n(n-1)9、在一个具有n个元素的最小堆中，插入一个新元素后，为了重新调整为最小堆，最坏情况下需要比较多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)10、在一个具有n个元素的顺序表中，删除第i个元素（1<=i<=n），平均需要移动的元素个数约为？A.n/2B.n-iC.iD.n-i+111、二叉树是一种重要的数据结构，具有多种遍历方式。对于先序遍历、中序遍历和后序遍历，以下描述错误的是（）A.先序遍历先访问根节点，然后递归遍历左子树和右子树B.中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树C.后序遍历先递归遍历左子树和右子树，最后访问根节点D.这三种遍历方式的结果总是相同的12、若要对100个元素进行排序，以下哪种排序算法在最坏情况下的时间复杂度最低？A.冒泡排序B.选择排序C.插入排序D.归并排序13、对于一个具有n个元素的有序单链表，若要在其中查找一个特定元素，其平均时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、以下哪种数据结构在处理频繁的插入和删除操作时，不需要移动大量元素？（）A.数组B.链表C.栈D.队列15、在数据结构中，斐波那契堆是一种可合并堆，以下关于斐波那契堆的特点，描述不正确的是（）A.插入操作的时间复杂度为O(1)B.查找最小元素的时间复杂度为O(1)C.删除最小元素的时间复杂度为O(logn)D.合并操作的时间复杂度为O(n)16、在一个循环队列中，队头指针为front，队尾指针为rear，队列最大容量为MAXSIZE，若rear>front，则队列中的元素个数为？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE17、以下哪种数据结构可以快速查找一个有序数组中的中位数？A.二叉搜索树B.堆C.哈希表D.链表18、在一个具有n个顶点的有向完全图中，边的数量为：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)19、一个有序序列为{12,18,24,35,47,50,62,83,90,115,134}，当用二分法查找值为90的元素时，需要比较的次数是（）。A.1B.2C.3D.420、在一个具有n个元素的双向链表中，删除一个指定节点，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）论述如何使用动态规划算法解决最长公共子串问题。2、（本题10分）详细说明选择排序算法的基本思想和在最坏情况下的时间复杂度分析。3、（本题10分）解释在平衡二叉搜索树中，删除操作可能导致的不平衡情况及相应的调整方法。4、（本题10分）论述如何使用分治法解决最大子数