成都锦城学院《数据可视化技术实训》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页成都锦城学院

《数据可视化技术实训》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下关于字符串匹配算法的描述，哪一项是不正确的？（）A.BF算法的时间复杂度在最坏情况下较高B.KMP算法通过利用已匹配的部分信息来提高效率C.BM算法在一般情况下比KMP算法效率更高D.所有字符串匹配算法的时间复杂度都与模式串的长度成正比2、以下关于哈希冲突解决方法中二次探测法的描述，哪一项是不正确的？（）A.可以减少聚集现象B.探测的位置是连续的C.可能会出现找不到空闲位置的情况D.相比线性探测法，性能更优3、在一个循环队列中，队头指针为front，队尾指针为rear，队列最大容量为MAXSIZE，若rear>front，则队列中的元素个数为？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE4、以下哪种排序算法在最坏情况下的交换次数最少？A.冒泡排序B.快速排序C.选择排序D.插入排序5、队列也是一种线性表，遵循先进先出原则。在一个循环队列中，队头指针为front，队尾指针为rear，队列最大容量为MAXSIZE，那么判断队列为空的条件是什么？A.front==rearB.(rear+1)%MAXSIZE==frontC.front==(rear+1)%MAXSIZED.以上都不对6、对于一个满二叉树，若其高度为h，则其节点总数为多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-17、在一个具有n个顶点的有向完全图中，边的数量为？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储其下三角部分，第一个元素A[1,1]存储在数组B[0]中，若A[8,5]在数组B中的存储位置为k，则A[7,5]在数组B中的存储位置为（）。A.k-13B.k-12C.k-11D.k-109、在一棵平衡二叉树中，插入一个新节点后可能导致失衡，需要进行调整。以下哪种调整操作可能涉及到旋转次数最多？（）A.LL型调整B.RR型调整C.LR型调整D.RL型调整10、对于一个具有n个元素的有序数组，若要查找某个元素是否存在，以下哪种查找算法效率最高？（）A.顺序查找B.二分查找C.分块查找D.以上算法效率相同11、已知一个具有n个顶点的无向图采用邻接矩阵存储，若要删除所有的边，时间复杂度为？（）A.O(n)B.O(n²)C.O(nlogn)D.O(e)12、对于一个具有n个元素的双向链表，若要在第i个位置（1<=i<=n）之前插入一个新节点，平均需要修改多少个指针？（）A.1B.2C.3D.413、队列是一种先进先出的线性表，若用一个数组实现循环队列，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素，队列最大容量为MAX_SIZE，那么判断队满的条件是什么？（）A.(rear+1)%MAX_SIZE==frontB.rear==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-114、在一个有n个顶点和e条边的无向图中，采用邻接矩阵存储，其空间复杂度为多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)15、以下哪种排序算法的空间复杂度最低？A.归并排序B.快速排序C.冒泡排序D.插入排序16、在一个链式存储的栈中，进行入栈和出栈操作时，以下关于时间复杂度的描述，哪一个是准确的？A.入栈和出栈的时间复杂度均为O(1)B.入栈的时间复杂度为O(n)，出栈的时间复杂度为O(1)C.入栈的时间复杂度为O(1)，出栈的时间复杂度为O(n)D.入栈和出栈的时间复杂度均为O(n)17、图的存储方式和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.图的邻接矩阵可以用于表示网络中的连接关系，适用于社交网络分析和交通网络规划等。B.图的邻接表可以用于表示稀疏图，适用于地图绘制和电路图设计等。C.图的遍历方式可以用于解决路径规划、网络流问题和最小生成树问题等，适用于物流配送和通信网络优化等。D.图的存储方式和遍历方式只适用于理论研究，在实际应用中没有实际价值。18、对于一个具有n个元素的堆，进行删除堆顶元素的操作，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一个大根堆中，删除堆顶元素后，为了重新调整为大根堆，需要进行的操作是？（）A.将最后一个元素移到堆顶，然后从堆顶向下调整B.将堆中所有元素重新排序C.将堆顶元素与最后一个元素交换，然后从堆顶向下调整D.无需调整20、队列是另一种特殊的线性数据结构，它遵循先进先出（FIFO）的原则。以下关于队列的说法中，错误的是？（）A.队列可以用数组或链表实现。B.队列的插入操作在队尾进行，删除操作在队首进行。C.队列可以用于实现任务调度、消息传递等。D.队列的容量是无限的，可以存储任意数量的元素。二、简答题（本大题共4个小题，共40分)1、（本题10分）论述伸展树在删除元素后的调整机制和性能影响。2、（本题10分）解释如何在一个链表中实现插入排序，给出算法步骤和实现代码，并分析其时间复杂度和空间复杂度。3、（本题10分）对于一个具有n个顶点的有向图，如何使用拓扑排序算法解决课程安排问题？4、（本题10分）详细说明在最短路径问题的变种中，如多源最短路径问题，如何求解。三、设计题（本大题共2个小题，共2