玉溪师范学院《数据结构》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页玉溪师范学院

《数据结构》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个元素的堆，进行堆排序。以下关于堆排序的平均时间复杂度和空间复杂度的描述，哪一个是准确的？A.平均时间复杂度为O(nlogn)，空间复杂度为O(1)B.平均时间复杂度为O(n^2)，空间复杂度为O(n)C.平均时间复杂度为O(logn)，空间复杂度为O(logn)D.平均时间复杂度为O(n)，空间复杂度为O(n)2、若一个图的广度优先遍历序列为ABCDEFG，则其深度优先遍历序列可能为？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG3、设有一个链栈，栈顶指针为top，若要在栈顶插入一个新元素，则需要执行的操作是（）。A.s->next=top;top=s;B.top->next=s;top=s;C.s->next=top->next;top->next=s;D.top=s;s->next=NULL;4、若要在一个具有n个元素的有序数组中插入一个新元素，同时保持数组有序，平均需要移动多少个元素？（）A.n/2B.nC.lognD.15、二叉树是一种重要的数据结构，以下关于二叉树的性质的说法中，错误的是？（）A.二叉树的每个节点最多有两个子节点。B.二叉树的左子树和右子树是有顺序的。C.满二叉树是一种特殊的二叉树，所有的叶节点都在同一层。D.完全二叉树是一种特殊的满二叉树，所有的节点都在同一层。6、在一个链式存储的栈中，若栈顶指针为top，要判断栈是否为空，应判断？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL7、二叉树的遍历方式可以递归实现，也可以非递归实现，以下关于它们的说法中，错误的是？（）A.递归实现的二叉树遍历方式简单直观，但可能会导致栈溢出问题。B.非递归实现的二叉树遍历方式需要使用栈或队列来辅助实现。C.非递归实现的二叉树遍历方式比递归实现的效率更高。D.二叉树的遍历方式只能用递归或非递归方式实现，不能用其他方式实现。8、若要对一个具有n个元素的无序数组进行排序，以下哪种排序算法在最坏情况下的时间复杂度最低？A.冒泡排序B.插入排序C.选择排序D.归并排序9、已知一个有序表为{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值为35的元素，需要比较的次数是（）。A.1B.2C.3D.410、对于一个用数组实现的小根堆，若要将堆顶元素与最后一个元素交换，然后重新调整堆，以下关于调整的方向，哪一项是正确的？A.从堆顶向下调整B.从堆底向上调整C.先从堆顶向下调整，再从堆底向上调整D.以上都不对11、在一个具有n个元素的有序链表中，若要查找第k个元素，以下关于查找操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(k)D.O(n)12、以下哪种排序算法在数据基本有序时的时间复杂度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.选择排序13、对于一个具有n个顶点和e条边的无向图，使用深度优先搜索算法进行遍历。以下关于算法中使用的标记数组的空间复杂度的描述，哪一项是正确的？A.O(1)B.O(n)C.O(e)D.O(n^2)14、在一个具有n个元素的最小堆中，删除堆顶元素后，为了恢复堆的性质，需要进行的调整操作的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、以下哪种数据结构适合用于实现一个可以快速查找最大值和最小值的数据集合？A.链表B.栈C.队列D.堆16、在一个具有n个元素的大顶堆中，插入一个新元素后，需要进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)17、图的存储方式和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.图的邻接矩阵可以用于表示网络中的连接关系，适用于社交网络分析和交通网络规划等。B.图的邻接表可以用于表示稀疏图，适用于地图绘制和电路图设计等。C.图的遍历方式可以用于解决路径规划、网络流问题和最小生成树问题等，适用于物流配送和通信网络优化等。D.图的存储方式和遍历方式只适用于理论研究，在实际应用中没有实际价值。18、在一个具有n个元素的小根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)19、对于一个具有n个节点的无向完全图，其边的数量为多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/220、在一个顺序存储的队列中，若要在队尾插入一个元素，需要移动元素的平均次数为（）A.0B.n/2C.nD.n-1二、简答题（本大题共4个小题，共40分)1、（本题10分）阐述如何将一个具有n个元素的无序数组构建为一个最小堆，并分析其时间复杂度。2、（本题10分）在一个顺序表中，插入和删除操作在平均情况下的时间复杂度分别是多少？并解释为什么会是这样的复杂度。3、（本题10分）阐述如何使用并查集解决集合合并和查询问题，说明并查集的优化方法和时间复杂度。4、（本题10分）详细阐述在具有n个顶点的图中，如何使用迪杰斯特拉（Dijkstra）算法求解每对顶点之间的最短路径，并分析其时间