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

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页北华大学《数据结构》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在数据结构中，树的遍历可以采用递归和非递归方式。以下关于非递归中序遍历二叉树的说法，错误的是（）A.可以使用栈来辅助实现B.比递归方式更复杂C.时间复杂度与递归方式相同D.空间复杂度一定比递归方式低2、在一个具有n个元素的顺序存储的线性表中，删除第i个元素（1<=i<=n），需要移动多少个元素？（）A.n-iB.iC.n-i+1D.n-i-13、在一棵度为4的树中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个叶子节点，那么这棵树的总节点数是多少？A.82B.81C.79D.784、设有一个字符串S="helloworld"，要计算字符串S的长度（不包括结束符'\0'），以下函数正确的是？（）A.intlength(char*s){intcount=0;while(*s!='\0'){count++;s++;}returncount;}B.intlength(char*s){intcount=0;for(;*s!='\0';s++){count++;}returncount;}C.intlength(char*s){intcount=0;do{count++;s++;}while(*s!='\0');returncount;}D.intlength(char*s){intcount=0;while(s[count]!='\0'){count++;}returncount;}5、以下哪种数据结构适合频繁进行插入和删除操作，并且能够快速查找最大元素？（）A.数组B.链表C.栈D.最大堆6、在一个栈中，若入栈序列为1,2,3,4，且在入栈过程中可以出栈，则可能得到的出栈序列有多少种？（）A.14B.15C.16D.177、在数据结构中，使用并查集解决集合合并问题时，以下关于路径压缩的描述，错误的是（）A.可以提高查找效率B.不改变集合的关系C.增加了合并操作的复杂度D.使树的高度降低8、在一个B树中，每个节点的关键字数量最少为多少？（）A.1B.2C.⌈m/2⌉-1D.m-19、在数据结构中，对于线性表的顺序存储和链式存储，以下说法正确的是：顺序存储结构可以随机访问元素，但插入和删除操作效率较低；链式存储结构插入和删除操作方便，但不能随机访问。那么在频繁进行插入和删除操作的情况下，应优先选择哪种存储结构？（）A.顺序存储B.链式存储C.两者均可D.无法确定10、一棵完全二叉树的第6层（根为第1层）有8个叶子节点，则该完全二叉树的节点总数最多为（）。A.39B.56C.111D.11911、若要在一个已排序的数组中使用二分查找算法查找一个特定元素，以下关于时间复杂度的描述，哪一项是正确的？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)12、在一个具有n个节点的完全二叉树中，若节点编号从1开始，对于编号为i的节点，其双亲节点的编号是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不对13、对于一个具有n个元素的有序链表，若要在其中查找一个特定元素，其平均时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、在一个字符串中，要查找某个子串首次出现的位置，通常可以使用哪种算法？（）A.冒泡排序B.快速排序C.顺序查找D.二分查找15、已知一个具有n个顶点的无向图采用邻接矩阵存储，若要删除所有的边，时间复杂度为？（）A.O(n)B.O(n²)C.O(nlogn)D.O(e)16、在一个具有n个节点的带权有向图中，若存在负权边，以下哪种最短路径算法可能不适用？A.迪杰斯特拉算法B.贝尔曼-福特算法C.弗洛伊德算法D.以上都适用17、对于一个具有n个顶点和e条边的带权有向图，使用弗洛伊德（Floyd）算法求所有顶点对之间的最短路径。以下关于该算法的时间复杂度的描述，哪一个是恰当的？A.O(n)B.O(n^2)C.O(n^3)D.O(e^3)18、在一个哈希表中，若采用线性探测法解决哈希冲突，当发生冲突时，新元素会存储在什么位置？A.冲突位置的下一个位置B.冲突位置C.随机位置D.以上都不对19、队列也是一种常见的数据结构，遵循先进先出的原则。对于一个循环队列，以下说法不正确的是（）A.队头指针和队尾指针的移动需要考虑循环的情况B.当队头指针等于队尾指针时，队列为空C.可以通过牺牲一个存储单元来区分队列空和队列满的情况D.循环队列可以避免假溢出的问题20、图是一种复杂的数据结构，有邻接矩阵和邻接表两种存储方式。对于一个稀疏图，以下说法正确的是（）A.邻接矩阵比邻接表更节省存储空间B.邻接表更适合用于存储和遍历C.两种存储方式的时间复杂度相同D.稀疏图的边数很少，节点数很多二、简答题（本大题共4个小题，共40分)1、（本题10分）解释图的生成树是什么，以及如何找到一个图的最小生成树。2、（本题10分）对于一个用链表实现的栈，解释其入栈和出栈操作的基本原理，并说明在什么情况下可能会出现栈溢出或栈下溢的情况。3、（本题10分）论述在二叉树的遍历中，如何利用线索二叉树优化遍历效率。4、（本题10分）论述如何在一个带权有向图中计算源点到所