北京邮电大学《数据结构与算法课程设计》2022-2023学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页北京邮电大学《数据结构与算法课程设计》

2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在图的存储结构中，邻接多重表主要用于存储无向图，以下关于邻接多重表的特点，描述错误的是（）A.可以方便地删除边B.存储空间比邻接矩阵节省C.对于判断两点之间是否有边，效率较高D.不适合用于有向图的存储2、在数据结构中，双向循环链表相较于单向链表，以下优势描述错误的是（）A.可以方便地反向遍历B.插入和删除节点的操作更简单C.查找前一个节点的时间复杂度更低D.空间复杂度更低3、若对一棵二叉搜索树进行先序遍历，得到的节点序列是一个递减序列，则该二叉搜索树（）。A.没有左子树B.没有右子树C.左子树均为空D.右子树均为空4、若一棵二叉树的先序遍历序列为ABC，中序遍历序列为BAC，则该二叉树的后序遍历序列为？（）A.BCAB.CBAC.ABCD.ACB5、对于一个具有n个节点的二叉排序树，删除一个节点后，重新调整为二叉排序树，其时间复杂度最坏情况下为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、设有一个具有n个元素的最大堆，若要获取堆中的最大元素，以下关于操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在数据结构中，字典树在处理大量字符串时，可能会出现内存占用过高的问题，以下解决方法错误的是（）A.压缩节点B.限制字典树的深度C.使用哈希表替代字典树D.减少字符串的存储8、以下哪种数据结构常用于实现LRU（最近最少使用）缓存淘汰策略？（）A.队列B.栈C.哈希表D.双向链表9、已知一个图的邻接矩阵如下所示：ABCDA0110B1011C1100D0100则该图中顶点A的度为：A.1B.2C.3D.410、在一个具有n个元素的双向链表中，若要删除尾结点，需要修改几个指针？（）A.1B.2C.3D.411、设有一个广义表L=(a,(b,c),d)，其长度和深度分别为？（）A.3和2B.3和3C.4和2D.4和312、对于一个具有n个顶点的无向图，若其边的集合为{(1,2),(1,3),(2,3),(2,4),(3,4)}，则该图的邻接表存储中，顶点2的链表中包含的顶点有：A.1,3,4B.1,3C.3,4D.1,413、设有两个串p和q，求q在p中首次出现的位置的运算称为：A.连接B.模式匹配C.求子串D.求串长14、在一个具有n个顶点和e条边的有向图中，采用邻接表存储，求顶点的入度的时间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)15、在一个具有n个顶点的强连通图中，至少有（）条边。A.n-1B.nC.n(n-1)D.n(n-1)/216、在一个具有n个顶点的连通图中，生成树的边数一定为？（）A.n-1B.nC.n+1D.2n17、以下关于哈希冲突解决方法中二次探测法的描述，哪一项是不正确的？（）A.可以减少聚集现象B.探测的位置是连续的C.可能会出现找不到空闲位置的情况D.相比线性探测法，性能更优18、在数据结构中，跳表的索引层数是根据数据量动态调整的，以下关于索引层数调整的描述，错误的是（）A.当数据量增加时，可能增加索引层数B.索引层数越多，查找效率越高C.调整索引层数的过程比较复杂D.索引层数的调整不会影响数据的存储结构19、对于一个具有n个元素的有序数组，使用二分查找算法查找一个特定元素。以下关于二分查找的时间复杂度的描述，哪一个是恰当的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、在二叉搜索树中，每个节点的值都大于其左子树中所有节点的值，小于其右子树中所有节点的值。以下关于二叉搜索树的操作，不正确的是（）A.插入操作需要按照节点值的大小找到合适的位置B.查找操作的时间复杂度在最坏情况下为O(n)C.删除节点时，如果该节点有两个子节点，可以选择其左子树中的最大节点或右子树中的最小节点进行替换D.二叉搜索树总是平衡的，即左右子树的高度差不超过1二、简答题（本大题共4个小题，共40分)1、（本题10分）阐述后缀树在自然语言处理中的应用场景和技术挑战。2、（本题10分）描述二叉树的遍历算法在二叉树的路径总和问题、节点间最大距离问题中的应用。3、（本题10分）论述如何利用深度优先搜索算法检测图中是否存在环。4、（本题10分）简述数据结构中栈的定义、特点及基本操作，并举例说明栈在实际中的应用。三、设计题（本大题共2个小题，共20分)1、（本题10分）给定一个链表，设计算法将其拆分成两个链表，一个包含奇数位置的节点，一个包含偶数位置的节点。2、（本题10分）设计一个程序，使用双向链表存储一组浮点数，实现链表的快速排序。