吉首大学《数据结构B》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页吉首大学《数据结构B》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个长度为n的顺序表中，删除第i个元素（1<=i<=n）时，需要移动的元素个数为：A.n-iB.i-1C.n-i+1D.i2、在一个具有n个元素的无序数组中，使用冒泡排序进行排序。以下关于冒泡排序的时间复杂度的描述，哪一项是正确的？A.最好情况为O(n)，最坏情况为O(n^2)B.最好情况和最坏情况均为O(n)C.最好情况为O(nlogn)，最坏情况为O(n^2)D.最好情况和最坏情况均为O(n^2)3、在一个具有n个节点的二叉排序树中，删除一个节点后，为了保持二叉排序树的性质，可能需要进行哪些操作？A.仅调整删除节点的子树B.从根节点开始重新调整C.调整整个树的结构D.以上都有可能4、一个具有n个顶点和e条边的无向图，采用邻接表存储，其空间复杂度为？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)5、在一个栈中，若入栈序列为1,2,3,4，且在入栈过程中可以出栈，则可能得到的出栈序列有多少种？（）A.14B.15C.16D.176、若一个图的广度优先遍历序列为ABCDEFG，则其深度优先遍历序列可能为？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG7、在一个具有n个元素的大顶堆中，若要将堆顶元素与最后一个元素交换，然后调整堆，其时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)8、在一个链队列中，假设队头指针为front，队尾指针为rear，删除队头元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL9、以下关于哈希表冲突解决方法的描述，哪一项是不正确的？（）A.链地址法会增加存储空间的开销B.开放定址法的查找效率一定高于链地址法C.再哈希法可以减少冲突的发生D.建立公共溢出区可以存储发生冲突的元素10、以下关于树的存储结构的描述，哪一项是不正确的？（）A.孩子兄弟表示法可以方便地实现树的遍历B.双亲表示法便于查找一个节点的双亲节点C.孩子链表表示法在处理多叉树时空间利用率较高D.以上存储结构在时间复杂度上没有明显差异11、栈是一种特殊的线性表，其操作遵循后进先出原则。若一个栈的初始状态为空，现在依次将元素1、2、3、4、5入栈，然后再依次出栈，那么出栈的顺序是什么？（）A.12345B.54321C.32154D.2154312、在二叉树中，判断两棵二叉树是否完全相同，以下方法不正确的是（）A.同时进行先序遍历，比较节点值B.同时进行中序遍历，比较节点值C.同时进行后序遍历，比较节点值D.比较两棵树的节点数量13、设有一个具有n个顶点的带权无向图，使用普里姆（Prim）算法求最小生成树。在算法执行过程中，需要选择一个顶点作为起始点。以下关于起始点选择对算法时间复杂度的影响，哪一个是恰当的？A.起始点的选择对时间复杂度没有影响B.选择不同的起始点可能导致时间复杂度不同C.选择顶点度最小的作为起始点可以降低时间复杂度D.选择顶点度最大的作为起始点可以降低时间复杂度14、对于一个具有n个元素的有序链表，若要在其中查找一个特定元素，其平均时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)15、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）。A.nB.n^2C.n(n-1)D.n(n+1)16、对于一个具有n个元素的有序双向链表，查找中间元素的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、对于一个用链表表示的线性表，在表头插入一个新元素和在表尾插入一个新元素，哪个操作更复杂？A.表头插入B.表尾插入C.复杂度相同D.取决于链表长度18、对于一个具有n个节点的红黑树，插入一个新节点后，调整树的结构以保持红黑树性质，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、图是一种复杂的数据结构，若要表示一个有向图，通常可以使用哪种存储结构？（）A.邻接矩阵B.邻接表C.十字链表D.以上均可20、设有一个具有n个顶点的有向图，采用邻接表存储。若要计算每个顶点的出度，以下关于操作的时间复杂度的描述，哪一项是恰当的？A.O(n)B.O(n+e)C.O(n^2)D.O(e)二、简答题（本大题共4个小题，共40分)1、（本题10分）论述在树的遍历优化中，如何利用线索化和缓存机制提高性能。2、（本题10分）对于一个用链表实现的双向循环队列，说明其入队、出队操作的实现方法，以及如何判断队列是否为空或已满。3、（本题10分）详细说明如何在一个具有n个顶点的图中，使用邻接矩阵存储结构判断两个顶点之间是否存在边，并分析其时间复杂度。4、（本题10分）在一个二叉树中，如何判断两棵二叉树是否相同