附上汇总帖历年CSP-J初赛真题解析 | 汇总单项选择题第1题一个32位整型变量占用 个字节。A.4B…8C.32D.128【答案】A【解析】基本单位是字节位是最小单位。1个字节8位32位就是4个字节第2题二进制数11.01在十进制下是 。A.3.25B.4.125C.6.25D.11.125【答案】A【解析】2 1 2 0 2 − 1 2 − 2 3.25 2^12^02^{-1}2^{-2}3.2521202−12−23.25第3题下面的故事与 算法有着异曲同工之妙。从前有座山山里有座庙庙里有个老和尚在给小和尚讲故事从前有座山山里有座庙庙里有个老和尚在给小和尚讲故事从前有座山山里有座庙庙里有个老和尚给小和尚讲故事…A.枚举B.递归C.贪心D.分治【答案】B【解析】自己调用自己第4题逻辑表达式 的值与变量A的真假无关。A.( A ∨ B ) ∧ ¬ A (A\lor B)\land \lnot A(A∨B)∧¬AB.( A ∨ B ) ∧ ¬ B (A\lor B)\land \lnot B(A∨B)∧¬BC.( A ∧ B ) ∨ ( ¬ A ∧ B ) (A\land B)\lor (\lnot A\land B)(A∧B)∨(¬A∧B)D.( A ∨ B ) ∧ ¬ A ∧ B (A\lor B)\land \lnot A\land B(A∨B)∧¬A∧B【答案】C【解析】A0,B0A1,B0A0,B1A1,B1( A ∨ B ) ∧ ¬ A (A\lor B)\land \lnot A(A∨B)∧¬A0010( A ∨ B ) ∧ ¬ B (A\lor B)\land \lnot B(A∨B)∧¬B01( A ∧ B ) ∨ ( ¬ A ∧ B ) (A\land B)\lor (\lnot A\land B)(A∧B)∨(¬A∧B)0011( A ∨ B ) ∧ ¬ A ∧ B (A\lor B)\land \lnot A\land B(A∨B)∧¬A∧B第5题将(261017)分别存储到某个地址区间为0~10的哈希表中如果哈希函数h(x) 将不会产生冲突 其中a mod b表示a除以b的余数。A.x mod 11B.x 2 x^2x2mod 11C.2x mod 11D.⌊ x ⌋ \lfloor \sqrt x\rfloor⌊x⌋mod 11 其中⌊ ⌋ \lfloor \ \rfloor⌊⌋表示向下取整【答案】D【解析】哈希表散列表根绝关键码值直接访问的数据结构根据计算结果从小到大存入不冲突表示h(x)计算结果不同261017x mod 1126106x 2 x^2x2mod 1143132x mod 114191⌊ x ⌋ \lfloor \sqrt x\rfloor⌊x⌋mod 111234第6题在十六进制表示法中字母A相当于十进制中的 。A.9B.10C.15D.16【答案】B【解析】16进制0,1,2,3,4,5,6,7,8,9,A,B,C,D,E对应10进制0~15第7题下图中所使用的数据结构是 。A.哈希表B.栈C.队列D.二叉树【答案】B【解析】后进先出的数据结构属于栈第8题在Windows资源管理器中 用鼠标右键单击一个文件时 会出现一个名为“复制”的操作选项它的意思是 。A.用剪切板中的文件替换该文件B.在该文件所在文件夹中将该文件克隆一份C.将该文件复制到剪切板并保留原文件D.将该文件复制到剪切板并删除原文件【答案】C【解析】复制文件保留第9题已知一棵二叉树有10个节点则其中至多有 个节点有2个子节点。A.4B.5C.6D.7【答案】A【解析】设有x个节点有2个子节点则至少还有2x个节点这2x个节点可能与前x个节点重合最多重合x-1个则整棵树最少有x2x-(x-1)2x1个2x1≤10解得x4第10题在一个无向图中如果任意两点之间都存在路径相连则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图至少要删去其中的 条1边。A.1B.2C.3D.4【答案】C【解析】每个节点有都3条边与别的节点相连至少删3条边第11题二叉树的 第一个访问的节点是根节点。A.先序遍历B.中序遍历C.后序遍历D.以上都是【答案】A【解析】先序遍历根左右中序遍历左根右后续遍历左右根第12题以A0作为起点对下面的无向图进行深度优先遍历时遍历顺序不可能是 。A.A0A1A2A3B.A0A1A3A2C.A0A2A1A3D.A0A3A1A2【答案】A【解析】A0, A1, A3, A2A0, A3, A1, A2A0, A2, A1, A3A0, A2, A3, A1访问A1后没有到底不能访问A2第13题IPv4协议使用32位地址 随着其不断被分配 地址资源日趋枯竭。因此它正逐渐被使用 位地址的IPv6协议所取代。A.40B.48C.64D.128【答案】D【解析】IPv6地址是128位第14题 的平均时间复杂度为O(nlogn) 其中n是待排序的元素个数。A.快速排序B.插入排序C.冒泡排序D.基数排序【答案】A【解析】快排的时间复杂度就是O(nlogn)插入和冒泡的平均时间复杂度是O ( n 2 ) O(n^2)O(n2)基数排序由待排数字的位数决定第15题下面是根据欧几里得算法编写的函数它所计算的是a和b的 。inteuclid(inta,intb){if(b0)returna;elsereturneuelid(b,a%b);}A.最大公共质因子B.最小公共质因子C.最大公约数D.最小公倍数【答案】C【解析】辗转相除法求最大公约数第16题通常在搜索引擎中对某个关键词加上双引号表示 。A.排除关键词不显示任何包含该关键词的结果B.将关键词分解在搜索结果中必须包含其中的一部分C.精确搜索只显示包含整个关键词的结果D.站内搜索只显示关键词所指向网站的内容【答案】C【解析】加双引号是为了严格匹配搜索第17题中国的国家顶级域名是 。A.cnB.chC.chnD.china【答案】A【解析】.cn是中国顶级域名china的简写。.ch是瑞士的第18题把64位非零浮点数强制转换成32位浮点数后不可能 。A.大于原数B.小于原数C.等于原数D.与原数符号相反【答案】D【解析】浮点数由符号位、尾码、解码组成double类型转为float符号位不变精确位数不确定第19题下列程序中 正确计算1 2 … 100这100个自然数之和sum初始值为0的是 。A.AB.BC.CD.D【答案】A【解析】i必须要≤100只有A选项满足第20题CCF NOIP复赛全国统一评测时使用的系统软件是 。A.NOI WindowsB.NOI LinuxC.NOI MacOSD.NOI DOS【答案】B【解析】NOI Linux北航开发的问题求解第21题7个同学围坐一圈要选2个不相邻的作为代表有 种不同的选法。【答案】14【解析】多少个不相邻的代表就是求n边行有多少条对角线n*(n-3)/214第22题某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s 1 , s 2 , … , s n s_1,s_2,\dots,s_ns1,s2,…,sn 均为0或1。该系统每次随机生成n个数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an 均为0或1 请用户回答s 1 a 1 s 2 a 2 ⋯ s n a n s_1a_1s_2a_2\dots s_na_ns1a1s2a2⋯snan除以2的余数。如果多次的回答总是正确即认为掌握密码。该系统认为即使问答的过程被泄露也无助于破解密码——因为用户并没有直接发送密码。然而事与愿违。例如当n4时有人窃听了以下5次问答就破解出了密码s 1 s_1s1 s 2 s_2s2 s 3 s_3s3 s 4 s_4s4 。【答案】0 1 1 1【解析】第1组(s1 s2) mod 2 1 - s212第2组(s3 s4) mod 2 0 - s414第3组(s2 s3 s4 ) mod 2 0第4组(s1s2s3) mod 2 0 - s313第5组s1 mod 2 0 - s101阅读程序#includeiostreamusingnamespacestd;intmain(){inta,b;cinab;coutababendl;}第23题输入3 5输出 【答案】358【解析】简单注意格式输出内容中没有空格#includeiostreamusingnamespacestd;intmain(){inta,b,u,i,num;cinabu;num0;for(ia;ib;i)if((i%u)0)num;coutnumendl;return0;}第24题输入1 100 15输出 【答案】6【解析】在1到100中如果是u的倍数num答案为6#includeiostreamusingnamespacestd;intmain(){constintSIZE100;intn,f,i,left,right,middle,a[SIZE];cinnf;for(i1;in;i)cina[i];left1;rightn;do{middle(leftright)/2;if(fa[middle])rightmiddle;elseleftmiddle1;}while(leftright);coutleftendl;return0;}第25题输入12 172 4 6 9 11 15 17 18 19 20 21 25输出 【答案】7【解析】二分法查找f那个数字所在的下标#includeiostreamusingnamespacestd;intmain(){constintSIZE100;intheight[SIZE],num[SIZE],n,ans;cinn;for(inti0;in;i){cinheight[i];num[i]1;for(intj0;ji;j){if((height[j]height[i])(num[j]num[i]))num[i]num[j]1;}}ans0;for(inti0;in;i){if(num[i]ans)ansnum[i];}coutansendl;}第26题输入62 5 3 11 12 4输出 【答案】4【解析】求最长上升子序列代码7-12行求出num数组1 2 2 3 4 3代码16-17用来求num数组中的最大值为4完善程序序列重排全局数组变量a定义如下cosntintSIZE100;inta[SIZE],n;它记录着一个长度为n的序列a[1],a[2],…,a[n]。现在需要一个函数以整数p(1≤p≤n)为参数实现如下功能将序列a的前p个数与后n-p个数对调且不改变这p个数或n-p个数之间的相对位置。例如长度为5的序列1,2,3,4,5当p2时重排结果为345 12。有一种朴素的算法可以实现这一需求其时间复杂度为O(n)空间复杂度为O(n)。voidswap(intp){inti,j,b[SIZE];for(i1;ip;i)b[__1__]a[i];for(ip1;in;i)b[i-p]__2__;for(i1;i__3__;i)a[i]b[i];}我们也可以利用时间换空间使用时间复杂度为O ( n 2 ) O(n^2)O(n2)空间复杂度为O(1)的算法voidswap2(intp){inti,j,temp;for(ip1;in;i){tempa[i];for(ji;j__4__;j--)a[j]a[j-1];__5__temp;}}第27题第一空填 。【答案】n-pi【解析】a[1] - b[n-p1]…a[n] - b[p]a和b的下标的差值保持一致所以a[i] - b[p-ni]第28题第二空填 。【答案】a[i]【解析】a[p1] - b[1]…a[n] - b[n-p]a和b的下标的差值保持一致所以a[i] - b[i-p]第29题第三空填 。【答案】n【解析】需要将b数组的内容重新拷贝回a数组中第30题第四空填 。【答案】i-p1【解析】每次挪动一部分单元格向右移一位第一次挪动a[1]~a[p]第二次挪动a[2]~a[p1]元素个数为p个所以对于a[?]~a[i]?i-p1第31题第五空填 。【答案】i-p【解析】a[p1] - a[1]a[p2] - a[2]…a[i] - a[i-p]二叉查找二叉查找树具有如下性质每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一个树是否为二叉查找树。输入的第一行包含一个整数n表示这棵树有n个顶点编号分别为1,2,…,n其中编号为1的为根节点。之后的第i行有三个数valueleft_childright_child分别表示该节点关键字的值左子节点的编号右子节点的编号如果不存在左子节点或右子节点则用0代替。输出1表示这棵树是二叉查找树输出0则表示不是。#includeiostreamusingnamespacestd;constintSIZE100;constintINFINITE1000000;structnode{intleft_child,right_child,value;};node a[SIZE];intis_bst(introot,intlower_bound,intupper_bound){intcur;if(root0)return1;cura[root].value;if((curlower_bound)(__1__)(is_bst(a[root].left_child,lower_bound,cur)1)(is_bst(__2__,__3__,__4__)1))return1;return0;}intmain(){inti,n;cinn;for(i1;in;i)cina[i].valuea[i].left_childa[i].right_child;coutis_bst(__5__,-INFINITE,INFINITE)endl;return0;}第32题1处填 【答案】curupper_bound【解析】每个子树的根的值一定要大于其左子树且小于右子树第33题2处填 【答案】a[root].right_child【解析】以右子树的节点作为其下层递归的根节点第34题3处填 【答案】cur【解析】左边界设置为cur第35题4处填 【答案】upper_bound【解析】右边界保持之前upper_bound第36题5处填 【答案】1【解析】以1为根节点进行搜索
