附上汇总帖历年CSP-J初赛真题解析 | 汇总单项选择第1题1MB等于 。A.10000字节B.1024字节C.1000×1000字节D.1024×1024字节【答案】D【解析】1 M B 2 10 K B 2 20 B 1MB2^{10}KB2^{20}B1MB210KB220B第2题在PC机中 PENTIUM奔腾、酷睿、赛扬等是指 。A.生产厂家名称B.硬盘的型号C.CPU的型号D.显示器的型号【答案】C【解析】计算机常识都是CPU型号第3题操作系统的作用是 。A.把源程序译成目标程序B.便于进行数据管理C.控制和管理系统资源D.实现硬件之间的连接【答案】C【解析】同2014年控制和管理系统资源。A是编译器作用第4题在计算机内部用来传送、存贮、加工处理的数据或指令都是以 形式进行的。A.二进制码B.八进制码C.十进制码D.智能拼音码【答案】A【解析】计算机只认二进制数据第5题下列说法正确的是 。A.CPU的主要任务是执行数据运算和程序控制B.存储器具有记忆能力其中信息任何时候都不会丢失C.两个显示器屏幕尺寸相同则它们的分辨率必定相同D.个人用户只能使用Wifi的方式连接到Internet【答案】A【解析】B选项RAM断电后信息会丢失。C选项分辨率可能不同。D选项除无线外也可以使用有线方式接入Internet第6题二进制数00100100和00010100的和是 A.00101000B.01100111C.01000100D.00111000【答案】D【解析】2014年已经有过这道题11需要进位第7题与二进制小数0.1相等的十六进制数是 。A.0.8B.0.4C.0.2D.0.1【答案】A【解析】( 0.1 ) 2 1 ∗ 2 − 1 ( 0.5 ) 10 (0.1)_21*2^{-1}(0.5)_{10}(0.1)21∗2−1(0.5)10十进制小数转化为R进制小数部分 * R取整再用剩余数字 * R继续取整依次得到R进制小数后每一位直到取整后0.0第8题所谓的“中断”是指 。A.操作系统随意停止一个程序的运行B.当出现需要时CPU暂时停止当前程序的执行转而执行处理新情况的过程C.因停机而停止一个程序的运行D.电脑死机【答案】B【解析】计算机基础概念三短一长选最长第9题计算机病毒是 。A.通过计算机传播的危害人体健康的一种病毒B.人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C.一种由于计算机元器件老化而产生的对生态环境有害的物质D.利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒【答案】B【解析】计算机基础概念第10题FTP可以用于 。A.远程传输文件B.发送电子邮件C.浏览网页D.网上聊天【答案】A【解析】2014年有过类似的题File Transfer Protocol第11题下面哪种软件不属于即时通信软件 。A.QQB.MSNC.微信D.P2P【答案】D【解析】2014年有介绍过P2P如迅雷。MSNMicrosoft Service Network第12题6个顶点的连通图的最小生成树其边数为 。A.6B.5C.7D.4【答案】B【解析】n个点至少要n-1条边才能连通第13题链表不具备的特点是 。A.可随机访问任何一个元素B.插入、删除操作不需要移动元素C.无需事物估计存储空间大小D.所需存储空间与存储元素个数成正比【答案】A【解析】2013年有过类似的题链表不能随机访问需要从头遍历第14题线性表若采用链表存储结构要求内存中可用存储单元地址 。A.必须连接B.部分地址必须连接C.一定不连接D.连接不连接均可【答案】D【解析】内存地址可连续可不连续第15题今有一空栈S对下列待进栈的数据元素序列abcdef依次进行进栈进栈出栈进栈进栈出栈的操作则此操作完成后栈的栈顶元素为 A.fB.cC.aD.b【答案】B【解析】模拟画栈的图栈顶为c第16题前序遍历序列与中序遍历序列相同的二叉树为 。A.根结点无左子树B.根结点无右子树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树【答案】D【解析】根左右左根右相当于所有节点都没有“左”子树不仅仅是根节点没有“左”子树。第17题如果根的高度为1具有61个结点的完全二叉树的高度为 A.5B.6C.7D.8【答案】B【解析】2 n − 1 − 1 2^{n-1}-12n−1−1 完全二叉树节点总数 2 n − 1 2^n-12n−1第18题下列选项中不属于视频文件格式的是 。A.TXTB.AVIC.MOVD.RMVB【答案】A【解析】2014年考过txt是文本格式第19题某算法的计算时间表示为递推关系式T(n)T(n-1)nn为正整数及T(0)1则该算法的时间复杂度 。A.O ( l o g n ) O(logn)O(logn)B.O ( n l o g n ) O(n logn)O(nlogn)C.O(n)D.O ( n 2 ) O(n^2)O(n2)【答案】D【解析】T(n)T(n-1)nT(n-1)T(n-2)(n-1)T(n-2)T(n-3)(n-2)…T(2)T(1)2T(1)T(0)1全部加起来T(n)T(0)12…nn 2 2 n 2 1 \frac{n^2}{2}\frac{n}{2}12n22n1时间复杂度为O ( n 2 ) O(n^2)O(n2)问题求解第20题在NOI系列赛事中参赛选手必须使用累承办单位统一提供的设备。下列物品中不允许选手自带的是 。A.鼠标B.笔C.身份证D.准考证【答案】A【解析】不能自带鼠标第21题重新排列1234使得每一个数字都不在原来的位置上一共有 种排法。【答案】9【解析】枚举即可第1个数字是22143、2341、2413第1个数字是33142、3412、3421第1个数字是44123、4312、4312第22题一棵结点数为2015的二叉树最多有 个叶子结点。【答案】1008【解析】二叉树性质叶子节点个数度为2的节点个数12015个节点有11层第10层时有2 10 − 1 1023 2^{10}-11023210−11023个节点叶子节点个数为2015-1023992第10层有496个父节点再用512-49616。共992161008个阅读程序#includeiostreamusingnamespacestd;intmain(){inta,b,c;a1;b2;c3;if(ab){if(ac)couta ;elsecoutb ;}coutcendl;return0;}第23题输出 【答案】3【解析】模拟因为ab所以第6行至第第10行都不执行。最后只输出c#includeiostreamusingnamespacestd;structpoint{intx;inty;};intmain(){structEX{inta;intb;point c;}e;e.a1;e.b2;e.c.xe.ae.b;e.c.ye.a*e.b;coute.c.x e.c.yendl;return0;}第24题输出 【答案】3 2【解析】#includeiostream#includestringusingnamespacestd;intmain(){string str;inti;intcount;count0;getline(cin,str);for(i0;istr.length();i){if(str[i]astr[i]z)count;}coutIt has count lowercasesendl;return0;}第25题输入NOI2016 will be held in Mian Yang.输出 【答案】It has 18 lowercases【解析】题目是输出字符串中所有小写字母的数量共18个。#includeiostreamusingnamespacestd;voidfun(char*a,char*b){ab;(*a);}intmain(){charc1,c2,*p1,*p2;c1A;c2a;p1c1;p2c2;fun(p1,p2);coutc1c2endl;return0;}第26题输出 【答案】Ab第4行a b 就是 a c2那么第5行修改*a的值就是在修改c2的值完善程序质因数分解给出正整数n请输出将n质因数分解的结果结果从小到大输出。例如输入n120程序应该输出2 2 2 3 5表示1202×2×2×3×5.输入保证2≤n≤10^9。提示先从小到大枚举变量i然后用i不停试除n来寻找所有的质因子。试补全程序。#include cstdio using namespace std; int n, i; int main() { scanf(%d, n); for (i __1__; __2__ n; i ) { __3__ { printf(%d , i); n n / i; } } if(__4__) printf(%d , __5__); return 0; }第34题1处应填 A.1B.n-1C.2D.0【答案】C【解析】从2开始的每个因数拿来试除n选C第35题2处应填 A.n / iB.n / (i * i)C.i * iD.i * i * i【答案】C【解析】质因数分解只试除到小于等于n \sqrt{n}n的那些质因子选C第36题3处应填 A.if (n % i 0)B.if (i * i n)C.while (n % i 0)D.while (i * i n)【答案】C【解析】若n%i0则反复除获得多个质因数选C第37题4处应填 A.n 1B.n 1C.i n / iD.i i n【答案】A【解析】试除完所有小于等于√n的因子后n还有剩没有被除成1说明这个此时n的值就是那个唯一大于√n的质因子第38题5处应填 A.2B.n / iC.nD.i【答案】C【解析】参考第4题此时就应该输出n。例如n5时输出5最小区间覆盖给出n个区间第i个区间的左右端点是[a i a_iai,b i b_ibi]。现在要在这些区间中选出若干个使得区间[0,m]被所选区间的并覆盖即每一个0 ≤ i ≤ m 0\le i\le m0≤i≤m都在某个所选的区间中。保证答案存在求所选区间个数的最小值。输入第一行包含两个整数n和m( 1 ≤ n ≤ 5000 , 1 ≤ m ≤ 10 9 ) (1\le n\le 5000, 1\le m\le 10^9)(1≤n≤5000,1≤m≤109)。接下来n行每行两个整数a i a_iaib i ( 0 ≤ a i , b i ≤ m ) b_i(0\le a_i,b_i\le m)bi(0≤ai,bi≤m)。提示使用贪心法解决这个问题。现有O ( n 2 ) O(n^2)O(n2)的时间复杂度排序然后贪心选择这些区间。试补全程序。#includeiostreamusingnamespacestd;constintMAXN5000;intn,m;structsegment{inta,b;}A[MAXN];voidsort()// 排序{for(inti0;in;i)for(intj1;jn;j)if(__1__){segment tA[j];__2__}}intmain(){cinnm;for(inti0;in;i)cinA[i].aA[i].b;sort();intp1;for(inti1;in;i)if(__3__)A[p]A[i];np;intans0,r0;intq0;while(rm){while(__4__)q;__5__;ans;}coutansendl;return0;}第39题1处应填 A.A[j].bA[j-1].bB.A[j].aA[j-1].aC.A[j].aA[j-1].aD.A[j].bA[j-1].b【答案】B【解析】冒泡排序每次循环将左端点最大的线段排到最右边第40题2处应填 A.A[j1]A[j];A[j]t;B.A[j-1]A[j];A[j]t;C.A[j]A[j1];A[j1]t;D.A[j]A[j-1];A[j-1]t;【答案】D【解析】如果左侧线段的左端点更大左右交换第41题3处应填 A.A[i].bA[p-1].bB.A[i].bA[i-1].bC.A[i].bA[i-1].bD.A[i].bA[p-1].b【答案】A【解析】把被其他更大范围的线段覆盖的线段删除第42题4处应填 A.q1nA[q1].arB.q1nA[q1].brC.qnA[q].arD.qnA[q].br【答案】A【解析】下下一个线段存在且左端点在已覆盖区间右边界左侧则下个线段就被跳过。所以出while循环时会保留最后一个线段左端点在已覆盖区间右边界左侧第43题5处应填 A.rmax(r,A[q1].b)B.rmax(r,A[q].b)C.rmax(r,A[q1].a)D.q【答案】B【解析】确定新的已覆盖区间右边界
历年CSP-J初赛真题解析 | 2015年CSP-J初赛
发布时间：2026/7/19 9:54:53
附上汇总帖历年CSP-J初赛真题解析 | 汇总单项选择第1题1MB等于 。A.10000字节B.1024字节C.1000×1000字节D.1024×1024字节【答案】D【解析】1 M B 2 10 K B 2 20 B 1MB2^{10}KB2^{20}B1MB210KB220B第2题在PC机中 PENTIUM奔腾、酷睿、赛扬等是指 。A.生产厂家名称B.硬盘的型号C.CPU的型号D.显示器的型号【答案】C【解析】计算机常识都是CPU型号第3题操作系统的作用是 。A.把源程序译成目标程序B.便于进行数据管理C.控制和管理系统资源D.实现硬件之间的连接【答案】C【解析】同2014年控制和管理系统资源。A是编译器作用第4题在计算机内部用来传送、存贮、加工处理的数据或指令都是以 形式进行的。A.二进制码B.八进制码C.十进制码D.智能拼音码【答案】A【解析】计算机只认二进制数据第5题下列说法正确的是 。A.CPU的主要任务是执行数据运算和程序控制B.存储器具有记忆能力其中信息任何时候都不会丢失C.两个显示器屏幕尺寸相同则它们的分辨率必定相同D.个人用户只能使用Wifi的方式连接到Internet【答案】A【解析】B选项RAM断电后信息会丢失。C选项分辨率可能不同。D选项除无线外也可以使用有线方式接入Internet第6题二进制数00100100和00010100的和是 A.00101000B.01100111C.01000100D.00111000【答案】D【解析】2014年已经有过这道题11需要进位第7题与二进制小数0.1相等的十六进制数是 。A.0.8B.0.4C.0.2D.0.1【答案】A【解析】( 0.1 ) 2 1 ∗ 2 − 1 ( 0.5 ) 10 (0.1)_21*2^{-1}(0.5)_{10}(0.1)21∗2−1(0.5)10十进制小数转化为R进制小数部分 * R取整再用剩余数字 * R继续取整依次得到R进制小数后每一位直到取整后0.0第8题所谓的“中断”是指 。A.操作系统随意停止一个程序的运行B.当出现需要时CPU暂时停止当前程序的执行转而执行处理新情况的过程C.因停机而停止一个程序的运行D.电脑死机【答案】B【解析】计算机基础概念三短一长选最长第9题计算机病毒是 。A.通过计算机传播的危害人体健康的一种病毒B.人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C.一种由于计算机元器件老化而产生的对生态环境有害的物质D.利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒【答案】B【解析】计算机基础概念第10题FTP可以用于 。A.远程传输文件B.发送电子邮件C.浏览网页D.网上聊天【答案】A【解析】2014年有过类似的题File Transfer Protocol第11题下面哪种软件不属于即时通信软件 。A.QQB.MSNC.微信D.P2P【答案】D【解析】2014年有介绍过P2P如迅雷。MSNMicrosoft Service Network第12题6个顶点的连通图的最小生成树其边数为 。A.6B.5C.7D.4【答案】B【解析】n个点至少要n-1条边才能连通第13题链表不具备的特点是 。A.可随机访问任何一个元素B.插入、删除操作不需要移动元素C.无需事物估计存储空间大小D.所需存储空间与存储元素个数成正比【答案】A【解析】2013年有过类似的题链表不能随机访问需要从头遍历第14题线性表若采用链表存储结构要求内存中可用存储单元地址 。A.必须连接B.部分地址必须连接C.一定不连接D.连接不连接均可【答案】D【解析】内存地址可连续可不连续第15题今有一空栈S对下列待进栈的数据元素序列abcdef依次进行进栈进栈出栈进栈进栈出栈的操作则此操作完成后栈的栈顶元素为 A.fB.cC.aD.b【答案】B【解析】模拟画栈的图栈顶为c第16题前序遍历序列与中序遍历序列相同的二叉树为 。A.根结点无左子树B.根结点无右子树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树【答案】D【解析】根左右左根右相当于所有节点都没有“左”子树不仅仅是根节点没有“左”子树。第17题如果根的高度为1具有61个结点的完全二叉树的高度为 A.5B.6C.7D.8【答案】B【解析】2 n − 1 − 1 2^{n-1}-12n−1−1 完全二叉树节点总数 2 n − 1 2^n-12n−1第18题下列选项中不属于视频文件格式的是 。A.TXTB.AVIC.MOVD.RMVB【答案】A【解析】2014年考过txt是文本格式第19题某算法的计算时间表示为递推关系式T(n)T(n-1)nn为正整数及T(0)1则该算法的时间复杂度 。A.O ( l o g n ) O(logn)O(logn)B.O ( n l o g n ) O(n logn)O(nlogn)C.O(n)D.O ( n 2 ) O(n^2)O(n2)【答案】D【解析】T(n)T(n-1)nT(n-1)T(n-2)(n-1)T(n-2)T(n-3)(n-2)…T(2)T(1)2T(1)T(0)1全部加起来T(n)T(0)12…nn 2 2 n 2 1 \frac{n^2}{2}\frac{n}{2}12n22n1时间复杂度为O ( n 2 ) O(n^2)O(n2)问题求解第20题在NOI系列赛事中参赛选手必须使用累承办单位统一提供的设备。下列物品中不允许选手自带的是 。A.鼠标B.笔C.身份证D.准考证【答案】A【解析】不能自带鼠标第21题重新排列1234使得每一个数字都不在原来的位置上一共有 种排法。【答案】9【解析】枚举即可第1个数字是22143、2341、2413第1个数字是33142、3412、3421第1个数字是44123、4312、4312第22题一棵结点数为2015的二叉树最多有 个叶子结点。【答案】1008【解析】二叉树性质叶子节点个数度为2的节点个数12015个节点有11层第10层时有2 10 − 1 1023 2^{10}-11023210−11023个节点叶子节点个数为2015-1023992第10层有496个父节点再用512-49616。共992161008个阅读程序#includeiostreamusingnamespacestd;intmain(){inta,b,c;a1;b2;c3;if(ab){if(ac)couta ;elsecoutb ;}coutcendl;return0;}第23题输出 【答案】3【解析】模拟因为ab所以第6行至第第10行都不执行。最后只输出c#includeiostreamusingnamespacestd;structpoint{intx;inty;};intmain(){structEX{inta;intb;point c;}e;e.a1;e.b2;e.c.xe.ae.b;e.c.ye.a*e.b;coute.c.x e.c.yendl;return0;}第24题输出 【答案】3 2【解析】#includeiostream#includestringusingnamespacestd;intmain(){string str;inti;intcount;count0;getline(cin,str);for(i0;istr.length();i){if(str[i]astr[i]z)count;}coutIt has count lowercasesendl;return0;}第25题输入NOI2016 will be held in Mian Yang.输出 【答案】It has 18 lowercases【解析】题目是输出字符串中所有小写字母的数量共18个。#includeiostreamusingnamespacestd;voidfun(char*a,char*b){ab;(*a);}intmain(){charc1,c2,*p1,*p2;c1A;c2a;p1c1;p2c2;fun(p1,p2);coutc1c2endl;return0;}第26题输出 【答案】Ab第4行a b 就是 a c2那么第5行修改*a的值就是在修改c2的值完善程序质因数分解给出正整数n请输出将n质因数分解的结果结果从小到大输出。例如输入n120程序应该输出2 2 2 3 5表示1202×2×2×3×5.输入保证2≤n≤10^9。提示先从小到大枚举变量i然后用i不停试除n来寻找所有的质因子。试补全程序。#include cstdio using namespace std; int n, i; int main() { scanf(%d, n); for (i __1__; __2__ n; i ) { __3__ { printf(%d , i); n n / i; } } if(__4__) printf(%d , __5__); return 0; }第34题1处应填 A.1B.n-1C.2D.0【答案】C【解析】从2开始的每个因数拿来试除n选C第35题2处应填 A.n / iB.n / (i * i)C.i * iD.i * i * i【答案】C【解析】质因数分解只试除到小于等于n \sqrt{n}n的那些质因子选C第36题3处应填 A.if (n % i 0)B.if (i * i n)C.while (n % i 0)D.while (i * i n)【答案】C【解析】若n%i0则反复除获得多个质因数选C第37题4处应填 A.n 1B.n 1C.i n / iD.i i n【答案】A【解析】试除完所有小于等于√n的因子后n还有剩没有被除成1说明这个此时n的值就是那个唯一大于√n的质因子第38题5处应填 A.2B.n / iC.nD.i【答案】C【解析】参考第4题此时就应该输出n。例如n5时输出5最小区间覆盖给出n个区间第i个区间的左右端点是[a i a_iai,b i b_ibi]。现在要在这些区间中选出若干个使得区间[0,m]被所选区间的并覆盖即每一个0 ≤ i ≤ m 0\le i\le m0≤i≤m都在某个所选的区间中。保证答案存在求所选区间个数的最小值。输入第一行包含两个整数n和m( 1 ≤ n ≤ 5000 , 1 ≤ m ≤ 10 9 ) (1\le n\le 5000, 1\le m\le 10^9)(1≤n≤5000,1≤m≤109)。接下来n行每行两个整数a i a_iaib i ( 0 ≤ a i , b i ≤ m ) b_i(0\le a_i,b_i\le m)bi(0≤ai,bi≤m)。提示使用贪心法解决这个问题。现有O ( n 2 ) O(n^2)O(n2)的时间复杂度排序然后贪心选择这些区间。试补全程序。#includeiostreamusingnamespacestd;constintMAXN5000;intn,m;structsegment{inta,b;}A[MAXN];voidsort()// 排序{for(inti0;in;i)for(intj1;jn;j)if(__1__){segment tA[j];__2__}}intmain(){cinnm;for(inti0;in;i)cinA[i].aA[i].b;sort();intp1;for(inti1;in;i)if(__3__)A[p]A[i];np;intans0,r0;intq0;while(rm){while(__4__)q;__5__;ans;}coutansendl;return0;}第39题1处应填 A.A[j].bA[j-1].bB.A[j].aA[j-1].aC.A[j].aA[j-1].aD.A[j].bA[j-1].b【答案】B【解析】冒泡排序每次循环将左端点最大的线段排到最右边第40题2处应填 A.A[j1]A[j];A[j]t;B.A[j-1]A[j];A[j]t;C.A[j]A[j1];A[j1]t;D.A[j]A[j-1];A[j-1]t;【答案】D【解析】如果左侧线段的左端点更大左右交换第41题3处应填 A.A[i].bA[p-1].bB.A[i].bA[i-1].bC.A[i].bA[i-1].bD.A[i].bA[p-1].b【答案】A【解析】把被其他更大范围的线段覆盖的线段删除第42题4处应填 A.q1nA[q1].arB.q1nA[q1].brC.qnA[q].arD.qnA[q].br【答案】A【解析】下下一个线段存在且左端点在已覆盖区间右边界左侧则下个线段就被跳过。所以出while循环时会保留最后一个线段左端点在已覆盖区间右边界左侧第43题5处应填 A.rmax(r,A[q1].b)B.rmax(r,A[q].b)C.rmax(r,A[q1].a)D.q【答案】B【解析】确定新的已覆盖区间右边界
MySQL之索引初识篇：索引机制、索引分类、索引使用与管理综述)
