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

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

《数据结构与算法》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的栈中，若要获取栈底元素但不删除，需要进行多少次操作？（）A.1B.n-1C.nD.n+12、在一个具有n个顶点的无向图中，若采用邻接矩阵存储，则存储空间复杂度为？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)3、在一个具有n个节点的有向图中，若存在多个入度为0的节点，进行拓扑排序时，应该选择哪个节点作为起始节点？A.任意一个入度为0的节点B.编号最小的入度为0的节点C.编号最大的入度为0的节点D.以上都不对4、在一个链式存储的线性表中，若要删除第i个元素（1<=i<=n），需要找到其前驱节点的时间复杂度为？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)5、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则存储空间的复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)6、在一个用邻接表表示的无向图中，若要删除一条边，需要进行哪些操作？A.在两个相关顶点的邻接表中删除对应的边节点B.只在一个顶点的邻接表中删除对应的边节点C.重新构建邻接表D.以上都不对7、在一个具有n个元素的顺序表中，若要在第i个元素之前插入一个新元素，平均需要移动多少个元素？（）A.n/2B.nC.iD.n-i8、对于一个循环队列，若队头指针为front，队尾指针为rear，队列最大容量为MAX_SIZE，那么判断队空的条件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-19、以下关于字符串匹配的BM算法的描述，哪一项是不正确的？（）A.从模式串的尾部开始匹配B.利用了坏字符和好后缀规则C.在一般情况下比KMP算法效率低D.可以通过预处理提高匹配速度10、哈希表的冲突解决方法和性能优化可以用于提高哈希表的效率，以下关于它们的说法中，错误的是？（）A.开放定址法和链地址法是哈希表的两种主要冲突解决方法，它们各有优缺点。B.可以通过调整哈希函数、增加哈希表的大小和采用二次探测等方法来优化哈希表的性能。C.哈希表的性能优化需要根据实际情况进行选择，不同的应用场景可能需要不同的优化方法。D.哈希表的冲突解决方法和性能优化只适用于理论研究，在实际应用中没有实际价值。11、若要对n个元素进行快速排序，在最坏情况下，其时间复杂度为？（）A.O(n)B.O(log₂n)C.O(nlog₂n)D.O(n²)12、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储其下三角部分，第一个元素A[1,1]存储在数组B[0]中，若A[8,5]在数组B中的存储位置为k，则A[7,5]在数组B中的存储位置为（）。A.k-13B.k-12C.k-11D.k-1013、对于一个具有n个元素的堆，进行堆排序。以下关于堆排序的平均时间复杂度和空间复杂度的描述，哪一个是准确的？A.平均时间复杂度为O(nlogn)，空间复杂度为O(1)B.平均时间复杂度为O(n^2)，空间复杂度为O(n)C.平均时间复杂度为O(logn)，空间复杂度为O(logn)D.平均时间复杂度为O(n)，空间复杂度为O(n)14、以下关于图的深度优先搜索和广度优先搜索的描述，哪一项是正确的？（）A.深度优先搜索使用队列实现B.广度优先搜索使用栈实现C.两种搜索算法都可以用于判断图是否连通D.深度优先搜索一定能找到最短路径15、在循环链表中，尾指针rear指向链表的尾节点，若要在链表中插入一个新的节点，使其成为新的尾节点，以下操作正确的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;16、对于一个具有n个元素的有序链表，若要在其中插入一个新元素并保持有序，平均需要移动的元素个数为？（）A.n/2B.nC.lognD.nlogn17、对于一个具有n个节点的二叉树，其高度的最小值和最大值分别是多少？（）A.log₂n,n-1B.1,nC.log₂n,nD.1,n-118、在一个具有n个节点的图中，使用深度优先搜索算法遍历所有节点，其时间复杂度主要取决于什么？A.边的数量B.节点的数量C.图的存储方式D.以上都是19、对于一个具有n个节点的完全二叉树，若底层从左到右填充，则第i个节点的左孩子节点的编号为？A.2iB.2i+1C.i*2D.i*2+120、对于一个具有n个元素的无序数组，使用冒泡排序进行排序，最坏情况下的比较次数为？A.n(n-1)/2B.nlognC.n^2D.2^n二、简答题（本大题共4个小题，共40分)1、（本题10分）描述二叉树的层次遍历方法，并说明其实现思路。2、（本题10分）解释一下什么是栈，并说明栈的基本操作（入栈、出栈）的实现原理。同时，举例说明栈在表达式求值和括号匹配中的应用。3、（本题10分）论述如何在一个有向图中计算强连通分量，给出具体的算法步骤。4、（本题10分）解释在平衡二叉搜索树中，删除操作后如何恢复树的平