数组

如果选择Θ(1)，请考虑示例：

• {1, 2, 2, 2, 4, 4}
• {1, 1, 2, 2, 2, 2, 3, 3}

判断已排序（升序）数组中是否存在出现次数超过 n/2 次的整数的最佳方法是使用二分查找。具体步骤如下：

1. 通过分治技术在 O(log(n)) 时间内找到目标元素的首次出现位置 i
2. 通过分治技术在 O(log(n)) 时间内找到目标元素的末次出现位置 j
3. 计算该元素的出现次数：count = j - i + 1

时间复杂度分析：

O(log n) [首次查找]
+ O(log n) [末次查找]
+ 1 [计数计算]
= O(log n)

• 无序数组：插入操作的时间复杂度为 O(1)，因为可以在末尾直接插入。
• 最小堆：插入操作需要 O(log n) 时间（参考二叉堆操作）。
• 有序数组：插入操作可能需要移动所有元素，最坏情况下为 O(n)。
• 有序双向链表：需要 O(n) 时间来找到插入位置。

由于插入操作的数量在渐近意义上最高（N 次），因此优先选择插入效率最高的 无序数组。尽管其他操作如删除和减键可能需要额外开销，但题目明确提供了直接指针，使得这些操作可在 O(1) 时间内完成，从而整体时间复杂度由插入操作主导。

解释：

• 可以采用快速排序的分区思想进行分组
• 通过单次遍历即可完成符号分组操作
• 时间复杂度与数组长度呈线性关系
• 最终时间复杂度为 O(N)

• 数组中共有 $ \frac{n(n-1)}{2} $ 个满足 $ i < j $ 的数对组合
• 对于任意一对 $ (a_i, a_j) $，由于元素互异且随机排列，出现逆序对的概率为 $ \frac{1}{2} $
• 根据期望的线性性质，总期望为： $$ \frac{1}{2} \times \frac{n(n-1)}{2} = \frac{n(n-1)}{4} $$

• 计算行偏移：

  $$ \text{行偏移} = 11 \times 10 \times 4 = 440 $$

  因此，A[11][0] 的地址为：

  $$ 100 + 440 = 540 $$

• 计算列偏移： $$ \text{列偏移} = 5 \times 4 = 20 $$ 最终地址为： $$ 540 + 20 = 560 $$

解析：
选项 A 正确地声明了一个整数数组 geeks，其大小为 20。

• int 指定了数组元素的数据类型为整型。
• geeks 是数组的名称。
• [20] 表示数组可存储 20 个元素。

其他选项均不符合 C/C++ 的数组声明语法规范。

解析：

1. 行优先存储原理
   三维数组 int A[x][y][z] 在内存中按行优先顺序存储，其访问顺序遵循：

   • 第一维（x）变化最慢
   • 第二维（y）次之
   • 第三维（z）变化最快

2. 地址计算步骤

   • 定位到第 p 行
     需跨越前 p 行的所有元素： $$ \text{元素数量} = p \times (y \times z) $$
   • 定位到第 q 列
     需跨越当前行中前 q 列的所有元素： $$ \text{元素数量} = q \times z $$
   • 定位到第 r 个元素
     直接取当前列的第 r 个元素： $$ \text{元素数量} = r $$

3. 总偏移量与地址公式

   • 总元素偏移量： $$ \text{Total Offset} = y \cdot z \cdot p + z \cdot q + r $$
   • 最终地址： $$ \text{Address} = &A[0][0][0] + w \cdot (\text{Total Offset}) $$ 即： $$ &A[0][0][0] + w \cdot (y \cdot z \cdot p + z \cdot q + r) $$

4. 结论
   选项 B 的表达式完全匹配上述推导结果，因此 选项 B 正确。

• 关键分析：观察第一个循环中的三步操作：
  1. Temp = A[i][j] + C
  2. A[i][j] = A[j][i]
  3. A[j][i] = Temp - C
• 执行效果：当 i ≠ j 时，该操作实现了 A[i][j] 与 A[j][i] 的值交换（通过中间变量 Temp）。
• 双重交换机制：由于循环遍历所有 (i, j) 组合，每个非对角线元素会被交换两次（一次作为 (i,j)，另一次作为 (j,i)），从而恢复原始值。
• 结论：矩阵整体未发生任何变化，最终输出仍为原矩阵 A。

解析

• 题目要求统计高于 50 的成绩的频率
• 成绩范围是 [0..100]，因此高于 50 的有效成绩范围是 51 到 100（共 50 个不同值）
• 每个值对应的频率可以用一个长度为 50 的数组存储
• 其他选项要么空间浪费（如 100/500/550），要么不符合实际需求
• 因此，一个包含 50 个数字的数组是最优解

• 数组退化规则：在 C/C++ 中，数组作为函数参数传递时会自动退化为指向其首元素的指针
• 参数匹配：char arr[] 在函数参数中等价于 char* 类型
• 正确调用：直接使用 arr 即可（等价于 &arr[0]），与函数参数类型 char* 完全匹配
• 错误选项分析：
  • fun(&arr) 实际传递的是 char(*)[9] 类型（指向数组的指针）
  • _arr 不是合法标识符
  • None 选项不符合实际需求

• 解析：
  在函数 fun 中，通过双重循环遍历矩阵的上三角区域（即 $i < j$ 的位置）。
  • 对于每个元素 $A[i][j]$，将其与 $A[j][i]$ 交换。
  • 这一操作实际上将矩阵的行和列互换位置，最终得到的是矩阵 $A$ 的转置矩阵。
    因此，正确答案是 (C)。

假设我们声明一个数组：

arr[5] = {1, 2, 3};

此时数组的大小被声明为 5，但实际仅初始化了 3 个元素。这种预分配空间与实际使用量的差异会直接导致内存资源的浪费。因此选项（D）描述的情况是数组的典型局限性。

在上述程序中，我们只是将数组元素循环右移 3 位。循环从 i=3 运行到 9，在循环内部：

• a[3%6] = a[3] = 'D'
• a[4%6] = a[4] = 'E'
• a[5%6] = a[5] = 'F'
• a[6%6] = a[0] = 'A'
• a[7%6] = a[1] = 'B'
• a[8%6] = a[2] = 'C'

因此选项 (B) 正确。

解析：

1. 第一个空白处（while 循环条件）
   p <= d
   因为初始值 p = 1，需要循环执行 d 次（每次左移一个元素），所以条件应为 p <= d。

2. 第二个空白处（for 循环条件）
   i < n - 1
   循环需将前 n-1 个元素依次前移，因此终止条件为 i < n - 1。

3. 第三个空白处（更新最后一个元素）
   arr[n - 1] = last;
   将原首元素 last 赋值给数组末尾，完成单次左移操作。

综上，选项 (A) 正确。