D
将 (2, 6, 10, 17)(2,6,10,17)带入四个选项，当我们选取“\lfloor\sqrt x\rfloor \bmod 11⌊
x
​
⌋mod11”做哈希函数时，(2, 6, 10, 17)(2,6,10,17) 散列后的值分别为 (1, 2, 3, 4)(1,2,3,4)，不会产生冲突。

D
IPv4 协议使用 3232 位地址，IPv6 协议则使用 128128 位地址，可以有效地解决地址资源枯竭的问题。

C
“(A \lor B) \land \lnot A(A∨B)∧¬A”选项，当 AA 为真的时候，此式恒为假，当 AA 为假的时候，值取决于 BB。

“(A \lor B) \land \lnot B(A∨B)∧¬B”选项，当 BB 为真的时候，此式恒为假，当 BB 为假的时候，值取决于 AA。

“(A \land B) \lor ( \lnot A \land B)(A∧B)∨(¬A∧B)”选项，当 BB 为真的时候，此此式恒为真，当 BB 为假的时候，此式子恒为假，结果与 AA 的真假无关。

“(A \lor B) \land \lnot A \land B(A∨B)∧¬A∧B”选项，当 BB 为真的时候，此式结果为 \lnot A¬A，于 AA 有关，当 BB 为假的时候，此式恒为假。

D
根据 IEEE 的规范，浮点数由符号位、尾码和阶码组成，在将 6464 位浮点数强制转换成 32位浮点数时，符号位保留不点，尾码和阶码则可能由于精度问题改变它们的值。因此大于、小于、等于原数的情况都有可能出现。

B
CCF NOIP 复赛全国统一评测时使用的系统软件是 NOI Linux
7 个同学围坐一圈，要选 22 个不相邻的作为代表，有____种不同的选法
14
选择第一个同学共有 77 种选项，第二个同学由于不能相邻，只剩下 44 个可选，同时每对同学会被重复计算两次，因此一共有 \dfrac{7\times 4}2=14
2
7×4
​
=14 种不同的选法。
#include [HTML_REMOVED]
using namespace std;
int main(){
const int SIZE = 100;
int n, f, i, left, right, middle, a[SIZE];
cin>>n>>f;
for (i = 1; i <= n; i++)
cin>>a[i];
left = 1;
right = n;
do {
middle = (left + right) / 2;
if (f <= a[middle])
right = middle;
else
left = middle + 1;
} while (left < right);
cout<<left<<endl;
return 0;
}
输入：

1
12 17
2
2 4 6 9 11 15 17 18 19 20 21 25
7

include [HTML_REMOVED]

using namespace std;
int main(){
const int SIZE = 100;
int height[SIZE], num[SIZE], n, ans;
cin>>n;
for (int i = 0; i < n; i) {
cin>>height[i];
num[i] = 1;
for (int j = 0; j < i; j) {
if ((height[j] < height[i]) && (num[j] >= num[i]))
num[i] = num[j]+1;
}
}
ans = 0;
for (int i = 0; i < n; i++) {
if (num[i] > ans) ans = num[i];
}
cout<<ans<<endl;
}
输入：

1
6
2
2 5 3 11 12 4
4
（序列重排）全局数组变量 aa 定义如下：

const int SIZE = 100;int a[SIZE], n;

它记录着一个长度为 nn 的序列 a[1], a[2], …, a[n]a[1],a[2],…,a[n]。

现在需要一个函数，以整数 pp(1 \le p \le n)(1≤p≤n) 为参数，实现如下功能：将序列 aa 的前 pp 个数与后 n - pn−p 个数对调，且不改变这 pp 个数(或 n - pn−p 个数)之间的相对位置。例如，长度为 55 的序列 1, 2, 3, 4, 51,2,3,4,5，当 p = 2p=2 时重排结果为 3, 4, 5, 1, 23,4,5,1,2。

有一种朴素的算法可以实现这一需求，其时间复杂度为 \mathcal{O}(n)O(n)、空间复杂度为 \mathcal{O}(n)O(n)：

1
void swap1(int p){
2
int i, j, b[SIZE];
3
for (i = 1; i <= p; i)
4
b[ ① ] = a[i];
5
for (i = p + 1; i <= n; i)
6
b[i - p] = ② ;
7
for (i = 1; i <= ③ ; i++)
8
a[i] = b[i];
9
}
我们也可以用时间换空间，使用时间复杂度为 \mathcal{O}(n^2)O(n
2
)、空间复杂度为 \mathcal{O}(1)O(1) 的算法：

void swap2(int p){
int i, j, temp;
for (i = p + 1; i <= n; i) {
temp = a[i];
for (j = i; j >= ④ ; j–)
a[j] = a[j - 1];
⑤ = temp;
}
}
1
void swap2(int p){
2
int i, j, temp;
3
for (i = p + 1; i <= n; i) {
4
temp = a[i];
5
for (j = i; j >= ④ ; j–)
6
a[j] = a[j - 1];
7
⑤ = temp;
8
}
9
}
题目答案

填空位置 ①：

n - p + i

填空位置 ②：

a[i]

填空位置 ③：

n

填空位置 ④：

i - p + 1

填空位置 ⑤：

a[i - p]
题目解析

本题一共给出了 22 种算法：

第一种是开一个临时数组，将后 n - pn−p 个数和前 pp 个数依次拷贝到临时数组中，再把临时数组复制给当前数组。这一朴素的算法时间和空间复杂度均为 \mathcal{O}(n)O(n)。

第二种是每次把整个数组往左移一位(最左边的移到最后)，这样左移 pp 次即是最终的数组。省去了 \mathcal{O}(n)O(n) 的临时空间，但是时间复杂度上升至 \mathcal{O}(n2)O(n2)。

事实上还存在第三种算法，在时间和空间上结合了前两个算法的优点，具体做法是：取 pp 和 n - pn−p 之间的较小值，设为 qq，对调前 qq 个和后 qq 个元素，然后递归处理剩下长度为 n -2qn−2q 的子序列。具体代码实现读者可以参看提高组试题和解答。
（二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。

输入的第一行包含一个整数 nn，表示这棵树有 nn 个顶点，编号分别为 1, 2, …, n1,2,…,n，其中编号为 11 的为根结点。之后的第 ii 行有三个数 value，left_child，right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用 00 代替。输出 11 表示这棵树是二叉查找树，输出 00 则表示不是。

1

include [HTML_REMOVED]

2
using namespace std;
3
const int SIZE = 100;
4
const int INFINITE = 1000000;
5
struct node {
6
int left_child, right_child, value;
7
};
8
node a[SIZE];
9
int is_bst(int root, int lower_bound, int upper_bound){
10
int cur;
11
if (root == 0)return 1;
12
cur = a[root].value;
13
if ((cur > lower_bound) && ( ① ) &&
14
(is_bst(a[root].left_child, lower_bound, cur) == 1) && (is_bst(②,③,④) == 1))
15
return 1;
16
return 0;
17
}
18
int main(){
19
int i, n;
20
cin>>n;
21
for (i = 1; i <= n; i++)
22
cin>>a[i].value>>a[i].left_child>>a[i].right_child;
23
cout<<is_bst( ⑤ , -INFINITE, INFINITE)<<endl;
24
return 0;
25
}
题目答案

填空位置 ①：

cur < upper_bound

填空位置 ②：

a[root].right_child

填空位置 ③：

cur

填空位置 ④：

upper_bound

填空位置 ⑤：

1
题目解析

题目要求检查输入的二叉树是否为二叉查找树，试题中使用了一个较为巧妙的函数is_bst来判断：

a)当前子树是否为二叉查找树

b)当前子树所有的值是否在区间 [lower_bound, upper_bound][lower_bound,upper_bound]内。

初始时，我们从根节点出发，并将 lower_boundlower_bound，upper_boundupper_bound 分别设为无穷小、无穷大。我们去检验当前该点值是否符合传递下来的范围，也就是是否在区间 [lower_bound, upper_bound][lower_bound,upper_bound]内。然后，检验左子树是否是二叉查找树，右子树是否是二叉查找树，如果 22 个子树都是二叉查找树，同时当前点的值也在范围内，说明以当前点为根的树也是二叉查找树。

剩下的问题就是如何检验子树是否是二叉查找树，这个问题利用递归就可以来解决，直接调用is_bst，同时传递子树以及更新边界的值，即[lower_bound, upper_bound][lower_bound,upper_bound]，如果是左子树则将 upper_boundupper_bound 修改为 curcur，如果是右子树则将 lower_boundlower_bound 修改为 curcur。直到发现root == 0也就是当前点为空，证明递归到终点。