下载文档原格式
第24届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2 0 18 年10月13日14： 30-1 6:30选手注意：1、试题纸共有7页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上得一律无效。
2、不得使用任何电子设备（如计算器、手机、电子词典等）或査阅任何书籍资料。
一、单项选择题（共1 5题，每题2分，共计3 0分;每题有且仅有一个正确选项）1、以下哪一种设备属于输出设备：（）A、扫描仪B、键盘C、鼠标D、打印机2、下列四个不同进制得数中，与其它三项数值上不相等得就是（）。
A、（269）16 （注解：2 * l 6 入2 + 6 * 16^ 1 +9 * 1 6八0 = 617）B、（617）10C、（1 15 1）8 （注解：1 * 8入3 + 1 ± 8 ^2 +5 ^8^1+1 * 8^0 = 617）D、（1001101011） 23、1 MB 等于（）。
A、100 0字节B、 1 024字节C、 1 000 X 1000 字节D、1024 X 1024 字节4、广域网得英文缩写就是（）。
A、LANB、WAN （Wide Area Network）C、MAND、LNA5、中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。
A、 1 983B、19 8 4C、198 5D、19 8 66、如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 得顺序循环按键，即Ca psLock. A、S、I）、F、CapsLock. A、S、D、F ................. ，屏幕上输岀得第8 1个字符就是字母（）。
A、AB、SC、 DD、a7、根节点深度为0,—棵深度为h得满k（ k > 1 ）叉树，即除最后一层无任何子节点外, 每一层上得所有结点都有k个子结点得树，共有（）个结点。
![[NOIP]-CCFNOIP2018普及组初赛试题+答案](https://img.taocdn.com/s1/m/221de3b6f424ccbff121dd36a32d7375a417c647.png)
[NOIP]-CCFNOIP2018普及组初赛试题+答案第24届全国青少年信息学奥林匹克联赛初赛普及组C++语⾔试题竞赛时间：2018 年 10 ⽉ 13 ⽇ 14:30~16:30选⼿注意：1、试题纸共有 7 页，答题纸共有 2 页，满分 100 分。
请在答题纸上作答，写在试题纸上的⼀律⽆效。
2、不得使⽤任何电⼦设备（如计算器、⼿机、电⼦词典等）或查阅任何书籍资料。
⼀、单项选择题（共15题，每题2分，共计30分；每题有且仅有⼀个正确选项）1. 以下哪⼀种设备属于输出设备:( )A.扫描仪B.键盘C.⿏标2. 下列四个不同进制的数中，与其它三项数值上不相等的是( )。
A. (269)16 (注解：2 * 16^2 + 6 * 16^1 + 9 * 16 ^0 = 617)B. (617)10C. (1151)8 （注解：1 * 8^3 + 1 * 8^2 + 5 * 8^1 + 1 * 8^0 = 617）23. 1MB等于( )。
A. 1000 字节B. 1024 字节C. 1000 X 1000字节4. ⼴域⽹的英⽂缩写是( )。
A. LAN(Wide Area Network)C. MAND.LNA5. 中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。
A. 1983C. 1985D. 19866. 如果开始时计算机处于⼩写输⼊状态，现在有⼀只⼩⽼⿏反复按照 CapsLock、字母键 A、字母键S、字母键 D、字母键 F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、......，屏幕上输出的第 81 个字符是字母 ( )。
B. SC. DD. a7. 根节点深度为 0，⼀棵深度为 h 的满 k(k>1)叉树，即除最后⼀层⽆任何⼦节点外，每⼀层上的所有结点都有k个⼦结点的树，共有( )个结点。
C. k hD. (k h-1) / (k - 1)8. 以下排序算法中，不需要进⾏关键字⽐较操作的算法是( )。
例13-4迷宫寻宝【问题描述】一个n行m列的迷宫（1<=n,m<=5），入口在左上角，规定只能向下或向右走。
迷宫的某些地方藏有不同价值（>0）的宝藏，同时又存在一些障碍无法通过。
求到达右下角出口时收集宝藏的最大值。
【输入】第一行n和m一下n行m列描述迷宫矩阵a[I,j]（-1：障碍）；最大值【样例输入】342-150513-16-18910【样例输出】33【分析】A[I,j]保存第i行第j列的宝藏价值。
令f[I,j]为从（1，1）走到第i行第j列时所能收集的宝藏的最大价值。
状态转移方程：F[I,j]=max{f[I-1,j],f[I,j-1]}+a[I,j](i<=n,1<=m)条件：n[I,j]<>-1初始：f[1,1]=a[1,1]目标：f[n,m]【参考程序】Const maxn=50;maxm=50;Fin=’b1.in’;Fout=’b1.out’;VarF,a:array[0..maxn+1,0..maxm+1]of integer;I,j,k,n,m,t:integer;Procedure init;BeginAssign(input,fin);Reset(input);Readln(n,m);For i:=0to n+1doFor j:=0to m+1do a[I,j]:=-1;A[0,1]:=0;For i:=1to n doFor j:=1to m doBeginRead(a[I,j]);If(a[I,j-1]=-1)and(a[i-1,j]=-1)then a[I,j]:=-1;//很关键的预处理End;Close(input);End;Function max(a,b:integer):integer;Begin max:=a;if b>a then max:=b;end;Procedure work;BeginFillchar(f,sizeof(f),0);For i:=1to n doFor j:=1to m doIf a[I,j]<>-1Then f[I,j]:=max(f[i-1,j],f[I,j-1])+a[I,j];End;Procedure print;BeginAssign(output,fout);Rewrite(output);Writeln(f[n,m]);Close(output);End;BeginInit;Work;Print;End.13-5花店橱窗布置（IOI1999）【问题描述】假设你想以最美观的方式布置花店的橱窗。
第二十四届全国青少年信息学奥林匹克联赛初赛
提高组参考答案
一、单项选择题（共10题，每题2分，共计20分）
1 2 3 4 5 6 7 8 9 10
D D B A D B B A D B
二、不定项选择题（共5题，每题2分，共计10分；每题有一个或多个正确选项，没有部分分）
1 2 3 4 5
AB CD ABD ABD BCD
三、问题求解（共2题，每题5分，共计10分）
1.去了没去没去没下雨（第4空2分，其余1分）
2.454
四、阅读程序写结果（共4题，每题8分，共计32分）
1. 4
2. 6
3.16
4.输出1：2 1 3 5 6 4（3分）输出2：3 2 5 6 1 4（5分）
五、完善程序（共计28分，以下各程序填空可能还有一些等价的写法，由各省赛区组织本省专家审定及上机验证，可以不上报CCF NOI科学委员会复核）
Pascal语言C++语言C语言分值
1 . (1) a[x] := i a[x] = i 3
(2) i + 1 2
(3) R[a[i]] 3
(4) a[i] 3
(5) R[i] 3 2
2 . (1) a[i] * 0.95 <= b[i] 或b[i] >= a[i] * 0.95 2
(2)
total_a >= threshold 或threshold <= total_a 或total_a >= 50000 或50000 <=
total_a
3
(3) total_a + j + a[i] 3
(4) f[j] + total_b - total_b_prefix 3
(5) f[j - a[i]] 3。
2018年第二十四届全国青少年信息学奥林匹克联赛（NOIP 2018）广东赛区成绩公告2018年第二十四届全国青少年信息学奥林匹克联赛（NOIP 2018）广东赛区初赛实际参加人数为5201人（其中提高组1984人，普及组3217人），参赛学校337所。
复赛实际参赛人数为1469人（提高组647人，普及组822人）, 有资格参加复赛的学校有139所。
本届参赛选手程序全部由全国统一测评，其中提高组一等奖按分配名额划线，结果提高组317名同学（含初二21人，初三52人）获联赛一等奖。
今届广东省获提高组联赛一等奖分数线高出全国基准分数线65分，分数线在全国排第五，获奖人数在全国排第二，表明广东省信息学竞赛不仅普及面而且尖子层人数也在全国前列。
35年的实践表明，GDOI（广东省青少年信息学（计算机）奥林匹克竞赛活动）是培养我们国家、我省计算机优秀后备人才的成功之路。
今年提高组一、二、三等奖及普及组一、二、三等奖均由全国划定基准分数线及获奖比例，最后确认：提高组一、二、三等奖分数线分别为310、160、120，普及组一、二、三等奖分数线分别为215、100、70。
今年全国提高组一等奖分数线按初、复参赛人数及平均分计算，各省分数线差别很大，广东一等奖奖项大幅度地高于全国的基准分数线，同时，广东提高组平均分在296分以上，高于全国21个省的一等奖分数线。
按照广东省信息学竞赛评委会制定的评估方法，综合测评省内各校在开展计算机教学和科技活动中取得的成绩，从全省参加复赛的学校中评出成绩优异的前60所学校，其中校团体一等奖10所，二等奖20所，三等奖30所。
在个人奖方面，NOIP2018广东赛区复赛分数线按照中国计算机学会规定划定一、二、三等奖，边界同分同奖的规则。
获奖统计情况如下表所列：参赛人数省一等省二等省三等获奖总数提高647317人（占49%）234人（占36.17%）32人（占4.95%）583人（占90.11%）普及822214人（占26.03%）544人(占66.18%）10人(占1.22%）768人（占93.43%）总数1469531人（占36.15%）778人（占52.96%）42人（占2.86%）1351人（占91.97%）其中，提高组获奖人数（583人）占复赛90.11%，普及组获奖人数（768人）占复赛93.43%，全省获奖人数（1351人）占复赛总人数91.97%。
第24届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2018 年10 月13 日14:30~16:30选手注意：1、试题纸共有7 页，答题纸共有2 页，满分100 分。
请在答题纸上作答，写在试题纸上的一律无效。
2、不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）1. 以下哪一种设备属于输出设备:( )A.扫描仪B.键盘C.鼠标D.打印机2. 下列四个不同进制的数中，与其它三项数值上不相等的是( )。
A. (269)16 (注解：2 * 16^2 + 6 * 16^1 + 9 * 16 ^0 = 617)B. (617)10C. (1151)8 （注解：1 * 8^3 + 1 * 8^2 + 5 * 8^1 + 1 * 8^0 = 617）D. (1001101011)23. 1MB等于( )。
A. 1000 字节B. 1024 字节C. 1000 X 1000字节D. 1024 X 1024字节4. 广域网的英文缩写是( )。
A. LANB. WAN (Wide Area Network)C. MAND.LNA5. 中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。
A. 1983B. 1984C. 1985D. 19866. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、......，屏幕上输出的第81 个字符是字母( )。
A. AB. SC. DD. a7. 根节点深度为0，一棵深度为h 的满k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有( )个结点。
A. (k h+1-1)/(k-1)B. k h-1C. k hD. (k h-1) / (k - 1)8. 以下排序算法中，不需要进行关键字比较操作的算法是( )。
全国青少年信息学奥林匹克竞赛联赛试题大纲一、试题形式每次联赛的试题分四组：普及组初赛题A1、普及组复赛题A2、提高组初赛题B1和提高组复赛题B2。
其中，A1和B1类型一样，A2和B2类型一样，但题目不完全一样，提高组难度高于普及组。
〔一般初中学生参加普及组，高中或中专学生参加提高组〕初赛：初赛全部为笔试，总分值100分。
试题由四局部组成：1、选择题：共20题，每题1.5分，共计30分。
每题有5个备选答案，前10个题为单项选择题〔即每题有且只有一个正确答案，选对得分〕，后10题为不定项选择题〔即每题有1至5个正确答案，只有全部选对才得分〕。
2、问题求解题：共2题，每题5分，共计10分。
试题给出一个表达较为简单的问题，要求学生对问题进展分析，找到一个适宜的算法，并推算出问题的解。
考生给出的答案及标准答案一样，那么得分；否那么不得分。
3、程序阅读理解题：共4题，每题8分，共计32分。
题目给出一段程序〔不一定有关于程序功能的说明〕，考生通过阅读理解该段程序给出程序的输出。
输出及标准答案一致，那么得分；否那么不得分。
4、程序完善题：共2题，每题14分，共计28分。
题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了假设干个语句或语句的一局部并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。
填对那么得分；否那么不得分。
复赛：复赛的题型和考试形式及NOI类似，全部为上机编程题，但难度比NOI低。
题目包括4道题，每题100分，共计400分。
每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。
测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得10－20分，累计分即为该道题的得分。
二、试题的知识范围1．初赛内容及要求：2、复赛内容及要求：在初赛的内容上增加以下内容。
NOIP2018初赛普及组C++题目+解析二十四届全国青少年信息学奥林匹克联赛初赛——普及组一、单项选择题（共15 题，每题2 分，共计30 分；每题有且仅有一个正确选项）1. 以下哪一种设备属于输出设备：（）A. 扫描仪B. 键盘C. 鼠标D. 打印机答案:D解析:扫描仪是输出设备显而易见2. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。
A. (269)16B. (617)10C. (1151)8D. (1001101011)2答案: D解析：都转成二进制，然后前3个都是1001101001，跟D不同3. 1MB 等于（）。
A. 1000 字节B. 1024 字节C. 1000 X 1000 字节D. 1024 X 1024 字节答案:D解析:1 M B = 1024 K B = 1024 ∗1024 B1MB=1024KB=1024*1024B1MB=1024KB=1024∗1024B 4. 广域网的英文缩写是（）。
B. WANC. MAND. LNA广域网（英语：Wide Area Network，缩写为WAN），又称广域网、外网、公网。
是连围从几十公里到几千公里，它能连接多个地区、城市和国家，或横跨几个洲并能提供远距LAN（Local Area Network (缩写:LAN)）局域网的覆盖范围一般是方圆几千米之内，其具备的安装便捷、成本节约、扩展方便等特点使其在各类办公室内运用广泛。
局域网可以实现全，能够有效地保护资料安全，保证局域网网络能够正常稳定的运行。
答案:B A是局域网C是城域网5. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。
A. 1983B. 1984D. 1986答案:B6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81 个字符是字母（）。
![[NOIP]-CCFNOIP2018普及组初赛试题+答案](https://img.taocdn.com/s1/m/7714569da1116c175f0e7cd184254b35eefd1a8e.png)
[NOIP]-CCFNOIP2018普及组初赛试题+答案第24届全国青少年信息学奥林匹克联赛初赛普及组C++语⾔试题竞赛时间：2018 年 10 ⽉ 13 ⽇ 14:30~16:30选⼿注意：1、试题纸共有 7 页，答题纸共有 2 页，满分 100 分。
请在答题纸上作答，写在试题纸上的⼀律⽆效。
2、不得使⽤任何电⼦设备（如计算器、⼿机、电⼦词典等）或查阅任何书籍资料。
⼀、单项选择题（共15题，每题2分，共计30分；每题有且仅有⼀个正确选项）1. 以下哪⼀种设备属于输出设备:( )A.扫描仪B.键盘C.⿏标2. 下列四个不同进制的数中，与其它三项数值上不相等的是( )。
A. (269)16 (注解：2 * 16^2 + 6 * 16^1 + 9 * 16 ^0 = 617)B. (617)10C. (1151)8 （注解：1 * 8^3 + 1 * 8^2 + 5 * 8^1 + 1 * 8^0 = 617）23. 1MB等于( )。
A. 1000 字节B. 1024 字节C. 1000 X 1000字节4. ⼴域⽹的英⽂缩写是( )。
A. LAN(Wide Area Network)C. MAND.LNA5. 中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。
A. 1983C. 1985D. 19866. 如果开始时计算机处于⼩写输⼊状态，现在有⼀只⼩⽼⿏反复按照 CapsLock、字母键 A、字母键S、字母键 D、字母键 F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、......，屏幕上输出的第 81 个字符是字母 ( )。
B. SC. DD. a7. 根节点深度为 0，⼀棵深度为 h 的满 k(k>1)叉树，即除最后⼀层⽆任何⼦节点外，每⼀层上的所有结点都有k个⼦结点的树，共有( )个结点。
C. k hD. (k h-1) / (k - 1)8. 以下排序算法中，不需要进⾏关键字⽐较操作的算法是( )。
第十四届全国青少年信息学奥林匹克联赛初赛试题（提高组 C++ 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确答案）。
1. 在以下各项中，（）不是操作系统软件。
A. SolarisB. LinuxC. SybaseD. Windows VistaE. Symbian 2．微型计算机中，控制器的基本功能是（）。
A. 控制机器各个部件协调工作B. 实现算术运算和逻辑运算C.存储各种控制信息D. 获取外部信息E. 存放程序和数据3. 设字符串S=”Olympic”，S的非空子串的数目是（）。
A. 29B. 28C. 16D. 17E. 74．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。
A. N-1B. 2*NC. ND. 2N-1E. N/25．将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。
A. 4B. 5C. 6D. 7E. 86．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，则栈S 的容量至少应该是（）。
A. 6B. 5C. 4D. 3E. 27. 与十进制数28.5625相等的四进制数是（）。
A. 123.21B. 131.22C. 130.22D. 130.21E. 130.208．递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。
A. 队列B. 多维数组C. 线性表D. 链表E. 栈9. TCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。
TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。
关于第二十四届全国青少年信息学(计算机)奥林匹克联赛（NOIP2018）获奖情况的通报各镇（街）宣教办（局），松山湖科教局，各中小学，市青少年活动中心：第二十四届全国青少年信息学（计算机）奥林匹克联赛（NOIP2018）顺利结束。
根据全国和省学科竞赛委员会统一划定的获奖分数线，我市学生在高手如林的竞赛中，再创佳绩：获全国一等奖51人、全国二等奖140人、全国三等奖8人，一等奖人数比2017年增加7人，获全国一等奖人数列全省第四名。
根据全国和省组委会划定的初赛和复赛的评奖分数线，本次活动评出了市学校团体奖、市学生个人奖和优秀辅导教师若干名。
现给予通报表彰，并颁发获奖证书以资奖励。
希望获奖的学校和个人戒骄戒躁，再接再厉，进一步提高学习和训练水平，争取在今后的竞赛中取得更好成绩。
也希望其他学校向他们学习，积极开展信息技术教育，大力开展中学生普及计算机基础知识活动，为培养更多的计算机科学与工程领域后备人才作出新的更大的贡献。
附件：第二十四届全国青少年信息学奥林匹克联赛（NOIP2018）获奖名单一、团体奖一等奖东莞市东莞中学松山湖学校、东莞市东华高级中学、东莞市东莞中学、东莞外国语学校、东莞市东华初级中学、东莞市东莞中学南城学校、东莞市东莞中学初中部、东莞市新世纪英才学校二等奖东莞市第一中学、东莞市石龙中学、东莞市莞城少年宫、东莞市可园中学、东莞市望牛墩中学、东莞市石龙第二中学、东莞市石龙第三中学、东莞市南城阳光实验中学、东莞市松山湖实验中学、东莞市东城第一中学三等奖东莞市第六高级中学、东莞市塘厦初级中学、东莞市常平镇振兴中学、东莞市中堂中学、东莞市万江第三中学二、个人奖名单2.提高组获全国一、二、三等奖4、提高组获市一、二、三等奖名单5.优秀辅导教师奖。
第二十四届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题竞赛时间：2018 年 10 月 13 日 14:30~16:30(WORD重新整理排版)选手注意：●试题纸共有 9 页，答题纸共有 2 页，满分 100 分。
请在答题纸上作答，写在试题纸上的一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共 10 题，每题 2 分，共计 20 分；每题有且仅有一个正确选项）1. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。
A. (269)16B. (617)10C. (1151)8D. (1001101011)22. 下列属于解释执行的程序设计语言是（）。
A. CB. C++C. PascalD. Python3. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。
A. 1983B. 1984C. 1985D. 19864. 设根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（）个结点。
A. (k h+1 - 1) / (k - 1)B. k h-1C. k hD. (k h-1 ) / (k - 1)5. 设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（）。
A. O(log n)B. O(n log n)C. O(n)D. O(n2 )6. 表达式 a * d - b * c 的前缀形式是（）。
A. a d * b c * -B. - * a d * b cC. a * d - b * cD. - * * a d b c7. 在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。
A. 1 / 2B. 1 / 3C. 2 / 3D. 3 / 58. 关于 Catalan 数 Cn = (2n)! / (n + 1)! / n!，下列说法中错误的是（）。
第二十四届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题竞赛时间：2018 年 10 月 13 日 14:30~16:30(WORD重新整理排版)选手注意：●试题纸共有 9 页，答题纸共有 2 页，满分 100 分。
请在答题纸上作答，写在试题纸上的一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共 10 题，每题 2 分，共计 20 分；每题有且仅有一个正确选项）1. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。
A. (269)16B. (617)10C. (1151)8D. (1001101011)22. 下列属于解释执行的程序设计语言是（）。
A. CB. C++C. PascalD. Python3. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。
A. 1983B. 1984C. 1985D. 19864. 设根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（）个结点。
A. (k h+1 - 1) / (k - 1)B. k h-1C. k hD. (k h-1 ) / (k - 1)5. 设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（）。
A. O(log n)B. O(n log n)C. O(n)D. O(n2 )6. 表达式 a * d - b * c 的前缀形式是（）。
A. a d * b c * -B. - * a d * b cC. a * d - b * cD. - * * a d b c7. 在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。
A. 1 / 2B. 1 / 3C. 2 / 3D. 3 / 58. 关于 Catalan 数 Cn = (2n)! / (n + 1)! / n!，下列说法中错误的是（）。
A. Cn 表示有 n + 1 个结点的不同形态的二叉树的个数。
B. Cn 表示含 n 对括号的合法括号序列的个数。
C. Cn 表示长度为 n 的入栈序列对应的合法出栈序列个数。
D. Cn 表示通过连接顶点而将 n + 2 边的凸多边形分成三角形的方法个数。
9. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。
有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。
最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（）。
A. 1 : 2B. 2 : 1C. 1 : 3D. 1 : 110. 为了统计一个非负整数的二进制形式中 1 的个数，代码如下：int CountBit(int x){int ret = 0;while (x){ret++;________;}return ret;}则空格内要填入的语句是（）。
A. x >>= 1B. x &= x - 1C. x |= x >> 1D. x <<= 1二、不定项选择题（共 5 题，每题 2 分，共计 10 分；每题有一个或多个正确选项，多选或少选均不得分）1. NOIP 初赛中，选手可以带入考场的有（）。
A. 笔B. 橡皮C. 手机（关机）D. 草稿纸2. 2-3 树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同。
如果一棵 2-3 树有 10 个叶结点，那么它可能有（）个非叶结点。
A. 5B. 6C. 7D. 83. 下列关于最短路算法的说法正确的有（）。
A. 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。
B. 当图中不存在负权边时，调用多次 Dijkstra 算法能求出每对顶点间最短路径。
C. 图中存在负权回路时，调用一次 Dijkstra 算法也一定能求出源点到所有点的最短路。
D. 当图中不存在负权边时，调用一次 Dijkstra 算法不能用于每对顶点间最短路计算。
4. 下列说法中，是树的性质的有（）。
A. 无环B. 任意两个结点之间有且只有一条简单路径C. 有且只有一个简单环D. 边的数目恰是顶点数目减 15. 下列关于图灵奖的说法中，正确的有（）。
A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。
B. 目前获得该奖项的华人学者只有姚期智教授一人。
C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
三、问题求解（共 2 题，每题 5 分，共计 10 分）1. 甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。
如果周末丙去了，则甲________（去了/没去）(1 分)，乙________（去了/没去）(1 分)，丁________（去了/没去）(1 分)，周末________（下雨/没下雨）(2 分)。
2. 方程 a*b = (a or b) * (a and b)，在 a,b 都取 [0, 31] 中的整数时，共有_____组解。
（*表示乘法；or 表示按位或运算；and 表示按位与运算）四、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1.#include <cstdio>int main() {int x;scanf("%d", &x);int res = 0;for (int i = 0; i < x; ++i) {if (i * i % x == 1) {++res;}}printf("%d", res);return 0;}输入：15输出：__________2.#include <cstdio>int n, d[100];bool v[100];int main() {scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d", d + i);v[i] = false;}int cnt = 0;for (int i = 0; i < n; ++i) {if (!v[i]) {for (int j = i; !v[j]; j = d[j]) {v[j] = true;}++cnt;}}printf("%d\n", cnt);return 0;}输入： 10 7 1 4 3 2 5 9 8 0 6输出：___________3.#include <iostream>using namespace std;string s;long long magic(int l, int r) {long long ans = 0;for (int i = l; i <= r; ++i) {ans = ans * 4 + s[i] - 'a' + 1;}return ans;}int main() {cin >> s;int len = s.length();int ans = 0;for (int l1 = 0; l1 < len; ++l1) {for (int r1 = l1; r1 < len; ++r1) {bool bo = true;for (int l2 = 0; l2 < len; ++l2) {for (int r2 = l2; r2 < len; ++r2) {if (magic(l1, r1)==magic(l2, r2) &&(l1!=l2 || r1!=r2)) {bo = false;}}}if (bo) {ans += 1;}}}cout << ans << endl;return 0;}输入：abacaba输出：________________4.#include <cstdio>using namespace std;const int N = 110;bool isUse[N];int n, t;int a[N], b[N];bool isSmall() {for (int i = 1; i <= n; ++i)if (a[i] != b[i]) return a[i] < b[i];return false;}bool getPermutation(int pos) {if (pos > n) {return isSmall();}for (int i = 1; i <= n; ++i) {if (!isUse[i]) {b[pos] = i; isUse[i] = true;if (getPermutation(pos + 1)) {return true;}isUse[i] = false;}}return false;}void getNext() {for (int i = 1; i <= n; ++i) {isUse[i] = false;}getPermutation(1);for (int i = 1; i <= n; ++i) {a[i] = b[i];}}int main() {scanf("%d%d", &n, &t);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}for (int i = 1; i <= t; ++i) {getNext();}for (int i = 1; i <= n; ++i) {printf("%d", a[i]);if (i == n) putchar('\n'); else putchar(' ');}return 0;}输入1：6 10 1 6 4 5 3 2输出1：__________（3分）输入2：6 200 1 5 3 4 2 6输出2：__________（5分）五、完善程序（共共 2 题，每题 14 分，共计 28 分）1. 对于一个1到n的排列P（即1到n中每一个数在P中出现了恰好一次），令q i为第个位置之后第一个比P i值更大的位置，如果不存在这样的位置，则q i=n +1。
