NOIP初赛复习练习.ppt

1、NIOP初赛辅导 v1.0beta4,福州八中 林荣辉 ,1.大纲,2,一、初赛内容与要求：（#表示普及组不涉及，以下同） 计算机基本常识 * 诞生与发展 *特点*在现代社会中的应用 * 计算机系统的基本组成 * 计算机的工作原理#*计算机中的数的表示 * 计算机信息安全基础知识 *计算机网络 计算机基本操作 * MS DOS与Windows的使用基础 * 常用输入/输出设备的种类、功能、使用 * 汉字输入/输出方法 * 常用计算机屏示信息,全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲,3,一、初赛内容与要求：（#表示普及组不涉及，以下同） 程序设计基本知识 程序的表示 * 自然语言的描

2、述 * PASCAL或BASIC语言 数据结构的类型 * 简单数据的类型 * 构造类型：数组、字符串 * 了解基本数据结构（线性表、队列与栈） 程序设计 * 结构化程序的基本概念 * 阅读理解程序的基本能力 * 具有完成下列过程的能力： 现实世界（指知识范畴的问题） 信息世界（表达解法） 计算机世界（将解法用计算机能实现的数据结构和算法描述出来）,全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲,4,一、初赛内容与要求：（#表示普及组不涉及，以下同） 基本算法处理 * 简单搜索 * 字串处理 * 排序 * 查找 * 统计 * 分类 * 合并 * 简单的回溯算法 * 简单的递归算法,全国青少年

3、信息学（计算机）奥林匹克分区联赛竞赛大纲,5,二、复赛内容与要求： 在初赛的内容上增加以下内容 计算机软件 *操作系统的使用知识 *编程语言的使用 数据结构 *结构类型中的记录类型 *文件（提高组必须会使用文本文件输入） *链表 *树 *图#,全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲,6,二、复赛内容与要求： 在初赛的内容上增加以下内容 程序设计 *程序设计能力 *设计测试数据的能力 *运行时间和占用空间的估算能力# 算法处理 *排列组合的应用 *进一步加深回溯算法、递归算法 *分治法 *搜索算法：宽度、深度优先算法 *表达式处理：计算、展开、化简等# *动态规划#,全国青少年信息学

4、（计算机）奥林匹克分区联赛竞赛大纲,7,三、初赛试题类型：注：试题语言两者选一 （程序设计语言：基本BASIC或PASCAL） *判断 *填空 *完善程序 *读程序写运行结果 *问答,全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲,NIOP初赛辅导,福州八中 林荣辉 ,2.计算机基础选择题,9,计算机的发展和应用,1946年2月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer），这台计算机占地170平方米，重30吨，用了18000多个电子管，每秒能进行5000次加法运算。,复杂指令计算机C

5、ISC,精简指令计算机RISC,10,计算机体系的提出,冯诺依曼理论 1944年，美籍匈牙利数学家 冯诺依曼 提出 计算机基本结构和工作方式的设想，为计算机 的 诞生和发展提供了理论基础。时至今日，尽 管 计算机软硬件技术飞速发展，但计算机本身 的 体系结构并没有明显的突破，当今的计算机 仍属于冯诺依曼架构。,输 入 设 备,输 出 设 备,运算器,存储器,控制器,计算机的类型,大型通用机,巨型机,小型机,工作站,微型机,网络计算机,11,我国的计算机发展情况*,我国从1956年开始计算机的科研和教学工作； 1960年我国第一台自行设计的通用电子计算机107机诞生； 1964年我国研制成大型通

6、用电子计算机119机； 1983年每秒运行一亿次的银河巨型计算机在国防科技大学诞生； 1992年研制成功每秒运行10亿次的“银河II”巨型计算机； 1997年又研制成功每秒运行130亿次的“银河III”巨型计算机； 我国较有名的微型计算机品牌有：“联想”、“长城”、“方正”等；,“三金”工程,金桥工程,金关工程,金卡工程,12,计算机系统（硬件）,存储器,内 存,地址 译码器,读写控制电路,数据总线,读写命令,出入内存的信息,地址总线,存贮器地址,存储器,内存,外存,硬盘,光盘,半导体,13,计算机系统（硬件）,CPU,程序计数器,地址寄存器,运算器,数据寄存器,操作控制器,指令译码器,指令寄

7、存器,内存,ALU,DR,IR,PC,CPU结构,14,计算机系统（软件）,计算机软件,应用软件,系统软件,数据库系统,语言程序,操作系统,各种功能的软件,应用软件必须有系统软件的支持,操作系统,MS-DOS,WINDOWS,UNIX,Linux,Mactonish-OS,数据库,Oracle,Foxpro,SQL,Access,15,1101101.0101 =1*20+0*21+1*22+1*23+0*24+1*25+1*26+0*2-1+1*2-2+0*2-3+1*2-4 =109.3125,信息的表示与存储,进制转换,R进制数转10进制,2进制转10进制,（1101101.0101）2

8、,（1101101.0101）B,16,3506.2 =6*80+0*81+5*82+3*83+2*8-1 =1862.25,8进制转10进制,（3506.2）8,0.2A =2*16-1+10*16-2 =0.1640625,16进制转10进制,（0.2A）H,17,进制转换,10进制数转R进制,57,28,14,1,7,3,2,2,0,2,2,2,2,1,0,0,1,1,1,余数,5710=1110012,整数部分,小数部分,0.3125*2=0.625 0.625*2=1.25 0.25*2=0.5 0.5*2=1,0.312510=0.01012,取整,18,进制转换,2、8、16进制

9、互转,指数=位数,1011010.102转换为8进制和16进制 001 011 010 . 100 1 3 2 . 4 132.48 0101 1010.1000 5 A . 8 5A.816,8=23,16=24,F7.28H转换为2进制 F 7 . 2 8 1111 0111 . 0010 1000 F7.2816=11110111.001012 25.638转换为2进制数 2 5 . 6 3 010 101. 110 011 25.638=10101.1100112,24,23,19,计算机中数的表示法,在生活中表示数的时候一般都是把正数前面加一个“+”，负数前面加一个“-”，但是在数字

10、设备中，机器是不认识这些的，我们就把“+”用“0”表示，“-”用“1”表示。,原码,-1101001原=11101001,原数据加上符号位,反码,-1101001反=11101001反 =10010110,除符号位，按位取反,补码,-1101001补=11101001补 =10010111,除符号位，按位取反再加1,正数的原反补是一样的,20,信息存储单位,位,度量数据的最小单位，表示一位2进制信息,bit，缩写为b,注意小写,字节,字节是信息存储中最常用的基本单位,一字节由8位2进制数组成,1 Byte=8 bit,KB（千字节） 1K=1024 Byte MB(兆) 1M=1024K GB

11、（千兆字节） 1G=1024M,21,非数值信息的表示,西文,中文,美国信息交换标准代码,国家标准信息交换用汉字编码,简称“国标码”,国标码共6763个汉字，一级汉字3755个，二级汉字3008个,即ASCII码. 用7位2进制表示，有128个状态,常用码：A=65;0=48;a=97,按拼音,按部首,22,练习,练习1微型计算机的问世是由于( ) 的出现。 A)中小规模集成电路 B)晶体管电路 C) (超)大规模集成电路 D) 电子管电路 练习2中央处理器(CPU)能访问的最大存储器容量取决于( ) 。 A)地址总线 B)数据总线 C) 控制总线 D) 实际内存容量 练习3微型计算机中，(

12、) 的存取速度最快。 A)高速缓存 B)外存储器 C) 寄存器 D) 内存储器 练习4在计算机硬件系统中，cache是( )存储器。 A)只读 B)可编程只读 C)可擦除可编程只读 D)高速缓存,寄存器高速缓存内存储器外存储器,23,练习5若我们说一个微机的CPU是用的PII300，此处的300确切指的是( )。 A)CPU的主时钟频率 B)CPU产品的系列号 C)每秒执行300百万条指令 D)此种CPU允许最大内存容量 练习6计算机主机是由CPU与（）构成的。 控制器B. 输入、输出设备C. 运算器D.内存储器 练习7计算机系统总线上传送的信号有（ ）。 A.地址信号与控制信号B. 数据信号

13、、控制信号与地址信号 C.控制信号与数据信号D. 数据信号与地址信号 练习8不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（ ）。 A.快存/辅存/主存B. 外存/主存/辅存C. 快存/主存/辅存D. 主存/辅存/外存,24,练习9微机内存储器的地址是按（ ）编址的。 A.二进制位 B. 字长 C.字节 D. 微处理器的型号 练习10在微机中，通用寄存器的位数是（ ）。 A 8 位 B16位 C.计算机字长 D32位 练习11不同的计算机，其指令系统也不同，这主要取决于（ ）。 A 所用的操作系统 B. 系统的总体结构 C所用的CPU D所用的程序设计语言 练习12下

14、列说法中，哪个（些）是错误的（ ）。 A）程序是指令的序列，它有三种结构：顺序、分支和循环。 B）数据总线决定了中央处理器CPU所能访问的最大内存空间的大小。 C）中央处理器CPU内部有寄存器组，用来储存数据。 D）不同厂家生产的CPU所能处理的指令集是相同的。 E）数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了差错。 练习13CPU访问内存的速度比访问下列哪个（些）存储设备要慢（AD ）。 A）寄存器 B）硬盘 C）软盘 D）高速缓存 E）光盘,在字节增加一位，按位相加判断奇偶，以便校对,25,练习14下列哪个不是CPU（中央处理单元）（ ）。 A. Intel It

15、anium B. DDR SDRAM C. AMD Athlon64 D. AMD Opteron E. IBM Power 5 练习15下列说法中错误的是（ ）。 A.CPU的基本功能就是执行指令。 B.CPU访问内存的速度快于访问高速缓存的速度。 C.CPU的主频是指CPU在1秒内完成的指令周期数。 D.在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。 E.数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。 练习16用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ ）。 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪

16、 练习17以下哪个不是计算机的输出设备（ ）。 A. 音箱 B. 显示器 C. 打印机 D. 扫描仪 E. 绘图仪,原复习文档答案有误,26,练习18十进制数11/128可用二进制数码序列表示为( ) 。 A)1011/1000000 B)1011/100000000 C) 0.001011 D) 0.0001011 练习19算式(2047)10(3FF)16(2000)8的结果是( ) 。 A)(2048)10 B)(2049)10 C) (3746)8 D) (1AF7)16 练习20已知x=(0.1011010)2,则x/2 =( ) 2 。 0.1011101. B) 11110110

17、 C) 0.0101101 D) 0.100110 练习21已知A=35H,则A05HA3OH的结果是:( ) 。 A)3OH B)05H C) 35H D) 53H 练习22x补码=10011000，其原码为( ) A)011001111 B)11101000 C)11100110 D)01100101 练习23下列无符号数中，最小的数是（） A.（11011001）2B.(75)10C.(37)8D.(2A)16,1023,1024,and与; or或; not非;,NIOP初赛辅导,福州八中 林荣辉 ,3.多媒体选择填空题,28,多媒体技术,多媒体计算机,音频信号处理,图形和图像处理,视

18、频处理,视频输入输出,日常办公,通信网络,外部设备,多媒体技术个 人计算机系统,29,光盘,CD,DVD,BR-DVD,VCD,Compact Disc,Digital CD,Video CD,Blue-Ray DVD,CD表面,OFF,光感测器,0,解码电路,ON,光感测器,1,解码电路,棱镜,棱镜,激光束,激光束,凸,凹,导出区,数据区,导入区,目录区,光盘读取数据原理,30,人眼睛能分辨的颜色大约有16000种，这么多颜色我们用24bit来描述，这种显示模式就称为真彩色。,自然界常见的各种颜色光，都可由红、绿、蓝3种颜色按不同比例配制而成，反之亦可三原色原理,图形图像,彩色的描述,亮度,

19、色调,饱和度,明亮程度,颜色种类,颜色纯度,图形图像分类,位图,矢量图,点阵像素,几何元素,拉伸变形,拉伸不变形,图像占用 空间计算,图像存储空间=分辨率*颜色（*数据压缩比）,点阵大小,位数,某图片分辨率为1024*768，256色，则他的存储空间=1024*768*8=6291456bit 他的大小=空间/8=786432Byte786K,28=256,真彩色,224=16M,31,练习,练习1目前，图像文件格式有很多种，其中，windows附件所带的画图程序默认的图形格式是（ ）；Photoshop的标准文件格式是（ ）；JPG文件的主要特点是（） ：JPG B.PSD C.BMP D.

20、GIF 2 : JPG B.PSD C.BMP D.GIF 3 : A.图像质量高 B.图像色彩数高 C.图像占用空间大 D.压缩效率很高 练习2若视频信号的每幅黑白图像均为256级灰度，1024*768的点阵表示，当数据的压缩比为30时，每幅图像的存储空间为1（ ）比特。以每秒25幅的方式播出时，容量为600M比特的视频图像以压缩形式在网络上需传输2（ ）秒，传输速度不应低于每秒3（ ）比特。 1： 1024*768*8/300.2MB 2： 600/(0.2MB*25)=120s 3: 0.2MB*25=5MB,颜色？,32,网络基础,网络历程,1.“主机-中端”系统,多台设备连接到一台中

21、央计算机,雏形,2.ARPANET,阿帕网,里程碑,3.广域网 （1) 已知中缀表达式：A+B*C/D 求它的前缀表达式和后缀表达式？ （2）已知前缀表达式：+A*BC 注表示一元运算符负号，即A表示-A 求它的中缀表达式和后缀表达式？ 解答：画（二叉）表达式树。 （1）的结果：+A*B/CD；ABCD/*+ （2）的结果：（-A）+B*（-C）；ABC*+,74,例题6已知一个数列U1,U2,U3.Un.,往往可以找到一个最小的K值和K个数a1,a2,.,ak,使得数列从某项开始都满足:U(n+k)=a1*U(n+k-1)a2*U(n+k-2)+.akUn (式A) 例如数列 1,1,2,3

22、,5.可以发现:当K=2,a1=1,a2=1时,从第3项起(N=1)满足: U(n+2)U(n+1) Un 试对数列13 ,23 ,33 ,.,N3,求K和a1,a2,.ak,使得式A成立。 解答：解方程，先设K=2，列出方程组： a1*23+a2*13=33 a1*33+a2*23=43 以上方程组无整数解。再设K=3，列出方程组： a1*02+a2*12+a3*22=32 a1*12+a2*22+a3*32=42 a1*22+a2*32+a3*42=52 以上方程的整数解为：a1=1，a2=-3，a3=3，此时K=3,75,例题7设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走

23、3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。 解答：两种方法，一是“猜”+“凑”，从具体的n=1,2,3算起，只能算比较简单的，容易错；二是用组合数学和归纳法进行推导，一般先假设 F（n）= a*F（n-1）+b*F（n-2）+c*F（n-3）+， 然后算a，b，c直到某个系数=0就结束，再代入式子中。 F（1）1 F（2）2 F（3）4 F（N）F（N3）F（N2）F（N1） （N4）,76,例题8将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法:红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄

24、红黄红黄 黄黄黄红红。问题：当N=4,M=3时有多少种不同排法?(不用列出每种排法) 解答：35 例题9在书架上放有编号为1 ，2 ，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n = 3时： 原来位置为：1 2 3 放回去时只能为：3 1 2 或 2 3 1 这两种 问题：求当n = 5时满足以上条件的放法共有多少种？（不用列出每种放法） 解答：f(n)=n*f(n-1) 1(n1,且n为偶数时取+，n为奇数时取-) f(1)=0 所以，当n=5时，满足以上条件的方法共有44种。,NIOP初赛辅导,福州八中 林荣辉 ,6.阅读程序部分,78,

25、阅读和分析程序,由于初赛没有上机条件，因此只能通过人工阅读程序得到计算结果。阅读一份没有任务说明的程序是十分费力的工作。在阅读时，由于疏忽或考虑不周全可能对程序的理解出现各种各样的偏差，导致错误的计算结果。正确的阅读方法和熟练的分析技巧能大大缩短理解程序原意的时间。,79,1.直接推理/模拟,例题1 var m,n,i:integer; t:extended; begin readln(n,m); t:=1; for i:=1 to m do t:=t*(n-i+1)/i; writeln(t:0:0); end. 输入 10 5 输出_,extended扩展类型，即使不知道，也不会影响计算,

26、252,80,2.动态模拟,例题2 var i,j:integer; a:array1.3,1.3of integer; begin for i:=1 to 3 do begin for j:=1 to 3 do begin if i=3 then ai,j:=ai-1,ai-1,j+1; else ai,j:=j; writeln(ai,j); end; writeln; end; readln; end. 输出_,直接模拟的进化，过程中记录现场的变化,81,例题3 var a,d:array1.100of integer; n,i,j,k,x,s:integer; begin n:=5;a

27、1:=1;d1:=1; for i:=1 to n do begin s:=i+1;x:=0; for j:=1 to n+1-i do begin k:=s+x;x:=x+1;aj+1:=aj+k; writeln(aj, ); end; writeln(.);di+1:=di+i;a1:=di+1; end; end.,1 3 6 10 15 . 2 5 9 14 . 4 8 13 . 12 . 11 .,82,3.观察输入,例题4 label 10,20,30; var s,p:string; i,k,n,j,m:integer; begin readln(s);n:=length(s)

28、; readln(p);m:=length(p); i:=0; 10: i:=i+1; j:=i; k:=1; 20: if sjpk then begin if in-m+1 then goto 10; i:=0; goto 30; end; else if km then begin j:=j+1;k:=k+1; goto 20; end; 30: writeln(i); end. 输入 asabcdffdin fdi 输出_,遇到没见过的语句不必慌张，观察语句的实现作用,看到goto，猜想是不是跳转语句,两段字符串的输入，猜想是不是比较子序列,继续观察20这步，发现是找匹配字串的位置,8

29、,NIOP初赛辅导,福州八中 林荣辉 ,7.完善程序部分,84,初赛中，程序填空题的内容通常有以下几个方面,变量方面的填空； 循环方面的填空； 分支转移方面的填空； 主程序和子程序关系方面的填空； 输入和输出方面的填空。,85,1.完善不含子程序的程序,例题1求元素之和最大的子方阵：在m*n（m,n=20）的正整数方阵中，找出一个p*q的子阵(1=p=m,1=q=n)使其元素之和最大。例如，下面给出的矩阵中，元素之和最大为一个2*3的子阵,86,程序(求p*q最大方阵元素之和子阵),var a:array1.20,1.20of integer; m,n,p,q,i,j,max,p1,q1,s,

30、i1,j1:integer; begin for i:=1 to 20 do for j:=1 to 20 do ai,j:=0; readl(m,n); for i:=1 to m do begin for j:=1 to n do read(ai,j); readln; end; readln(p,q); max:=0;,for i:=1 to m-p+1 do for j:=1 to n-q+1 do begin _; for i1:=i to p+i-1 do for j1:= j to q+j-1 do _; if smax then begin _; p1:=i; q1:=j; e

31、nd; end; for i:=p1 to _do begin for j:=q1 to _do writeln(ai,j:3); writeln; end; readln; end.,方阵清零,根据规模读方阵,根据规模读子阵，计数器初始化,穷举子阵,由 i+p-1=m 得 i=m-p+1,因穷举且无数组供 数据存放故累加无 望推得此处必定为 累加数之初始化,s:=0,累加,s:=s+ai1,j1,岗哨,max:=s,记录位置,由 i+p-1 得 p1+p-1,p1+p-1,q1+q-1,87,例题2以下程序完成对数组每个元素向后移动n个单位。数组元素的下标依次为0到m-1，对任意一个数组元素

32、ai而言，他的值移动后将存储在数组元素a(i+n)mod m中。 例如，m=10，n=3，移动前数组中数据如下第一行，运行后数据如下第二行。 0 3 86 20 27 67 31 16 37 42 16 37 42 0 3 86 20 27 67 31 分析：循环链移动为ai-a(i+n) mod m-a(i+n+n) mod m-a(i+3*n) mod m-.-ai 移动前注意判断是否已经移动过，避免重复移动。,即i+2*n,88,程序(数组循环链),const maxm=10000; var i,k,m,n,rest,start,temp:longint; a:array0.maxm o

33、f longint; begin randomize; write(input m,n:); readln(m,n); for i:=0 to m-1 do ai:=random(100); writeln(before move); for i:=0 to m-1 do write(ai:5); writeln; rest:=m;start:=0;,while _do begin k:=start; repeat k:=(k+n) mod m until k=start; if _then begin temp:=ak; repeat ak:=a(m*n+k-n)mod m; k:=(m*n

34、+k-n)mod m; _ until k=start; _ end; _ end; writeln(after move); for i:=0 to m-1 do write(ai:5); writeln; end.,下标和移动单位,输出初始值,看变量名猜含义： rest(余下未移动) start(首元素),仍然有余下的数,含mod参考题目 猜想k是当前指针,追加猜想start 为移动起始元素,眼前推断不能，暂留,看变量名猜含义2： temp(暂存？),移动开始,下面是移动，那么这里应该就是判断整条链是否已经移动,k由start起，不断后移，直到链头(kstart表示原start位置已移动；

35、k=start表示未移动过）,k=start,rest0,移一个，少一个,rest：=rest-1,最后temp里的数 给新的astart或者ak,a(k+n) mod m:=temp,寻找下一个链,inc（start）,89,2.完善含子程序结构的程序,例题3用09中的n(1=n=10)个数字填入如下乘法运算的*处，数字可重复使用，且所使用的数字至少有一个是素数，要求输出满足下列算式的方案数。函数有作用提示 * * * X * * * * * * * * * * * *,90,程序（乘法填空）,const p:set of 0.9=2,3,5,7; var s:set of 0.9; n:i

36、nteger; ans:longint; procedure init; var i:integer; t:byte; begin readln(n); s:=; for i:=1 to n do begin read(t); s:=s+t; end; end;,判断x是否满足条件,function ok(x,l:integer):boolean; var t:byte; begin ok:=false; if _l then exit; while x0 do begin t:=x mod 10; if not (t in s) then exit; x:=x div 10; end; ok

37、:=true; end;,素数集,也是整型,集成操作数集,exit结束子程序 break结束循环,不等于1的时候退出函数，猜想是位数,求位数我们引入对数log,logab可以理解为求a的多少次方等于b，即ax=b，求x,那么，一个多位数的位数可以表示为 trunc(log10 x)+1,如584在100和1000之间，即102 ,103,求的trunc（2.XX）+1为3,pascal里对数不方便写，我们改写为trunc(ln(x)/ln(10)+1; 利用的对数的换底公式： logaN=logbN/logba. log10 x可以写成ln(x),trunc(ln(x)/ln(10)+1,这里对10取模印证了我们对位数的猜测,91,判断x中是否包含素数,function inset(x:integer):boolean; var t:byte; begin inset:=false; while _do begin t:=x mod 10; if t in p then begin inset:=true; exit; end; _; end; end;,procedure work; var i,i1,i2,i3,j1,j2: