安徽工业大学《数据结构与算法》2022-2023学年期末试卷

装订线装订线PAGE2第1页，共3页安徽工业大学

《数据结构与算法》2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种数据结构常用于实现表达式求值？A.二叉树B.栈C.队列D.哈希表2、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则其后序遍历序列为？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA3、对于一个具有n个顶点和e条边的有向图，采用邻接表存储，进行深度优先遍历。以下关于遍历的时间复杂度的描述，哪一个是恰当的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)4、已知一个图的邻接矩阵如下所示，则从顶点V1出发进行深度优先遍历，可能得到的顶点访问序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V55、以下哪种数据结构常用于实现图的存储？A.邻接矩阵和邻接表B.二叉树和链表C.栈和队列D.数组和哈希表6、对于一个具有n个顶点的无向完全图，其边的数量为多少？（）A.n(n-1)/2B.n(n-1)C.n²D.2n7、设有两个串p和q，求q在p中首次出现的位置的运算称为：A.连接B.模式匹配C.求子串D.求串长8、排序算法的稳定性和时间复杂度可以用于选择合适的排序算法，以下关于它们的说法中，错误的是？（）A.稳定性对于某些应用场景非常重要，如对具有多个关键字的记录进行排序时。B.时间复杂度是衡量排序算法效率的重要指标，不同的排序算法具有不同的时间复杂度。C.可以根据实际情况选择稳定的或不稳定的排序算法，以及时间复杂度较低的排序算法。D.排序算法的稳定性和时间复杂度只适用于理论研究，在实际应用中没有实际价值。9、对于一个具有n个元素的双向链表，若要在第i个位置（1<=i<=n）之前插入一个新节点，平均需要修改多少个指针？（）A.1B.2C.3D.410、对于一个具有n个节点的带权连通图，其最小生成树一定包含图中的所有节点吗？A.一定包含B.不一定包含C.视情况而定D.以上都不对11、以下哪种排序算法在最坏情况下的交换次数最少？A.冒泡排序B.快速排序C.选择排序D.插入排序12、在一个链式存储的队列中，若队头指针为front，队尾指针为rear，当进行一次出队操作后，front指针应该如何移动？A.front=front->nextB.front=rearC.front不变D.front=NULL13、对于一个采用链表存储的栈，若要获取栈的大小（元素数量），以下关于操作的时间复杂度的描述，哪一个是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一个具有n个元素的最小堆中，删除堆顶元素后，为了恢复堆的性质，需要进行的调整操作的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、对于一个具有n个元素的有序数组，使用二分查找算法查找一个特定元素。以下关于二分查找的时间复杂度的描述，哪一个是恰当的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、在一个B树中，每个节点的关键字数量最少为多少？（）A.1B.2C.⌈m/2⌉-1D.m-117、在一个具有n个元素的顺序表中，删除第i个元素（1<=i<=n），平均需要移动的元素个数约为？A.n/2B.n-iC.iD.n-i+118、在一个循环链表中，若要删除链表中的最后一个节点，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一个循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，队列最大容量为MAXSIZE，若当前队列长度为n，则判断队满的条件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE20、在一个用数组实现的栈中，若要将栈的容量扩大一倍，以下哪种操作的时间复杂度最低？（）A.重新创建一个更大的数组并复制元素B.逐步将元素移动到新的更大的数组中C.直接在原数组后面追加空间D.以上操作时间复杂度相同二、简答题（本大题共4个小题，共40分)1、（本题10分）解释在一个有序数组中进行二分查找的基本思路和步骤，分析其时间复杂度和空间复杂度。2、（本题10分）详细论述在一个具有n个顶点的无向图中，如何进行顶点的割点求解。3、（本题10分）数组的排序算法中，快速排序的实现过程是怎样的？时间复杂度和空间复杂度分别是多少？4、（本题10分）在一个二叉树中，如何进行前序遍历的非递归实现？三、设计