NOIP信息学奥赛普及组初赛C++试题
NOIP2016第二十二届全国青少年信息学奥林匹克联赛初赛
普及组C++语言试题
竞赛时间：2016年10月22日14:30～16:30
一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）
1．以下不是微软公司出品的软件是( )。
A．Powerpoint B．Word C.Excel D. Acrobat Reader
2．如果256种颜色用二进制编码来表示，至少需要( )位。
A．6 B．7 C．8 D．9
3．以下不属于无线通信技术的是( )。
A．蓝牙B．WiFi C．GPRS D．以太网
4．以下不是CPU生产厂商的是( )。
A.Intel
B.AMD
C.Microsoft
D.IBM
5．以下不是存储设备的是( )。
A．光盘B．磁盘C．固态硬盘D．鼠标
6．如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S 和字母键D的顺序循环按键，即CapsLock、A、S、D、CapsLock、A、S、D、……，屏幕上输出的第81个字符是字母( )。
A．A B．S C．D D．a
7．二进制数00101100和00010101的和是( )。
A.00101000
B.01000001
C.01000100
D.
8．与二进制小数0.1相等的八进制数是( )。
A．0.8 B．0.4 C．0.2 D．0.1
9．以下是32位机器和64位机器的区别的是( )。
A．显示器不同B．硬盘大小不同
C．寻址空间不同D．输入法不同
10．以下关于字符串的判定语句中正确的是( )
A．字符串是一种特殊的线性表B．串的长度必须大于零
C．字符串不可以用数组来表示D．空格字符组成的串就是空串
11．一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二
叉树中的结点（根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、
右孩子位于下标(2i+1)处），则图中所有结点的最大下标为( ) 。
A.6 B．10 C．12 D．15
12．若有如下程序段，其中s、a、b、c均己定义为整型变量，且a、c均己赋值（c大于0）。
s=a;
for (b=1;b<=c;b++)
s=s+1;
则与上述程序段修改s值的功能等价的赋值语句是( )。
A. s=a+b;
B. s=a+c;
C. s=s+c;
D. s=b+c;
13．有以下程序：
#include
using namespace std;
int main() {
int k=4,n=0;
while(n n++; if (n%3!=0) conntinue; k--; ) cout< return O; ) 程序运行后的输出结果是( )。 A．2,2 B．2,3 C．3,2 D．3,3 14.给定含有n个不同的数的数组L= 正确的填空顺序是( )。 A.c,a,b B. c,b,a C.a,b,c D.b,a,c 15．设简单无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 A．10 B．12 C．8 D．16 16．有7个一模一样的苹果，放到3个一样的盘子中，一共有( )种放法。 A．7 B．8 C．21 D．37 17．下图表示一个果园灌溉系统，有A、B、C、D四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的是( )。 A．B打开，其他都关上B．AB都打开，CD都关上 C．A打开，其他都关上D．D打开，其他都关上 18．Lucia和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人A向他（她）的朋友B分享了某张照片，那么B就可以对该照片进行评论；如果B评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非A也向他（她）分享了该照片）。现在Lucia已经上传了一张照片，但是她不想让Jacob看见这张照片，那么她可以向以下朋友( )分享该照片。 A.Dana, Michael, Eve B.Dana, Eve, Monica C.Michael, Eve, Jacob D.Micheal, Peter, Monica 19．周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜10分钟，然后切菜10分钟，最后炒菜10分钟。那么做一道菜需要30分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要( )分钟。 A．90 B．60 C．50 D．40 20．参加NOI比赛，以下不能带入考场的是( )。 A．钢笔B．适量的衣服C．U盘D．铅笔 二、问题求解（共2题，每题5分，共计10分；第一题全部答对得5分，没有部分分；第二题第一空2分，第二空3分） 1．从一个4×4的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有_______种方法。2．约定二叉树的根节点高度为1。一棵结点数为2016的二叉树最少有________个叶子结点；一棵结点数为2016的二叉树最小的高度值是___________。 三、阅读程序写结果（共4题，每题8分，共计32分） 1.#include using namespace std; int main() { int max, min, sum, count=0; int tmp; cin>>tmp; if (tmp==0) return 0; max=min=sum=tmp; count++; while (tmp!=0) { cin>>tmp; if (tmp!=0) { sum+=tmp; count++; if (tmp>max) max=tmp; if (tmp } } cout< return 0; } 输入：1 2 3 4 5 6 0 7 输出：2.#include using namespace std; int main() { int i=100,x=0,y=0; while (i>0) { i--; x=i%8; if (x==1) y++; } cout< return 0; } 输出： 3. #include using namespace std; int main() { int a[6]={1,2,3,4,5,6}; int pi=0; int pj=5; int t,i; while (pi { t=a[pi]; a[pi]=a[pj]; a[pj]=t; pi++; pj--; } for (i=0;i<6;i++) cout< cout< return 0; } 输出： 4. #include using namespace std; int main() { int i,length1, length2; string s1,s2; s1="I have a dream."; s2="I Have A Dream."; length1=s1.size(); length2=s2.size(); for (i=0;i if (s1[i]>='a'&&s1[i]<='z') s1[i]-='a'-'A'; for (i=0;i if (s2[i]>='a'&&s2[i]<='z') s2[i]-='a'-'A'; if (s1==s2) cout<<"="<< endl; else if (s1>s2) cout <<">"<< endl; else cout<<"<"< return 0; } 输出：_________ 四、完善程序（共2 题，每题14分，共计28分） 1.（读入整数）请完善下面的程序，使得程序能够读入两个int 范围内的整数，并将这两个整数分别输出，每行一个。（第一、五空 2.5 分，其余3 分） 输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。 例如： 输入：123 -789 输出：123 -789 #include using namespace std; int readint() { int num = 0; // 存储读取到的整数 int negative = 0; // 负数标识 char c; // 存储当前读取到的字符 c = cin.get(); while ((c < '0' || c > '9') && c != '-') c = (1) ; if (c == '-') negative = 1; else (2) ; c=cin.get(); while ( (3) ) { (4) ; c=cin.get(); } if (negative == 1) (5) ; return num; } int main() { int a, b; a = readint(); b = readint(); cout< return 0; } 2.(郊游活动)有n名同学参加学校组织的郊游活动，已知学校给这n 名同学的郊游总经费为A 元，与此同时第i 位同学自己携带了Mi 元。为了方便郊游，活动地点提供B(≥n)辆自行车供人租用，租用第j 辆自行车的价格为Cj元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。（第四、五空2.5 分，其余3 分） 本题采用二分法。对于区间[l, r]，我们取中间点mid 并判断租用到自行车的人数能否达到mid。判断的过程是利用贪心算法实现的。 #include using namespace std; #define MAXN 1000000 int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid; bool check(int nn) { int count = 0, i, j; i = (1) ; j = 1; while (i <= n) { if ( (2) ) count += C[j] - M[i]; i++; j++; } return (3) ; } void sort(int a[], int l, int r) { int i = l, j = r, x = a[(l + r) / 2], y; while (i <= j) { while (a[i] < x) i++; while (a[j] > x) j--; if (i <= j) { y = a[i]; a[i] = a[j]; a[j] = y; i++; j--; } } if (i < r) sort(a, i, r); if (l < j) sort(a, l, j); } int main() { int i; cin >> n >> B >> A; for (i = 1; i <= n; i++) cin >> M[i]; for (i = 1; i <= B; i++) cin >> C[i]; sort(M, 1, n); sort(C, 1, B); l = 0; r = n; while (l <= r) { mid = (l + r) / 2; if ( (4) ) { ans = mid; l = mid + 1; } else r = (5) ; } cout << ans << endl; return 0; } 第七届分区联赛提高组初赛 (提高组PASCAL语言二小时完成) 一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分) 1、中央处理器CPU能访问的最大存储器容量取决于( ) A)地址总线B)数据总线C)控制总线 D)内存容量 2、计算机软件保护法是用来保护软件( )的。 A)编写权B)复制权C)使用权D)著作权 3、64KB的存储器用十六进制表示，它的最大的地址码是( ) A)10000 B)FFFF C)1FFFF D)EFFFF 4、在树型目录结构中，不允许两个文件名相同主要指的是( ) A)同一个磁盘的不同目录下B)不同磁盘的同一个目录下 C)不同磁盘的不同目录下 C)同一个磁盘的同一个目录下 5、下列设备哪一项不是计算机输入设备( ) A)鼠标B)扫描仪C)数字化仪D)绘图仪 6、在计算机硬件系统中，cache是( )存储器 A)只读B)可编程只读C)可擦除可编程只读D)高速缓冲 7、若我们说一个微机的CPU是用的PII300，此处的300确切指的是( ) A)CPU的主时钟频率B)CPU产品的系列号 C)每秒执行300百万条指令D)此种CPU允许最大内存容量 8、Email邮件本质上是一个( ) A)文件B)电报C)电话D)传真 9、2KB的内存能存储( )个汉字的机内码 A)1024 B)516 C)2048 D)218 10、以下对Windows的叙述中，正确的是( ) A)从软盘上删除的文件和文件夹，不送到回收站 B)在同一个文件夹中，可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件 D)不能打开两个写字板应用程序 11、运算式(2047)10—(3FF)16+(2000)8的结果是( ) A)(2048)10B)(2049)10C)(3746)8D)(1AF7)16 12、TCP/IP协议共有( )层协议 A)3 B)4 C)5 D)6 13.若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是( ) A)i B)n-1 C)n-i+1 D)不确定 14.计算机病毒是( ) A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 15.下面关于算法的错误说法是( ) A)算法必须有输出B)算法必须在计算机上用某种语言实现 信息学奥赛NOIP初赛复习知识点 1、计算机相关科学家： A：被西方人誉为“计算机之父”的美籍匈牙利科学家、数学家冯·诺依曼于1945年发表了一个 全新的"存储程序通用电子计算机方案"—EDVAC。EDVAC方案提出了著名的“ 冯·诺依曼体系结构”理论：（1）采用二进制形式表示数据和指令（2）采用存储程序方式（3）由运算器、存储器、控制器、输 入设备和输出设备五大部件组成计算机系统 B：“图灵机”与“冯·诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另 一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。与计算机有关的最高奖项“图灵奖”。 2、与竞赛有关的知识： A：信息学奥赛相关的软件有：anjuta 1.2.2版； Red Hat 9.0 自带了gcc/g++ 3.2.2版； Lazarus 0.9.10版；free pascal编译器 2.0.1版； gdb 6.3版；RHIDE；（turbo pascal淘汰） 3、与计算机系统相关的知识： A：常见的操作系统有：DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、WIN2007、LINUX、VISTA 4、与计算机软件相关的知识：无 5、与计算机硬件相关的知识： A：断电后能保存信息的有：ROM（只读存储器）、硬盘、软盘、光盘、U盘、MP3、MP4等；不能保存的主要是RAM（读写存储器）。 B：CPU又名中央处理器，它可以拆分成运算器、控制器 6、病毒及防火墙： A：防火墙的作用是防止黑客攻击。 7、与编程语言相关的知识： A：1972年PARC发布了Smalltalk的第一个版本。大约在此时，“面向对象”这一术语正式确定。Smalltalk被认为是第一个真正面向对象的语言 B：第一代语言：机器语言（0101001）；第二代语言：20世纪50年代，汇编语言，第三代语言：高级语言、算法语言，如BASIC，FORTRAN，COBOL，PASCAL，C；高级语言的特点是可读性强，编 程方便；第四代语言：非过程化语言；SQL；第五代语言：智能性语言，PROLOG（代表）；还有：LISP，APL，SNOBOL，SIMULA。 1. 话说去年苹果们被陶陶摘下来后都很生气，于是就用最先进的克隆技术把陶陶克隆了好多份>.<然后把他们挂在树上，准备摘取。摘取的规则是，一个苹果只能摘一个陶陶，且只能在它所能摘到的高度以下（即是小于关系）的最高的陶陶，如果摘不到的话只能灰溜溜的走开了>.<给出苹果数目及每个苹果可以够到的高度和各个陶陶的高度，求苹果们都摘完后剩下多少个陶陶…… 【输入格式】第一行为两个数，分别为苹果的数量n和陶陶的数量m（n,m<=2000）以下的n行，分别为各个苹果能够到的最大高度。再接下来的m行，分别为各个陶陶的高度。高度均不高于300。 当然了，摘取的顺序按照输入的“苹果够到的最大高度”的顺序来摘。 【输出格式】输出仅有一个数，是剩下的陶陶的数量 【样例输入】5 5↙9↙10↙2↙3↙1↙6↙7↙8↙9↙10 【样例输出】3 2. 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。 任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 279 5 279 这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：5 279 7 279则按输出错误处理，不能得分。【输入】输入文件scholar.in包含n+1行： 第1行为一个正整数n，表示该校参加评选的学生人数。 第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。 所给的数据都是正确的，不必检验。 【输出】输出文件scholar.out共有5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。 【输入输出样例1】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例2】 scholar.in scholar.out 8 80 89 89 8 265 2 264 信息学奥赛基础知识习题(答案版) 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上） 1．我们把计算机硬件系统和软件系统总称为 C 。 (A)计算机CPU (B)固 件 (C)计算机系统 (D)微处 理机 2．硬件系统是指 D 。 (A)控制器，器运算 (B)存储器，控制器 (C)接口电路，I/O设备 (D)包括(A)、(B)、(C) 3. 计算机软件系统包括 B 。 A) 操作系统、网络软件 B) 系统软件、应用软件 C) 客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D 。 (A)高级语言 (B)符号语言 (C)汇编语言 (D)机器语言 5．硬盘工作时应特别注意避免 B 。 (A)噪声 (B)震动 (C)潮 湿 (D)日光 6．计算机中数据的表示形式是 C 。 (A)八进制 (B)十进制 (C)二进 制 (D)十六进制 7．下列四个不同数制表示的数中，数值最大的是 A 。 (A)二进制数11011101 (B)八进制数334 (C)十进制数219 (D)十六进制 数DA 8．Windows 9x操作系统是一个 A 。 (A)单用户多任务操作系统 (B)单用户单任务操 作系统 (C)多用户单任务操作系统 (D)多用户多任务操 作系统 9．局域网中的计算机为了相互通信，必须安装___B__。 （A）调制解调器（B）网卡（C）声卡（D）电视卡 10．域名后缀为edu的主页一般属于__A____。 （A）教育机构（B）军事部门（C）政府部门（D）商业组织 11. 在世界上注册的顶级域名是__A____。 （A）hk（B）cn（C）tw（D） 12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D ）。 （A）采用超大规模集成电路（B）采用CPU作为中央核心部件 （C）采用操作系统（D）存储程序和程序控制 13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。 (A)用鼠标左键单击该图标 (B)用鼠标右键单击该 图标 (C)用鼠标左键双击该图标 (D)用鼠标右键双击该 图标 2002年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （普及组竞赛用时：3 小时） 题一级数求和（存盘名：NOIPC1） [问题描述]: 已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。 现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。 [输入] 键盘输入 k [输出] 屏幕输出 n [输入输出样例] 输人：1 输出：2 题二选数（存盘名：NOIPC2） [问题描述]: 已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。 现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3＋7＋19＝29）。 [输入]： 键盘输入，格式为： n , k （1<=n<=20，k＜n） x1,x2，…,xn （1<=xi<=5000000） [输出]： 屏幕输出，格式为： 一个整数（满足条件的种数）。 [输入输出样例]: 输入： 4 3 3 7 12 19 输出： 1 [问题描述]: 给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。 规则： 一位数可变换成另一个一位数： 规则的右部不能为零。 例如：n=234。有规则（k＝2）： 2－> 5 3－> 6 上面的整数 234 经过变换后可能产生出的整数为（包括原数）: 234 534 264 564 共 4 种不同的产生数 问题： 给出一个整数 n 和 k 个规则。 求出： 经过任意次的变换（0次或多次），能产生出多少个不同整数。 仅要求输出个数。 [输入]: 键盘输人，格式为： n k x1 y1 x2 y2 ... ... xn yn [输出]: 屏幕输出，格式为： 一个整数（满足条件的个数）： [输入输出样例]: 输入: 234 2 2 5 3 6 输出： 4 第十六届全国青少年信息学奥林匹克联赛初赛试题 （ 提高组 C++ 语言 两小时完成 ） ? ? 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ?? 、单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确选项。 ） 1．与十六进制数 A1.2 等值的十进制数是（ ) A ． 101.2 B ． 111.4 C ． 161.125 D ． 177.25 &主存储器的存取速度比中央处理器 （CPU ）的工作速度慢的多，从而使得后者的效率受到影响。而 根据局部性原理，CPU 所访问的存储单元通常都趋于一个较小的连续区域中。于是，为了提高系统 整体的执行 效率，在 CPU 中引入了（ ）。 A ．寄存器 B ．高速缓存 C ．闪存 D ．外存 9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序 结构的数组中。假定根结点存放在数组的 1 号位置上，则第 k 号结点的父结点如果存在的话，应当 存放在数组中的（ ）号位置。 A ．2k B ．2k+1 C ．k/2 下取整 D ．（k+1）/2 2．一个字节（ byte ）由（ ）个二进制组成。 A ．8 B ．16 上都有可能 3．以下逻辑表达式的值恒为真的是（ ）。 A . P V （n P A Q ）V （n P 心 Q ） B C . P V Q V （ P A n Q ）V （n P A Q ） D 4 ． Linux 下可执行文件的默认扩展名是 （ ） 。 A. exe B. com 都不是 C ． 32 D .以 Q V( n P A Q )V (P A n Q ) P V n Q V( P A n Q V (n P A n Q) C. dll D. 以上 5 ．如果在某个进制下等式 7*7=41 成立，那么在该进制下等式 12*12= （ A. 100 B. 144 C. 164 ）也成立。 D. 196 6 ．提出“存储程序”的计算机工作原理的是（ A. 克劳德 ?香农 B. 戈登?摩尔 ）。 C. 查尔斯 ?巴比奇 D. 冯?诺依曼 7 ．前缀表达式“ + 3 * 2 + 5 12 ” 的值是（ ）。 A. 23 B. 25 C. 37 D. 6 第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （普及组 竞赛用时：3小时） 第一题 Cantor 表（30分） 现代数学的著名证明之一是Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的： 我们以Z 字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，… 输入：整数N （1≤N ≤10000000） 输出：表中的第N 项 样例： INPUT OUTPUT N=7 1/4 第二题 回文数（30分） 若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次N 进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N （2<=N<=10，N=16）进制数M ，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible ！” 样例： INPUT OUTPUT N = 9 M= 87 STEP=6 第三题 旅行家的预算（40分） 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C （以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P 和沿途油站数N （N 可以为零），油站i 离出发点的距离Di 、每升汽油价格Pi （i=1，2，…，N ）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution ”。 样例： INPUT … 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … 3/1 3/2 3/3 … 4/1 4/2 … 5/1 … … 2015 年第二十一届全国青少年信息学奥林匹克联赛初赛普及组 C++语言试题竞赛日寸间： 2015 年 10 月 l 1 日 14:30~16:30 选手注意： ?试题纸共有 7 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。?不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项) 1.1MB 等于( ) 。 A ．1000 字节 B ．1024 字节 C ． 1000X 1000 字节 D ．1024X 1024 字节 2．在 PC机中， PENTIUM(奔腾)、酷睿、赛扬等是指 ( ) 。 A ．生产厂家名称 B ．硬盘的型号 C ．CPU的型号 D ．显示器的型号 3．操作系统的作用是( ) 。 A ．把源程序译成目标程序 B ．便于进行数据管理 C ．控制和管理系统资源 D ．实现硬件之间的连接 4．在计算机内部用来传送、存贮、加工处理的数据或指令都是以( ) 形式进行的。 A ．二进制码 B ．八进制码 C ．十进制码 D ．智能拼音码 5．下列说法正确的是 ( ) 。 A ． CPU的主要任务是执行数据运算和程序控制 B ．存储器具有记忆能力，其中信息任何时候都不会丢失 C ．两个显示器屏幕尺寸相同，则它们的分辨率必定相同 D ．个人用户只能使用 Wifi 的方式连接到 Internet 6．二进制数 00100100 和 00010100 的和是 ( ) 。 A.00101000 B. 01001001 C. 01000100 D.00111000 7．与二进制小数 0.1 相等的十六进制数是( ) 。 A ． 0.8 B ． 0.4 C ． 0.2 D ． 0.1 8．所谓的“中断”是指 ( ) 。 A ．操作系统随意停止一个程序的运行 B ．当出现需要时， CPU暂时停止当前程序的执行转而执行处理新情况的过程 C ．因停机而停止一个程序的运行 D ．电脑死机 9．计算机病毒是 ( ) 。 A ．通过计算机传播的危害人体健康的一种病毒 B ．人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C ．一种由于计算机元器件老化而产生的对生态环境有害的物质 D ．利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 10． FTP可以用于 ( ) 。 A ．远程传输文件 B ．发送电子邮件 C ．浏览网页 D ．网上聊天 11．下面哪种软件不属于即时通信软件 ( ) 。 A ．QQ B ． MSN C ．微信 D ． P2P 12.6 个顶点的连通图的最小生成树，其边数为 ( ) 。 A ． 6 B ． 5 C ． 7 D ． 4 13. 链表不具备的特点是 ( ) 。 A ．可随机访问任何一个元素 B ．插入、删除操作不需要移动元素 C ．无需事先估计存储空间大小 D ．所需存储空间与存储元素个数成正比 14. 线性表若采用链表存储结构，要求内存中可用存储单元地址( ) 。 A ．必须连续 B ．部分地址必须连续 c ．一定不连续 D ．连续不连续均可 15．今有一空栈 S，对下列待进栈的数据元素序列 a,b ，c， d，e，f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S 的栈顶元素为 ( ) 。 A． f B ．c C ．a D ． b NOIP2017普及组初赛试题及答案 一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项） 1.在8位二进制补码中，10101011表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D. -84 2.计算机存储数据的基本单位是( )。 A. bit B. Byte C. GB D. KB 3.下列协议中与电子邮件无关的是( )。 A. POP3 B. SMTP C. WTO D. IMAP 4.分辨率为800x600、16位色的位图，存储图像信息所需的空间为( )。 A.937.5KB B. 4218.75KB C.4320KB D. 2880KB 5.计算机应用的最早领域是( )。 A.数值计算 B.人工智能 C.机器人 D.过程控制 6.下列不属于面向对象程序设计语言的是( )。 A. C B. C++ C. Java D. C# 7.NOI的中文意思是( )。 A.中国信息学联赛 B.全国青少年信息学奥林匹克竞赛 C.中国青少年信息学奥林匹克竞赛 D.中国计算机协会 8. 2017年10月1日是星期日，1999年10月1日是( )。 A.星期三 B.星期日 C.星期五 D.星期二 9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有( )种。 A. 36 B. 48 C. 96 D. 192 10.设G是有n个结点、m条边(n ≤m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 11.对于给定的序列{ak}，我们把(i, j)称为逆序对当且仅当i < j且ai> aj。那么 序列1, 7, 2, 3, 5, 4的逆序对数为()个。 A. 4 B. 5 C. 6 D. 7 12.表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。 NOIP2016第二十二届全国青少年信息学奥林匹克联赛初赛 试 题 普及组C++语言 时间：2016 年10 月22 日14:30 ～16:30 竞赛 项） 一、单项选 择题（共20 题，每题 1.5 分，共计30 分；每题有且仅有一个正确选 1．以下不是微软公司出品的软件是( ) 。 A ．Powerpoint B ．Word C.Excel D. Acrobat Reader 2．如果256 种颜色用二进制编码来表示，至少需要( ) 位。 A ．6 B ．7 C ．8 D ．9 3．以下不属于无线通信技术的是( ) 。 A ．蓝牙B．WiFi C ．GPRS D ．以太网 4．以下不是CPU生产厂商的是( ) 。 A.Intel B.AMD C.Microsoft D.IBM 5．以下不是存储设备的是( ) 。 A ．光盘 B ．磁盘 C ．固态硬盘 D ．鼠标 6．如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照C apsLock、字母键A、字母键S ，即 C apsLock、A、S、D、CapsLock、A、S、D、??，屏幕上输出的第81 个 D的顺序循环按键 和字母键 字符是字母( ) 。 A ．A B ．S C ． D D ．a 7．二进制数00101100 和00010101 的和是( ) 。 A.00101000 B.01000001 C.01000100 D.00111000 8．与二进制小数0.1 相等的八进制数是( ) 。 A ．0.8 B ．0.4 C ．0.2 D ．0.1 9．以下是32 位机器和64 位机器的区别的是( ) 。 A．显示器不同B．硬盘大小不同 C．寻址空间不同D．输入法不同 10．以下关于字符串的判定语句中正确的是( ) A．字符串是一种特殊的线性表 B ．串的长度必须大于零 C．字符串不可以用数组来表示 D ．空格字符组成的串就是空串 11．一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二 叉树中的结点（根结点的下标 为i ，则其左孩子位于下标 2i 为1，若某结点的下标 大下标为( ) 。 处、右孩子位于下标 (2i+1) 处），则图中所有结点的最 A.6 B ．10 C ．12 D ．15 12．若有如下程序段，其中s、a、b、c 均己定义为整型变量，且a、c 均己赋值（ c 大于0）。 s=a; for (b=1;b<=c;b++) s=s+1; 则与上述程序段修改 s值的功能等价的赋值语句是( ) 。 A. s=a+b; B. s=a+c; C. s=s+c; D. s=b+c; 13．有以下程序： #include CCF全国信息学奥林匹克联赛（NOIP2015）复赛 普及组 （请选手务必仔细阅读本页内容） 一、题目概况 中文题目名称金币扫雷游戏求和推销员 coin mine sum salesman 英文题目与子目 录名 可执行文件名coin mine sum salesman 输入文件名coin.in mine.in sum.in salesman.in 输出文件名coin.out mine.out sum.out salesman.out 每个测试点时限1秒 测试点数目10 每个测试点分值10 附加样例文件有 结果比较方式全文比较（过滤行末空格及文末回车） 题目类型传统 运行内存上限128M 二、提交源程序文件名 对于C++语言coin.cpp mine.cpp sum.cpp salesman.cpp 对于C语言coin.c mine.c sum.c salesman.c 对于Pascal语言coin.pas mine.pas sum.pas salesman.pas 四、注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm)II x2240processor，2.8GHz，内存4G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。 1.金币 (coin.cpp/c/pas) 【问题描述】 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。 请计算在前K天里，骑士一共获得了多少金币。 【输入格式】 输入文件名为coin.in。 输入文件只有1行，包含一个正整数K，表示发放金币的天数。 【输出格式】 输出文件名为coin.out。 输出文件只有1行，包含一个正整数，即骑士收到的金币数。 【输入输出样例1】 coin.in coin.out 614 见选手目录下的coin/coin1.in和coin/coin1.ans。 【输入输出样例1说明】 骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到1+2+2+3+3+3=14枚金币。 【输入输出样例2】 coin.in coin.out 100029820 见选手目录下的coin/coin2.in和coin/coin2.ans。 【数据说明】 对于100%的数据，1≤K≤10,000。 NOIP提高组初赛历年试题及答案求解题篇问题求解题（每次2题，每题5分，共计10分。每题全部答对得5分，没有部分分）注：答案在文末 提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。 NOIP2011-1．平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边，如图所示。那么，5个顶点的平面图至多有_________条边。 NOIP2011-2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将A移到B之前，变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_________次操作。 NOIP2012-1. 本题中，我们约定布尔表达式只能包含p,q, r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（?）三种布尔运算。如果无论p, q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r和p∨(q∨r)等价，p∨?p 和q∨?q 也等价；而p∨q 和p∧q不等价。那么，两两不等价的布尔表达式最多有_________个。 NOIP2012-2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集）， 图2有14个不同的独立集。那么，图3有_________个不同的独立集。 NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn，均为0或1。该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。 然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答： 就破解出了密码s1=_________，s2=_________，s3=_________， s4=_________。 NOIP2013-2. 现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1,2,…,k号荷叶之一上，直至跳到1号荷叶 信息学竞赛复习材料（一）信息学与名人知识 图灵英国科学家，他是计算机人工智能技术的鼻祖。1937年他提出了能思考的计算机——图灵机的概念，推进了计算机理论的发展。图灵机模型是一种抽象计算模型，用来精确定义可计算函数，是实现机器人的最基本的一个理论模型。1950年，艾伦图灵发表题为《计算技能思考吗》的论文，设计了著名的图灵测验，解决了如何判定机器人是否具有同人类相等的智力问题 冯·诺依曼(John Von Neuman)凭他的天才和敏锐，在电脑初创期，提出了现代计算机的理论基础，从而规范和决定了电脑的发展方向。时至今日，我们所有的电脑都叫“冯·诺依曼计算机”，即计算机是由控制器、运算器、存储器、输入设备、输出设备组成的，是对这位数学天才最好的评价。 对于冯·诺依曼来说，人类第一台电脑造了一半时才参与开发，多少有些遗憾。但是，他刚好在那大机器程序存储问题无法解决的关键时刻出现，这使得冯·诺依曼的天才得到淋漓尽致的发挥。他明确指出：一定要彻底实现程序由外存储向内存储的转化，原有的设计必须作修改，经费不够再追加。在冯·诺依曼的影响下，整个研制工作取得了突破性的进展。冯·诺依曼提出了新的改进方案：一是用二进制代替十进制，进一步提高电子元件的运算速度；二是存储程序，即把程序放在计算机内部的存储器中，即把程序本身当作数据来对待。1945年6月，他写了一篇题为《关于离散变量自动电子计算机的草案》的论文，第一次提出了在数字计算机内部的存储器中存放程序的概念，这是所有现代电子计算机的范式，被称为“冯·诺依曼结构”。按这一结构建造的电脑称为存储程序计算机， 又称为通用计算机。时至今日，所有的电脑都逃脱不了冯·诺依曼的掌心，我们所有的电脑，都有一个共同的名字，叫“冯·诺依曼机器”，它超越了品牌、国界、速度和岁月。 摩尔定律与高登·摩尔 当人们不断追逐新款PC时,殊不知这后面有一只无形的大手在推动,那就是摩尔定律,而这著名定律的发明人就是高登·摩尔(Gordon Moore)。 1965年的一天，摩尔顺手拿了把尺子和一张纸，画了一张草图，纵坐标代表不断发展的集成电路，横坐标是时间。他在月份上逐个描点，得到一幅增长的曲线图。这条曲线显示出每24个月，集成电路由于内部晶体管数量的几何级数的增长，而使性能几乎翻倍提高，同时集成电路的价格也恰好减少一倍。后来高登·摩尔把时间调整为18个月。摩尔是在集成电路技术的早期作出结论的，那时候，超大规模集成电路技术还远未出现，所以他在1965年的预言并未引起世人的注意。 高登·摩尔的另一壮举是在1968年与罗伯特·诺伊斯带头率领一群工程师离开仙童公司，成立了一家叫集成电子的公司，简称“Intel”，这就是今日名震世界的英特尔公司。 阿达·奥古斯塔，19世纪诗人拜伦的女儿，数学家。穿孔机程序创始人，建立了循环和子程序概念。为计算程序拟定“算法”，写作的第一份“程序设计流程图”，被珍视为“第一个给计算机写程序的人”。 【最新整理，下载后即可编辑】 历年noip普及组初赛试题汇编 芜湖县实验学校NOIP初赛复习资料 第十五届全国青少年信息学奥林匹克联赛初赛试题(2009) （普及组C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸 上一律无效●● 一．单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。） 1、关于图灵机下面的说法哪个是正确的： A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作，图灵机运行速度很慢。 C)图灵机是英国人图灵发明的，在二战中为破译德军的密码 发挥了重要作用。 D)图灵机只是一个理论上的计算模型。 2、关于计算机内存下面的说法哪个是正确的： A)随机存储器（RAM）的意思是当程序运行时，每次具体分 配给程序的内存位置是随机而不确定的。 B)1MB内存通常是指1024*1024字节大小的内存。 C)计算机内存严格说来包括主存（memory）、高速缓存（cache） 和寄存器（register）三个部分。 D)一般内存中的数据即使在断电的情况下也能保留2个小时 以上。 3、关于BIOS下面说法哪个是正确的： A)BIOS是计算机基本输入输出系统软件的简称。 B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输 入输出设备的驱动程序。 C)BIOS一般由操作系统厂商来开发完成。 D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文 件管理功能。 4、关于CPU下面哪个说法是正确的： A)CPU全称为中央处理器（或中央处理单元）。 B)CPU可以直接运行汇编语言。 C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。 D)CPU最早是由Intel公司发明的。 5、关于ASCII，下面哪个说法是正确的： A)ASCII码就是键盘上所有键的唯一编码。 B)一个ASCII码使用一个字节的内存空间就能够存放。 C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的 编码。 D)ASCII码是英国人主持制定并推广使用的。 6、下列软件中不是计算机操作系统的是： A) Windows B) Linux C) OS/2 D) WPS 7、关于互联网，下面的说法哪一个是正确的： A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 B)互联网的入网主机如果有了域名就不再需要IP地址。 C)互联网的基础协议为TCP/IP协议。 D)互联网上所有可下载的软件及数据资源都是可以合法免 费使用的。 8、关于HTML下面哪种说法是正确的： A）HTML实现了文本、图形、声音乃至视频信息的统一编码。 B）HTML全称为超文本标记语言。 C）网上广泛使用的Flash动画都是由HTML编写的。 D）HTML也是一种高级程序设计语言。 第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题 (普及组PASCAL语言二小时完成) 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一.选择一个正确答案代码(A/B/C/D,填入每题的括号内(每题1.5分,多选无分,共30分) 1)微型计算机的问世是由于( ) 的出现。 A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 D) 电子管电路 2)下列说法中正确的是( ) 。 A) 计算机体积越大,其功能就越强 B) CPU的主频越高,其运行速度越快 C) 两个显示器屏幕大小相同,则它们的分辨率必定相同 D)点阵打印机的针数越多,则能打印的汉字字体越多 3)Windows98中,通过查找命令查找文件时,若输入F*.? , 则下列文件( ) 可以被查到。 A) F.BAS B) FABC.BAS C) F.C D) EF. 4)CPU处理数据的基本单位是字,一个字的字长( ) 。 A) 为8个二进制位 B) 为16个二进制位 C) 为32个二进制位 D) 与芯片的型号有关 5)资源管理器的目录前图标中增加"+"号,这个符号的意思是( ) 。 A) 该目录下的子目录已经展开 B) 该目录下还有子目录未展开 C) 该目录下没有子目录 D) 该目录为空目录, 6)下列哪一种程序设计语言是解释执行的( ) 。 A) Pascal B) GWBASIC C) C++ D) FORTRAN 7)启动WORD的不正确方法是( ) 。 A) 单击Office工具栏上的Word图标 B) 单击"开始"→"程序"→Word C) 单击"开始"→"运行",并输入Word按回车 D) 双击桌面上的"Word快捷图标" 8)多媒体计算机是指( ) 计算机。 A) 专供家庭使用的 B) 装有CDROM的 C) 连接在网络上的高级 D) 具有处理文字、图形、声音、影像等信息的 9)在树型目录结构中,不允许两个文件名相同主要是指( ) 。 A) 同一个磁盘的不同目录下 B) 不同磁盘的同一个目录下 C) 不同磁盘的不同目录下、 D) 同一个磁盘的同一个目录下 10)用画笔(Paintbrush)绘制图形并存储在文件中,该图形文件的文件名缺省的后缀为( ) 。 A) .jpg B) .bmp C) .gif D).tiff t11)E-ml地址中用户名和邮件所在服务器名之间的分隔符号是( ) 。 E A) # B) @ C) & D) $ 12)(0.5)10=( ) 16. A) 0.1 B) 0.75 C) 0.8 D) 0.25 第十九届全国青少年信息学奥林匹克联赛初赛 提高组Pascal语言试题 竞赛时间：2013 年10 月13 日14:30~16:30 选手注意： ●试题纸共有12 页，答题纸共有2 页，满分100 分。请在答题纸上作答，写在试题纸上 的一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。 一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确选项） 1. 一个32 位整型变量占用（）个字节。 A. 4 B. 8 C. 32 D. 128 2. 二进制数11.01 在十进制下是（）。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 3. 下面的故事与（）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’” A. 枚举 B. 递归 C. 贪心 D. 分治 4. 1948 年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。 A. 冯·诺伊曼（John von Neumann） B. 图灵（Alan Turing） C. 欧拉（Leonhard Euler） D. 克劳德·香农（Claude Shannon） 5. 已知一棵二叉树有2013 个节点，则其中至多有（）个节点有2 个子节点。 A. 1006 B. 1007 C. 1023 D. 1024 6. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通 图，至少要删去其中的（）条边。 N O I P2011普及组复赛 1．数字反转（c/pas） 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。（参见样例2） 【输入】 输入文件名为。 输入共一行，一个整数N。 【输出】 输出文件名为。 输出共1行，一个整数，表示反转后的新数。 -1,000,000,000≤N≤1,000,000,000。 【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题（以及-0，但测试数据没出）。 【法一】字符串处理 Var i,l,k:integer; s:string; p:boolean; begin assign(input, ''); reset(input); assign(output, ''); rewrite(output); readln(s); l:=length(s); k:=1; if s[1]='-' then begin write('-'); k:=2; end; p:=true;; for i:=l downto k do begin if(p)and((s[i]='0')) then continue else begin write(s[i]); p:=false;; end; end; close(input); close(output); end. 【法二】数字处理 Var f:integer; n,ans:longint; begin assign(input, ''); reset(input); 排列与组合基础知识 有关排列与组合的基本理论和公式： 加法原理：做一件事，完成它可以有n 类办法，在第一类办法中有m 1种不同的方法，在第二类中办 法中有m 2种不同的方法，……，在第n 类办法中有m n 种不同方法。那么完成这件事共有 N ＝m 1＋m 2＋…＋m n 种不同的方法，这一原理叫做加法原理。 乘法原理：做一件事，完成它需要分成n 个步骤，做第一步有m 1种不同的方法，做第二步有m 2种 不同的方法，……，做第n 步有m n 种不同的方法，那么完成这件事共有N ＝m 1×m 2×…×m n 种不同的方法，这一原理叫做乘法原理。 公式：阶乘公式!(1)(2) 321n n n n =?-?-??，规定0！＝1； 全排列公式!n n P n = 选排列公式!(1)(2)(1)()! m n n P n n n n m n m =---+=-、m m m n n m P C P = 圆排列：n 个不同元素不分首位围成一个圆圈达到圆排列，则排列数为： !(1)!n n n =- 组合数公式(1)(2)(1)!!!()! m m n n m m P n n n n m n C P m m n m ---+===-、规定01n C = m n m n n C C -=、11m m m n n n C C C -+=+、0122n n n n n n C C C C ++++=） 提示：（1）全排列问题和选排列问题，都可根据乘法原理推导出来。 （2）书写方式：r n P 记为P （n,r ） ；r n C 记为C （n,r ）。 加法原理例题：图1中从A 点走到B 点共有多少种方法？（答案：4＋2＋3＝9） 乘法原理例题：图2中从A 点走到B 点共有多少种方法？（答案：4×6＝24） 加法原理与乘法原理综合：图3、图4中从A 走到B 共有多少种方法？（答案：28、42） A B 图1 A B 图2NOIP2001提高组初赛试题答案
信息学奥赛NOIP初赛复习知识点
noip普及组复赛模拟试题18
信息学奥赛基础知识习题(答案版)
NOIP2002普及组(复赛)
(完整word)NOIP2010提高组初赛试题及详细解析
NOIP1999普及组(复赛)
noip205信息学奥赛普及组初赛c++试题
NOIP2017普及组初赛试题及答案
NOIP2016信息学奥赛普与组初赛C试题与答案解析较完美版
NOIP2015普及组复赛试题
NOIP提高组初赛历年试题及答案求解题篇
信息学竞赛复习材料(一)信息学与名人知识
历年noip初赛普及组试题(完整资料).doc
NOIP2002普及组初赛试题及答案
NOIP2013初赛提高组Pascal试题
NOIP普及组复赛试题源程序
(信息学奥赛辅导)排列和组合基础知识
- NOIP2000普及组初赛试题答案
- CCF全国信息学奥林匹克联赛 NOIP 普及组复赛试题
- CCF全国信息学奥林匹克联赛(NOIP2018)普及组复赛试题
- NOIP2002普及组(复赛)
- NOIP2008普及组复赛试题与解题报告
- NOIP2008普及组复赛试题
- NOIP1998普及组初赛试题及答案
- NOIP2017复赛普及组试题
- 历年noip初赛普及组试题(完整资料).doc
- NOIP2011普及组复赛试题
- NOIP1997普及组复赛试题
- NOIP 普及组复赛试题
- NOIP2017_普及组复赛试题
- noip普及组复赛模拟试题18
- NOIP普及组复赛试题
- NOIP2016普及组复赛试题讲解(c++版本)
- NOIP2005普及组复赛试题(附题解)
- noip普及组复赛模拟试题14(附答案)
- NOIP2015普及组复赛试题
- NOIP2015普及组复赛试题讲解(c++版本)