郑州西亚斯学院《数据结构》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页郑州西亚斯学院《数据结构》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个顶点和e条边的有向完全图，其弧的条数为（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/22、对于一个具有n个顶点和e条边的带权有向图，若采用迪杰斯特拉（Dijkstra）算法求单源最短路径，其时间复杂度为（）。A.O(n^2)B.O(elog₂e)C.O(nlog₂n)D.O(n^3)3、若要从一个具有n个元素的有序单链表中删除所有值重复的元素，使得链表中每个元素的值都不同，最优的算法时间复杂度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)4、对于一个具有n个顶点和e条边的无向连通图，其生成树中边的条数为（）。A.nB.n-1C.eD.e-15、在一个具有n个元素的链表中，若要在表头插入一个新元素，平均需要修改几个指针？（）A.1B.2C.nD.n+16、在一个具有n个元素的线性表中，采用顺序查找法查找一个特定元素，若查找成功，平均查找长度为？（）A.(n+1)/2B.n/2C.lognD.n7、在一个具有n个顶点的强连通图中，至少有多少条边？（）A.n-1B.nC.n(n-1)/2D.n(n-1)8、图的存储方式有邻接矩阵和邻接表两种，以下关于它们的特点的说法中，错误的是？（）A.邻接矩阵适合存储稠密图，空间复杂度为O(n^2)。B.邻接表适合存储稀疏图，空间复杂度为O(n+m)，其中n是顶点数，m是边数。C.邻接矩阵的查找边的时间复杂度为O(1)。D.邻接表的插入边和删除边的时间复杂度为O(n)。9、在一个用十字链表存储的有向图中，查找一个顶点的所有出边和入边的时间复杂度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)10、在一个具有n个节点的完全二叉树中，若底层从左到右第x个节点为叶子节点，则x的取值范围是（）A.[2^(h-1),2^h-1]B.[2^(h-2),2^(h-1)-1]C.[2^(h-1)-1,2^h-2]D.[2^(h-2)-1,2^(h-1)-1]11、对于一个具有n个顶点和e条边的有向图，采用邻接表存储，进行深度优先遍历。以下关于遍历的时间复杂度的描述，哪一个是恰当的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)12、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法13、设有一个带权有向图G=(V,E)，采用拓扑排序算法对其进行排序，若得到的拓扑序列唯一，则图G一定是？（）A.有环图B.无环图C.强连通图D.弱连通图14、在一个具有n个元素的顺序存储的循环队列中，队满的条件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front15、对于一个具有n个节点的AVL树，插入一个新节点后，调整树的平衡，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、对于一个栈，进行入栈和出栈操作时，以下哪种情况会导致栈溢出？A.入栈元素过多B.出栈元素过多C.连续进行入栈操作且存储空间已满D.连续进行出栈操作且栈为空17、设有一个具有n个节点的二叉树，若每个节点都有左右子树，则该二叉树的叶子节点数量与度为2的节点数量之间存在特定关系。以下关于这种关系的描述，哪一项是正确的？A.叶子节点数量等于度为2的节点数量B.叶子节点数量比度为2的节点数量多1C.叶子节点数量比度为2的节点数量少1D.两者之间没有固定关系18、队列也是一种常见的数据结构，遵循先进先出的原则。对于一个循环队列，以下说法不正确的是（）A.队头指针和队尾指针的移动需要考虑循环的情况B.当队头指针等于队尾指针时，队列为空C.可以通过牺牲一个存储单元来区分队列空和队列满的情况D.循环队列可以避免假溢出的问题19、以下哪种数据结构常用于实现图的广度优先遍历的辅助队列？A.循环队列B.链队列C.优先队列D.双端队列20、以下关于堆的描述，正确的是：A.大顶堆中每个父节点的值都大于其子节点的值B.小顶堆中每个父节点的值都小于其子节点的值C.堆可以用顺序存储也可以用链式存储D.堆是完全二叉树二、简答题（本大题共4个小题，共40分)1、（本题10分）论述在二叉树的遍历中，如何利用线索二叉树优化遍历效率。2、（本题10分）详细解释在二叉搜索树中进行查找操作的过程，以及如何保证查找效率的优化。3、（本题10分）解释图的哈密顿回路和哈密顿路径是什么，以及如何判断一个图是否存在哈密顿回路或哈密顿路径。4、（本题10分）在一个具有n个节点的二叉搜索树中，如何查找第k小的元素，给出算法思路