浙江工业大学之江学院《数据可视化》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页浙江工业大学之江学院《数据可视化》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种数据结构常用于实现字典操作，并且能够快速查找、插入和删除元素？（）A.栈B.队列C.二叉搜索树D.数组2、二叉树的遍历方式可以递归实现，也可以非递归实现，以下关于它们的说法中，错误的是？（）A.递归实现的二叉树遍历方式简单直观，但可能会导致栈溢出问题。B.非递归实现的二叉树遍历方式需要使用栈或队列来辅助实现。C.非递归实现的二叉树遍历方式比递归实现的效率更高。D.二叉树的遍历方式只能用递归或非递归方式实现，不能用其他方式实现。3、以下哪种数据结构能够在O(1)的时间复杂度内实现元素的随机访问？（）A.链表B.队列C.栈D.数组4、对于一个用数组实现的小根堆，进行删除堆顶元素操作后，需要重新调整堆以保持堆的性质。以下关于删除操作的时间复杂度的描述，哪一个是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、已知一个图的邻接表存储结构，若要判断任意两个顶点之间是否存在边，哪种方法最有效？（）A.遍历邻接表B.建立逆邻接表C.建立邻接矩阵D.深度优先搜索6、在一个带权的有向图中，使用迪杰斯特拉算法求从源点到其他顶点的最短路径，每次选择的顶点是？（）A.距离源点最近的顶点B.距离源点最远的顶点C.未确定最短路径的顶点中权值最小的顶点D.未确定最短路径的顶点中权值最大的顶点7、若对一棵二叉搜索树进行先序遍历，得到的节点序列是一个递减序列，则该二叉搜索树（）。A.没有左子树B.没有右子树C.左子树均为空D.右子树均为空8、在图的存储结构中，十字链表主要用于存储有向图，以下关于十字链表的特点，描述不正确的是（）A.既能方便地访问出边，也能方便地访问入边B.存储空间比邻接表节省C.对于删除边的操作比较复杂D.不适合用于稀疏有向图9、在一个具有n个节点的二叉树中，若每个节点都有左右孩子，则叶子节点的数量与度为2的节点数量有什么关系？A.叶子节点数量=度为2的节点数量+1B.叶子节点数量=度为2的节点数量-1C.叶子节点数量=度为2的节点数量D.以上都不对10、以下关于拓扑排序的描述，正确的是：A.拓扑排序的结果是唯一的B.一个有环的图也可以进行拓扑排序C.拓扑排序可以用于判断一个图是否有环D.拓扑排序只能用于有向图11、在一个具有n个元素的有序数组中，使用插入排序进行排序，其最坏情况下的时间复杂度为？（）A.O(n)B.O(log₂n)C.O(n²)D.O(nlog₂n)12、在一个具有n个元素的最大堆中，插入一个新元素后，为了恢复堆的性质，需要进行的调整操作的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一个循环链表中，若要删除链表中的最后一个节点，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一个有n个顶点和e条边的无向图中，采用邻接矩阵存储，其空间复杂度为多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)15、树是一种非线性数据结构，它由节点和边组成。以下关于树的说法中，错误的是？（）A.树中的每个节点都有一个父节点（除了根节点）和零个或多个子节点。B.二叉树是一种特殊的树，每个节点最多有两个子节点。C.树可以用于实现文件系统、数据库索引等。D.树的遍历方式只有前序遍历、中序遍历和后序遍历三种。16、在一个具有n个顶点的有向完全图中，边的数量为：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)17、对于一棵二叉树，先序遍历序列为ABC，中序遍历序列为BAC，则其后序遍历序列为？A.BCAB.CBAC.ACBD.ABC18、对于一个具有n个元素的堆，进行删除堆顶元素的操作，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、对于一个具有n个节点的无向完全图，其边的数量为多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/220、以下哪种排序算法在最坏情况下的交换次数最少？A.冒泡排序B.快速排序C.选择排序D.插入排序二、简答题（本大题共4个小题，共40分)1、（本题10分）详细阐述如何在一个具有n个元素的无序数组中，使用快速选择算法查找第k小的元素，分析其时间复杂度。2、（本题10分）简述数据结构中栈的定义、特点及基本操作，并举例说明栈在实际中的应用。3、（本题10分）比较冒泡排序和快速排序在对小规模数据的处理速度。4、（本题10分）详细阐述在一个具有n个顶点的无向图中，如何进行边的双连通分量的求解。三、设计题