北方民族大学《数据可视化》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页北方民族大学《数据可视化》

2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的顺序表中，进行插入操作时，平均移动元素的个数为：A.n/2B.(n+1)/2C.nD.n-12、二叉树是一种重要的数据结构。对于一个满二叉树，若其高度为h，则节点总数为多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-13、对于一个具有n个元素的无序数组，使用冒泡排序进行排序，最坏情况下的比较次数为？A.n(n-1)/2B.nlognC.n^2D.2^n4、对于一个具有n个顶点的无向连通图，若要判断其是否存在环，以下哪种算法的时间复杂度最低？A.深度优先搜索B.广度优先搜索C.拓扑排序D.以上算法时间复杂度相同5、以下哪种数据结构常用于实现表达式求值？A.二叉树B.栈C.队列D.哈希表6、已知一个有序表为{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值为77的元素，需要比较的次数是（）。A.1B.2C.3D.47、已知一个哈希表的装填因子为0.8，哈希函数为H(key)=key%11，采用线性探测法处理冲突。若依次插入关键字31、25、19、49、37、21、13、17，则在查找关键字19时需要进行几次比较？（）A.1B.2C.3D.48、在图的存储结构中，邻接多重表主要用于存储无向图，以下关于邻接多重表的特点，描述错误的是（）A.可以方便地删除边B.存储空间比邻接矩阵节省C.对于判断两点之间是否有边，效率较高D.不适合用于有向图的存储9、在数据结构中，跳表的索引层数是根据数据量动态调整的，以下关于索引层数调整的描述，错误的是（）A.当数据量增加时，可能增加索引层数B.索引层数越多，查找效率越高C.调整索引层数的过程比较复杂D.索引层数的调整不会影响数据的存储结构10、对于一个具有n个顶点的连通图，其生成树中边的数量为：A.n-1B.nC.n+1D.不确定11、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法12、在一个带头结点的双向链表中，若要在p所指结点之后插入一个新结点q，需要修改几个指针？（）A.2B.4C.6D.813、对于一个具有n个元素的小根堆，若要删除堆顶元素并重新调整堆，以下关于操作的平均时间复杂度的描述，哪一项是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、对于一个具有n个节点的二叉排序树，删除一个节点后，重新调整为二叉排序树，其时间复杂度最坏情况下为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、在一棵二叉搜索树中，删除一个有两个子节点的节点时，通常采用的方法是：A.用左子树的最大值替代该节点B.用右子树的最小值替代该节点C.随机选择左子树或右子树的节点替代D.不进行替代，直接删除16、在数据结构中，对于一个具有n个元素的有序数组，使用二分查找算法查找一个特定元素，其平均时间复杂度为（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)17、二叉树是一种重要的数据结构，若一个二叉树的先序遍历序列为ABC，中序遍历序列为BAC，那么它的后序遍历序列是什么？（）A.BCAB.CBAC.CABD.ACB18、对于一个具有n个元素的有序双向链表，查找中间元素的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、若一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBDAEGF，则其后序遍历序列为？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF20、对于一个具有n个元素的快速排序，在最好情况下，其时间复杂度为？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)二、简答题（本大题共4个小题，共40分)1、（本题10分）详细解释什么是平衡二叉树，以及如何通过旋转操作来保持平衡二叉树的平衡性质，给出常见的旋转类型和示例。2、（本题10分）详细说明如何在一个图中判断两个顶点是否在同一个连通分量中。3、（本题10分）解释什么是可持久化线段树，并说明其应用场景。4、（本题10分）详细说明如何反转一个链表，分析所使用的算法和时间复杂度。