北京联合大学《数据结构A》2021-2022学年期末试卷

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

《数据结构A》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的循环队列中，若队头指针为front，队尾指针为rear，且rear<front，则队列中的元素个数为？A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n2、在一个具有n个顶点和e条边的无向图中，采用邻接表存储，其时间复杂度为？（）A.O(n+e)B.O(n²)C.O(e²)D.O(ne)3、若要对一组无序的整数进行排序，使其最终变为一个递增的有序序列，以下哪种排序算法在平均情况下性能最优？A.冒泡排序B.插入排序C.选择排序D.希尔排序4、对于一个具有n个顶点和e条边的无向连通图，利用Prim算法构造最小生成树时，其时间复杂度为：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)5、在一个用邻接矩阵存储的图中，若要判断两个节点是否相邻，时间复杂度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、对于一个具有n个顶点和e条边的有向完全图，其弧的条数为（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/27、以下关于串的描述，错误的是：A.串是一种特殊的线性表B.串的长度是指串中字符的个数C.空串和空格串是相同的概念D.串的存储方式有顺序存储和链式存储8、在一个具有n个顶点的带权无向图中，若采用普里姆（Prim）算法生成最小生成树，其时间复杂度为？（）A.O(n²)B.O(eloge)C.O(nlogn)D.O(e²)9、对于一个具有n个元素的有序链表，进行二分查找的时间复杂度为（）A.O(n)B.O(logn)C.O(nlogn)D.不能进行二分查找10、对于一个具有n个元素的堆，进行堆排序。以下关于堆排序的平均时间复杂度和空间复杂度的描述，哪一个是准确的？A.平均时间复杂度为O(nlogn)，空间复杂度为O(1)B.平均时间复杂度为O(n^2)，空间复杂度为O(n)C.平均时间复杂度为O(logn)，空间复杂度为O(logn)D.平均时间复杂度为O(n)，空间复杂度为O(n)11、在数据结构中，跳表的索引层数是根据数据量动态调整的，以下关于索引层数调整的描述，错误的是（）A.当数据量增加时，可能增加索引层数B.索引层数越多，查找效率越高C.调整索引层数的过程比较复杂D.索引层数的调整不会影响数据的存储结构12、在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的方法。以下关于它们的描述，错误的是（）A.DFS使用栈来保存未访问的节点B.BFS使用队列来保存未访问的节点C.DFS可能会陷入死循环D.BFS一定能找到最短路径13、在一个具有n个元素的顺序表中，若要在第i个元素（1<=i<=n）之前插入一个新元素，需要向后移动多少个元素？（）A.n-iB.iC.n-i+1D.n-i-114、在一个具有n个节点的二叉排序树中，删除一个节点后，为了保持二叉排序树的性质，可能需要进行哪些操作？A.仅调整删除节点的子树B.从根节点开始重新调整C.调整整个树的结构D.以上都有可能15、以下哪种数据结构常用于实现字符串的最长公共子序列问题？A.二维数组B.栈C.队列D.树16、设有一个栈，元素进栈的次序为A、B、C、D、E，下列不可能的出栈序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE17、以下哪种数据结构常用于实现优先级队列？A.链表B.队列C.栈D.堆18、以下哪种数据结构常用于实现图的深度优先遍历的栈？A.顺序栈B.链栈C.共享栈D.以上均可19、在一个长度为n的顺序表中，删除第i个元素（1<=i<=n）时，需要移动的元素个数为：A.n-iB.i-1C.n-i+1D.i20、在数据结构中，链表的每个节点通常包含数据域和指针域。若要在一个单向链表中删除一个指定节点，以下哪种操作是关键步骤？A.修改被删除节点的前一个节点的指针B.修改被删除节点的后一个节点的指针C.释放被删除节点的内存D.以上都是二、简答题（本大题共4个小题，共40分)1、（本题10分）在一个二叉搜索树中，如何查找值在给定范围内的所有元素？2、（本题10分）解释数据结构中栈的应用场景，如括号的嵌套深度问题、表达式的括号匹配高级问题等，并说明其原理。3、（本题10分）深入解释在具有n个元素的链表中，如何实现链表的奇偶节点分离，将奇数位置的节点和偶数位置的节点分别连接成两个链表。4、（本题10分）详细阐述在堆的实现细节中，如何处理堆的扩容和缩容