夜雨聆风一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个 正确选项）
每个不同的二进制数可以表示一位学生，现要用二进制数来表示 1200 位学生，至少需要二进制数的位数是（ ） A.11 B. 10 C. 12 D.13 若有如下程序段，其中 s、x、y、z 均已定义为int 类型变量，且 x、z 均已赋值（z大于0）。则与下面程序段修改 s 值的功能等价的赋 值语句是（ ）。 s = X;for(y=z;y>= 1;y--){s=s + 1;}A. s = y + z; B. s = x + y; C. s = s + z; D.s = x + z; 已知有序表（13,18,24,35,47,50,62,83,90,115,134），当折半查 找值为90的元素时，查找成功的比较次数为（ ）。 A.4 B. 5 C. 3 D.2 已知大写字母 A 的 ASCII 编码为 65（十进制），则大写字母 J 的 十进制 ASCII 编码为( ) A.71 B. 72 C. 73 D.74 设x=true ，y=true ，z=false ，以下逻辑表达式值为真的是（ ）。 A.(x ∨ y) Λ z B. x Λ (z ∨ y) Λ z C.(x ∨ y) Λ (x ∨ z) D.(y ∨ z) Λ x Λ z 一个二叉搜索树前序遍历的结果为 7、2、1、5、13、9 ，这棵树 的根的左子树有多少个节点？（）。 A.2 B. 5 C. 4 D.3 某算法计算时间表示为递推关系式：T (N) = N + T( N/2 ),则该算法时 间复杂度为( )。 A.$O(N^2 )$ B. $O(Nlog N )$ C. $O(N ) $ $D.O(1) $ 共9个互不相同的数，它们的最大公约数是2021 的一个大于1的因 子(6有2、3、6这三个大于1的因子，因子可以包含自身)，且这9个数 的和小于等于2021，则这9个数的和是多少?( ) A.1849 B. 1935 C. 2021 D.1927 一个 n 个顶点的强连通图最少有几条边( )。 A.n B. n + 1 C. n − 1 D. n × (n − 1) 小帅计划展出 10 幅不同的画，其中 1 幅水彩画、4 幅油画、5 幅 国画，排成一行陈列，要求同一品种的画必须连在一起，并且水彩画不放在两端，那么不同的陈列方式有( )种。 A.5760 B. 2880 C. 17280 D.8640 在一个图中，所有顶点的度数之和等于所有边数的( )倍。 A.2 B. 4 C. 1 D.3 6个人分乘两辆不同的汽车，每辆车最多坐 4人，则不同的乘车方法数为( )。 A.40 B. 50 C. 70 D.60 设 G 是有 6 个结点的完全图，要得到一棵生成树，需要从 G 中删 去（ ）条边。 A.6 B. 9 C. 10 D.15 8颗子弹，编号为 1、2、3、4、5、6、7、8，从编号 1 开始按序嵌入弹夹，以下有哪个不是正常的打出子弹的次序（ ） A.87654321 B. 32154876 C. 32164587 D.12345678 某公司派赵钱孙李周五人出国学习，选派条件是： 若赵去，钱也去； 李、周两人必有一人去； 如周去，则赵、钱也同去; 孙李二人同去或同不去 如何选他们出国?（ ） A.孙赵周去 B. 李周孙去 C.赵钱周去 D.钱孙去
二、阅读程序（程序输入不超过数组或字符串定义的 范围；判断题正 确填 T，错误填 F；除特殊说明外， 判断题1.5 分，选择题 3 分，共 计 40 分）
阅读下面程序，完成第16~21题。
#include#includeusing namespace std;intmain(){int t[256];char s[10];int i;scanf(”%s”, s);for (i = 0; i < 256; i++) t[i] = 0;for (i = 0; i < strlen(s); i++) t[s[i]]++;for (i = 0; i < strlen(s); i++)if (t[s[i]] == 1) {cout << s[i] << endl;return 0;}cout << ”no” << endl;return 0;}
程序会将读入的字符串中出现次数等于 1 的字符依次输出。（ ） 将程序中的 for (i = 0; i < 256; i++) t[i] = 0; 删掉可能会影响程序 的正确性。（ ） 当程序读入字符串的内容是 "xyzxyw" 时，程序的输出结果是 w 。 （ ） 对于一组输入数据 "abc?ac" ，如果希望程序的输出结果为 b ，则 ? 处应替换为 b 。（ ） 若输入的字符串中 a 到 g 这 7 种字符均至少出现一次，如果希望输出结果为 no ，则输入的字符串长度至少为14。（ ） 这个程序最多正确输入并处理长度为( )的字符串 s 。
A.256 B. 10 C. 9 D.11
阅读下面程序，完成第 22~27 题
#includeusing namespace std;const int MAXN = 100;int arr[MAXN];boolBinarysearch(int n, int target){int left=0, right=n-1;while (left <= right) {int middle = (left + right) / 2;if(arr[middle]> n;for (int i=0; i>arr[i];sort(arr,arr+n);//(1)将arr数组中的元素从小到大排序cin>> m;for (int i= 0; i < m; i++) {int target;cin>>target;if(Binarysearch(n,target))cout<<”YEs”<<endl;else cout<<”No”<<endl;}return 0;}
22.该算法的时间复杂度是 O(mlog n )。（不考虑(1)的排序）（ ）。
23.将 while (left <= right) 改成 while(left < right) ，其他地方不做 改动，对程序最终的输出结果没有影响。（ ）
24.将 sort(arr, arr + n); 改成把 arr 数组中的元素从大到小排序的代码， 其他地方不做改动，对程序最终的输出结果没有影响。（ ）
25.将 int middle = (left + right) / 2; 改成下列选项中的哪一项，对 于程序的运行没有影响。（ ）
A.int middle = (left + right) >> 1;
B. int middle = (left + right) << 1;
C. int middle = (left + right) > 1;
D.int middle = (left + right) < 1;
26.若给定 n 和 arr 数组，在最好情况下，函数 BinarySearch 中的 while 循环需要被执行（ ）次。
A.n B. m C. m×⌈log_2 n⌉ $ D.$m×⌊log_2 n⌋ $
27.（4分）若输入如下数据：
5
1 5 2 4 3
3
2 5 6
则输出结果为(用空格表示换行)：（ ）。
A.YES YES YES B. YES NO YES C. YES YES NO D.NO NO NO
阅读下面程序，完成第 28~33 题。
#includeusing namespace std;int w[35000],d[35000],dp[35000];intmain(){int n, m;scanf(”%d%d”, &n, &m);for (int i = 1; i <= n; i++)scanf(”%d%d”, &w[i], &d[i]);for (int i = 1; i <= n; i++) {for (int j = m; j >= w[i]; j--) {dp[j] = max(dp[j],dp[j-w[i]] + d[i]);}}printf(”%d\n”, dp[m]);return 0;}
上述代码中，双重循环里循环变量 j 的枚举顺序改为从 w[i] 到 m， 输出结果一定不变。（ ） 上述代码中，双重循环中变量 i 的枚举顺序改为从 n 到 1，输出结 果一定不变。（ ） 若输入数据中，1≤n≤30000, 1≤m≤30000, 1≤w[i]≤30000, 1≤d[i] ≤30000,则所求答案一定没有溢出。（ ） 当输入为：
4 6
1 4
2 6
3 12
2 7
输出为（ ）
A.17 B.28 C.29 D.23
（4分）若输入数据中，1 ≤ n ≤ 30000, 1 ≤ m ≤ 30000, 1 ≤ w[i] ≤ 30000,下列给出的 d[i]的范围，哪个选项所求答案有可能会超出 INT 的范围（ ） A.1 ≤ d[i] ≤ 100 B. 1 ≤ d[i] ≤ 1000 C. 1 ≤ d[i] ≤ 10000 D.1 ≤ d[i] ≤ 100000 上述代码的时间复杂度为（ ） A.O(n) B. $O(n^2m)$ C. O(nm) D.$O(nm^2 ) $
三、完善程序（单选题，每小题3分，共计30分）
阅读下面题目，完成第 34∼38 题。
题目描述
在二维平面内有若干个点，每个点的视野价值定义为其左下方的点的数目，即$ val_i=∑_j[x_j<x_i]and[y_j < y_i]$，求出每个点的视野价值并输出最具有视野价值的点的编号，如果有多个这样的点，输出其中最大的编号。
输入说明：
第一行一个正整数 n ，表示二维平面中点的个数。 接下来 n 行，每行两个数，表示编号为 i 的点的坐标。
输出说明 :
第一行 n 个正整数，表示编号为 i 的点的视野价值。 第二行一个正整数，表示视野价值最高的点的编号，如果有多个视野价值相同的点，则输出编号最大的那个。
样例输入
52 33 21 13 55 3
样例输出1 1 0 2 25
请补全下面的代码。
#includeusing namespace std;const int N=100;int x[N],y[N],f[N],n, max_f, ans;intmain() {cin >> n;for (int i=1; i<=n; i++) cin>>x[i]>>y[i];for (int i=1;i<= n; i++) {f[i]= ①;for (int j= 1; j <= n; j++) {if(x[j]<x[i]&&②)③;}if(④){max_f = f[i];⑤;}}for(int i=1;i<=n; i++) cout<<f[i]<< ” ”;cout << endl<< ans << endl;return 0;}
34.①处应填( )
A.0 B. 1 C. i D.INT_MAX
35.②处应填( )
A.y[j]<=y[i] B. y[j]y[i] D.y[j]>=y[i]
36.③处应填( )
A.ans=i B. f[i]++ C.f[i]-- D.ans++
37.④处应填( )
A.(f[0]>max_f) B. (f[i]>=max_f)
C.(f[i]<max_f) D.(f[i]<=max_f)
38.⑤处应填( )A
A.ans++ B. ans+=max_f C. ans=i D.ans= max_f
阅读下面题目，完成第 39~43 题。
题目描述
小帅的幼儿园有 n 个小朋友，在一次升旗仪式中，共有 n 个可以上场的小朋友，现在共需要 m 个小朋友来组成仪仗队，请你列举出所有可能的仪仗队，并按照字典序进行输出。
输入说明输入共一行，两个正整数 n, m，分别表示能上场的小朋友的数目和仪仗队的人数。
输出说明输出有若干行，每一行有 m 个数，表示一种可能的仪仗队组成形式， 并按照字典序输出。
样例输入3 2
样例输出
1 21 32 12 33 13 2
请补全下面的代码
#includeusing namespace std;const int N = 25;int n, m,data[N];bool flag,used[N];intmain(){cin>>n>>m;memset(used, false, sizeof(used));for (int i = 1; i <= m; ++i) {data[i] = i;used[i]= true;}flag = true;while (flag) {for (int i = 1; i <= m - 1; i++) cout <= 1; i--){②for (int j= data[i] + 1; j <= n; j++) {if (!used[j]) {used[j] = true;data[i]=③;flag = true;break;}}if (flag){for (int k=i+ 1;k <= m; k++){for (int j= 1; j <= ④; j++) {if (!used[i]){data[k]=j;used[j]=true;break;}}}⑤;}}}return 0;}
39.① 处应填( )A.false B. true C. 1 D.-1
40.② 处应填( )A.used[i]= true B. data[i]=i C. used[data[i]]= true D.used[data[i]]= false
41.③ 处应填( )A.j B. i C.true D.false
42.④ 处应填( )A.n B. m C. i D.j
43.⑤ 处应填( )A.return 0 B. exit C. continue D.break
答案速览
1~5 ADDDC 6~10 DCBAA11~15 ABCCC 16~20 FTFFT21~25 CTFFA
26~30 BCFTT 31~35 DDCAB 36~40 BBCAD 41~43 AAD
解析部分：
模拟1
A。2 10 < 1200 < 2 11 D。考察程序设计基础知识。先将 s 赋值为 x ；再循环 z 次， 每次给 s 累加 1，相当于给 s 一共累加了 z。总体看来，是将 s 赋值为 x + z。 D。第一次比较的元素为 50，第二次比较的元素为 90。 D。ASCII 计算。 C。x∣∣y = true, x∣∣z == true, true&&true = true。 D。二叉搜索树根节点的左子树中所有节点的权值小于根节点 的权值，前序遍历序列的第一个节点为根节点，故左子树的大 小为 3。 + + ... = N(1 + + + ...) = 2N 向上选 nlogn C 。$T(N) = N +N/2+N/4+……=N(1+1/2+1/4+……)=2N$,时间复杂度去掉系数。 B。2021 有两个因数: 43 和 47，由最大公约数的性质可知， 若其因数为 x ，则和最小的 9 个数字为: x, 2x, 3x, 4x, 5x, 6x, 7x, 8x, 9x。代入运算可知答案为 1935。 A。边数最少的强连通图即形成一个环的时候。此时边数最小， 为 n。 A。因为同一品种的画只能放在一起，所以如果将所有同类型 的画先视为相同，有 2 种摆放方式， 在考虑每一个类型内部 的顺序，分别为, 1!, 4!, 5! 所以答案为：2*1! *4! *5! = 5760。 A。每一条边都会使得两个点的度数加一，所以度数和是边数 的两倍。 B。1）.分配方式一:2人+4人 从6人中选2人坐第一辆车，剩余4人自然坐第二辆车:方法数为$C_6^2$。 由于两辆车不同，“第一辆2人、第二辆4人"与“第一辆4人、第二辆2人"是两种不同方案，因此需乘以2·计算:2x$C_6^2$=2x15=30。 2）.分配方式二:3人+3人 ·从6人中选3人坐第一辆车，剩余3人坐第二辆车:方法数为$C_6^3$。 注意:此时“第一辆3人、第二辆3人”与“第一辆3人、第二辆3人”是同一种分配(因为交换后人数不变)，因此无需乘以2。 计算:$C_6^3$=20. C。完全图具（5*6）/2=15 条边，树有 6−1=5 条边，所以需。要删去 15−5=10 条边就可以得到一颗生成树。 C。嵌入弹夹相当于入栈，打出子弹相当于出栈。 C。使用排除法。孙赵去或赵钱周去。 F。程序会将读入的字符串中出现次数等于 1 的第一个字符 T。如果删掉这部分语句的话，会导致数组 t 中的元素不一定 初始化为 0，导致最终结果出错。 F。 F。 T。最短的符合要求的字符串为 a 到 g 每个字符出现两次，总 长度为 7 × 2 = 14。 C。【个人认为选B】数组 s 的长度为 10，最后一位需要保存 \0 ，因此数组 s 能正确输入并处理的最大长度为 10 − 1 = 9。 T。代码显然是二分查找。 F。有 left == right 时恰好是关键字所在位置这一情况。 F。如果是从大到小排序，15 行和 17 行的两个 if 语句也要反 过来。 A。考察位运算基本知识。 B。每次进循环第一次就找到，所以是总共 m 次。 C。查找序列中是否含有带查询元素。 F。若更改则变为完全背包，显然不正确。 T。容易知道物品的枚举顺序没有影响。 T。30000*30000<=INT_MAX ，不会溢出。 D。 D。判断方法同上。 C。复杂度上限决定于枚举物品及体积的循环，易知答案为 O(nm)。
34~38 题 通过枚举的方式计算每个点的视野价值，并且将每个点的视野价值与全局最大值进行判断。要注意的是题目中提出了在视野价值相 同的情况下选择编号大的点，所以代码中是从小到大枚举点，并 在 f[i] 与 max_f 相等时也进行答案的更新。
A。 B。 B。 B。 C。
39~43 题 这段代码的主要原理是通过一个已经有的排列，推断出该排列在字典序中的下一个排列。操作方法很简单：假设当前排列中 的第 i 个的值为 data[i] ，那么就倒着寻找第一个可以使 data[i]变大的下标， 设为k，令 data[k] 变成一个更大的数字，这样就可以使得字典序增大。同时为了保证这是在字典序上直接与当前排 列相邻的排列，我们需要让 data[k+1..m] 这部分构成的序列字典序最小（在不修改 data[1..k-1] 的情况下）。所以我们需要重新对其值进行分配，也就是代码中 if(flag) 分支的部分。
A。 D。 A。 A。 D。