北京联合大学《数据结构与算法（C描述）》2022-2023学年期末试卷

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

2022-2023学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个元素的无序数组，若要对其进行排序，以下哪种算法在最坏情况下时间复杂度最高？（）A.冒泡排序B.快速排序C.插入排序D.选择排序2、对于一个具有n个元素的堆，进行删除操作并调整堆的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、以下哪种数据结构常用于实现字符串的最长公共子序列问题？A.二维数组B.栈C.队列D.树4、在数据结构中，块状链表结合了链表和数组的优点，以下关于块状链表的特点，描述不正确的是（）A.适合频繁的插入和删除操作B.可以提高随机访问的效率C.每个块内部是有序的D.空间复杂度比普通链表低5、在数据结构中，伸展树（SplayTree）通过自调整保持较好的性能，以下关于伸展树的操作，不正确的是（）A.查找操作会将被查找的节点旋转到根节点B.插入操作可能会引起多次旋转C.伸展树的平均性能较好D.伸展树的空间复杂度较高6、在数据结构中，优先队列可以用堆来实现，以下关于堆调整的描述，错误的是（）A.插入元素时，从下往上调整堆B.删除堆顶元素时，从上往下调整堆C.调整堆的过程中，节点的值可能会交换D.调整堆的时间复杂度与堆的大小无关7、在数据结构中，使用队列来实现广度优先遍历图，以下关于遍历过程的描述，错误的是（）A.从起始节点开始入队B.队列为空时结束遍历C.访问节点时将其未访问的邻接节点入队D.节点不会被重复访问8、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法9、在数据结构中，哈弗曼编码是一种用于数据压缩的编码方式，以下关于哈弗曼编码的描述，错误的是（）A.出现频率高的字符编码较短B.编码是唯一的C.解码过程简单D.对所有数据都能达到很好的压缩效果10、设有一个具有n个顶点的带权无向图，使用普里姆（Prim）算法求最小生成树。在算法执行过程中，需要选择一个顶点作为起始点。以下关于起始点选择对算法时间复杂度的影响，哪一个是恰当的？A.起始点的选择对时间复杂度没有影响B.选择不同的起始点可能导致时间复杂度不同C.选择顶点度最小的作为起始点可以降低时间复杂度D.选择顶点度最大的作为起始点可以降低时间复杂度11、在一个具有n个元素的小根堆中，删除堆顶元素后，将最后一个元素放到堆顶，然后进行调整，其时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)12、设有一个字符串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;}13、在一个顺序存储的栈中，若栈顶指针top为-1，则表示栈（）A.已满B.为空C.已损坏D.无法确定14、对于一个具有n个顶点和e条边的无向图，使用深度优先搜索算法进行遍历。以下关于算法中使用的标记数组的空间复杂度的描述，哪一项是正确的？A.O(1)B.O(n)C.O(e)D.O(n^2)15、对于一个用链表表示的线性表，在表头插入一个新元素和在表尾插入一个新元素，哪个操作更复杂？A.表头插入B.表尾插入C.复杂度相同D.取决于链表长度16、在一个具有n个元素的单链表中，若要在第i个位置（1<=i<=n）插入一个新元素，平均需要遍历多少个节点？（）A.i-1B.iC.(i-1)/2D.i/217、对于一个具有n个元素的双向循环链表，若要删除第i个节点（1<=i<=n），平均需要修改多少个指针？（）A.2B.3C.4D.518、数据结构是计算机科学中重要的基础课程，它研究数据的组织、存储和管理方式。以下关于数据结构的说法中，错误的是？（）A.数据结构可以分为线性结构和非线性结构两大类。B.线性结构包括数组、链表、栈和队列等。C.非线性结构包括树、图和集合等。D.数据结构只与编程语言有关，与实际应用场景无关。19、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则其后序遍历序列为：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD20、在一个具有n个顶点的连通图中，生成树的边数一定为？（）A.n-1B.nC.n+1D.2n二、简答题（本大题共4个小题，共40分)1、（本题10分）在一个二叉搜索树中，如何实现删除操作并保证树的性质不变？2、（本题10分）阐述后缀树在信息检索中的应用和优化策略。3、（本题10分）详细说明如何在一个具有n个元素的有序数组中，进行二分查找的非递归实现，并分析其时间复杂度和空间复杂度。4、（本题10分）论