西华师范大学《数据结构》2021-2022学年期末试卷

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

2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个节点的完全二叉树，若底层从左到右填充，则第i个节点的左孩子节点的编号为？A.2iB.2i+1C.i*2D.i*2+12、以下哪种排序算法是稳定的排序算法？A.快速排序B.选择排序C.冒泡排序D.希尔排序3、在一个m行n列的二维数组中，元素存储的地址计算公式为LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d为每个元素所占的存储单元数。若按行优先存储，则a23的地址为？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d4、在一个具有n个元素的无序数组中，使用选择排序进行排序，其空间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(n²)5、在一个平衡二叉搜索树中，插入一个新节点后，可能需要进行的调整操作次数最多为（）A.1B.lognC.nD.nlogn6、对于一个具有n个节点的二叉树，进行先序遍历和中序遍历，得到的序列相同，则该二叉树的形状为？A.只有一个根节点B.所有节点只有左子树C.所有节点只有右子树D.是一棵满二叉树7、设有一个具有n个元素的最大堆，若要获取堆中的最大元素，以下关于操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、设有一个栈，元素进栈的次序为A、B、C、D、E，下列不可能的出栈序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE9、对于一个具有n个元素的堆，进行堆排序。以下关于堆排序的平均时间复杂度和空间复杂度的描述，哪一个是准确的？A.平均时间复杂度为O(nlogn)，空间复杂度为O(1)B.平均时间复杂度为O(n^2)，空间复杂度为O(n)C.平均时间复杂度为O(logn)，空间复杂度为O(logn)D.平均时间复杂度为O(n)，空间复杂度为O(n)10、深度为5的满二叉树的结点数为：A.16B.31C.32D.1511、对于一个具有n个元素的栈，若要实现将栈中元素逆置，需要借助的辅助数据结构为？（）A.队列B.栈C.链表D.数组12、在数据结构中，桶排序是一种外部排序算法，以下关于桶排序的描述，错误的是（）A.要求输入数据具有特定的分布B.时间复杂度为O(n)C.空间复杂度较高D.适用于大规模数据排序13、在一个具有n个元素的大顶堆中，若要将堆顶元素与最后一个元素交换，然后调整堆，其时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、在一个具有n个顶点的有向图中，若存在顶点的入度为0，则该图可能是：A.强连通图B.弱连通图C.非连通图D.以上都不对15、二叉树是一种重要的数据结构。对于一个满二叉树，若其高度为h，则节点总数为多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-116、在一个具有n个顶点和e条边的无向图中，使用邻接矩阵存储，进行深度优先遍历，其时间复杂度为？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)17、对于一个具有n个节点的完全二叉树，若按照层次遍历的顺序将节点编号为1到n，已知编号为i的节点有左孩子，则其左孩子的编号为？A.2iB.2i+1C.i*2D.i/218、在一个具有n个元素的顺序表中，删除第i个元素（1<=i<=n），平均需要移动的元素个数约为？A.n/2B.n-iC.iD.n-i+119、在一个具有n个元素的有序数组中进行二分查找，其时间复杂度为？A.O(n)B.O(nlogn)C.O(logn)D.O(n^2)20、若要在一个具有n个元素的有序数组中插入一个新元素，同时保持数组有序，平均需要移动多少个元素？（）A.n/2B.nC.lognD.1二、简答题（本大题共4个小题，共40分)1、（本题10分）解释什么是拓扑排序，并说明其在项目管理等领域的应用。2、（本题10分）解释并举例说明在一个具有n个元素的顺序表中，如何使用排序算法解决区间最值问题。3、（本题10分）详细说明如何在一个图中判断两个顶点是否在同一个连通分量中。4、（本题10分）链表的遍历和数组的遍历有哪些不同之处？各自的优缺点是什么？三、设计题（本大题共