北京城市学院《数据可视化技术》2022-2023学年期末试卷

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

《数据可视化技术》2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、图是一种复杂的数据结构。在有向图中，顶点的入度是指指向该顶点的边的数量。若要计算一个有向图中所有顶点的入度，哪种算法较为合适？A.深度优先搜索B.广度优先搜索C.拓扑排序D.以上都可以2、在二叉搜索树的删除操作中，如果删除的节点是其父节点的唯一子节点，以下处理方式错误的是（）A.直接将该节点删除，不做其他调整B.将该节点的值替换为其父节点的值，并删除父节点C.将该节点的左子树或右子树替代该节点D.以上处理方式都不对3、在数据结构中，树的遍历可以采用递归和非递归方式。以下关于非递归中序遍历二叉树的说法，错误的是（）A.可以使用栈来辅助实现B.比递归方式更复杂C.时间复杂度与递归方式相同D.空间复杂度一定比递归方式低4、对于一个具有n个顶点的无向图，若要判断其是否为连通图，以下哪种方法效率较高？（）A.深度优先搜索B.广度优先搜索C.枚举所有边D.以上方法效率相同5、在一个顺序存储的栈中，若要实现共享栈，即两个栈共用一个数组空间，以下关于栈顶指针的设置，哪一种方案较为合理？A.两个栈的栈顶指针分别从数组的两端向中间移动B.两个栈的栈顶指针都从数组的同一端开始移动C.一个栈的栈顶指针从数组的开头移动，另一个从结尾移动D.以上都可以6、对于一个具有n个元素的哈希表，负载因子（loadfactor）为0.7，当表中元素数量超过一定阈值时需要进行扩容。以下关于扩容操作的时间复杂度的描述，哪一个是恰当的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、对于一个用邻接矩阵存储的图，若要判断两个顶点之间是否存在边，时间复杂度为？（）A.O(1)B.O(n)C.O(log₂n)D.O(n²)8、若要对一个具有n个元素的有序链表进行二分查找，是否可行？（）A.可行B.不可行C.有时可行D.取决于链表长度9、若要对一棵二叉树进行层次遍历，需要使用哪种数据结构辅助？（）A.栈B.队列C.优先队列D.哈希表10、对于一个大根堆，若要删除堆顶元素并保持堆的性质，以下哪种操作是正确的？A.将堆底元素移到堆顶，然后从堆顶向下调整B.将堆顶元素直接删除，不进行其他操作C.将堆顶元素与任意子节点交换，然后调整D.以上都不对11、在一个字符串中，要查找某个子串首次出现的位置，通常可以使用哪种算法？（）A.冒泡排序B.快速排序C.顺序查找D.二分查找12、对于一个具有n个顶点和e条边的有向图，采用邻接表存储，进行深度优先遍历。以下关于遍历的时间复杂度的描述，哪一个是恰当的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)13、在一个具有n个元素的队列中，若要获取队头元素的前一个元素但不删除，以下操作不可行的是？（）A.遍历整个队列B.使用辅助数据结构C.直接获取D.以上都不可行14、设有一个栈S和一个队列Q，初始时栈为空，队列为{1,2,3,4,5}。经过一系列入栈和出栈、入队和出队操作后，栈顶元素为3，此时队列的头元素为？（）A.1B.2C.4D.515、以下关于拓扑排序的描述，正确的是：A.拓扑排序的结果是唯一的B.一个有环的图也可以进行拓扑排序C.拓扑排序可以用于判断一个图是否有环D.拓扑排序只能用于有向图16、在一个具有n个顶点的图中，若存在回路，则深度优先遍历可能会出现什么情况？（）A.访问某些顶点多次B.无法完成遍历C.结果不正确D.以上都有可能17、在一个具有n个元素的无序链表中，若要对其进行快速排序，以下关于快速排序的平均时间复杂度的描述，哪一项是准确的？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)18、队列也是一种常见的数据结构，遵循先进先出的原则。对于一个循环队列，以下说法不正确的是（）A.队头指针和队尾指针的移动需要考虑循环的情况B.当队头指针等于队尾指针时，队列为空C.可以通过牺牲一个存储单元来区分队列空和队列满的情况D.循环队列可以避免假溢出的问题19、栈和队列在计算机科学中有很多应用，以下关于它们的应用场景的说法中，错误的是？（）A.栈可以用于实现表达式求值、括号匹配等。B.队列可以用于实现任务调度、消息队列等。C.栈和队列可以用于实现图的深度优先搜索和广度优先搜索。D.栈和队列只能在编程语言的底层实现中使用，不能在实际应用中直接使用。20、在一个具有n个元素的有序链表中，若要查找第k个元素，以下关于查找操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(k)D.O(n)二、简答题（本大题共4个小题，共40分)1、（本题10分）解释什么是AVL树，并说明其在保持平衡方面的调整策略。2、（本题10分）论述AVL树的删除操作中可能出现的四种情况及相应的调整策略。3、（本题10分）详细阐述在拓扑排序的性能优化中，如何减少不必要的比较和操作。4、（本题10分）在数据结构中，阐述如何使用跳表进行范围查询，给出算法