北京联合大学《数据结构》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页北京联合大学《数据结构》

2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种数据结构常用于实现LRU（最近最少使用）缓存淘汰策略？（）A.队列B.栈C.哈希表D.双向链表2、在一个不带头结点的单链表中，若要删除表头结点，需要修改几个指针？（）A.0B.1C.2D.33、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则存储空间的复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)4、在一个具有n个元素的顺序表中，若要查找一个元素，平均需要比较多少次？（）A.n/2B.nC.lognD.不确定5、若要在一个具有n个元素的有序链表中插入一个新元素，使其仍然有序，平均时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)6、对于一个有向图，使用邻接矩阵存储，判断是否存在从顶点i到顶点j的边的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n^2)7、以下哪种数据结构常用于实现并查集？（）A.数组B.链表C.树D.哈希表8、若对线性表的操作只有两种，即插入和删除，且以链表作为存储结构，则插入和删除操作的时间复杂度分别为：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)9、对于一个具有n个顶点的带权有向图，若采用迪杰斯特拉（Dijkstra）算法求单源最短路径，其时间复杂度为：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)10、以下哪种数据结构能够在O(1)的时间复杂度内实现元素的随机访问？（）A.链表B.队列C.栈D.数组11、已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则其先序遍历序列为（）。A.CEABDB.CEDBAC.CABDED.CEDAB12、在一个具有n个元素的二叉排序树中，查找一个不存在的元素，其时间复杂度最坏情况下为？（）A.O(1)B.O(log₂n)C.O(n)D.O(n²)13、在一个用邻接表表示的无向图中，若要删除一条边，需要进行哪些操作？A.在两个相关顶点的邻接表中删除对应的边节点B.只在一个顶点的邻接表中删除对应的边节点C.重新构建邻接表D.以上都不对14、二叉树是一种重要的数据结构。对于一个满二叉树，若其高度为h，则节点总数为多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-115、对于一个用数组实现的最小堆，若要删除堆顶元素并调整堆，以下操作正确的是？（）A.将堆尾元素移到堆顶，然后从堆顶向下调整B.将堆顶元素与堆尾元素交换，然后从堆顶向下调整C.将堆顶元素删除，然后重新构建堆D.以上都不对16、数据结构的应用非常广泛，以下关于它们的应用场景的说法中，错误的是？（）A.数组可以用于存储和处理大量的相同类型的数据。B.链表可以用于实现动态数据结构，如栈、队列和链表等。C.树可以用于实现文件系统、数据库索引和表达式求值等。D.数据结构只在计算机科学领域有应用，在其他领域没有实际价值。17、对于一个用邻接矩阵存储的图，若要判断两个顶点之间是否存在边，时间复杂度为？（）A.O(1)B.O(n)C.O(log₂n)D.O(n²)18、若对一棵二叉排序树进行中序遍历，得到的节点序列是一个递增序列，则该二叉排序树（）。A.没有左子树B.没有右子树C.左子树均为空D.右子树均为空19、在一个具有n个顶点的强连通图中，至少有（）条边。A.n-1B.nC.n(n-1)D.n(n-1)/220、在一个具有n个节点的图中，使用弗洛伊德算法求所有节点对之间的最短路径，其时间复杂度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)二、简答题（本大题共4个小题，共40分)1、（本题10分）在一个具有n个顶点的无向图中，如何找出所有的割点，给出一种有效的算法并分析其时间复杂度。2、（本题10分）在一个链表中，如何实现链表的复制操作？3、（本题10分）论述如何使用随机化快速排序优化普通快速排序在某些特殊情况下的性能。4、（本题10分）详细阐述在堆的应用拓展中，如何使用堆进行数据流中的中