郑州大学《数据可视化》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页郑州大学

《数据可视化》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在数据结构中，树的遍历可以采用递归和非递归方式。以下关于非递归中序遍历二叉树的说法，错误的是（）A.可以使用栈来辅助实现B.比递归方式更复杂C.时间复杂度与递归方式相同D.空间复杂度一定比递归方式低2、以下关于图的存储结构的描述，哪一项是正确的？（）A.邻接矩阵适合存储稀疏图B.邻接表在存储稠密图时空间效率较高C.十字链表适合存储有向图D.以上都不正确3、在一个具有n个顶点的有向图中，若存在环，则使用拓扑排序算法会？A.正常排序B.无法排序C.部分排序D.排序结果不确定4、对于一棵具有n个节点的二叉搜索树，其平均查找长度的上限大约为？A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)5、在一个具有n个元素的双向链表中，删除一个指定节点，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一个具有n个元素的小根堆中，最小元素的值位于（）。A.根节点B.任意节点C.叶子节点D.无法确定7、对于一个具有n个元素的快速排序，在最好情况下，其时间复杂度为？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)8、在一个用数组实现的堆中，若要删除堆底的元素，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、以下哪种数据结构常用于实现图的存储？A.邻接矩阵和邻接表B.二叉树和链表C.栈和队列D.数组和哈希表10、并查集是一种用于处理不相交集合的数据结构。在并查集中，以下操作不正确的是（）A.查找操作用于确定元素所属的集合B.合并操作将两个集合合并为一个C.并查集可以高效地判断两个元素是否在同一个集合中D.并查集的时间复杂度与集合的数量成正比11、已知一个带权无向图的邻接矩阵表示，若要计算图中两个顶点之间的最短路径，可以使用的算法是？（）A.深度优先搜索B.广度优先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法12、对于一个具有n个顶点和e条边的带权有向图，若采用迪杰斯特拉（Dijkstra）算法求单源最短路径，其时间复杂度为（）。A.O(n^2)B.O(elog₂e)C.O(nlog₂n)D.O(n^3)13、在数据结构中，使用并查集解决集合合并问题时，以下关于路径压缩的描述，错误的是（）A.可以提高查找效率B.不改变集合的关系C.增加了合并操作的复杂度D.使树的高度降低14、在一棵平衡二叉树中，插入一个新结点后，可能需要进行的调整操作是：A.左旋B.右旋C.左旋和右旋D.不需要调整15、以下关于哈希冲突解决方法中二次探测法的描述，哪一项是不正确的？（）A.可以减少聚集现象B.探测的位置是连续的C.可能会出现找不到空闲位置的情况D.相比线性探测法，性能更优16、在一个具有n个元素的大顶堆中，插入一个新元素后，需要进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)17、在一个具有n个元素的顺序表中，若要查找一个元素，平均需要比较多少次？（）A.n/2B.nC.lognD.不确定18、对于一个循环队列，若队列的最大容量为m，当前front指针为5，rear指针为2，则队列中的元素个数为（）A.7B.3C.m-3D.m-719、已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEABC，则其先序遍历序列为？（）A.CEDBAB.CEABDC.ABCDED.EACDB20、设有一个广义表L=(a,(b,c),d)，其长度和深度分别为？（）A.3和2B.3和3C.4和2D.4和3二、简答题（本大题共4个小题，共40分)1、（本题10分）解释有向无环图的概念，说明如何使用拓扑排序对有向无环图进行顶点的排序，并分析其时间复杂度。2、（本题10分）解释如何在一个具有n个顶点的无向图中判断是否存在自环。3、（本题10分）详细论述在一个具有n个顶点和e条边的无向图中，采用邻接表存储和邻接矩阵存储的优缺点，并比较它们的空间复杂度。4、（本题10分）论述在树的遍历优化中，如何利用线索化和缓存机制提高性能。三、设计题（本大题共