保山学院《数据结构》2022-2023学年期末试卷

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

2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个用链表实现的队列中，若要删除队尾元素，需要进行哪些操作？A.遍历链表找到队尾元素并删除B.将队尾元素的前一个元素设为队尾C.直接删除队尾元素D.以上都不对2、在一个具有n个元素的循环队列中，若队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，则队列中元素的个数为？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+13、对于一个具有n个元素的小根堆，若要删除堆顶元素并重新调整堆，以下关于操作的平均时间复杂度的描述，哪一项是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在一个具有n个元素的双向链表中，在p所指的节点之后插入一个新节点q，其操作步骤为（）。A.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B.q->next=p->next;q->prior=p;p->next=q;p->next->prior=q;C.p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D.p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;5、栈是一种特殊的线性表，其操作遵循后进先出原则。若一个栈的初始状态为空，现在依次将元素1、2、3、4、5入栈，然后再依次出栈，那么出栈的顺序是什么？（）A.12345B.54321C.32154D.215436、在一个具有n个顶点的无向图中，若采用邻接矩阵存储，则矩阵中非零元素的个数至少为？（）A.nB.n-1C.2(n-1)D.n(n-1)/27、在一个用链表实现的栈中，若要获取栈底元素的值，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、若一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，则其先序遍历序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB9、对于一个具有n个元素的双向循环链表，若要删除第i个节点（1<=i<=n），平均需要修改多少个指针？（）A.2B.3C.4D.510、对于一个具有n个元素的堆排序，其空间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、设有一个栈，元素进栈的次序为A、B、C、D、E，下列不可能的出栈序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE12、对于一个用链表表示的线性表，在表头插入一个新元素和在表尾插入一个新元素，哪个操作更复杂？A.表头插入B.表尾插入C.复杂度相同D.取决于链表长度13、在一个具有n个元素的顺序表中，若要在第i个元素之前插入一个新元素，平均需要移动多少个元素？（）A.n/2B.nC.iD.n-i14、在一个长度为n的有序线性表中进行二分查找，在最坏情况下，需要比较的次数为（）。A.O(n)B.O(n^2)C.O(log₂n)D.O(nlog₂n)15、在一个具有n个元素的双向循环链表中，删除一个节点后，需要修改几个指针？A.2B.3C.4D.516、若要对一个具有n个元素的有序链表进行二分查找，是否可行？（）A.可行B.不可行C.有时可行D.取决于链表长度17、一棵完全二叉树的第5层（根为第1层）有16个叶子节点，则该完全二叉树的节点总数最少为（）。A.47B.55C.63D.6418、在一个用邻接矩阵存储的图中，若要判断两个节点是否相邻，时间复杂度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)19、对于一个具有n个节点的二叉树，其先序遍历、中序遍历和后序遍历的结果都是唯一确定的，这个二叉树一定是（）A.满二叉树B.完全二叉树C.单支树D.以上都不是20、已知一棵二叉排序树的中序遍历序列为{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,25二、简答题（本大题共4个小题，共40分)1、（本题10分）对于一个具有n个顶点的无向图，如何使用广度优先搜索算法计算顶点的度？2、（本题10分）详细阐述桶排序在处理大规模数据时的优化策略。3、（本题10分）解释字符串匹配的常见算法，如暴力匹配算法、KMP算法，分析它们的时间复杂度和改进思路。4、（本题10分）对于一个用链表实现的栈，如何实现栈的逆序操作，要求空间复杂度为O(