常州大学《数据可视化》2022-2023学年期末试卷

装订线装订线PAGE2第1页，共3页常州大学《数据可视化》

2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一棵平衡二叉树中，插入一个新节点后可能导致失衡，需要进行调整。以下哪种调整操作可能涉及到旋转次数最多？（）A.LL型调整B.RR型调整C.LR型调整D.RL型调整2、对于一个具有n个元素的快速排序，每次划分选取的基准元素不同，对排序的时间复杂度有何影响？（）A.没有影响B.可能会提高C.可能会降低D.以上都不对3、以下关于哈希冲突解决方法中二次探测法的描述，哪一项是不正确的？（）A.可以减少聚集现象B.探测的位置是连续的C.可能会出现找不到空闲位置的情况D.相比线性探测法，性能更优4、对于一个循环队列，若队头指针为front，队尾指针为rear，队列最大容量为MAX_SIZE，那么判断队空的条件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-15、在一个具有n个顶点的带权有向图中，使用迪杰斯特拉（Dijkstra）算法求单源最短路径。以下关于该算法的时间复杂度的描述，哪一项是准确的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)6、在一个具有n个顶点的有向强连通图中，至少需要多少条边？（）A.n-1B.nC.n(n-1)/2D.n(n-1)7、若一个图的广度优先遍历序列为ABCDEFG，则其深度优先遍历序列可能为？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG8、对于一个具有n个顶点的无向图，若要判断其是否为连通图，以下哪种方法效率较高？（）A.深度优先搜索B.广度优先搜索C.枚举所有边D.以上方法效率相同9、在一个有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比较的次数是：A.1B.2C.3D.410、栈和队列的操作可以用栈和队列的基本操作来实现，以下关于它们的操作实现的说法中，错误的是？（）A.可以用两个栈实现一个队列，也可以用两个队列实现一个栈。B.用栈实现队列时，需要考虑队列的先进先出特性，可能需要使用辅助栈。C.用队列实现栈时，需要考虑栈的后进先出特性，可能需要使用辅助队列。D.栈和队列的操作只能用栈和队列的基本操作来实现，不能用其他数据结构来辅助实现。11、设有一个带权无向图，采用Prim算法生成最小生成树。在算法执行过程中，每次选择的边都是权值最小的边。以下关于Prim算法的时间复杂度的描述，哪一项是准确的？A.O(n)B.O(n^2)C.O(nlogn)D.O(elogv)（其中n为顶点数，e为边数）12、对于一个具有n个元素的有序数组，使用二分查找算法查找一个特定元素。以下关于二分查找的时间复杂度的描述，哪一个是恰当的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一个具有n个节点的无向图中，若要判断图是否连通，可以使用哪种算法？A.深度优先搜索B.广度优先搜索C.克鲁斯卡尔算法D.以上都可以14、在一个堆排序中，最大堆用于升序排序，最小堆用于降序排序。那么对于一个初始无序的数组，构建最大堆的时间复杂度是多少？（）A.O(n)B.O(log₂n)C.O(nlog₂n)D.O(n²)15、设有一个带头结点的单链表，头指针为head，若要在第一个元素之前插入一个新元素，则需要执行的操作是（）。A.s->next=head;head=s;B.s->next=head->next;head->next=s;C.head->next=s;s->next=head;D.s->next=head;s=head;16、在一个具有n个顶点的强连通图中，至少有多少条边？（）A.n-1B.nC.n(n-1)/2D.n(n-1)17、在一棵AVL树中，进行插入操作后，可能导致树失去平衡，此时需要进行的旋转操作最多为（）A.1次B.2次C.logn次D.n次18、对于一个具有n个节点的二叉排序树，删除一个节点后，重新调整为二叉排序树，其时间复杂度最坏情况下为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一个有向图中，所有顶点的入度之和与出度之和的关系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.没有确定的关系20、对于一个具有n个元素的无序链表，若要对其进行排序，以下哪种排序算法较为合适？（）A.冒泡排序B.快速排序C.插入排序D.选择排序二、简答题（本大题共4个小题，共40分)1、（本题10分）对于一个用链表实现的有序表，解释如何合并两个有序链表为一个新的有序链表，给出算法步骤和时间复杂度分析。2、（本题10分）论述在有向图中，如何判断是否存在回路，以及如何找出所有的强连通分量。3、（本题10分）阐述如何在一个具有n个元素的无序数组中，使用冒泡排序算法进行排序，并分析其时间复杂度和空间复杂度。4、（本题10分）阐述二叉树的定义和基本性质，说明二叉树的遍历方式有哪些，并