1 条题解
-
0
入门级 CSP-J 第7套初赛模拟试题 —— 详细解析
一、单项选择题（共15题，每题2分，共计30分）
1. 以下属于系统软件的是：（ A ）。
A．C++编译器 B．腾讯QQ C．CAD D．游戏软件
解析： 系统软件是指负责管理计算机硬件资源、为其它软件提供运行/开发基础环境的软件，典型代表有操作系统、编译器、数据库管理系统等。C++编译器属于开发工具类的系统软件，是编写、编译程序所必需的基础环境；而QQ、CAD、游戏软件都是面向具体用户任务的应用软件。答案为 A。
2. ___年___月___日在国际电信标准组织3GPP RAN第78次全体会议上，5G NR首发版本正式发布，这是全球第一个可商用部署的5G标准。（ D ）
A．2017年8月18日 B．2018年1月1日 C．2017年12月25日 D．2017年12月21日
解析： 这是一道通信技术发展史实题。3GPP在第78次RAN全会上正式冻结/发布5G NR（New Radio）首发版本（非独立组网NSA标准）的时间是2017年12月21日，这是全球第一个可商用部署的5G标准。答案为 D。
3. 如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。例如：00000001表示+1,10000001表示-1，试问这样表示法的整数A的范围应该是（ A ）。
A．-127<=A<=127 B．-128<=A<=128 C．-128<=A<128 D．-127<=A<=128
解析： 这是原码表示法：最高位是符号位，其余7位是数值位。7位能表示的最大数值是
2⁷-1=127。由于原码中"+0"（00000000）和"-0"（10000000）是两种不同的编码但代表同一个数值0，所以正数范围是0~127，负数范围是-0~-127，实际可表示的整数范围为 -127 到 +127。答案为 A。
4. 下列属于网络模型的名称是（ B ）。
A．LAN B．TCP/IP C．FTP D．SMTP
解析： LAN（局域网）是网络的一种物理规模类型，FTP、SMTP都是具体的应用层协议，而 TCP/IP 才是一整套完整的网络体系结构模型（协议簇），规定了从物理层到应用层各层之间的分工与协作关系。答案为 B。
5. 在C++中，(-7)%(-5)等于（ B ）。
A．2 B．-2 C．3 D．-3
解析： C++中整数取模运算的结果符号与被除数（左操作数）的符号保持一致，且除法采用"向零截断"的方式取商。
-7 / -5向零截断的商是1（因为-7/-5≈1.4，截断取整为1），于是(-7)%(-5) = -7 - (-5)×1 = -7+5 = -2。答案为 B。
6. 学号为1到30的小朋友顺时针排成一圈，从数字1开始顺时针数下去，1,2,3,…,28,29,30,31,32,…，一圈又一圈，问当数到数字n，所在的小朋友的学号为多少？（ B ）。
A．(n-1)%30 B．1+(n-1)%30 C．(n+1)%30-1 D．(n+1)%30
解析： 这是经典的"循环编号"取模问题。验证选项B：
1+(n-1)%30。- n=1时：1+(1-1)%30 = 1+0 = 1 ✓（数到1时正是1号）
- n=30时：1+(30-1)%30 = 1+29 = 30 ✓（数到30时正是30号）
- n=31时：1+(31-1)%30 = 1+30%30 = 1+0 = 1 ✓（数到31，正好绕回1号小朋友）
规律完全吻合，答案为 B。
7. 一棵完全二叉树的结点总数为41，其叶结点数为（ D ）。
A．18个 B．19个 C．20个 D．21个
解析： 在一棵完全二叉树中，设叶子结点（度为0）数为 n₀，度为1的结点数为 n₁，度为2的结点数为 n₂，则有关系：
- 总结点数：
n = n₀+n₁+n₂ - 二叉树的边数关系：
n₂×2+n₁×1 = n-1（每个非根结点都恰好有一条边连向父结点）
结合这两式可以推出
n₀ = n₂+1。又因为完全二叉树中度为1的结点数 n₁ 只能是0或1：当总结点数 n 为奇数时（本题n=41为奇数），意味着 n₁ 必须为0（否则总数的奇偶性会矛盾）。此时n = n₀+n₂ = n₀+(n₀-1) = 2n₀-1，解得n₀=(n+1)/2=(41+1)/2=21。答案为 D（21个）。
8. 给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是（ D ）。
A．O(n)、O(n²)、O(log₂n) B．O(log₂n)、O(n)、O(n²) C．O(n²)、O(n)、O(n) D．O(n²)、O(n²)、O(n²)
解析： 插入排序、冒泡排序、选择排序都属于基础的比较类排序算法，三者的（平均及最坏情况）时间复杂度都是 O(n²)——它们都需要通过两层嵌套循环逐个比较、移动元素来完成排序，属于同一量级的排序方法。答案为 D。
9. 请给以下四个事件发生的时间顺序（ B ）。
1．举办第一次NOIP 2．举办第一次NOI网络同步赛 3．NOIP提高组由四题改为三题 4．举办第一次APIO A．1234 B．1243 C．2134 D．2143
解析： 这是信息学奥赛发展历史的考查题。按照历史脉络，第一次NOIP（全国青少年信息学奥林匹克联赛）最早举办；随后逐步开展了NOI网络同步赛这一面向更广泛地区的观摩/同步赛制；再往后，APIO（亚太地区信息学奥林匹克竞赛）首次举办；而"NOIP提高组由四题改为三题"这一赛制调整是相对更晚才发生的变化。按时间先后排列即为：1（NOIP）→2（NOI网络同步赛）→4（APIO）→3（提高组改三题），对应选项"1243"。答案为 B。
10. 以下在OSI模型中属于TCP/IP模型中的应用层的是（ D ）。
A．应用层 B．网络层 C．数据链路层 D．表示层
解析： TCP/IP模型只有四层（网络接口层、网络层、传输层、应用层），其中TCP/IP的"应用层"实际上合并了OSI七层模型中的会话层、表示层、应用层这三层的功能。本题四个选项中，"网络层""数据链路层"分别对应TCP/IP的网络层和网络接口层，都不属于TCP/IP的应用层；而"表示层"正是被合并进TCP/IP应用层的OSI层次之一。答案为 D。
11. 以下关于图的不正确说法是（ B ）。
A．所有顶点的度数之和等于边数的2倍 B．所有顶点的度数之和不一定等于边数的2倍 C．任意一个图一定有偶数个奇点 D．在有向图中顶点的入度之和等于出度之和
解析： 图论中的"握手定理"明确指出：无向图中所有顶点的度数之和恒等于边数的2倍（因为每条边都会给它的两个端点各贡献1点度数），这是一条恒成立的定理，A的说法是正确的。而 B 说"不一定等于"，与握手定理直接矛盾，是错误的说法（本题要选的就是这个错误说法）。C（奇点个数必为偶数个）和D（有向图中所有顶点的入度之和等于出度之和，因为每条边同时贡献一次入度和一次出度）都是正确的图论结论。答案为 B。
12. 6个人分乘两辆不同的汽车，每辆车最多坐4人，则不同的乘车方法数为（ B ）。
A．40 B．50 C．60 D．70
解析： 设两辆车分别为甲车、乙车（两车不同，需要区分）。由于每辆车最多坐4人，6个人分成两组的合法分配方式（每组都不超过4人）只有：(2人,4人)、(3人,3人)、(4人,2人)这三种人数组合（(0,6)、(1,5)、(5,1)、(6,0)都因为其中一辆车超过4人而不合法）。
分别计算每种组合下的方法数（从6人中选出坐甲车的人，剩下的人自动坐乙车）：
- 甲车2人、乙车4人：C(6,2)=15种
- 甲车3人、乙车3人：C(6,3)=20种
- 甲车4人、乙车2人：C(6,4)=15种
总计：15+20+15=50种。答案为 B。
13. 为了实现两数交换，代码如下：
void swapAB(int &a,int &b) { ______; b=a-b; a=a-b; }则空格内要填入的语句是（ A ）。 A．a=a+b B．a=a*b C．a=a-b D．a=a&b
解析： 这是经典的"不借助临时变量、用加减法交换两数"技巧：
- 空格处填
a=a+b，此时a保存了原a、原b的和； b=a-b= (原a+原b)-原b = 原a（b现在变成了原来的a）；a=a-b= (原a+原b)-原a = 原b（a现在变成了原来的b）。
三步下来正好完成了a、b的交换。答案为 A。
14. 某数列有1000个各不相同的数，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检索（ B ）个数据。
A．1000 B．10 C．100 D．500
解析： 二分查找每比较一次，待查找的范围就缩小一半，最坏情况下所需的比较次数约为
⌈log₂n⌉。对于n=1000，log₂1000≈9.97，向上取整约等于 10 次左右。答案为 B。
15. 以下简称和全称不对应的是（ C ）。
A．NAT(Network Address Translation) B．TCP(Transmission Control Protocol) C．ARP(Adobe Resolution Protocol) D．ICMP(Internet Control Message Protocol)
解析： ARP 的正确全称应为 Address Resolution Protocol（地址解析协议，用于将IP地址解析为MAC地址），选项中给出的"Adobe Resolution Protocol"是错误的全称（Adobe是一家软件公司，与该协议毫无关系）。其余NAT、TCP、ICMP的简称与全称都对应正确。答案为 C。
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填"√"，错误填"×"；除特殊说明外，判断题1.5分，选择题4分，共计40分）
第1题：统计两字符串间相同字符对的数目
01 #include<bits/stdc++.h> 02 using namespace std; 03 int main() 04 { 05 string s1,s2; 06 cin>>s1;cin>>s2; 07 int cnt=0; 08 for (int i=0;i<s1.size();i++) 09 { 10 for (int j=0;j<s2.size();j++) 11 if (s1[i]==s2[j]) cnt++; 12 } 13 cout<<cnt; 14 }背景说明： 这段代码用双重循环遍历s1的每一个字符和s2的每一个字符，只要两者相等（
s1[i]==s2[j]）就把计数器cnt加一。也就是说，cnt统计的是：把s1中每个字符和s2中每个字符两两配对，一共有多少对是"字符相同"的（如果某字符在s1中出现a次、在s2中出现b次，则单是这个字符就会贡献a×b次匹配）。判断题
(1) 输入必须全要是字母，否则无法被识别。（ × ）
解析：
cin>>s1读取字符串时，只是以空白字符（空格、换行、制表符等）作为分隔，并不限制字符必须是字母——数字、标点等任意非空白可见字符都能被正常读入。因此该说法不成立，判错。(2) 将10行的j全部换成i是有问题的。（ √ ）
解析： 第10行
for (int j=0;j<s2.size();j++)如果把里面的j全部换成i，会变成for (int i=0;i<s2.size();i++)。虽然内层用int重新声明变量i在语法上是合法的（内层i会遮蔽外层同名的i），但这样一来，第11行原本想引用"外层循环变量i（遍历s1的下标）"，实际引用到的却是这个刚被内层重新定义、范围是s2长度的新i，导致s1的下标访问逻辑完全错乱（可能越界，也可能统计结果完全错误）。因此这样的替换确实"有问题"，判对。(3) 本程序的功能是统计两个字符串的最长公共子序列长度。（ × ）
解析： 本程序统计的只是"两字符串中字符两两相等的配对总数"，与"最长公共子序列（LCS）"是完全不同的概念——LCS要求在保持字符相对先后顺序不变的前提下，找出两串共有的最长子序列长度，通常需要动态规划求解，与本程序简单的双重循环计数完全是两回事。判错。
(4) 本程序的时间复杂度为O(n²)。（ √ ）
解析： 双重循环分别遍历s1和s2，若两字符串长度都是n量级，则总的基本操作次数是 n×n，时间复杂度为 O(n²)。判对。
选择题
(5) 若输入的两个字符串长度均为12，那么输出最大为（ B ）。 A．0 B．144 C．12 D．24
解析： 当s1和s2的12个字符完全相同（例如都是同一个字母重复12次）时，s1中的每一个字符都能与s2中的每一个字符匹配成功，此时cnt能达到最大值
12×12=144。答案为 B。(6) 若s1长度为4，输出为6，则s2的长度至少为（ B ）。 A．1 B．2 C．3 D．4
解析： 设s1中某个字符出现了k次（k<=4），s2中这个相同字符出现了m次，则这两者单独就能贡献
k×m次匹配。要用最短的s2凑出总匹配数6，应当尽量利用s1中出现次数最多的那个字符：比如让s1中某字符出现3次（如s1="aaab"），s2中这个字符出现2次（m=2），则贡献3×2=6，恰好达到目标，此时s2只需要长度2（"aa"）即可，不需要更多字符。答案为 B。
第2题：差分数组统计区间总覆盖次数
01 #include<bits/stdc++.h> 02 using namespace std; 03 const int MAXN=1e5+7; 04 int a[MAXN],b[MAXN]; 05 int main(){ 06 int n,m,x,y; 07 cin>>n>>m; 08 for (int i=1;i<=n;i++) 09 { 10 cin>>x>>y; 11 a[x]++; 12 a[y+1]--; 13 } 14 int cnt=0,ans=0; 15 for (int i=0;i<=m;i++) 16 { 17 cnt+=a[i]; 18 ans+=cnt; 19 } 20 cout<<ans; 21 }注：输入流中 1<=x<=y<=m
背景说明： 这是经典的差分数组技巧：对于每个区间
[x,y]，在差分数组上执行a[x]++、a[y+1]--，这样对差分数组做一次前缀和，就能在任意位置i得到"有多少个区间覆盖了位置i"（记为cnt）。第14~19行先求出每个位置i(0~m)的覆盖次数cnt，再把这些覆盖次数逐个累加到ans里。最终ans的含义就是：所有n个区间的长度之和（因为每个区间对"覆盖次数之和"的贡献，恰好等于它自身的长度y-x+1）。判断题
(1) 输入的x和y可以是全体整数。（ × ）
解析： 题目已明确注明"输入流中1<=x<=y<=m"，也就是说x、y必须是满足这个范围约束的正整数，而不能是任意整数（比如负数、超过m的数，或者x>y的情况），否则不仅会破坏"区间"的语义，还可能造成数组访问越界。判错。
(2) 将14行的清零过程除去没有问题。（ × ）
解析： 第14行
int cnt=0,ans=0;其实是对cnt、ans这两个局部变量的初始化赋值（并非什么额外的"清零操作"，而是变量声明时就该赋的初值）。如果去掉这行，cnt和ans将成为未初始化的局部变量，其值是不确定的垃圾数据，后续的累加运算会得到完全错误、不可预测的结果。判错。(3) 将17行与18行交换位置不会影响最终结果。（ × ）
解析： 第17行
cnt+=a[i];和第18行ans+=cnt;存在严格的先后依赖：必须先把当前位置的差分值累加进cnt（得到"截至当前位置i的覆盖次数"），然后才能把这个最新的cnt值累加进ans。如果颠倒顺序，ans+=cnt会先于cnt+=a[i]执行，此时用的是上一轮（位置i-1）留下的旧cnt值，导致每一步都"错位"了一格，最终ans的结果会整体出错。判错。(4) 将11行的x改成x-1并把12行的y+1改成y不会影响最终结果。（ √ ）
解析： 原本
a[x]++; a[y+1]--;使得覆盖区间恰好是[x,y]（长度为y-x+1）。改成a[x-1]++; a[y]--;后，覆盖区间变成了[x-1,y-1]——相当于整个区间整体向左平移了1个单位，但区间的长度依然不变（仍是y-x+1）。由于ans本质上统计的是"所有区间长度之和"，只要平移后的区间仍完整落在数组有效范围内（不发生越界丢失），每个区间对总长度的贡献不会因为整体平移而改变，所以最终的ans结果不受影响。判对。选择题
(5) 现在已知输入的n与m，则答案的极差为（ C ）。 A．n-m B．2n-m C．nm-n D．n²-2m
解析： 由前面分析可知，
ans等于n个区间各自长度（y-x+1）之和。在满足1<=x<=y<=m的约束下：- 每个区间的最小长度是1（当x=y时，即单独一个点），因此ans的最小值为
n×1=n； - 每个区间的最大长度是m（当x=1,y=m，覆盖整个范围时），因此ans的最大值为
n×m。
极差（最大值-最小值）=
nm-n。答案为 C。(6) 在(1)的基础上，去除"注"中的条件，则答案的极差为（ A ）。 A．2n+2nm B．n+m C．2n+2m D．mn+m
解析： 一旦去掉"1<=x<=y<=m"这一限制，x、y可以不再满足有序、有界的关系。注意到最终统计范围只看
i∈[0,m]这段区间内的覆盖次数（第15行for(int i=0;i<=m;i++)），所以每个区间对ans的贡献实际上取决于它的"+1"和"-1"分别落在哪个位置：- 要让某个区间对ans的贡献最大：让
a[x]++落在位置0（即x=0，从最开始就生效），同时让a[y+1]--落在m之后（即不在0~m统计范围内，不发生任何抵消），这样该区间会让[0,m]这m+1个位置的cnt都多算1，贡献了 (m+1)； - 要让某个区间对ans的贡献最小（即负得最多）：反过来，让
a[y+1]--落在位置0（提前生效），而a[x]++落在m之后（不在统计范围内），这样该区间会让[0,m]这m+1个位置的cnt都少算1，贡献了 -(m+1)。
n个区间独立选择"最大贡献"或"最小贡献"，可得ans的最大值为
n(m+1)，最小值为-n(m+1)。极差 =
n(m+1) - (-n(m+1)) = 2n(m+1) = 2n+2nm。答案为 A。
第3题：值传递、引用传递与指针
01 #include<bits/stdc++.h> 02 using namespace std; 03 int a[6]; 04 int change(int a){a++;} 05 int change1(int &a){a++;} 06 int main(){ 07 int c=1;for (int i=1;i<=5;i++) a[i]=i*3; 08 int*b=&a[1]; 09 change(*b);cout<<*b<<endl;cout<<a[1]<<endl; 10 *b++;cout<<*b<<endl;cout<<a[1]<<endl; 11 change1(*b);cout<<*b<<endl;cout<<a[1]<<endl; 12 *b=c; 13 change(c);cout<<*b<<endl;cout<<c<<endl; 14 change1(c);cout<<*b<<endl;cout<<c<<endl; 15 return 0; 16 }背景说明：
change(int a)是按值传递：函数内部拿到的是实参的一份拷贝，函数内的修改不会影响到函数外的实参。change1(int &a)是按引用传递：形参a是实参的"别名"，函数内的修改会直接反映到调用者的变量上。先完整模拟一遍程序的运行过程（便于后面各小题分析）：
- 初始化：
a[1]=3,a[2]=6,a[3]=9,a[4]=12,a[5]=15；c=1；指针b=&a[1]（此时*b即a[1]=3）。 - 第9行：
change(*b)按值传递，只修改函数内部的临时拷贝，a[1]不变。输出：*b→3，a[1]→3。 - 第10行：
*b++;由于++的运算优先级高于*（解引用），这一句实际上是*(b++)——先取*b的值（丢弃不用），真正产生的副作用是让指针b自身向后移动一位，现在b指向a[2]（值为6），a[1]的内容并未改变。输出：*b（此时是a[2]）→6，a[1]→3。 - 第11行：
change1(*b)此时b指向a[2]，按引用传递直接修改的是a[2]本身，a[2]从6变成7。输出：*b（a[2]）→7，a[1]→3（依然没变）。 - 第12行：
*b=c;把c(=1)赋值给*b（即a[2]），所以a[2]变成1。 - 第13行：
change(c)按值传递，c本身不变，仍是1。输出：*b（a[2]，第12行刚设为1，未受影响）→1，c→1。 - 第14行：
change1(c)按引用传递，c真正变成2。输出：*b（a[2]依旧是1，没有被这次调用触及）→1，c→2。
于是完整的输出序列依次是：3，3，6，3，7，3，1，1，1，2。
判断题
(1) 将第7行中int换为long long后程序依然能通过编译。（ × ）
解析： 第7行
int c=1;如果把c的类型改为long long c=1;，虽然前面大部分语句仍能正常编译（如change(c)按值传递时long long会被隐式截断为int，这是允许的），但到第14行change1(c);时，change1要求的形参是int &a（对int的非常量引用），而此时实参c是long long类型——编译器需要先把long long隐式转换成int（产生一个临时的int值），而非常量引用是不能绑定到这种由隐式类型转换产生的临时量上的，这会导致编译错误。因此"依然能通过编译"的说法是错误的，判错。(2) change与change1两个函数等价。（ × ）
解析：
change是按值传递、change1是按引用传递，二者对实参的实际影响完全不同（从前面的模拟也能看出：change(c)之后c仍是1，而change1(c)之后c真的变成了2），二者并不等价。判错。(3) 将第12行改为b=&c；输出值不变。（ × ）
解析： 原第12行
*b=c;是把c的值赋给*b（即a[2]=1），此后b依然指向a[2]。如果改成b=&c;，则是让指针b转而指向变量c本身，此后*b就等价于c了。重新模拟第13、14行：
change(c)：c不变（仍是1）。输出：*b（此时即c本身）→1，c→1。change1(c)：c变成2。输出：*b（此时即c本身，已变为2）→2，c→2。
对比原程序最后两行的输出（1,1,1,2），修改后的最后两行输出变成了（1,1,2,2）——最后一次
*b的值由原来的"1"变成了"2"，输出结果发生了变化，并非"不变"。判错。(4) 将第8行换为int * b=a+1；输出值不变。（ √ ）
解析： 数组名
a本身可以看作指向a[0]的指针，a+1（指针加法）恰好等价于&a[1]，两者是同一个地址。所以把第8行int*b=&a[1];改写成int*b=a+1;，b最终指向的位置完全相同，对整个程序的运行结果没有任何影响。判对。选择题
(5) 输出结果的最大值是（ C ）。 A．6 B．4 C．7 D．5
解析： 完整输出序列为
3,3,6,3,7,3,1,1,1,2，其中最大的数是 7（来自第11行change1(*b)之后a[2]的值）。答案为 C。(6) 输出结果的积是（ A ）。 A．6804 B．5760 C．11520 D．13608
解析： 把全部10个输出数值连乘：
3×3×6×3×7×3×1×1×1×2= 3×3=9 → ×6=54 → ×3=162 → ×7=1134 → ×3=3402 → ×1×1×1不变 → ×2=6804答案为 A。
三、完善程序（单选题，每小题3分，共计30分）
第1题：统计每个数前面比它大的数字个数
给出N个整数，要统计每个数前面有多少比它大的数字。比如有5个数的数列：2 5 1 3 4，则第1个数2之前有0个数比它大；第2个数5之前有0个数比它大；第3个数1之前有2个数比它大；第4个数3之前有1个数比它大；第5个数4之前有1个数比它大。 数据范围：每个数范围是[0…200]，N<=10⁵
01 #include<iostream> 02 using namespace std; 03 int d[100002]; 04 int c[1300]; 05 int main() { 06 int n,ans,x; 07 cin>>n; 08 for (int i=0;i<n;i++) 09 ___①___; 10 for (int i=0;i<n;i++) { 11 ___②___; 12 for (int j=___③___;j<=200;j++) 13 ___④___; 14 cout<<ans<<" "; 15 ___⑤___; 16 } 17 cout<<endl; 18 return 0; 19 }背景说明： 这是一种利用"值域计数数组"（桶计数）来避免暴力双重循环的技巧。由于数值范围只有0~200，可以用数组
c[]记录"到目前为止，每个具体数值分别出现过多少次"。对当前处理到的数d[i]，只要把c[]中所有比d[i]大的值对应的出现次数加总，就是"d[i]前面有多少个数比它大"，而不需要真的对每个数都去和前面所有数逐一比较。(1) ①处应该填（ B ）。 A．cin>>c[i] B．cin>>d[i] C．read(c[i]) D．read(d[i])
解析： 第一个循环的作用是把输入的N个原始数据依次读入数组d（题目中数组
d就是用来存放原始数列的），所以应当是 cin>>d[i]。答案为 B。(2) ②处应该填（ C ）。 A．ans++ B．c[i]=d[i] C．ans=0 D．c[i]++
解析： 每处理一个新的数d[i]之前，都要先把"统计其前面有多少数比它大"的计数器ans清零，即 ans=0，然后再重新累加。答案为 C。
(3) ③处应该填（ C ）。 A．d[i] B．c[i]+1 C．d[i]+1 D．c[i]
解析： 我们要统计的是"比d[i]大"的数的个数，所以内层遍历值域的循环应当从 d[i]+1（严格大于d[i]的最小可能取值）开始，一直遍历到200。答案为 C。
(4) ④处应该填（ D ）。 A．c[j]+=d[i] B．ans+=(c[j]==1) C．ans++ D．ans+=c[j]
解析：
c[j]表示数值j在d[i]之前已经出现过的次数，只要把内层循环遍历到的每一个j对应的c[j]累加进ans，就能统计出"比d[i]大的数一共出现了多少次"，即 ans+=c[j]。答案为 D。(5) ⑤处应该填（ A ）。 A．c[d[i]]++ B．c[i]++ C．ans=c[i] D．d[c[i]]++
解析： 处理完当前的d[i]、输出它对应的ans之后，需要把d[i]这个数值本身计入统计数组，供后面的数字在做统计时使用，也就是把值为d[i]的计数加一：c[d[i]]++。答案为 A。
第2题：求中位数（二分查找思想）
给定n个数 a₁,…,aₙ。求n个数字当中第l到第r个数字当中的中位数，我们可以用二分的经典思想来解决此问题。所谓中位数就是n个数中从小到大排序第⌊n/2⌋+1个数。
01 #include<bits/stdc++.h> 02 using namespace std; 03 const int MAXN=1e3+10; 04 int n,m,a[MAXN],maxn; 05 int main(){ 06 cin>>n>>m; 07 for(int i=1;i<=n;i++)cin>>a[i],maxn=max(maxn,a[i]); 08 while(m--){ 09 int lft,rgt;cin>>lft>>rgt; 10 int l=1,r=___①___; 11 while(___②___){ 12 int mid=___③___,s1=0,s2=0; 13 for(int i=lft;i<=rgt;i++){ 14 if(a[i]>mid)s1++; 15 if(a[i]<mid)s2++; 16 } 17 if(s1<=s2)___④___=mid; 18 else ___⑤___=mid; 19 }cout<<l; 20 } 21 return 0; 22 }背景说明： 这道题采用的是"二分答案"的思想，二分的对象不是数组下标，而是数值本身：在
[1, maxn+1]范围内猜一个候选值mid，统计区间[lft,rgt]内比mid大的数的个数s1、比mid小的数的个数s2；如果s1<=s2，说明mid偏大（比它大的数不太多），中位数应当不超过mid，于是把搜索范围的右边界往mid收缩；反之说明mid偏小，把左边界往mid推进。如此不断二分，最终l会收敛到真正的中位数。(1) ①处应该填（ B ）。 A．maxn B．maxn+1 C．maxn-1 D．n*2
解析： 二分查找的初始区间需要完全覆盖所有可能的答案取值。数组中出现过的最大值是
maxn，为了保证答案（哪怕恰好等于maxn）也落在开区间(l,r)内部（配合后面l+1<r的循环写法，需要初始时r严格大于所有可能的答案），右边界应设为 maxn+1。答案为 B。(2) ②处应该填（ D ）。 A．l+r<n B．l<=r C．l<r D．l+1<r
解析： 这是一种"左右边界相差1时才停止"的二分写法：当
l和r相邻（即l+1==r）时，就认为已经找到了唯一确定的答案（存放在l中），因此循环继续的条件应该是 l+1<r（左右边界之间还有间隔，需要继续二分）。答案为 D。(3) ③处应该填（ B ）。 A．l+r B．(l+r)>>1 C．r-l+1 D．r-l
解析： mid应当是l和r的中间值，标准写法为
(l+r)>>1（即(l+r)/2，用位运算右移实现整除2）。答案为 B。(4) ④处应该填（ B ）。 A．l B．r C．lft D．rgt
解析： 当
s1<=s2（比mid大的数不多于比mid小的数）时，说明真正的中位数不会比mid更大，应当把搜索范围的右边界收缩到mid，即 r=mid。答案为 B。(5) ⑤处应该填（ A ）。 A．l B．r C．lft D．rgt
解析： 否则（
s1>s2，比mid大的数偏多），说明mid偏小，真正的中位数应该比mid更大，应当把搜索范围的左边界推进到mid，即 l=mid。答案为 A。
附：全部答案速查表
一、单项选择题： 1-A 2-D 3-A 4-B 5-B 6-B 7-D 8-D 9-B 10-D 11-B 12-B 13-A 14-B 15-C
二、阅读程序：
- 第1题（字符匹配计数）：(1)× (2)√ (3)× (4)√ (5)B (6)B
- 第2题（差分数组）：(1)× (2)× (3)× (4)√ (5)C (6)A
- 第3题（值传递/引用传递/指针）：(1)× (2)× (3)× (4)√ (5)C (6)A
三、完善程序：
- 第1题（统计前面比它大的数）：①B ②C ③C ④D ⑤A
- 第2题（求中位数）：①B ②D ③B ④B ⑤A
- 1
冀公网安备13098402000493号