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

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页长春工业大学《数据可视化技术》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个顺序存储的栈中，若要实现共享栈，即两个栈共用一个数组空间，以下关于栈顶指针的设置，哪一种方案较为合理？A.两个栈的栈顶指针分别从数组的两端向中间移动B.两个栈的栈顶指针都从数组的同一端开始移动C.一个栈的栈顶指针从数组的开头移动，另一个从结尾移动D.以上都可以2、若哈希函数H(key)=key%7，要将关键字38插入到长度为7的哈希表中，其存储位置是：A.3B.5C.6D.03、对于一个具有n个节点的红黑树，插入一个新节点后，调整树的结构以保持红黑树性质，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、以下关于树的存储结构的描述，哪一项是不正确的？（）A.孩子兄弟表示法可以方便地实现树的遍历B.双亲表示法便于查找一个节点的双亲节点C.孩子链表表示法在处理多叉树时空间利用率较高D.以上存储结构在时间复杂度上没有明显差异5、对于一个具有n个元素的有序单链表，要查找一个值为x的元素，平均比较次数约为？A.n/2B.nC.lognD.16、对于一个具有n个元素的哈希表，负载因子越大，发生冲突的可能性如何变化？（）A.越大B.越小C.不变D.不确定7、一个具有n个顶点和e条边的无向图，采用邻接表存储，其空间复杂度为？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)8、对于一个具有n个元素的循环队列，队头指针为front，队尾指针为rear，队列满的条件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front9、以下哪种排序算法是稳定的排序算法？A.快速排序B.选择排序C.冒泡排序D.希尔排序10、以下哪种排序算法对大规模数据排序时，通常不被优先选择？A.冒泡排序B.插入排序C.快速排序D.归并排序11、设有一个具有n个顶点的带权无向图，使用普里姆（Prim）算法求最小生成树。在算法执行过程中，需要选择一个顶点作为起始点。以下关于起始点选择对算法时间复杂度的影响，哪一个是恰当的？A.起始点的选择对时间复杂度没有影响B.选择不同的起始点可能导致时间复杂度不同C.选择顶点度最小的作为起始点可以降低时间复杂度D.选择顶点度最大的作为起始点可以降低时间复杂度12、以下哪种数据结构适合频繁进行插入和删除操作，并且能够快速查找最大元素？（）A.数组B.链表C.栈D.最大堆13、在一个用数组实现的栈中，若要将栈的容量扩大一倍，以下哪种操作的时间复杂度最低？（）A.重新创建一个更大的数组并复制元素B.逐步将元素移动到新的更大的数组中C.直接在原数组后面追加空间D.以上操作时间复杂度相同14、在一个具有n个元素的双向链表中，删除一个指定节点，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、若一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，则其先序遍历序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB16、在一棵平衡二叉树中，插入一个新节点后可能导致失衡，需要进行调整。以下哪种调整操作可能涉及到旋转次数最多？（）A.LL型调整B.RR型调整C.LR型调整D.RL型调整17、对于一个具有n个元素的栈，若要实现将栈中元素逆置，需要借助的辅助数据结构为？（）A.队列B.栈C.链表D.数组18、对于一个大根堆，若将堆中所有元素按照层次遍历的顺序存储到一个数组中，以下关于数组元素的排列，哪一项是正确的？A.完全无序B.从左到右依次递减C.从左到右依次递增D.以上都不对19、设栈的初始状态为空，元素1、2、3、4、5依次入栈，出栈序列不可能是？（）A.54321B.21543C.21345D.1543220、在一个具有n个元素的双向循环链表中，删除一个节点后，需要修改几个指针？A.2B.3C.4D.5二、简答题（本大题共4个小题，共40分)1、（本题10分）详细论述在利用二叉树进行按层遍历的过程中，如何使用队列实现，并处理空层的情况，给出具体的算法步骤和代码实现。2、（本题10分）详细说明如何在一个具有n个元素的队列中，实现元素的循环移位，并分析其时间复杂度和空间复杂度。3、（本题10分）分析在字符串匹配中，Sunday算法的工作原理和特点。4、（本题10分）数组和链表在存储数据方面有哪些不同之处？各自的优缺点是什么？三、设计题（本大题