南京传媒学院《数据结构B》2021-2022学年期末试卷

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

《数据结构B》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个m行n列的二维数组，按行优先存储时，元素a[i][j]（0<=i<m,0<=j<n）的地址计算公式为：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i2、在一个大根堆中，删除堆顶元素后，为了重新调整为大根堆，需要进行的操作是？（）A.将最后一个元素移到堆顶，然后从堆顶向下调整B.将堆中所有元素重新排序C.将堆顶元素与最后一个元素交换，然后从堆顶向下调整D.无需调整3、栈和队列在计算机科学中有很多应用，以下关于它们的应用场景的说法中，错误的是？（）A.栈可以用于实现表达式求值、括号匹配等。B.队列可以用于实现任务调度、消息队列等。C.栈和队列可以用于实现图的深度优先搜索和广度优先搜索。D.栈和队列只能在编程语言的底层实现中使用，不能在实际应用中直接使用。4、在一棵度为4的树中，度为4的节点个数为1，度为3的节点个数为2，度为2的节点个数为3，度为1的节点个数为4，叶子节点个数为（）。A.15B.16C.17D.185、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则其后序遍历序列为？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA6、在一个具有n个元素的堆中，查找最大元素的时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)7、以下哪种排序算法是稳定的排序算法？A.快速排序B.选择排序C.冒泡排序D.希尔排序8、对于一个具有n个元素的有序单链表，要查找一个值为x的元素，平均比较次数约为？A.n/2B.nC.lognD.19、在一棵二叉搜索树中，删除一个只有左子树的节点，其右子树的节点需要（）A.替换被删除节点B.保持不动C.全部删除D.移动到左子树10、在一个带头结点的单链表中，若要删除表中所有值为x的结点，最优的算法时间复杂度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)11、设有一个用链表实现的双向循环链表，若要在其中一个节点之后插入一个新节点，以下关于插入操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、一棵哈夫曼树中，叶子节点的编码长度一定（）非叶子节点的编码长度。A.大于B.等于C.小于D.不小于13、以下关于图的最短路径算法的描述，哪一项是正确的？（）A.Dijkstra算法不能处理负权边B.Floyd算法的时间复杂度低于Dijkstra算法C.所有最短路径算法都能在有向图和无向图中使用D.最短路径一定是唯一的14、栈和队列的应用场景非常广泛，以下关于它们的应用的说法中，错误的是？（）A.栈可以用于实现函数调用、表达式求值和括号匹配等。B.队列可以用于实现任务调度、消息队列和广度优先搜索等。C.栈和队列可以用于实现图的深度优先搜索和广度优先搜索。D.栈和队列只适用于计算机科学领域，在其他领域没有实际价值。15、平衡二叉树是一种特殊的二叉搜索树，通过自动调整保持树的平衡。以下关于平衡二叉树的操作，不正确的是（）A.插入节点可能会导致树的不平衡，需要进行旋转调整B.平衡二叉树的查找效率在最坏情况下为O(logn)C.平衡因子用于判断节点是否平衡D.平衡二叉树的节点删除操作比插入操作更复杂16、并查集是一种用于处理不相交集合的数据结构。在并查集中，以下操作不正确的是（）A.查找操作用于确定元素所属的集合B.合并操作将两个集合合并为一个C.并查集可以高效地判断两个元素是否在同一个集合中D.并查集的时间复杂度与集合的数量成正比17、在一个有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比较的次数是：A.1B.2C.3D.418、在数据结构中，桶排序是一种外部排序算法，以下关于桶排序的描述，错误的是（）A.要求输入数据具有特定的分布B.时间复杂度为O(n)C.空间复杂度较高D.适用于大规模数据排序19、在一个有序的单链表中，若要删除一个重复出现的元素，使得链表中不再有重复元素，应如何操作？（）A.从头遍历，遇到重复元素就删除B.从尾遍历，遇到重复元素就删除C.先排序，再删除重复元素D.建立一个新链表，将不重复元素插入20、在一个具有n个元素的链表中，要删除所有值为x的节点，最好的方法是？A.逐个删除B.先查找再删除C.建立新链表D.以上方法效率相同二、简答题（本大题共4个小题，共40分)1、（本题10分）解释在一个具有n个顶点的无向完全图中，生成所有生成树的方法和步骤。2、（本题10分）在一个双向链表中，如何交换两个相邻结点的位置？3、（本题10分）在一个链表中，如何判断链表是否为回文链表？4、（本题10分）在一个二叉树中，如