贵州工程应用技术学院《数据结构课程设计》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页贵州工程应用技术学院《数据结构课程设计》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、二叉树是一种重要的数据结构。对于一个满二叉树，若其高度为h，则节点总数为多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-12、以下关于平衡二叉树旋转调整的描述，正确的是：A.旋转调整一定会改变树的中序遍历结果B.左旋操作是将右子树变为根节点，原根节点变为左子节点C.右旋操作是将左子树变为根节点，原根节点变为右子节点D.平衡二叉树不需要进行旋转调整3、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则存储空间的复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)4、设有一个广义表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)5、在一个具有n个元素的无序数组中，使用顺序查找算法查找一个特定元素，平均比较次数约为？A.n/2B.nC.lognD.nlogn6、对于一个具有n个顶点和e条边的无向连通图，利用Prim算法构造最小生成树时，其时间复杂度为：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)7、已知一个图的邻接表如下所示，则从顶点V1出发进行广度优先遍历，可能得到的顶点访问序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V58、在一个具有n个元素的线性表中，采用顺序查找法查找一个特定元素，若查找成功，平均查找长度为？（）A.(n+1)/2B.n/2C.lognD.n9、若对一棵二叉排序树进行中序遍历，得到的节点序列是一个递增序列，则该二叉排序树（）。A.没有左子树B.没有右子树C.左子树均为空D.右子树均为空10、在一个用邻接矩阵存储的图中，若要判断两个节点是否相邻，时间复杂度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)11、在一个哈希表中，解决冲突的方法通常有开放定址法和链地址法。如果要保证查找的平均时间复杂度较低，应该优先选择哪种方法？（）A.开放定址法B.链地址法C.两者效果相同D.取决于哈希函数12、已知一个完全二叉树的节点总数为100，其叶子节点的个数为（）。A.49B.50C.51D.不确定13、在一个具有n个元素的小根堆中，最小元素的值位于（）。A.根节点B.任意节点C.叶子节点D.无法确定14、栈是一种特殊的线性表，其操作遵循后进先出原则。若一个栈的初始状态为空，现在依次将元素1、2、3、4、5入栈，然后再依次出栈，那么出栈的顺序是什么？（）A.12345B.54321C.32154D.2154315、设有一个具有n个节点的二叉树，若每个节点都有左右子树，则该二叉树的叶子节点数量与度为2的节点数量之间存在特定关系。以下关于这种关系的描述，哪一项是正确的？A.叶子节点数量等于度为2的节点数量B.叶子节点数量比度为2的节点数量多1C.叶子节点数量比度为2的节点数量少1D.两者之间没有固定关系16、在一个具有n个元素的顺序存储的循环队列中，队满的条件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front17、在一个具有n个元素的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时，需要向后移动的元素个数为：A.n-iB.iC.n-i+1D.n-i-118、在一个具有n个元素的循环队列中，若队头指针为front，队尾指针为rear，且rear<front，则队列中的元素个数为？A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n19、已知一个带权有向图G=(V,E)，顶点集合V={1,2,3,4,5}，边集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求从顶点1到顶点5的最短路径，经过的中间顶点依次为？（）A.2,4B.3,4C.2,3D.3,520、对于一个具有n个顶点的连通图，其生成树中边的数量为：A.n-1B.nC.n+1D.不确定二、简答题（本大题共4个小题，共40分)1、（本题10分）深入探讨在有向图和无向图中，如何判断图是否连通，以及求连通分量的方法。2、（本题10分）阐述如何在一个具有n个元素的双向链表中，进行查找操作，并分析其时间复杂度和空间复杂度。3、（本题10分）详细说明队列的特点和基本操作，阐述循环队列是如何解决顺序队列中“假溢出”问题的，并给出循环队列的队空和队满的判断条件。4、（本题10分）详细阐述在堆的应用中，如何使用堆实现优先级队列，