当前位置:首页 >> 学科竞赛 >>

信息学奥赛初赛知识复习


信息学奥林匹克 分区联赛的基础知识

初赛试题结构
第一部分 第二部分 第三部分 第四部分 基础知识 问题求解 阅读程序 完善程序

第一部分 基础知识
一、计算机的产生与发展 二、计算机的系统组成 三、计算机的特点及应用 四、计算机中有关数及编码知识 五、计算机网络基础知识 六、计算机信息安全知识

/> 一、 计算机的产生与发展
计算机的产生是20世纪最重要的科学技术大事件之一 。世界上的第一台计算机(ENIAC)于1946年诞生在美 国宾夕法尼亚大学,到目前为止,计算机的发展大致经历 了四代: ① 第一代电子管计算机,始于1946年,结构上以CPU为 中心,使用计算机语言,速度慢,存储量小,主要用于数 值计算; ② 第二代晶体管计算机,始于1958年,结构上以存储器 为中心,使用高级语言,应用范围扩大到数据处理和工业 控制; ③ 第三代中小规模集成电路计算机,始于1964年,结构 上仍以存储器为中心,增加了多种外部设备,软件得到了 一定的发展,文字图象处理功能加强; ④ 第四代大规模和超大规模集成电路计算机,始于1971 年,应用更广泛,很多核心部件可集成在一个或多个芯片 上,从而出现了微型计算机。

我国的计算机发展情况
1. 我国从1956年开始计算机的科研和教学工作; 2. 1960年我国第一台自行设计的通用电子计算机 107机诞生; 3. 1964年我国研制成大型通用电子计算机119机; 4. 1983年每秒运行一亿次的银河巨型计算机在国防 科技大学诞生; 5. 1992年研制成功每秒运行10亿次的“银河Ⅱ‖巨 型计算机; 6. 1997年又研制成功每秒运行130亿次的“银河Ⅲ‖ 巨型计算机; 7. · 我国较有名的微型计算机品牌有:“联想”、“ 长城”、“方正”等;

1、国产银河型数字式电子计算机是属于下列 哪种类型计算机( ) A.微型 B.小型 C.中型 D.巨型 2、最早的计算机的用途是用于( ) A.科学计算 B.自动控制 C.辅助设计 D.系统仿真 3、微型计算机的问世是由于( C ) 的出现。 A.中小规模集成电路 B.晶体管电路 C.超大规模集成电路 D.电子管电路

4、在下列关于图灵奖的说法中,不正确的是( )。 A. 图灵奖是美国计算机协会于1966年设立的,专门奖励那 些对计算机事业作出重要贡献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止,还没有华裔计算机科学家获此殊荣。 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰· 图灵 5、关于图灵机下面的说法哪个是正确的: A.图灵机是世界上最早的电子计算机。 B.由于大量使用磁带操作,图灵机运行速度很慢。 C.图灵机是英国人图灵发明的,在二战中为破译德军的密码 发挥了重要作用。 D.图灵机只是一个理论上的计算模型。

5、全国信息学奥林匹克的官方网站为参与信 息学竞赛的老师同学们提供相关的信息和 资源,请问全国信息学奥林匹克官方网站 的网址是: A) http://www.noi.com/ B) http://www.noi.org/ C) http://www.noi.cn/ D) http://www.xinxixue.com/

二、计算机的系统组成
计算机系统由硬件和软件两部分组成。 (1) 计算机的主要硬件 :输入设备、 输出设备、 中央处理器(CPU):包括控制器和运算器运算 器、存储器(内存和外存)。 (2)计算机的软件主要分为系统软件和应用软件两 类。 (3)总线是一组为系统部件之间数据传送的公用信 号线,一般按信号类型将总线分为三组,其中AB (Address Bus)为地址总线;DB(Data Bus)为 数据总线;CB(Control Bus)控制总线。

二、计算机的系统组成
微型机的主要技术指标: 1.字长 2.运算速度 3.时钟频率(主频) 4.存取速度 5.存储容量

微型机的主要技术指标:
1.字长 字长是指计算机能直接处理的二进制信息的 位数。字长是由CPU内部的寄存器、加法器和数 据总线的位数决定的。字长标志着计算机处理信 息的精度。字长越长,精度越高,速度越快,但 价格也越高。当前普通微机字长有16位,32位, 高档微机的字长是64位。

微型机的主要技术指标:
2.运算速度 运算速度是指计算机每秒钟能执行的指 令条数。单位是次每秒或百万次每秒。百 万次每秒(1秒内可以执行100万条指令) 又称为MIPS。

微型机的主要技术指标:
3.时钟频率(主频) 时钟频率是指CPU在单位时间(秒)内发出 的脉冲数。它在很大程度上决定了计算机的运算 速度。时钟频率越快,计算机的运算速度也越快 。主频的单位是兆赫兹(MHz)。如80486为25 ~100 MHz,80586为75~266 MHz。

微型机的主要技术指标:
4.存取速度 存储器完成一次读/写操作所需的时 间称为存储器的存取时间或访问时间。存 储器连续进行读/写操作所允许的最短时 间间隔,称为存取周期。存取周期越短, 则存取速度越快,它是反映存储器性能的 一个重要参数。通常,存取速度的快慢决 定了运算速度的快慢。半导体存储器的存 取周期约在几十到几百微秒之间。

微型机的主要技术指标:
5.存储容量 ⑴内存容量。指内存储器能够存储信息的 总字节数。内存容量的大小反映了计算机 存储程序和处理数据能力的大小,容量越 大,运行速度越快。 ⑵外存容量。指外存储器所能容纳的总字 节数。

1、中央处理器(CPU)能访问的最大存储器容 量取决于( A ) 。 A)地址总线 B)数据总线 C) 控制总线 D) 实际内存容量 2、微型计算机中,( C ) 的存取速度最快。 A)高速缓存 B)外存储器 C) 寄存器 D) 内存储器 3、计算机硬件系统中,cache是( D)存储器 A)只读 B)可编程只读 C)可擦除可编程只读 D)高速缓冲

4、若我们说一个微机的CPU是用的PII300, 此处的300确切指的是(A )。 A)CPU的主时钟频率 B)CPU产品的系列号 C)每秒执行300百万条指令 D)此种CPU允许最大内存容量 5、计算机主机是由CPU与(D)构成的。 A. 控制器 B. 输入、输出设备 C. 运算器 D.内存储器

6、计算机系统总线上传送的信号有( B )。 A.地址信号与控制信号 B. 数据信号、控制信号与地址信号 C.控制信号与数据信号 D. 数据信号与地址信号 7、不同类型的存储器组成了多层次结构的存储器 体系,按存取速度从快到慢的排列是(C)。 A.快存/辅存/主存 B. 外存/主存/辅存 C. 快存/主存/辅存 D. 主存/辅存/外存 8、微机内存储器的地址是按(C)编址的。 A.二进制位 B. 字长 C.字节 D. 微处理器的型号

三、计算机的特点及应用
1、计算机特点 运算速度快,运算精度高,具有记忆能力,具 有逻辑判断能力,具有自动控制能力; 2、计算机应用 1)数值计算:弹道轨迹、天气预报、高能物理等 2)信息管理:企业管理、物资管理、电算化等 3)过程控制:工业自动化控制,卫星飞行方向控 制。 4)辅助工程:CAD、CAM、CAT、CAI 等

四、计算机中有关数和编码知识
1.计算机是智能化的电器设备 计算机就其本身来说是一个电器设备,为了能 够快速存储、处理、传递信息,其内部采用了 大量的电子元件,在这些电子元件中,电路的通 和断、电压高低,这两种状态最容易实现, 也最稳定、也最容易实现对电路本身的控制。 我们将计算机所能表示这样的状态,用0,1来 表示、即用二进制数表示计算机内部的所有运算 和操作。

四、计算机中有关数和编码知识
2.二进制数的运算法则 二进制数运算非常简单,计算机很容易实现,其 主要法则是: 0+0=0 0+1=1 1+0=1 1+1=0 0*0=0 0*1=0 1*0=0 1*1=1 由于运算简单,电器元件容易实现,所以计算机 内部都用二进制编码进行数据的传送和计算。

四、计算机中有关数和编码知识
3、十进制与二进制、八进制、十六进制数之 间的相互转换 例如:(2008)10分别转化为二进制、八进制、 十六进制。





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、下列哪些计算机网络不是按覆盖地域划分的 ( d ) 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 输出: —10—45—120—2

例二
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<n-m+1 then goto 10; 输入 i:=0; asabcdffdin goto 30; fdi end 输出_________ else if k<m then begin j:=j+1;k:=k+1;goto 20; end; 30:writeln(i); End.

例三
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. 输出:_____________

第四部分 完善程序
? 变量方面的填空(定义类型、设定初值、 变量赋值等) ? 循环方面的填空(定义变量、设定循环的 初值和终值、在循环中如何引用) ? 分支转移方面的填空(定义布尔表达式、 确定程序的走向) ? 主程序和子程序关系方面的填空(值参、 变参、调用格式) ? 输入输出方面的填空

不含子程序
例一、求元素之和 最大的子方阵: 在m4*n5的正整 数数字方阵中, 找出一个p3*q3的 子阵,使得其元 素之和最大。
3 11 5 10 2 8 1 21 3 7 5 4 7 6 8 12 22 9 2 9 3

21 6 8 12

10 3 2 7

程序清单
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<n then p___(4)____; End; begin readln(n);first:=true;write(n:5,‘=?);p(n);writeln; readln end.

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 冯?诺伊曼型计算机
运算器CPU 输入 输 入 设 备 存储器 控制器cpu 输 出 设 备 输出

第一台具有存储功能的计算机EDVAC逻辑功能图

2 . 2 计算机硬件系统

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 ? 表示为-127----+127

补码表示法
[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 3表示范围:-128-------+127

反码表示法
当X>=0时,[X]反=X 当X<=0时,符号位为1,其余各 位取反。
? 特点: 1.反码的和等于和的反码 2.有二个零 +0=00……0 -0=11……1 3.当最高位有进位而丢掉进位(即2)时,要 在最低位加1(循环进位) 表示范围:-127------+127

原码,反码和补码之间的转换
[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 汉字信息编码
? 3、汉字交换码 ? (1)区位码:GB2312-80"信息交换用汉字编码字符集", 组成一个94*94的矩阵。每一行称为一个"区",每一列称为 一个"位"。一个汉字的区号和位号合在一起构成"区位码" ? (2)汉字交换码(国标码,GB2312-80 ):国标码收入 6763个汉字,其中一级汉字(最常用)3755个(按拼音排 序),二级汉字3008个(按部首排序),另外还包括682个西文 字符、图符。区位码(十进制)的两个字节分别转换为十 六进制后加20H 转换成国际码。 ? 4、汉字机内码:是计算机系统中对汉字的一种运行代码, 系统内部的存储、传输都是对机内码进行的。它也和汉字 存在着一一对应的关系。机内码也占两个字节,且最高位 为1。同一个汉字,在同一种汉字操作系统中,内码是相同 的。 ? 汉字机内码是汉字交换码两个字节的最高位分别加"1",即 汉字交换码的两个字节分别加80H;或区位码(十进制)的 两个字节分别转换为十六进制后加A0H。

? 由于GB2312-80是80年代制定的标准,在实际应用时常 常感到不够,所以,建议处理文字信息的产品采用新颁布 的GB18030信息交换用汉字编码字符集,这个标准繁、 简字均处同一平台,可解决两岸三地间GB码与BIG5码间 的字码转换不便的问题。
? 字形存储码是指供计算机输出汉字(显示或打印)用的二 进制信息,也称字模。通常,采用的是数字化点阵字模, 有16×16,24×24,64×64等,每一个点在存储器中用 一个二进制位(bit)存储。例如,在16×16的点阵中, 需8×32 bit 的存储空间,每8 bit为1字节,所以,需32字 节的存储空间。在相同点阵中,不管其笔划繁简,每个汉 字所占的字节数相等。

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

整数转换

小数转换

? ? ? ? ? ? ? ? ?

数的定点表示和浮点表示 (1) 定点小数格式 任何一个M位的小数可以表示成: N=Ns . N-1N-2…N-m (其中Ns 是符号位,其值表示的范围|N|<=1-2-m) (2) 定点整数格式 任何一个N位带符号的整数都可表示为: N=Ns Nn-1Nn-2…N0 (其中Ns 是符号位,其值表示的范围|N|<=2n-1) (3) 数的浮点表示 浮点数是指小数点在数据中的位置可以左右移动的数。一个数N要用浮点表示 可以写成:N=M?RE 其中M表示浮点数的尾数,E表示浮点数的指数或称为阶 码,R指的是在这个指数下的基数。浮点数通常表示成如下格式:

Ms

E

M

? 1位 m位 n位 ? M:浮点数的尾数,用定点小数表示,小数点在尾数最高位之前,是 默认的。尾数用于表示浮点数的有效位,其位数N的大小反映了此浮 点数的精度。 ? E:浮点数的阶码,用定点整数表示。 ? Ms:浮点数的符号位,也就是尾数的符号位,一般放在整个浮点数的 最高位

信息在计算中的存储地址
? 所有的存储单元都按顺序排列,计算机中以一个字节为单位处 理,所以计算机对每个存储单元进行了编号,这种编号称为单 元地址。通过地址编号寻找在存储器中的数据单元称为"寻址1、 地址编号:用二进制数编码,存储器的总容量决定了地址的范 围,也决定了地址编号的二进制数位数。 ? 如存储器的总容量为64MB,那么它的地址编码为0 ~ 64×220-1;对应的二进制数是00 0000 0000 0000 0000 0000 0000~11 1111 1111 1111 1111 1111 1111;对应的十六进制 数是0000000~3FFFFFF;需要用26位二进制来表示,也就是 需要26根地址线。 ? 2、地址和容量的计算 ? (1)由地址线,求寻址空间。 ? 若地址线有32根,则它的寻址空间为 232B = 222 KB = 212 MB = 4GB

? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ?

(2)由起始地址和末地址,求存储空间。 若编号为4000H ~ 4FFFH的地址中,包含的单元数的计算: 方法一:用十六进制计算。 4FFFH-4000H +1=FFFH+1 = 1000H = 1 ′ 163 = 4096 =4KB 方法二:转换成十进制计算。 4FFFH-4000H +1=20479-16384+1=4096=4KB (3)由存储容量和起始地址,求末地址。 若存储器的容量32KB,地址起始编号为0000H, 末地址的计算: 方法一:用十六进制计算。 0000H+32KB-1H =0000H+32 ′1024-1H =0000H+8000H-1H= 7FFFH 方法二:转换成十进制计算。 0+32KB-1= 0+32768-1 = 32767=7FFFH 方法三:转换成二进制计算。 0000 H +32KB-1 H = 0000 H +32′ 210-1 H= 0000 H +215-1 H =0000 0000 0000 0000 B+ 1000 0000 0000 0000 B -0000 0000 0000 0001 B =0111 1111 1111 1111 B=7FFFH

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包括MPEGeg:mp4视频、 MPEGeg:MP3音 频和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七层协议
1 2 3

主机A 应用层协议 应用层
表示层 会话层 表示层协议 会话层协议 运输层协议 网络层协议 链路层协议 物理层协议

主机B 应用层
表示层 会话层

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.com.cn中,最高域 名 为 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‖开头写出你的安排方 案: 。

1.排列的定义:从n个不同元素中,任取m个元素,按照一定的 顺序排成一列,叫做从n个不同元素中取出m 个元素的一个排列. 2.组合的定义:从n个不同元素中,任取m个元素,并成一组, 叫做从n个不同元素中取出m个元素的一个 组合. 3.排列数公式:

4.组合数公式: Cn m
?

P n ( n ? 1)( n ? 2) ? ( n ? m ? 1) ? nm ? m! P m
m

n! m! ( n ? m )!

排列与组合的区别与联系:与顺序有关的为排列问题,与顺序 无关的为组合问题.

例1 学校师生合影,共8个学生,4个老师,要求老师在 学生中间,且老师互不相邻,共有多少种不同的合影方 式? 分析 此题涉及到的是不相邻问题,并且是对老师有特殊 的要求,因此老师是特殊元素,在解决时就要特殊对待. 所涉及问题是排列问题. P 8 种排法,然后把老师插入学生 解 先排学生共有 8 之间的空档,共有7个空档可插,选其中的4个空档,共 有 P 4 种选法.根据乘法原理,共有的不同坐法为 P88 P74 7 种. 结论1 插入法:对于某两个元素或者几个元素要求不 相邻的问题,可以用插入法.即先排好没有限制条件的 元素,然后将有限制条件的元素按要求插入排好元素 的空档之中即可.

例2 5个男生3个女生排成一排,3个女生要排在一起, 有多少种不同的排法? 分析 此题涉及到的是排队问题,对于女生有特殊的限 制,因此,女生是特殊元素,并且要求她们要相邻,因此 可以将她们看成是一个元素来解决问题. 解 因为女生要排在一起,所以可以将3个女生看成是 一个人,与5个男生作全排列,有 P66 种排法,其中女生内 部也有P33 种排法,根据乘法原理,共有P66 P33 种不同的排 法. 结论2 捆绑法:要求某几个元素必须排在一起的问题, 可以用捆绑法来解决问题.即将需要相邻的元素合并 为一个元素,再与其它元素一起作排列,同时要注意合 并元素内部也可以作排列.

例3 袋中有5分硬币23个,1角硬币10个,如果从袋中 取出2元钱,有多少种取法? 分析 此题是一个组合问题,若是直接考虑取钱的问题 的话,情况比较多,也显得比较凌乱,难以理出头绪来. 但是如果根据组合数性质考虑剩余问题的话,就会很 容易解决问题. 解 把所有的硬币全部取出来,将得到 0.05×23+0.10×10=2.15元,所以比2元多0.15元,所 以剩下0.15元即剩下3个5分或1个5分与1个1角,所以 3 1 1 C23 ? C23 ? C10 种取法. 共有 结论3 剩余法:在组合问题中,有多少取法,就有多少 种剩法,他们是一一对应的,因此,当求取法困难时,可 转化为求剩法.

例4 学校安排考试科目9门,语文要在数学之前考,有 多少种不同的安排顺序? 分析 对于任何一个排列问题,就其中的两个元素来讲 的话,他们的排列顺序只有两种情况,并且在整个排列 中,他们出现的机会是均等的,因此要求其中的某一种 情况,能够得到全体,那么问题就可以解决了.并且也避 免了问题的复杂性. P99 种,“语文安排 解 不加任何限制条件,整个排法有 在数学之前考”,与“数学安排在语文之前考”的排法 1 9 P 是相等的,所以语文安排在数学之前考的排法共有 9 2 种. 结论4 对等法:在有些题目中,它的限制条件的肯定与 否定是对等的,各占全体的二分之一.在求解中只要求 出全体,就可以得到所求.

例5 某个班级共有43位同学,从中任抽5人,正、副 班长、团支部书记至少有一人在内的抽法有多少种? 分析 此题若是直接去考虑的话,就要将问题分成好几 种情况,这样解题的话,容易造成各种情况遗漏或者重 复的情况.而如果从此问题相反的方面去考虑的话,不 但容易理解,而且在计算中也是非常的简便.这样就可 以简化计算过程. 5 C43 种,正副班长,团支部 解 43人中任抽5人的方法有 5 C40 种,所以正副班长,团支部书 书记都不在内的抽法有 5 5 C43 ? C40 种. 记至少有1人在内的抽法有 结论5 排异法:有些问题,正面直接考虑比较复杂,而它 的反面往往比较简捷,可以先求出它的反面,再从整体中 排除.

?扩展

数据结构相关题目
? 1.(第六届)已知,按中序遍历二叉树的结果为: abc 问:有多少种不同形态的二叉树可以得到这一 遍历结果,并画出这些二叉树。 ? 2.(第七届)已知一棵二叉树的结点名为大写英 文字母,其中序与后序遍历的顺序分别为: CBGEAFHDIJ与CGEBHFJIDA,则该二叉树 的先序遍历的顺序为:_________。 ? 3.(第九届)无向图G有16条边,有3个4度 顶点、4个3度顶点,其余顶点的度均小于3, 则G至少_______个顶点。

二叉树
二叉树由结点的有限集合构成,这个有 限集合或者为空集,或者由一个根结点及两 棵不相交的分别成为这个根的左子树和右子 树的二叉树(它们也是结点的集合)组成。 二叉树的结点的子树要区分左子树和右 子树,即使在结点只有一棵子树的情况下也 要明确指出该子树是左子树还是右子树。

二叉树的五种形态

(1)

(2)

(3)

(4)

(5)

满二叉树
? 如果一棵二叉树的任何结点,或者是树叶, 或者恰有两棵非空子树,则此二叉树称为 满二叉树。 ? 在满二叉树里,树叶的个数等于分支结点 个数加一。

完全二叉树
? 如果一棵二叉树最多只有最下面的两层结 点度数可以小于2,并且最下面一层的结点 都集中在该层左边的若干位置,则此二叉 树称作完全二叉树。

二叉树的遍历
? 先序:根-左子树-右子树 ? 中序:左子树-根-右子树 ? 后序:左子树-右子树-根
a

(abcd) (badc) (bdca)

b

c

d


? 习惯上,常用G=(V,E)代表一个图,图中的 结点又称为顶点,V是结点的有限集合,结 点的偶对称为边,E是边的集合。 ? 任意一个具有n个结点的无向图,其边数小 于等于n*(n-1)/2;我们把边数恰好等于n*(n1)/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


相关文章:
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 全新...
信息学奥赛NOIP初赛复习知识点+基本函数
信息学奥赛 NOIP 初赛复习知识点+基本函数 1 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个全新的 " 存储程序...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A:被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯 ·诺依曼 于 1945 年发表了一个 全新的...
信息学奥赛初赛复习题
信息学奥赛初赛复习题_学科竞赛_高中教育_教育专区。内部资料 注意保密 信息学...补码表示都有两种 四、网络知识 1、调制解调器又称为 Modem,可用于连结计算机...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: :被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 ...
信息学奥赛初赛复习2012-16K
信息学奥赛初赛复习2012-16K_学科竞赛_小学教育_教育专区。内部资料 注意保密 信息学奥赛初赛复习 金陵中学河西分校 2012 年 6 月 第 0 页 第一部分:选择题一、...
信息学奥赛计算机基础知识复习材料
信息学奥赛计算机基础知识复习材料第一章 计算机的概念、诞生与发展、应用、分类 一、计算机的概念:是一种能迅速而高效的自动完成信息处理的电子设备,它能按照程序对...
2015信息学奥赛初赛 普级组
2015信息学奥赛初赛 普级组_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2015信息学奥赛初赛 普级组_学科竞赛_初中教育_教育专区。 ...
全国青少年信息学奥林匹克联赛初赛讲义
12:04:41| 分类: 牛妈的教学工作 | 标签:奥赛讲义 全国青少年信息学奥林匹克联赛初赛复习讲义 初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其...
更多相关标签: