郑州大学《数据结构综合实验》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页郑州大学

《数据结构综合实验》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、若一个栈的输入序列为1,2,3,4,5，不可能得到的输出序列是？（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,52、在一个循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，队列最大容量为MAXSIZE，若当前队列长度为n，则判断队满的条件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE3、在一个具有n个元素的大根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)4、对于一个具有n个顶点的强连通有向图，其邻接矩阵中至少有（）个非零元素。A.nB.n-1C.n(n-1)D.n(n-1)/25、在一个具有n个顶点和e条边的带权无向图中，使用Prim算法生成最小生成树。若采用邻接矩阵存储图，以下关于算法的空间复杂度的描述，哪一项是正确的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)6、在数据结构中，哈希表的负载因子对性能有很大影响。以下关于负载因子的描述，不正确的是（）A.负载因子越大，哈希冲突的可能性越大B.负载因子越小，存储空间利用率越高C.负载因子通常在0.5到1之间D.可以通过调整负载因子来优化哈希表性能7、在循环链表中，尾指针rear指向链表的尾节点，若要在链表中插入一个新的节点，使其成为新的尾节点，以下操作正确的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;8、排序算法的时间复杂度和空间复杂度是衡量算法性能的重要指标，以下关于它们的说法中，错误的是？（）A.时间复杂度是指算法执行所需的时间与问题规模之间的关系。B.空间复杂度是指算法执行所需的存储空间与问题规模之间的关系。C.不同的排序算法具有不同的时间复杂度和空间复杂度，选择合适的排序算法可以提高算法的性能。D.排序算法的时间复杂度和空间复杂度越低越好，不需要考虑其他因素。9、以下关于二叉排序树的描述，错误的是：A.左子树上所有结点的值均小于根结点的值B.右子树上所有结点的值均大于根结点的值C.中序遍历二叉排序树可得到一个有序序列D.二叉排序树的查找效率总是最高的10、对于一个具有n个顶点的无向图，若要判断其是否为连通图，以下哪种方法效率较高？（）A.深度优先搜索B.广度优先搜索C.枚举所有边D.以上方法效率相同11、在一个链式存储的栈中，若栈顶指针为top，要判断栈是否为空，应判断？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL12、对于一个具有n个顶点的无向图，若其所有顶点的度之和为20，则该图的边数为（）。A.5B.10C.15D.2013、对于一个具有n个元素的无序数组，使用选择排序进行排序，其交换次数最多为？A.n-1B.nC.n(n-1)/2D.n^214、在一个具有n个顶点的有向图中，若所有顶点的出度之和为m，入度之和为k，则m和k的关系是？（）A.m=kB.m>kC.m<kD.不确定15、以下关于图的遍历算法的描述，哪一项是正确的？（）A.深度优先遍历和广度优先遍历都能访问到图中的所有节点B.深度优先遍历适合用于求解最短路径问题C.广度优先遍历的空间复杂度低于深度优先遍历D.两种遍历算法的时间复杂度都与图的边数成正比16、在一个具有n个顶点的无向图中，若采用邻接矩阵存储，则矩阵中非零元素的个数至少为？（）A.nB.n-1C.2(n-1)D.n(n-1)/217、在一个用链表实现的栈中，若要获取栈底元素的值，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、在一个具有n个元素的有序数组中进行二分查找，其时间复杂度为？A.O(n)B.O(nlogn)C.O(logn)D.O(n^2)19、对于一个m行n列的二维数组，按行优先存储时，元素a[i][j]（0<=i<m,0<=j<n）的地址计算公式为：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i20、在一个具有n个元素的大顶堆中，若要将堆顶元素与最后一个元素交换，然后调整堆，其时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)二、简答题（本大题共4个小题，共40分)1、（本题10分）解释如何在一个字符串中查找所有不重复的字符组合。2、（本题10分）解释在一个具有n个节点的有向无环图中，如何计算每个节点的入度和出度。3、（本题10分）在一个单链表中，如何实现链表的反转操作？请给出具体的算法步骤和代码示例。4、