# [2024笔试] CSP - J考前刷题 ## A. CSP-J 模拟1 ## 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项) 1. 在标准ASCII码表中，已知英文字母Z的ASCII码十进制表示是90，那么英文字 母B的ASCII码二进制表示是（ )。 {{ select(1) }} - 01000001 - 01000010 - 01000011 - 01000000 2.以下关于CSP与NOIP的描述正确的是（ ) {{ select(2) }} - A.CSP属于非专业认证，只有在校生才能参加 - B.CSP是中国电子学会举办的程序设计竞赛 - C.CSP和NOIP毫无关系，没参加CSP也可以直接参加 NOIP - D.CSP和NOIP都是CCF旗下的程序设计赛事 3.以下不能用作C++程序中的标识符的是（ )。 {{ select(3) }} - A.private - B.friends - C.news - D.pascal 4. NOI复赛测评机所用的 Linux系统属于( )。 {{ select(4) }} - A.UML - B.IDE - C.OS - D.Database 5. 如果65536种颜色用二进制编码来表示，至少需要( ）个二进制位。 {{ select(5) }} - A.16 - B.8 - C.12 - D.10 6.搜索算法中的BFS算法经常用到的数据结构是（ )。 {{ select(6) }} - A.堆 - B.栈 - C.链表 - D.队列 7.在已经从小到大排好序的n元素单向链表中查询是否存在关键字为k的元素，最坏 情况下运行的时间复杂度是（ ). {{ select(7) }} - A.O(logn) - B.O(n) - C.O(n) - D.O(nlogn) 8.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（) {{ select(8) }} - A.归并排序 - B.快速排序 - C.冒泡排序 - D.桶排序 9.关于计算机网络，下面的说法中正确的是（）。 {{ select(9) }} - A.现在的计算机必须连接到互联网才能正常运行 - B.192.168.0.1是A类IP地址 - C.互联网的诞生用到了现代计算机技术和现代通信技术 - D.接入互联网的计算机的IP地址已经全部升级到了IPv6地址 10. 将(2,6,10，17)分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x)。( )，将不会产生冲突，其中ab表示a除以b的余数，sqrt表示开平方，floor表示向下取整。 {{ select(10) }} - A.×%11 - B.x%11 - C.2×%11 - D.floor(sqrt(x))%11 11.现在有一个十六进制数27，它等于二进制数的（ )。 {{ select(11) }} - A.100011 - B.100101 - C.100111 - D.100011 12.以下逻辑表达式中，不管A、B如何取值，恒为假的是（ )。 {{ select(12) }} - A.(-AVB)A(AVB)AA - B.((-AVB)V(AV-B))AB - C.AA((-AVB)V(AV-B))A-A - D.((-AVB)V(AV-B))AAA-B 13.某二叉树有16个结点都同时有左孩子结点和右孩子结点，则该二叉树中的叶子结点数是（ ）个。 {{ select(13) }} - A.19 - B.17 - C.18 - D.16 14.现有16张不同的卡片，其中红、黄、蓝、绿色卡片各4张。从中任取3张，要求红 色最多有1张并且3张卡片不能是同一种颜色，不同的取法组合共有（）种。 {{ select(14) }} - A.232 - B.472 - C.256 - D.484 15.有8个结点的非连通无向图最多有( ）条边 {{ select(15) }} - A.8 - B.7 - C.21 - D.49 ## 二、阅读程序（程序输入不超过数组或字符串定义的范围，判断题正确填√，错误填× ### 除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分） #### (1) ```c++ #include using namespace std; int gcd(int a, int b){ int tmp; if(b) tmp = a%b; else return a; while(tmp)f a =b; b = tmp; tmp = a%b; return b; } int lcm(int a, int b)[ return a/gcd(a,b)*b; } int main(){ int a,b; cin >> a >> b; cout << gcd(a, b) << endl; return 0; } ``` ### 判断题 16. 若输入`0 2024`，则输出结果为0。 (） {{ select(16) }} - true - false 18. 将第5行中的 `if(b)` 改为`if(0!=b)` ，程序的运行结果不会改变。 (） {{ select(17) }} - true - false 20. 若输入2.4 4.8，则输出错误。 () {{ select(18) }} - true - false 22. 将第15行 `return a/gcd(a，b)*b` 替换成 `return a*b/gcd(a，b)` ，程序的运行结果不会改变。 ） {{ select(19) }} - true - false ### 选择题 20. 若输入数据为`20244204 12348`，则输出为（ )。. {{ select(20) }} - A.18 - B.36 - C.12 - D.24 21. 若将第20行`cout << gcd(a，b)<< endl`替换成`cout<< lcm(a，b)<< endl`， 输入数据为`20244204 12348`，则输出为()。 {{ select(21) }} - A.6,943,761,972 - B.程序出错，无输出 - C.3,471,880,986 - D.某个负数 #### (2) ```C++ #include using namespace std; int main(){ char s[128] = 10; cin.getline(s,128); for(int i = 0; i< strlen(s); ++i){ if(s[i]>= 65 88 s[i] <= 90)[ if(s[i]== 90){ s[i]= 65; }else{ s[i]+= 1; } s[i] ^=’ ’; } cout << s << endl; return 0; } ``` ### 判断题 22. 输入一个长度大于128的字符串，程序的输出一定会出错。() {{ select(22) }} - true - false 24. 将第6行cin.getline(s，128)更换为getline(cin，s)，程序的运行结果不（) {{ select(23) }} - true - false 26. 将第13行s[i]^='‘更换为s[i]^=32，程序的运行结果不变。 () {{ select(24) }} - true - false 28. 将第9行if(s[i]==90)更换为if(slil==‘z'）。程序的运行结果不变() {{ select(25) }} - true - false ### 选择题 26. 若输入字符串s为`CSPjs2024`，则输出为（）。 {{ select(26) }} - A.dtqjs2024 - B.cspjs2024 - C.DTQjs2024 - D.CSPjs2024 27.若输出`bcdea`，则输入字符串s为( )。 {{ select(27) }} - A.BCDEA - B.ABCDZ - C.abcde - D.bcdez #### (3) ```C++ #include using namespace std; int used[20],a[20],n; long long ret=0; bool flag; void dfs(int x) { int i; if(x>n) { flag=1; for(i=l;ic=n;i++) { if(a[i]+i > n+2) { flag=0; break; } } if(flag) ret++; return; } for(i=1l;ic=n;i++) { if(used[i]==0) { used[i]=1, a[x]=i; dfs(x+1); used[i]=0, a[x]=0; } } } int main() { cin>>n; cout< using namespace std; int a[33],cnt; int main() { int n,sum,X; cin>>n; cnt=0; ①; while(x>0) { a[②]=x%2; ③； } sum=0； for(int i=1;④;i++) if(a[i]==1) ⑤; cout< using namespace std; int n,i,j,k,ans; int a[105][105],vis[105][105]；//a 表示棋盘，vis统计点是否走过 int dx[4]=f-1,1,0,0),dy[4]=[0,0,1,-1]; void dfs(int x,int y,int step) { ans = ①; for(int i=0;i<4;i++) { int tx=x,ty=y,s=0; while(tx+dx[i]>0 and tx+dx[i]<=nand ty+dy[i]>0 and ty+dy[i]<=n) { tx+=dx[i]; ty+=dy[i]; S++； if(②) break; } if(tx>0 and tx<=n and ty>0 and ty<=n and vis[tx][ty]==0 and a[tx][ty]==0 and s!=1) { vis[tx][ty]=1; dfs(tx,ty,③); ④; } } int main() { int x,y,i,j; cin>>n>>x>>y; for(i=1;ic=n;i++) { for(j=1;j<=n;j++) { cin>>a[i][j]; } } ⑤; dfs(x,y,0); cout< #include using namespace std; char s1[1005], s2[1005]; int a[1005],b[1005], c[1005]; int main() { int la,lb,lc; scanf("%s",s1); scanf("%s",s2); la = strlen(s1); lb = strlen(s2); lc = max(la,lb)+ 1; for(int i=0;i0) lc--; for(int i=lc;i>0;i--) printf("%d",c[i]); return 0; } ``` ### 判断题 16. 将第2行代码改为#include，程序的运行结果不会改变 ( ) {{ select(16) }} - true - false 18. 将第9~10行代码改为cin>>s1>>s2；，程序的运行结果不会改变。 ( ) {{ select(17) }} - true - false 20. 若输入两个都超过1005位长的正整数，则程序一定会出错且无输出。 ( ) {{ select(18) }} - true - false 22. 在输入00的情况下，将第24行代码中的1c>0去掉，程序的运行结果不会() {{ select(19) }} - true - false ### 选择题 20. 若输入数据为1024 1000，则输出为（ )。{{ select(20) }} - A.24 - B.2024 - C.1024 - D.1000 21.若输入数据为1-1，则输出为（ )。{{ select(21) }} - A.1 - B.0 - C.-1 - D.以上都不是 (2) ```C++ #include using namespace std; const int MAXN = 10005; int n, a[MAXN], b[MAXN] ; void mergesort(int *a, int l, int r) { int i,j,cnt,mid; if (1 == r) return; mid = (l + r)/2; mergesort(a, l, mid); mergesort(a, mid + 1, r); i =l,j=mid +1,cnt= 0; while (i c= mid 66 j <= r) { if (a[i] <= alj]) b[++cnt]= a[i++]; else b[++cnt]= a[j++]; } while (i <= mid) b[++cnt]s a[i++]; while (j<= r) b[++cnt]= alj++]; for(i =l; i co r; i++) a[i] =b[i-l+1]; } int main(void) { cin >> n; for (int i =1; i <= n; i++) cin >> a[i]; mergesort(a,1, n); for (int i= 1; i<= n; i++) cout << a[i] << (i == n? \n':'’); return 0; } ``` ### 判断题 22. 该排序算法用到的是不稳定的排序算法。 ( ）{{ select(22) }} - true - false 24. 将第10行改为mid=+r>>1；，程序的输出结果不变。 ( ）{{ select(23) }} - true - false 26. 该排序算法用到了分治的思想。 ( ）{{ select(24) }} - true - false 28. 第35行代码用到的三目运算符处理代码可以用等价的条件语句来写。 (){{ select(25) }} - true - false ### 选择题 26. 在最坏情况下，该算法的时间复杂度和下面哪个算法相当？（）{{ select(26) }} - A.插入排序 - B.选择排序 - C.堆排序 - D.快速排序 27. 若输出2 3 5 7 8，则输入可能为（ )。{{ select(27) }} - A.1 2 4 6 7 - B.87 5 2 3 - C.3 4 2 5 7 - D.8 2 3 4 5 (3) ```C++ #include using namespace std; int t,x[100],a[100]; void dfs(int d,int i,int n) { if(n==1) { for(int k=0;k>n; for(int i=n;i>1;i--) if(n%i==0) x[t++]=i; dfs(0,0,n); return 0; } ``` ### 判断题 28. 该程序的作用是对n进行质因数分解并从小到大依次打印。(){{ select(28) }} - true - false 30. 将第9行代码printf（"%4d"，a［k］）；中的4去掉，程序输出不变。(){{ select(29) }} - true - false 32. 第24~26行的作用是求出n的所有因子。(){{ select(30) }} - true - false 34. 程序运行过程中，若输入n为0或者负数，程序一定会打印错误，崩溃退出(){{ select(31) }} - true - false ### 选择题 32. 若输入6，则输出为（ )。{{ select(32) }} - A.6 3 2 - B.72 36 2 - C.6 2 3 - D.72 2 36 33. 若输入n=1，那么输出结果可能是（）。 {{ select(32) }} - A. 2 - B. 1 - C.0 - D.什么也不输出 34. （4分）若输入2024，则输出有（ ）行。 {{ select(33) }} - A.18 - B.20 - C.21 - D.19 ## 三、完善程序（单选题，每小题3分，共计30分) （1）扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷 （称为地雷格），其他格子不含地雷（称为非地雷格）。玩家翻开一个非地雷格时，该 格子中将会出现一个数字，提示周围格子中有多少个是地雷格。玩家的目标是在不 翻出任何地雷格的条件下，找出所有的非地雷格。请将程序补充完整。 现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。 注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下这8个 方向上与之直接相邻的格子。 输入格式： 第1行是用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符*表示相应格子是地雷格，字符?表示相应格子是 非地雷 格。相邻字符之间无分隔符。 输出格式： 输出文件包含n行，每行m个字符，描述整个雷区。用*表示地雷格，用周围 的地雷个数表示非地雷格。相邻字符之间无分隔符。 输入样例： ``` 33 *?? ?? ?*? ``` 输出样例： ``` *10 221 1*1 ``` ```c++ #include using namespace std; const int dx[]= (1, 1,1,0,0,-1，-1，-1]; const int dy[] = (-1,0,1,-1,1,-1,0,1]； char g[101][101]; int main() { int n,m,cnt; cin>>n>>m; for(int i=0;icn;i++) for(int j=0;j>g[i][j]; for(int i=0;icn;i++){ for(int j=0;j using namespace std; int hcb[10]=f6,2,5,5,4,5,6,3,7，6]； int n; int matches(int num) { int i,k=0; for(i=num;i!=0;①) ②; if(③) k+=hcb[0]; return k; } int main() { int i,j,count; ④; cin>>n; for(i=0;i<=1000;i++） for(j=0;j<=1000;j++） if(⑤) count++； cout< 内存 > 高速缓存 >U盘 - B.高速缓存 > 内存 > 硬盘 >U 盘 - C.高速缓存 > 硬盘 > 内存>U盘 - D.U盘 > 硬盘 > 内存 > 高速缓存 2. 杨辉三角形和( ）算法的思想最接近。 {{ select(2) }} - A.贪心 - B.二分 - C.DFS - D.递推 3.下列属于输入设备的是（) {{ select(3) }} - A.显示器 - B.麦克风 - C.音箱 - D.打印机 4.小写字母a的ASCII码值为97，小写字母z的ASCII码值是（) {{ select(4) }} - A.120 - B.119 - C.122 - D.121 5. IP地址是每台上网的计算机所必需的，下列IP地址中可以作为合法主机址的是( )。 {{ select(5) }} - A.225.225.225.225 - B.200.256.192.8 - C.192.168.1.12 - D.0.0.0.0 6.下面哪个可以用作C++程序中的标识符？（) {{ select(6) }} - A.default - B.private - C.this - D.them 7.快速排序在最坏情况下运行的时间复杂度是（)。 {{ select(7) }} - A. O(logn) - B.O(n) - C.O(nm) - D.O(nlogn) 8. 字符串 a="98"，字符串 b="123”，使用 strcmp 函数，比较两者大小的结果是 ( )。 {{ select(8) }} - A.a大 - B.b大 - C.一样大 - D.无法判断 9.关于计算机网络，下面的说法哪个是正确的？() {{ select(9) }} - A.现在的计算机互联网是俄罗斯人发明的 - B.计算机网络拓扑结构只包括星形、流水线型和环形 - C. TCP/IP是因特网的最基本的协议 - D.SMTP属于物理层协议 10.关于信息安全与网络道德，下列做法正确的是( )。 {{ select(10) }} - A.确认环境安全后再输入支付密码 - B.随意点击不熟悉的电子邮件中的链接 - C.未经许可将其他人的私密照片和视频上传到互联网上 - D.在微信里随意转发未经证实的信息 11.现在有一个十进制算式13*64+7，它等于二进制数的（) {{ select(11) }} - A.1100100111 . - B.1101001111 - C.1101000111 - D.1111101101 12.逻辑表达式A=true，B=C=D=false，则逻辑表达式取值为真的是() {{ select(12) }} - A.(AAB)V(CADV-A) - B.-((AABVC)AD) - C.AA(BVCVD)VD - D.(AV(CVD))AB 13.某二叉树树根层次为0，则有64个结点的完全二叉树的高度是（) {{ select(13) }} - A.9 - B.8 - C.7 - D.6 14.书架上同一格放5本书，A和B必须相邻.C和D必须不相邻，不同的放法共有()种。 {{ select(14) }} - A.24 - B.12 - C.18 - D.48 15. 字符串S="abcdefgh"的子串个数为() {{ select(15) }} - A.33 - B.35 。 - C.37 - D.36 ## 二、阅读程序（程序输入不超过数组或字符虫定义的范围，判断题正确填√、错误× 除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分) (1) ```c++ #include using namespace std; const int SIZE = 100007; int a[SIZE], b[SIZE]; int main() { int n, m, P, q, count=0, ret=0; cin >> n >> m; for (int i = 1; i c= n;i++) { cin >> p>> q; a[p]++; a[q+1]--; } for(int i = 1; i c= m;i++) { count += a[i]; ret += count; } cout << ret; return 0; } ``` 注：输入流中1 p q using namespace std; bool fun(int n) { int i=7; if(n==2 || n==3 l| n==5) return true; if(n==1|| n%2==0 1| n%3==0 || n%5==0) return false; while(i*i<=n) { if(n%i==0) return false; i+= 4； if(n%i==0） return false; i+=2; } return true; } int main() { int n,m; cin>>n>>m; if(fun(n) 8& fun(m) &8 fun(n+m+1)) cout<<"YES"< using namespace std; int main() { stack s; char a[1005]; int back,front,result; cout <<"Input:"; cin >> a; for (int i = 0;i < strlen(a); i++) { if (a[i] >= '0' && a[i] <='9') s.push(a[i] -'0'); else { back = s.top(); s.pop(); front = s.top(); s.pop(); if (a[i]=='+') result = front + back; else if(a[i] =='-') result = front - back; else if (a[i] =='*') result = front * back; else if(a[i]=='/') result = front / back; else if(a[i]=='%') result = front % back; s.push(result); } } cout << "Output:"<< s.top() << endl; return 0; } ``` ### 判断题 28.将第1行改为#include，程序的运行结果不变。() {{ select(28) }} - true - false 29.本程序用到了队列而不是栈的思想。() {{ select(29) }} - true - false 30.将第12行中的'0'替换为48，程序的运行结果不会改变。() {{ select(30) }} - true - false 31.如果输入的都是非零数字和加、减、乘、除四则运算符号，那么运行程序输出的值一定是正整数。 ( ) {{ select(31) }} - true - false ### 选择题 32.本题的主要思想是求（ ）表达式的值。 {{ select(32) }} - A.前缀 - B.后缀 - C.中缀 - D.逻辑 33.若输入234--，那么程序的输出结果是（ ） {{ select(33) }} - A.3。 - B.2 - C.1 - D.0 34.（4分）若输入数据为5432*%/，则输出是（)。 {{ select(34) }} - A.3 - B.2 - C.10 - D.0 ## 三、完善程序（单选题，每小题3分，共计30分） (1) 输入两个正整数n和m(1 using namespace std; const int MAXN = 15; bool flag, vis[MAXN]; int nm,i.j,k,a[MAXN]; int main() { cin>>n>>m; memset(vis,false,sizeof(vis)); for(i=1;i<=m;i++) { a[i]=i; vis[i]=true; } flag=true; while(flag) { for(1=1;i<=m-1;i++) cout << a[i]<" "; cout << a[m]<=1;i--) { } ②; for(j=ali]+1;jc=n;j++) { if(tvis[j]) { vis[j]=true; ③; flag=true; break; } } if(flag) { } for(k=i+1;k<=m;k++) { for(j=1;④;j++) { if(!vis[j]) { a[k]=j; fvis[j]=true; break; } } } ⑤; } return 0; } ``` 35.①处应填() {{ select(35) }} - A.flag = false - B.flag = true - C.vis[1]= false - D.vis[1]= true 36. ②处应填( )。 {{ select(36) }} - A.vis[i]= true - B.a[i]= i - C.vis[a[i]]= true - D.vis[a[i]]= false 37.③处应填() {{ select(37) }} - A.a[i]i - B.a[i]=j - C.a[i] = true - D.a[i] = false 38. 4处应填( ) {{ select(38) }} - A.j<=m - B.j<=k - C.j<=n - D.j<=i 39.⑤处应填( )。 {{ select(39) }} - A.exit - B.return 0 - C.continue - D.break （2） 求一个有向图中有多少个环并输出环的总数。 输入格式： 第1行为n，第2行为n个点的编号。 输出格式： 输出有向图的环的总数。 输入样例： ``` 10 7 1 4 3 2 5 9 8 0 6 ``` 输出样例： ``` 6 ``` 样例说明： a 0]=7,a[7]=8,a[8]=0,0,7,8)构成一个环；a[1]=1,1)构成一个环；a[2]=4,a[4]=2.(2,4)构成一个环；a[3]=3,(33构成一个环；a[5]=5,(5)构成一个环;a[6]=9,a[9]=6,(6,9)构成一个环。该有向图共有6个环。 ```C++ #includecbits/stdc++.h> using namespace std; int n,point[100]; bool vis[100]; int main() { int cnt; scanf("%d",Sn); for (int i = 0; ic n; ++i) { scanf("%d",①); ②; } cnt = 0; for (int i = 0; 1< n;++1) if (③) { for (int j=i;lvis[j];④) { vis[j] = true; } ⑤; } printf("%d", cnt); return 0; } ``` 40.①处应填（ )。 {{ select(40) }} - A.`&point` - B.`point + i` - C.`&point + i` - D.`point[i]` 41.②处应填（ )。 {{ select(41) }} - A.`vis[j]=false` - B.`vis[j] = true` - C.`vis[i]= true` - D.`vis[i]= false` 42.③处应填( )。 {{ select(42) }} - A.`!vis[i]` - B.`vis[i]` - C.`!vis[point[i]]` - D.`vis[point[i]]` 43.④处应填() {{ select(43) }} - A.`j =point[i]` - B.`j = point[j]` - C.`i=point[j]` - D.`i = point[i]` 44.⑤处应填（) {{ select(44) }} - A.`cnt=j+1` - B.`cnt=n-j` - C.`++cnt` - D.`cnt = n-i` --- ## D. CSP-J 模拟4 ## 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项） 1.正整数2024与1840的最大公约数是（ )。 {{ select(1) }} - A.46 - B.92 - C.44 - D.184 2. 十进制数28与二进制数10000001110000求和的结果是（ ) {{ select(2) }} - A.十进制数 8332 - B.十六进制数208A - C.二进制数100000000110 - D.八进制数20212 3. C++程序中，（25|6）^5的值是（ )。{{ select(3) }} - A.25 - B.26 - C.27 - D.28 4. 在数组 A[x]中，若存在（i A[j])，则称(A[i]，A[j])为数组A[x]的一个逆序对。对于序列(7,4.1,9,3,6,8,5)，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少4。{{ select(4) }} - A.1 - B.3 - C.6 - D.5 5.如果字符串s在字符串A中出现了，则字符串 s被称作字符串 A的子串。设字符串A ="players"，A的非空子串的数目是（ ) {{ select(5) }} - A.27 - B.29 - C.28 - D.30 6.以下哪种算法的主要框架不是非比较排序？(). {{ select(6) }} - A.计数排序 - B.堆排序 - C.基数排序 - D.桶排序 7.采用了倍增法的程序运行的时间复杂度是（ ) {{ select(7) }} - A.O(logn) - B.O(n) - C.O(n') - D.O(nlogn) 8. 将数组（9.33.5.18.71.3.52.851中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次 {{ select(8) }} - A.4 - B.5 - C.6 - D.7 9.关于计算机网络，下面的说法中哪个是正确的？（） {{ select(9) }} - A.计算机网络是一个管理信息系统 - B.计算机网络是一个管理数据系统 - C.计算机网络是一个在协议控制下的多机互联系统 - D.计算机网络是一个独立的操作系统 10.下列哪款软件不是操作系统软件的名字？（） {{ select(10) }} - A.安卓 - B.Windows 11 - C.华为鸿蒙 - D.ChatGPT 11. 下述选项中哪个不是算法描述的通用方法？( ) {{ select(11) }} - A.自然语言 - B.流程图 - C.人工智能 - D.伪代码 12.若A=True，B=False，C=True，D=False，以下逻辑运算表达式的运算结果为真的是( )。 {{ select(12) }} - A.(AAB)V(CADV-A) - B.((AAB)AC)A-B - C.(BVCVD)VDAA - D.(AA(DV-C)AB 13.一棵二叉树的高度为h，所有结点的度数都为0或2，则此树最少有（ ）个结点。 {{ select(13) }} - A.2'-1 - B.2h-1 - C.2h+1 - D.h+1 14.从12个人中选出5个人，其中甲、乙、丙必选的方法共有（ ）种。 {{ select(14) }} - A.60 - B.36 - C.72 - D.120 15.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ )倍。 {{ select(15) }} - A.1/2 - B.2 - C.1 - D.4 ## 二、阅读程序（程序输入不超过数组或字符串定义的范围：判断题正确填V，错误填x：除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分） (1) ```C++ #includecbits/stdc++.h> using namespace std; char change(char str) { if(str >='a' 8& str <='z') str -= 32; return str; } int main() { string S1, s2; cin >> S1 >> s2; int cnt = 0; for (int i = 0; i< s1.size(); i++) { for(int j= 0; j< s2.size(); j++) if (change(s1[i]) == change(s2[j])) cnt++; } cout << cnt; return 0; } ``` ### 判断题 16.将第1行头文件改为#includeciostream>，程序的运行结果不会改变。 ( ） {{ select(16) }} - true - false 17.将第5行中的'a'替换为97，程序的运行结果不会改变。 ( ) {{ select(17) }} - true - false 18.将第6行中的32替换为’’，程序的运行结果不会改变。 ( ) {{ select(18) }} - true - false 19.将第14行代码去掉，程序的运行结果不会改变。 () {{ select(19) }} - true - false ### 选择题 20.若输入数据为ABCDE AbCdE，则输出为( )。 {{ select(20) }} - A.3 - B.5 - C.2 - D.0 21.若输入数据为WorldYiwuAsiaShanghai ChinaHangzhouZhejiangJinhua，则输 出为（ )。 {{ select(21) }} - A.36 - B.40 - C.42 - D.44 (2) ```C++ #include using namespace std; int solve(int n,int m) { int i,sum; if(m==1) return 1; sum=0; for(i=1;i>n>>m; cout< using namespace std; const int MAXN = 2e5 + 5; int nums[MAXN]; int left_bound(int n, int target) { int left - 0. rightsn-1i while (left <= right) { int mid s (left + right) / 2; if(nums[mid] < target) left =mid + 1; else right -mid-1; } if(left < n && nums[left] && target) return Left; return -1; } int right_bound(int n, int target) { int left = 0, right =n-1; while (left <= right) { int mid = (left + right)/ 2; if(nums[mid] <= target) left = mid + 1; else right = mid-1; } if(right >= 0 66 nums[right] == target) return right; return -1; } int main() { int n, C; cin>>n>>c; for(int i = 0; ic n; ++i) cin>>nums[i]; sort(nums, nums + n); long long ans = 0; for(int i = 0; i< n; ++i) { int left s left_bound(n, nums[i] +c); int right = right_bound(n, nums[i] + c); if(left != -1) ans += right - left + 1; } cout<> 1 - D.mid = (left + right)%2 33.本程序的时间复杂度为( )。 {{ select(33) }} - A.O(logn) - B.O(n) - C.O(nm) - D.O(nlogn) 34.(4分)当输入 4 1 112 3 时，程序的输出结果为（ )。 {{ select(34) }} - A.1 - B.2 - C.3 - D.4 ## 三、完善程序（单选题，每小题3分，共计30分） （1）给定一棵树，输出树的根root、孩子结点最多的结点max以及它的孩子结点。 输入格式： 第1行输入n（结点数 100）和m（边数<200）。以下m行输入每行两个结点 x和y，表示y是x的孩子结点（xy 1000）。 输出格式： 第1行是树根root。第2行是孩子结点最多的结点max。第3行是max的孩子结点。 输入样例： 87 41 42 13 15 26 27 28 输出样例： 42 678 ```C++ #include using namespace std; int n,m,tree[105]= 0]; int main() { int i,x,y,root,maxroot,sum=0,j,Max=0; cin>>n>>m; for(i=1;i<=m;i++) { cin>>x>>y; ①; } for(i=1;i<=n;i++) //找出树的根 if(②) { root=i; ③; } for(i=1;ic=n;i++) //找孩子结点最多的结点 { sum=0; for(j=1;jc=n;j++) if(tree[j]==i) sum++; if(④) Max=sum;maxroot=i; } cout< Max` - D.`sum < Max` 39.⑤处应填（) {{ select(39) }} - A.`tree[i] != maxroot` - B.`tree[i] <= maxroot` - C.`tree[i] >= maxroot` - D.`tree[i] == maxroot` （2）快速排序是一种高效的排序算法，我们常用的STL 函数 sort 就是采用快速排序 思想实现的。如下代码是一个经典的快速排序过程，输入一个整数n，然后输入 个整数，程序会按照从小到大的顺序将所有整数进行排序并输出。请将程序补充 完整。 ```C++ #includecbits/stdc++.h> using namespace std; int a[1005]; void quickSort(int al], int begin, int end) { int i,j,tmp; if(begin >= end) return; ①； i = begin; j = end; while(i< j) { while(alj] > tmp) j--； while(②) i++； if(il= j) swap(a[i], alj]); } ③； ④； quickSort(a,i+1,end); } int main() { int n; cin>>n; for(int i=1;ic=n;i++) cin>>a[i]; for(int i=l;ic=n;i++) cout<= tmp && i < j` - B.`a[i] >= tmp && i > j` - C.`a[i] <= tmp && i > j` - D.`a[i] <= tmp && i < j` 42.③处应填（ )。 {{ select(42) }} - A.`swap(a[i],alj])` - B.`swap(a[begin],a[i])` - C.`swap(a[begin],a[j])` - D.`swap(a[begin],a[end])` 43.④处应填( )。 {{ select(43) }} - A.`quickSort(a,begin,i)` - B.`quicksort(a,begin,i-1)` - C.`quickSort(a,1,i)` - D.`quickSort(a,1,i-1)` 44. 5处应填( )。 {{ select(44) }} - A.`quickSort(a,1,n-1)` - B.`quickSort(a,0,n-1)` - C.`quickSort(a,1,n)` - D.`quickSort(a,0,n)` --- ## E. CSP-J 模拟5 ## 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项） 1. 十进制数2024的八进制表示是（ )。 {{ select(1) }} - A.3749 - B.3750 - C.3751 - D.3752 2.以下关于计算机协会竞赛的描述正确的是（)。 {{ select(2) }} - A.NOI国家集训队每年产生4名选手代表中国参加IOI - B.CSP-J/CSP-S是2018年开始举办的 - C.USACO晋级白金的选手可以直接参加 NOIP - D.ACSL 和NOIP都是CCF旗下的程序设计赛事 3.以下哪个可以用作C++程序中的变量名？（） {{ select(3) }} - A.public - B.loops - C.new - D.delete 4.以下哪个数据结构不属于线性结构？（）{{ select(4) }} - A.栈 - B.数组 - C.树 - D.链表 5.以下哪个属于STL 函数？（） {{ select(5) }} - A.main - B.sort - C.freopen - D.scanf 6.小明用递归的方法写了一个斐波那契数列的程序，在这里递归函数经常用到的数据 结构是( )。 {{ select(6) }} - A.树 - B.栈 - C.链表 - D.队列 7.堆排序程序运行的时间复杂度是（) {{ select(7) }} - A.O(logn) - B.O(n) - C.O(nm) - D.O(nlogn) 8.在下列排序算法中，( ）是稳定的排序算法。 {{ select(8) }} - A.归并排序 - B.快速排序 - C.选择排序 - D.拓扑排序 9. 一台32位操作系统的计算机运行C++，下面哪个说法是正确的？（） {{ select(9) }} - A.C++语言中的一个int类型的变量占8字节 - B.C++语言中的一个指针类型的变量占4字节 - C.C++语言中的一个bool类型的变量占2字节 - D.C++语言中的一个double类型的变量占4字节 10.设全集I=fa，b.c，d.e.fg.h)，集合BUA=fa，b,c,d,e,f，CnA=(c,d,e,~BNA=(a,d) 那么集合CnBDA为（)。 {{ select(10) }} - A.(c,e) - B.(d,c) - C.(e) - D. c,d,e 11. 在不大于19000的正整数中，与19000互质的正整数有( ）个。 {{ select(11) }} - A.9500 - B.9498 - C.9497 - D.9499 12.假设P=true，Q=false，R=true，S=true，逻辑运算表达式PAQVRAS的值是( )。 {{ select(12) }} - A.true - B. false - C.null - D. NIL 13.对于二叉树T，已知其前序遍历序列为1243576，中序遍历序列为4215 73 6. 则其后序遍历序列为( )。 {{ select(13) }} - A.4257631 - B.4275631 - C.4275361 - D.4723561 14.一个口袋内装有大小相同的7个白球和2个黑球，从口袋中取出3个球，使其中不 含黑球，有多少种取法？（） {{ select(14) }} - A.32 - B.35 - C.24 - D.56 15.在下图中，从顶点（ )出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。 {{ select(15) }} - A.B点 - B.A点 - C.E点 - D.C点 ![image](/file/267/CNNvlmJp9Go39obqh46lR.jpeg) ## 二、阅读程序（程序输入不超过数组或字符串定义的范围：判断题正确填V，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分） (1) ```C++ #include using namespace std; int a[100005]; bool judge(int x) { int i=2; if(x==0||x==1) return false; while( i <= floor(sqrt(x)) 88(×%i!=0)) i++; if(i> floor(sqrt(x))) return true; return false; } int inverted(int n) { int sum; sum = 0; while(n > 0) { sum = sum*10 + n%10; n /= 10; } return sum; } int main() { int m,n,k; bool flag; k=0; flag = false; cin >> m >> n; for(int i=m; i<=n; i++) if( judge(i) 88 judge(inverted(i))) { k++; a[k]= i; flag = true; } if(flag) { for(int i=1; ick; i++) cout << a[i] << ","; cout << a[k] << endl; } else cout<< "No"<< endl; return 0; } ``` ### 判断题 16.若去掉第6行，程序的输出结果不受任何影响 () {{ select(16) }} - true - false 17.若去掉第8行，程序的输出结果中的数字总数不变。 () {{ select(17) }} - true - false 18.程序的输出结果是一个从小到大排列的整数序列。 （) {{ select(18) }} - true - false 19.将第10行中的s.size()替换成s.length（），程序的运行结果不会改变。（) {{ select(19) }} - true - false ### 选择题 20.将第13行s.insert(k)替换成for(int izl;ic=6;i++)s.insert(i)，则输出 为( )。 {{ select(20) }} - A.1 2 3 4 5 6 - B.654321 - C.1236 54 - D.1-6随机分布值 21、将第 13 行 s.insert(k)替换成for(int i=l;icn7;i++) s.insert(i)，第20 行替换为int x=i+1，第21行替换为int y=i，则输出为（ )。 {{ select(21) }} - A.123456 - B.6 5432 1 - C.2 345671 - D.2 3 4 56 7 (2) ```C++ #includecbits/stdc++,h> using namespace std; int month[13]=f-1,31,28,31,30，31，30，31，31，30，31，30，311； int date,ans1,ans2,y,m,d; bool check1(int date) { char s[32]; sprintf(s, "%d", date); if(s[0]==s[7] 88 s[1]==s[6] 88 s[2]==s[5] 88 s[3]==s[4]) return true; return false; } bool check2(int date) { char s[32]; sprintf(s,"%d",date); if(s[0]==s[2] 88 s[0]==s[5] 68 s[0]==s[7] 88 s[1]==s[3] s[1]==s[4] 88 s[1]==s[6]) return true; return false; } int main() { cin>>date; y=date/10000; m=date/100%100; d=date%100； for(int i=y;;i++) if(1%400==0 1 (1%100!=0 88 1%4==0)) month[2]= 29; else month[2]= 28; int j=(i==y)?m:1; for(;j<=12;j++) { int k=(i==y 88 j==m)?d+1:1; for(;k<=month[j];k++) { int date=i*10000+j*100+k; if(check1(date) &8 ans1==0) ans1=date; if(check2(date)) return cout< using namespace std; const int MAXN = 100; bool Prime_Number_Judge(const int &num){ if (num <= 3) return num > 1; for (int i = 2; i < num; i++) if (num % i == 0) return false; return true; } int& Get_Number_Size(const int &num) { int digit = 0, val = num; while (val) { val /= 10; digit++; } return digit; } vectorc&Get_Digits(const int &num, vectorcint> &digits){ int vactor_val = 0; for(int num_size=Get_Number_Size(num);num_size>0;num_size--){ vactor_val = num %(int)pow(10.0, num_size); vactor_val = vactor_val/(int)pow(10.0,num_size-1); digits.push_back(vactor_val); } return digits; } vectorcint>8Get_K_Adjacent(const int 8num, vector6adjacent){ vectorkint> digists_number; char tmp[128], buf_tmp[128]; Get_Digits(num,digists_number); int digits = Get_Number_Size(num); for (int i = 0; i< digits; i++) { for (int j = 0; j buf; Get_K_Adjacent(i, buf); int sign = 1; for (int j =0; j < buf.size();j++) if(!Prime_Number_Judge(buf.at(j))) sign = 0; break; if (sign) count++; cout< using namespace std; int main() { int n,t,×,y; t=1, x=1, y=1; int v[505][505],p[505][505]; cin >> n; for(int i=1;i<=n;i++) for(int j=l;jc=n;j++) cin>>p[i][j]; printf("%d"，①); ②; while(③) { if(y+1 <= n) { ++t; y++; v[x][y]=1； printf("%d",p[x][y]); } while(x+1<=n 66 y-1>=1 66 4) { ++t； v[x+1][y-1]=1; printf("%d",p[x+1][y-1]); X++； y--; if(x+1<=n) { ++t； x++; v[x][y]= 1; printf("%d",p[x][y]); } while(x-1 >= 1 88 y+1 <= n 8& !v[x-1][y+1]) { ++t; ⑤; printf("%d"，p[x-1][y+1]); x--； y++; } } } return 0; } ``` 35.①处应填（ ){{ select(35) }} - A.p[0][0] - B.p[0][1] - C.p[1][0] - D.p[1][1]. 36.②处应填() {{ select(36) }} - A.v[0][0]=1 - B.v[1][1]=1 - C.v[0][1]=1 - D.v[1][0]=1 37.③处应填（ )。 {{ select(37) }} - A.t< n*n - B.t <= n*n - C.t < n - D.t<= n 38.④处应填( )。 {{ select(38) }} - A.v[x+1][y-1] - B.v[x-1][y+1] - C.!v[x+1][y-1] - D.!v[x-1][y+1] 39.⑤处应填( )。 {{ select(39) }} - A.v[x-1][y-1]= 1 - B.v[x+1][y+1]= 1 - C.v[x+1][y-1]= 1 - D.v[x-1][y+1]=1 （2）你有一架天平和N个砝码，这N个砝码的重量依次是W、W.··Ww。请计算：一 共可以称出多少种不同的重量？注意砝码可以放在天平两边。 输入格式： 输入的第1行包含一个整数N。第2行包含个整数：W，W2.…,Ww。输出格式： 输出一个整数代表答案。 输入样例： 3 146 输出样例： 10 样例说明： 能称出的10种重量是1、2、3、4、5、6、7、9、10、11。 1=1 2=6-4(天平一边放6，另一边放4) 3=4-1 4=4 5=6-1 6=6 7=1+6 9-4+6-1 10-4+6 11=1+4+6 评测用例规模与约定： 对于50%的评测用例，$1\le N \le15$； 对于所有评测用例，$1\le N\le 100 $，N个砝码的总重量不超过$10^5$。 ```C++ #include using namespace std; const int maxn = 105, maxv = 1e5 + 5; int n, a[maxn], f[maxn][maxv], sum,ans; int main() { cin >> n; for(int i=1; i<= n; i++) { cin >> a[i]; ①; } f[0][0]=1; for(int i= 1; i <= n; i++) for(int ②;j >= 0;j--)//2 { f[i][j] l= f[i-1][j]; f[i][j] |=③; if(4) f[i][j] |= f[i-1][j + a[i]]; } for(int i =1; i <= sum;i++) ⑤; cout << ans; return 0; } ``` 40.①处应填() {{ select(40) }} - A.sum += a[i] - B.sum += a[1] - C.sum += a[n] - D.sum= a[i] 41.②处应填( )。 {{ select(41) }} - A.j=f[i][j] - B.j= sum-1 - C.j·n - D.j sum 42 ③处应填( ） {{ select(42) }} - A.f[i-1][j-a[i]] - B.f[1-1][abs(j-a[i])] - C.ff1][abs()-a(1])] - D.f[i-1][a[i]-j] 43.④处应填()。 {{ select(43) }} - A.j+ali] < sum - B.j +a[i] <= sum - C.j+a[i-1] < sum - D.j +a[i-1] <= sum 44.⑤处应填( )。 {{ select(44) }} - A.ans += f[n][i-1] - B.ans += f[n-1][i-1] - C.ans += f[n][i] - D.ans += f[n-1][i] --- ## F. CSP-J 模拟6 ## 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项） 1. 2024的因子与质因子分别有（ )个。 {{ select(1) }} - A.18和3 - B.16和3 - C.15和3 - D.16和4 2.使用邻接矩阵表示N个结点的有向图，所需要的存储空间为（ )。 {{ select(2) }} - A.NX(N+1) - B.N2 - C.N×(N-1) - D.N×(N-1)/2 3.在C++程序中，表达式a%=b与下列哪个表达式是等价的？（） {{ select(3) }} - A.a=%b - B.a/=b - C.a=b%a - D.a=a%b 4.线性表若采用链表存储结构，则要求内存中可用存储单元地址（ )。{{ select(4) }} - A. 必须连续 - B.必须不连续 - C.连续或不连续都行 - D.部分连续 5. 我们输入一个新闻网站的网址便可访问该网站，其中用到的网络协议是( ) {{ select(5) }} - A.DNS - B.FTP - C.SSH - D.TELNET 6. 以下哪个不属于STL中栈的操作函数？( ) {{ select(6) }} - A.empty - B.front - C.push - D.pop 7.平面上任取n个整点（横坐标和纵坐标都是整数），其中一定存在两个点，它们的中 点也是整点，那么n至少是（ )。 {{ select(7) }} - A.4 - B.5 - C.6 - D.7 8.以下哪个操作属于位运算范畴？( ） {{ select(8) }} - A.66 - B.11 - C.>>> - D.^ 9.关于树这种数据结构，下面的说法中哪个是正确的？（ ) {{ select(9) }} - A.满二叉树的结点总数一定是奇数 - B.完全二叉树的结点总数一定是奇数 - C.树形结构只有双亲表示法和孩子表示法 - D.二叉树的遍历方法只有前序遍历法和后序遍历法 10. 以下哪个选项不属于头文件cmath？(） {{ select(10) }} - A.find(iterator first, iterator last, int x) - B.abs(int x) - C.ceil(double x) - D.pow(double x,double y) 11.在C++语言中，表达式584|3的值等于（ )。 {{ select(11) }} - A.7 - B.5 - C.4 - D.3 12.定义变量double n，如果下面的代码输入为1000，则输出最接近（ ) {{ select(12) }} ``` #include using namespace std; int main() { double n; cin>>n; cout << log10(n)-log2(n)<< endl; return 0; } ``` - A.0 B.-5 C.-7 D.7 13.在图的广度优先搜索中，要维护一个标识数组表示已经访问过的图的结点，需要 （）数据结构存放结点以实现遍历。 {{ select(13) }} - A.栈 B.队列 C.哈希表 D.堆 14.从一个6×6的棋盘（不可旋转）中选取不在同一行也不在同一列的两个方格，共有 ( )种方法。 {{ select(14) }} - A.480 B.450 C.360 D.720 15.下列关于集合的说法哪个不正确？（) {{ select(15) }} - A.一个元素是否属于一个集合是确定的 - B.集合中的元素两两不同 - C.0属于空集 - D. 集合中的元素不存在先后次序 ## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填V，错误填×除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分） (1) ```C++ #include using namespace std; int main() { set s; srand(time(0)); int n=6; int 1=12; int k,i=0,a[n]; while(s.size()::iterator it; for(it=s.begin();it!=s.end(); it++) a[i++] = xit; for(int i=0; icn; i++) { int x=rand()%n; int y=rand()%n; if(a[x] > aly]) swap(alx],aly]); } for(int i=0; icn; i++) cout< using namespace std; int month[13]=f-1,31,28,31,30，31，30，31，31，30，31，30，311； int date,ans1,ans2,y,m,d; bool check1(int date) { char s[32]; sprintf(s, "%d", date); if(s[0]==s[7] 88 s[1]==s[6] 88 s[2]==s[5] 88 s[3]==s[4]) return true; return false; } bool check2(int date) { char s[32]; sprintf(s,"%d",date); if(s[0]==s[2] 88 s[0]==s[5] 68 s[0]==s[7] 88 s[1]==s[3] 88 s[1]==s[4] 88 s[1]==s[6]) return true; return false; } int main() { cin>>date; y=date/10000; m=date/100%100; d=date%100； for(int i=y;;i++){ if(1%400==0 1 (1%100!=0 88 1%4==0)) month[2]= 29; } month[2]= 28; int j=(i==y)?m:1; for(;j<=12;j++) { int k=(i==y 88 j==m)?d+1:1; for(;k<=month[j];k++){ int date=i*10000+j*100+k; if(check1(date) &8 ans1==0) ans1=date; if(check2(date)) return cout< using namespace std; const int MAXN = 100; bool Prime_Number_Judge(const int &num) { if (num <= 3) return num > 1; for (int i = 2; i < num; i++) if (num % i == 0) return false; return true; } int& Get_Number_Size(const int &num) { int digit = 0, val = num; while (val){ val /= 10; digit++; } return digit; } vectorc&Get_Digits(const int &num, vectorcint> &digits){ int vactor_val = 0; for(int num_size=Get_Number_Size(num);num_size>0;num_size--){ vactor_val = num %(int)pow(10.0, num_size); vactor_val = vactor_val/(int)pow(10.0,num_size-1); digits.push_back(vactor_val); } return digits; } vectorc&Get_K_Adjacent(const int 8num, vector6adjacent){ vectork digists_number; char tmp[128], buf_tmp[128]; Get_Digits(num,digists_number); int digits = Get_Number_Size(num); for (int i = 0; i< digits; i++){ for (int j = 0; j buf; Get_K_Adjacent(i, buf); int sign = 1; for (int j =0; j < buf.size();j++) if(!Prime_Number_Judge(buf.at(j))) sign = 0;break; if (sign) count++; } } cout< using namespace std; int main() { int n,t,×,y; t=1, x=1, y=1; int v[505][505],p[505][505]; cin >> n; for(int i=1;i<=n;i++) for(int j=l;jc=n;j++) cin>>p[i][j]; printf("%d"，①); ②; while(③) { if(y+1 <= n) { ++t; y++; v[x][y]=1； printf("%d",p[x][y]); } } while(x+1<=n 66 y-1>=1 66 4) { ++t; v[x+1][y-1]=1; printf("%d",p[x+1][y-1]); X++; y--; } if(x+1<=n) { ++t; x++; v[x][y]= 1; printf("%d",p[x][y]); } while(x-1 >= 1 88 y+1 <= n 8& !v[x-1][y+1]) { ++t; ⑤; printf("%d"，p[x-1][y+1]); x--; y++; } return 0; } ``` 35.①处应填（ ) {{ select(35) }} - A.p[0][0] - B.p[0][1] - C.p[1][0] - D.p[1][1] 36.②处应填() {{ select(36) }} - A.v[0][0]=1 - B.v[1][1]=1 - C.v[0][1]=1 - D.v[1][0]=1 37.③处应填（ )。 {{ select(37) }} - A.t< n*n - B.t <= n*n - C.t < n - D.t<= n 38.④处应填( )。 {{ select(38) }} - A.v[x+1][y-1] - B.v[x-1][y+1] - C.!v[x+1][y-1] - D.!v[x-1][y+1] 39.⑤处应填( )。 {{ select(39) }} - A.v[x-1][y-1]= 1 - B.v[x+1][y+1]= 1 - C.v[x+1][y-1]= 1 - D.v[x-1][y+1]=1 （2）你有一架天平和N个砝码，这N个砝码的重量依次是W、W.··Ww。请计算：一 共可以称出多少种不同的重量？注意砝码可以放在天平两边。 输入格式： 输入的第1行包含一个整数N。第2行包含个整数：W，W2.…,Ww。输出格式： 输出一个整数代表答案。 输入样例： 3 146 输出样例： 10 样例说明： 能称出的10种重量是1、2、3、4、5、6、7、9、10、11。 1=1 2=6-4(天平一边放6，另一边放4) 3=4-1 4=4 5=6-1 6=6 7=1+6 9-4+6-1 10-4+6 11=1+4+6 评测用例规模与约定： 对于50%的评测用例，1＜N 15； 对于所有评测用例，1 N 100，N个砝码的总重量不超过10°。 ```C++ #include using namespace std; const int maxn = 105, maxv = 1e5 + 5; int n, a[maxn], f[maxn][maxv], sum,ans; int main() { cin >> n; for(int i=1; i<= n; i++) { cin >> a[i]; ①； } f[0][0]=1; for(int i= 1; i <= n; i++) for(int ②;j >= 0;j--)//2 { f[i][j] l= f[i-1][j]; f[i][j] |=③; if(4) f[i][j] |= f[i-1][j + a[i]]; } for(int i =1; i <= sum;i++) ⑤; cout << ans; return 0; } ``` 40.①处应填(){{ select(40) }} - A.sum += a[i] - B.sum += a[1] - C.sum += a[n] - D.sum= a[i] 41.②处应填( )。 {{ select(41) }} - A.j=f[i][j] - B.j= sum-1 - C.j·n - D.j sum 42 ③处应填( ）{{ select(42) }} - A.f[i-1][j-a[i]] - B.f[1-1][abs(j-a[i])] - C.ff1][abs()-a(1])] - D.f[i-1][a[i]-j] 43.④处应填()。 {{ select(43) }} - A.j+ali] < sum - B.j +a[i] <= sum - C.j+a[i-1] < sum - D.j +a[i-1] <= sum 44.⑤处应填( )。 {{ select(44) }} - A.ans += f[n][i-1] - B.ans += f[n-1][i-1] - C.ans += f[n][i] - D.ans += f[n-1][i] --- ## G. CSP-J 模拟7 ## 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项） 1.在标准ASCII码表中，字符'4'的ASCII码值用二进制表示是（ )。 {{ select(1) }} - A.00000100 - B.00110100 - C.00110101 - D.00110011 2.关于树这种数据结构的下述说法，正确的是（ )。 {{ select(2) }} - A.一个有m个顶点和m-1条边的图就是树 - B.树中的任意两个顶点之间有且只有一条简单路径 - C.树中有的结点可能构成环 - D.若树根层次为1，则对应高度为n的二叉树最多有2”个结点 3. 以下哪个不是输入设备？( ) {{ select(3) }} - A.绘图仪 - B.触摸屏 - C.扫描仪 - D.麦克风 4.当a=3，b=2.c=l时，执行以下程序段后c=（){{ select(4) }} ```C++ if(a>b) a=b; if(b>c) b=C； else c=b; c=a--; ``` - A.0 - B.1 - C.2 - D.3 5.学生在大学选修某些课程时需要先上其他的前置课程，所有课程和课程间的先修关 系构成一个有向图G，有向边表示课程M是课程N的先修课，则要找到某 门课程L的全部先修课，下面哪种算法不可行？（） {{ select(5) }} - A. Dijkstra - B. BFS - C.DFS - D.BFS+DFS 6.下列对语句freopen("function.in"，"r"，stdin）;的分析中正确的是（ ) {{ select(6) }} - A.freopen是文件名 - B.function.in是重定向函数名 - C.r代表重定向为“写”方式 - D.语句将cin重定向到文件function.in 7.Windows下可执行文件的扩展名是( )。 {{ select(7) }} - A.com - B.exe - C.cpp - D.dll 8.[x]补码=10011000，其原码为（)。 {{ select(8) }} - A.011001111 - B.11101000 - C.11100110 . - D.01100101 9.下面有关布尔类型的函数的说法，正确的是( )。 {{ select(9) }} - A.布尔类型函数只能返回0和1两个值 - B.布尔类型函数可以返回负数 - C.布尔类型函数必须有参数传递 - D.布尔类型函数可以返回 NULL 10.下面有关格雷码的说法，错误的是（ )。 {{ select(10) }} - A.在格雷码中，任意两个相邻的代码只有一位二进制数不同 - B.格雷码是一种可靠性编码 - C.在格雷码中，最大数和最小数只有一位二进制数不同 - D.格雷码是一种唯一性编码 11.现在有5个整数-2，-1，0，1，2，从中任意挑选两个整数，它们的和为0的概率是多少？ （） {{ select(11) }} - A.1/6 - B.1/4 - C.1/5 - D.1/10 12.小明走楼梯，每次上台阶能跨1或2级。下面是走到第N步台阶的C++实现代码该段代码采用的是（ ）算法。 {{ select(12) }} ```C++ int UpStairs(int N) { if(N==1） return 1; else if(N==2) return 2; else return UpStairs(N-2)+ UpStairs(N-1); } ``` - A.递推 - B.贪心 - C.动态规划 - D.分治 13.某内容中仅会出现A，B，C，D，E，F，G，对应的出现概率分别为0.40，0.30,0.15,0. 0.04,0.03,0.03，如下图所示。按照哈夫曼编码规则，假设B的编码为11，则D编码为（ )。 {{ select(13) }} ![image](file://NYG4rNavpKkb0OqREpPeU.png) - A.10010 - B.10011 - C.10111 - D.10001 14.某学习小组有5名男生和3名女生，从中选3名男生和1名女生参加3项竞赛活动每项活动至少有1人参加，则参赛方法有( )种。 {{ select(14) }} - A.960 - B.1080 - C.2160 - D.540 15.简单无向连通图G有18条边，且每个顶点的度数为2.则图G有（ )个顶点。 {{ select(15) }} - A.81 - B.17 - C.18 - D.64 ## 二、阅读程序（程序输入不超过数组或字符串定义的范围：判断题正确填V，错误填x除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分） (1) ```C++ #includecbits/stdc++.h> using namespace std; int a[101000]; int p(int deep){ return pow(2,deep); } int main(){ int n,mindeep=1,1=2,deep=2; scanf("%d %d”,5n,&a[1]); long long maxx = a[1]; for(i=2;i<=n;i++) scanf("%d”,Sa[i]); i=2； while(i<=n){ long long sum=0; for(;i maxx) maxx = sum, mindeep = deep; deep++; } cout << mindeep; return 0; } ``` 判断题 16.将第8行中的i=2改为i，程序的运行结果不会改变。 （） {{ select(16) }} 17如果输入都是正整数，那么将第10行中的a[1]替换成a[0]，将第13行中的i=2 替换成i=1，程序的运行结果不会改变。 () {{ select(17) }} 18.将第15 行中的long long sum=0；替换成long long sum;，程序的运行结果不会改变 ( ) {{ select(18) }} 19.将第 18 行中的 if(sum > maxx)替换成 if(sum >= maxx)，程序的运行结果不会改变 （) {{ select(19) }} 选择题 20 若输入为71654 3 2 1，则输出为() {{ select(20) }} - A11 - B.2 - C.10 - D.3 21.若输入为1594533212111 11 1 1，则输出为（) {{ select(21) }} - A4 - B.3 - C.2 - D.1 (2) ```C++ #include using namespace std; bool judge(int a) { while(al=0) { int t = a%10; if(t==2 ll t==4) return 0; a = a/10; } return 1; } int main(void) { int sum=0,n; cin>>n; for(int i=l;icn/3+1;i++) if(judge(i)) for(int j=i+1;j using namespace std; typedef long long LL; int a[100005],b[100005],c[100005]; int small(int n, int a[], int key) { int left=1, right=n; while(left < right) { int mid = (left+right+1)/2; if(a[mid]< key) left = mid; else right = mid - 1; return left; } } int big(int n, int c[], int key) { int left=1, right=n; while(left < right) { int mid = (left+right)/2; if(c[mid] > key) ght = mid; else left = mid + 1; } return left; } int main() { int n; cin>>n; for(int i=l;i<=n;++i) cin>a[i]; for(int i=1;ic=n;++i) cin>>b[i]; for(int i=1;ic=n;++i) cin>>c[i]; sort(a+1,a+n+1); sort(b+1,b+n+1); sort(c+1,C+n+1); LL count = 0; for(int i=1;i<=n;i++) { int key = b[i]; LL wa = small(n,a,key); LL wc = big(n,c,key); if(a[wa] < key 65 c[wc] > key) count += wa*(n+1-wc); } cout<>1，程序的运行结果不会改变 ( ) {{ select(29) }} 30.若将第23行中的(left+right)/2替换为left+(right-left)/2，程序的运行结果不会改变 ( ) {{ select(30) }} 31.若将第48行中的small(n,a，key)替换为(lower_bound(a+1,a+n+1，b[i])-a)-1，程序的运行结果不会改变 （ ) {{ select(31) }} 选择题 32.本程序运行的时间复杂度是（ ) {{ select(32) }} - 0(1) - B.O(n) - C.o(n^2) - D.O(nlogn) 33.若输入3111222333，那么输出结果是 {{ select(33) }} - 27 - B.21 - C.18 ) - D.15 34.(4分)若输入3123345 5 67，那么输出结果是() {{ select(34) }} - A.27 - B.21 - A.18 - D.15 ## 三、完善程序（单选题，每小题3分，共计30分） (1)一个nxn的正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照下列转换方法转换成新图案所采用的最小序号的方式。 ①转90°：图案顺时针旋转90°。 ②转180°：图案顺时针旋转180°。 3转270°：图案顺时针旋转270°。 ④反射：图案在水平方向翻转(以中央铅垂线为中心形成原图案的镜像）。 5组合：图案在水平方向翻转，然后再按照①-③中的一种再次转换。 ⑥不改变：原图案不改变。 ⑦无效转换：无法用以上方法得到新图案。 如果有多种可用的转换方法，请选择序号最小的那个。 只使用上述7种步骤中的一个来完成这次转换。 输入格式： 第1行一个正整数n。然后是n行，每行n个字符，全部为@或-，表示初始的 正方形。接下来的n行，每行n个字符，全部为@或-，表示最终的正方形。输出格式： 单独的一行包括1~7中的一个数字（在上文已描述），表明需要将转换前的正 方形变为转换后的正方形的转换方法。 输入样例： @-@ 一 @@- @-@ -@ 输出样例： 1 数据范围： 对于 100%的数据，1 using namespace std; int n; char a[15][15],b[15][15],c[15][15],d[15][15]; bool work1(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ①; for(int i=1;ic=n;i++) for(int j=1;jc=n;j++) if(b[i][j]!=c[i][j]) return 0; return 1; } bool work2( ){ for(int i=1;ic=n;i++) for(int j=1;jc=n;j++) ②; for(int i=1;i<=n;i++) for(int j=1;jc=n;j++) if(b[i][j]!=c[i][j]) return 0; return 1; } bool work3(){ for(int i=1;i<=n;i++) for(int j=1;jc=n;j++) ③; for(int i=1;ic=n;i++) for(int j=1;jc=n;j++) if(b[i][j]!=c[i][j]) return 0; return 1; } bool work4(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ④; for(int i=1;ic=n;1++) for(int j=1;jk=n;j++) if(b[i][j]!=c[i][j]) return 1; return 0; } bool work5(){ for(int i=l;ic=n;i++) for(int j=1;jc=n;j++) a[i][j]=b[i][j]; work1（）） return 1; for(int i=1;ic=n;i++) for(int j=l;j<=n;j++) a[i][j]=b[i][j]; if(work2()) return 1; for(int i=1;ik=n;i++) for(int j=1;jc=n;j++) a[i][j]=b[i][j]; if(work3()) return 1; return 0; } bool work6(){ for(int i=1;i<=n;i++)for(int j=l;j<=n;j++)if(b[i][j]!=c[i][j]) return 0; return 1; } void work(){ if(work1())cout<<1;return; if(work2())cout<<2; return; if(work3())fcout<<3;return; if(work4())cout<<4;return; if(work5())fcout<<5; return; if(work6()) fcout<<6;return; cout<<7; } int main(){ cin>>n; for(int i=l;ic=n;i++) for(int j=1;j<=n;j++) cin>>ali][j];d[i][j]=a[i][j]; for(int 1=1;i<=n;1++) for(int j=1;j<=n;)++)cin>>c[i][j]; work( ); return 0; } ``` 35.①处应填()。 {{ select(35) }} - A.blj][n-i+1j=a[jj[i] - B.b[j][n-i]=a[j][i] - C.b[j][n-i+1]=a[ij[j] - D.b[j][n-i]=a[i][j] 36.②处应填()。 {{ select(36) }} - A.b[n-i][n-j】=a[i][j] - B.b[n-i+1][n-j+1]=a[i][j] - C.b[n-i)[n-j] = a[j][i] - D.b[n-j+1][n-i+1]=a[i][j] 37.3处应填() {{ select(37) }} - A.b[n-j+1][iJ=a[i][j] - B.b[n-j][i]=a[i][j] - C.b[n-j+1][iJ=alj][i] - D.b[n-j][i]=a[j][i] 38.④处应填( ） {{ select(38) }} - A.b[n-j+1][iJ=a[i][ j] - B.b[i][n-j]=a[i][j] - C.b[i】[n-j+1J=a[i][j] - D.b[i][n-j]=a[j][i] 39 5处应填( ) {{ select(39) }} - A.work1( ) - B.work2( ) - C.work3() - D.work4() （2）一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是 空的）给定两个城市之间的距离D、汽车油箱的容量C（以升为单位）、每升汽 能行驶的距离D、出发点每升汽油的价格P 沿途加油站数N（N可以为零）、加油 站1高出发点的距离D，每升汽油的价格P（=12··N）计算结果四舍五入至 数点后两位。如果无法到达目的地，则输出 No Solution 输人格式： 第1行，D.C，D、P.N.接下来有N行第+1行，两个数字，即加油站；离出发点的距离D和每升汽油的价格 P 输出精式： 所需的最少费用，计算结果四舍五入至小数点后两位。如果无法到达目的地， 则输出 No Solution 输入神例： 2756119274282 182029 22002.2 输出样例： 26.95 说明/提示： N<6，其余数字<500. ```C++ #include using namespace std; const int MAXN = 100; int N; double D[MAXN], P[MAXN], D1, C, per, req; int main(){ cin>>D1>>C>>per>>P[0]>>N; D1 /= per; for(int i=1; ic=N;i++) { cin>>D[i]>>P[i]; D[i] /= per; } D[0]= 0; ①; P[N+1] = 0; double cur = 0, ans = 0; for(int i=0; i<=N;i++) { int ni = N+1; for(int j=i+1;j<= N+1;j++) if（P[j]<= P[i]） ni=j; break; ②; if(req> C) ③; if(req > cur){ ans +=(req - cur)* P[i]; cur = req; } ④; if(cur<0) break; } if(cur < 0) cout<<"No Solution"<lchild); postorder(bt->rchild); cout << bt->data; } } ``` - - 后序遍历 - B.中序遍历 - C.前序遍历 - D.层次遍历 13.有规格尺寸相同的5种颜色的手套(不分左右）各15只混装在箱子里，从中至少取 出多少只，才能保证配出3副颜色相同的手套？（） {{ select(13) }} - 8 - B.9 - C.10 - D.11 14.由3个a、5个b和2个c构成的字符串中，包含子串"abc"的共有（ )个。 {{ select(14) }} - 39 600 - B.780 - C.840 - D.260 15.1GB代表的字节数量是（) {{ select(15) }} - 21° - B.220 - C.220 - D.2“0 ## 读程序（程序输入不超过数组或字符串定义的范围；判断题正确填V，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分） (1) ```C++ #include using namespace std; const int SIZE = 25; int n,k,a[SIZE]; int cnt=0; long long ans; bool isPrime(int n) { cnt++;cout<> n >>k; for (int i = 0; i< n;++i) cin >> a[i]; dfs(0,0,0)； cout << ans <=k，a数组的元素均为相等的正整数，则输出为（) {{ select(20) }} - A.0 - B.2 - C.4 - D.8 21.若输入12 8，则isPrime 被调用的次数为()。 {{ select(21) }} - A.4 - B.66 - C.132 - D.495 (2) ```C++ #include using namespace std; int CNT, P; int check(int tmp, int n) { int res = 0; for(int i=tmp; i>0; i--) { res += n; int a=0,ans=res; while(ans%n == 0) a++,ans/=n; i -= a-1; } return res; } int main() { cin >> CNT; while(CNT--) { int ans=1; cin >> p; for(int i=2; ic=sqrt(p); i++) { int tmp=0; while(p%i == 0) tmp++,p/=i; if(tmp) ans = max(ans,check(tmp,i)); } ans = max(ans,p); cout< #include #includecset> using namespace std; string a, s[105]; int cnt=0; setedict; void trim(string &s) { if(Is.empty()) { s.erase(0,s.find_first_not_of("")); s.erase(s.find_last_not_of("")+1); } } int main() { cin>>a; while(a!="#") { int length = a.length(); for(int i=0;i>a; } for(set::iterator it=dict.begin();it!=dict.end();++it) cout << *it << ""; return 0; } ``` 判断题 28.STL中的set属于关联式容器。 (） {{ select(28) }} 29.若将第6行中的int cnt=0替换为int cnt，程序的运行结果不会改变。 ( ) {{ select(29) }} 30.若将第21行中的a.length（）替换为a.size（），程序的运行结果不会改变。 () {{ select(30) }} 31. 若输入 34 12 56 #，则程序输出 12 34 56。 {{ select(31) }} 选择题 32 若输入为A Dream Is To Build A Big Big World #，则输出是（ )。 {{ select(32) }} - A Dream Is To Build A Big Big World - a dream is to build a big big world - a big build dream is to world - A Big Build Dream Is To World 33.入为WorlaYimu AsiaShanghai ChinaHangzhou ZhejiangJinhua #，则输能是( )。 {{ select(33) }} - Worldrimu AsiaShanghai ChinaHangzhou ZhejiangJinhua - B.worldyiwu asiashanghai chinahangzhou zhejiangjinhua - C.AsiaShanghai ChinaHangzhou WorldYiwu ZhejiangJinhua - D.asiashanghai chinahangzhou worldyiwu zhejiangjinhua 34.（4分）若输入为I am 12 years old.#，则输出是（ )。 {{ select(34) }} - A.am i old years - B.am I old years - C.I am years old. - D.I am 12 years old. 三、完善程序（单选题，每小题3分，共计30分） （1）假设有一个无向图，将这个无向图的某一条欧拉路或者欧拉回路用算法实现并打印出来 输入格式： 第1行是n和m，表示有n个点和m条边，以下m行描述每条边连接的两点输入样例： 55 12 23 34 45 51 输出格式： 欧拉路或欧拉回路 输出样例： 154321 ```C++ #includecbits/stdc++.h> using namespace std; #define MAXN 105 int g[MAXN][MAXN]; int du(MAXN); int CirCuit[MAXN]; int n,e,circultpos.x.v,start; void fied circuit(int 1) { for fint )=1;)c=n; js*) if(①) { g[j][i]= 0; g[i][j]= 0; nd_circuit(j); } ②; } int main() { memset(g,0,sizeof(g)); cin >> n >> e; for (int i=1; i<= e;i++) { cin >>x>> y; g[y][x]=1; ③; du[x]++; du[y]++; } start = 1; for (int i=1; i <= n; i++) if(④) start = i; circuitpos = 0; for (int i = 1; i <= circuitpos; i++) cout << circuit[i] <<''; cout << endl; return 0; } ``` 35.①处应填( ) {{ select(35) }} - A.g[i][j] == 0 - B.g[i][j]== 1 - C.du[i]==1 - D.du[j]==1 36.②处应填( ) {{ select(36) }} - A.circuit[++circuitpos]= i - B.circuit[circuitpos]= i - D.circuit[i]=j - C.circuit[j]=i 37.③处应填（)。 {{ select(37) }} - A.start=1 - B.start=0 - C.g[x][y]=1 - D.g[x][y]=0 38.④处应填（ )。 {{ select(38) }} - A.g[i][j]%2 == 0 - B.g[i][j]%2 == 1 - C.du[i] % 2 == 0 - D.du[i] %2 == 1 39.⑤处应填（) {{ select(39) }} - A.find_circuit(0) - B.find_circuit(start) - C.find_circuit(1) - D.find_circuit(n) （2）设一棵n结点的二叉树tree的中序遍历为（1,2,3.··n），其中数字1,23,···n为结点编 号。每个结点都有一个分数（均为正整数），记第i个结点的分数为d，tree及它的 每棵子树都有一个加分，任意一棵子树subtree（也包含tree本身）的加分计算方法 如下： subtree的左子树的加分×subtree的右子树的加分+subtree的根的分数若某棵子树为空，规定其加分为1。叶子的加分就是叶子结点本身的分数，不考虑它的空子树。试求一棵符合中序遍历为(1.2.3··）日加分最高的二叉树 tree要求输出：（1）tree的最高加分；（2）tree的前序遍历 输入格式： 第1行是一个整数n，为结点个数。第2行是》个用空格隔开的整数，为每个 结点的分数（0<分数<100） 输出格式： 第1行是一个整数，为最高加分（结果不会超过int范围）第2行是n个用空 格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的 方案。 数据范围： n<30 输入样例： 571210 输出样例： 145 31245 ```C++ #includecbits/stdc++.h> using namespace std; const int N=30; int n, w[N], f[N][N], rt[N][N]; void print(int l, int r) { if(l> r) return; ①; printf("%d",root); 12 ②; print(root+1,r); } int main() { memset(f,0,sizeof(f)); scanf("%d",&n); for (int i=1; ic=n;++i) { scanf("%d"，6w[i]); ③; rt[i][i]= i; } for (int l=n; l>=1; 1--) for(int r=l+1; r<=n; r++) for(int root=l; root<=r; root++) { int lw=f[l][root-1]; ④; if(lw == 0) lw= 1; if(rw == 0) rw= 1; if(⑤) { f[l][r]= lw*rw+w[root]; rt[l][r]= root; } } printf("%d\n",f[1][n]); print(1, n); printf("\n"); return 0; } ``` 40.①处应填（）。 {{ select(40) }} - A. int root =0 - B. int root 1 - C. int root rt[l][r] - D. int root rt[1][n] 41.②处应填（）。 {{ select(41) }} - A. print(1, root-1) - B. print(l, root-1) - C. print(1, root) - D. print(l, root) - 42.③处应填（）。 {{ select(42) }} - A.f[i][i] = 0 - B.f[i][i] = 1 - C. f[i][i] i - D.f[i][i]= w[i] - 43.④处应填（）。 {{ select(43) }} - A. int rw=f[root][r] - B.int rw=f[root+1][r] - C. int rw=f[root][n] - D. int rw=f[root+1][n] - 44.⑤处应填（）。 {{ select(44) }} - A. lw\*rw+w[ root] f[l][r] - B.lw\*rw+w[root] f[l][r] D.lw\*rw+w[root] f[1][n] - C. lw\*rw+w[ root] f[1][n] - D.lw\*rw+w[root] f[1][n] --- ## I. CSP-J 模拟9 ## 答案解析 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项） 1.已知数组A中，每个元素A[i][j]在存储时要占3字节，设i从1变化到8，j从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问：A[4][7]的 起始地址是什么？（） {{ select(1) }} - A. SA+108 - B. SA+141 - C. SA+111 - D. SA+126 2.以下关于算法的描述正确的是（）。 {{ select(2) }} - A.算法可以没有输出 - B.算法至少有一个输入 - C.算法必须在计算机上用某种语言实现 - D.算法的改进在很大程度上推动了计算机科学与技术的进步 3.执行下述C+代码，输出的结果是（）。 {{ select(3) }} ```C++ #include using namespace std; int main() { int pos=2; string s=("noip"); cout< using namespace std; priority_queue c int, vectorkint,greatercint?) int main() { int n,x,ans=0,t1=0，t2=0，t3=0; cin >> n; for(int i=0; icn; i++) { cin>>×; q.push(x); } for(int i=n;i>1;i--) { t1 =q.top(); q.pop()； t2 = q.top(); q.pop()； t3 = t1+t2; ans += t3; q.push(t3); } cout<去掉，不管输入如何，程序的运行结果都不变() {{ select(17) }} 18.将第15行和第17行互换，不管输人如何，程序的运行结果都不变。() {{ select(18) }} 19.将第21行去掉，不管输入如何，程序的运行结果都不变。() {{ select(19) }} 选择题 20.若输入312 9.则输出ans为() {{ select(20) }} - A.12 - B.22 - C.23 - D.15 21 若输入4 5 4 3 6，则输出ans为() {{ select(21) }} - A.30 - B.36 - C.37 - D.38 (2) ```C++ #include using namespace std; typedef long long LL; LL fun(LL a, LL b, LL &×, LL 5y) { LL t; if(O==b) { x=1; y=0; return a; } Ll d = fun(b,a%b,x,y); t=x; x=y; y=t-(a/b)*y; return d; } int main() { LL a，b，x=0，y=0; cin >> a >> b; cout << fun(a, b, x, y)<< endl; cout << x << ""<< y << endl; return 0; } ``` 判新题 将第3行中的typedef long long LL改为#define long long LL，程序的运( ） {{ select(22) }} 行结果不会改变 将第4行中的两个5去掉，程序的运行结果不会改变 () {{ select(23) }} 若输入b=0，则输出结果是a （ ） {{ select(24) }} 不国入两个为索数的正整数，则输出结果中，x和y一定有负数 （ ） {{ select(25) }} 选择题 26.若输入为02024，则输出为（ )。 {{ select(26) }} - A.2024 1 1 - B.2024 0 1 - C.0 1 1 - D.0 0 1 27.若输入为36 48，则输出为（ )。 {{ select(27) }} - A.144 1 -1 - B.144 -1 1 - C.12 1 -1 - D.12 -1 1 (3) ```C++ #include using namespace std; int a[101][3], b[101]; void dfs(int k, int w){ if(1==w） cout<>n; for(int j=1; ic=n; i++) { cin>t; cinxxaltl(1l>>aft][2); bfaft](1)]-1; bla[t][2)]-1; } for (inr lsl;jcsn; j++) if(b[i]==0){ root=i; break; } dfs(root,1); cout<>altJ(1J>>altJ[2)更改为cin>>a[1][t]>>a[2][t]，程序的运行结不会改变。( ) {{ select(29) }} 30.若将第29行去掉，程序的运行结果不会改变。 ( ) {{ select(30) }} 31.若将第34行dfs(root，1)更换为dfs(root，4)，程序的运行结果不会改变。() {{ select(31) }} 选择题 32.若输入如下数据，则输出是( )。 {{ select(32) }} 8 124 200 4 80 315 5 6 0 6 0 7 8 0 0 70 0 - A.31248567 - B.2 1 8 4 3 6 7 5 - C.2 8 4 1 7 6 5 3 - D.3 2 1 8 4 5 7 6 33 若输入和第32题一样，将第34行dfs(root，1)更换为dfs(root，2)，则输出是( )。{{ select(33) }} - A.3 1 2 4 8 5 6 7 - B.2 1 8 4 3 6 7 5 - C.2 8 4 1 7 6 5 3 - D.3 2 1 8 4 5 7 6 34.(4分)若输入和第32题一样，将第34行dfs(root，1)更换为dfs(root，3)，则输出是（)。 {{ select(34) }} - A.3 1 2 4 8 5 6 7 - B.2 1 8 4 3 6 7 5 - C.2 8 4 1 7 6 5 3 - D.3 2 1 8 4 5 7 6 三、完善程序（单选题，每小题3分，共计30分） （1）米老鼠上次在唐老鸭的迷宫城堡里玩了很久，现在她也想设计一个迷宫让唐老鸭来 走。但是她设计迷宫的思路不一样，她认为所有的通道都应该是双向连通的，也就 是说，如果有一个通道连通了房间A和房间B，那么既可以通过它从房间A走到房 间B，也可以通过它从房间B走到房间A。为了提高难度，米老鼠希望任意两个房 间有且仅有一条路径可以相通（除非走了回头路)。米老鼠现在把她的设计图给你 让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合 条件的，但是最后一个有两种方法从5到达8。 输入格式： 输入包含多组数据，每组数据是一个以00结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1， ，且不超过 100 000。每两组数 据之间有一个空行。整个输入以两个-1结尾。 输出格式： 对于输人的每一组数据，输出仅包括一行。如果该迷官符合米老鼠的思路， 么输出YES，否则输出NO. 输入样例： 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 输出样例： YES YES NO ```c++ #include using namespace std; #define MAXN 100005 int fa[MAXN]; int visit[MAXN]; int path, node; void init(int n){ for(int i=1;ic=n;++i){ fa[i]=i; visit[i] = 0; } path= 0; node = 0; int get(int x)t if(x == fa[x]) return x; else return ①; } int main(){ int a,b； bool flag; cin>>a>>b; while(a!=-1 66 b!=-1){ init(MAXN); flag = true; if(O==a 66 0==b) path--; while（②){ path++; if(visit[a]==0){ visit[a]=1; node++; } } if(visit[b]==0){ visit[b]=1; node++; } int root1=get(a); int root2=get(b); if(③) flag = false; else ; cin>>a>>b; if(⑤) cout<<"NO"<>a>>b; } return 0; } ``` 35. ①处应填( )。 {{ select(35) }} - A.fa[x] - B.× - C.fa[x]= get(fa[x]) - D.1 36. 2处应填() {{ select(36) }} - A.a！=0 1| b!=0 - B.a！=0 88 b!=0 - C.a！=0 - D.b!=0 37. ③处应填( )。 {{ select(37) }} - A.root1 == root2 - B.root1 != root2 - C.flag == true - D.visit[a]== visit[b] 38.④处应填( )。 {{ select(38) }} - A.fa[root1]= root1 - B.fa[root2]= root2 - C.fa[root1]= root2 - D.flag = true 39.⑤处应填（ ) {{ select(39) }} - A.path != node 85 I flag - B.path != node ll !flag - C.path != node-1 68 !flag - D.path != node-1 ll !flag (2)给定一个字符串，请计算至少添加几个字符，可以让其构成回文字符串 输入样例： 5 acbed 输出样例： 2 ```c++ #include using namespace std; #define MAXN 5005 char str1[MAXN], str2[MAXN]; int maxlen[2][MAXN]; int main() { int n; while(cin>>n) { for(int i=1;i<=n;++i) cin>>str1[i]; str1[n+1]='\0'; for(int i=1; i<=n;++i) ①; memset(maxlen,0,sizeof(maxlen)); int x=0; for(int i=1; i<=n; ++i) { x=1-×; for(int j=0; j<=n; ++j) { if(str1[i] == str2[j]) 2; else int len1 =3; int len2 = maxlen[1-x][j]; if(④) maxlen[x][j]= len1; else maxlen[x][j]= len2; } } cout<<⑤< len2 +1 - B.len1 > len2 - C.len2 > len1 - D.len2 > len1 + 1 44.⑤处应填( ） {{ select(44) }} - A.maxlen[xj[n] - B.n-maxlen[x][n] - C.maxten[1-x][n] - D.n-maxlen[1-x][n] --- ## J. CSP-J 模拟10 ## 一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项) 用C+语言将一个大写字母转换为对应的小写字母(比如将大写字母A转换为小写 字母a)，以下哪个代码不正确？( ) {{ select(1) }} - A.c+=32 - B.c-=32 - C.c-=· - D.c-=32 2 下列说法中错误的是(）。 {{ select(2) }} - A.栈、队列、树和图都属于数据结构的范畴 - B.CSP-JCSP-S是中国计算机学会举办的程序设计竞赛 - C.背包问题属于动态规划算法中的一种类型 - D.按照分布的地理范围，计算机网络类型可以分为星形、环形和总线型 3下列C++数组的定义中，会丢失数据的是（ )。 {{ select(3) }} - A.char str1[］= ('C','s','P'; - B.int num1[]= (3,6,9; - C.char str2[］=（'CSP-J', 'CSP-S','NOIP'; - D.float num2[]= 1.0,3.0,5.0; 4执行下面的C++代码，输出是（) ```C++ #include uising namespace std; int main(){ int tmp = 1; for(int i=1; i<10;i++) for(int j=1; j<5; j++) if(i%)==1) tmp++; cout<a。那么序列1 9.2.4.8.6的逆序对有（）个。 {{ select(15) }} - A.7 - B.6 - C.5 - D.4 ## 二、阅读程序（程序输入不超过数组或字符串定义的范围：判断题正确填V，错误填x；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分) (1) ```C++ #include using namespace std; int a[10]; void print_num(){ cout<<'1'; for(int i=2;i<=9;++i){ if(a[i]==0) cout<<'+'; else cout<<'-'; cout<=2;j--){ if(k61){ s-=j; a[j]=1; } else{ s+=j; a[j]=0; } k>>=1; if(s==9) print_num();if(k61){ s-=j; a[j]=1; } else{ s+=j; a[j]=0; } k>>=1; if(s==9) print_num(); } return 0; } ``` 判断题 16.将第8行和第10行交换，程序的运行结果不会改变。() {{ select(16) }} 17.将第8行中的'+'改为"+”，程序的运行结果不会改变。() {{ select(17) }} 18.将第20行中的k&1改为k%2，程序的运行结果不会改变。() {{ select(18) }} 19.将第28行中的k>>=1改为k/=2，程序的运行结果不会改变。() {{ select(19) }} 选择题 20.输出数据共有（ )行。 {{ select(20) }} - A.11 - B.10 - C.12 - D.13 21.程序主要用到了（ ）的算法思想。 {{ select(21) }} - A.贪心 - B.二分 - C.二进制 - D.动态规划 (2) ```C++ #include using namespace std; stack s; int main() { string a; int len,mid,next,top; getline(cin,a); len=a.length(); mid=len/2-1; for(int i=0; i<=mid; i++) s.push(a[i]); if(len%2==0） next=mid+1; else next=mid+2; for(int i=next;lc=len-1;i++) { if(a[i]!= s.top()) break; s.pop(); } if(S.s1ze()==0) cout<<"yes"; else cout<<"no"; return 0; } ``` 判断题 22.将第6行中的string a改为char a[256]，程序的输出结果不变() {{ select(22) }} 23.即使输人的字符串中间有空格，getline函数也支持相应的处理。 ( ) {{ select(23) }} 24. 将第11行中的int i=0改为int i=1，程序的输出结果不变。 （） {{ select(24) }} 25 若输入abc cba，同时将第8行的getline(cin，a)改为cin>>a，程序的输出结果为no。 ( ) {{ select(25) }} 选择题 26.若输出结果为yes，则输入可能为（ )。 {{ select(26) }} - A.abc big big abc - B.abc big big cba - C.abc big gib abc - D.abc big gib cba 27.若输出结果为no，则输入可能为（ ） {{ select(27) }} - A.1234567890987654321 - B.12345 6789899876 54321 - C.12345 678909876 54321 - D.12345 6789009876 54321 (3) ```C++ #include using namespace std; struct node{ int data; node next; } int n,m; node * head,*,*r; int main() { cin >> n >> m; head = new node; head->data= 1; head->next = NULL; r = head; for(int i=2;ic=n;i++) { p = new node; p->data=i; p->next =NULL; r->next = P; r=p; } r->next = head; r = head; for(int i=1;ic=n;i++) { for(int j=1;j<=m-2;j++) r = r->next; cout<next->data<<""; r->next =r->next->next; r =r->next; } return 0; } ``` 判断题 28.node这个结构体在内存空间中占8字节。() {{ select(28) }} 29.程序中有new却没有做delete，输入n大于10必然会导致程序运行时崩遗。() {{ select(29) }} 30.若输入为85，去掉第15行，程序的运行结果不会改变。() {{ select(30) }} 31.本程序用到了双向链表的技巧。() {{ select(31) }} 选择题 32.若输入为85，则输出是（ ） {{ select(32) }} - A.5 2 7 8 1 4 6 3 - B.5 2 87 1 4 6 3 - C.5 2 8 7 4 1 6 3 - D.5 2 8 7 1 4 3 6 33.若输入为11 4，则输出是( )。 {{ select(33) }} - A. 4 8 1 6 11 7 3 2 5 10 9 - B.4 8 6 1 11 7 3 2 5 10 9 - C.4 8 1 11 6 7 3 2 5 10 9 - D.4 8 1 6 11 7 2 3 5 10 9 34.(4分)程序运行的时间复杂度是（ )。 {{ select(34) }} - A.O(n) - B.O(logn) - C.O(nm) - D.O(m) 三、完善程序（单选题，每小题3分，共计30分） (1)交叉字符串问题。给出3个字符串s1、s2和s3，判断s3是否可以由s1和52两个字符串经过交叉组合而成，组合过程不能改变字符在s1和s2中的原本顺序。如51=“aabcc"，s2="dbbca"，s3="aadbbcbcac"或s3="aadbbbaccc"。给了两种3的情况，第一种情况下答案是yes，第二种情况下答案是no，因为找不到任何一种sl和s2的交叉组合方式可以组合成s3。 输入格式： 第1行输入一个整数N。第2行到第N+1行输入3个字符串对s1,s2.s3，s1和2的长度都不超过200，s3的长度等于s1和s2的长度之和。 输出格式： 每个测试样例输出一行，yes代表可以构成，no代表不能。 输入样例： 3 cat tree tcraete cat tree catrtee cat tree cttaree 输出样例： yes yes No ```C++ #include using namespace std; string str1,str2,str; bool pos; int vis[205][205]; void dfs(int s1,int s2,int s){ if(s1==str1.length() && s2==str2.length()){ ①; return; } if（②） return; if（③） return; vis[s1][s2]=1; if(str1[s1]==str[s]） ④； if(str2[s2]==str[s]) dfs(s1,s2+1,s+1); } int main() { int t,n; cin>>t; while(t--){ cin>>str1>>str2>>str; ⑤; memset(vis,0,sizeof(vis)); dfs(0,0,0); if（pos) cout<<"yes"< using namespace std; int main() { int a[105],s[105],f[100][100]; int j,n,p,m; cin>>n; s[0]=0; for(int i=1;i<=n;i++){ cin>>a[i]; ①; f[i][i]=0; } for(p=1;p<=n-1;p++) for(int i=1;icn;i++){ ②; if(j<=n) { m=INT_MAX; for(int k=i;k