成都锦城学院《数据可视化技术与应用》2022-2023学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页成都锦城学院

《数据可视化技术与应用》2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个顶点和e条边的无向图，使用深度优先搜索算法进行遍历。以下关于算法中使用的标记数组的空间复杂度的描述，哪一项是正确的？A.O(1)B.O(n)C.O(e)D.O(n^2)2、在数据结构中，使用队列来实现广度优先遍历图，以下关于遍历过程的描述，错误的是（）A.从起始节点开始入队B.队列为空时结束遍历C.访问节点时将其未访问的邻接节点入队D.节点不会被重复访问3、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则其后序遍历序列为？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA4、在二叉树中，判断两棵二叉树是否完全相同，以下方法不正确的是（）A.同时进行先序遍历，比较节点值B.同时进行中序遍历，比较节点值C.同时进行后序遍历，比较节点值D.比较两棵树的节点数量5、以下哪种数据结构常用于实现并查集？（）A.数组B.链表C.树D.哈希表6、在一个用链表实现的队列中，若要实现队列的遍历操作，以下哪种方式较为合适？A.从队头开始，依次访问每个节点B.从队尾开始，依次向前访问每个节点C.随机访问链表中的节点D.以上都不对7、在一个有n个顶点和e条边的无向图中，采用邻接矩阵存储，其空间复杂度为多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)8、对于一个具有n个顶点的连通图，其生成树中边的数量为：A.n-1B.nC.n+1D.不确定9、在一个堆排序中，最大堆用于升序排序，最小堆用于降序排序。那么对于一个初始无序的数组，构建最大堆的时间复杂度是多少？（）A.O(n)B.O(log₂n)C.O(nlog₂n)D.O(n²)10、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则存储空间的复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)11、在一个小根堆中，最小的元素总是位于堆顶。若要将一个元素插入到堆中并保持堆的性质，以下哪种操作是必须的？A.从堆顶向下调整B.从堆底向上调整C.先删除堆顶元素再插入D.以上都不对12、在一个带权无向图中，使用普里姆算法构造最小生成树，每次选择的边是？（）A.权值最小的边B.连接已选顶点和未选顶点的权值最小的边C.任意一条边D.以上都不对13、在一个字符串匹配算法中，BM算法相对于朴素的字符串匹配算法，其优势在于？（）A.平均性能更好B.代码更简洁C.空间复杂度更低D.适用于短字符串匹配14、字符串匹配是数据结构中的一个重要问题，KMP算法是一种高效的字符串匹配算法。关于KMP算法，以下描述错误的是（）A.通过利用已经匹配的部分信息来提高匹配效率B.计算next数组是KMP算法的关键步骤C.KMP算法的时间复杂度为O(m+n)，其中m和n分别是主串和模式串的长度D.KMP算法在任何情况下都比暴力匹配算法快15、对于一个具有n个顶点的带权有向图，若采用迪杰斯特拉（Dijkstra）算法求单源最短路径，其时间复杂度为：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)16、在一个m行n列的二维数组中，按列优先存储时，元素aij的存储地址为？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d17、在一个用数组实现的小根堆中，若要插入一个元素，应该将其插入到数组的哪个位置？A.数组末尾B.堆顶C.任意位置D.以上都不对18、对于一个具有n个元素的顺序存储的栈，若要判断栈是否已满，应判断？（）A.top==n-1B.top==nC.top>=n-1D.top>=n19、对于一个具有n个元素的冒泡排序，若要交换相邻两个元素，平均需要移动多少次？（）A.0B.1C.2D.320、在一个具有n个顶点的有向完全图中，边的数量为：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)二、简答题（本大题共4个小题，共40分)1、（本题10分）论述在Trie树中，如何节省存储空间，例如采用压缩存储或节点合并等方法。2、（本题10分）论述哈希表的冲突解决方法，如线性探测法、二次探测法和链地址法，并分析它们的优缺点。3、（本题10分）对于一个用邻接表存储的图，说明如何判断图是否为哈密顿图，给出一种有效的算法并分析其时间复杂度。4、（本题10分）在一个具有n个顶点的无向图中，如何使用深度优先搜索算法找出所有的连通分量，给出算法步骤