南京工程学院《数据结构与算法》2021-2022学年期末试卷

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

2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、图的存储方式和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.图的邻接矩阵可以用于表示网络中的连接关系，如社交网络、交通网络等。B.图的邻接表可以用于表示稀疏图，如地图、电路图等。C.图的遍历方式可以用于解决路径规划、网络流问题和最小生成树问题等。D.图的存储方式和遍历方式只适用于理论研究，在实际应用中没有实际价值。2、若要在一个具有n个元素的有序链表中插入一个新元素，使其仍然有序，平均时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)3、以下关于并查集的描述，错误的是：A.并查集可以用于判断两个元素是否在同一个集合中B.并查集的查找操作时间复杂度较低C.并查集的合并操作时间复杂度较高D.并查集通常采用树形结构存储4、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则该二叉树的后序遍历序列为（）。A.CBEFDGAB.CEBFDGAC.CBEFGDAD.CEBFGDA5、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占一个存储单元，则a85的地址为？（）A.33B.32C.18D.406、对于一个具有n个元素的有序链表，进行折半查找，其时间复杂度为？A.O(logn)B.O(nlogn)C.O(n)D.不能进行折半查找7、若要从一个具有n个元素的有序单链表中删除所有值重复的元素，使得链表中每个元素的值都不同，最优的算法时间复杂度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)8、在一个具有n个元素的大根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)9、对于一个具有n个节点的无向完全图，其边的数量为多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/210、设有一个具有n个节点的二叉树，若每个节点都有左右子树，则该二叉树的叶子节点数量与度为2的节点数量之间存在特定关系。以下关于这种关系的描述，哪一项是正确的？A.叶子节点数量等于度为2的节点数量B.叶子节点数量比度为2的节点数量多1C.叶子节点数量比度为2的节点数量少1D.两者之间没有固定关系11、队列也是一种常见的数据结构，遵循先进先出的原则。对于一个循环队列，以下说法不正确的是（）A.队头指针和队尾指针的移动需要考虑循环的情况B.当队头指针等于队尾指针时，队列为空C.可以通过牺牲一个存储单元来区分队列空和队列满的情况D.循环队列可以避免假溢出的问题12、设有一个长度为n的顺序表，要在第i个元素之前插入一个新元素，并且移动元素的平均次数为n/2，则插入算法的平均时间复杂度为？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)13、已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则其先序遍历序列为（）。A.CEABDB.CEDBAC.CABDED.CEDAB14、对于一个具有n个节点的二叉排序树，删除一个节点后，重新调整为二叉排序树，其时间复杂度最坏情况下为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、已知一个栈的进栈序列为1,2,3,4，出栈序列为3,2,4,1，则栈的容量至少为（）。A.2B.3C.4D.516、对于一个采用顺序存储的栈，若栈顶指针top等于-1时，表示：A.栈满B.栈空C.栈中只有一个元素D.栈中至少有一个元素17、已知一个具有n个顶点的无向图采用邻接矩阵存储，若要删除所有的边，时间复杂度为？（）A.O(n)B.O(n²)C.O(nlogn)D.O(e)18、在一个具有n个节点的带权无向图中，使用普里姆算法构造最小生成树，其时间复杂度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取决于图的结构19、在数据结构中，优先队列可以用堆来实现，以下关于堆调整的描述，错误的是（）A.插入元素时，从下往上调整堆B.删除堆顶元素时，从上往下调整堆C.调整堆的过程中，节点的值可能会交换D.调整堆的时间复杂度与堆的大小无关20、在一个链式存储的栈中，进行入栈和出栈操作时，以下关于时间复杂度的描述，哪一个是准确的？A.入栈和出栈的时间复杂度均为O(1)B.入栈的时间复杂度为O(n)，出栈的时间复杂度为O(1)C.入栈的时间复杂度为O(1)，出栈的时间复杂度为O(n)D.入栈和出栈的时间复杂度均为O(n)二、简答题（本大题共4个小题，共40分)1、（本题10分）对于一个用哈希表存储的整数集合，解释如何实现集合的交集、并集和差集运算，给出算法思路和时间复杂度分析。2、（本题10分）论述伸展树在数据分布不均匀情况下的性能表现和应对措施。3、（本题10分）详细说明最短路径问题的定义，以及Dijkstra算法和Floyd算法在解决不同类型最短路径问题中的应用。4、（本题10分）解释在平衡二叉搜索树中，删除操作后如何恢复树的平衡且不破坏中序遍历的性质。三、