一、单选题
1、一个 32 位整型变量占用（ ）个字节。
A 4
B 8
C 32
D 128
解析：【喵呜刷题小喵解析】：在大多数现代计算机系统中，一个字节（Byte）由8位（bit）组成。因此，一个32位的整型变量会占用4个字节。这是因为32除以8等于4，所以正确答案是A选项，即4个字节。
2、二进制数 11.01 在十进制下是（ ）。
A 3.25
B 4.125
C 6.25
D 11.125
解析：【喵呜刷题小喵解析】
二进制数11.01转换为十进制数，整数部分11转换为十进制是1×2^1+1×2^0=3，小数部分0.01转换为十进制是1×2^-2=0.25，所以二进制数11.01转换为十进制数是3.25。因此，正确答案是B选项，即3.25。
3、下面的故事与（ ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事： "从前有座山， 山 里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个 老和尚给小和尚讲故事.... ’"
A 枚举
B 递归
C 贪心
D 分治
解析：【喵呜刷题小喵解析】：题目中描述的故事是一个典型的递归故事，因为故事的内容不断地重复，形成了一个递归的结构。递归算法是一种自我调用的算法，它将问题分解为更小的相同子问题，直到子问题变得足够简单以至于可以直接解决。在这个故事中，老和尚讲故事的过程就是一个递归的过程，每次重复讲述相同的故事，形成了一种递归的结构。因此，答案选B，即递归算法。
4、逻辑表达式（ ）的值与变量 A 的真假无关。
A (A ˅ B) ^ ¬A
B (A ˅ B) ^ ¬B
C (A ^ B) ˅ (¬A ^ B)
D (A ˅ B) ^ ¬A ^ B
解析：【喵呜刷题小喵解析】
首先，我们需要理解逻辑表达式中的符号。
* "A ˅ B" 表示 A 或 B，即 A 和 B 中至少有一个为真。
* "A ^ B" 表示 A 和 B 同时为真。
* "¬A" 表示非 A，即 A 为假。
* "^" 表示逻辑与，当且仅当两侧都为真时，结果为真。
* "˅" 表示逻辑或，当两侧至少有一个为真时，结果为真。
接着，我们分析每个选项：
A. (A ˅ B) ^ ¬A：这个表达式只有在 A 为真，B 为任意值（真或假）时，结果为真。因此，它的值与 A 的真假有关。
B. (A ˅ B) ^ ¬B：这个表达式只有在 B 为假时，结果为真，与 A 的真假无关。
C. (A ^ B) ˅ (¬A ^ B)：这个表达式只有在 A 和 B 同时为真，或者 A 为假且 B 为真时，结果为真。因此，它的值与 A 的真假有关。
D. (A ˅ B) ^ ¬A ^ B：这个表达式只有在 A 为假，B 为真时，结果为真。因此，它的值与 A 的真假有关。
因此，只有选项 B 的值与变量 A 的真假无关。
5、将（2, 6, 10, 17）分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数 h(x)= ( ), 将不会产生冲突，其中 amod b 表示 a 除以 b 的余数。
A x mod 11
B x2 mod 11
C 2x mod 11
D ⌊
⌋ mod 11，其中⌊⌋表示下取整
解析：【喵呜刷题小喵解析】：根据题目，我们需要找到一个哈希函数，使得（2, 6, 10, 17）存储到地址区间为0~10的哈希表中不会产生冲突。
首先，我们需要明确哈希表的大小，即地址区间的范围。在这个例子中，地址区间为0~10，共有11个地址。
然后，我们需要找到一个哈希函数，使得这4个元素（2, 6, 10, 17）在哈希表中的地址不重复。
对于选项A，x mod 11，当x分别为2, 6, 10, 17时，哈希值分别为1, 5, 0, 6，这4个值在0~10的范围内且不重复，满足条件。
对于选项B，x2 mod 11，当x分别为2, 6, 10, 17时，哈希值分别为4, 18, 81, 289，这些值在0~10的范围内有重复，不满足条件。
对于选项C，2x mod 11，当x分别为2, 6, 10, 17时，哈希值分别为4, 12, 20, 34，这些值在0~10的范围内有重复，不满足条件。
对于选项D，由于存在开方运算，并且开方后的结果再进行取整和取模操作，计算过程复杂且不一定满足条件，因此可以排除。
综上所述，选项A的哈希函数x mod 11满足条件，不会产生冲突。
6、在十六进制表示法中，字母 A 相当于十进制中的（ ）。
A 9
B 10
C 15
D 16
解析：【喵呜刷题小喵解析】在十六进制表示法中，字母A相当于十进制中的10。十六进制的字母A代表10，B代表11，C代表12，D代表13，E代表14，F代表15。因此，选项C是正确的。
7、2013-下图中所使用的数据结构是（ ）。
A 哈希表
B 栈
C 队列
D 二叉树
解析：【喵呜刷题小喵解析】：从图中可以看到，每个数据元素都通过键值对的方式存储，这种存储方式的特点是查找速度快，插入和删除的速度也相对较快，且可以根据键值直接访问数据。因此，这种数据结构称为哈希表，也称散列表。栈是一种后进先出（LIFO）的数据结构，通常用于实现函数调用、解析表达式等；队列是一种先进先出（FIFO）的数据结构，常用于实现消息队列、任务队列等；二叉树是一种树形结构，每个节点最多有两个子节点，常用于实现二叉搜索树、堆等。因此，根据图中的数据结构特点，可以判断所使用的数据结构是哈希表。
8、在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的 操作选项，它的意思是（ ）。
A 用剪切板中的文件替换该文件
B 在该文件所在文件夹中， 将该文件克隆一份
C 将该文件复制到剪切板， 并保留原文件
D 将该文件复制到剪切板， 并删除原文件
解析：【喵呜刷题小喵解析】：在Windows资源管理器中，当用鼠标右键单击一个文件时，出现的“复制”操作选项的意思是将该文件复制到剪切板，同时保留原文件。因此，选项C“将该文件复制到剪切板，并保留原文件”是正确的。其他选项A、B、D都与“复制”操作的实际意义不符。
9、已知一棵二叉树有 10 个节点，则其中至多有（ ）个节点有 2 个子节点。
A 4
B 5
C 6
D 7
解析：【喵呜刷题小喵解析】：在一棵二叉树中，节点的子节点数可以是0、1或2。若一棵二叉树有10个节点，那么最多可能有5个节点是叶子节点（即没有子节点），5个节点有1个子节点。剩下的0个节点有2个子节点。因此，其中至多有6个节点有2个子节点。
10、在一个无向图中，如果任意两点之间都存在路径相连， 则称其为连通图。下图是一个有4个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。
A 1
B 2
C 3
D 4
解析：【喵呜刷题小喵解析】：
首先，观察给定的无向图，它确实是一个连通图，因为任意两点之间都存在路径相连。
为了使其成为非连通图，我们需要删去一些边。观察图的结构，可以发现存在三个三角形：A-B-C，A-B-D，和C-D-E。如果删去三角形中的任意一条边，那么该三角形就不再连通，整个图也就变成了非连通图。
从给定的选项中，我们可以看到，需要删去的边的最少数量是3条（例如，删去A-B，B-C，和C-D）。因此，正确答案是C。
11、二叉树的（ ）第一个访问的节点是根节点。
A 先序遍历
B 中序遍历
C 后序遍历
D 以上都是
解析：【喵呜刷题小喵解析】：二叉树的遍历方式有三种：先序遍历、中序遍历和后序遍历。在先序遍历中，首先访问的是根节点，然后递归地遍历左子树，最后遍历右子树。在中序遍历中，首先遍历左子树，然后访问根节点，最后遍历右子树。在后序遍历中，首先遍历左子树，然后遍历右子树，最后访问根节点。因此，无论是先序遍历、中序遍历还是后序遍历，第一个访问的节点都是根节点。所以，选项D“以上都是”是正确的。
12、以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。
A A0, A1, A2, A3
B A0, A1, A3, A2
C A0, A2, A1, A3
D A0, A3, A1, A2
解析：【喵呜刷题小喵解析】：深度优先遍历是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索图的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
对于给定的无向图，从A0开始深度优先遍历，可能的遍历顺序是A0 -> A1 -> A2 -> A3或者A0 -> A1 -> A3 -> A2。因此，选项C（A0, A2, A1, A3）是不可能的遍历顺序。
13、IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（ ）位地址的 IPv6 协议所取代。
A 40
B 48
C 64
D 128
解析：【喵呜刷题小喵解析】：IPv4协议使用32位地址，而IPv6协议使用128位地址。随着IPv4地址的不断被分配，地址资源日趋枯竭，因此IPv6协议逐渐取代IPv4协议，成为下一代互联网协议。因此，正确答案是D，即IPv6协议使用128位地址。
14、（ ）的平均时间复杂度为 O(nlog n)，其中 n 是待排序的元素个数。
A 快速排序
B 插入排序
C 冒泡排序
D 基数排序
解析：【喵呜刷题小喵解析】：快速排序的平均时间复杂度为O(nlog n)，其中n是待排序的元素个数。这是因为快速排序采用分治策略，将待排序序列分成两个子序列，然后对子序列进行递归排序。在平均情况下，每次划分都能将待排序序列分成大小相近的两部分，因此时间复杂度为O(nlog n)。而插入排序和冒泡排序的时间复杂度通常为O(n^2)，基数排序的时间复杂度取决于待排序序列的位数，因此不符合题意。
15、下面是根据欧几里得算法编写的函数，它所计算的是a和b的（ ）。
int euclid(int a, int b)
{
if (b == 0)
return a;
else
return euclid(b, a % b);
}A 最大公共质因子
B 最小公共质因子
C 最大公约数
D 最小公倍数
解析：【喵呜刷题小喵解析】：欧几里得算法（辗转相除法）用于计算两个整数的最大公约数。在这个函数中，当b不为0时，递归调用euclid函数，将b和a对b的余数作为新的两个参数。当b等于0时，返回a，此时的a即为最大公约数。因此，这个函数所计算的是a和b的最大公约数。所以，正确选项是C。
16、通常在搜索引擎中， 对某个关键词加上双引号表示（ ）。
A 排除关键词，不显示任何包含该关键词的结果
B 将关键词分解，在搜索结果中必须包含其中的一部分
C、 精确搜索，只显示包含整个关键词的结果
D、
站内搜索，只显示关键词所指向网站的内容
解析：【喵呜刷题小喵解析】：在搜索引擎中，对某个关键词加上双引号表示精确搜索，只显示包含整个关键词的结果。因此，正确答案为C选项。A选项“排除关键词，不显示任何包含该关键词的结果”是错误的，因为加双引号不会排除关键词，而是精确匹配；B选项“将关键词分解，在搜索结果中必须包含其中的一部分”也是错误的，加双引号不会将关键词分解；D选项“站内搜索，只显示关键词所指向网站的内容”与加双引号的功能无关，因此也是错误的。
17、中国的国家顶级域名是（ ）。
A、 .cn
B、
.ch
C、
.chn
D、
.china
解析：【喵呜刷题小喵解析】：中国的国家顶级域名是“.cn”，其中“cn”代表“China”的缩写。因此，选项A“.cn”是正确的答案。选项B“.ch”并不是中国的国家顶级域名，选项C“.chn”和选项D“.china”也不是标准的国家顶级域名。
18、把 64 位非零浮点数强制转换成 32 位浮点数后，不可能（ ）。
A 大于原数
B 小于原数
C 等于原数
D 与原数符号相反
解析：【喵呜刷题小喵解析】
首先，我们需要理解浮点数在计算机中的表示。浮点数通常由一个符号位、一个尾数部分和一个指数部分组成。当我们把一个64位浮点数强制转换成32位浮点数时，我们实际上是在截断尾数部分和可能改变指数部分。
截断尾数部分意味着我们可能会丢失一些精度。由于尾数部分通常是小数部分，这种精度损失通常会导致转换后的数值比原数小。例如，如果原数的尾数部分是0.1011（这只是为了解释，实际数字可能会有更多位），截断后可能变成0.101，这就小于原数。
改变指数部分同样可能导致数值变小。如果原数的指数部分在转换过程中发生了变化，这也可能影响到最终的数值大小。
然而，有一种情况是我们需要考虑的：如果原数是一个非常大或者非常小的数，其32位浮点数表示可能是科学计数法的表示形式，而且指数部分在转换过程中并没有变化，那么32位浮点数可能仍然能精确地表示原数。这种情况下，转换后的数值可能会等于原数。
另外，由于有符号位，转换后的数值不可能与原数符号相反。因此，选项D“与原数符号相反”是不可能的。
综上，最不可能的情况是“与原数符号相反”，所以正确答案是D。
19、下列程序中，正确计算 1, 2, … , 100 这 100 个自然数之和 sum（初始值为 0）的是（ ）。
A、
i = 1;
do {
sum += i;
i++;
} while (i <= 100); B、
i = 1;
do {
sum += i;
i++;
} while (i > 100);C、i = 1;
while (i < 100) {
sum += i;
i++;
}
D、
i = 1;
while (i >= 100) {
sum += i;
i++;
}解析：【喵呜刷题小喵解析】：题目要求计算 1 到 100 这 100 个自然数之和。A 和 B 选项使用了 do-while 循环，但是 B 选项的循环条件是 `i > 100`，这会导致循环不执行任何操作，因为 `i` 初始值为 1，永远不会大于 100。A 选项的循环条件 `i <= 100` 是正确的，但循环体中的 `i++` 会使 `i` 在下次循环时超过 100，导致漏掉数字 100。C 选项使用了 while 循环，循环条件是 `i < 100`，循环体中 `i++` 会使 `i` 在下次循环时刚好等于 100，这样就不会漏掉任何数字。D 选项的循环条件是 `i >= 100`，这会导致循环不执行任何操作，因为 `i` 初始值为 1，永远不会大于等于 100。因此，正确答案是 C。
20、CCF NOIP复赛全国统一评测时使用的系统软件是（ ）。
A NOI Windows
B NOI Linux
C NOI Mac OS
D NOI DOS
解析：【喵呜刷题小喵解析】：CCF NOIP复赛全国统一评测时使用的系统软件通常是Linux。这是因为Linux是一个开源的操作系统，被广泛应用于各种计算机系统中，包括服务器和工作站。同时，Linux也提供了稳定的运行环境和强大的功能，能够满足评测系统的需求。因此，NOI Linux是最有可能的答案。其他选项如NOI Windows、NOI Mac OS和NOI DOS都不是通常使用的评测系统软件，因此不是正确答案。
二、简答题
21、7 个同学围坐一圈，要选2个不相邻的作为代表，有 种不同的选法。
参考答案：共有21种不同的选法。
解析：【喵呜刷题小喵解析】：
首先，我们可以将7个同学围坐一圈看作是一个排列问题。假设这7个同学按照顺时针方向排列，分别为A、B、C、D、E、F、G。
要选2个不相邻的同学作为代表，我们可以按照以下步骤来求解：
1. 首先，考虑第一个同学A，它不能选，所以第一个位置空着。
2. 接着，考虑第二个同学，它可以是B、C、D、E、F中的任意一个，所以有5种选择。
3. 接下来，考虑第三个同学，它不能是已经被选的B和第二个同学相邻的同学，所以它可以是C、D、E、F中的任意一个，但是有B在前面已经选过了，所以只有4种选择。
4. 以此类推，第四个同学有3种选择，第五个同学有2种选择，第六个同学有1种选择。
根据乘法原理，总的选法为：5 × 4 × 3 × 2 × 1 = 120种。
但是，这120种选法中有109种是相邻的，因为相邻的选法可以通过旋转得到。所以，实际的选法为：120 - 109 = 11种。
但是，我们还需要考虑一种特殊情况，即两个代表分别坐在首尾位置，即A的左边和G的右边。这样的选法有1种。
所以，总的选法为：11 + 1 = 12种。
但是，题目要求的是不相邻的选法，所以实际的选法为：C(7,2) - 12 = 21种。
因此，共有21种不同的选法。
22、某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数 s1, s2, … , sn ，均为0或1。该系统每次随机生成n个数a1, a2, … , an，均为0或1，请用户回答(s1a1+s2a2+… +snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为， 即使 问答的过程被泄露， 也无助于破解密码—— 因为用户并没有直接发送密码。
然而， 事与愿违。例如，当n= 4 时， 有人窃听了以下 5 次问答：
就破解出了密码 s1= ，s2= ，s3= ，s4= 。
参考答案：根据题目描述，当n=4时，有人窃听了以下5次问答，并尝试破解密码。根据给出的问答数据，我们可以按照以下步骤进行解析：1. 观察给出的5次问答数据，可以发现a1、a2、a3、a4的取值均为0或1。2. 根据题目要求，我们需要计算(s1a1+s2a2+s3a3+s4a4)除以2的余数，并判断该余数是否与窃听到的回答一致。3. 根据5次问答数据，我们可以列出以下5个方程：- 方程1：(s1*0 + s2*0 + s3*1 + s4*0) mod 2 = 0- 方程2：(s1*0 + s2*1 + s3*0 + s4*1) mod 2 = 1- 方程3：(s1*1 + s2*0 + s3*0 + s4*1) mod 2 = 1- 方程4：(s1*1 + s2*1 + s3*0 + s4*0) mod 2 = 0- 方程5：(s1*1 + s2*0 + s3*1 + s4*0) mod 2 = 14. 解这5个方程，我们可以得到s1、s2、s3、s4的取值。
解析：【喵呜刷题小喵解析】：
在这个问题中，我们需要根据窃听到的问答数据来破解密码。由于密码是n个数s1, s2, …, sn，均为0或1，我们需要通过问答的方式来验证密码的正确性。在问答过程中，系统随机生成n个数a1, a2, …, an，均为0或1，然后要求用户回答(s1a1+s2a2+…+snan)除以2的余数。
根据题目描述，当n=4时，有人窃听了以下5次问答，并尝试破解密码。我们可以按照上述步骤，列出5个方程，然后解方程来得到s1、s2、s3、s4的取值。由于每次问答中a的取值均为0或1，我们可以利用mod 2的运算来简化方程。通过观察5次问答数据，我们可以发现a1、a2、a3、a4的取值规律，然后根据方程求解，得到密码的取值。
需要注意的是，虽然该系统声称即使问答的过程被泄露，也无助于破解密码，但实际上通过多次问答数据，攻击者可以通过分析来破解密码。因此，在设计密码验证系统时，需要考虑到各种安全因素，并采取更加安全的验证方式。
23、
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin>>a>>b;
cout<<a<<"+"<<b<<"="<<a+b<<endl;
}
输入： 3 5
输出：
参考答案：代码中的错误有：1. 缺少空格：`cout` 和 `a` 之间缺少空格，应该改为 `cout << a << " + " << b << " = " << a + b << endl;`2. `endl` 的使用不正确：`endl` 是流的操纵符，应该紧跟在输出流后面，不应该有空格，应该改为 `<< endl;`
解析：【喵呜刷题小喵解析】：
在给出的代码中，存在几个问题。首先，`cout` 和 `a` 之间缺少空格，这会导致输出格式不正确。其次，`endl` 的使用也有误，它应该紧跟在输出流后面，不应该有空格。修正后的代码应该是：`cout << a << " + " << b << " = " << a + b << endl;`。这样，当输入为 3 和 5 时，输出应该为 `3 + 5 = 8`。
24、
#include <iostream>
using namespace std;
int main()
{
int a, b, u, i, num;
cin>>a>>b>>u;
num = 0;
for (i = a; i <= b; i++)
if ((i % u) == 0)
num++;
cout<<num<<endl;
return 0;
}
输入： 1 100 15
输出：
参考答案：输出结果为：6
解析：【喵呜刷题小喵解析】：在这个程序中，用户输入三个整数a、b和u。程序计算从a到b（包括a和b）的所有整数中，能被u整除的整数的数量，并将结果输出。在这个例子中，输入的整数是1、100和15，所以程序计算从1到100（包括1和100）的所有整数中，能被15整除的整数的数量。在1到100之间，能被15整除的整数有：15、30、45、60、75和90，共6个，所以输出结果为6。
25、
#include <iostream>
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;
}
输入：
12 17 2 4 6 9 11 15 17 18 19 20 21 25
输出：
参考答案：输出：7
解析：【喵呜刷题小喵解析】：
该程序实现的是二分查找算法。首先，程序从输入中读取两个整数n和f，其中n表示数组a的长度，f是需要查找的整数。接着，程序读入数组a的n个元素。
程序初始化左边界left为1，右边界right为n。然后，程序进入do-while循环，循环条件是left小于right。在每次循环中，程序计算中间位置middle为(left + right) / 2。然后，程序检查f是否小于等于a[middle]。如果是，说明f可能在左半部分，因此将right更新为middle。否则，说明f可能在右半部分，因此将left更新为middle + 1。
当循环结束时，left和right相等，此时left的值就是f在数组a中的位置（如果f在数组a中）。程序输出left的值，即f在数组a中的位置。
对于给定的输入，数组a为2 4 6 9 11 15 17 18 19 20 21 25，需要查找的整数f为17。程序从数组a的中间位置开始查找，每次比较f和中间位置的元素，直到找到f或者left和right相等。在查找过程中，程序将right更新为7，此时left和right相等，即f在数组a中的位置为7，因此输出结果为7。
26、
#include <iostream>
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;
}
输入：
6
2 5 3 11 12 4
输出：
参考答案：3
解析：【喵呜刷题小喵解析】：该题是一道算法题，根据给定的代码和输入，需要求解最大的序列长度。
首先，代码定义了一个常量`SIZE`，表示数组的大小为100。然后定义了两个数组`height`和`num`，分别用于存储高度和对应的序列长度。`n`表示输入的高度数量，`ans`用于存储最大的序列长度。
接下来，代码通过循环读入`n`个高度，并初始化对应的序列长度为1。然后，对于每个高度，代码会遍历之前的所有高度，如果当前高度比前面的某个高度小，且该高度的序列长度大于等于当前高度的序列长度，则更新当前高度的序列长度。
最后，代码再次遍历所有的高度，找到最大的序列长度，并输出。
根据给定的输入，程序会先读入6个高度，然后遍历这6个高度，并更新对应的序列长度。最后，程序会输出最大的序列长度，即3。
需要注意的是，题目中并没有给出期望的输出，因此需要根据代码的逻辑和输入来推断输出。
三、实操题
27、完善程序:（序列重排）全局数组变量a定义如下：
const int SIZE = 100;
int a[SIZE], n;
它记录着一个长度为n的序列a[1],a[2], … , a[n]。
现在需要一个函数，以整数p(1≤p≤n)为参数，实现如下功能：将序列a的前p个数与后n–p个数对调，且不改变这p 个数（或n–p个数）之间的相对位置。例如，长度为5的序列1,2,3,4,5，当p=2 时重排结果为3,4,5,1,2。
有一种朴素的算法可以实现这一需求，其时间复杂度为O(n)、空间复杂度为O(n)：
void swap1(int p)
{
int i, j, b[SIZE];
for (i = 1; i <= p; i++)
b[ (1) ] = a[i]; //（3 分）
for (i = p + 1; i <= n; i++)
b[i - p] = (2) ; //（3 分）
for (i = 1; i <= (3) ; i++) //（2 分）
a[i] = b[i];
}
我们也可以用时间换空间，使用时间复杂度为O(n2)、空间复杂度为O(1)的算法：
void swap2(int p)
{
int i, j, temp;
for (i = p + 1; i <= n; i++) {
temp = a[i];
for (j = i; j >= (4) ; j--) //（3 分）
a[j] = a[j - 1];
(5) = temp; //（3 分）
}
}
参考答案：1. 对于第一个空，应填入`i`，表示将前p个数存入数组b中。2. 对于第二个空，应填入`a[i]`，表示将后n-p个数存入数组b中。3. 对于第三个空，应填入`n`，表示从数组b中取出元素，存入数组a中。4. 对于第四个空，应填入`p+1`，表示从数组a中开始向前移动元素。5. 对于第五个空，应填入`a[j-1]`，表示将元素temp存入正确的位置。
解析：【喵呜刷题小喵解析】：
对于第一个空，我们需要将数组a的前p个数存入数组b中，所以应该填入`i`，表示当前正在处理的是第i个数。
对于第二个空，我们需要将数组a的后n-p个数存入数组b中，所以应该填入`a[i]`，表示当前正在处理的是第i个数。
对于第三个空，我们需要从数组b中取出元素，存入数组a中，所以应该填入`n`，表示从数组b中取出所有元素。
对于第四个空，我们需要从数组a中的第p+1个位置开始，向前移动元素，所以应该填入`p+1`。
对于第五个空，我们需要将元素temp存入正确的位置，即原数组中第i-1个位置，所以应该填入`a[j-1]`。
28、完善程序:（二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的 值、小于其右子树上所有节点的值。 试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数n，表示这棵树有n个顶点， 编号分别为1,2, … ,n，其 中编号为1的为根结点。之后的第i行有三个数value,left_child,right_child，分别表示 该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节 点，则用0代替。输出1表示这棵树是二叉查找树，输出0则表示不是。
#include <iostream>
using namespace std;
const int SIZE = 100;
const int INFINITE = 1000000;
struct node {
int left_child, right_child, value;
};
node a[SIZE];
int is_bst(int root, int lower_bound, int upper_bound)
{
int cur;
if (root == 0)
return 1;
cur = a[root].value;
if ((cur > lower_bound) && ( (1) ) && //（3 分）
(is_bst(a[root].left_child, lower_bound, cur) == 1) &&
(is_bst( (2) , (3) , (4) ) == 1)) //（3 分，3 分，3 分）
return 1;
return 0;
}
int main()
{
int i, n;
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i].value>>a[i].left_child>>a[i].right_child;
cout<<is_bst( (5) , -INFINITE, INFINITE)<<endl; //（2 分）
return 0;
}
参考答案：1. 完善函数`is_bst`中的条件判断，确保左子树和右子树都是二叉查找树。2. 在`main`函数中，将根节点的编号从用户输入中读入，并传递给`is_bst`函数。
解析：【喵呜刷题小喵解析】：
根据题目要求，我们需要判断给定的树是否为二叉查找树。二叉查找树的性质是每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。
首先，我们注意到`is_bst`函数的参数有三个：`root`表示当前节点的编号，`lower_bound`表示当前节点值可以取的最小值，`upper_bound`表示当前节点值可以取的最大值。
在函数内部，我们首先检查当前节点是否为0（即不存在），如果是，则返回1，表示这是一个空树，可以认为是二叉查找树。
然后，我们检查当前节点的值是否在`lower_bound`和`upper_bound`之间。如果不在，说明该树不是二叉查找树，直接返回0。
接下来，我们需要检查左子树和右子树是否都是二叉查找树。这里，我们需要递归调用`is_bst`函数，并传入左子节点的编号、当前节点的值和右子节点的编号作为参数。
对于左子树，我们传入左子节点的编号作为根节点，当前节点的值作为`lower_bound`（因为左子树上所有节点的值都应该小于当前节点的值），当前节点的值作为`upper_bound`（因为左子树的值不能超过当前节点的值）。
对于右子树，我们传入右子节点的编号作为根节点，当前节点的值作为`lower_bound`（因为右子树上所有节点的值都应该大于当前节点的值），无穷大`INFINITE`作为`upper_bound`（因为右子树的值不能超过无穷大）。
如果左子树和右子树都是二叉查找树，那么当前树也是二叉查找树，返回1；否则，返回0。
在`main`函数中，我们首先从用户输入中读入树的节点数`n`，然后读入每个节点的值、左子节点编号和右子节点编号，并存储在数组`a`中。
最后，我们调用`is_bst`函数，传入根节点的编号（题目中未明确给出，需要根据用户输入读入）、负无穷大`-INFINITE`作为`lower_bound`、正无穷大`INFINITE`作为`upper_bound`，并将结果输出。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
