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

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页长春工业大学

《数据可视化》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个元素的顺序存储的循环队列，队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，若队列非空，则队列中元素的个数为？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+12、在一棵二叉树中，若每个节点的左子树和右子树的高度最多相差1，则该二叉树被称为平衡二叉树。对于一个平衡二叉树，进行插入操作后，为了保持平衡，可能需要进行多少次旋转调整？A.0次B.1次C.最多2次D.不确定3、在一个链队列中，假设队头指针为front，队尾指针为rear，删除队头元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL4、在数据结构中，斐波那契堆是一种可合并堆，以下关于斐波那契堆的特点，描述不正确的是（）A.插入操作的时间复杂度为O(1)B.查找最小元素的时间复杂度为O(1)C.删除最小元素的时间复杂度为O(logn)D.合并操作的时间复杂度为O(n)5、在数据结构中，桶排序是一种外部排序算法，以下关于桶排序的描述，错误的是（）A.要求输入数据具有特定的分布B.时间复杂度为O(n)C.空间复杂度较高D.适用于大规模数据排序6、已知一个完全二叉树的节点总数为100，其叶子节点的个数为（）。A.49B.50C.51D.不确定7、在一个用十字链表存储的有向图中，查找一个顶点的所有出边和入边的时间复杂度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)8、哈希表是一种用于快速查找的数据结构，通过哈希函数将关键字映射到存储位置。关于哈希冲突的解决方法，错误的是（）A.开放定址法通过寻找空闲位置来解决冲突B.链地址法将冲突的元素存储在链表中C.再哈希法通过更换哈希函数来解决冲突D.哈希冲突无法避免，且对查找效率没有影响9、以下哪种数据结构常用于实现并查集？（）A.数组B.链表C.树D.哈希表10、以下哪种数据结构可以方便地实现字符串的模式匹配操作？A.二叉树B.哈希表C.栈D.后缀树11、若一棵二叉树的叶子节点数为n0，度为2的节点数为n2，则n0和n2之间的关系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+112、已知一个图的邻接表存储结构，若要判断任意两个顶点之间是否存在边，哪种方法最有效？（）A.遍历邻接表B.建立逆邻接表C.建立邻接矩阵D.深度优先搜索13、已知一个哈希表的长度为11，哈希函数为H(key)=key%11，采用二次探测法处理冲突。若依次插入关键字15、38、61、84，则在查找关键字61时需要进行几次探测？（）A.1B.2C.3D.414、以下哪种排序算法在平均情况下的时间复杂度最优？A.冒泡排序B.快速排序C.插入排序D.选择排序15、在一个具有n个节点的二叉排序树中，删除一个节点后，为了保持二叉排序树的性质，可能需要进行哪些操作？A.仅调整删除节点的子树B.从根节点开始重新调整C.调整整个树的结构D.以上都有可能16、在一个具有n个顶点的有向完全图中，边的数量为？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n17、对于一个具有n个元素的无序数组，使用插入排序进行排序，其最好情况下的时间复杂度为（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)18、对于一个具有n个元素的快速排序，每次划分选取的基准元素不同，对排序的时间复杂度有何影响？（）A.没有影响B.可能会提高C.可能会降低D.以上都不对19、在一个具有n个顶点和m条边的无向图中，若采用邻接表存储，则存储空间复杂度主要取决于？A.nB.mC.n+mD.n^220、已知一个栈的进栈序列为1,2,3,4,5，下列序列中不可能是出栈序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,5二、简答题（本大题共4个小题，共40分)1、（本题10分）解释如何判断一个二叉树是否为满二叉树，给出相应的算法和代码。2、（本题10分）深入探讨在一个具有n个元素的二叉搜索树中，如何求第k小的元素。3、（本题10分）阐述队列在任务调度中的应用，如任务队列、优先级队列等，并解释其作用。4、（本题10分）在一个具有n个元素的双向链表中，说明如何实现向前和向后的遍历，以及如何在双向链表中插入和删除节点。三、设计题（本大题共2个小