湖南工商大学《数据结构》2022-2023学年期末试卷

装订线装订线PAGE2第1页，共3页湖南工商大学《数据结构》

2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下关于图的遍历算法的描述，哪一项是正确的？（）A.深度优先遍历和广度优先遍历都能访问到图中的所有节点B.深度优先遍历适合用于求解最短路径问题C.广度优先遍历的空间复杂度低于深度优先遍历D.两种遍历算法的时间复杂度都与图的边数成正比2、在一个具有n个顶点的图中，若存在回路，则深度优先遍历可能会出现什么情况？（）A.访问某些顶点多次B.无法完成遍历C.结果不正确D.以上都有可能3、对于一个具有n个顶点的带权连通图，若采用克鲁斯卡尔（Kruskal）算法生成最小生成树，其时间复杂度为（）。A.O(n^2)B.O(elog₂e)C.O(nlog₂n)D.O(e^2)4、在一个具有n个元素的顺序表中，删除第i个元素（1<=i<=n），需要移动的元素个数最多为（）。A.i-1B.n-iC.n-i+1D.n-15、对于一个具有n个元素的哈希表，若采用链地址法处理冲突，以下关于查找操作的平均时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则该二叉树的后序遍历序列为（）。A.CBEFDGAB.CEBFDGAC.CBEFGDAD.CEBFGDA7、以下关于快速排序的描述，错误的是：A.快速排序在平均情况下的时间复杂度为O(nlogn)B.快速排序是一种不稳定的排序算法C.快速排序在最坏情况下的时间复杂度为O(n^2)D.快速排序不需要额外的存储空间8、对于一个具有n个元素的待排序序列，若采用冒泡排序算法进行排序，在最坏情况下需要进行的比较次数为？（）A.n(n-1)/2B.nlognC.n-1D.n9、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法10、对于一个具有n个顶点和e条边的无向连通图，利用Prim算法构造最小生成树时，其时间复杂度为：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)11、对于一个用链表实现的栈，若要获取栈中元素的个数，以下哪种方法效率较高？A.遍历链表B.维护一个计数器C.以上效率相同D.以上都不对12、若要在一棵二叉搜索树中查找一个特定的值，平均时间复杂度为？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)13、以下哪种数据结构常用于实现操作系统中的进程调度？A.队列B.栈C.树D.图14、对于一个具有n个节点的完全二叉树，若按层序编号，则编号为i的节点，其双亲节点的编号为？A.i/2B.(i-1)/2C.2iD.2i+115、以下哪种数据结构能够高效地支持动态集合的操作，如合并、查找等？（）A.链表B.二叉树C.并查集D.哈希表16、以下关于串的描述，错误的是：A.串是一种特殊的线性表B.串的长度是指串中字符的个数C.空串和空格串是相同的概念D.串的存储方式有顺序存储和链式存储17、对于一个具有n个节点的二叉树，其先序遍历、中序遍历和后序遍历的结果都是唯一确定的，这个二叉树一定是（）A.满二叉树B.完全二叉树C.单支树D.以上都不是18、在一个顺序存储的栈中，若要实现共享栈，即两个栈共用一个数组空间，以下关于栈顶指针的设置，哪一种方案较为合理？A.两个栈的栈顶指针分别从数组的两端向中间移动B.两个栈的栈顶指针都从数组的同一端开始移动C.一个栈的栈顶指针从数组的开头移动，另一个从结尾移动D.以上都可以19、若要在一个已排序的数组中使用二分查找算法查找一个特定元素，以下关于时间复杂度的描述，哪一项是正确的？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)20、在一个具有n个节点的无向图中，若边的数量远远小于n(n-1)/2，则适合使用哪种存储方式？A.邻接矩阵B.邻接表C.十字链表D.以上都可以二、简答题（本大题共4个小题，共40分)1、（本题10分）深入探讨在一个具有n个元素的二叉搜索树中，如何进行范围查询。2、（本题10分）深入分析在具有n个顶点的图中，如何进行拓扑排序以确定任务的执行顺序，并说明其应用场景。3、（本题10分）详细说明最短路径问题的定义，以及Dijkstra算法和Floyd算法在解决不同类型最短路径问题中的应用。4、（本题10分）解释如何在一个二叉搜索树中进行删除操作的多线程实现，给出算法步骤和实现代码，并