宝鸡文理学院《数据结构》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页宝鸡文理学院

《数据结构》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个节点的完全二叉树中，若底层从左到右依次编号，节点i的左孩子节点编号是多少（假设根节点编号为1）？A.2iB.2i+1C.i*2D.以上都不对2、在一个具有n个顶点的无向图中，若要判断两个顶点之间是否存在路径，使用哪种算法较为合适？A.迪杰斯特拉算法B.弗洛伊德算法C.深度优先遍历或广度优先遍历D.拓扑排序3、对于一个具有n个元素的无序数组，使用快速排序算法进行排序，在平均情况下的空间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、对于一个具有n个元素的选择排序，在最坏情况下，需要进行多少次交换操作？（）A.n-1B.nC.n(n-1)/2D.05、以下关于哈夫曼树的描述，正确的是：A.哈夫曼树一定是完全二叉树B.哈夫曼树中不存在度为1的节点C.哈夫曼树的带权路径长度是唯一的D.哈夫曼树的构建过程不需要进行节点的比较和交换6、在一个具有n个元素的小根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)7、对于一个具有n个节点的二叉树，其高度的最小值和最大值分别是多少？（）A.log₂n,n-1B.1,nC.log₂n,nD.1,n-18、对于一个具有n个节点的完全二叉树，若底层从左到右填充，则第i个节点的左孩子节点的编号为？A.2iB.2i+1C.i*2D.i*2+19、一个具有n个顶点和e条边的无向图，采用邻接表存储，其空间复杂度为？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)10、以下关于图的存储结构的描述，错误的是：A.邻接矩阵适合存储稠密图B.邻接表适合存储稀疏图C.十字链表是邻接表和逆邻接表的结合D.邻接多重表只适合无向图11、在一个具有n个元素的有序数组中，采用插入排序进行排序，在最好情况下，需要比较的次数为（）。A.n-1B.nC.0D.n(n-1)/212、对于一个具有n个元素的双向链表，若要在第i个位置（1<=i<=n）之前插入一个新节点，平均需要修改多少个指针？（）A.1B.2C.3D.413、以下关于拓扑排序的描述，正确的是：A.拓扑排序的结果是唯一的B.一个有环的图也可以进行拓扑排序C.拓扑排序可以用于判断一个图是否有环D.拓扑排序只能用于有向图14、在一个平衡二叉树中，插入一个新节点后可能会导致树的不平衡，此时需要进行调整。以下哪种调整操作可能会被执行？（）A.左旋B.右旋C.先左旋后右旋D.以上都有可能15、在图的存储结构中，十字链表主要用于存储有向图，以下关于十字链表的特点，描述不正确的是（）A.既能方便地访问出边，也能方便地访问入边B.存储空间比邻接表节省C.对于删除边的操作比较复杂D.不适合用于稀疏有向图16、在一个具有n个元素的无序数组中，使用冒泡排序进行排序。以下关于冒泡排序的时间复杂度的描述，哪一项是正确的？A.最好情况为O(n)，最坏情况为O(n^2)B.最好情况和最坏情况均为O(n)C.最好情况为O(nlogn)，最坏情况为O(n^2)D.最好情况和最坏情况均为O(n^2)17、在一个m行n列的二维数组中，按列优先存储时，元素aij的存储地址为？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d18、在一个具有n个元素的数组中，进行顺序查找，若查找成功，平均比较次数约为？A.n/2B.nC.lognD.119、在一个具有n个元素的大顶堆中，插入一个新元素后，需要进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)20、对于一个具有n个元素的堆，若要将其所有元素从小到大排序，最好的方法是？A.每次删除堆顶元素并调整B.直接使用快速排序C.先构建大顶堆再调整D.以上方法效率相同二、简答题（本大题共4个小题，共40分)1、（本题10分）论述AVL树的删除操作中可能出现的四种情况及相应的调整策略。2、（本题10分）解释数据结构中栈的应用场景，如表达式的前缀、中缀、后缀转换等，并说明其原理。3、（本题10分）详细阐述如何在一个带权有向图中计算两个顶点之间路径经过的顶点数量。4、（本题10分）请说明二叉搜索树的定义和性质，阐述其