北京邮电大学《数据结构课程设计》2021-2022学年期末试卷

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

2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个链式存储的线性表中，若要在第i个位置插入一个新元素，需要修改多少个指针？（）A.1B.2C.iD.i+12、在数据结构中，栈是一种特殊的线性表，遵循先进后出的原则。以下关于栈的操作，错误的是（）A.入栈操作将元素添加到栈顶B.出栈操作取出并删除栈顶元素C.可以在栈的任意位置进行插入和删除操作D.栈顶指针始终指向栈顶元素3、设有一个长度为n的顺序表，要在第i个元素之前插入一个新元素，并且移动元素的平均次数为n/2，则插入算法的平均时间复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)4、在数据结构中，线段树的区间更新操作可以通过懒标记实现，以下关于懒标记的描述，不正确的是（）A.减少不必要的节点更新B.提高更新操作的效率C.可能会导致查询结果不准确D.标记需要在适当的时候向下传递5、在一个哈希表中，若采用线性探测法解决哈希冲突，当发生冲突时，新元素会存储在什么位置？A.冲突位置的下一个位置B.冲突位置C.随机位置D.以上都不对6、以下关于堆的描述，正确的是：A.大顶堆中每个父节点的值都大于其子节点的值B.小顶堆中每个父节点的值都小于其子节点的值C.堆可以用顺序存储也可以用链式存储D.堆是完全二叉树7、对于一个具有n个元素的希尔排序，其时间复杂度取决于？（）A.初始序列B.增量序列C.元素值D.以上都是8、对于一个采用链式存储的队列，若队头指针和队尾指针相同，则队列的状态为：A.队空B.队满C.不确定D.队列中只有一个元素9、在一个循环链表中，若要删除链表中的最后一个节点，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一个具有n个元素的栈中，若要获取栈底元素但不删除，需要进行多少次操作？（）A.1B.n-1C.nD.n+111、在一个具有n个节点的带权无向图中，使用普里姆算法构造最小生成树，其时间复杂度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取决于图的结构12、以下哪种数据结构常用于实现字符串的反转操作？A.栈B.队列C.链表D.树13、若要在一个具有n个元素的有序链表中插入一个新元素，使其仍然有序，平均时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)14、对于一个具有n个顶点和e条边的带权无向图，若采用Prim算法生成最小生成树，其时间复杂度为（）。A.O(n^2)B.O(elog₂e)C.O(nlog₂n)D.O(n^3)15、对于一个具有n个元素的选择排序，在最坏情况下，需要进行多少次交换操作？（）A.n-1B.nC.n(n-1)/2D.016、若要在一个具有n个元素的有序数组中插入一个新元素，同时保持数组有序，平均需要移动多少个元素？（）A.n/2B.nC.lognD.117、在一个具有n个元素的有序数组中，使用二分查找查找一个不存在的元素，最多比较次数约为？A.lognB.nC.n/2D.nlogn18、广义表((a,b),c,(d,(e,f)))的长度和深度分别为：A.3和2B.3和3C.4和2D.4和319、对于一个具有n个元素的归并排序，其时间复杂度为？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)20、对于一棵二叉树，先序遍历序列为ABC，中序遍历序列为BAC，则其后序遍历序列为？A.BCAB.CBAC.ACBD.ABC二、简答题（本大题共4个小题，共40分)1、（本题10分）分析在数据结构中，如何利用树状数组实现高效的区间查询和更新操作。2、（本题10分）详细说明如何在一个带权无向图中计算所有顶点对之间的最小权值路径的平均值。3、（本题10分）详细说明在一个具有n个顶点的有向图中，如何判断图中是否存在环，给出一种有效的算法并分析其时间复杂度。4、（本题10分）详细论述在一个具有n个顶点的无向图中，如何判断两个子图是否同构。三、设计题（本大题共2个小题，共