noip初赛复习（全）new

分区联赛初赛复习

初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考查的是知识，而问题解决类型的题目更加重视能力的考查。一般说来，选择题只要多用心积累就可以了。问题解决题目的模式比较固定，大家应当做做以前的题目。写运行结果和程序填空也需要多做题目，并且培养良好的程序阅读和分析能力，就像语文的阅读理解一样。 近几年来，初赛的考查范围有了很大的变化，越来越紧跟潮流了。这就需要大家有比较广泛的知识，包括计算机硬件、软件、网络、简单的数据结构（例如栈、队列、树和图等）和简单的算法（例如排序、查找和搜索等），程序设计语言以及一些基本的数学知识和技巧（例如排列组合）。但最主要的，还是取决于你对程序设计语言的熟悉程度，再加上认真仔细的心态。

选择题

一、硬件

计算机发展可划分：

第一代 第二代 第三代 第四代

1946年2月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer），这台计算机占地170平方米，重30吨，用了18000多个电子管，每秒能进行5000次加法运算。

冯·诺依曼理论

1944年，美籍匈牙利数学家 冯·诺依曼 提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体系结构并没有明显的突破，当今的计算机仍属于冯·诺依曼架构。

其理论要点如下：

1、计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备5部分组成。 2、存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。

年代 1946－1958 1959－1964 1965－1970 1971－？ 元件 电子管 晶体管 集成电路 大规模集成电路 我国的计算机发展情况

·我国从1956年开始计算机的科研和教学工作；

·1960年我国第一台自行设计的通用电子计算机107机诞生； 1964年我国研制成大型通用电子计算机119机；

·1983年每秒运行一亿次的银河巨型计算机在国防科技大学诞生； 1992年研制成功每秒运行10亿次的“银河Ⅱ”巨型计算机； 1997年又研制成功每秒运行130亿次的“银河Ⅲ”巨型计算机； ·我国较有名的微型计算机品牌有：“联想”、“长城”、“方正”等；

微型机的主要技术指标

1、字长：知己算计能够直接处理的二进制数据的位数。单位为位（BIT）

2、主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上决定了计算机的运 算速度。

3、内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（BYTE）。 8BIT=1BYTE 1024B=1KB 1024KB=1MB 4、外存容量：一般指软盘、硬盘、光盘。

计算机的特点：

运算速度快，运算精度高，具有记忆能力，具有逻辑判断能力，具有自动控制能力；

计算机的应用：

1、数值计算：弹道轨迹、天气预报、高能物理等等 2、信息管理：企业管理、物资管理、电算化等 3、过程控制：工业自动化控制，卫星飞行方向控制

4、辅助工程：计算机辅助教学（CAI）、计算机辅助设计（CAD）、计算机辅助制造（CAM）、计算机辅助测试（CAT）、计算机集成制造（CIMS）等

计算机硬件由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。

中央处理器（CPU——Central 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）：主要有针式打印机、喷墨打印机、激光打印机。 ·绘图仪 ·音箱

中央处理器(CPU)能访问的最大存储器容量取决于地址总线 微型计算机中，寄存器的存取速度最快。 在计算机硬件系统中，cache是高速缓冲存储器。

若我们说一个微机的CPU是用的PII300，此处的300确切指的是CPU的主时钟频率 计算机主机是由CPU与内存储器构成的。

计算机系统总线上传送的信号有：数据信号、控制信号与地址信号

不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是：快存/主存/辅存

微机内存储器的地址是按字节编址的。 在微机中，通用寄存器的位数是计算机字长

不同的计算机，其指令系统也不同，这主要取决于所用的CPU 程序是指令的序列，它有三种结构：顺序、分支和循环。 中央处理器CPU内部有寄存器组，用来储存数据。 CPU访问内存的速度比访问寄存器和高速缓存要慢

DDR SDRAM不是CPU（中央处理单元）

用静电吸附墨粉后转移到纸张上，是激光打印机的工作方式。

处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A 和处理器B 的指令，编译结果处理器A 的指令数是处理器B 的4 倍。已知程序P 在处 理器A 上执行需要1 个小时，那么在输入相同的情况下，程序P 在处理器B 上执行需 要1 / 2小时。

二、进制与编码

四种常用的数制及它们之间的相互转换： 进制 十进制 二进制 八进制 十六进制 基数 基数个数 0、1、2、3、4、5、6、7、8、9 10 0、1 0、1、2、3、4、5、6、7 0、1、2、3、4、5、6、7、8、9、2 8 16 权 10i 2i 8 16i i进数规律 逢十进一 逢二进一 逢八进一 逢十六进一 A、B、C、D、E、F 十进制数转换为二进制数、八进制数、十六进制数的方法： 二进制数、八进制数、十六进制数转换为十进制数的方法：按权展开求和法 1．二进制与十进制间的相互转换：

（1）二进制转十进制

方法：“按权展开求和”

例： （1011.01）2 ＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2 ）10

＝（8＋0＋2＋1＋0＋0.25）10 ＝（11.25）10

规律：个位上的数字的次数是0，十位上的数字的次数是1，......，依奖递增，而十

分位的数字的次数是-1，百分位上数字的次数是-2，......，依次递减。

注意：不是任何一个十进制小数都能转换成有限位的二进制数。

（2）十进制转二进制

· 十进制整数转二进制数：“除以2取余，逆序排列”（短除反取余法）

例： （89）10 ＝（1011001）2

2 89 2 44 ??1 2 22 ??0 2 11 ??0 2 5 ??1 2 2 ??1 2 1 ??0

0 ??1

· 十进制小数转二进制数：“乘以2取整，顺序排列”（乘2取整法） 例： (0．625)10= (0．101)2

0．625 X 2

1．25 1 X 2