分区联赛基础知识
图片预览
文档简介
(共78张PPT)
信息学奥林匹克
分区联赛的基础知识
初赛试题结构
第一部分 基础知识
第二部分 问题求解
第三部分 阅读程序
第四部分 完善程序
第一部分
一、计算机的发展与应用
二、计算机概述
三、多媒体技术应用
四、计算机网络使用基础
一、计算机的发展与应用
一、计算机的发展与应用
1、下面列出的四项中，不属于计算机病毒特征的是( )
A．潜伏性 B．激发性 C．传播性 D．免疫性
2、国产银河型数字式电子计算机是属于下列哪种类型计算机( )
A．微型 B．小型 C．中型 D．巨型
3、计算机病毒是指( )
A．能传染给用户的磁盘病毒 B．已感染病毒的磁盘
C．具有破坏性的特制程序 D．已感染病毒的程序
4、最早的计算机的用途是用于( )
A．科学计算 B．自动控制
C．辅助设计 D．系统仿真
5、操作系统在第几代计算机开始应用( )
A．第一代 B．第二代 C．第三代 D．第四代
第二代晶体管计算机(1956-1963)
1948年，晶体管的发明大大促进了计算机的发展，晶体管代替了体积庞大电子管，电子设备的体积不断减小。1956年，晶体管在计算机中使用，晶体管和磁芯存储器导致了第二代计算机的产生。第二代计算机体积小、速度快、功耗低、性能更稳定。首先使用晶体管技术的是早期的超级计算机，主要用于原子科学的大量数据处理，这些机器价格昂贵，生产数量极少。
1960年，出现了一些成功地用在商业领域、大学和政府部门的第二代计算机。第二代计算机用晶体管代替电子管，还有现代计算机的一些部件:打印机、磁带、磁盘、内存、操作系统等。计算机中存储的程序使得计算机有很好的适应性，可以更有效地用于商业用途。在这一时期出现了更高级的COBOL(Common Business-Oriented Language)和FORTRAN(Formula Translator)等语言，以单词、语句和数学公式代替了含混晦涩的二进制机器码，使计算机编程更容易。新的职业(程序员、分析员和计算机系统专家)和整个软件产业由此诞生。
1 什么是CISC机？什么是RISC机？
2 计算机的发展分为几个阶段？正在研制的新型计算机具有哪些特点？
3 简述“三金”工程的含义。
4 什么是计算机病毒，它具有哪些特征，如何采取具体的防范措施？
资 料
CISC微处理器是台式计算机系统的中心，这个核心中的核心就是运行指令的电路。指令由完成任务的多个步骤所组成，例如把数值传送进寄存器或进行相加运算，都是需要指令的，这些指令被称为微代码（microcode），不同制造商的微处理器有不同的微代码系统，制造商可按自己的意愿使微代码做得简单或复杂。指令系统越丰富，微处理器编程就越简单，然而，执行速度也相应越慢，而且设计这样的处理器的代价也就越大，但是由于指令系统丰富，对上层的支持就比较好。下面我们来看看两种处理器的比较：
复杂指令系统计算机（CISC）包含一个丰富的微代码系统，简化了处理器上运行程序的编制。
精简指令系统计算机（RISC）有一个精简的指令系统。从而提高了微理器的效率，但需要更复杂的外部程序，也就是把在处理器层没有完成的工作放到了上层进行，而处理器层少的这些成本可以用对物理器件速度的提高上去。
RISC方案基于John Cocke在IBM公司的工作，他发现约20％的计算机指令完成约80％的工作。因此，RISC系统通常比CISC系统要快。他的80／20规则促进了RISC体系结构的开发。大多数台式微处理器方案如Intel和Motorola芯片都采用CISC方案；工作站处理器加MIDS芯片DEC Alpha和IBM RS系列芯片均采用RISC体系结构。将来的处理器会在RISC和CISC之间寻找到一条合适的途径来保证处理器的成本较小，而且功能比较合适。
二、计算机概述
1. 世界上首先实现存储程序的电子数字计算机是（ ）。
A．ENIAC B、UNIVAC
C、EDVAC D、EDSAC
2、计算机能直接执行的指令包括两部分，它们是( )
A．源操作数与目标操作数 B．操作码与操作数
C．ASCII码与汉字代码 D．数字与字符
3、下列诸因素中，对微机工作影响最小的是( )
A．尘土 B．噪声 C．温度 D．湿度
4、在计算机中，ASCII码是几位二进制代码( )
A．7 B．8 C．12 D．16
5、下面四个不同进制的数，最小的一个数是( ) A．(11011001)2 B．(37)8
C．(75)10 D．(A7)16
资 料
1 简述冯 诺依曼型计算机的组成与工作原理。
2 计算机硬件系统由哪五个基本部分组成？它们各自的功能是什么？
3 机器指令由哪几部分组成？按其功能分为哪几种指令类型？
4.在计算机中，带符号数有几种表示方法？它们之间的转换关系是什么？各自有什么用途？
5 ASCII码由几位二进制数组成？它能表示什么信息？
6 二进制的计算规则。
三、多媒体技术应用
1．彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（ ）。
A. 红 B. 白 C. 蓝 D. 绿 E. 橙
2．下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。
A.CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存
3.下列哪个（些）不是个人计算机的硬件组成部分（ ）。 A.主板 B.虚拟内存 C.电源 D.硬盘 E.总线
4.一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，屏幕左上角开始，位移为0，然后逐列逐列存储。求位于屏幕（X，Y）的第一个字节的位移是（ ） A.（Y*80+X）*2-1 B.（（Y-1）*80+X-1）*2 C.（Y*80+X-1）*2 D.（（Y-1）*80+X）*2-1
1. 多媒体计算机系统的基本配置包含了哪些设备？
2 CD-ROM的功能大小取决于哪几个参数？
3 显示存储空间由哪几个主要的因素决定？
4 目前国际上有哪几种压缩数据的标准？
资 料
四、计算机网络使用基础
1、Internet的规范译名应为( )
A．英特尔网 B．因特网
C．万维网 D．以太网
2、下列哪些计算机网络不是按覆盖地域划分的( )
A．局域网 B．都市网
C．广域网 D．星型网
3、以下列举Internet的各种功能中，错误的是( )
A．编译程序 B．传送电子邮件
C．查询信息 D．数据库检索
4、计算机网络最突出的优点是( )
A．传送信息速度高 B．共享资源
C．内存容量大 D．交互性好
5、TCP／IP协议共有( )层协议 A.3 B.4 C.5 D.6
1 什么是WAN网？什么是LAN网，他们各自的功能是什么？
2 什么是计算机网络的拓扑结构？常见的拓扑结构有几种？
3. 什么是计算机网络协议？说出OSI 的七层协议的名称。
4. 在Internet中，IP地址和域名的作用是什么？它们之间有什么异同？
资 料
第二部分
数学知识
组合、排列、集合等
数据结构
图、树等
第三部分 阅读程序
直接推理
有流程图推断算法
动态模拟
由底向上阅读分析
例一
Var
m,n,i:integer;
t:extended;
Begin
read(n,m);
t:=1;
for i:=1 to m do t:=t*(n-i+1)/i;
writeln(t:0:0);
End.
输入：
10 5
输出：
——————
例二
Label 10,20,30;
Var s,p:string;I,k,n,j,m:integer;
Begin
readln(s);n:=length(s);
readln(p);m:=length(p);
i:=0;
10: i:=i+1;j:=I;k:=1;
例二（续）
20: If s[ j ]<>p[ k ]
then begin
if ii:=0;
goto 30;
end
else if kthen begin j:=j+1;k:=k+1;goto 20; end;
30:writeln(i);
End.
输入
asabcdffdin
fdi
输出_________
例三
Var i,j:integer;
a:array[1..3,1..3] of integer;
Begin
for i:=1 to 3 do
begin
for j:=1 to 3 do
begin
if i=3 then a[i,j]:=a[i-1,a[i-1,j]]]+1 else a[i,j]:=j;
write(a[i.j]);
end;
Writeln End Readln
End.
例四
Var a,d:array[1..100] of integer;
N,I,j,k,x,s:integer;
Begin
n:=5;a[1]:=1;d[1]:=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; a[j+1]:=a[j]+k; write(a[j],’ ’);
end;
writeln(‘…’);d[i+1]:=d[i]+I;a[1]:=d[i+1];
end;
End. 输出：_____________
第四部分 完善程序
变量方面的填空（定义类型、设定初值、变量赋值等）
循环方面的填空（定义变量、设定循环的初值和终值、在循环中如何引用）
分支转移方面的填空（定义布尔表达式、确定程序的走向）
主程序和子程序关系方面的填空（值参、变参、调用格式）
输入输出方面的填空
不含子程序
例一、求元素之和最大的子方阵：在m*n的正整数数字方阵中，找出一个p*q的子阵，使得其元素之和最大。
3 8 4 22
11 1 7 9
5 21 6 2
10 3 8 9
2 7 12 3
5 21 6
10 3 8
2 7 12
程序清单
Var a:array[1..20,1..20] of integer;
m,n,p,q,I,j,max,p1,q1,s,i1,j1:integer;
Begin
for i:=1 to 20 do
for j:=1 to 20 do
a[i,j]:=0;
readln(m,n);
for i:=1 to m do
begin for j:=1 to n do read(a[i,j]);readln end;
readln(p,q);
max:=0;
程序清单（续）
For i:=1 to m-p+1 do
for j:=1 to n-q+1do
begin __(1)___;
for i1:=I to p+i-1 do
for j1:=j to q+j-1 do ___(2)____;
if s>max then begin ___(3)___;
p1:=I;q1:=j;end;
end;
For i:=p1 to ___(4)____ do
Begin for j:=q1 to ____(5)____do write(a[I,j]:3);writeln;end;readln
end.
例二
Const maxm=10000;
Var I,k,m,n,rest,start,temp:longint;
a:array[0..maxm] of longint;
Begin
write(‘input m,n:’);
readln(m,n);
for i:=0 to m-1 do a[i]:=random(100);
writeln(’before move’);
for i:=0 to m-1 do write(a[i]:5);writeln;
rest:=m;start:=0;
while ____(1)______do
begin k:=start;
repeat k:=(k+n) mod m until k<=start;
例二（续）
If ___(2)____then
Begin
temp:=a[k];
Repeat
a[k]:=a[(m*n+k-n) mod m];
k:=(m*n+k-n) mod m; _____(3)______
until k=start;
______(4)_______;
End;
_______(5)_____
End;
Writeln(‘after move’);
For i:=0 to m-1 do write(a[i]:5);Writeln
End.
完善含有子程序的程序
例、 输入任意一个正整数n，输出组成n的互不相同的菲波那契数。
Var n:integer;
first:boolean;
Function find(n:integer):integer;
Var a,b,c:integer;
Begin a:=1;b:=1;
repeat c:=___(1)_____;a:=b;b:=c;
until b>=n;
if b=n then find:=__(2)__ else find:=__(3)__
End;
例（续）
Procedure p(n:integer);
Var a:integer;
begin
a:=find(n);
if first then begin write(a:4);first:=false;end
else write(‘+’,a:4);
if aEnd;
begin readln(n);first:=true;write(n:5,’=‘);p(n);writeln;
readln
end.
与您共勉
“愚蠢的教师把学生讲糊涂了，聪明的教师把学生讲明白了，只有那些富有智慧的教师把学生讲聪明了。 ”
谢谢 ！
联系方式：
电话: 83666039
E-mail: bj12zhyw@
1 . 1 CISC 与RISC
CISC即Complex Instruction Set Computer。在最初，人们采用的优化方法是增强计算机指令系统功能的方法，就是设置一些功能复杂的指令，把一些原来由软件实现的，常用的功能改用硬件的指令系统实现，以提高计算机的执行速度，这种计算机系统就被称为复杂指令系统计算机。
RISC即Reduced Instruction Set Computer。是在80年代才发展起来的，其基本思想是尽量简化计算机指令功能，只保留那些功能简单、能在一个节拍内执行完成的指令，而把较复杂的功能用一段子程序来实现，这种计算机系统就被称为精简指令系统计算机。
1 . 2 计算机发展的阶段
第一代 第二代 第三代 第四代
1946-1958 1958-1964 1964-1975 1975-现在
主机电子器件 电子管 晶体管 中小规模集成电路 大规模/超大规模集成电路
内存 汞延迟线 磁芯存储器 半导体存储器 半导体存储器
外存储器 穿孔卡片，纸带 磁带 磁带，磁盘 磁盘、光盘等大容量存储器
处理速度 (指令数/秒) 几千条 几百万条 几千万条 数亿条以上
1 . 2 研制中的第五代计算机
1、创建非冯 诺伊曼式语言
LISP, PROLOG
2、创建以人脑神经系统处理信息的原理为基础的非冯 诺伊曼式的计算机模型
生物计算机
光子计算机
量子计算机
1 . 3 三金工程
“金桥”工程又称经济信息通信网工程，它是建设国家
公用经济信息通信网、实现国民经济信息化的基础设
施。这项工程的建设，对于提高我国宏观经济调控和
决策水平以及信息资源共享、推动信息服务业的发
展，都具有十分重要的意义。
“金关”工程又称为海关联网工程，其目标是推广电子
数据交换（EDI）技术，以实现货物通关自动化、国
际贸易无纸化。
“金卡”工程又称电子货币工程，它是借以实现金融电子化和商业流通现代化的必要手段。
1 . 4 计算机病毒
计算机病毒是一种功能特殊的计算机程序，它一旦运行，便取得系统控制权,同时把自己复制到媒体中去。
计算机病毒的特征：
1、能够自身复制到其他程序中。
2、不独立以文件形式存在，仅附加在别的程序上。当调用该程序运行时，此病毒则首先运行。
2 . 1 冯 诺伊曼型计算机
输 入 设 备
运算器
存储器
控制器
输 出 设 备
输入
输出
第一台具有存储功能的计算机EDVAC逻辑功能图
2 . 2 计算机硬件系统
计算机硬件(computer hardware)主要由输入设备、输出设备、存储器、运算器、控制器五大部分组成
1) 输入设备 若要计算机按我们的要求进行工作，计算机必须接受外部的信息。使计算机从外部获得信息的设备，称为输入设备(input device)。 常用的输入设备包括键盘、光笔、鼠标器、扫描仪、话筒等，通过它们可以输入文字、图像、声音等不同的信息。 输入设备种类很多，近几年来出现了触摸屏、手写汉字输入设备、自然语言输入设备、数码照相机等。
2) 输出设备 计算机把信息处理的结果以人们能够识别的形式表示出来的设备，称为输出设备(output device)。例如，显示器、打印机、绘图仪等。
3) 存储器 计算机在处理信息的过程中，许多信息被存放在存储器(memory)中。存储器又分为内存储器和外存储器两种。
4) 运算器 运算器 (arithmetic unit) 是计算机实施算术运算和逻辑判断的主要部件。它能按照计算机程序的要求，在控制器的控制下，进行加、减、乘、除等基本运算和进行判别数的符号，比较数的大小等逻辑运算。
5) 控制器 控制器(controller)是指挥、控制计算机运行的中心。它从存储器中取出信息并进行分析，然后根据指令向计算机各个部分发出各种控制信息，使计算机按照要求自动、协调地完成任务。一般将运算器和控制器合称为中央处理器（简称CPU）。
2.3 计算机指令系统
机器指令是要计算机执行某种操作的命令，且由计算机直接识别执行。所有指令的集合称为计算机的指令系统。
一条指令通常有操作码和地址码两部分组成。
操作码 地址码
指令按功能可分为操作类命令和控制转移类命令。
操作码指明计算机执行的某种操作的性质和功能；地址码指出被操作的数据（简称操作数）存放在何处，即指明操作数地址，有的指令格式允许地址码部分就是操作数本身。
2 . 6 软件系统
软件一般分为系统软件和应用软件。
系统软件是生成、准备和执行其他程序所需要的一组程序。它通常负责管理、控制和维护计算机的各种软硬件资源，并为用户提供友好的操作界面。
应用软件是专业人员为各种应用目的而编写的程序。一般不能独立地在计算机上运行，必须要有系统软件的支持。
2.4 机器数
在计算机中，数是存放在由寄存单元组成的寄存器中，二进制数码1和0是由寄存器单元的两种不同的状态来表示的。
为了运算的方便，在计算机中常用三种表示法：
原码
补码
反码
原码表示法
也称为 符号-幅值 表示法
符号位用0-----正数 符号位用1-----负数
其余位表示数的大小
例:X= +1011 [X]原=01011
X= -1011 [X]原=11011
缺点：
运算（加、减法）低效
0有两个表示
+0：00000000 –0：10000000
补码表示法
[X]补=X， 当 X>=0;
[X]补=2(n+1)+X， 当-2n<=X<0 mod( 2(n+1) );
对于定点小数：n=0
定点整数：n>=1
例如：X=+100101 [X]补=0 100101
X=–100101 [X]补=1 011011
特点:1.补码的和等于和的补码,符号位和数值位一样参加运算,不必单独处理,即 [X]补+[Y]补=[X+Y]补
2.补码相减: [X]补-[Y]补=[X]补+[-Y]补
[Y]补→[-Y]补: 符号位连同数值位一起取反加1
反码表示法
当X>=0时，[X]反=X 当X<=0时，符号位为1，其余各位取反。
特点: 1.反码的和等于和的反码
2.有二个零 +0=00……0
-0=11……1
3.当最高位有进位而丢掉进位(即2)时,要在最低位加1(循环进位)
原码,反码和补码之间的转换
[X]反
符号位不变↑数值位 不变(符号位为0)
变反(符号位为1)
+,–←→0,1 ↓
X真值 ←―→ [X]原
数值位不变 ↑ 数值位不变(符号位为0)
变反加1(符号位为1)
符号位不变↓
[X]补
当X为正数，[X]反=[X]原=[X]补=X，
当X为负数时，[X]补=[X]反+1，[[X]补]=[X]原
2 . 5 ASCII码
ASCII码是美国信息交换标准代码的缩略语。是目前国际上最为流行的字符信息编码方案。它包括数字0~9、大小写字母和专用符号等95种可打印字符，还有33种控制字符。
一个字符ASCII码通常占一个字节，用七位二进制编码组成，ASCII码最多可表示128个不同的符号。字节的最高位被很多系统用做校验码，以便提高字符信息传输的可靠性。
2 . 12 汉字信息编码
汉字信息也采用二进制的数字化信息编码。目前的汉字编码方案有二字节、三字节甚至四字节的。
国标码（国家标准信息交换用汉字编码），是二字节码，用七位二进制数编码表示一个汉字。目前国标码收入6763个汉字，其中一级汉字（最常用）3755个，二级汉字3008个，另外还包括682个西文字符、图符。
2 . 6 二进制
采用二进制，优点：
（1）易于物理实现
（2）二进制运算简单
（3）机器可靠性高
（4）通用性强
乘法 除法 整数转换 小数转换
0+0=0 0+1=1
1+0=1 1+1=10
0*0=0 0*1=0
1*0=0 1*1=1
3 . 2 CD-ROM
光驱的技术指标 (1) 数据传输率(Data Transfer Rate),即大家常说的倍速，它是衡量光驱性能的最基本指标。单倍速光驱就是指每秒可从光驱存取150KB数据的光驱。现在年青一代的40或48倍速光驱每秒钟能读取6000KB和7200KB的数据。 (2) 平均寻道时间(Average Access Time),平均寻道时间是指激光头（光驱中用于读取数据的一个装置）从原来位置移到新位置并开始读取数据所花费的平均时间，显然，平均寻道时间越短，光驱的性能就越好。 (3) CPU占用时间(CPU Loading)，CPU占用时间是指光驱在维持一定的转速和数据传输率时所占用CPU的时间，它也是衡量光驱性能好坏的一个重要指标。CPU占用时间越少，其整体性能就越好。 (4) 数据缓冲区(Buffer)，数据缓冲区是光驱内部的存储区。它能减少读盘次数，提高数据传输率。现在大多数光驱的缓冲区为128K或256K。
3 . 3 显示存储空间
显示存储空间
=水平分辨率×垂直分辨率×色彩数目
例如，若采用640 ×480，16色显示模式，只需要150KB的存储空间。但是，如果想在1280 ×1024，16M色的显示模式下运行，4MB的显示存储空间是不可能运行的。
3 .4 压缩标准
目前，国际上的压缩技术标准有 JPEG，MPEG 和P ×4。
JPEG适合于连续色调、多级灰度、彩色或单色静止图象数据压缩的国际标准。可获得10：1到80：1的压缩比。
MPEG包括MPEG视频、 MPEG音频和MPEG系统三部分，处理活动影象中的视频压缩、音频压缩，以及多种压缩后数据流的复合和同步问题。可获得50：1到00：1的压缩比。
P ×4目标是针对可视电话和电视会议的。适应各种通道容量的传输。
4 . 1 广域网和局域网
1、广域网WAN（Wide Area Network）
是跨地域性的网络系统，大多数WAN都是网络互连而成的，如著名的Internet网络。
2、局域网LAN（Local Area Network）
一般由一个部门或公司组建，地理范围仅在建筑楼内或单位内部。
3、城域网：可以看成是广域网的一种。
4 . 2 计算机网络拓扑结构
网络中各个站点相互连接的方法和形式称之为网络拓扑。把向工作站、服务器等网络单元抽象成为“点”，把网络中的电缆等通信媒体抽象为“线”，从而抽象出了络系统的具体结构，即为逻辑结构。网络拓扑结构有：
计算机网络拓扑结构
4.3 网络协议
计算机通信协议指双方在通信中所应共同遵守的约定。计算机通信协议精确地定了计算机在彼此通信时的所有细节。它规定每台计算机发送每条信息的格式和含义，规定哪些情况下应发送那些特殊的信息，以及接受方的计算机所应作出什么反映等等。
OSI七层协议
主机A 主机B
1 应用层 应用层
2 表示层 表示层
3 会话层 会话层
4 运输层 运输层
5 网络层 网络层
6 数据链路层 数据链路层
7 物理层 物理层
应用层协议
表示层协议
会话层协议
运输层协议
网络层协议
链路层协议
物理层协议
4.4 IP地址
Internet中的每台主机都被分配一个唯一的32位地址，即IP地址。该地址由网络号和主机号两部分组成，其中网络号表示一个网络，而主机号表示这个网络中的一台计算机。
IP地址由4个十进制数字字段组成, 字段之间用点分开, 4个字段中的每个数字在0~255之间，如210.30.240.11。。
IP地址类型
IP地址按网络规模的大小主要可分成三类: A类地址、B类地址、C类地址。A类的第一个字段的值在1～126之间，一般用于大型网络；B类的第一个字段的值在128 ～ 191之间，一般用于中型网络或网络管理器，如路由器等；C类的第一个字段在值在191 ～ 233之间，一般用于小型网络。
网络地址数 网络主机数 主机总数
A类 126 16,38 7,064 2,064,770,064
B类 16,256 6 4,516 1,048,872,096
C类 2,064,512 254 524,386,048
域名
用IP地址标识主机既没有规律，又很难记忆，用户很难用数字表示的IP地址与计算机的情况联系起来，给访问Internet带来了很大的不便如果采用域名系统，就可以很好地解决这些问题。
域名系统是由TCP/IP提供的一种服务，可以将域名翻译成相应的IP地址。域名系统采用层次结构，按地理域或组织域进行分层，各层间用圆点“.” 隔开。在主机的域名表示中，从左向右，域名依次从小到大，例如在www.easthuman.中，最高域名为cn，次高域名为com，最后一个域名为easthuman。
数学相关题目
1．（第八届）在书架上放有编号为1，2，...n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时,原来位置为1 2 3,放回去时只能为： 3 1 2 或 2 3 1 这两种。 问题：求当n=5时满足以上条件的放法共有多少种 (不用列出每种放法)
2.(第九届) 某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程为C1，C2，C3，C4，C5，C6，S(Ci)为学习Ci 的学生集合。已知S(Ci)∩S(C6)≠ф，i=1，2，...，5，S(Ci)∩S(Ci+1)≠ф，i=1，2，3，4，S(C5)∩S(C1)≠ф，问至少安排_____天才能考完这6门课程。
题目
3．(第七届)平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形
4．（第十届）已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案： 。
从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.
2.组合的定义:
从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.
3.排列数公式:
4.组合数公式:
1.排列的定义:
排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题.
例1 学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？
解 先排学生共有 种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有 种选法.根据乘法原理,共有的不同坐法为 种.
结论1 插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.
分析 此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待.所涉及问题是排列问题.
解 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法.
例2 5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法
结论2 捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.
分析 此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题.
解 把所有的硬币全部取出来,将得到 0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法.
例3 袋中有5分硬币23个,1角硬币10个,如果从袋中取出2元钱,有多少种取法
结论3 剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法.
分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.
例4 学校安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序
解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有 种.
结论4 对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求.
分析 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性.
例5 某个班级共有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种
解 43人中任抽5人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有1人在内的抽法有 种.
结论5 排异法:有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除.
分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.
数据结构相关题目
1.(第六届)已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
2．(第七届)已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA，则该二叉树的先序遍历的顺序为：_________。
3．（第九届）无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_______个顶点。
扩展
二叉树
二叉树由结点的有限集合构成，这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别成为这个根的左子树和右子树的二叉树（它们也是结点的集合）组成。
二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
二叉树的五种形态
（1） （2） （3） （4） （5）
满二叉树
如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称为满二叉树。
在满二叉树里，树叶的个数等于分支结点个数加一。
完全二叉树
如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层左边的若干位置，则此二叉树称作完全二叉树。
二叉树的遍历
先序：根-左子树-右子树 (abcd)
中序：左子树-根-右子树 (badc)
后序：左子树-右子树-根 (bdca)
a
b
c
d
图
习惯上，常用G=(V,E)代表一个图，图中的结点又称为顶点，V是结点的有限集合，结点的偶对称为边，E是边的集合。
任意一个具有n个结点的无向图，其边数小于等于n*(n-1)/2;我们把边数恰好等于n*(n-1)/2的n个结点的无向图称为完全图。
在一个n个结点的有向图中，最大边数为n*(n-1)。
一个结点的度就是与该结点相关联的边的数目。
1．(第七届)一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点 A)2h-1 B)2h—1 C)2h十1 D)h十1
2．(第七届)无向图G＝(V，E)，其中V＝{a，b，c，d，e，f } E＝{(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}， 对该图进行深度优先遍历，得到的顶点序列正确的是( ) A)a，b，e，c，d，f B)a，c，f，e，b，d C)a，e，b，c，f，d D)a，b，e，d，f，c
3．（第八届）按照二叉树的定义，具有3个结点的二叉树有( )种。 A)3 B)4 C)5 D)6
4．（第八届）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。 A)1／2 B)1 C)2 D)4
5.（第九届） 假设我们用d=(a1,a2,...,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d 值合理（ ）。 A）{5，4，4，3，1} B）{4，2，2，1，1} C）{3，3，3，2，2} D）{5，4，3，2，1} E）{2，2，2，2，2}
6．（第十届）满二叉树的叶结点个数为N，它的结点总数为 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1
信息学奥林匹克
分区联赛的基础知识
初赛试题结构
第一部分 基础知识
第二部分 问题求解
第三部分 阅读程序
第四部分 完善程序
第一部分
一、计算机的发展与应用
二、计算机概述
三、多媒体技术应用
四、计算机网络使用基础
一、计算机的发展与应用
一、计算机的发展与应用
1、下面列出的四项中，不属于计算机病毒特征的是( )
A．潜伏性 B．激发性 C．传播性 D．免疫性
2、国产银河型数字式电子计算机是属于下列哪种类型计算机( )
A．微型 B．小型 C．中型 D．巨型
3、计算机病毒是指( )
A．能传染给用户的磁盘病毒 B．已感染病毒的磁盘
C．具有破坏性的特制程序 D．已感染病毒的程序
4、最早的计算机的用途是用于( )
A．科学计算 B．自动控制
C．辅助设计 D．系统仿真
5、操作系统在第几代计算机开始应用( )
A．第一代 B．第二代 C．第三代 D．第四代
第二代晶体管计算机(1956-1963)
1948年，晶体管的发明大大促进了计算机的发展，晶体管代替了体积庞大电子管，电子设备的体积不断减小。1956年，晶体管在计算机中使用，晶体管和磁芯存储器导致了第二代计算机的产生。第二代计算机体积小、速度快、功耗低、性能更稳定。首先使用晶体管技术的是早期的超级计算机，主要用于原子科学的大量数据处理，这些机器价格昂贵，生产数量极少。
1960年，出现了一些成功地用在商业领域、大学和政府部门的第二代计算机。第二代计算机用晶体管代替电子管，还有现代计算机的一些部件:打印机、磁带、磁盘、内存、操作系统等。计算机中存储的程序使得计算机有很好的适应性，可以更有效地用于商业用途。在这一时期出现了更高级的COBOL(Common Business-Oriented Language)和FORTRAN(Formula Translator)等语言，以单词、语句和数学公式代替了含混晦涩的二进制机器码，使计算机编程更容易。新的职业(程序员、分析员和计算机系统专家)和整个软件产业由此诞生。
1 什么是CISC机？什么是RISC机？
2 计算机的发展分为几个阶段？正在研制的新型计算机具有哪些特点？
3 简述“三金”工程的含义。
4 什么是计算机病毒，它具有哪些特征，如何采取具体的防范措施？
资 料
CISC微处理器是台式计算机系统的中心，这个核心中的核心就是运行指令的电路。指令由完成任务的多个步骤所组成，例如把数值传送进寄存器或进行相加运算，都是需要指令的，这些指令被称为微代码（microcode），不同制造商的微处理器有不同的微代码系统，制造商可按自己的意愿使微代码做得简单或复杂。指令系统越丰富，微处理器编程就越简单，然而，执行速度也相应越慢，而且设计这样的处理器的代价也就越大，但是由于指令系统丰富，对上层的支持就比较好。下面我们来看看两种处理器的比较：
复杂指令系统计算机（CISC）包含一个丰富的微代码系统，简化了处理器上运行程序的编制。
精简指令系统计算机（RISC）有一个精简的指令系统。从而提高了微理器的效率，但需要更复杂的外部程序，也就是把在处理器层没有完成的工作放到了上层进行，而处理器层少的这些成本可以用对物理器件速度的提高上去。
RISC方案基于John Cocke在IBM公司的工作，他发现约20％的计算机指令完成约80％的工作。因此，RISC系统通常比CISC系统要快。他的80／20规则促进了RISC体系结构的开发。大多数台式微处理器方案如Intel和Motorola芯片都采用CISC方案；工作站处理器加MIDS芯片DEC Alpha和IBM RS系列芯片均采用RISC体系结构。将来的处理器会在RISC和CISC之间寻找到一条合适的途径来保证处理器的成本较小，而且功能比较合适。
二、计算机概述
1. 世界上首先实现存储程序的电子数字计算机是（ ）。
A．ENIAC B、UNIVAC
C、EDVAC D、EDSAC
2、计算机能直接执行的指令包括两部分，它们是( )
A．源操作数与目标操作数 B．操作码与操作数
C．ASCII码与汉字代码 D．数字与字符
3、下列诸因素中，对微机工作影响最小的是( )
A．尘土 B．噪声 C．温度 D．湿度
4、在计算机中，ASCII码是几位二进制代码( )
A．7 B．8 C．12 D．16
5、下面四个不同进制的数，最小的一个数是( ) A．(11011001)2 B．(37)8
C．(75)10 D．(A7)16
资 料
1 简述冯 诺依曼型计算机的组成与工作原理。
2 计算机硬件系统由哪五个基本部分组成？它们各自的功能是什么？
3 机器指令由哪几部分组成？按其功能分为哪几种指令类型？
4.在计算机中，带符号数有几种表示方法？它们之间的转换关系是什么？各自有什么用途？
5 ASCII码由几位二进制数组成？它能表示什么信息？
6 二进制的计算规则。
三、多媒体技术应用
1．彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（ ）。
A. 红 B. 白 C. 蓝 D. 绿 E. 橙
2．下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。
A.CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存
3.下列哪个（些）不是个人计算机的硬件组成部分（ ）。 A.主板 B.虚拟内存 C.电源 D.硬盘 E.总线
4.一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，屏幕左上角开始，位移为0，然后逐列逐列存储。求位于屏幕（X，Y）的第一个字节的位移是（ ） A.（Y*80+X）*2-1 B.（（Y-1）*80+X-1）*2 C.（Y*80+X-1）*2 D.（（Y-1）*80+X）*2-1
1. 多媒体计算机系统的基本配置包含了哪些设备？
2 CD-ROM的功能大小取决于哪几个参数？
3 显示存储空间由哪几个主要的因素决定？
4 目前国际上有哪几种压缩数据的标准？
资 料
四、计算机网络使用基础
1、Internet的规范译名应为( )
A．英特尔网 B．因特网
C．万维网 D．以太网
2、下列哪些计算机网络不是按覆盖地域划分的( )
A．局域网 B．都市网
C．广域网 D．星型网
3、以下列举Internet的各种功能中，错误的是( )
A．编译程序 B．传送电子邮件
C．查询信息 D．数据库检索
4、计算机网络最突出的优点是( )
A．传送信息速度高 B．共享资源
C．内存容量大 D．交互性好
5、TCP／IP协议共有( )层协议 A.3 B.4 C.5 D.6
1 什么是WAN网？什么是LAN网，他们各自的功能是什么？
2 什么是计算机网络的拓扑结构？常见的拓扑结构有几种？
3. 什么是计算机网络协议？说出OSI 的七层协议的名称。
4. 在Internet中，IP地址和域名的作用是什么？它们之间有什么异同？
资 料
第二部分
数学知识
组合、排列、集合等
数据结构
图、树等
第三部分 阅读程序
直接推理
有流程图推断算法
动态模拟
由底向上阅读分析
例一
Var
m,n,i:integer;
t:extended;
Begin
read(n,m);
t:=1;
for i:=1 to m do t:=t*(n-i+1)/i;
writeln(t:0:0);
End.
输入：
10 5
输出：
——————
例二
Label 10,20,30;
Var s,p:string;I,k,n,j,m:integer;
Begin
readln(s);n:=length(s);
readln(p);m:=length(p);
i:=0;
10: i:=i+1;j:=I;k:=1;
例二（续）
20: If s[ j ]<>p[ k ]
then begin
if i
goto 30;
end
else if k
30:writeln(i);
End.
输入
asabcdffdin
fdi
输出_________
例三
Var i,j:integer;
a:array[1..3,1..3] of integer;
Begin
for i:=1 to 3 do
begin
for j:=1 to 3 do
begin
if i=3 then a[i,j]:=a[i-1,a[i-1,j]]]+1 else a[i,j]:=j;
write(a[i.j]);
end;
Writeln End Readln
End.
例四
Var a,d:array[1..100] of integer;
N,I,j,k,x,s:integer;
Begin
n:=5;a[1]:=1;d[1]:=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; a[j+1]:=a[j]+k; write(a[j],’ ’);
end;
writeln(‘…’);d[i+1]:=d[i]+I;a[1]:=d[i+1];
end;
End. 输出：_____________
第四部分 完善程序
变量方面的填空（定义类型、设定初值、变量赋值等）
循环方面的填空（定义变量、设定循环的初值和终值、在循环中如何引用）
分支转移方面的填空（定义布尔表达式、确定程序的走向）
主程序和子程序关系方面的填空（值参、变参、调用格式）
输入输出方面的填空
不含子程序
例一、求元素之和最大的子方阵：在m*n的正整数数字方阵中，找出一个p*q的子阵，使得其元素之和最大。
3 8 4 22
11 1 7 9
5 21 6 2
10 3 8 9
2 7 12 3
5 21 6
10 3 8
2 7 12
程序清单
Var a:array[1..20,1..20] of integer;
m,n,p,q,I,j,max,p1,q1,s,i1,j1:integer;
Begin
for i:=1 to 20 do
for j:=1 to 20 do
a[i,j]:=0;
readln(m,n);
for i:=1 to m do
begin for j:=1 to n do read(a[i,j]);readln end;
readln(p,q);
max:=0;
程序清单（续）
For i:=1 to m-p+1 do
for j:=1 to n-q+1do
begin __(1)___;
for i1:=I to p+i-1 do
for j1:=j to q+j-1 do ___(2)____;
if s>max then begin ___(3)___;
p1:=I;q1:=j;end;
end;
For i:=p1 to ___(4)____ do
Begin for j:=q1 to ____(5)____do write(a[I,j]:3);writeln;end;readln
end.
例二
Const maxm=10000;
Var I,k,m,n,rest,start,temp:longint;
a:array[0..maxm] of longint;
Begin
write(‘input m,n:’);
readln(m,n);
for i:=0 to m-1 do a[i]:=random(100);
writeln(’before move’);
for i:=0 to m-1 do write(a[i]:5);writeln;
rest:=m;start:=0;
while ____(1)______do
begin k:=start;
repeat k:=(k+n) mod m until k<=start;
例二（续）
If ___(2)____then
Begin
temp:=a[k];
Repeat
a[k]:=a[(m*n+k-n) mod m];
k:=(m*n+k-n) mod m; _____(3)______
until k=start;
______(4)_______;
End;
_______(5)_____
End;
Writeln(‘after move’);
For i:=0 to m-1 do write(a[i]:5);Writeln
End.
完善含有子程序的程序
例、 输入任意一个正整数n，输出组成n的互不相同的菲波那契数。
Var n:integer;
first:boolean;
Function find(n:integer):integer;
Var a,b,c:integer;
Begin a:=1;b:=1;
repeat c:=___(1)_____;a:=b;b:=c;
until b>=n;
if b=n then find:=__(2)__ else find:=__(3)__
End;
例（续）
Procedure p(n:integer);
Var a:integer;
begin
a:=find(n);
if first then begin write(a:4);first:=false;end
else write(‘+’,a:4);
if a
begin readln(n);first:=true;write(n:5,’=‘);p(n);writeln;
readln
end.
与您共勉
“愚蠢的教师把学生讲糊涂了，聪明的教师把学生讲明白了，只有那些富有智慧的教师把学生讲聪明了。 ”
谢谢 ！
联系方式：
电话: 83666039
E-mail: bj12zhyw@
1 . 1 CISC 与RISC
CISC即Complex Instruction Set Computer。在最初，人们采用的优化方法是增强计算机指令系统功能的方法，就是设置一些功能复杂的指令，把一些原来由软件实现的，常用的功能改用硬件的指令系统实现，以提高计算机的执行速度，这种计算机系统就被称为复杂指令系统计算机。
RISC即Reduced Instruction Set Computer。是在80年代才发展起来的，其基本思想是尽量简化计算机指令功能，只保留那些功能简单、能在一个节拍内执行完成的指令，而把较复杂的功能用一段子程序来实现，这种计算机系统就被称为精简指令系统计算机。
1 . 2 计算机发展的阶段
第一代 第二代 第三代 第四代
1946-1958 1958-1964 1964-1975 1975-现在
主机电子器件 电子管 晶体管 中小规模集成电路 大规模/超大规模集成电路
内存 汞延迟线 磁芯存储器 半导体存储器 半导体存储器
外存储器 穿孔卡片，纸带 磁带 磁带，磁盘 磁盘、光盘等大容量存储器
处理速度 (指令数/秒) 几千条 几百万条 几千万条 数亿条以上
1 . 2 研制中的第五代计算机
1、创建非冯 诺伊曼式语言
LISP, PROLOG
2、创建以人脑神经系统处理信息的原理为基础的非冯 诺伊曼式的计算机模型
生物计算机
光子计算机
量子计算机
1 . 3 三金工程
“金桥”工程又称经济信息通信网工程，它是建设国家
公用经济信息通信网、实现国民经济信息化的基础设
施。这项工程的建设，对于提高我国宏观经济调控和
决策水平以及信息资源共享、推动信息服务业的发
展，都具有十分重要的意义。
“金关”工程又称为海关联网工程，其目标是推广电子
数据交换（EDI）技术，以实现货物通关自动化、国
际贸易无纸化。
“金卡”工程又称电子货币工程，它是借以实现金融电子化和商业流通现代化的必要手段。
1 . 4 计算机病毒
计算机病毒是一种功能特殊的计算机程序，它一旦运行，便取得系统控制权,同时把自己复制到媒体中去。
计算机病毒的特征：
1、能够自身复制到其他程序中。
2、不独立以文件形式存在，仅附加在别的程序上。当调用该程序运行时，此病毒则首先运行。
2 . 1 冯 诺伊曼型计算机
输 入 设 备
运算器
存储器
控制器
输 出 设 备
输入
输出
第一台具有存储功能的计算机EDVAC逻辑功能图
2 . 2 计算机硬件系统
计算机硬件(computer hardware)主要由输入设备、输出设备、存储器、运算器、控制器五大部分组成
1) 输入设备 若要计算机按我们的要求进行工作，计算机必须接受外部的信息。使计算机从外部获得信息的设备，称为输入设备(input device)。 常用的输入设备包括键盘、光笔、鼠标器、扫描仪、话筒等，通过它们可以输入文字、图像、声音等不同的信息。 输入设备种类很多，近几年来出现了触摸屏、手写汉字输入设备、自然语言输入设备、数码照相机等。
2) 输出设备 计算机把信息处理的结果以人们能够识别的形式表示出来的设备，称为输出设备(output device)。例如，显示器、打印机、绘图仪等。
3) 存储器 计算机在处理信息的过程中，许多信息被存放在存储器(memory)中。存储器又分为内存储器和外存储器两种。
4) 运算器 运算器 (arithmetic unit) 是计算机实施算术运算和逻辑判断的主要部件。它能按照计算机程序的要求，在控制器的控制下，进行加、减、乘、除等基本运算和进行判别数的符号，比较数的大小等逻辑运算。
5) 控制器 控制器(controller)是指挥、控制计算机运行的中心。它从存储器中取出信息并进行分析，然后根据指令向计算机各个部分发出各种控制信息，使计算机按照要求自动、协调地完成任务。一般将运算器和控制器合称为中央处理器（简称CPU）。
2.3 计算机指令系统
机器指令是要计算机执行某种操作的命令，且由计算机直接识别执行。所有指令的集合称为计算机的指令系统。
一条指令通常有操作码和地址码两部分组成。
操作码 地址码
指令按功能可分为操作类命令和控制转移类命令。
操作码指明计算机执行的某种操作的性质和功能；地址码指出被操作的数据（简称操作数）存放在何处，即指明操作数地址，有的指令格式允许地址码部分就是操作数本身。
2 . 6 软件系统
软件一般分为系统软件和应用软件。
系统软件是生成、准备和执行其他程序所需要的一组程序。它通常负责管理、控制和维护计算机的各种软硬件资源，并为用户提供友好的操作界面。
应用软件是专业人员为各种应用目的而编写的程序。一般不能独立地在计算机上运行，必须要有系统软件的支持。
2.4 机器数
在计算机中，数是存放在由寄存单元组成的寄存器中，二进制数码1和0是由寄存器单元的两种不同的状态来表示的。
为了运算的方便，在计算机中常用三种表示法：
原码
补码
反码
原码表示法
也称为 符号-幅值 表示法
符号位用0-----正数 符号位用1-----负数
其余位表示数的大小
例:X= +1011 [X]原=01011
X= -1011 [X]原=11011
缺点：
运算（加、减法）低效
0有两个表示
+0：00000000 –0：10000000
补码表示法
[X]补=X， 当 X>=0;
[X]补=2(n+1)+X， 当-2n<=X<0 mod( 2(n+1) );
对于定点小数：n=0
定点整数：n>=1
例如：X=+100101 [X]补=0 100101
X=–100101 [X]补=1 011011
特点:1.补码的和等于和的补码,符号位和数值位一样参加运算,不必单独处理,即 [X]补+[Y]补=[X+Y]补
2.补码相减: [X]补-[Y]补=[X]补+[-Y]补
[Y]补→[-Y]补: 符号位连同数值位一起取反加1
反码表示法
当X>=0时，[X]反=X 当X<=0时，符号位为1，其余各位取反。
特点: 1.反码的和等于和的反码
2.有二个零 +0=00……0
-0=11……1
3.当最高位有进位而丢掉进位(即2)时,要在最低位加1(循环进位)
原码,反码和补码之间的转换
[X]反
符号位不变↑数值位 不变(符号位为0)
变反(符号位为1)
+,–←→0,1 ↓
X真值 ←―→ [X]原
数值位不变 ↑ 数值位不变(符号位为0)
变反加1(符号位为1)
符号位不变↓
[X]补
当X为正数，[X]反=[X]原=[X]补=X，
当X为负数时，[X]补=[X]反+1，[[X]补]=[X]原
2 . 5 ASCII码
ASCII码是美国信息交换标准代码的缩略语。是目前国际上最为流行的字符信息编码方案。它包括数字0~9、大小写字母和专用符号等95种可打印字符，还有33种控制字符。
一个字符ASCII码通常占一个字节，用七位二进制编码组成，ASCII码最多可表示128个不同的符号。字节的最高位被很多系统用做校验码，以便提高字符信息传输的可靠性。
2 . 12 汉字信息编码
汉字信息也采用二进制的数字化信息编码。目前的汉字编码方案有二字节、三字节甚至四字节的。
国标码（国家标准信息交换用汉字编码），是二字节码，用七位二进制数编码表示一个汉字。目前国标码收入6763个汉字，其中一级汉字（最常用）3755个，二级汉字3008个，另外还包括682个西文字符、图符。
2 . 6 二进制
采用二进制，优点：
（1）易于物理实现
（2）二进制运算简单
（3）机器可靠性高
（4）通用性强
乘法 除法 整数转换 小数转换
0+0=0 0+1=1
1+0=1 1+1=10
0*0=0 0*1=0
1*0=0 1*1=1
3 . 2 CD-ROM
光驱的技术指标 (1) 数据传输率(Data Transfer Rate),即大家常说的倍速，它是衡量光驱性能的最基本指标。单倍速光驱就是指每秒可从光驱存取150KB数据的光驱。现在年青一代的40或48倍速光驱每秒钟能读取6000KB和7200KB的数据。 (2) 平均寻道时间(Average Access Time),平均寻道时间是指激光头（光驱中用于读取数据的一个装置）从原来位置移到新位置并开始读取数据所花费的平均时间，显然，平均寻道时间越短，光驱的性能就越好。 (3) CPU占用时间(CPU Loading)，CPU占用时间是指光驱在维持一定的转速和数据传输率时所占用CPU的时间，它也是衡量光驱性能好坏的一个重要指标。CPU占用时间越少，其整体性能就越好。 (4) 数据缓冲区(Buffer)，数据缓冲区是光驱内部的存储区。它能减少读盘次数，提高数据传输率。现在大多数光驱的缓冲区为128K或256K。
3 . 3 显示存储空间
显示存储空间
=水平分辨率×垂直分辨率×色彩数目
例如，若采用640 ×480，16色显示模式，只需要150KB的存储空间。但是，如果想在1280 ×1024，16M色的显示模式下运行，4MB的显示存储空间是不可能运行的。
3 .4 压缩标准
目前，国际上的压缩技术标准有 JPEG，MPEG 和P ×4。
JPEG适合于连续色调、多级灰度、彩色或单色静止图象数据压缩的国际标准。可获得10：1到80：1的压缩比。
MPEG包括MPEG视频、 MPEG音频和MPEG系统三部分，处理活动影象中的视频压缩、音频压缩，以及多种压缩后数据流的复合和同步问题。可获得50：1到00：1的压缩比。
P ×4目标是针对可视电话和电视会议的。适应各种通道容量的传输。
4 . 1 广域网和局域网
1、广域网WAN（Wide Area Network）
是跨地域性的网络系统，大多数WAN都是网络互连而成的，如著名的Internet网络。
2、局域网LAN（Local Area Network）
一般由一个部门或公司组建，地理范围仅在建筑楼内或单位内部。
3、城域网：可以看成是广域网的一种。
4 . 2 计算机网络拓扑结构
网络中各个站点相互连接的方法和形式称之为网络拓扑。把向工作站、服务器等网络单元抽象成为“点”，把网络中的电缆等通信媒体抽象为“线”，从而抽象出了络系统的具体结构，即为逻辑结构。网络拓扑结构有：
计算机网络拓扑结构
4.3 网络协议
计算机通信协议指双方在通信中所应共同遵守的约定。计算机通信协议精确地定了计算机在彼此通信时的所有细节。它规定每台计算机发送每条信息的格式和含义，规定哪些情况下应发送那些特殊的信息，以及接受方的计算机所应作出什么反映等等。
OSI七层协议
主机A 主机B
1 应用层 应用层
2 表示层 表示层
3 会话层 会话层
4 运输层 运输层
5 网络层 网络层
6 数据链路层 数据链路层
7 物理层 物理层
应用层协议
表示层协议
会话层协议
运输层协议
网络层协议
链路层协议
物理层协议
4.4 IP地址
Internet中的每台主机都被分配一个唯一的32位地址，即IP地址。该地址由网络号和主机号两部分组成，其中网络号表示一个网络，而主机号表示这个网络中的一台计算机。
IP地址由4个十进制数字字段组成, 字段之间用点分开, 4个字段中的每个数字在0~255之间，如210.30.240.11。。
IP地址类型
IP地址按网络规模的大小主要可分成三类: A类地址、B类地址、C类地址。A类的第一个字段的值在1～126之间，一般用于大型网络；B类的第一个字段的值在128 ～ 191之间，一般用于中型网络或网络管理器，如路由器等；C类的第一个字段在值在191 ～ 233之间，一般用于小型网络。
网络地址数 网络主机数 主机总数
A类 126 16,38 7,064 2,064,770,064
B类 16,256 6 4,516 1,048,872,096
C类 2,064,512 254 524,386,048
域名
用IP地址标识主机既没有规律，又很难记忆，用户很难用数字表示的IP地址与计算机的情况联系起来，给访问Internet带来了很大的不便如果采用域名系统，就可以很好地解决这些问题。
域名系统是由TCP/IP提供的一种服务，可以将域名翻译成相应的IP地址。域名系统采用层次结构，按地理域或组织域进行分层，各层间用圆点“.” 隔开。在主机的域名表示中，从左向右，域名依次从小到大，例如在www.easthuman.中，最高域名为cn，次高域名为com，最后一个域名为easthuman。
数学相关题目
1．（第八届）在书架上放有编号为1，2，...n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时,原来位置为1 2 3,放回去时只能为： 3 1 2 或 2 3 1 这两种。 问题：求当n=5时满足以上条件的放法共有多少种 (不用列出每种放法)
2.(第九届) 某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程为C1，C2，C3，C4，C5，C6，S(Ci)为学习Ci 的学生集合。已知S(Ci)∩S(C6)≠ф，i=1，2，...，5，S(Ci)∩S(Ci+1)≠ф，i=1，2，3，4，S(C5)∩S(C1)≠ф，问至少安排_____天才能考完这6门课程。
题目
3．(第七届)平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形
4．（第十届）已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案： 。
从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.
2.组合的定义:
从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.
3.排列数公式:
4.组合数公式:
1.排列的定义:
排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题.
例1 学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？
解 先排学生共有 种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有 种选法.根据乘法原理,共有的不同坐法为 种.
结论1 插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.
分析 此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待.所涉及问题是排列问题.
解 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法.
例2 5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法
结论2 捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.
分析 此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题.
解 把所有的硬币全部取出来,将得到 0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法.
例3 袋中有5分硬币23个,1角硬币10个,如果从袋中取出2元钱,有多少种取法
结论3 剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法.
分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.
例4 学校安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序
解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有 种.
结论4 对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求.
分析 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性.
例5 某个班级共有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种
解 43人中任抽5人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有1人在内的抽法有 种.
结论5 排异法:有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除.
分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.
数据结构相关题目
1.(第六届)已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
2．(第七届)已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA，则该二叉树的先序遍历的顺序为：_________。
3．（第九届）无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_______个顶点。
扩展
二叉树
二叉树由结点的有限集合构成，这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别成为这个根的左子树和右子树的二叉树（它们也是结点的集合）组成。
二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
二叉树的五种形态
（1） （2） （3） （4） （5）
满二叉树
如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称为满二叉树。
在满二叉树里，树叶的个数等于分支结点个数加一。
完全二叉树
如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层左边的若干位置，则此二叉树称作完全二叉树。
二叉树的遍历
先序：根-左子树-右子树 (abcd)
中序：左子树-根-右子树 (badc)
后序：左子树-右子树-根 (bdca)
a
b
c
d
图
习惯上，常用G=(V,E)代表一个图，图中的结点又称为顶点，V是结点的有限集合，结点的偶对称为边，E是边的集合。
任意一个具有n个结点的无向图，其边数小于等于n*(n-1)/2;我们把边数恰好等于n*(n-1)/2的n个结点的无向图称为完全图。
在一个n个结点的有向图中，最大边数为n*(n-1)。
一个结点的度就是与该结点相关联的边的数目。
1．(第七届)一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点 A)2h-1 B)2h—1 C)2h十1 D)h十1
2．(第七届)无向图G＝(V，E)，其中V＝{a，b，c，d，e，f } E＝{(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}， 对该图进行深度优先遍历，得到的顶点序列正确的是( ) A)a，b，e，c，d，f B)a，c，f，e，b，d C)a，e，b，c，f，d D)a，b，e，d，f，c
3．（第八届）按照二叉树的定义，具有3个结点的二叉树有( )种。 A)3 B)4 C)5 D)6
4．（第八届）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。 A)1／2 B)1 C)2 D)4
5.（第九届） 假设我们用d=(a1,a2,...,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d 值合理（ ）。 A）{5，4，4，3，1} B）{4，2，2，1，1} C）{3，3，3，2，2} D）{5，4，3，2，1} E）{2，2，2，2，2}
6．（第十届）满二叉树的叶结点个数为N，它的结点总数为 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1
同课章节目录