2024-2025-2期中卷¶

单项选择题，每题2分，总共100分。

（注：在答题纸上答题时，可以五道题目一组，例如1-5 XXXXX; 6-10 ΥΥΥΥΥ...）

以下关于红黑树性质的描述，错误的是：

A. 根节点必须是黑色

B. 每个叶子节点(NIL)是黑色

C. 红色节点的子节点必须是黑色

D. 从任意节点到其所有后代叶子节点的路径中，节点数量相同

向红黑树中插入一个新节点后，若父节点为红色，叔叔节点为黑色，且新节点是父节点的右子节点，此时应如何调整？

A. 对父节点左旋，然后重新着色

B. 对父节点右旋，然后重新着色

C. 对祖父节点左旋，然后重新着色

D. 对祖父节点右旋，然后重新着色

对以下红黑树进行左旋操作(以节点X为中心)，左旋后的结构是？

    X
/   \
A       Y
        / \
      B C

A. Y为根，X为Y的左子，B为Y的右子

B. Y为根，X为Y的右子，B为X的右子

C. X仍为根，Y为X的右子，B为Y的左子

D. Y为根，X为Y的左子，B为X的左子

给定序列 \([9,3,7,1,4,2,5]\)，使用最大堆建堆时，总共需要多少次元素交换？

A) 1

B) 2

C) 3

D) 4

对最大堆 \([10,8,9,3,5,7]\) 执行一次堆排序(交换堆顶和末尾，调整堆)，结果是什么？

A) \([9,8,7,3,5,10]\)

B) \([9,5,8,3,7,10]\)

C) \([9,8,7,3,5,10]\)

D) 以上均不对

对最大堆 \([7,4,6,1,3,2]\) 删除堆顶后调整，需要多少次比较？

A) 1

B) 2

C) 3

D) 4

向最大堆 \([10,5,8,3,2]\) 插入元素 9，调整后的堆是？

A) \([10,5,9,3,2,8]\)

B) \([10,9,8,3,2,5]\)

C) \([10,5,8,9,2,3]\)

D) 以上均不对

对序列 \([3,1,4,2,5]\) 进行堆排序，总共需要多少次交换(包括建堆和排序)？

A) 6

B) 7

C) 8

D) 以上均不对

给定数组 \(A=[-3,5,2,-1,0,5]\)，在计数排序中，计数数组C的长度是多少？

A. 5

B. 9

C. 8

D. 6

在计数排序的最后一步，将元素从计数数组放回原数组时，为什么要逆序遍历原数组？

A. 减少时间复杂度

B. 保持排序的稳定性

C. 节省空间

D. 处理负数
对数组 \(A = [9,4,6,2,7,3,5]\) 使用计数排序，计数数组中 \(C[3]\) 的值是多少？

A. 0

B. 1

C. 2

D. 3
当元素范围 \(k=O(n)\) 时，计数排序的时间复杂度是？

A. \(O(n)\)

B. \(O(n + k)\)

C. \(O(k)\)

D. 以上都对
对包含负数的数组使用计数排序时，必须进行以下哪一步？

A. 将所有元素取绝对值

B. 找到最小值并在计数时进行偏移

C. 使用稳定的排序算法

D. 将计数数组长度设为最大值的绝对值
给定数组 \([9, 7, 5, 11, 12, 2, 14, 3, 10, 6]\)，选择第一个元素为基准，第一次划分后的结果是什么？

A. \([6, 7, 5, 3, 2, 9, 14, 12, 10, 11]\)

B. \([5, 2, 3, 6, 7, 9, 11, 12, 14, 10]\)

C. \([3, 2, 5, 7, 6, 9, 14, 12, 10, 11]\)

D. 以上都不对
对已升序排列的数组 \([1,2,3,4,5]\) 使用快速排序(选第一个元素为基准)，比较次数是多少？

A. 5

B. 10

C. 15

D. 以上都不对
快速排序中，若每次划分均将数组分为长度相等的两部分，总比较次数的递推公式是？

A. \(T(n)=2T(n/2)+O(n)\)

B. \(T(n)=T(n-1)+O(n)\)

C. \(T(n)=T(n/2)+O(n)\)

D. \(T(n)=2T(n/2)+O(1)\)
给定数组 \([5,3,8,6,2]\)，执行插入排序时，第三趟排序结束后的数组状态是？

A. \([3,5,6,8,2]\)

B. \([3,5,8,6,2]\)

C. \([3,5,8,2,6]\)

D. 以上都不对
对长度为 5 的逆序数组 \([5,4,3,2,1]\) 进行插入排序，总比较次数是？

A. 10

B. 15

C. 5

D. 以上都不对
对已按升序排列的数组 \([1,2,3,4,5]\) 进行插入排序，总比较次数是？

A. 0

B. 4

C. 10

D. 以上都不对
当数组大部分有序时，插入排序的时间复杂度接近？

A. \(O(n^2)\)

B. \(O(n)\)

C. \(O(n \log n)\)

D. \(O(1)\)
在插入排序过程中，数组某中间状态为 \([2,5,7,3,9]\)，此时处理第四个元素 3 需要移动多少次？

A. 0

B. 1

C. 2

D. 以上都不对
设有一个大小为7的散列表，哈希函数为 \(h(k) = k \bmod 7\)，冲突解决采用线性探测法。现有键序列：8, 15, 22, 29 依次插入空表。插入完成后，键29的最终位置是？

A. 0

B. 1

C. 2

D. 以上都不对
散列表大小为11(质数)，哈希函数为 \(h(k)=k \bmod 11\)，冲突解决采用二次探测 \(h(k,i)=(h(k)+i^2) \bmod 11\)。插入键23后，再插入键34，此时需要多少次探测才能成功？

A. 1

B. 2

C. 3

D. 插入失败
散列表大小为10，哈希函数 \(h_1(k) = k \bmod 10\)，\(h_2(k) = 7 - (k \bmod 7)\)。插入键25时发生冲突，其最终位置是？

A. 5

B. 6

C. 7

D. 以上都不对
拟在大小为7的空散列表中依次插入14和21，哈希函数 \(h(k) = k \bmod 7\)。键14和21均哈希到位置0。若使用双重哈希法 \(h_2(k)=5-(k \bmod 5)\)，键21的最终位置是？

A. 0

B. 2

C. 4

D. 以上都不对
在二叉搜索树中删除节点15，该节点有两个子节点，已知该节点的右子树结构为：右子节点是18，18的左子节点是16，16的右子节点是17，替换15的后继节点是？

A. 16

B. 17

C. 18

D. 以上都不对
依次将元素20, 10, 30, 5, 15, 25, 35, 12插入空二叉搜索树，插入完成后节点12的父节点是？

A. 10

B. 15

C. 5

D. 以上都不对
以下哪个序列不可能是二叉搜索树的前序遍历结果？

A. 5, 3, 2, 4, 7, 6, 8

B. 8, 3, 1, 6, 4, 7, 10, 14, 13

C. 10, 5, 15, 6

D. 7, 5, 9, 8, 10, 12
在依次插入 20, 10, 30, 5, 15, 25, 35, 23, 28的二叉搜索树中，查找24需比较哪些节点？

A. 20, 30, 25, 23

B. 20, 30, 25, 28

C. 20, 30, 25, 23, 28

D. 以上都不对
有10个节点的二叉搜索树的最小可能高度是？

A. 3

B. 4

C. 2

D. 1
给定以下有根树的结构(根为A)，求叶子节点的数量。

树结构如下：A的子节点为B、C；B的子节点为D、E；C的子节点为F；E的子节点为G；F的子节点为H。

A) 3

B) 4

C) 5

D) 6
一棵完全二叉树有1001个节点，其最小高度是多少？(高度从0开始)

A) 9

B) 10

C) 11

D) 12
某二叉树的后序遍历序列为D, E, B, F, G, C, A，中序遍历为D, B, E, A, F, C, G，根节点的右子节点是：

A) B

B) C

C) F

D) 以上都不对
归并排序的空间复杂度为？

A. \(\Theta(1)\)

B. \(\Theta(n)\)

C. \(\Theta(\log n)\)

D. \(\Theta(n \log n)\)
归并排序是否稳定？

A. 是

B. 否

C. 取决于具体实现

D. 只有在元素全不同时稳定
给定序列 \([1,2,3,4,5,6,7]\)，用自底向上方法构建最大堆，总的比较次数是多少？

A. 6

B. 8

C. 10

D. 以上都不对
在最大堆 \([9,7,8,3,5,6,4]\) 中插入元素10，需要多少次交换操作？

A. 1

B. 2

C. 3

D. 4
初始最大堆为 \([9,7,8,3,5,6,4]\)，执行一次堆排序操作(取出堆顶后调整)，调整后的堆结构是？

A. \([8,7,6,3,5,4]\)

B. \([8,7,6,3,4,5]\)

C. \([8,7,5,3,6,4]\)

D. 以上都不对
最大堆 \([10,9,8,7,6,5,4]\) 中删除堆顶10后，调整过程中需要多少比较？

A. 2

B. 3

C. 4

D. 5
将两个大小分别为m和n的最大堆合并为一个最大堆的最优时间复杂度是？

A. \(\Theta(m+n)\)

B. \(\Theta(m \log n+n \log m)\)

C. \(\Theta(\log m+\log n)\)

D. \(\Theta(mn)\)
当输入数组每次划分都能精确分为大小相等的两部分时，总比较次数为？

A) \(O(n)\)

B) \(O(n \log n)\)

C) \(O(n^2)\)

D) \(O(n^3)\)
在快速排序算法中，对逆序数组 \([5,4,3,2,1]\)，使用最后一个元素为基准的比较次数为？

A) 5

B) 10

C) 15

D) 以上都不对
在一个长度为n的无序数组中，同时查找最大值和最小值，最少需要多少次比较？

A. \(2n-2\)

B. \(\lceil 3n/2 \rceil -2\)

C. \(n \log n\)

D. \(n^2\)
快速选择算法(QuickSelect)用于查找第k小的元素，其最坏时间复杂度是？

A. \(O(n)\)

B. \(O(n \log n)\)

C. \(O(n^2)\)

D. \(O(\log n)\)
假设用分治法在无序数组中查找中位数，每次将数组划分为大小为 \(\lfloor n/5 \rfloor\) 的组，递归求解中位数的中位数，递归式为 \(T(n)=T(n/5)+T(7n/10)+O(n)\)，其时间复杂度是？

A. \(O(n)\)

B. \(O(n \log n)\)

C. \(O(n^2)\)

D. \(O(\log n)\)
在数组 \([9,1,3,5,8,7,2,6,4]\) 中查找第4小的元素(从1开始计数)。若第一次选择主元为5，划分后下一步应处理哪个子数组？

A. \([1,3,2,4]\)

B. \([9,8,7,6]\)

C. \([1,3,5,2,4]\)

D. 以上都不对
已知某二叉树的前序遍历为 \([1,2,4,5,3,6,7]\)，中序遍历为 \([4,2,5,1,6,3,7]\)，则后序遍历为( )。

A. \([4, 5, 2, 6, 7, 3, 1]\)

B. \([4, 2, 5, 6, 3, 7, 1]\)

C. \([4, 5, 2, 6, 3, 7, 1]\)

D. 以上都不对
已知某二叉树的后序遍历为 \([8,4,5,2,9,6,7,3,1]\)，中序遍历为 \([8,4,2,5, 1, 9, 3, 6, 7]\)。则前序遍历为( )。

A. \([1, 2, 4, 8, 5, 3, 9, 6, 7]\)

B. \([1, 2, 4, 8, 5, 3, 6, 9, 7]\)

C. \([1, 2, 4, 8, 5, 3, 9, 7, 6]\)

D. 以上都不对
某二叉树的镜像树前序遍历为 \([3,7,9,6,2,5,4]\)，原树的后序遍历为( )。

A. \([4, 5, 2, 6, 9, 7, 3]\)

B. \([4, 5, 2, 6, 7, 9, 3]\)

C. \([4, 2, 5, 6, 9, 7, 3]\)

D. 以上都不对
某完全二叉树的层次遍历为 \([1,2,3,4,5,6,7]\)，其前序遍历为( )。

A. \([1, 2, 4, 5, 3, 6, 7]\)

B. \([1, 2, 4, 5, 3, 7, 6]\)

C. \([1, 2, 4, 3, 5, 6, 7]\)

D. \([1, 2, 3, 4, 5, 6, 7]\)