湖南财政经济学院《数据可视化》2023-2024学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页湖南财政经济学院

《数据可视化》2023-2024学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个节点的完全二叉树中，其叶子节点的数量大约为（）A.n/2B.n/4C.n/8D.n/2-12、对于一个具有n个节点的二叉树，其先序遍历、中序遍历和后序遍历的结果都是唯一确定的，这个二叉树一定是（）A.满二叉树B.完全二叉树C.单支树D.以上都不是3、在一个具有n个元素的链式队列中，若队头指针为front，队尾指针为rear，要入队一个元素，应执行的操作是？（）A.rear->next=newNode;rear=newNode;B.newNode->next=front;front=newNode;C.rear->next=newNode;front=newNode;D.newNode->next=rear;rear=newNode;4、在一棵二叉搜索树中，删除一个只有左子树的节点，其右子树的节点需要（）A.替换被删除节点B.保持不动C.全部删除D.移动到左子树5、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则该二叉树的后序遍历序列为（）。A.CBEFDGAB.CEBFDGAC.CBEFGDAD.CEBFGDA6、对于单链表，若要访问链表中的第i个元素，必须从链表的头指针开始依次遍历，平均时间复杂度为O(n)。那么如果要在链表的末尾添加一个新元素，时间复杂度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、若一个图的邻接矩阵对角线以下（不包括对角线）的元素全为0，则该图一定是：A.无向图B.有向图C.强连通图D.弱连通图8、对于一个具有n个节点的二叉树，进行先序遍历和中序遍历，得到的序列相同，则该二叉树的形状为？A.只有一个根节点B.所有节点只有左子树C.所有节点只有右子树D.是一棵满二叉树9、在一个具有n个元素的有序双向链表中，删除一个节点并保持链表有序，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一个具有n个节点的带权无向图中，使用普里姆算法构造最小生成树，其时间复杂度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取决于图的结构11、在一个具有n个顶点的图中，若存在回路，则深度优先遍历可能会出现什么情况？（）A.访问某些顶点多次B.无法完成遍历C.结果不正确D.以上都有可能12、队列是一种先进先出的线性表，若用一个数组实现循环队列，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素，队列最大容量为MAX_SIZE，那么判断队满的条件是什么？（）A.(rear+1)%MAX_SIZE==frontB.rear==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-113、在一个具有n个顶点的连通图中，生成树的边数一定为？（）A.n-1B.nC.n+1D.2n14、在一个具有n个元素的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时，需要向后移动的元素个数为：A.n-iB.iC.n-i+1D.n-i-115、以下哪种数据结构常用于实现字符串的最长公共子序列问题？A.二维数组B.栈C.队列D.树16、若要从一个具有n个元素的有序单链表中删除所有值重复的元素，使得链表中每个元素的值都不同，最优的算法时间复杂度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)17、在一个具有n个顶点和e条边的无向图中，使用邻接矩阵存储，进行深度优先遍历，其时间复杂度为？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)18、在数据结构的应用中，优先队列常用于实现任务调度，以下关于优先队列的描述，错误的是（）A.可以使用堆来实现B.元素的出队顺序按照优先级确定C.插入元素的时间复杂度为O(logn)D.不支持修改元素的优先级19、在一个二叉搜索树中，进行中序遍历得到的序列是一个有序序列。若要删除一个节点，并且保持二叉搜索树的性质不变，以下哪种情况处理起来最复杂？（）A.删除叶子节点B.删除只有一个子节点的节点C.删除有两个子节点的节点D.以上情况复杂度相同20、在一个具有n个元素的有序数组中，若要删除一个特定元素，并且保持数组的有序性，以下关于删除操作的平均时间复杂度的描述，哪一项是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）阐述如何使用计数排序对特定条件下的数据进行排序，分析其优缺点和适用场景。2、（本题10分）阐述如何在一个具有n个元素的顺序表中，进行查找操作，并分析其时间复杂度和空间复杂度。3、（本题10分）论述跳表在数据更新操作频繁且数据量大的情况下的性能瓶颈及解决方案。4、（本题10分）解释有向无环图的概念，说明如何使用拓扑排序对有向无环图进行顶点的排序，并分析其时间复杂度。三、