南京信息工程大学《数据可视化》2022-2023学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页南京信息工程大学

《数据可视化》2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个顶点的带权有向图，若采用迪杰斯特拉（Dijkstra）算法求单源最短路径，其时间复杂度为：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)2、树是一种非线性数据结构，它由节点和边组成。以下关于树的说法中，错误的是？（）A.树中的每个节点都有一个父节点（除了根节点）和零个或多个子节点。B.二叉树是一种特殊的树，每个节点最多有两个子节点。C.树可以用于实现文件系统、数据库索引等。D.树的遍历方式只有前序遍历、中序遍历和后序遍历三种。3、图的存储方式有邻接矩阵和邻接表两种，以下关于它们的特点的说法中，错误的是？（）A.邻接矩阵适合存储稠密图，空间复杂度为O(n^2)。B.邻接表适合存储稀疏图，空间复杂度为O(n+m)，其中n是顶点数，m是边数。C.邻接矩阵的查找边的时间复杂度为O(1)。D.邻接表的插入边和删除边的时间复杂度为O(n)。4、对于一个具有n个节点的红黑树，插入一个新节点后，调整树的结构以保持红黑树性质，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、以下哪种数据结构适合用于实现一个可以快速查找最大值和最小值的数据集合？A.链表B.栈C.队列D.堆6、在一个具有n个元素的二叉排序树中，查找一个不存在的元素，其时间复杂度最坏情况下为？（）A.O(1)B.O(log₂n)C.O(n)D.O(n²)7、在一个具有n个元素的有序单链表中，进行插入操作时，平均需要移动的元素个数约为？A.n/2B.nC.lognD.18、以下哪种排序算法的空间复杂度最低？A.归并排序B.快速排序C.冒泡排序D.插入排序9、在一个具有n个元素的双向链表中，要在指定节点之后插入一个新节点，需要修改几个指针？A.2B.3C.4D.510、一个具有n个顶点和e条边的无向图，采用邻接表存储，其空间复杂度为？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)11、在一个用顺序存储结构实现的栈中，若栈顶指针top指向栈顶元素的上一个位置，当栈为空时，top的值为？A.-1B.0C.1D.n-1（其中n为栈的最大容量）12、以下哪种数据结构可以快速查找一个有序数组中的中位数？A.二叉搜索树B.堆C.哈希表D.链表13、在一个具有n个元素的双向链表中，删除一个指定节点，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、数据结构的应用非常广泛，以下关于它们的应用场景的说法中，错误的是？（）A.数组可以用于存储和处理大量的相同类型的数据。B.链表可以用于实现动态数据结构，如栈、队列和链表等。C.树可以用于实现文件系统、数据库索引和表达式求值等。D.数据结构只在计算机科学领域有应用，在其他领域没有实际价值。15、对于一个具有n个元素的无序数组，若要找出第k小的元素，以下哪种算法较为合适？（）A.冒泡排序B.快速排序C.选择排序D.堆排序16、对于一个具有n个顶点和e条边的无向图，采用邻接表存储时，其空间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)17、在一棵平衡二叉树中，插入一个新节点后可能导致失衡，需要进行调整。以下哪种调整操作可能涉及到旋转次数最多？（）A.LL型调整B.RR型调整C.LR型调整D.RL型调整18、在一个B树中，每个节点的关键字数量最少为多少？（）A.1B.2C.⌈m/2⌉-1D.m-119、在一个链式存储的栈中，进行入栈和出栈操作时，以下关于时间复杂度的描述，哪一个是准确的？A.入栈和出栈的时间复杂度均为O(1)B.入栈的时间复杂度为O(n)，出栈的时间复杂度为O(1)C.入栈的时间复杂度为O(1)，出栈的时间复杂度为O(n)D.入栈和出栈的时间复杂度均为O(n)20、已知一个有序表为{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值为77的元素，需要比较的次数是（）。A.1B.2C.3D.4二、简答题（本大题共4个小题，共40分)1、（本题10分）对于一个用链表实现的栈，如何实现栈的逆序操作，要求空间复杂度为O(1)，给出算法思路和实现代码。2、（本题10分）解释并举例说明在一个具有n个元素的顺序表中，如何使用排序算法进行数据去重。3、（本题10分）论述在哈希表的性能评估中，如何通过实验测试不同负载因子和冲突解决方法的效果。4、（本题10分）阐述如何在一个二叉树中找到两个节点的最近公共祖先，