北京工业大学《数据结构与算法分析》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页北京工业大学

《数据结构与算法分析》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个m行n列的二维数组中，元素存储的地址计算公式为LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d为每个元素所占的存储单元数。若按行优先存储，则a23的地址为？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d2、设有一个栈，元素进栈的次序为A、B、C、D、E，下列不可能的出栈序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE3、设有一个具有n个节点的二叉树，采用中序遍历将其转换为一个有序的单链表。以下关于转换过程的时间复杂度的描述，哪一项是正确的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)4、设有一个具有n个元素的最大堆，若要获取堆中的最大元素，以下关于操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、在一个用链表实现的队列中，若要删除队头元素并返回其值，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一棵二叉树中，若度为2的节点有10个，度为1的节点有20个，那么叶子节点的数量是多少？A.11B.21C.30D.无法确定7、对于一个具有n个节点的二叉树，进行先序遍历和中序遍历，得到的序列相同，则该二叉树的形状为？A.只有一个根节点B.所有节点只有左子树C.所有节点只有右子树D.是一棵满二叉树8、在字符串处理中，后缀数组是一种有效的数据结构，以下关于后缀数组的描述，错误的是（）A.可以用于字符串的匹配和查找B.构建后缀数组的时间复杂度较高C.空间复杂度相对较低D.不适合处理大规模字符串9、已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEABC，则其先序遍历序列为？（）A.CEDBAB.CEABDC.ABCDED.EACDB10、对于一个具有n个元素的希尔排序，其时间复杂度取决于？（）A.初始序列B.增量序列C.元素值D.以上都是11、在一个具有n个元素的双向链表中，要在指定节点之后插入一个新节点，需要修改几个指针？A.2B.3C.4D.512、对于一个具有n个节点的二叉树，其先序遍历、中序遍历和后序遍历的结果都是唯一确定的，这个二叉树一定是（）A.满二叉树B.完全二叉树C.单支树D.以上都不是13、在一个具有n个元素的顺序表中，若要将其逆置，以下关于操作的时间复杂度的描述，哪一项是恰当的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、已知一个哈希表的装填因子为0.8，哈希函数为H(key)=key%11，采用线性探测法处理冲突。若依次插入关键字31、25、19、49、37、21、13、17，则在查找关键字19时需要进行几次比较？（）A.1B.2C.3D.415、哈希表的性能取决于哈希函数的设计和冲突解决方法的选择，以下关于它们的说法中，错误的是？（）A.好的哈希函数应该具有均匀分布性、随机性和高效性等特点。B.冲突解决方法的选择应该根据哈希表的大小、数据的特点和操作的频率等因素来决定。C.哈希表的性能可以通过调整哈希函数和冲突解决方法来优化。D.哈希表的性能只取决于哈希函数的设计，与冲突解决方法无关。16、在一个具有n个元素的小顶堆中，若将堆顶元素与最后一个元素交换，然后对堆进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)17、以下关于图的最短路径算法的描述，哪一项是正确的？（）A.Dijkstra算法不能处理负权边B.Floyd算法的时间复杂度低于Dijkstra算法C.所有最短路径算法都能在有向图和无向图中使用D.最短路径一定是唯一的18、线段树是一种用于处理区间查询和更新的数据结构。对于线段树的应用，以下说法错误的是（）A.可以快速计算给定区间内元素的和B.可以用于查找区间内的最大值和最小值C.构建线段树的时间复杂度为O(n)D.线段树的空间复杂度与节点数量成正比19、以下哪种数据结构常用于实现图的存储？A.邻接矩阵和邻接表B.二叉树和链表C.栈和队列D.数组和哈希表20、若一个图的邻接矩阵对角线以下（不包括对角线）的元素全为0，则该图一定是：A.无向图B.有向图C.强连通图D.弱连通图二、简答题（本大题共4个小题，共40分)1、（本题10分）详细说明队列的应用场景，如任务调度、广度优先搜索等，给出相应的算法步骤和实现代码。2、（本题10分）在数据结构中，阐述如何使用块状链表进行高效的插入和删除操作，给出算法步骤和实现代码，并分析其性能优势。3、（本题10分）解释数据结构中栈的应用场景，如回溯算法、迷宫求解等，并说明其原理。4、（本题10分）论述如何使