NOIP(普及~组)初赛复习资料1.doc

|分区联赛初赛复习初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考查的是知识，而问题解决类型的题目更加重视能力的考查。一般说来，选择题只要多用心积累就可以了。问题解决题目的模式比较固定，大家应当做做以前的题目。写运行结果和程序填空也需要多做题目，并且培养良好的程序阅读和分析能力，就像语文的阅读理解一样。近几年来，初赛的考查范围有了很大的变化，越来越紧跟潮流了。这就需要大家有比较广泛的知识，包括计算机硬件、软件、网络、简单的数据结构（例如栈、队列、树和图等）和简单的算法（例如排序、查找和搜索等） ，程序设计语言以及一些基本的数学知识和技巧（例如排列组合） 。但最主要的，还是取决于你对程序设计语言的熟悉程度，再加上认真仔细的心态。选择题一、硬件计算机发展可划分：年代 元件第一代 19461958 电子管第二代 19591964 晶体管第三代 19651970 集成电路第四代 1971？ 大规模集成电路1946 年 2 月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer） ，这台计算机占地 170 平方米，重 30 吨，用了 18000 多个电子管，每秒能进行 5000 次加法运算。冯·诺依曼理论1944 年，美籍匈牙利数学家 冯·诺依曼 提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体系结构并没有明显的突破，当今的计算机仍属于冯·诺依曼架构。其理论要点如下：1、计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备 5 部分组成。2、存储程序思想把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。|我国的计算机发展情况·我国从 1956 年开始计算机的科研和教学工作；·1960 年我国第一台自行设计的通用电子计算机 107 机诞生；1964 年我国研制成大型通用电子计算机 119 机；·1983 年每秒运行一亿次的银河巨型计算机在国防科技大学诞生；1992 年研制成功每秒运行 10 亿次的“银河”巨型计算机；1997 年又研制成功每秒运行 130 亿次的“银河”巨型计算机；·我国较有名的微型计算机品牌有：“联想” 、 “长城” 、 “方正”等；微型机的主要技术指标1、字长：知己算计能够直接处理的二进制数据的位数。单位为位（BIT）2、主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上决定了计算机的运算速度。3、内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（BYTE）。8BIT=1BYTE 1024B=1KB 1024KB=1MB4、外存容量：一般指软盘、硬盘、光盘。计算机的特点：运算速度快，运算精度高，具有记忆能力，具有逻辑判断能力，具有自动控制能力；计算机的应用：1、数值计算：弹道轨迹、天气预报、高能物理等等2、信息管理：企业管理、物资管理、电算化等3、过程控制：工业自动化控制，卫星飞行方向控制4、辅助工程：CAD、CAM、CAT、CAI 等计算机硬件由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。中央处理器（CPUCentral Processing Unit）由运算器、控制器和一些寄存器组成；运算器进行各种算术运算和逻辑运算；|控制器是计算机的指挥系统；CPU 的主要性能指标是主频和字长。存储器内部存储器中央处理器能直接访问的存储器称为内部存储器，它包括快速缓冲存储器和主存储器，中央处理器不能直接访问的存储器称为外部存储器，外部存储器中的信息必须调入内存后才能为中央处理器处理。主存储器：内存也常泛称主存，但严格上说，只有当内存中只有主存，而没有快速缓冲存储器时，才能称为主存。主存储器按读写功能，可分只读存储器（ROM）和随机存储器（RAM）两种。外部存储器外存储器：也称为辅助存储器，一般容量较大，速度比主存较慢。硬盘（Hard disk）：目前的硬盘大多采用了温彻斯特技术，所以又称为“温盘” ；温氏技术的特点是：将盘片、读写磁头及驱动装置精密地组装在一个密封盒里；采用接触式起停，非接触式读写的方式（磁盘不工作时，磁头停在磁盘表面的起停区，一旦加电后，磁头随着盘片旋转的气流“飞”起来，悬浮在磁盘表面，进行读写） 。软盘（Floppy Disk）：目前常见的是 3.5 英寸/1.44 MB 的软盘。光盘存储器（CD-ROM）：普通的 CD-ROM，只能读，不能写； CD 盘片的存储量大约是650 MB。输入设备·键盘（Keyboard）：目前大多使用 104 或 108 键盘·鼠标（Mouse）：主要有机械型鼠标和光电型鼠标两种·手写笔 ·触摸屏 ·麦克风 ·扫描仪（Scanner）·视频输入设备·条形码扫描器输出设备·显示器（Monitor）：目前主要有 CRT（阴极射线管）显示器和 LCD 液晶显示器。·打印机（Printer）：主要有针式打印机、喷墨打印机、激光打印机。·绘图仪 ·音箱例题微型计算机的问世是由于( C ) 的出现。A)中小规模集成电路 B)晶体管电路 C) (超)大规模集成电路 D) 电子管电路中央处理器(CPU)能访问的最大存储器容量取决于( A ) 。A)地址总线 B)数据总线 C) 控制总线 D) 实际内存容量微型计算机中，( C ) 的存取速度最快。A)高速缓存 B)外存储器 C) 寄存器 D) 内存储器在计算机硬件系统中，cache 是(D )存储器。|A)只读 B)可编程只读 C)可擦除可编程只读 D)高速缓冲若我们说一个微机的 CPU 是用的 PII300，此处的 300 确切指的是(A )。A)CPU 的主时钟频率 B)CPU 产品的系列号C)每秒执行 300 百万条指令 D)此种 CPU 允许最大内存容量计算机主机是由 CPU 与（ D ）构成的。A. 控制器 B. 输入、输出设备 C. 运算器 D.内存储器计算机系统总线上传送的信号有（ B ） 。A.地址信号与控制信号 B. 数据信号、控制信号与地址信号C.控制信号与数据信号 D. 数据信号与地址信号不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（C） 。A.快存/辅存/主存 B. 外存/主存/辅存 C. 快存/主存/辅存 D. 主存/辅存/外存微机内存储器的地址是按（C）编址的。A. 二进制位 B. 字长 C.字节 D. 微处理器的型号在微机中，通用寄存器的位数是（C） 。A 8 位 B16 位 C.计算机字长 D32 位不同的计算机，其指令系统也不同，这主要取决于（C） 。A 所用的操作系统 B. 系统的总体结构C所用的 CPU D所用的程序设计语言下列说法中，哪个（些）是错误的（ BDE ）。A）程序是指令的序列，它有三种结构：顺序、分支和循环。B）数据总线决定了中央处理器 CPU 所能访问的最大内存空间的大小。C）中央处理器 CPU 内部有寄存器组，用来储存数据。D）不同厂家生产的 CPU 所能处理的指令集是相同的。E）数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了差错。CPU 访问内存的速度比访问下列哪个（些）存储设备要慢（ AD ）。A）寄存器 B）硬盘 C）软盘 D）高速缓存 E）光盘下列哪个（些）不是个人计算机的硬件组成部分（ B ）。A）主板 B）虚拟内存 C）电源 D）硬盘 E）总线美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（ C ） 。A. 提出理想计算机的数学模型，成为计算机科学的理论基础。|B. 是世界上第一个编写计算机程序的人。C. 提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机 EDVAC。D. 采用集成电路作为计算机的主要功能部件。E. 指出计算机性能将以每两年翻一番的速度向前发展。下列哪个不是 CPU（中央处理单元） （ B ） 。A. Intel Itanium B. DDR SDRAM C. AMD Athlon64D. AMD Opteron E. IBM Power 5下列说法中错误的是（ B ） 。A. CPU 的基本功能就是执行指令。B. CPU 访问内存的速度快于访问高速缓存的速度。C. CPU 的主频是指 CPU 在 1 秒内完成的指令周期数。D. 在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。E. 数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ C ） 。A. 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪处理器A 每秒处理的指令数是处理器 B 的2 倍。某一特定程序P 分别编译为处理器A和处理器B 的指令，编译结果处理器 A 的指令数是处理器B 的4 倍。已知程序P 在处理器A 上执行需要1 个小时，那么在输入相同的情况下，程序P 在处理器B 上执行需要（D）小时。A. 4 B. 2 C. 1 D. 1 / 2 E. 1 / 4以下哪个不是计算机的输出设备（D）。A. 音箱 B. 显示器 C. 打印机 D. 扫描仪 E. 绘图仪二、进制与编码四种常用的数制及它们之间的相互转换：进制 基数 基数个数 权 进数规律十进制 0、1、2、3、4、5、6、7、8、 9 10 10i 逢十进一二进制 0、1 2 2i 逢二进一八进制 0、1、2、3、4、5、6、7 8 8i 逢八进一十六进制 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F 16 16i 逢十六进一十进制数转换为二进制数、八进制数、十六进制数的方法：二进制数、八进制数、十六进制数转换为十进制数的方法：按权展开求和法1二进制与十进制间的相互转换：（1）二进制转十进制|方法：“按权展开求和”例： （1011.01） 2 （1×2 30×2 21×2 11×2 00×2 1 1×2 2 ）10（802100.25） 10（11.25） 10规律：个位上的数字的次数是 0，十位上的数字的次数是 1，.，依奖递增，而十分位的数字的次数是-1，百分位上数字的次数是-2，.，依次递减。注意：不是任何一个十进制小数都能转换成有限位的二进制数。（2）十进制转二进制· 十进制整数转二进制数：“除以 2 取余，逆序排列” （短除反取余法）例： （89） 10 （1011001） 22 892 44 12 22 02 11 02 5 12 2 12 1 00 1· 十进制小数转二进制数：“乘以 2 取整，顺序排列” （乘 2 取整法）例： (0625) 10= (0101) 20625X 2 125 1X 2 05 0X 2 10 12八进制与二进制的转换：二进制数转换成八进制数：从小数点开始，整数部分向左、小数部分向右，每 3 位为一组用一位八进制数的数字表示，不足 3 位的要用“0”补足 3 位，就得到一个八进制数。八进制数转换成二进制数：把每一个八进制数转换成 3 位的二进制数，就得到一个二进制数。例：将八进制的 37.416 转换成二进制数：3 7 4 1 6011 111 100 001 110即：（37.416） 8 （11111.10000111） 2 例：将二进制的 10110.0011 转换成八进制：0 1 0 1 1 0 . 0 0 1 1 0 0 2 6 . 1 4 即：（10110.011） 2 （26.14） 83十六进制与二进制的转换：二进制数转换成十六进制数：从小数点开始，整数部分向左、小数部分向右，每 4 位为一组用一位十六进制数的数字表示，不足 4 位的要用“0”补足 4 位，就得到一个十六进制数。十六进制数转换成二进制数：把每一个八进制数转换成 4 位的二进制数，就得到一个二进制数。|例：将十六进制数 5DF.9 转换成二进制：5 D F 90101 1101 1111 1001即：（5DF.9） 16 （10111011111.1001） 2 例：将二进制数 1100001.111 转换成十六进制：0110 0001 11106 1 E即：（1100001.111） 2 （61.E） 16注意：以上所说的二进制数均是无符号的数。这些数的范围如下表：无符号位二进制数位数 数值范围 十六进制范围表示法8 位二进制数 0255 （255=2 8-1） 000FFH16 位二进制数 065535 （65535=2 16-1）0000H0FFFFH32 位二进制数 0232-1 00000000H0FFFFFFFFH带符号数的机器码表示方法1带符号二进制数的表示方法：带符号二进制数用最高位的一位数来表示符号：0 表示正，1 表示负。含符号位二进制数位数 数值范围 十六进制范围表示法8 位二进制数 -128 +127 80H7FH16 位二进制数 -32768 +32767 8000H7FFFH32 位二进制数 -2147483648 +214748364780000000H7FFFFFFFH2、符号位的表示：最常用的表示方法有原码、反码和补码。（1）原码表示法：一个机器数 x 由符号位和有效数值两部分组成，设符号位为 x0，x真值的绝对值|x|=x 1x2x3.xn，则 x 的机器数原码可表示为：x原 = .0，当 x>=0 时，x 0=0，当 x<0 时，x 0=1。例如：已知：x 1=-1011B，x 2= +1001B，则 x1，x 2有原码分别是x1 原 =11011B，x 2原 =01001B规律：正数的原码是它本身，负数的原码是取绝对值后，在最高位（左端）补“1” 。（2）反码表示法：一个负数的原码符号位不变，其余各位按位取反就是机器数的反码表示法。正数的反码与原码相同。按位取反的意思是该位上是 1 的，就变成 0，该位上是 0 的就变成 1。即 1=0，0=1例： Bx10， x02，求 反1x和 反2。解： 反= ， 反= B（3）补码表示法：首先分析两个十进制数的运算：78-38=41，79+62=141如果使用两位数的运算器，做 79+62 时，多余的 100 因为超出了运算器两位数的范围而自动丢弃，这样在做 78-38 的减法时，用 79+62 的加法同样可以得到正确结果。模是批一个计量系统的测量范围，其大小以计量进位制的基数为底数，位数为指数的幂。如两位十进制数的测量范围是 19，溢出量是 100，模就是 102=100，上述运算称为模运算，可以写作：79+（-38）=79+62 （mod 100)进一步写为 -38=62，此时就说 38 的补法（对模 100 而言）是 62。计算机是一种有限字长的数字系统，因此它的运算都是有模运算，超出模的运算结果都将溢出。n 位二|进制的模是 2n,一个数的补码记作x 补 ，设模是 M，x 是真值，则补码的定义如下：)0(xMx原补例：设字长 n=8 位，x=-1011011B，求x 补 。解：因为 n=8，所以模 M=2 8=100000000B，x<0，所以x补 =M+x=100000000B-1011011B=10100101B注意：这个 x 的补码的最高位是“1” ，表明它是一个负数。对于二进制数还有一种更加简单的方法由原码求出补码：（1）正数的补码表示与原码相同；（2）负数的补码是将原码符号位保持“1”之后，其余各位按位取反，末位再加 1 便得到补码，即取其原码的反码再加“1”：x 补 =x反 +1。下表列出 1287,390及 的 8 位二进制原码，反码和补码并将补码用十六进制表示。真值 原码（B） 反码（B） 补码（B） 补码（H）+127 0 111 1111 0 111 1111 0 111 1111 7F+39 0 010 0111 0 010 0111 0 010 0111 27+0 0 000 0000 0 000 0000 0 000 0000 00-0 1 000 0000 1 111 1111 0 000 0000 00-39 1 010 0111 1 101 1000 1 101 1001 D9-127 1 111 1111 1 000 0000 1 000 0001 81-128 无法表示 无法表示 1 000 0000 80从上可看出，真值+0 和-0 的补码表示是一致的，但在原码和反码表示中具有不同形式。8 位补码机器数可以表示-128，但不存在+128 的补码与之对应，由此可知，8 位二进制补码能表示数的范围是-128+127。还要注意，不存在-128 的 8 位原码和反码形式。定点数和浮点数（一）定点数（ Fixed-Point Number）计算机处理的数据不仅有符号，而且大量的数据带有小数，小数点不占有二进制一位而是隐含在机器数里某个固定位置上。通常采取两种简单的约定：一种是约定所有机器数的小数的小数点位置隐含在机器数的最低位之后，叫定点纯整机器数，简称定点整数。另一种约定所有机器数的小数点隐含在符号位之后、有效部分最高位之前，叫定点纯小数机器数，简称定点小数。无论是定点整数，还是定点小数，都可以有原码、反码和补码三种形式。（二）浮点数（ Floating-Point Number）计算机多数情况下采作浮点数表示数值，它与科学计数法相似，把一个二进制数通过移动小数点位置表示成阶码和尾数两部分： SNE2其中：EN 的阶码（Expoent） ，是有符号的整数SN 的尾数（Mantissa） ，是数值的有效数字部分，一般规定取二进制定点纯小数形式。例：1011101B=2 +7*0.1011101，101.1101B=2 +3*0.1011101，0.01011101B=2 -1*0.1011101浮点数的格式如下：E0 E1E2En E0 E1E2En阶符 阶 尾符 尾数 浮点数由阶码和尾数两部分组成，底数 2 不出现，是隐含的。阶码的正负符号 E0，在最前位，阶反映了数 N 小数点的位置，常用补码表示。二进制数 N 小数点每左移一位，阶|增加 1。尾数是这点小数，常取补码或原码，码制不一定与阶码相同，数 N 的小数点右移一位，在浮点数中表现为尾数左移一位。尾数的长度决定了数 N 的精度。尾数符号叫尾符，是数 N 的符号，也占一位。例：写出二进制数-101.1101B 的浮点数形式，设阶码取 4 位补码，尾数是 8 位原码。-101.1101=-0.1011101*2+3浮点形式为：阶码 0011 尾数 11011101补充解释：阶码 0011 中的最高位“0”表示指数的符号是正号，后面的“011”表示指数是“3” ；尾数 11011101 的最高位“1”表明整个小数是负数，余下的 1011101 是真正的尾数。例：计算机浮点数格式如下，写出 x=0.0001101B 的规格化形式，阶码是补码，尾数是原码。x=0.0001101=0.1101*10-3又-3 补 =-001B补 =1011补 =1101B所以 浮点数形式是 1 101 0 1101000ASCII 码 ( American Standard Code for Information Interchange )美国标准信息交换代码将每个字符用 7 位的二进制数来表示，共有 128 种状态大小字母、09、其它符号、控制符 0 48 A 65 a 97汉字信息编码1 汉字输入码汉字输入方法大体可分为：区位码（数字码） 、音码、形码、音形码。· 区位码：优点是无重码或重码率低，缺点是难于记忆；· 音码：优点是大多数人都易于掌握，但同音字多，重码率高，影响输入的速度；· 形码：根据汉字的字型进行编码，编码的规则较多，难于记忆，必须经过训练才能较好地掌握；重码率低；·音形码：将音码和形码结合起来，输入汉字，减少重码率，提高汉字输入速度。2汉字交换码汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。自国家标准 GB231280 公布以来，我国一直延用该标准所规定的国标码作为统一的汉字信息交换码。GB231280 标准包括了 6763 个汉字，按其使用频度分为一级汉字 3755 个和二级汉字3008 个。一级汉字按拼音排序，二级汉字按部首排序。此外，该标准还包括标点符号、数种西文字母、图形、数码等符号 682 个。由于 GB231280 是 80 年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字信息的产品采用新颁布的 GB18030 信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，可解决两岸三地间 GB 码与 BIG5 码间的字码转换不便的问题。3字形存储码字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模。如下图：|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 一般的点阵规模有 16×16，24×24，32×32，64×64 等，每一个点在存储器中用一个二进制位（bit）存储。例如，在 16×16 的点阵中，需 16×16bit=32 byte 的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。为了节省存储空间，普遍采用了字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息。例题十进制数 11/128 可用二进制数码序列表示为( D ) 。A)1011/1000000 B)1011/100000000 C) 0.001011 D) 0.0001011算式(2047) 10(3FF) 16(2000) 8的结果是( A ) 。A)(2048)10 B)(2049)10 C) (3746)8 D) (1AF7)16已知 x=(0.1011010)2,则x/2 =( C ) 2 。A) 0.1011101. B) 11110110 C) 0.0101101 D) 0.100110已知 A=35H,则 A05HA3OH 的结果是:( C ) 。A)3OH B)05H C) 35H D) 53H16×16 点表示