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

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

《数据结构B》2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、已知一个带权无向图的邻接矩阵表示，若要计算图中两个顶点之间的最短路径，可以使用的算法是？（）A.深度优先搜索B.广度优先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法2、对于一个具有n个元素的堆，若要将其所有元素从小到大排序，最好的方法是？A.每次删除堆顶元素并调整B.直接使用快速排序C.先构建大顶堆再调整D.以上方法效率相同3、在一个有序的单链表中，若要删除一个重复出现的元素，使得链表中不再有重复元素，应如何操作？（）A.从头遍历，遇到重复元素就删除B.从尾遍历，遇到重复元素就删除C.先排序，再删除重复元素D.建立一个新链表，将不重复元素插入4、对于一个用邻接矩阵存储的图，若要判断两个顶点之间是否存在边，时间复杂度为？（）A.O(1)B.O(n)C.O(log₂n)D.O(n²)5、在一个具有n个节点的图中，若要找出所有的连通分量，可以使用哪种算法？A.深度优先搜索B.广度优先搜索C.并查集D.以上都可以6、在一个具有n个元素的小根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)7、若要对一个具有n个元素的数组进行归并排序，需要额外的辅助空间大小为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一个用邻接表表示的无向图中，若要删除一条边，需要进行的操作是？（）A.在两个顶点的邻接表中删除对应的边节点B.只在一个顶点的邻接表中删除对应的边节点C.重新构建邻接表D.以上都不对9、堆是一种特殊的树形数据结构，分为大顶堆和小顶堆。对于大顶堆，以下描述不正确的是（）A.根节点的值大于其左右子节点的值B.可以用于实现优先队列C.构建大顶堆的时间复杂度为O(nlogn)D.每次删除堆顶元素后，需要重新调整堆以保持大顶堆的性质10、在一个具有n个元素的最小堆中，若要将堆顶元素与堆底元素交换，然后调整堆的结构，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一个用数组实现的小根堆中，若要插入一个元素，应该将其插入到数组的哪个位置？A.数组末尾B.堆顶C.任意位置D.以上都不对12、在一个具有n个顶点的无向完全图中，每个顶点的度为多少？（）A.n-1B.nC.2(n-1)D.2n13、在一个带头结点的循环链表中，若要判断链表是否为空，应检查？（）A.头结点的指针是否为空B.头结点的下一个结点的指针是否指向头结点C.尾结点的指针是否为空D.尾结点的下一个结点的指针是否指向头结点14、在一个用数组实现的堆中，若要删除堆底的元素，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、以下关于快速排序的描述，错误的是：A.快速排序在平均情况下的时间复杂度为O(nlogn)B.快速排序是一种不稳定的排序算法C.快速排序在最坏情况下的时间复杂度为O(n^2)D.快速排序不需要额外的存储空间16、在一棵二叉搜索树中，删除一个节点后，为了保持二叉搜索树的性质，需要进行的调整操作可能包括（）A.左旋B.右旋C.左右旋结合D.以上都有可能17、对于一个具有n个元素的冒泡排序，若元素基本有序，其时间复杂度接近？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)18、对于一个用链表实现的栈，若要在栈顶插入一个元素，时间复杂度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)19、在数据结构中，使用队列来实现广度优先遍历图，以下关于遍历过程的描述，错误的是（）A.从起始节点开始入队B.队列为空时结束遍历C.访问节点时将其未访问的邻接节点入队D.节点不会被重复访问20、在一棵度为4的树中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个叶子节点，那么这棵树的总节点数是多少？A.82B.81C.79D.78二、简答题（本大题共4个小题，共40分)1、（本题10分）详细说明如何在一个具有n个顶点的无向图中找出所有顶点之间的最短路径长度之和。2、（本题10分）深入探讨在一个具有n个元素的循环队列中，如何有效地判断队列是否已满。3、（本题10分）请详细阐述在顺序表中进行插入操作时，平均移动元素次数的计算方法，并说明在什么情况下移动元素的次数最多。4、（本题10分）论述哈希表的冲突解决方法，如线性探测法、二次探测法和链地址法，