2026年信奥赛C普及组csp-j初赛模拟卷三【文末附答案和解析】一、单项选择题共15题每题2分共30分每题有且仅有一个正确选项1.二进制数1101.101对应的十进制数是 。A. 13.625B. 13.5C. 13.25D. 13.1252.八进制数( 753 ) 8 (753)_8(753)8​转换为十六进制数是 。A.( 1 E B ) 16 (1EB)_{16}(1EB)16​B.( 1 E C ) 16 (1EC)_{16}(1EC)16​C.( 1 E D ) 16 (1ED)_{16}(1ED)16​D.( 1 E E ) 16 (1EE)_{16}(1EE)16​3.已知x 12y 7则表达式(x y) | (x ^ y)的值是 。A. 4B. 12C. 15D. 74.表达式8 | 3 2的值是 。提示优先级高于|A. 11B. 12C. 14D. 205.一棵完全二叉树共有 1000 个结点则该二叉树中叶子结点的个数为 。A. 500B. 501C. 499D. 500 或 5016.已知一棵二叉树的前序遍历序列为ABDECFG中序遍历序列为DEBACFG则该二叉树的后序遍历序列为 。A.EDBFGCAB.EDBGCFAC.DEBGFCAD.DBEGFCA7.用权值{5, 6, 8, 9, 12}构造哈夫曼树该树的带权路径长度WPL为 。A. 85B. 90C. 91D. 1008.一棵哈夫曼树共有 11 个结点则其叶子结点的个数为 。A. 5B. 6C. 7D. 89.一个具有 8 个顶点的无向连通图至少需要 条边才能保证是连通的若要构成一棵树则需要 条边。A. 78B. 89C. 77D. 8810.在一个有向图中所有顶点的入度之和为 20则该有向图的边数为 。A. 10B. 20C. 40D. 无法确定11.以下关于图的说法中错误的是 。A. 无向完全图K n K_nKn​的边数为n ( n − 1 ) / 2 n(n-1)/2n(n−1)/2B. 树是连通且无环的无向图C. 有向图中所有顶点的入度之和等于出度之和D. 连通无向图的边数一定大于等于顶点数12.int类型变量x的值为-832位补码表示则x 2的结果为 。A.-2B.-3C.2D.313.十进制数-27的 8 位二进制补码表示为 。A.11100101B.11100100C.11100110D.1001101114.栈是一种特殊的线性表具有 的特性。A. 先进先出B. 先进后出C. 随机存取D. 只能插入不能删除15.以下排序算法中最坏情况下时间复杂度为O(n²)的是 。A. 归并排序B. 快速排序C. 堆排序D. 以上都是二、阅读程序题共3题共40分一本题8分阅读下面的程序回答 16~20 题。#includeiostreamusingnamespacestd;intn,ans;inta[100];voiddfs(intx,intsum){if(xn){if(sumans)anssum;return;}dfs(x1,sum);dfs(x2,suma[x]);}intmain(){cinn;for(inti1;in;i)cina[i];ans0;dfs(1,0);coutansendl;return0;}判断题每题1分16.若输入n3a {1, 2, 3}程序输出为 4。 17.函数dfs的时间复杂度为O ( 2 n ) O(2^n)O(2n)。 18.若将所有a[i]都改为正数程序输出的含义是从数组a中选取若干个不相邻的元素使总和最大。 19.若输入n4a {10, 1, 10, 1}程序输出为 20。 20.该程序可以用动态规划优化为O(n)的时间复杂度。 二本题12分阅读下面的程序回答 21~26 题。#includeiostreamusingnamespacestd;intn,m;intg[105][105];intvis[105];intq[105],head,tail;voidbfs(ints){head1;tail1;q[1]s;vis[s]1;while(headtail){intuq[head];head;for(intv1;vn;v){if(g[u][v]!vis[v]){vis[v]1;tail;q[tail]v;}}}}intmain(){cinnm;for(inti1;im;i){intu,v;cinuv;g[u][v]1;g[v][u]1;}intcnt0;for(inti1;in;i){if(!vis[i]){cnt;bfs(i);}}coutcntendl;return0;}判断题每题1.5分21.该程序读入的是一个有向图。 22.变量cnt最终输出的是图中连通分量的个数。 23.若输入n5, m4边为(1,2), (2,3), (3,4), (4,5)程序输出为 2。 24.若将g[u][v] 1; g[v][u] 1;改为g[u][v] 1;程序功能不变。 25.该程序在最坏情况下的时间复杂度为O ( n 2 ) O(n^2)O(n2)。 选择题3分26.若输入n6, m5边为(1,2), (2,3), (4,5), (5,6), (1,6)程序输出为 。A. 1B. 2C. 3D. 4三本题20分阅读下面的程序回答 27~33 题。#includeiostream#includecstringusingnamespacestd;chars[100];intstk[100],top;intmain(){cins;intlenstrlen(s);top0;boolflagtrue;for(inti0;ilen;i){if(s[i](||s[i][||s[i]{){stk[top]s[i];}else{if(top0){flagfalse;break;}charcstk[top--];if((s[i])c!()||(s[i]]c![)||(s[i]}c!{)){flagfalse;break;}}}if(top!0)flagfalse;cout(flag?YES:NO)endl;return0;}判断题每题2分27.输入()时程序输出YES。 28.输入([)]时程序输出YES。 29.输入{时程序输出NO。 30.该算法的时间复杂度为O(n)其中n为字符串长度。 31.若输入字符串中包含数字字符如(1)程序会因数组越界而崩溃。 选择题每题5分32.输入({[]})时程序的输出是 。A.YESB.NOC. 程序出错D. 无法确定33.输入((()))时程序的输出是 。A.YESB.NOC. 程序出错D. 无法确定三、完善程序题共2题每题15分共30分一本题15分二叉树的层序遍历给定一棵二叉树每个结点用整数编号表示左、右孩子用-1表示空。请补全程序输出该二叉树的层序遍历序列从根结点开始逐层从左到右输出每个结点的编号。算法提示层序遍历可以使用队列实现。先将根结点入队然后每次从队首取出一个结点并输出再将其非空的左、右孩子依次入队重复此过程直到队列为空。试补全程序。#includeiostreamusingnamespacestd;structNode{intleft,right;}tree[100];intq[100],head,tail;voidlevelOrder(introot){if(root-1)return;head①;tail②;q[tail]root;while(③){intuq[head];coutu ;if(④)q[tail]tree[u].left;if(⑤)q[tail]tree[u].right;}}intmain(){intn,root;cinn;for(inti1;in;i){cintree[i].lefttree[i].right;}cinroot;levelOrder(root);return0;}34.①处应填 A.0B.1C.-1D.root35.②处应填 A.0B.1C.-1D.root36.③处应填 A.head tailB.head tailC.head tailD.head tail37.④处应填 A.tree[u].left ! -1B.tree[u].left -1C.tree[u].leftD.tree[u].left 038.⑤处应填 A.tree[u].right ! -1B.tree[u].right -1C.tree[u].rightD.tree[u].right 0二本题15分最大连续子段和给定一个长度为n的整数序列a[1..n]求其最大连续子段和。例如序列{-2, 1, -3, 4, -1, 2, 1, -5, 4}的最大子段和为6对应子段{4, -1, 2, 1}。本题保证子段非空即序列中至少有一个正数。算法提示使用动态规划。令dp[i]表示以a[i]结尾的最大连续子段和则状态转移方程为若dp[i-1] 0则dp[i] dp[i-1] a[i]否则dp[i] a[i]。答案ans为所有dp[i]中的最大值。试补全程序。#includeiostreamusingnamespacestd;intn,a[100],dp[100];intmain(){cinn;for(inti1;in;i)cina[i];intans①;dp[0]②;for(inti③;in;i){if(④)dp[i]dp[i-1]a[i];elsedp[i]a[i];if(⑤)ansdp[i];}coutansendl;return0;}39.①处应填 A.a[1]B.0C.-100000D.a[n]40.②处应填 A.0B.a[1]C.-100000D.141.③处应填 A.1B.2C.0D.n42.④处应填 A.dp[i-1] 0B.dp[i-1] 0C.dp[i-1] 0D.dp[i-1] 043.⑤处应填 A.dp[i] ansB.dp[i] ansC.dp[i] ansD.dp[i] ans参考答案与解析一、单项选择题1. A解析1101.101₂ 1×8 1×4 0×2 1×1 1×0.5 0×0.25 1×0.125 13.625。2. A解析(753)₈ 7×64 5×8 3 491。491 ÷ 16 30 余 11(E)30 ÷ 16 1 余 14(E)1 ÷ 16 0 余 1得(1EB)₁₆。3. C解析(x y) | (x ^ y) x | y 12 | 7 15二进制1100 | 0111 1111。4. B解析3 2 120011左移两位得11008 | 12 121000 | 1100 1100。5. A解析完全二叉树中叶子结点数 ⌈n/2⌉ 500。6. A解析由前序知A为根中序左子树DEB右子树CFG。递归得后序为EDBFGCA。7. C解析构造哈夫曼树合并5、6得11合并8、9得17合并11、12得23合并17、23得40。WPL 11 17 23 40 91。8. B解析哈夫曼树中度为2的结点数 叶子数 - 1总结点数 2n - 1 11 ⇒ n 6。9. C解析连通图至少n-17条边树也是n-17条边。10. B解析有向图中入度之和 出度之和 边数。11. D解析连通无向图边数至少为n-1可以等于n-1树不一定大于等于n。12. A解析-8的补码右移2位算术右移得-2。13. A解析27的二进制00011011取反11100100加1得11100101。14. B解析栈是先进后出LIFO。15. B解析快速排序最坏情况O(n²)。二、阅读程序题一阅读程序一16. 正确1分解析枚举不相邻选取最大为134。17. 正确1分解析每个位置两种选择递归规模2^n。18. 正确1分解析选当前则跳过下一个即不相邻。19. 正确1分解析选101020。20. 正确1分解析可用dp[i] max(dp[i-1], dp[i-2]a[i])优化。二阅读程序二21. 错误1.5分解析同时设置g[u][v]和g[v][u]表示无向图。22. 正确1.5分解析BFS遍历每个连通块cnt为连通分量数。23. 错误1.5分解析5个顶点4条边形成一条链全部连通cnt1。24. 错误1.5分解析改为有向图后BFS只能沿单向边功能改变。25. 正确1.5分解析两层循环最坏O(n²)。26. B3分解析边形成两个连通分量{1,2,3,6}和{4,5}。三阅读程序三27. 正确2分解析()匹配栈空输出 YES。28. 错误2分解析([)]中遇到)时栈顶为[不匹配输出 NO。29. 正确2分解析{入栈后循环结束栈非空flagfalse输出 NO。30. 正确2分解析每个字符处理一次时间复杂度 O(n)。31. 错误2分解析数字字符进入else若栈空则 flagfalse否则与栈顶比较不会越界stk[top--]在top0时访问合法。32. A5分解析({[]})括号完全匹配输出 YES。33. A5分解析((()))完全匹配输出 YES。三、完善程序题一二叉树的层序遍历34. A队列头指针初始化为 035. A队列尾指针初始化为 036. A当head tail时队列非空继续循环37. A左孩子非空! -1时才入队38. A右孩子非空! -1时才入队二最大连续子段和39. Aans初始为a[1]保证子段非空40. Adp[0] 0方便i1时判断41. A循环从 1 开始包含第一个元素42. A经典 Kadane 算法若前一个最大和为正则累加否则重新开始43. A若当前dp[i]更大则更新答案更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.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;}