CSP-J复习指南（整理中）
LemonZhang2024 · · 个人记录
信息学初赛复习指南
前言
CSP-J/S 简介
(1) 时间和题型
CSP 分入门组 CSP-J 和提高组 CSP-S，前者是小学/初中的，后者是高中的。二者题目不完全相 同，提高组难度高于入门组。
1. 初赛
今年CSP-J第一轮初赛在2020年10月11日进行，可参考历年真题复习。
2. 复赛
第二轮复赛在2020年11月7日。 入门组复赛共 4 道题，每题 100 分，共计 400 分。 试题包括：题目、问题描述、输入输出要求、样例数据（部分题目有样例的说明）。测试时，测试程序为每道题提供了 10－20 组测试数据，考生程序每答对一组得 5 －10 分，累计分即为该道题的得分。程序将在 NOI Linux 1.3（Ubuntu 系统） 的环境下测评，G++编译器版本为 4.4.5，评测系统为Arbiter。2011 年测评器 CPU 为 P4 3.0GHz，内存大小为 1GB。
(2) 初赛大纲
计算机基本常识
- 计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）
- 信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）
- 信息的表示与处理（信息编码、微处理部件 MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）
- 信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）
- 信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP 协议、HTTP 协议、WEB 应用的主要方式和特点）
- 人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））
- 信息技术的新发展、新特点、新应用等。
计算机基本操作
- Windows 和 Linux 的基本操作知识
- 互联网的基本使用常识（网上浏览、搜索和查询等）
- 常用的工具软件使用（文字编辑、电子邮件收发等）
程序设计基本知识
数据结构
- 程序语言中基本数据类型（字符、整数、长整、浮点）
- 浮点运算中的精度和数值比较
- 一维数组（串）、线性表、队列与栈
- 记录类型（PASCAL）/结构类型（C/C++）
程序设计
- 结构化程序设计的基本概念
- 阅读理解程序的基本能力
- 具有将简单问题抽象成适合计算机解决的模型的基本能力
- 具有针对模型设计简单算法的基本能力
- 程序流程描述（自然语言/伪码/NS 图/其他）
- 程序设计语言（PASCAL/C/C++）
基本算法处理
- 初等算法（计数、统计、数学运算等）
- 排序算法（冒泡法、插入排序、合并排序、快速排序）
- 查找（顺序查找、二分法）
- 简单搜索
- 字符串处理
- 回溯算法
- 递归算法
(3) 复赛大纲
在初赛内容的基础上增加以下内容：
计算机软件
- 操作系统的使用
- 编程语言的使用
数据结构
- 指针类型
- 多维数组
- 单链表及循环链表
- 二叉树
- 文件操作
程序设计
- 算法的实现能力
- 程序调试基本能力
- 设计测试数据的基本能力
算法处理
- 离散数学知识的应用（如排列组合、简单图论、数理逻辑）
- 分治
- 模拟法
- 贪心法
- 简单搜索算法、剪枝
- 动态规划
第一部分 计算机发展及应用
1. 计算机的发展
1946年2月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机 ENIAC（Electronic Numerical Integrator And Computer），这台计算机占地 170 平方米，重 30吨，用了 18000 多个电子管，每秒能进行 5000 次加法运算。 1958 年中国研制了第一台电子管计算机，速度每秒二千次。 “银河”1983 年问世，运算速度为每秒 1 亿次。 2001 年，中科院计算所研制成功我国第一款通用 CPU——”龙芯”
2. 计算机的名人
冯•诺依曼 ————计算机之父
1944 年 8 月至 1945 年 6 月，美籍匈牙利科学家冯•诺依曼提出了一个全新的计算机概念，即“冯•诺依曼计算机”模型。主要贡献：确立了现代计算机的基本结构。
艾兰•图灵 ————人工智能之父，图灵机
“图灵奖”是计算机科学领域的最高奖项，有“计算机界诺贝尔奖”之称。设立这个大奖，既是为了促进计算机科学的进一步发展，也是为了纪念一位天才数学家、计算机科学的奠基人艾兰•图灵。图灵是走在时代前面的天才，在计算机远未问世之前，他构造出一台完全属于想象中的”计算机”，数学家们把它称为”图灵机”，而冯•诺依曼相当于把图灵虚构的”图灵机”进行了实现。（图灵机不是一台真正的计算机）
摩尔 ———— 摩尔定律
1965 年，英特尔联合创始人戈登•摩尔提出以自己名字命名的”摩尔定律”，意指集成电路上可容纳的元器件的数量每隔 18 至 24 个月就会增加一倍，性能也将提升一倍。（摩尔定律过去是每 5 年增长 10 倍，每 10 年增长 100 倍。而如今，摩尔定律每年只能增长几个百分点，每 10 年可能只有 2 倍。因此，摩尔定律结束了。）
比尔•盖茨
比尔•盖茨（Bill Gates），全名威廉•亨利•盖茨三世，简称比尔或盖茨。1955 年 10月 28 日出生于美国华盛顿州西雅图，企业家、软件工程师、慈善家、微软公司创始人。曾任微软董事长、CEO 和首席软件设计师。微软公司在个人计算机和商业软件、服务和互联网技术方面都是全球范围内的领导者。我们所用的 windows 操作系统系列，office 等应用软件都是他们的产品。
王选
江苏无锡人，出生于上海，计算机文字信息处理专家，计算机汉字激光照排技术创始人，当代中国印刷业革命的先行者，被称为“汉字激光照排系统之父”，被誉为“有市场眼光的科学家”。 1958 年毕业于北京大学数学力学系，1984 年晋升为教授，1991 年当选为中国科学院院士，1994 年当选为中国工程院院士，1995 年加入九三学社，2002 年 2 月 1 日获得 2001 年度国家最高科学技术奖，陈嘉庚科 学奖获得者。
3. 计算机的特点
速度快——普通计算机每秒可执行几亿次运算 计算精度高——主要取决于计算机的字长 记忆能力强——有存储器 可靠的逻辑判断能力——能进行逻辑运算 有自动控制能力——具有程序控制下的自动执行能力
4. 计算机语言的发展
第一代: 机器语言
由 0 和 1 组成，能让计算机直接接受的代码称为机器指令。 所谓机器语言是指计算机指令的集合 机器语言的缺点: 难学、难写、难记、难检查、难修改
第二代: 汇编语言
由于机器语言难以记忆，汇编语言使用了一些助记符来表示每一条机器指令。但 汇编语言要通过汇编程序翻译成机器语言才能执行 汇编语言的缺点: 只适应于特定的计算机
第三代： 高级语言
第一种高级语言是 fortran
比较常见的高级语言有: pascal,c,basic,fortran
把高级语言翻译成机器语言有两种方式:
编译方式:把高级语言写的源程序直接输入计算机，编译程序把整个源程序翻译成目标程序，然后由计算机执行目标程序（Pascal，C/C++采用编译方式）
解释方式：把高级语言写的源程序直接输入计算机，解释程序把源程序逐句翻译，翻译一句马上执行，边解释边执行
第四代： 面向对象的高级语言
如果说第三代语言要求告诉计算机怎么做，那么第四代语言只需要告诉计算机做什么。第一个面向对象的语言是smalltalk。
比较常见的面向对象的高级语言有：free pascal,C,C++,object pascal,c# 等
第五代： 人工智能语言
代表语言是 LISP 语言和 Prolog 语言
NOIP 比赛可使用的语言：Pascal ， C/C++
5. 计算机的分类
1. 以”代”分类：
第一代：1946~1957 年，电子管计算机
第二代：1958~1964 年，晶体管计算机
第三代：1965~1971 年，中小规模集成电路计算机
第四代：1972 至今，大规模集成电路计算机
第五代：人工智能计算机
2. 以功能规模分类
巨型机、大型机、中型机、小型机、微型机（如 PC 即个人电脑）
6. 计算机的应用
科学计算:弹道轨迹、天气预报、高能物理等等
数据处理（即信息处理）：企业管理、物资管理、电算化等
自动控制：工业自动化控制，卫星飞行方向控制
计算机辅助设计和教学
人工智能
第二部分 计算机硬件
1944 年，美籍匈牙利数学家 冯•诺依曼 提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体系结构并没有明显的突破，当今的计算机仍属于冯•诺依曼架构。 计算机硬件设备由存储器、运算器、控制器、输入设备 和 输出设备（I/O 设备）五个部 分组成。 存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数 据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。 1) 微型机的主要技术指标 字长：知己算计能够直接处理的二进制数据的位数。单位为位（BIT） 主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上决定了计算机的运算 速度。 内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（BYTE）。 外存容量：一般指软盘、硬盘、光盘。 计算机硬件由五大部分组成：运算器、控制器、存储器、输入设备、输出设备（I/O 设备）。 2) 中央处理器（CPU——Central Processing Unit） 由运算器、控制器和一些寄存器组成； 运算器进行各种算术运算和逻辑运算； 控制器是计算机的指挥系统； CPU 的主要性能指标是主频和字长。 3) 存储器 内部存储器 中央处理器能直接访问的存储器称为内部存储器，它包括快速缓冲存储器和主存储器， 中央处理器不能直接访问的存储器称为外部存储器，外部存储器中的信息必须调入内存后 才能为中央处理器处理。 主存储器：内存也常泛称主存，但严格上说，只有当内存中只有主存，而没有快速缓 冲存储器时，才能称为主存。 主存储器按读写功能，可分只读存储器（ROM）[断电后信息不丢失]和随机存储器（RAM） [断电后信息丢失]两种。 外部存储器 外存储器：也称为辅助存储器，一般容量较大，速度比主存较慢。 硬盘（Hard disk）：将盘片、读写磁头及驱动装置精密地组装在一个密封盒里；采用接 触式起停，非接触式读写的方式（磁盘不工作时，磁头停在磁盘表面的起停区，一旦加电 后，磁头随着盘片旋转的气流“飞”起来，悬浮在磁盘表面，进行读写）。 软盘（Floppy Disk）：目前常见的是 3.5 英寸/1.44 MB 的软盘。 光盘存储器（CD-ROM）：普通的 CD-ROM，只能读，不能写； CD 盘片的存储量大约 是 650 MB。 高速缓冲存储器 又叫 Cache，由于 CPU 速度远大于内存，所以它在中间起协调作用。 比较 内存和外存的主要区别:内存小/外存大，内存贵/外存便宜，内存快/外存慢 存储器的速度:寄存器>Cache>内存>外存（辅存） 4) 输入设备 键盘（Keyboard）：目前大多使用 104 或 108 键盘 鼠标（Mouse）：主要有机械型鼠标和光电型鼠标两种 扫描仪（Scanner） 手写笔、触摸屏、麦克风 视频输入设备、条形码扫描器 5) 输出设备 显示器（Monitor）：目前主要有 CRT（阴极射线管）显示器和 LCD 液晶显示器。 打印机（Printer）：主要有针式打印机、喷墨打印机、激光打印机。 绘图仪、音箱 计算机在运行时，先从内存中取出一条指令，通过控制器的译码，按指令的要求，从存储器中 取出数据进行指定的运算和逻辑操作等加工，然后再按地址把结果送到内存中去。 接下来取出下一条指令，在控制器的指挥下完成规定操作，依次进行下去，直到遇到停止指令 各部分联系示意图 第三部分 软件与操作系统 软件系统按其功能以及重要性可主要分为系统软件和应用软件两大类，系统软件管理整个计算 机系统，应用软件在系统软件的基础上使计算机能解决各种实际问题。 1) 应用软件在系统软件的基础上开发，但系统软件也属于应用软 件 系统软件：用来支持应用软件的开发和运行的，主要是操作系统软件如：DOS、 Windows95/98/2000、Unix、Linux、WindowsNT； 应用软件：为了某个应用目的而编写的软件，主要有文字处理软件、电子表格软件、 数据库管理软件等。 2) 操作系统（OS——Operating System） 操作系统是控制与管理计算机系统资源的软件，是硬件的第一层扩充，任何应用软件 的运行都必须依靠操作系统的支持。 操作系统大致有:dos , ucdos , windows 系列 , Linux , unix , os/2 ... Windows 系列操作系统 Windows 是 Microsoft 公司开发的图形化界面的操作系统。 基本概念： 图标、任务栏、标题栏、菜单栏、滚动条、工具栏、对话框、开始菜单„„ 基本操作： （1）鼠标单击、双击、拖动，左键、右键功能； （2）窗口操作：最大（小）化、大小调整、拖动、关闭、排列、切换； （3）剪贴板：复制（Ctrl－C）、粘贴（Ctrl－V）、剪切（Ctrl－X） 复制屏幕图像：可将当前屏幕图形以 BMP 格式传送到剪贴板„„ （4）其它：查找、运行、切换 Windows、进入 DOS 环境、文件夹选项 3) 语言处理软件 Basic , Cobol , Pascal ,C/C++ ,Java 4) 数据库管理系统 Sybase , dbase , foxbase , foxpro , access , oracle , mysql 5) 常用的应用软件 Office 系列:Word(文字处理) , Excel（表格处理） ,Frontpage(网页制作) , Powerpoint(幻 灯片) 图像处理软件: 画图 、 photoshop ,fireword , Acdsee 网页制作软件: dreamweaver 声音处理软件: goldwave 动画制作软件: flash 6) 常见的文件类型扩展名 可执行类文件: bat、com、exe、sys、tmp、zip、„„ 文档类文件: doc、xls、txt、htm、„„ 图像文件: bmp、gif、jpg、psd、„„ 音频文件: wav、avi、mp3、swf…… 第四部分 进制与编码 1) 四种常用的数制及它们之间的相互转换： 进制 基数 基数个数 权 进数规律 十进制 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 逢十六进一 十进制数转换为二进制数、八进制数、十六进制数的方法： 二进制数、八进制数、十六进制数转换为十进制数的方法：按权展开求和法 2) 二进制与十进制间的相互转换： （1）二进制转十进制 方法：“按权展开求和” 例：（1011.01）2 ＝（1×2 3＋0×2 2＋1×2 1＋1×2 0＋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 取整，顺序排列”（乘 2 取整法） 例： (0．625)10 ＝ (0．101)2 0．625 X 2 1．25 1 X 2 0．5 0 X 2 1．0 1 3) 八进制与二进制的转换： （1）二进制数转换成八进制数：从小数点开始，整数部分向左、小数部分向右，每 3 位为一组用一位八进制数的数字表示，不足 3 位的要用“0”补足 3 位，就得到一个八 进制数。 （2）八进制数转换成二进制数：把每一个八进制数转换成 3 位的二进制数，就得到 一个二进制数。 例：将八进制的 37.416 转换成二进制数： 3 7 ． 4 1 6 011 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）8 4) 十六进制与二进制的转换： （1）二进制数转换成十六进制数：从小数点开始，整数部分向左、小数部分向右， 每 4 位为一组用一位十六进制数的数字表示，不足 4 位的要用“0”补足 4 位，就得到 一个十六进制数。 （2）十六进制数转换成二进制数：把每一个八进制数转换成 4 位的二进制数，就得 到一个二进制数。 例：将十六进制数 5DF.9 转换成二进制： 5 D F ． 9 0101 1101 1111 ．1001 即：（5DF.9）16 ＝（10111011111.1001）2 例：将二进制数 1100001.111 转换成十六进制： 0110 0001 ． 1110 6 1 ． E 即：（1100001.111）2 ＝（61.E）16 注意：以上所说的二进制数均是无符号的数。这些数的范围如下表： 无符号位二进制数位数 数值范围 十六进制范围表示法 8 位二进制数 0~255（255=28 -1） 00~0FFH 16 位二进制数 0~65535 （65535=216
- 1） 0000H~0FFFFH
32 位二进制数 0~232
-1 00000000H~0FFFFFFFFH
5) 带符号数的机器码表示方法
（一）带符号二进制数的表示方法：
带符号二进制数用最高位的一位数来表示符号：0 表示正，1 表示负。
含符号位二进制数位数 数值范围 十六进制范围表示法
8 位二进制数 -128 ~ +127 80H~7FH
16 位二进制数 -32768 ~ +32767 8000H~7FFFH
32 位二进制数 -2147483648 ~ +2147483647 80000000H~7FFFFFFFH
（二）符号位的表示：最常用的表示方法有原码、反码和补码。
（1）原码表示法：一个机器数 x 由符号位和有效数值两部分组成，设符号位为 x0，x 真值的
绝对值|x|=x1x2x3...xn，则 x 的机器数原码可表示为：
[x]原= x0 x1 x2 ...xn ，当 x>=0 时，x0=0，当 x<0 时，x0=1。
例如：已知：x1=-1011B，x2= +1001B，则 x1，x2 有原码分别是
[x1] 原=11011B，[x2]原=01001B
规律：正数的原码是它本身，负数的原码是取绝对值后，在最高位（左端）补“1”。
（2）反码表示法：一个负数的原码符号位不变，其余各位按位取反就是机器数的反码表示法。
正数的反码与原码相同。
按位取反的意思是该位上是 1 的，就变成 0，该位上是 0 的就变成 1。即 1̅=0，0̅=1
例： x1 = −1011B ， x2 = ，求[x1]反 和[x2]反 。
解：[x1]反 =10100 B ，[x2 ]反 = 01001 B
（3）补码表示法：首先分析两个十进制数的运算：79-38=41，79+62=141
如果使用两位数的运算器，做 79+62 时，多余的 100 因为超出了运算器两位数的范围而自动
丢弃，这样在做 79-38 的减法时，用 79+62 的加法同样可以得到正确结果。
模是批一个计量系统的测量范围，其大小以计量进位制的基数为底数，位数为指数的幂。如两
位十进制数的测量范围是 1——9，溢出量是 100，模就是 102
=100，上述运算称为模运算，可以写
作：
79+（-38）=79+62（mod 100)
进一步写为 -38=62，此时就说 –38 的补法（对模 100 而言）是 62。计算机是一种有限字长
的数字系统，因此它的运算都是有模运算，超出模的运算结果都将溢出。n 位二进制的模是 2
n
,
一个数的补码记作[x]补，设模是 M，x 是真值，则补码的定义如下：
[????]补 = {
[????]原 (???? ≥ 0)
???? + ???? (???? < 0)
例：设字长 n=8 位，x=-1011011B，求[x]补。
解：因为 n=8，所以模 M=28
=100000000B，x<0，所以
[x]补 =M+x=100000000B-1011011B=10100101B
注意：这个 x 的补码的最高位是“1”，表明它是一个负数。对于二进制数还有一种更加简单的
方法由原码求出补码：
（4）总结
a) 正数的原码、反码、补码都是相同的；
b)负数的补码是将原码符号位保持“1”之后，其余各位按位取反，末位再加 1 便得到
补码，即取其原码的反码再加“1”：[x]补=[x]反+1。
下表列出±0，±39，±127 以及-128 的 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 位原码和反码形式。
6) 定点数和浮点数
（1）定点数（Fixed-Point Number）
计算机处理的数据不仅有符号，而且大量的数据带有小数，小数点不占有二进制一位而是隐含
在机器数里某个固定位置上。通常采取两种简单的约定：一种是约定所有机器数的小数的小数点位
置隐含在机器数的最低位之后，叫定点纯整机器数，简称定点整数。另一种约定所有机器数的小数
点隐含在符号位之后、有效部分最高位之前，叫定点纯小数机器数，简称定点小数。无论是定点整
数，还是定点小数，都可以有原码、反码和补码三种形式。
（2）浮点数（Floating-Point Number）
计算机多数情况下采作浮点数表示数值，它与科学计数法相似，把一个二进制数通过移动小数
点位置表示成阶码和尾数两部分：
N = 2
E
× S
其中：E——N 的阶码（Expoent），是有符号的整数
S——N 的尾数（Mantissa），是数值的有效数字部分，一般规定取二进制定点纯小数形
式。
例：1011101B=2+70.1011101，101.1101B=2+30.1011101，0.01011101B=2-1
0.1011101 浮点数的
格式如下：
浮点数由阶码和尾数两部分组成，底数 2 不出现，是隐含的。阶码的正负符号 E0，在最前位，
阶反映了数 N 小数点的位置，常用补码表示。二进制数 N 小数点每左移一位，阶增加 1。尾数是
这点小数，常取补码或原码，码制不一定与阶码相同，数 N 的小数点右移一位，在浮点数中表现
为尾数左移一位。尾数的长度决定了数 N 的精度。尾数符号叫尾符，是数 N 的符号，也占一位。
例：写出二进制数-101.1101B 的浮点数形式，设阶码取 4 位补码，尾数是 8 位原码。
-101.1101 = -0.10111012+3
浮点形式为：
阶码 0011 尾数 11011101
补充解释：阶码 0011 中的最高位“0”表示指数的符号是正号，后面的“011”表示指数是“3”；
尾数 11011101 的最高位“1”表明整个小数是负数，余下的 1011101 是真正的尾数。
例：计算机浮点数格式如下，写出 x=0.0001101B 的规格化形式，阶码是补码，尾数是原码。
x=0.0001101=0.110110-3
又[-3]补=[-001B]补=[1011]补=1101B
所以浮点数形式是
1 101 0 1101000
7) ASCII 码 (American Standard Code for Information Interchange)
美国标准信息交换标准码
常用字符有 128 个，编码从 0 到 127。
空格 ―― 32
‘0’~‘9’ ―― 48 ~ 57
‘A’~‘Z’ ―― 65 ~ 90
‘a’~‘z’ ―― 97 ~ 122
ASCII 码用一个字节来表示，所以英文字符大小都是一个字节汉字在计算机内使用机内码存储，
需要两个字节。
8) 汉字信息编码
1． 汉字输入码
汉字输入方法大体可分为：区位码（数字码）、音码、形码、音形码。
（1）区位码：优点是无重码或重码率低，缺点是难于记忆；
（2）音码：优点是大多数人都易于掌握，但同音字多，重码率高，影响输入的速度；
（3）形码：根据汉字的字型进行编码，编码的规则较多，难于记忆，必须经过训练才能较好
地掌握；重码率低；
（4）音形码：将音码和形码结合起来，输入汉字，减少重码率，提高汉字输入速度。
2．汉字交换码
汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码
标准。自国家标准 GB2312－80 公布以来，我国一直延用该标准所规定的国标码作为统一的汉字信
息交换码。
GB2312－80 标准包括了 6763 个汉字，按其使用频度分为一级汉字 3755 个和二级汉字 3008
个。一级汉字按拼音排序，二级汉字按部首排序。此外，该标准还包括标点符号、数种西文字母、
图形、数码等符号 682 个。
由于 GB2312－80 是 80 年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字
信息的产品采用新颁布的 GB18030 信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，
可解决两岸三地间 GB 码与 BIG5 码间的字码转换不便的问题。
3．字形存储码
字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的
是数字化点阵字模。
一般的点阵规模有 16×16，24×24，32×32，64×64 等，每一个点在存储器中用一个二进制
位（bit）存储。例如，在 16×16 的点阵中，需 16×16bit=32 byte 的存储空间。在相同点阵中，
不管其笔划繁简，每个汉字所占的字节数相等。
为了节省存储空间，普遍采用了字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点
阵字模进行压缩后得到的汉字字形的数字化信息。
图像的大小表示为：分辨率像素大小
例如 1024 768 分辨率下，一张 16 位的图片大小 = 102476816/8(B)
9) 常见的单位与换算:
二进制位：简称位，计算机中信息表示的最小单位，用 bit（比特）表示，也就是一个 0 或者
一个 1。例如 8 可以表示为四位的二进制 1000
8BIT = 1BYTE（简称 B）
1024B = 1KB （千字节）
1024KB = 1MB（兆字节）
1024MB = 1GB （千兆字节）
1024GB = 1TB （兆兆字节）
10) 逻辑运算
概念介绍：
非：not ¬ 与：and ∧ 或：or ∨ 异或：xor ⊕
运算级比较：
括号 > 非 > 与 > 或、异或 （ or 和 xor 是同级的）
如果加入加减乘除，就是以下这样：
注意：同级的运算符不分高低，计算时按照从左到右运算。
运算法则：
∧：两边相同返回真；两边中有一个不同则返回假；
A and B 只要 A 和 B 有一个是 false 就是 false
∨：两边只要又一边为真，即可返回真；否则返回假；
A or B 只要 A 和 B 有一个是 true 就是 true
⊕：两边一样则假，不一样则真
A xor B 只要 A 和 B 不一样就是 true，相同就是 true
即 A xor A = 0
¬：如果后面的为假，则返回真，如果为真，则返回假；
Not 表示取反，Not true = false
A B Not A A and B A or B A xor B
False False True False False False
False True True False True True
True False False False True True
True True False True True False
11) 位运算
表示把整数化成二进制后逐位比较，求出比较结果后，再转换成十进制
常见运算符：and，or，xor，>>(右移)，<<（左移）
运算 10 and 6 10 or 6 10 xor 6 10 >> 3 10 << 3
10 1010 1010 1010 1010 右移
三位
1010 左移
6 0110 0110 0110 三位
二进制结果 0010 1110 1100 1 1010000
最后结果 2 14 12 1 80
说明 转换成二进制后，位数不够的在高位补 0，
然后逐位比较
1 相当于 true
0 相当于 false
10 >> 3 = 10 / 8 = 1
10 << 3 = 10 8 = 80
N >> X = N / (2^X)
N << X = N (2^X)
12) 表达式的三种类型
（一）什么是中缀、前缀、后缀表达式
例子：有一个数学表达式：a(b+c)-d
1：中缀表达式
a(b+c)-d 这个是中缀表达式，运算符号在中间，我们数学中的表达式都是中缀表达式
2：后缀表达式
计算机运算时采用的是后缀表达式，这个表达式的后缀表达式是 abc+d计算机从左到右进行运算，遇到运算符号就把前面两个数值进行相关计算。
3：前缀表达式
前缀表达式就是运算符号在前面，数值放在后面，计算机计算时从右往左运算。
遇到运算符号就把前面两个数值进行相关计算。这个表达式的前缀表达式是 -*a+bcd
（二）把中缀表达式转化成后缀表达式的思想如下：
算法基本思想：
使用三个数组，一个数组保存用户输入的表达式（中缀表达式），一个数组保存后缀
表达式，一个数组作为运算符的栈。
从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理；
1、如果是数字则直接放入后缀表达式数组；
2、如果是左括号则直接入栈；
3、如果是右括号，则把从栈顶直到对应左括号之间的运算符依次退栈，写入后
缀表达式数组,并清除对应的左括号；
4、对于运算符，如果该运算符的优先级大于栈顶优先级，则直接入栈，若该运
算符的优先级小于等于栈顶优先级，则把栈顶运算符逐个出栈，写入后缀表达式
数组，直到遇到左括号或者遇到比它优先级小的运算符。然后再入栈；5、扫描
完成后，取出栈中所有运算符，写入后缀表达式数组。
第五部分 信息安全
计算机安全(computer security)是指防范与保护计算机系统及其信息资源在生存过程中免受蓄
意攻击、人为失误和自然灾害等引起的损失和破坏。
计算机病毒是人类自己想像和发明出来的，它是一种特殊的程序，有着与生物病毒极为相似的
特点。一是寄生性，它们大多依附在别的程序上面。二是隐蔽性，它们是悄然进入系统的，人们很
难察觉。三是潜伏性，它们通常是潜伏在计算机程序中，只在一定条件下才发作的。四是传染性，
它们能够自我复制繁殖，通过传输媒介蔓延。五是破坏性，轻则占用一定数量的系统资源，重则破
坏整个系统。
对于计算机病毒，我们不必谈虎变色，而应采取积极的防治态度。首先，要防止“病从口入”，
因为病毒不是自生的，而是外来的。另外，要用优秀的防杀病毒软件，对外来的软件和资料要进行
严格的检查和杀毒。注意，防杀病毒软件需要及时更新(主要是其中的数据文件)，一般每周一次，
不更新基本上等于没有防杀毒功能。
20 世纪 50、60 年代，黑客(hacker)曾是编程高手的代名词。后来，黑客成为一个独特的群体，
他们通过各种渠道交流技艺，不少人以攻击计算机及其网络系统为乐趣。黑客们的胆大妄为已经给
社会造成了很大的影响，一些黑客已经蜕变为威胁社会安全的罪犯。
要防止“黑客”攻击，主要方法是加强安全措施，例如设置防火墙（见图 3.1.1）。防火墙是一种计
算机设备，它设置在内部网络与外部网络之间，起一个隔离的作用，既可以阻止外部信息非法进入
内部系统，也可以阻止内部人员非法访问外部系统。
例题
1.计算机病毒传染的必要条件是( B ) 。
A)在内存中运行病毒程序 B)对磁盘进行读写操作
C)在内存中运行含有病毒的程序 D) 复制文件
2.计算机病毒是( B )
A)通过计算机传播的危害人体健康的一种病毒
B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合
C)一种由于计算机元器件老化而产生的对生态环境有害的物质
D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒
3、计算机病毒的特点是（ C ）
A. 传播性、潜伏性、易读性与隐蔽性 B. 破坏性、传播性、潜伏性与安全性
C. 传播性、潜伏性、破坏性与隐蔽性 D. 传播性、潜伏性、破坏性与易读性
第六部分 计算机网络
1) 关于网络的一些定义
所谓计算机网络，就是利用通信线路和设备，把分布在不同地理位置上的多台计算机连接起来。
计算机网络是现代通信技术与计算机技术相结合的产物。
网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。
TCP/IP
用于网络的一组通讯协议。包括 IP(Internet Protocol)和 TCP(Transmission Control Protocol)。
TCP/IP 是一组协议，包括上百个各种功能的协议，其中 TCP 和 IP 是最核心的两个协议。TCP/IP
协议把 Internet 网络系统描述成具有四个层次功能的网络模型。
- 链路层：这是 TCP/IP 结构的第一层，也叫网络接口层，其功能是提供网络相邻节点间的信 息传输以及网络硬件和设备驱动。
- 网络层：（IP 协议层）其功能是提供源节点和目的节点之间的信息传输服务，包括寻址和 路由器选择等功能。
- 传输屋：（TCP 协议）其功能是提供网络上的各应用程序之间的通信服务。
- 应用层：这是 TCP/IP 最高层，其功能是为用户提供访问网络环境的手段，主要提供 FTP、 TELNET、GOPHER 等功能软件。 IP 协议适用于所有类型网络。TCP 协议则处理 IP 协议所遗留的通信问题，为应用程序提供可靠 的通信连接，并能自动适应网络的变化。TCP/IP 目前成为最为成功的网络体系结构和协议规范。 Netbeui 一种非常简单的协议，MICROSOFT 开发。 IPX 用于 NOVELL 网络。 网络的发展 计算机网络的发展过程大致可以分为三个阶段： 远程终端联机阶段： 主机—终端 计算机网络阶段： 计算机—计算机 Internet 阶段： Internet 2) 网络的主要功能： （1）资源共享 （2）信息传输 （3）分布处理 （4）综合信息服务 3) 网络的分类 计算机网络的分类方式有很多种,可以按地理范围、拓扑结构、传输速率和传输介质等分类。
- 按地理范围分类 ① 局域网 LAN(Local Area Network) 局域网地理范围一般几百米到 10km 之内，属于小范围内的连网。如一个建 筑物内、一个学校内、一个工厂的厂区内等。局域网的组建简单、灵活，使用方 便。 ② 城域网 MAN(Metropolitan Area Network) 城域网地理范围可从几十公里到上百公里,可覆盖一个城市或地区,是一种中 等形式的网络。 ③ 广域网 WAN(Wide Area Network) 广域网地理范围一般在几千公里左右,属于大范围连网。如几个城市,一个或 几个国家,是网络系统中的最大型的网络,能实现大范围的资源共享,如国际性的 Internet 网络。
- 按传输速率分类 ① 网络的传输速率有快有慢,传输速率快的称高速网,传输速率慢的称低速网。传输速 率的单位是 b/s(每秒比特数,英文缩写为 bps)。 一般将传输速率在Kb/s—Mb/s范围的网络称低速网 , 在 Mb/s—Gb/s 范围的网称 高速网。 也可以将 Kb/s 网称低速网,将 Mb/s 网称中速网,将 Gb/s 网称高速网。 ② 网络的传输速率与网络的带宽有直接关系。带宽是指传输信道的宽度,带宽的单位 是 Hz(赫兹)。按照传输信道的宽度可分为窄带网和宽带网。 一般将 KHz—MHz 带宽的网称为窄带网,将 MHz—GHz 的网称为宽带网,也可以将 kHz 带宽的网称窄带网,将 MHz 带宽的网称中带网,将 GHz 带宽的网称宽带网 ③ 通常情况下,高速网就是宽带网,低速网就是窄带网。
- 按传输介质分类 传输介质是指数据传输系统中发送装置和接受装置间的物理媒体,按其物理形态可以 划分为有线和无线两大类。 ① 有线网 传输介质采用有线介质连接的网络称为有线网,常用的有线传输介质有双绞线、同 轴电缆和光导纤维。 ● 双绞线是由两根绝缘金属线互相缠绕而成,这样的一对线作为一条通信线路, 由四对双绞线构成双绞线电缆。双绞线点到点的通信距离一般不能超过 100m。 目前,计算机网络上使用的双绞线按其传输速率分为三类线、五类线、六类线、七 类线,传输速率在 10Mbps 到 600Mbps 之间,双绞线电缆的连接器一般为 RJ-45。 ● 同轴电缆由内、外两个导体组成,内导体可以由单股或多股线组成,外导体一 般由金属编织网组成。内、外导体之间有绝缘材料,其阻抗为 50Ω。同轴电缆分 为粗缆和细缆,粗缆用 DB-15 连接器,细缆用 BNC 和 T 连接器。 ● 光缆由两层折射率不同的材料组成。内层是具有高折射率的玻璃单根纤维体 组成,外层包一层折射率较低的材料。光缆的传输形式分为单模传输和多模传输, 单模传输性能优于多模传输。所以,光缆分为单模光缆和多模光缆,单模光缆传送 距离为几十公里,多模光缆为几公里。光缆的传输速率可达到每秒几百兆位。光缆 用ST 或SC 连接器。光缆的优点是不会受到电磁的干扰,传输的距离也比电缆远， 传输速率高。光缆的安装和维护比较困难,需要专用的设备。 ② 无线网 采用无线介质连接的网络称为无线网。目前无线网主要采用三种技术：微波通信, 红外线通信和激光通信。这三种技术都是以大气为介质的。其中微波通信用途最广, 目前的卫星网就是一种特殊形式的微波通信,它利用地球同步卫星作中继站来转发微 波信号,一个同步卫星可以覆盖地球的三分之一以上表面,三个同步卫星就可以覆盖地 球上全部通信区域。
- 按拓扑结构分类 计算机网络的物理连接形式叫做网络的物理拓扑结构。连接在网络上的计算机、大容 量的外存、高速打印机等设备均可看作是网络上的一个节点,也称为工作站。计算机网络中 常用的拓扑结构有总线型、星型、环型等。 ① 总线拓扑结构 总线拓扑结构是一种共享通路的物理结构。这种结构中总线具有信息的双向传输 功能，普遍用于局域网的连接,总线一般采用同轴电缆或双绞线。 总线拓扑结构的优点是：安装容易,扩充或删除一个节点很容易,不需停止网络的 正常工作,节点的故障不会殃及系统。由于各个节点共用一个总线作为数据通路,信道 的利用率高。但总线结构也有其缺点：由于信道共享,连接的节点不宜过多，并且总线 自身的故障可以导致系统的崩溃。 ② 星型拓扑结构 星型拓扑结构是一种以中央节点为中心,把若干外围节点连接起来的辐射式互联 结构。这种结构适用于局域网,特别是近年来连接的局域网大都采用这种连接方式。这 种连接方式以双绞线或同轴电缆作连接线路。 星型拓扑结构的特点是：安装容易,结构简单,费用低,通常以集线器(Hub)作为中央 节点,便于维护和管理。中央节点的正常运行对网络系统来说是至关重要的。 ③ 环型拓扑结构 环型拓扑结构是将网络节点连接成闭合结构。信号顺着一个方向从一台设备传到 另一台设备,每一台设备都配有一个收发器,信息在每台设备上的延时时间是固定的。 这种结构特别适用于实时控制的局域网系统。 环型拓扑结构的特点是：安装容易,费用较低,电缆故障容易查找和排除。有些网 络系统为了提高通信效率和可靠性,采用了双环结构,即在原有的单环上再套一个环,使 每个节点都具有两个接收通道。环型网络的弱点是,当节点发生故障时,整个网络就不 能正常工作。 4) 网络的体系结构 OSI 的七层体系结构从上往下依次是： 应用层,表示层,会话层,运输层,网络层,数据链路层,物理层 5) 局域网的工作方式 1.客户机/服务器(Client/Server): 提供资源并管理资源的计算机称为服务器；使用共享资源的计算机称客户机； 2.对等(Peer-to-Peer): 不使用服务器来管理网络共享资源，所以的计算机处于平等的地位。 6) Internet 的形成与发展 Internet 又称国际互联网，规范的译名是“因特网”，指当前各国、各地区众多开发的网络连接 在一起而形成的全球性网络。 我国 Internet 的发展情况: 八十年代末，九十年代初才起步。 1989 年我国第一个公用分组交换网 CNPAC 建成运行。 我国已陆续建成与 Internet 互联的四个全国范围的公用网络： 中国公用计算机互联网（CHINANET）、中国金桥信息网（CHINAGBN） 中国教育和科研计算机网（CERNET）、中国科学技术网（CSTNET） 7) IP 地址 我们把整个 Internet 看作一个单一的、抽象的网络，所谓 IP 地址，就是为 Internet 中的每一 台主机分配一个在全球范围唯一地址。IPv4 地址是由 32 位二进数码表示的，为方便记记忆，把这 32 位二进制数每 8 个一段用“.” 隔开，再把每一段的二进制数化成十进制数，也就得到我们现 在所看到的 IP 地址形式。 IP 地址是用“.”隔开地四个十进制整数，每个数字取值为 0—255。 IP 地址分 A、B、C、D；E 五类，目前大量使用的是 A、B、C 三类，D 类为 Internet 体系结 构委员会 IAB 专用，E 类保留在今后使用。 最高位 1..126 为 A 类，128..191 是 B 类，192..223 是 C 类。 域名 域名地址采用层次结构，一个域名一般有 3－5 个子段，中间用“. ”隔开。IP 地址作为 Internet 上主机的数字标识，对计算机网络来说是非常有效的。但对于使用者来说，很难记忆这些由数字组 成的 IP 地址了。为此，人们研究出一种字符型标识，在 Internet 上采用“名称”寻址方案，为每台 计算机主机都分配一个独有的“标准名称”，这个用字符表示的“标准名称”就是我们现在所广泛 使用的域名（DN，domain name）。因此主机的域名和 IP 地址一样，也采用分段表示的方法。其结 构一般是如下样式：计算机名.组织结构名.网络名.最高层域名。 顶级域名有三类： • 国家顶级域名,如 cn（中国）、us（美国）、uk（英国）； • 国际顶级域名—— int ，国际性组织可在 int 下注册； • 通用顶级域名，如：com、net、edu、gov、org、„„ 有了域名标识，对于计算机用户来说，在使用上的确方便了很多。但计算机本身并不能自动识 别这些域名标识，于是域名管理服务器 DNS（domain name system）就应运而生了。所谓的域名管 理系统 DNS（domain name system）就是以主机的域名来代替其在 Internet 上实际的 IP 地址的系统， 它负责将 Internet 上主机的域名转化为计算机能识别的 IP 地址。从 DNS 的组织结构来看，它是一 个按照层次组织的分布式服务系统；从它的运行机制来看，DNS 更像一个庞大的数据库，只不过这 个数据库并不存储在任一计算机上，而是分散在遍布于整个 Internet 上数以千计的域名服务器中而 已。通过上面的 IP 地址、域名 DN 和域名管理系统 DNS，就把 Internet 上面的每一台主机给予了 唯一的定位。三者之间的具体联系过程如下：当连接网络并输入想访问主机的域名后，由本地机向 域名服务器发出查询指令，域名服务器通过连接在整个域名管理系统查询对应的 IP 地址，如找到 则返回相应的 IP 地址，反之则返回错误信息。说到这里，想必大家都明白了为什么当我们在浏览 时，浏览器左下角的状态条上会有这样的信息：“正在查找 xxxxxx”、“xxxxxx 已经发现，正在连接 xxxxxx”，其实这也就是域名通过 DNS 转化为 IP 地址的过程。 当然域名通过 DNS 转化为 IP 地址需要等待一段时间，因为如果你所使用的域名服务器上如果 没有你所需要域名的对应 IP 地址，它就会向上级域名服务器查询，如此类推，直至查到结果，或 返回无效信息。一般而言，这个查询过程都非常短，你很难察觉到。 8) Internet（译为因特网或国际互联网）的服务与工具 Internet 的服务有：电子邮件、远程登陆、文件传输、信息服务等； 电子邮件（E-Mail）：电子邮件地址格式为： 收信人邮箱名@邮箱所在主机的域名。例：winner01@ 21cn.com ，[email protected] 远程登陆（Telnet）：指通过 Internet 与其它主机连接。 登陆上另一主机，你就可以使用该主机对外开放的各种资源，如联机检索、数据查询。 文件传输（FTP）：用于在计算机间传输文件。如下载软件等。 9) 全球信息网（WWW－World Wide Web） 又称万维网，是一个全球规模的信息服务系统，由遍布于全世界的数以万计的 Web 站点组成。