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

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

《数据可视化》2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在数据结构中，基数排序是一种非比较排序算法，以下关于基数排序的描述，不正确的是（）A.按照位数依次进行排序B.可以用于整数和字符串的排序C.时间复杂度为O(d(n+r))，其中d是位数，r是基数D.对数据的分布敏感2、图的存储方式有邻接矩阵和邻接表两种，以下关于它们的特点的说法中，错误的是？（）A.邻接矩阵适合存储稠密图，空间复杂度为O(n^2)。B.邻接表适合存储稀疏图，空间复杂度为O(n+m)，其中n是顶点数，m是边数。C.邻接矩阵的查找边的时间复杂度为O(1)。D.邻接表的插入边和删除边的时间复杂度为O(n)。3、在一个具有n个元素的顺序存储的循环队列中，队满的条件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front4、对于一个具有n个元素的大顶堆，若要获取堆中的第k大元素（1<=k<=n），以下哪种方法效率较高？A.先排序再获取B.每次删除堆顶元素k-1次C.构建一个大小为k的小顶堆，然后逐步替换D.以上方法效率相同5、在一个顺序存储的数组中实现一个简单的栈结构，若栈顶指针top初始值为-1，当进行一次入栈操作后，top的值应该如何变化？A.top不变B.top=top+1C.top=top-1D.top=06、若一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，则其先序遍历序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB7、对于一个采用顺序存储结构的完全二叉树，若已知根节点在数组中的位置为1，则其第i个节点的左孩子节点在数组中的位置为？A.2iB.2i+1C.i*2D.i*2-18、对于一个具有n个元素的哈希表，若采用链地址法处理冲突，以下关于查找操作的平均时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、以下关于哈希冲突解决方法中二次探测法的描述，哪一项是不正确的？（）A.可以减少聚集现象B.探测的位置是连续的C.可能会出现找不到空闲位置的情况D.相比线性探测法，性能更优10、设有一个广义表L=((a,b),c,(d,e))，其表头和表尾分别为？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)11、以下哪种排序算法在数据基本有序时的时间复杂度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.选择排序12、树的遍历方式有多种，以下关于它们的说法中，错误的是？（）A.前序遍历是先访问根节点，然后遍历左子树，最后遍历右子树。B.中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。C.后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。D.树的遍历方式只有前序遍历、中序遍历和后序遍历三种。13、若哈希函数H(key)=key%7，要将关键字38插入到长度为7的哈希表中，其存储位置是：A.3B.5C.6D.014、数据结构的抽象数据类型（ADT）是一种定义数据结构的方式，它包括数据的存储结构和操作集合。以下关于ADT的说法中，错误的是？（）A.ADT使得数据结构的实现与使用分离，提高了代码的可维护性和可扩展性。B.ADT可以用多种编程语言实现，不同的实现方式可能会有不同的性能和特点。C.ADT的操作集合包括插入、删除、查找、遍历等基本操作。D.ADT只适用于线性数据结构，不适用于非线性数据结构。15、以下关于字符串压缩算法的描述，哪一项是不正确的？（）A.哈夫曼编码可以根据字符出现频率进行压缩B.LZW压缩算法基于字典进行压缩C.压缩算法一定能减小字符串的存储空间D.不同的压缩算法适用于不同类型的字符串16、若要对一棵二叉排序树进行中序遍历，得到的序列是一个有序序列，这是因为二叉排序树的定义具有什么特性？（）A.左子树的值小于根节点，右子树的值大于根节点B.左子树和右子树的深度相同C.每个节点的值都不同D.以上都不是17、对于一个具有n个顶点和e条边的带权无向图，若采用克鲁斯卡尔（Kruskal）算法生成最小生成树，其时间复杂度为？（）A.O(n²)B.O(eloge)C.O(nlogn)D.O(e²)18、在一个用数组实现的小根堆中，若要插入一个元素，应该将其插入到数组的哪个位置？A.数组末尾B.堆顶C.任意位置D.以上都不对19、在一个具有n个节点的图中，使用弗洛伊德算法求所有节点对之间的最短路径，其时间复杂度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)20、排序算法的稳定性和时间复杂度可以用于选择合适的排序算法，以下关于它们的说法中，错误的是？（）A.稳定性对于某些应用场景非常重要，如对具有多个关键字的记录进行排序时。B.时间复杂度是衡量排序算法效率的重要指标，不同的排序算法具有不同的时间复杂度。C.可以根据实际情况选择稳定的或不稳定的排序算法，以及时间复杂度较低的排序算法。D.排序算法的稳定性和时间复杂度只适用于理论研究，在实际应用中没有实际价值。二、简答题（本大题共4个小题，共40分)1、（本题10分）对于一个用链表实现的队列，如何实现循环队列的扩容操作，给出算法思路和代码实现。2、（本题10分）深入分析在一个具有n个元素的顺序表中，如何进行插入排序，并分析其时间复杂度。3、（本题10分）深入分析在一个具有n个元素的链表中，如何删除指定区间内的节点。4、（本题10分）解释如何使用递归思