2020CCF非专业级别软件能力认证第一轮CSP-J初赛试题

2020CCF非专业级别软件能力认证第一轮 (CSP-])入门级C++语言试题 认证时间：2020年10月11日14：30~16：30 考生注意事项： ●试题纸共有10页，答题纸共有1页，满分180分。请在答题纸上作答，写 在试题纸上的一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍 资料。 一、单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选 项) 1.在内存储器中每个存储单元都被赋予·个唯·的序号，称为()。 A.下标 B.地址 C.序号 2.编译器的主要功能是()。 A.将源程序翻译成机器指令代码 B.将一种高级语言翻译成另一种高级语言 C. 将源程序重新组合 D. 将低级语言翻译成高级语言 3,设x=true,y=true,z=false,以下逻辑运算表达式值为真的是()。 A.(xΛy)Az B.x∧(zVy)Az C.(xAy)V(zVx) D.(yVz)A×Az 4.现有一张分辨率为2048×1024像素的32位真彩色图像。请问要存储这张图 像，需要多大的存储空间？()。 A.4MB B.8MB C.32MB D.16MB 5.冒泡排序算法的伪代码如下： 输入：数组L,n≥1。输出：按非递减顺序排序的L。 算法BubbleSort: 1.FLAG←-n /标记被交换的最后元素位置 2.while FLAG 1 do 3. k←FLAG-1 4. FLAG←-1 5. for j=1 to k do 6. if L(j)>L(j+1)then do 7. L(j)L(j+1) 8. FLAG←-j CCF CSP-J2020第一轮C++语言试题 第1页，共10页 对个数用以上冒泡排序算法进行排序，最少需要比较多少次？()。 A.n B.n-2 C.n2 D.n-1 6.设A是n个实数的数组，考虑下面的递归算法： XYZ (A[1..n]) 1.if n=1 then return A[l] 2.else temp XYZ (A[1..n-1]) 3. if temp<A[n] 4. then return temp 5. else return A[n] 请问算法XY2的输山是什么？()。 A.A数组的平均 B.A数组的最小值 C.A数组的最人值 D.A数组的中值 7.链表不具有的特点是()。 A.插入删除不需要移动元素 9 可随机访问任一元素 C.不必事先估计行储空何 D.所需空间与线性表长度成止比 8.有19个顶点的无向图至少应该有()条边才能确保是一个连通图。 A.10 B.12 C.9 D.11 9.二进制数1011转换成十进制数是()。 A.10 B.13 C.11 D.12 10.五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双 胞胎必须相邻，则有()种不同排列方法？ 4.24 B.36 C.72 D.48 11.下图中所使用的数据结构是()。 压入A 压入B 弹出B 压入C B C ◇ → A A A. 哈希表 B. 二叉树 C. 栈 D.队列 12.独根树的高度为1。具有61个结点的完全·义树的高度为()。 A.7 B.5 C.8 D.6 13.千支纪年法是中国传统的纪年方法，由10个天下和12个地支组合成60个 天十地支。由公历年份可以根据以下公式和表格换算出对应的天千地支。 天干=（公历年份)除以10所得余数 地支=（公历年份)除以12所得余数 CCF CSP-J2020第一轮C++语言试题 第2页，共10页 天干甲乙丙厅戊庚辛王癸 456789123 地支子丑寅卵辰已午未申酉戌亥 45678918118123 例如，今年是2020年，2020除以10余数为0，查表为“庚”：2020除以12， 余数为4，查表为子”，所以今年是庚子年。 请问1949年的天干地支是() A.己亥 B.己丑 C.己卯 D.己酉 14.10个一好学生名额分配到7个班级，每个班级至少有一个名额，一共有 ()种不同的分配方案。 A.56 B.84 C.72 D.504 15.有副不同颜色的手套（共16只手套，何副手叁左右手各1只），一次性 从中取6只手套，请问恰好能配成两副手套的不同取法有()种。 A.30 B.150 C.188 D.128 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填V, 错误填×；除特殊说明外，判断题1.5分，选择题3分，共计4阳分) 1. 01 #include <cstdlib> 02 #include <iostream> 03 using namespace std; 04 05 char encoder[26]{'C','S','P',0}; 06 char decoder[26]; 07 08 string st; 09 10 int main(){ 11 int k =0; 12 for (int i =0;i 26;++i) 13 if (encoder[i]!0)++k; 14 for (char x 'A';x <'Z';++x){ 15 bool flag true; 16 for (int i=0;i<26;++i) 17 if (encoder[i]==x){ 18 flag false; 19 break; CCF CSP-J2020第一轮C+语言试题 第3页，共10页 20 21 if(f1ag）){ 22 encoder[k]x; 23 +k; 24 25 } 26 for (int i =0;i<26;++i) 27 decoder[encoder[i]-'A']i+'A'; 28 cin >st; 29 for (int i 0;i<st.length();++i) 30 st[i]decoder[st[i]-'A']; 31 cout <st; 32 return 0; 33} ●判断题 1)输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。 () 2)若输入的字符申不是空串，则输入的字符中与输出的字符申一定不一 样。() 3)将第12行的“1<26”改为“i<16”,程序运行结果不会改变 () 4)将第26行的“1<26”改为“i<16”,程序运行结果不会改变。 ●单选题 5)若输出的字符串为“ABCABCABCA”,，则下列说法正确的是()。 A.输入的字符串中既有A又有P B.输入的字符串中既有S又有B C. 输入的字符串中既有S又有P D.输入的字符串中既有A又有B 6)若输出的字符弗为“CSPCSPCSPCSP”,则下列说法正确的是()。 A.输入的字符串中既有J又有R B. 输入的字符串中既行P又行K C.输入的字符串中既有)又有K D.输入的字符中巾既有P又有R 2. 01 #include <iostream> CCF CSP-J2020第一轮C+语言试题 第4页，共10页 02 using namespace std; 03 04 longlong n,ans; 05 int k,len; 06 long long d[1000000]; 07 08 int main(){ 09 cin >n >k; 10 d[6]=0; 11 1en=1; 12 ans 0; 13 for (long long i 0;i n;++i){ 14 +d[o]; 15 for (int j=0;j+1<len;++j){ 16 if (d[j]==k){ 17 d[j]=0; 18 d[j+1]+=1; 19 ++ans; 2 21 22 if(d[1en-1]==k){ 陕西 23 d[1en-1]=0; 24 d[1en]=1; 25 ++len; 26 ++ans; 27 28 29 cout <ans <endl; 30 return 0; 31 假设输入的n是不超过262的正整数，k都是不超过10000的正整数，完 成下面的判断题和单选题： ●判断题 1)若k=1,则输出ans时，1en=n。() 2)若k>1,则输出ans时，1en一定小于n。() 3)若k>1,则输出ans时，k1en一定大于n。() ●单选题 4)若输入的n等丁1015，输入的k为1，则输出等丁()。 A.(1039-1015)/2B.(1038+1015)/2 C.1 D. 1815 CCF CSP-J2020第一轮C++语言试题 第5项，共10页 5)若输入的n等于205,891,132,894,649（即338），输入的k为3，则 输出等于()。 A. (330-1)/2 B.338 C.338-1 D.(330+1)/2 6)若输入的n等于100,010,802,000,890，输入的k为10，则输出等 于()。 A.11,112,222,444,543 B.11,122,222,444,453 C.11,122,222,444,543 D.11,112,222,444,453 3. 01 #include <algorithm> 02 #include <iostream> 03 using namespace std; 04 05 int n; 06 int d[50][2]; 07 int ans; 08 09 void dfs(int n,int sum){ 10if(n==1){ 陕西 11 ans max(sum,ans); 12 return; 13 14 for (int i =1;i <n;++i){ 15 inta=d[i-1][0],b=d[i-1][1]; 16 int×=d[i][o],y=d[i][1]; d[i-1][6]=a+x; 18 d[i-1][1]-b+y; 19 for (int j=i;j<n-1;++j) 0 d[j][]=d[j+1][o],d[j][1]=d[j+1][1]; 21 int s a x abs(b y); 22 dfs(n-1,sum +s); 23 for (int j=n -1;j>i;--j) 24 d[j][o]=d[j-1][6],d[j][1]=d[j-1][1]; 25 d[i-1][0]=a,d[i-1][1]=b; 26 d[i][o]=×,d[i][1]=y; 27} 28} 29 30 int main(){ 31 cin >n; 32 for (int i=0;i<n;++i) CCF CSP-J2020第一轮C++语言试题 第6项，共10页 33 cin >d[i][e]; 34 for (int i =0;i<n;++i) 35 cin>>d[i][1]; 36 ans 0; 37 dfs(n,0); 38 cout <ans <endl; 39 return 0; 40 假设输入的n是不超过56的正整数，d[i][o]、d[i][1]都是不超过 1080的正整数，完成下面的判断题和单选题： ●判断题 1)若输入n为6，此程序可能会死循环或发生运行错误。() 2)若输入n为20，接下来的输入全为0，则输出为0。() 3)输出的数定不小于输入的d[i][0]和d[1][1]的任意 ●单选题 4)若输入的n为20，接下来的输入是20个9和20个6，则输出为 ()。 A.1917 B.1908 C.1881 D. 1890 5)若输入的n为30，接下来的输入是30个0和30个5，则输出为 ()。 A.2020 B.2030 C.2010 D.2000 6)(4分)若输入的n为15，接下来的输入是15到1，以及15到1，则 输出为 () A.2420 9 2220 C.2440 D.2240 三、完善程序（单选题，每小题3分，共计30分） 1,(质因数分解)给出正整数n,请输出将n质因数分解的结果，结果从小 到大输出。 例如：输入n=120,程序应该输出22235，表示120=2×2×2×3× 5。输入保证2≤n≤10。提示：先从小到大枚举变量1，然后用1不停试 除n来寻找所有的质因子。 试补全程序。 01 #include <cstdio> 02 using namespace std; CCF CSP-J2020第一轮C++语言试题 第7页，共10页 03 04 int n,i; 05 06 int main(){ 07 scanf("%d",&n); 08 for(i=①；②<=n;i++){ 09 ③{ 10 printf("%d "i); 11 nn/i; 12 13 } 14 if(④) 15 printf("%d",⑤)； 16 return 0; 17} 1)①处应填() A.n-1 B.0 2)②处应填() A.n i B.n /(ii)C.i i i*i 3)③处应填() A.if (i*i<=n) B.if (n i==0) C.while (i *i<=n) D. while (n i ==0) 4)④处应填( n>1 B.n<=1 C.i+i<=n D.i<n /i 5)⑤处应填() A.2 B.i C.n/i D.n 2.(最小区间覆盖)给出n个区间，第i个区间的左右端点是[a1,b1]。现在 要在这些区间中选出若干个，使得区间[9，m]被所选区间的并覆盖（即每 一个B≤1≤m都在某个所选的区间中)。保证答案存在，求所选区间个数 的最小值。 输入第一行包含两个整数n和m(1≤n≤5000,1≤m≤10) 接下米n行，每行两个整数ai,b1(0≤a1,b:≤m) 提示：使州贪心法解决这个问题。先用(2)的时间复杂度排序，然后贪心 选择这些区间。 试补全程序。 CCF CSP-J2020第一轮C++语言试题 第8页，共10页 01 #include <iostream> 02 03 using namespace std; 04 05 const int MAXN 5000; 06 int n,m; 07 struct segment int a,b;A[MAXN]; 08 9 void sort()//排序 10{ 11 for (int i=0;i<n;i++) 12 for (int j=1;j<n;j++) 13 if(①) 14 5 segment t =A[j]; 16 ② } 18 9 20 int main() 陕西 21{ 22 cin >n >m; 23 for (int i =0;i<n;i++) 24 cin >A[i].a >A[i].b; 25 sort(); int p=1; 21 for (int i 1;i<n;i++) 8 if(③) 29 A[P+]=A[i]; 30 n =p; 31 int ans =0,r=0; 32 int g 0; 33 while (r m) 34 35 whi1e(④) 36 q++; 37 ⑤； 38 ans++j 39 } 40 cout <ans <endl; 41 return 0; 42} CCF CSP-J2020第一轮C+语言试题 第9页，共10页 典机 1)①处应填() A.A[j].b<A[j-1].b B.A[j].b>A[j-1].b C.A[j].aA[j-1].a D.A[j].aA[j-1].a 2)②处应填() A.A[j-1]=A[j];A[j]=t; B.A[j+1]=A[j];A[j]=t; C.A[j]=A[j-1];A[j-1]=t; D.A[j]=A[j+1];A[j+1]=t; 3)③处应填() A.A[i].b A[p -1].b B.A[1].b>A[i-1].b C.A[i].b A[p 1].b D.A[i].b A[i-1].b 4)④处应填() A.q+1<n&A[q+1].b<=r B.q+1<n&8A[q+1].a<=r C.q<n &A[q].a <=r D.q<n &A[q].b <=r 陕西 5)⑤处应填() A.r=max(r,A[q 1].a) B.r max(r,A[q].b) C.r=max(r,A[q 1].b) D.q++ 陕 CCF CSP-J2020第一轮C+语言试题 筑10页，共10页