2026山东信息学体验营初赛试卷解析文末附答案和解析一、单项选择题共15题每题2分共计30分1.十进制数2026的二进制表示中有多少个1A. 7 B. 8 C. 9 D. 102.下列四个数中最大的是A. (26)₈ B. (23)₁₀ C. (10111)₂ D. (1B)₁₆3.已知x是一个正整数x (x-1) 0成立。则x不可能是以下哪个值A. 2 B. 4 C. 6 D. 84.C中执行以下代码后变量res的值是inta5,b2;doubleresa/b0.5;A. 2.5 B. 3.0 C. 3 D. 2.05.C中执行以下代码#includebits/stdc.husingnamespacestd;intmain(){inta,b;longlongc;cinab;ca*b;coutc;return0;}如果输入100000 200000。下列描述正确的是A. 编译错误 B. 运行错误 C. 输出20000000000 D. ABC描述都不正确6.C中执行以下代码后输出结果是#includeiostreamusingnamespacestd;inta[]{2,4,6,8,10};intsum(intL,intR){if(LR)returna[L];intmid(LR)/2;returnsum(L,mid)sum(mid1,R);}intmain(){coutsum(0,4);return0;}A. 6 B. 8 C. 12 D. 307.给定整数序列-8, -2, -6使用动态规划算法求最大子段和连续元素和。设dp[i]表示以第 i 个元素结尾的最大子段和则 dp 数组的值是A. -13 -2 B. -12 0 -6 C. -8 -2 -6 D. -13 1 -8.下列哪一组二进制编码不能作为哈夫曼编码A. 010 110 111 B. 101 001 000 C. 00 01 10 11 D. 100 011 0119.对长度为100000的数组进行排序下列排序算法中在最坏情况下时间复杂度最低的是A. 冒泡排序 B. 快速排序 C. 归并排序 D. 插入排序10.一个栈的入栈序列为2, 4, 6, 8, 10按此顺序依次入栈在任意时刻可以出栈。以下哪个出栈序列是不可能出现的A. 2,4,6,8,10 B. 10,8,6,4,2 C. 4,2,10,8,6 D. 6,2,4,8,1011.一棵完全二叉树根节点的编号是1。按深度自上而下、每层自左向右的顺序依次编号若某个节点的编号为25则该节点的父亲编号是多少A. 12 B. 13 C. 50 D. 5112.已知无向图的顶点集合{A,B,C,D,E}边的集合是{(A,B),(B,D),(A,C),(C,E)}。从A点进行DFS深度优先搜索以下可能的遍历顺序是A. ABCDE B. ABDEC C. ACEDB D. ABDCE13.一个简单无向图有10个顶点其中2个顶点的度数为33个顶点的度数为4其余顶点的度数均为2。则该图的边数是多少A. 12 B. 13 C. 14 D. 2814.将6名不同的学生分配到两个不同的班级要求两个班人数相差不能超过2人则不同的分配方案有多少种A. 50 B. 54 C. 60 D. 6215.用数字1、2、3、4、5、6组成无重复数字的六位数要求1和2不相邻且5和6也不相邻。这样的六位数共有多少个A. 240 B. 336 C. 624 D. 480二、阅读程序判断题2分单选题3分共40分程序1#includebits/stdc.husingnamespacestd;constintN210;inta[N],f[N];intn,x,ans0;intmain(){cinn;for(inti1;in;i)cina[i];ansf[1]1;for(inti2;in;i){for(intj1;ji;j)if(a[j]a[i])f[i]max(f[i],f[j]1);f[i];ansmax(ans,f[i]);}printf(%d\n,ans);return0;}完成下面的判断题和单选题16.1分程序的功能是求数组a的最长上升子序列的长度。 17.将程序中的a[j] a[i]改为a[j] a[i]程序输出结果不变。 18.若数组a元素全部相等程序输出结果为1。 选择题当程序运行后输入9 8 2 7 1 9 10 14 319.f[5]的值是A. 1 B. 2 C. 3 D. 420.程序最后输出结果是A. 2 B. 3 C. 4 D. 5程序2#includebits/stdc.husingnamespacestd;constintN10000005;boolisPrime[N];intn;voidwork(intn){memset(isPrime,1,sizeof(isPrime));isPrime[0]isPrime[1]0;for(inti2;i*in;i){if(isPrime[i]){for(intji*i;jn;ji)isPrime[j]0;}}}intmain(){cinn;work(n);intcnt0;for(inti2;in;i){if(isPrime[i])cnt;}coutcntendl;return0;}完成下面的判断题和单选题21.1分程序的功能是输出2到n之间包含2和n的素数的个数。 22.将第11行的j i * i改为j 2 * i程序功能不变。 23.若输入n 2程序输出结果为0。 24.输入n 30时程序输出结果是A. 8 B. 9 C. 10 D. 1125.在work函数中当i 3时内层循环会标记哪些数的isPrime[]为0A. 3, 6, 9, 12, … B. 9, 12, 15, … C. 3, 9, 15, … D. 6, 12, 15, …26.若将第9行的i * i n改为i n以下哪个描述正确A. 运行结果不变 B. 运行更快 C. 数组会越界 D. 数据运算可能会溢出程序3#includebits/stdc.husingnamespacestd;constintN31;intw[N],v[N];intn,m;intmain(){cinnm;for(inti0;in;i){cinw[i]v[i];}intans0;for(ints0;s(1n);s){inttotal_w0;inttotal_v0;for(inti0;in;i){if(s(1i)){total_ww[i];total_vv[i];}}if(total_wmtotal_vans)anstotal_v;}coutansendl;return0;}完成下面的判断题和单选题27.该程序的功能是求解0-1背包问题的最大价值。 28.若将程序第18行中的total_w m改为total_w m程序输出结果不变。 29.若n 20该程序在1秒内可以运行完毕。 30.输入如下数据4 6 1 4 2 6 3 12 2 7程序的输出结果是A. 22 B. 23 C. 25 D. 2931.在枚举过程中s 5二进制0101表示选择了哪些物品假设物品编号从0开始A. 物品0和物品2 B. 物品1和物品3 C. 物品0和物品1 D. 物品1和物品232.若n 31以下哪个描述正确A. 程序输出结果一定是正确的 B. 算法时间复杂度是 O(n)C. 数组会越界 D. 程序可能因1 n溢出而结果错误三、完善程序单选题每小题3分共计30分1图的连通分量给定一个n × m的网格每个格子是0空地或1障碍物。定义四连通上下左右相邻的0格子属于同一个连通块。以下程序统计网格中0格子的连通块个数。试补全程序。#includebits/stdc.husingnamespacestd;constintN101;intn,m;intg[N][N];boolvis[N][N];intdx[]{0,0,-1,1};intdy[]{____,____};voiddfs(intx,inty){vis[x][y]1;for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx1nxnny1nym){if(______){______;}}}}intmain(){cinnm;for(inti1;in;i){for(intj1;jm;j){cing[i][j];}}intcnt0;for(inti1;in;i){for(intj1;jm;j){if(______){dfs(i,j);______;}}}coutcntendl;return0;}33.①处应填A.{1, 0, -1, 0}B.{1, 1, 0, 0}C.{0, 0, 1, -1}D.{1, -1, 0, 0}34.②处应填A.g[nx][ny] 1B.g[x][y] 1C.g[nx][ny] 0D.g[x][y] 035.③处应填A.dfs(x, y)B.dfs(dx[i], dy[i])C.dfs(nx, ny)D.dfs(nxdx[i], nydy[i])36.④处应填A.g[i][j] 0 !vis[i][j]B.g[i][j] 1 !vis[i][j]C.g[i][j] 0D.!vis[i][j]37.⑤处应填A.cntB.cntC.cnt 1D.vis[i][j] 12归并排序以下程序实现归并排序升序。试补全程序并完成问题解答。#includebits/stdc.husingnamespacestd;inta[100005],b[100005];voidmerge(intL,intmid,intR){intiL,jmid1,kL;while(imidjR){if(______){b[k]a[i];}else{b[k]a[j];}}while(imid)b[k]a[i];while(jR)b[k]a[j];for(intiL;iR;i)______;}voidmergeSort(intL,intR){if(LR)return;intmid(LR)/2;______;______;merge(L,mid,R);}intmain(){intn;cinn;for(inti1;in;i)cina[i];mergeSort(1,n);for(inti1;in;i)couta[i] ;return0;}38.①处应填A.a[i] a[j]B.a[i] a[j]C.a[i] a[j]D.a[i] a[j]39.②处应填A.a[i] b[i]B.b[i] a[i]C.a[L] b[L]D.a[i] b[k]40.③处应填A.mergeSort(L, mid-1)B.mergeSort(L, mid)C.mergeSort(mid, R)D.mergeSort(mid, R)41.④处应填A.mergeSort(L, mid)B.mergeSort(mid1, R)C.mergeSort(L, mid-1)D.mergeSort(mid, R)42.若输入数组a为[3, 2, 7, 3, 8, 6, 5]则merge函数在第一次被调用时L, mid, R的值是A. L1, mid1, R2 B. L1, mid1, R1 C. L1, mid3, R7 D. L1, mid4, R7参考答案与解析一、单项选择题B2026 1024512256128643282 2¹⁰2⁹2⁸2⁷2⁶2⁵2³2¹二进制11111101010₂共8个1。DA: (26)₈22B: 23C: (10111)₂23D: (1B)₁₆27最大为27。Cx (x-1) 0当且仅当x是2的幂。6不是2的幂。Aa/b是整数除法 5/22然后 20.52.5res为double。Da*b在int范围内计算100000×20000020,000,000,000溢出结果错误但不会编译或运行错误也不是20000000000故选D。D递归求和24681030。Cdp[1]-8dp[2]max(-2, -8-2-10)-2dp[3]max(-6, -2-6-8)-6。D哈夫曼编码要求任意编码不是另一个的前缀且每个编码唯一。D中011重复出现不能作为哈夫曼编码。C归并排序最坏O(n log n)其余最坏O(n²)。D若要6先出则2,4,6已入栈出6后栈顶为4下一个不可能出2。A完全二叉树中节点i的父亲为 ⌊i/2⌋⌊25/2⌋12。D从A出发若先访问B分支则顺序 A→B→D回溯后访问C→E得到 A B D C EC总度数 2×3 3×4 5×2 28边数 28/2 14。A分配方案(3,3)有C(6,3)20(4,2)有C(6,4)×230共50。B总数6! 720减去1和2相邻的2×5!240减去5和6相邻的240加上两者同时相邻的2×2×4!96得720-240-24096336。二、阅读程序16. 正确程序用动态规划求LIS长度。17. 错误改为后求最长不下降子序列结果可能变大。18. 正确全相等时严格递增条件不成立每个位置长度均为1。19. C3输入序列第5个元素为9前面小于9的最长长度为2如2,7故f[5]213。20. D5最长上升子序列可为2,7,9,10,14长度5。21. 正确埃氏筛统计素数个数。22. 正确从2*i开始标记虽然重复但最终结果相同效率略低。23. 错误n2时2是素数输出1。24. C102到30的素数2,3,5,7,11,13,17,19,23,29共10个。25. B当i3时从j9开始步长3标记9,12,15,…。26. C改为i n后当i较大时i*i可能溢出int导致j为负访问数组越界。27. 正确二进制枚举所有组合求不超过容量m的最大价值。28. 错误改为会漏掉总重量恰好等于m的方案。29. 正确n20时约2²⁰×20≈2千万次操作1秒内通常可完成。30. B23最优选择物品01,4、物品23,12、物品32,7总重6价值23。31. A二进制0101表示第0位和第2位为1即物品0和2。32. Dn31时131溢出为负数枚举出错。三、完善程序33. Ddx{0,0,-1,1}需配合dy{1,-1,0,0}得到右、左、上、下四个方向。34. C判断相邻格子是否为空地0。35. C递归访问相邻空地dfs(nx, ny)。36. A主循环中若当前格子为空地且未访问则启动DFS。37. A每找到一个连通块计数器cnt。38. C升序归并当左边元素 右边元素时取左边。39. A将临时数组b复制回原数组aa[i] b[i]。40. B递归排序左半部分[L, mid]。41. B递归排序右半部分[mid1, R]。42. AmergeSort(1,7)→ mid4 →mergeSort(1,4)→ mid2 →mergeSort(1,2)→ mid1 → 先递归左半mergeSort(1,1)再右半mergeSort(2,2)然后执行merge(1,1,2)故 L1, mid1, R2。更多内容请查看专栏《信奥赛C普及组CSP-J一等奖通关刷题题单及题解》https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}