南京信息工程大学《数据结构与算法》2022-2023学年期末试卷

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

《数据结构与算法》2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、若一棵二叉树的叶子节点数为n0，度为2的节点数为n2，则n0和n2之间的关系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+12、树的遍历方式有多种，以下关于它们的说法中，错误的是？（）A.前序遍历是先访问根节点，然后遍历左子树，最后遍历右子树。B.中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。C.后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。D.树的遍历方式只有前序遍历、中序遍历和后序遍历三种。3、若要对一个具有n个元素的数组进行归并排序，需要额外的辅助空间大小为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在一个具有n个元素的顺序表中，若要在第i个元素（1<=i<=n）之前插入一个新元素，需要移动的元素个数为？（）A.n-iB.iC.n-i+1D.n-i-15、以下关于字符串匹配算法的描述，哪一项是不正确的？（）A.BF算法的时间复杂度在最坏情况下较高B.KMP算法通过利用已匹配的部分信息来提高效率C.BM算法在一般情况下比KMP算法效率更高D.所有字符串匹配算法的时间复杂度都与模式串的长度成正比6、以下哪种数据结构能够在O(1)的时间复杂度内实现元素的随机访问？（）A.链表B.队列C.栈D.数组7、在一个具有n个顶点的有向强连通图中，至少需要多少条边？（）A.n-1B.nC.n(n-1)/2D.n(n-1)8、在一个具有n个元素的小根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)9、对于一个具有n个元素的有序数组，若采用折半插入排序算法进行排序，其时间复杂度为？（）A.O(n)B.O(nlogn)C.O(n²)D.O(logn)10、以下关于平衡二叉树旋转调整的描述，正确的是：A.旋转调整一定会改变树的中序遍历结果B.左旋操作是将右子树变为根节点，原根节点变为左子节点C.右旋操作是将左子树变为根节点，原根节点变为右子节点D.平衡二叉树不需要进行旋转调整11、设有一个广义表L=((a,b),c,(d,e))，其表头和表尾分别为？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)12、在一棵度为4的树中，度为4的节点个数为1，度为3的节点个数为2，度为2的节点个数为3，度为1的节点个数为4，叶子节点个数为（）。A.15B.16C.17D.1813、在一个具有n个顶点的无向图中，若要判断两个顶点之间是否存在路径，使用哪种算法较为合适？A.迪杰斯特拉算法B.弗洛伊德算法C.深度优先遍历或广度优先遍历D.拓扑排序14、在一个具有n个节点的完全二叉树中，若底层从左到右依次编号，节点i的左孩子节点编号是多少（假设根节点编号为1）？A.2iB.2i+1C.i*2D.以上都不对15、以下关于堆的描述，正确的是：A.大顶堆中每个父节点的值都大于其子节点的值B.小顶堆中每个父节点的值都小于其子节点的值C.堆可以用顺序存储也可以用链式存储D.堆是完全二叉树16、对于一个具有n个顶点的无向图，若要判断其是否为连通图，以下哪种方法效率较高？（）A.深度优先搜索B.广度优先搜索C.枚举所有边D.以上方法效率相同17、对于一个用数组实现的最小堆，若要删除堆顶元素并调整堆，以下操作正确的是？（）A.将堆尾元素移到堆顶，然后从堆顶向下调整B.将堆顶元素与堆尾元素交换，然后从堆顶向下调整C.将堆顶元素删除，然后重新构建堆D.以上都不对18、若一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBDAEGF，则其后序遍历序列为？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF19、在图的最小生成树算法中，Kruskal算法和Prim算法都能得到最小生成树，以下关于这两个算法的比较，错误的是（）A.Kruskal算法基于边，Prim算法基于节点B.Kruskal算法需要使用并查集C.Prim算法的时间复杂度通常比Kruskal算法低D.对于稀疏图，Kruskal算法更优20、对于一个有向无环图（DAG），进行拓扑排序的方法不止一种。以下关于拓扑排序的描述，错误的是（）A.可以使用深度优先搜索实现B.结果不唯一C.可以用于判断图中是否存在环D.所有节点的入度在排序过程中不会改变二、简答题（本大题共4个小题，共40分)1、（本题10分）解释什么是并查集，并说明其在解决某些问题中的应用。2、（本题10分）在一个具有n个顶点的无向图中，如何找出所有的生成树，给出一种有效的算法并分析其时间复杂度。3、（本题10分）在一个具有n个元素的有序链表和有序数组中，分别说明如何进行合并操作，给出算法步骤和时间复杂度分析。4、（本题10分）深入分析在具有n个元素的有序链表中，如何进行插入操作以保持链表