沈阳城市学院《数据可视化R语言》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页沈阳城市学院

《数据可视化R语言》2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的循环队列中，若队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，则队列中元素的个数为？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+12、以下哪种数据结构常用于实现文件系统的目录结构？A.二叉树B.多叉树C.链表D.栈3、在一个具有n个元素的小根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)4、在一个顺序存储的队列中，若要在队尾插入一个元素，需要移动元素的平均次数为（）A.0B.n/2C.nD.n-15、已知一个图的邻接表存储结构，若要判断任意两个顶点之间是否存在边，哪种方法最有效？（）A.遍历邻接表B.建立逆邻接表C.建立邻接矩阵D.深度优先搜索6、在一个带头结点的单链表中，若要删除表中所有值为x的结点，最优的算法时间复杂度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)7、若要对一棵二叉排序树进行中序遍历，得到的序列是一个有序序列，这是因为二叉排序树的定义具有什么特性？（）A.左子树的值小于根节点，右子树的值大于根节点B.左子树和右子树的深度相同C.每个节点的值都不同D.以上都不是8、在数据结构中，斐波那契堆是一种可合并堆，以下关于斐波那契堆的特点，描述不正确的是（）A.插入操作的时间复杂度为O(1)B.查找最小元素的时间复杂度为O(1)C.删除最小元素的时间复杂度为O(logn)D.合并操作的时间复杂度为O(n)9、以下哪种数据结构常用于实现图的广度优先遍历的辅助队列？A.循环队列B.链队列C.优先队列D.双端队列10、若要对一个具有n个元素的无序数组进行排序，以下哪种排序算法在最坏情况下的时间复杂度最低？A.冒泡排序B.插入排序C.选择排序D.归并排序11、对于一个具有n个元素的顺序存储的循环队列，队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，若队列非空，则队列中元素的个数为？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+112、对于一个具有n个节点的完全二叉树，若按层序编号，则编号为i的节点，其双亲节点的编号为？A.i/2B.(i-1)/2C.2iD.2i+113、对于一个满二叉树，若其高度为h，则其节点总数为多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-114、对于一个采用链式存储的队列，若队头指针和队尾指针相同，则队列的状态为：A.队空B.队满C.不确定D.队列中只有一个元素15、在一个循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，队列最大容量为MAXSIZE，若当前队列长度为n，则判断队满的条件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE16、图是一种复杂的数据结构，有邻接矩阵和邻接表两种存储方式。对于一个稀疏图，以下说法正确的是（）A.邻接矩阵比邻接表更节省存储空间B.邻接表更适合用于存储和遍历C.两种存储方式的时间复杂度相同D.稀疏图的边数很少，节点数很多17、对于单链表，若要访问链表中的第i个元素，必须从链表的头指针开始依次遍历，平均时间复杂度为O(n)。那么如果要在链表的末尾添加一个新元素，时间复杂度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)18、已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则其先序遍历序列为（）。A.CEABDB.CEDBAC.CABDED.CEDAB19、在一个B树中，每个节点的关键字数量最少为多少？（）A.1B.2C.⌈m/2⌉-1D.m-120、在一个具有n个元素的有序单链表中，若要查找一个特定元素，以下关于查找操作的时间复杂度的描述，哪一项是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）解释如何在一个具有n个元素的最小堆中，找出第k小的元素，并分析其时间复杂度。2、（本题10分）阐述如何在一个具有n个顶点和e条边的带权无向图中，使用Johnson算法求解所有顶点对之间的最短路径问题，分析其原理和时间复杂度。3、（本题10分）深入探讨在一个具有n个元素的小根堆中，如何使用堆来实现优先队列的功能。4、（本题10分）论述伸展