保山学院《数据结构》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页保山学院

《数据结构》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个节点的线索二叉树，若n个节点中有m个空指针域，则线索的数量为？A.mB.m/2C.n+1D.n-12、若要对一个具有n个元素的有序链表进行二分查找，是否可行？（）A.可行B.不可行C.有时可行D.取决于链表长度3、以下哪种数据结构在查找、插入和删除操作的综合性能上表现较好？（）A.二叉搜索树B.红黑树C.B树D.哈希表4、以下关于图的最短路径算法的描述，哪一项是正确的？（）A.Dijkstra算法不能处理负权边B.Floyd算法的时间复杂度低于Dijkstra算法C.所有最短路径算法都能在有向图和无向图中使用D.最短路径一定是唯一的5、若对一棵二叉搜索树进行先序遍历，得到的节点序列是一个递减序列，则该二叉搜索树（）。A.没有左子树B.没有右子树C.左子树均为空D.右子树均为空6、在一个具有n个顶点的无向完全图中，每个顶点的度为多少？（）A.n-1B.nC.2(n-1)D.2n7、在一个链式存储的栈中，进行入栈和出栈操作时，以下关于时间复杂度的描述，哪一个是准确的？A.入栈和出栈的时间复杂度均为O(1)B.入栈的时间复杂度为O(n)，出栈的时间复杂度为O(1)C.入栈的时间复杂度为O(1)，出栈的时间复杂度为O(n)D.入栈和出栈的时间复杂度均为O(n)8、设有一个循环队列，存储空间为Q[0..m-1]，初始时front=rear=m。现经过一系列入队与退队操作后，front=20，rear=15，则此时队列中的元素个数为（）。A.5B.6C.m-5D.m+59、队列是另一种特殊的线性数据结构，它遵循先进先出（FIFO）的原则。以下关于队列的说法中，错误的是？（）A.队列可以用数组或链表实现。B.队列的插入操作在队尾进行，删除操作在队首进行。C.队列可以用于实现任务调度、消息传递等。D.队列的容量是无限的，可以存储任意数量的元素。10、在一个容量为10的顺序存储的循环队列中，若front=4，rear=8，则此时队列中元素的个数为：A.4B.5C.6D.711、对于一个具有n个顶点和e条边的无向图，采用邻接表存储时，其空间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)12、对于一个采用顺序存储的栈，若要判断栈是否为空，以下哪种方法是最有效的？A.检查栈顶元素是否为NULLB.检查栈顶指针是否为-1C.检查栈顶指针是否等于栈的最大容量D.检查栈中元素的数量是否为013、对于一个具有n个节点的无向连通图，其生成树的边数为（）A.n-1B.nC.n+1D.2n14、对于一个大根堆，若将堆中所有元素按照层次遍历的顺序存储到一个数组中，以下关于数组元素的排列，哪一项是正确的？A.完全无序B.从左到右依次递减C.从左到右依次递增D.以上都不对15、以下哪种排序算法在最坏情况下的时间复杂度最低？A.冒泡排序B.插入排序C.选择排序D.归并排序16、在一个具有n个节点的二叉树中，若采用后序遍历得到的节点序列是ABC，中序遍历序列是BAC，则先序遍历序列是什么？A.CABB.ABCC.ACBD.无法确定17、以下关于哈夫曼树的描述，正确的是：A.哈夫曼树一定是完全二叉树B.哈夫曼树中不存在度为1的节点C.哈夫曼树的带权路径长度是唯一的D.哈夫曼树的构建过程不需要进行节点的比较和交换18、在二叉搜索树中，每个节点的值都大于其左子树中所有节点的值，小于其右子树中所有节点的值。以下关于二叉搜索树的操作，不正确的是（）A.插入操作需要按照节点值的大小找到合适的位置B.查找操作的时间复杂度在最坏情况下为O(n)C.删除节点时，如果该节点有两个子节点，可以选择其左子树中的最大节点或右子树中的最小节点进行替换D.二叉搜索树总是平衡的，即左右子树的高度差不超过119、以下关于并查集的描述，错误的是：A.并查集可以用于判断两个元素是否在同一个集合中B.并查集的查找操作时间复杂度较低C.并查集的合并操作时间复杂度较高D.并查集通常采用树形结构存储20、对于一个用数组实现的小根堆，进行删除堆顶元素操作后，需要重新调整堆以保持堆的性质。以下关于删除操作的时间复杂度的描述，哪一个是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）说明队列的先进先出（FIFO）特性对解决哪些问题有帮助，并举例说明。2、（本题10分）详细论述在利用二叉搜索树进行范围查询时，如何实现查找给定范围内的节点，并给出具体的算法步骤和代码实现。3、（本题10分）论述伸展树在处理随机数据时的性能表现和优化措施。4、（本题10分）在一个具有n个顶点的无向图中，如何找出所有的生成树