长春大学《数据可视化》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页长春大学《数据可视化》

2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、已知一个完全二叉树的节点总数为100，其叶子节点的个数为（）。A.49B.50C.51D.不确定2、在一个具有n个顶点的无向图中，使用广度优先遍历算法。以下关于遍历过程中使用的辅助队列的空间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(n^2)3、若一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则其先序遍历序列为？（）A.CEDBAB.CEABDC.ABCDED.EDCAB4、以下关于二叉排序树的描述，错误的是：A.左子树上所有结点的值均小于根结点的值B.右子树上所有结点的值均大于根结点的值C.中序遍历二叉排序树可得到一个有序序列D.二叉排序树的查找效率总是最高的5、在一个具有n个元素的队列中，若要获取队头元素的前一个元素但不删除，以下操作不可行的是？（）A.遍历整个队列B.使用辅助数据结构C.直接获取D.以上都不可行6、在数据结构中，树的遍历可以采用递归和非递归方式。以下关于非递归中序遍历二叉树的说法，错误的是（）A.可以使用栈来辅助实现B.比递归方式更复杂C.时间复杂度与递归方式相同D.空间复杂度一定比递归方式低7、以下哪种数据结构能够在O(1)的时间复杂度内实现元素的随机访问？（）A.链表B.队列C.栈D.数组8、设有一个具有n个节点的二叉平衡树，若要插入一个新节点并保持平衡，以下关于插入操作的平均时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、对于一个具有n个顶点和m条边的有向图，使用邻接表存储，其入度和出度的计算时间复杂度分别为（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)10、对于一个有向无环图（DAG），进行拓扑排序的方法不止一种。以下关于拓扑排序的描述，错误的是（）A.可以使用深度优先搜索实现B.结果不唯一C.可以用于判断图中是否存在环D.所有节点的入度在排序过程中不会改变11、在一个平衡二叉树中，插入一个新节点后可能会导致树的不平衡，此时需要进行调整。以下哪种调整操作可能会被执行？（）A.左旋B.右旋C.先左旋后右旋D.以上都有可能12、对于一个具有n个元素的顺序存储的栈，若要判断栈是否已满，应判断？（）A.top==n-1B.top==nC.top>=n-1D.top>=n13、在一棵二叉树中，若度为2的节点有10个，度为1的节点有20个，那么叶子节点的数量是多少？A.11B.21C.30D.无法确定14、在一个具有n个元素的无序数组中，使用选择排序进行排序。以下关于选择排序的时间复杂度的描述，哪一项是正确的？A.最好情况为O(n)，最坏情况为O(n^2)B.最好情况和最坏情况均为O(n)C.最好情况为O(nlogn)，最坏情况为O(n^2)D.最好情况和最坏情况均为O(n^2)15、在一个具有n个元素的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时，需要向后移动的元素个数为：A.n-iB.iC.n-i+1D.n-i-116、在一个具有n个元素的循环双链表中，若要在表头插入一个新元素，以下关于插入操作的时间复杂度的描述，哪一项是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、图的存储方式和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.图的邻接矩阵可以用于表示网络中的连接关系，适用于社交网络分析和交通网络规划等。B.图的邻接表可以用于表示稀疏图，适用于地图绘制和电路图设计等。C.图的遍历方式可以用于解决路径规划、网络流问题和最小生成树问题等，适用于物流配送和通信网络优化等。D.图的存储方式和遍历方式只适用于理论研究，在实际应用中没有实际价值。18、在一个带权无向图中，使用普里姆算法构造最小生成树时，每次选择的边是？（）A.权值最小的边B.连接两个连通分量的权值最小的边C.任意一条边D.以上都不对19、在一个用链表实现的栈中，若要获取栈底元素的值，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、对于一个具有n个顶点的带权有向图，若采用迪杰斯特拉（Dijkstra）算法求单源最短路径，其时间复杂度为：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)二、简答题（本大题共4个小题，共40分)1、（本题10分）详细阐述在图的表示中，如何将一个有权无向图转换为有权有向图，并分析其影响。2、（本题10分）在一个链表中，如何删除所有值为指定值的结点？3、（本题10分）比较冒泡排序和堆排序在时间复杂度上的优劣。4、（本题10分）论述在一个具有n个顶点的有向图中，如何计算强连通分