北京城市学院《数据结构》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页北京城市学院

《数据结构》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一棵二叉搜索树，进行中序遍历得到的序列是一个有序序列。若对其进行删除操作，以下关于时间复杂度的描述，哪一项是正确的？A.平均时间复杂度为O(logn)，最坏情况为O(n)B.时间复杂度始终为O(logn)C.平均时间复杂度为O(n)，最坏情况为O(nlogn)D.时间复杂度始终为O(n)2、在一个用顺序存储结构实现的栈中，若栈顶指针top指向栈顶元素的上一个位置，当栈为空时，top的值为？A.-1B.0C.1D.n-1（其中n为栈的最大容量）3、以下关于红黑树的性质，错误的是：A.每个节点要么是红色，要么是黑色B.根节点是黑色的C.每个叶子节点（NIL节点）是黑色的D.红色节点的子节点一定是红色的4、对于一个用链表表示的线性表，在表头插入一个新元素和在表尾插入一个新元素，哪个操作更复杂？A.表头插入B.表尾插入C.复杂度相同D.取决于链表长度5、在一个链式存储的线性表中，若要删除第i个元素（1<=i<=n），需要找到其前驱节点的时间复杂度为？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、若要对一棵二叉排序树进行中序遍历，得到的序列是一个有序序列，这是因为二叉排序树的定义具有什么特性？（）A.左子树的值小于根节点，右子树的值大于根节点B.左子树和右子树的深度相同C.每个节点的值都不同D.以上都不是7、在一个链式存储的栈中，若栈顶指针为top，要判断栈是否为空，应判断？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL8、在一个具有n个顶点和e条边的带权无向图中，使用Prim算法生成最小生成树。若采用邻接矩阵存储图，以下关于算法的空间复杂度的描述，哪一项是正确的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)9、在一个用链表实现的队列中，若要删除队头元素并返回其值，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一个字符串匹配算法中，BM算法相对于朴素的字符串匹配算法，其优势在于？（）A.平均性能更好B.代码更简洁C.空间复杂度更低D.适用于短字符串匹配11、在一棵平衡二叉树中，插入一个新结点后，可能需要进行的调整操作是：A.左旋B.右旋C.左旋和右旋D.不需要调整12、以下哪种数据结构常用于实现字符串的最长公共子序列问题？A.二维数组B.栈C.队列D.树13、以下哪种数据结构在处理频繁的插入和删除操作时，不需要移动大量元素？（）A.数组B.链表C.栈D.队列14、在一个具有n个节点的完全二叉树中，若底层从左到右第x个节点为叶子节点，则x的取值范围是（）A.[2^(h-1),2^h-1]B.[2^(h-2),2^(h-1)-1]C.[2^(h-1)-1,2^h-2]D.[2^(h-2)-1,2^(h-1)-1]15、在一个具有n个节点的完全二叉树中，若节点编号从1开始，对于编号为i的节点，其双亲节点的编号是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不对16、对于一个具有n个节点的线索二叉树，若n个节点中有m个空指针域，则线索的数量为？A.mB.m/2C.n+1D.n-117、对于单链表，若要访问链表中的第i个元素，必须从链表的头指针开始依次遍历，平均时间复杂度为O(n)。那么如果要在链表的末尾添加一个新元素，时间复杂度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)18、在一个顺序存储的栈中，若栈顶指针top为-1，则表示栈（）A.已满B.为空C.已损坏D.无法确定19、对于一个具有n个顶点和e条边的带权无向图，使用克鲁斯卡尔算法构造最小生成树时，每次选择的边是？（）A.权值最小的边B.连接两个连通分量的权值最小的边C.任意一条边D.以上都不对20、在一棵二叉搜索树中，删除一个只有左子树的节点，其右子树的节点需要（）A.替换被删除节点B.保持不动C.全部删除D.移动到左子树二、简答题（本大题共4个小题，共40分)1、（本题10分）比较计数排序和冒泡排序在处理大量重复数据时的效率。2、（本题10分）详细说明如何使用基数排序对整数或字符串进行排序，分析其原理和时间复杂度。3、（本题10分）论述如何使用堆优化迪杰斯特拉算法求解单源最短路径问题的性能。4、（本题10分）详细说明如何在一个无向图中判断是否为二部图，给出算法步骤和实现代码，并分析其时间复杂度。三、设