贺州学院《数据结构实验》2022-2023学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页贺州学院《数据结构实验》

2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、已知一棵二叉排序树的中序遍历序列为{10,12,15,18,20,25,30}，则其可能的前序遍历序列为？（）A.20,18,15,12,10,25,30B.10,12,15,18,20,25,30C.30,25,20,18,15,12,10D.10,12,18,15,20,30,252、在一个具有n个元素的数组中，进行顺序查找，若查找成功，平均比较次数约为？A.n/2B.nC.lognD.13、若一个队列的入队序列是1、2、3、4、5，在进行出队操作时，第一个出队的元素是：A.1B.2C.3D.44、在一个顺序存储的队列中，若要在队尾插入一个元素，需要移动元素的平均次数为（）A.0B.n/2C.nD.n-15、在一个顺序存储的栈中，若栈顶指针top为-1，则表示栈（）A.已满B.为空C.已损坏D.无法确定6、已知一个带权无向图的邻接矩阵表示，若要计算图中两个顶点之间的最短路径，可以使用的算法是？（）A.深度优先搜索B.广度优先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法7、以下哪种数据结构常用于实现表达式树？A.二叉树B.链表C.栈D.队列8、对于一棵二叉搜索树，进行中序遍历得到的序列是一个有序序列。若对其进行删除操作，以下关于时间复杂度的描述，哪一项是正确的？A.平均时间复杂度为O(logn)，最坏情况为O(n)B.时间复杂度始终为O(logn)C.平均时间复杂度为O(n)，最坏情况为O(nlogn)D.时间复杂度始终为O(n)9、以下哪种排序算法对大规模数据排序时，通常不被优先选择？A.冒泡排序B.插入排序C.快速排序D.归并排序10、若一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，则其先序遍历序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB11、设有一个广义表L=((a,b),c,(d,e))，其表头和表尾分别为？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)12、在一个具有n个顶点的有向无环图中，使用拓扑排序算法，其结果的唯一性如何？A.一定唯一B.可能不唯一C.取决于顶点的编号D.以上都不对13、栈和队列的应用场景非常广泛，以下关于它们的应用的说法中，错误的是？（）A.栈可以用于实现函数调用、表达式求值和括号匹配等。B.队列可以用于实现任务调度、消息队列和广度优先搜索等。C.栈和队列可以用于实现图的深度优先搜索和广度优先搜索。D.栈和队列只适用于计算机科学领域，在其他领域没有实际价值。14、在一个具有n个元素的有序数组中，使用插入排序进行排序，其最坏情况下的时间复杂度为？（）A.O(n)B.O(log₂n)C.O(n²)D.O(nlog₂n)15、以下关于红黑树的性质，错误的是：A.每个节点要么是红色，要么是黑色B.根节点是黑色的C.每个叶子节点（NIL节点）是黑色的D.红色节点的子节点一定是红色的16、在一个具有n个节点的带权无向图中，使用普里姆算法构造最小生成树，其时间复杂度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取决于图的结构17、在一个具有n个元素的最小堆中，插入一个新元素后，为了重新调整为最小堆，最坏情况下需要比较多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)18、在一个具有n个元素的顺序存储的循环队列中，队满的条件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front19、对于一个具有n个元素的循环队列，队头指针为front，队尾指针为rear，队列满的条件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front20、对于一个采用顺序存储的栈，若栈顶指针top等于-1时，表示：A.栈满B.栈空C.栈中只有一个元素D.栈中至少有一个元素二、简答题（本大题共4个小题，共40分)1、（本题10分）阐述如何在一个具有n个顶点的图中，使用邻接表存储结构获取顶点的度，并分析其时间复杂度。2、（本题10分）论述在字符串操作中，如何实现字符串的反转、拼接和比较等常见操作。3、（本题10分）分析在数据结构中，如何利用栈实现表达式的求值和转换。4、（本题10分）论述在最短路径算法的并行化实现中，如何划分任务和协调