成都大学《数据结构与算法》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页成都大学《数据结构与算法》

2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、平衡二叉树是一种特殊的二叉搜索树，其目的是为了保证查找效率。以下哪种操作可能会导致平衡二叉树失去平衡？A.插入节点B.删除节点C.查找节点D.以上都可能2、在一个有向无环图中，进行拓扑排序的结果是唯一的吗？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不对3、在一个具有n个顶点和e条边的有向图中，采用邻接表存储，求顶点的入度的时间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)4、对于一个具有n个节点的二叉树，其先序遍历、中序遍历和后序遍历的结果都是唯一确定的，这个二叉树一定是（）A.满二叉树B.完全二叉树C.单支树D.以上都不是5、对于一个具有n个元素的堆，进行删除操作并调整堆的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、对于一个用数组实现的小根堆，进行删除堆顶元素操作后，需要重新调整堆以保持堆的性质。以下关于删除操作的时间复杂度的描述，哪一个是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、以下哪种排序算法在平均情况下的时间复杂度最优？A.冒泡排序B.快速排序C.插入排序D.选择排序8、对于一个用数组实现的循环队列，若队列已满，此时front=10，rear=20，队列的最大容量为50，那么下一个入队元素应该存储在哪个位置？A.21B.0C.30D.无法确定9、在一个具有n个节点的带权有向图中，若存在负权边，以下哪种最短路径算法可能不适用？A.迪杰斯特拉算法B.贝尔曼-福特算法C.弗洛伊德算法D.以上都适用10、若一个图的邻接矩阵对角线以下（不包括对角线）的元素全为0，则该图一定是：A.无向图B.有向图C.强连通图D.弱连通图11、在一个具有n个元素的链表中，访问第i个元素的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、设有一个栈，元素进栈的次序为A、B、C、D、E，下列不可能的出栈序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE13、在一个具有n个节点的图中，使用弗洛伊德算法求所有节点对之间的最短路径，其时间复杂度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)14、在一个具有n个元素的顺序存储的线性表中，删除第i个元素（1<=i<=n），平均需要移动多少个元素？（）A.n-iB.iC.(n-i)/2D.n/215、若一个队列的入队序列是1、2、3、4、5，在进行出队操作时，第一个出队的元素是：A.1B.2C.3D.416、在一个哈希表中，若采用线性探测法解决哈希冲突，当发生冲突时，新元素会存储在什么位置？A.冲突位置的下一个位置B.冲突位置C.随机位置D.以上都不对17、栈和队列的实现可以使用数组或链表，以下关于它们的实现方式的说法中，错误的是？（）A.用数组实现栈和队列时，需要考虑数组的大小和溢出问题。B.用链表实现栈和队列时，插入和删除操作的时间复杂度为O(1)。C.栈和队列的实现方式只影响它们的性能，不影响它们的功能。D.栈和队列可以同时使用数组和链表实现，以提高性能和灵活性。18、对于一个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+i19、对于一个具有n个元素的有序数组，若采用折半插入排序算法进行排序，其时间复杂度为？（）A.O(n)B.O(nlogn)C.O(n²)D.O(logn)20、设有一个具有n个节点的二叉搜索树，若要查找一个值大于给定值的最小节点，以下关于查找操作的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）在一个二叉搜索树中，如何查找值在给定范围内的所有元素？2、（本题10分）在一个具有n个元素的有序链表中，如何进行高效的插入操作，使得链表仍然保持有序，分析其时间复杂度。3、（本题10分）解释如何在一个字符串中查找所有不重复的字符组合。4、（本题10分）论述在字符串匹配的模