湖南工商大学《数据结构与算法分析》2022-2023学年期末试卷

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

《数据结构与算法分析》2022-2023学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个元素的哈希表，负载因子越大，发生冲突的可能性如何变化？（）A.越大B.越小C.不变D.不确定2、在一个字符串匹配算法中，BM算法相对于朴素的字符串匹配算法，其优势在于？（）A.平均性能更好B.代码更简洁C.空间复杂度更低D.适用于短字符串匹配3、在一个用邻接矩阵存储的图中，若要判断两个节点是否相邻，时间复杂度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)4、对于一个具有n个元素的双向循环链表，若要删除第i个节点（1<=i<=n），平均需要修改多少个指针？（）A.2B.3C.4D.55、图的存储方式和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.图的邻接矩阵可以用于表示网络中的连接关系，如社交网络、交通网络等。B.图的邻接表可以用于表示稀疏图，如地图、电路图等。C.图的遍历方式可以用于解决路径规划、网络流问题和最小生成树问题等。D.图的存储方式和遍历方式只适用于理论研究，在实际应用中没有实际价值。6、深度为5的满二叉树的结点数为：A.16B.31C.32D.157、在一个带头结点的双向链表中，若要在p所指结点之后插入一个新结点q，需要修改几个指针？（）A.2B.4C.6D.88、以下关于红黑树的性质，错误的是：A.每个节点要么是红色，要么是黑色B.根节点是黑色的C.每个叶子节点（NIL节点）是黑色的D.红色节点的子节点一定是红色的9、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储其下三角部分，第一个元素A[1,1]存储在数组B[0]中，若A[8,5]在数组B中的存储位置为k，则A[7,5]在数组B中的存储位置为（）。A.k-13B.k-12C.k-11D.k-1010、以下哪种排序算法在元素基本有序的情况下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序11、若一个链表的每个节点只包含数据域和指针域，且指针域只指向其后继节点，这种链表称为：A.单向链表B.双向链表C.循环链表D.静态链表12、在一个顺序存储的队列中，若要在队尾插入一个元素，需要移动元素的平均次数为（）A.0B.n/2C.nD.n-113、以下关于字符串压缩算法的描述，哪一项是不正确的？（）A.哈夫曼编码可以根据字符出现频率进行压缩B.LZW压缩算法基于字典进行压缩C.压缩算法一定能减小字符串的存储空间D.不同的压缩算法适用于不同类型的字符串14、在一个具有n个元素的最大堆中，插入一个新元素后，为了恢复堆的性质，需要进行的调整操作的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、在一个具有n个元素的堆中，查找最大元素的时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)16、在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的方法。以下关于它们的描述，错误的是（）A.DFS使用栈来保存未访问的节点B.BFS使用队列来保存未访问的节点C.DFS可能会陷入死循环D.BFS一定能找到最短路径17、对于一个具有n个元素的循环队列，队头指针为front，队尾指针为rear，队列满的条件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front18、在一个具有n个节点的无向图中，若边的数量远远小于n(n-1)/2，则适合使用哪种存储方式？A.邻接矩阵B.邻接表C.十字链表D.以上都可以19、对于一个大根堆，若将堆中所有元素按照层次遍历的顺序存储到一个数组中，以下关于数组元素的排列，哪一项是正确的？A.完全无序B.从左到右依次递减C.从左到右依次递增D.以上都不对20、在一个具有n个节点的图中，使用弗洛伊德算法求所有节点对之间的最短路径，其时间复杂度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)二、简答题（本大题共4个小题，共40分)1、（本题10分）比较快速排序和插入排序在对重复元素较多的数据处理情况。2、（本题10分）详细阐述在图的广度优先遍历算法中，如何使用队列来实现，并说明其应用场景。3、（本题10分）详细阐述在具有n个顶点的无向图中，如何使用广度优先搜索算法判断两个顶点是否连通，并给出具体的算法步骤和代码实现。4、（本题10分）详细阐述如何在一个字符串中查找所有由相同字符组成的子串。三、设计题（本大题共2个小题，共20分)1、（本题10分）设计一个程