信息学奥林匹克竞赛培训资料 图论基础

信息学奥林匹克竞赛培训资料图论基础图论基础

一、3种数据模型

线性表(数组、链表):1:1

树(普通树、二叉树、森林):1:n，线性链表可以看成是树的特例(单链)

，树也可以看成是图的特例图(无向图、有向图):m:n

二、图的基本概念

1、图=(顶点集，边集)，顶点集必须非空，关键是把什么抽象成顶点，什么抽象成边,

2、图的分类:无向图和有向图，区分在于边是否可逆,

3、加权图(又称网或网络):权的含义,不加权的图也可以认为权是1。

4、阶和度:一个图的阶是指图中顶点的个数。

如果顶点A、B之间有一条边相连，则称顶点A和B是关联的;

顶点的度是指与该顶点相关联的边的数目，奇点和偶点,

对于有向图存在入度与出度之分;

定理:无向图中所有顶点的度之和等于边数的2倍;

有向图中所有顶点的入度之和等于所有顶点的出度之和;

任意一个无向图一定有偶数个(或0个)奇点; 5、完全图:一个n阶的完全无向图含有n*(n-1)/2条边;

一个n阶的完全有向图含有n*(n-1)条边;

稠密图:当一个图的边数接近完全图时;

稀疏图:当一个图的边数远远少于完全图时;

在具体使用时，要选用不同的存储结构;

6、子图:从一个图中取出若干顶点、若干边构成的一个新的图;

7、路径:对于图G=(V，E)，对于顶点a,b，如果存在一些顶点序列

x=a,x,……,x=b(k>1)，且12k(x,x)?E，i=1,2…k-1，则称顶点序列x,x,……,x为顶点

a到顶点b的一条路径，而路径ii+112k

上边的数目(即k-1)称为该路径的长度。并称顶点集合{x,x,……,x}为一个连通

集。 12k8、简单路径:如果一条路径上的顶点除了起点和终点可以相同外，其它顶

点均不相同，则称此路径为一条简单路径;起点和终点相同的简单路径称为回路(或环)。

下左图1—2—3是一条简单路径，长度为2，而1—3—4—1—3就不是简单路

径;下右图1-2-1

为一个回路。

9、有根图:在一个图中，如果从顶点U到顶点V有路径，则称U和V是连通的;

在一个图中，若存在一个顶点W，它与其它顶点都是连通的，则称此图为有根

图，顶点W即为它的根，下面的两个图都是有根图，左图的1、2、3、4都可以作

为根;而右图的1、2才可以作为根。

10、连通图:如果一个无向图中，任意两个顶点之间都是连通的，则称该无向

图为连通图。否则称为非连通图;上左图为一个连通图。

强连通图:在一个有向图中，对于任意两个顶点U和V，都存在着一条从U到V

的有向路径，同时也存在着一条从V到U的有向路径，则称该有向图为强连通图;

上右图不是一个强连通图。

连通分支:一个无向图的连通分支定义为该图的最大连通子图，左图的连通分

支是它本身。

强连通分支:一个有向图的强连通分支定义为该图的最大的强连通子图，右图含有两个强连通分支，一个是1和2构成的一个子图，一个是3独立构成的一个子图。

三、图的存储结构(n阶e条边)

存储邻接表表示法方比法邻接矩阵表示法边集数组表示法 (链式存储法) 较

直观方便，很容易查找存储稀疏图时，空间效便于查找任一顶点的关联边及图中任两个顶点i和j率比较好，也比较直观关联点，只要从表头向量中取之间有无边(或弧)，出对应的表头指针，然后进行优点以及边上的权值，只要查找即可。查找运算的时间复

看A[i,j]的值即可，时杂性平均为O(e/n)

间复杂性为O(1)

存储稀疏图，则会造成不适合对顶点的运算要查找一个顶点的前驱顶点和

很大的空间浪费和对任意一条边的运以此顶点为终点的边、以及该

算顶点的入度就不方便了，需要缺点扫描整个表，时间复杂度为O

(n+e)。可以用十字邻接表改

进

计算一个顶点的度(或从空间复杂性上讲，边对任一顶点的关联边(顶点)

入度、出度)和关联点，集数组适合于存储稀进行不断、重复的运算适用场合其时间复杂性均为O疏图和那些对边依次

(n) 进行处理的运算

空间复杂度 O(n*n) O(3e) ? O(6e+2n)

四、图的遍历

1、概念

从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问一次后就改为true。

图的遍历分为深度优先遍历和广度(宽度)优先遍历两种方法。

2、深度优先遍历

图的深度优先搜索类似于树的先序遍历。从图中某个顶点V出发，访问此顶点并作已访问标i

记，然后从V的一个未被访问过的邻接点V出发再进行深度优先遍历，当V的所有邻接点都被访iji问过时，则退回到上一个顶点V，再从V的另一个未被访问过的邻接点出发进行深度优先遍历，kk

直至图中所有顶点都被访问到为止。如下左图从顶点a出发，进行深度优先遍历的结果为:a，b，c，d，e，g，f;右图从V出发进行深度优先遍历的结果为:V，V，V，V，V，V，V，V。 112485367

对于一个连通图，深度优先遍历的递归过程如下。

图用邻接表存储} Procedure dfs(i:integer); {

Begin

访问顶点i;

Visited[i]:=True;p:=g[i].link;

While p<>Nil Do {按深度优先搜索的顺序遍历与i相关联的所有顶点}

Begin

j:=p^.adj; {j为i的一个后继}

If Not Visited[j] Then dfs(j); {递归}

p:=p^.next; {p为i的下一个后继}

End;

End;

Procedure dfs(i:integer); {图用邻接矩阵存储}

Begin

访问顶点i;

Visited[i]:=True;

For j:=1 to n do {按深度优先搜索的顺序遍历与i相关联的所有顶点}

Begin

If (Not Visited[j]) and (a[i,j]=1) Then dfs(j);

End;

End;

以上dfs(i)的时间复杂度为O(n*n)。对于一个非连通图，调用一次本过程

dfs(i)，即按深度优先顺序依次访问了顶点i所在的(强)连通分支。主程序如下: procedure work;{邻接矩阵}

begin

fillchar(Visited,sizeof(Visited),0); {初始化}

for i:=1 to n do {深度优先搜索每一个为访问的顶点}

if not Visited then dfs(i);

end;

3、广度(宽度)优先遍历

图的广度优先搜索类似于树的按层次遍历。从图中某个顶点V出发，访问此顶点，然后依次0

访问与V邻接的、未被访问过的所有顶点，然后再分别从这些顶点出发进行广度优先遍历，直到0

图中所有被访问过的顶点的相邻顶点都被访问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。如上左图从顶点a出发，进行广度优先遍历的结果为:a，b，d，e，f，c，g;如上右图从顶点V出发，进1行广度优先遍历的结果为:V，V，V，V，V，V，V，V。 12345678

两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”;而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。下面是广度优先遍历的过程: Procedure bfs(i:integer); {图用邻接矩阵表示}

Begin

访问顶点i;

Visited[i]:=true;

顶点i入队q;

while 队列q非空 do

begin

v; 从队列q中取出队首元素

for j:=1 to n do

begin

if (ot Visited[j]) and (a[v,j]=1) then

begin

访问顶点j;

Visited[j]:=true;

顶点j入队q

end;

end;

end;

End;

以上bfs(i)的时间复杂度仍为O(n*n)。对于一个非连通图，调用一次本过程bfs(i)，即按广度优先顺序依次访问了顶点i所在的(强)连通分支。主程序如下: procedure work;{邻接矩阵}

begin

fillchar(Visited,sizeof(Visited),0);

for i:=1 to n do {广度优先搜索每一个为访问的顶点}

if not Visited then bfs(i);

end;

信息学奥赛基础知识习题(答案版)

信息学奥赛基础知识习题(答案版) 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上） 1．我们把计算机硬件系统和软件系统总称为 C 。 (A)计算机CPU (B)固 件 (C)计算机系统 (D)微处 理机 2．硬件系统是指 D 。 (A)控制器，器运算 (B)存储器，控制器 (C)接口电路，I/O设备 (D)包括(A)、(B)、(C) 3. 计算机软件系统包括 B 。 A) 操作系统、网络软件 B) 系统软件、应用软件 C) 客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D 。 (A)高级语言 (B)符号语言 (C)汇编语言 (D)机器语言 5．硬盘工作时应特别注意避免 B 。 (A)噪声 (B)震动 (C)潮 湿 (D)日光 6．计算机中数据的表示形式是 C 。 (A)八进制 (B)十进制 (C)二进 制 (D)十六进制

7．下列四个不同数制表示的数中，数值最大的是 A 。 (A)二进制数11011101 (B)八进制数334 (C)十进制数219 (D)十六进制 数DA 8．Windows 9x操作系统是一个 A 。 (A)单用户多任务操作系统 (B)单用户单任务操 作系统 (C)多用户单任务操作系统 (D)多用户多任务操 作系统 9．局域网中的计算机为了相互通信，必须安装___B__。 （A）调制解调器（B）网卡（C）声卡（D）电视卡 10．域名后缀为edu的主页一般属于__A____。 （A）教育机构（B）军事部门（C）政府部门（D）商业组织 11. 在世界上注册的顶级域名是__A____。 （A）hk（B）cn（C）tw（D） 12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D ）。 （A）采用超大规模集成电路（B）采用CPU作为中央核心部件 （C）采用操作系统（D）存储程序和程序控制 13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。 (A)用鼠标左键单击该图标 (B)用鼠标右键单击该 图标 (C)用鼠标左键双击该图标 (D)用鼠标右键双击该 图标

信息学奥赛基础知识提纲

信息学奥赛基础知识提纲 （2014年9月） 1 计算机系统 1－1概述 一个完整的计算机系统包括硬件系统和软件系统两大部分，必须具有五大功能：数据传送功能、数据存储功能、数据处理功能、操作控制功能、操作判断功能。它的工作特点是：运算速度快、运算精度高、记忆能力强、通用性广、自动运算。 计算机按照规模可分为：巨型机、大型机、中型机、小型机、微型机、单片机等几种类型。根据用途不同分为通用机和专用机。 硬件指的是计算机的设备实体；软件通常泛指各类程序和文件。软硬件的关系：硬件是软件的基础。软件是硬件的扩充与完善。硬件与软件在逻辑上是等价的。 1946年，世界上第一台计算机诞生于宾夕法尼亚大学，称为ENIAC 。 1949年,第一台存储计算机EDSAC,英国剑桥大学威尔克斯（Wilkes ）设计和制造的。 1951年，第一台商用计算机是UNIVAC 。 1－2 硬件系统 1－2－1 冯·诺伊曼（J.von Neumann ）机：美籍匈牙利数学家 现代计算机的基本结构被称为冯·诺伊曼结构。它的主要特点是储存程序的概念： （1） 采用二进制形式表示数据和指令。 （2） 将程序（包括操作指令和操作数）事先存入主存储器中，使计算机在工作时能够自 动高速地从存储器中取出指令加以执行。 （3） 由运算器、存储器、控制器、输入设备、输出设备五大基础部件组成计算机系统。 冯·诺伊曼机 运 算 器存 储 器 输出设备 输入设备 控 制 器控 制 台 控制信号请 求 信 号 请 求 信 号 控制信号结 果 程序 反馈信息 操作指令 地址 指令

1－2－2 计算机的总线结构 计算机的各个部件需要以某种方式互联，进行数据交换。最常见的互联结构就是总线互联结构和多总线互联结构。总线是一种连接多种设备的信息传递通道，实际上是一组信号线。 典型的计算机总线结构由内部总线和系统总线组成。 （1） 内部总线：用于连接CPU 内部的各个模块。 （2） 系统总线：又称外部总线，用于连接CPU 、存储器和输入输出设备。系统总线的信 号线分为三类：数据线、地址线和控制线。 数据线（Data Bus ）：数据总线的宽度就是指组成数据总线的信号线的数目，它决定了在该总线上一次可以传送的二进制位数。 地址线（Address Bus ）：用以传递地址信息，来指示数据总线上的数据来源和去向。地址线的数目决定了能够访问空间的大小。 控制线（Control Bus ）：用来控制数据总线和地址总线。 某SRAM 芯片，其存储容量为64K*16位，则该芯片的地址线数目和数据线的数目？ 1－2－3 中央处理器（Central Processor Unit ） 1、CPU 包含了冯机五大部件中的运算器（即加法器）和控制器。 运算器：对信息加工和处理的部件，主要完成各种算术运算和逻辑运算。 控制器：通过读取各种指令，并进行翻译、分析，而后对各部件作出相应的控制。 2、CPU 主要由三大部分组成：寄存器组、算术逻辑单元（ALU ）和控制单元（控制器）。 寄存器组：分为通用寄存器（通用寄存器、数据寄存器、地址寄存器、标志寄存器）和状态控制寄存器（程序计数器PC 、指令寄存器IR 、存储器地址寄存器MAR 、存储器缓冲寄存器MBR ）以及程序状态字PSW 。 算术逻辑单元ALU ： 寄存器、存储器、I/O 设备把待处理的数据输入到ALU 。 控制单元：控制器的基本功能就是时序控制和执行控制。根据当前运行的程序，控 制器使CPU 按一定的时序关系执行一序列 的微操作从而完成程序。 时钟信号：控制器根据时钟电路产生的时钟信号进行定时，以控制各种操作按指定的时序进行。计算机的基本功能是执行程序，而程序由一连串的指令组成；计算机的执行过程由一连串的指令周期组成，每一指 令周期完成一条指令。这些指令周期又可进一步细分为更小的单元，直到微操作uop-----CPU 完成的基本的原子操作。 时钟脉冲发生器的晶振频率成为机器的主频，它产生的时钟脉冲信号是整个机器的时间基准，其周期T 称为该计算机的时钟周期。 完成一个微操作的时间就称为CPU 周期（机器周期）。执行一条机器指令所需的时间称为一个指令周期。 3、指令系统（精简指令系统）：操作类指令和控制类指令 一条指令：操作码 + 地址码 一条机器指令的执行：取指令――分析指令――执行指令 4、CPU 的主要指标有： 字长：CPU 一次所能处理的二进制位数。它决定着寄存器、加法器、数据总线等的位数。主频：计算机的时钟频率。（即内频）单位：MHz 或GHz 。 运算速度：CPU 每秒钟能完成的指令数MIPS 。运算速度=1÷ 执行一条机器指令所需的时间

信息学奥赛一本通题解目录-信息学奥赛取消

信息学奥赛一本通题解目录:信息学奥赛取消 第1章 数论1．1 整除1．2 同余1．3 最大公约数1．3．1 辗转相除法1．3．2 进制算法1．3．3 最小公倍数1．3．4 扩展欧几里得算法1．3．5 求解线性同余方程1．4 逆元1．5 中国剩余定理1．6 斐波那契数1．7 卡特兰数1．8 素数1．8．1 素数的判定1．8．2 素数的相关定理1．8．3 Miller-Rabin素数测试1．8．4 欧拉定理1．8．5 PollardRho算法求大数因子1．9

Baby-Step-Giant-Step及扩展算法1．10 欧拉函数的线性筛法1．11 本章习题第2章群论2．1 置换2．1．1 群的定义2．1．2 群的运算2．1．3 置换2．1．4 置换群2．2 拟阵2．2．1 拟阵的概念2．2．2 拟阵上的最优化问题2．3 Burnside引理2．4 Polya定理2．5 本章习题第3章组合数学3．1 计数原理3．2 稳定婚姻问题3．3 组合问题分类3．3．1 存在性问题3．3．2 计数性问题3．3．3 构造性问题3．3．4 最优化问题3．4 排列3．4．1

选排列3．4．2 错位排列3．4．3 圆排列3．5 组合3．6 母函数3．6．1 普通型母函数3．6．2 指数型母函数3．7 莫比乌斯反演3．8 Lucas定理3．9 本章习题第4章概率4．1 事与概率4．2 古典概率4．3 数学期望4．4 随机算法4．5 概率函数的收敛性4．6 本章习题第5章计算几何5．1 解析几何初步5．1．1 平面直角坐标系5．1．2 点5．1．3 直线5．1．4 线段5．1．5 多边形5．1．6

信息学奥赛试题汇编

第19届全国青少年信息学（计算机）奥林匹克BASIC 试题说明： 请考生注意，所有试题的答案要求全部做在答题纸上。 一、基础知识单项选择题（共10题，每小题3分，共计30分） 1、存储容量2GB相当于（） A、2000KB B、2000MB C、2048MB D、2048KB 2、输入一个数（可能是小数），再按原样输出，则程序中处理此数的变量最好使用（） A、字符串类型 B、整数类型 C、实数类型 D、数组类型 3、下列关于计算机病毒的说法错误的是（） A、尽量做到使用正版软件，是预防计算机病毒的有效措施。 B、用强效杀毒软件将U盘杀毒后，U盘就再也不会感染病毒了。 C、未知来源的程序很可能携带有计算机病毒。 D、计算机病毒通常需要一定的条件才能被激活。 4、国标码的“中国”二字在计算机内占（）个字节。 A、2 B、4 C、8 D、16 5、在计算机中，ASCⅡ码是( )位二进制代码。 A、8 B、7 C、12 D、16 6、将十进制数2013转换成二进制数是( )。 A、11111011100 B、11111001101 C、11111011101 D、11111101101 7、现有30枚硬币(其中有一枚假币，重量较轻)和一架天平，请问最少需要称几次，才能找出假币( )。 A、3 B、4 C、5 D、6 8、下列计算机设备中，不是输出设备的是（）。 A、显示器 B、音箱 C、打印机 D、扫描仪 9、在windows窗口操作时，能使窗口大小恢复原状的操作是（） A、单击“最小化”按钮 B、单击“关闭”按钮 C、双击窗口标题栏 D、单击“最大化”按钮 10、世界上第一台电子计算机于1946年诞生于美国，它是出于（）的需要。 A、军事 B、工业 C、农业 D、教学二、问题求解（共2题，每小题5分，共计10分） 1、请观察如下形式的等边三角形： 边长为 2 边长为4 当边长为２时，有4个小三角形。 问：当边长为6时，有________个小三角形。 当边长为n时，有________个小三角形。 2、A、B、C三人中一位是工人，一位是教师，一位是律师。已知：C比律师年龄大，A和教师不同岁，B比教师年龄小。问：A、B、C分别是什么身分？ 答：是工人，是教师，是律师。 三、阅读程序写结果（共4题，每小题8分，共计32分） 1、REM Test31 FOR I =1 TO 30 S=S+I\5 NEXT I PRINT S END 本题的运行结果是：( １) 2、REM Test32 FOR I =1 TO 4 PRINT TAB (13-3*I)； N=0 FOR J =1 TO 2*I-1 N=N+1 PRINT N； NEXT J PRINT NEXT I END 本题的运行结果是：( ２)

(完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档

信息学奥赛（NOIP）必看经典书目汇总！ 小编整理汇总了一下大神们极力推荐的复习资料！（欢迎大家查漏补缺） 基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。

2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。

信息学奥赛基础知识习题(标准答案版)

信息学奥赛基础知识习题(答案版） 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上) 1. 我们把计算机硬件系统和软件系统总称为 C 。 (A)计算机CPU （B）固 件 (C）计算机系统 (Ｄ）微处理机 2．硬件系统是指 D 。 (A）控制器,器运算 (B）存储器,控制器 (C)接口电路,I/O设备（D)包括(A)、(B）、(C） 3．计算机软件系统包括 B 。 A) 操作系统、网络软件Ｂ）系统软件、应用软件 C）客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件 4.计算机硬件能直接识别和执行的只有Ｄ。 (A)高级语言(B)符号语言 (Ｃ)汇编语言(D)机器语言 5.硬盘工作时应特别注意避免Ｂ。 (A)噪声 (B)震动 (C)潮 湿（Ｄ)日光 6．计算机中数据的表示形式是Ｃ。

（Ａ)八进制(B)十进制 (C)二进 制 (D)十六进制 ７．下列四个不同数制表示的数中，数值最大的是 A 。 （A）二进制数11０11１01 （B）八进制数３３4 (C）十进制数２１９（D)十六进制数DA 8.Wｉnｄowｓ９ｘ操作系统是一个 A 。 (Ａ)单用户多任务操作系统(Ｂ)单用户单任务操作系统 （C)多用户单任务操作系统 (D）多用户多任务操作系统 ９．局域网中的计算机为了相互通信,必须安装_＿＿B__。 (A）调制解调器(B)网卡(Ｃ)声卡（Ｄ)电视卡 １0．域名后缀为ｅdu的主页一般属于_＿A____。 (A）教育机构(B）军事部门（C）政府部门（D）商业组织 １1．香港在世界上注册的顶级域名是_＿A____。 （A)ｈk(B)ｃn(Ｃ）tw(D）cｏm 12.计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D )。 （A）采用超大规模集成电路 (B)采用CPＵ作为中央核心部件 （C)采用操作系统（D)存储程序和程序控制 1３.设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。

信息学奥赛基础知识讲义

[信息学奥赛基础知识讲义] 基础部分 一、进制：2进制数与8进制、10进制、16进制数的换算 换算1：将N进制数换算成10进制数（N可以为2,8,16或其它自然数） 换算2：将10进制数换算成N进制数（N可以为2,8,16或其它自然数） 1.下列无符号数中，最小的数是（） A.（11011001）2 B.（75）10 C.（37）8 D.（2A）16 7、小张用十六进制，八进制和十进制写下了如下一个等式： 52-19=33 式中三个数是各不相同进位制的数，试问52,19,33，分别为______。 （A）8，10， 16 （B）10, 16, 8 (c) 8, 16, 10 (D) 10, 8, 16 二、数据的存储和编码 所有的数据都是以二进制存储在计算机的存储器中的，数据的传送、存储、加工、处理或指令都是以二进制形式进行的。 对于数值:弄清原码、反码、补码以及定点数和浮点数。负数在计算机中以补码形式存放，小数在计算机中是以浮点数形式存放。 0的原码表示法有两种，+0和—0 8位定点整数的补码表示范围为-128_____+127 14、计算机中的数有浮点数与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。 A.指数与基数 B. 尾数与小数 C. 阶码与尾数 D.整数与小数 8、如果用一个字节表示一个整数，最高位用作符号位，其他位表示数值，例如 00000001表示+1，10000001表示-1 （1）试问这样表示法的整数a的范围应是———————— A、-127<=a<=127 B、-128<=a<=128 C、-128<=a<127 D、-128

小学信息学奥赛基础知识

信息学竞赛基础知识 第一章计算机的概念、诞生与发展、应用、分类 一、计算机的概念： 是一种能迅速而高效的自动完成信息处理的电子设备，它能按照程序对信息进行加工、处理、存储。 阶段时间逻辑器件应用范围 第一代1946——1958 真空电子管科学计算、军事研究 第二代1959——1964 晶体管数据处理、事物处理 第三代1965——1970 中小规模集成电路包括工业控制的各个领 域 第四代1971——至今大规模或超大规模集成电路应用到了各个领域 三、计算机的主要特点 1、惊人的运算速度； 2、很高的计算机精度； 3、超强的存储能力； 4、准确的逻辑判断能力； 5、自动控制能力。 四、计算机的主要应用： 1、数值计算： 2、数据和信息处理：其特点是数据量大，但计算相对简单。其中数据泛指计算机能处理的各种数字、图形、文字，以及声音、图像等信息。数据处理指对数据的收集、存储、加工、分析和传送的全过程。 3、过程控制：是生产自动化的重要技术内容和手段，是由计算机对所采集到的数据按一定方法经过计算，然后输出到指定执行机构去控制生产的过程。 4、计算机辅助系统：是指利用计算机帮助人们完成各种任务，包括计算机辅助设计(CAD)、计算机辅助制造(CAM)、计算机辅助测试(CAT)、计算机辅助教学(CAI)等。 CAD：即Computer Aided Design的缩写，名称为：计算机辅助设计。 CAM：即Computer Aided Manufacturing的缩写,名称为：计算机辅助制造。 CAI：Computer Aided Instruction的缩写，名称为：计算机辅助教学。 CAT：即Computer Aided Testing的缩写，名称为：计算机辅助测试。 CAE：即Computer Aided Engineering的缩写，名称为：计算机辅助工程。 5、人工智能：是指用计算机模拟人脑的思维过程，是计算机应用的重要领域。 五、计算机分类： 1、按规模分：巨型、大型、中型、小型、微型计算机。

信息学奥赛初赛题型、考试范围与基础知识复习材料

信息学奥赛计算机基础知识复习材料 第一章计算机的概念、诞生与发展、应用、分类 一、计算机的概念：是一种能迅速而高效的自动完成信息处理的电子设备，它能按照程序对信息进行加工、处理、存储。 三、计算机的主要特点 1、惊人的运算速度； 2、很高的计算机精度； 3、超强的存储能力； 4、准确的逻辑判断能力； 5、自动控制能力。 四、计算机的主要应用： 1、数值计算： 2、数据和信息处理：其特点是数据量大，但计算相对简单。其中数据泛指计算机能处理的各种数字、图形、文字，以及声音、图像等信息。数据处理指对数据的收集、存储、加工、分析和传送的全过程。 3、过程控制：是生产自动化的重要技术内容和手段，是由计算机对所采集到的数据按一定方法经过计算，然后输出到指定执行机构去控制生产的过程。 4、计算机辅助系统：是指利用计算机帮助人们完成各种任务，包括计算机辅助设计(CAD)、计算机辅助制造(CAM)、计算机辅助测试(CAT)、计算机辅助教学(CAI)等。 CAD：即Computer Aided Design的缩写，名称为：计算机辅助设计。 CAM：即Computer Aided Manufacturing的缩写,名称为：计算机辅助制造。 CAI：Computer Aided Instruction的缩写，名称为：计算机辅助教学。 CAT：即Computer Aided Testing的缩写，名称为：计算机辅助测试。 CAE：即Computer Aided Engineering的缩写，名称为：计算机辅助工程。 5、人工智能：是指用计算机模拟人脑的思维过程，是计算机应用的重要领域。 五、计算机分类： 1、按规模分：巨型、大型、中型、小型、微型计算机。我们学校和家庭使用的计算机都微型计算机，简称微机，又称个人计算机，或简称PC机。 2、按用途分：专业计算机、通用计算机。 3、按原理分：模拟计算机、数字计算机。 六、微型机的主要技术指标 1、字长：指计算机能够直接处理的二进制数据的位数。单位为位（BIT）。 2、主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上决定了计算机的运算速度。 3、内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（BYTE）。 8BIT=1BYTE 1024B=1KB 1024KB=1MB 4、外存容量：一般指软盘、硬盘、光盘。 七、微型计算机时代 1、第一代微型计算机通常把IBM-PC/XT及其兼容机称为第一代微型计算机。 2、第二代微型计算机286 AT机及其兼容机被称为第二代微型计算机。 3、第三代微型计算机 386微机被称为第三代微型计算机。

信息学奥赛基础知识习题答案版完整版

信息学奥赛基础知识习 题答案版 Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】

信息学奥赛基础知识习题(答案版) 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上） 1．我们把计算机硬件系统和软件系统总称为C?。 (A)计算机CPU?(B)固件? (C)计算机系统?(D)微处理机 2．硬件系统是指D。 (A)控制器，器运算(B)存储器，控制器 (C)接口电路，I/O设备?(D)包括(A)、(B)、(C) 3.计算机软件系统包括B。 A)操作系统、网络软件B)系统软件、应用软件 C)客户端应用软件、服务器端系统软件D)操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有D。 (A)高级语言?(B)符号语言 (C)汇编语言?(D)机器语言 5．硬盘工作时应特别注意避免B?。 (A)噪声?(B)震动?(C)潮湿?(D)日光 6．计算机中数据的表示形式是C。 (A)八进制?(B)十进制?(C)二进制?(D)十六进制 7．下列四个不同数制表示的数中，数值最大的是A?。 (B)八进制数334 (C)十进制数219?(D)十六进制数DA 8．Windows9x操作系统是一个A?。

(A)单用户多任务操作系统?(B)单用户单任务操作系统 (C)多用户单任务操作系统?(D)多用户多任务操作系统 9．局域网中的计算机为了相互通信，必须安装___B__。 （A）调制解调器（B）网卡（C）声卡（D）电视卡 10．域名后缀为edu的主页一般属于__A____。 （A）教育机构（B）军事部门（C）政府部门（D）商业组织 11.香港在世界上注册的顶级域名是__A____。 （A）hk（B）cn（C）tw（D）com 12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（D?）。 （A）采用超大规模集成电路?（B）采用CPU作为中央核心部件 （C）采用操作系统?（D）存储程序和程序控制 13．设桌面上已经有某应用程序的图标，要运行该程序，可以C?。 (A)用鼠标左键单击该图标?(B)用鼠标右键单击该图标 (C)用鼠标左键双击该图标?(D)用鼠标右键双击该图标 14．若己选定某文件，不能将该文件复制到同一文件夹下的操作是C?。 (A)用鼠标右键将该文件拖动到同一文件夹下 (B)先执行"编辑"菜单中的复制命令，再执行粘贴命令 (C)用鼠标左键将该文件拖动到同一文件夹下 (D)按注Ctrl键，再用鼠标右键将该文件拖动到同一文件夹下 15．在“我的电脑”窗口中，若已选定了文件或文件夹，为了设置其属性，可以打开属性对话框的操作是B。 (A)用鼠标右键单击“文件”菜单中的“属性”命令

信息学奥赛基础知识

§ 1 计算机概述 世界第一台电子数字式计算机于1946年美国宾夕法尼亚大学正式投入运行，它的名称叫ENIAC (埃尼阿克)，是电子数值积分计算机的缩写。它使用了17468个真空电子管，耗电174千瓦，占地170平方，重30吨，每秒钟可进行5000次加法运算。 被西方人誉为“计算机之父”的美籍匈牙利科学家、数学家冯·诺依曼于1945年发表了一个全新的"存储程序通用电子计算机方案"—EDVAC 。EDVAC 方案提出了著名的“冯·诺依曼体系结构”理论： (1)采用二进制形式表示数据和指令 在存储程序的计算机中，数据和指令都是以二进制形式存储在存储器中的。从存储器存储的内容来看两者并无区别．都是由0和1组成的代码序列，只是各自约定的含义不同而已。计算机在读取指令时，把从计算机读到的信息看作是指令；而在读取数据时，把从计算机读到的信息看作是操作数。数据和指令在软件编制中就已加以区分，所以正常情况下两者不会产生混乱。有时我们也把存储在存储器中的数据和指令统称为数据，因为程序信息本身也可以作为被处理的对象，进行加工处理，例如对照程序进行编译，就是将源程序当作被加工处理的对象。 (2)采用存储程序方式 这是冯·诺依曼思想的核心内容。如前所述，它意味着事先编制程序，事先将程序(包含指令和数据)存入主存储器中，计算机在运行程序时就能自动地、连续地从存储器中依次取出指令且执行。这是计算机能高速自动运行的基础。计算机的工作体现为执行程序，计算机功能的扩展在很大程度上也体现为所存储程序的扩展。计算机的许多具体工作方式也是由此派生的。 冯·诺依曼机的这种工作方式，可称为控制流(指令流)驱动方式。即按照指令的执行序列，依次读取指令，然后根据指令所含的控制信息，调用数据进行处理。因此在执行程序的过程中，始终以控制信息流为驱动工作的因素，而数据信息流则是被动地被调用处理。为了控制指令序列的执行顺序，设置一个程序(指令)计数器PC(ProgramCounter)，让它存放当前指令所在的存储单元的地址。如果程序现在是顺序执行的，每取出一条指令后PC 内容加l ，指示下一条指令该从何处取得。如果程序将转移到某处，就将转移的目标地址送入PC ，以便按新地址读取后继指令。所以，PC 就像一个指针，一直指示着程序的执行进程，就是指示控制流的形成。虽然程序与数据都采用二进制代码，仍可按照PC 的内容作为地址读取指令，再按照指令给出的操作数地址去读取数据。由于多数情况下程序是顺序执行的，所以大多数指令需要依次地紧挨着存放，除个别即将使用的数据可以紧挨着指令存放外、一般将指令和数据分别存放在该程序区的不同区域内。 (3)由运算器、存储器、控制器、输入设备和输出设备五大部件组成计算机系统，并规定了这五部分的基本功能。 上述这些概念奠定了现代计算机的基本结构思想，到目前为止，绝大多数计算机仍沿用这一体制，即冯·诺依曼型计算机体制。 巨型化、微型化、多媒体化、网络化、智能化 计算机的特点： 1.运算速度快：最快可以达到上万亿次/s 。 2.精确度高：微型机可达到十几位有效数字。 3.存储功能（有记忆功能）：能存储程序和数据。 4.能进行逻辑运算。 5.在程序的控制下能自动工作。 计算机的主要应用： 1、科学计算：密码破译，天气预报，地质勘探， 卫星轨道计算 2、数据处理：数据库管理，企业信息管理， 统计汇总、办公自动化 3、自动控制：机器人以及各种自动化装备 4、计算机辅助设计/分析/制造/教学：机械CAD ，建筑CAD ，计算机辅助教学CAI 5、智能模拟：人工智能、专家系统、自学习 6、电子商务： 7、休闲娱乐： 计算机分类： 1、按规模分：巨型机、大型机、中型机、小型机、 微型机 2、按用途分：专用机、通用机 3、按处理方式分：模拟计算机、数字计算机以 及数字模拟混合计算机 4、照其工作模式分：服务器、工作站 计算机的主要性能技术指标 1.字长 字长是计算机运算部件一次能处理的二进制数据的位数。字长愈长，计算机的处理能力就愈强。 早期的微型计算机的字长为16位，如：80286等。 现在的微型计算机的字长为32位，如80386， 80486，PIV 等。对于数据，字长愈长，运算精度愈高；对于指令，字长愈长，则功能愈强，而寻址的存储空间也愈大。 2.速度 不同配置微型计算机按相同的算法执行相同的任务所需要的时间可能是不同的，这和微型计算机的速度有关。 微型计算机速度指标可以用主频和运算速度来评价。主频也称时钟频率，是指CPU 工作时的频率。主频是衡量微型机运行速度的主要参数，主频越高，执行一条指令的时间就越短，因而速度就愈快。主频一般以兆赫兹（MHz ）为单位。目前的微机的主频在500MHz 左右，高的可达1000MHz 左右，甚至更高。 运算速度是以每秒百万指令数（MIPS ）为单位。这个指标较主频更能直观的反映微型计算机的运算速度。 速度是一个综合指标，影响微型计算机速度的因素还有许多，如存储器的存取时间系统总线的时钟频率等。 3.存储系统容量 存储系统主要包括主存储器（也称内存）和辅助存储器（也称外存）。内存储器容量是指为计算机系统所配置的内存总字节数，CPU 可直接访问的大部分存储空间。 存储容量以字节（B ）为单位，一个字节由8位二进制位组成。用KB ，MB ，GB ，TB 等表示，具体换算公式为： 目前，软件系统的体积越来越大，对存储空间要求也越来越高，很多复杂的软件，要有足够大的硬盘空间才能装得下，要有足够大的内存空间才能运行。 4.系统可靠性 计算机的可靠性以平均无故障时间（MTBF ）表示： 其中：Ti ：第i 次无故障时间；N ：故障总次数。MTBF 愈大，系统性能愈好。 5.系统可维护性 计算机的可维护性以平均修复时间（MTTR ）表示： 其中：Ti ：第i 次故障修复时间; M ：修复总次数。MTTR 愈大，系统性能愈好。 6.性价比 性价比是用来衡量计算机产品优劣的概括性指标。性：指性能，代表计算机的使用价值，它包括计算机的运算速度、存储器容量、存取周期。通道信息流量速率、输入输出设备的配置和计算机的可靠性。 价：指价格，代表计算机的售价。 性价比愈大，表明计算机系统愈好。 §2计算机系统的基本组成 完整的计算机系统系统包括：硬件系统和软件系统。两个部分又由若干个部件组成(如图）。 硬件系统是计算机的“躯干”，是物质基础。而软件系统则是建立在这个“躯干”上的“灵魂”。 （一）计算机硬件 计算机硬件系统由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。（如下图所示）

信息学奥赛-计算机基础知识

第一章计算机基础知识 (2) 第一节数制及其转换 (2) 第二节算术运算和逻辑运算 (4) 第三节原码、反码和补码 (7) 第四节浮点数的表示方法 (9) 第五节奇偶校验 (10) 第六节 ASCII码表 (12) 第二章计算机硬件基础 (13) 第一节中央处理器 (13) 第二节存储器系统 (15) 第三节输入输出系统 (17) 第三章网络基础知识 (19) 第一节网络的组成与结构 (19) 第二节网络协议 (20) 第三节 Internet相关知识 (20) 第三节 Internet相关知识 (21) 第四章其他相关基础知识 (23) 第一节计算机病毒 (23) 第二节数据库系统 (23) 第五章数据结构之线性结构 (25) 第一节线性表 (25) 第二节栈 (27) 第三节队列 (29) 第六章数据结构之非线性结构 (31) 第一节树的概念 (31) 第二节树的表示方法和存储结构 (33) 第三节二叉树的概念 (36) 第四节二叉树的遍历 (40) 第五节普通树的遍历 (44) 第六节根据两种遍历顺序确定树结构 (46) 第七节二叉排序树 (47) 第八节最优二叉树(哈夫曼树) (48) AOE网 (50)

第一章计算机基础知识 第一节数制及其转换 一、二、八、十六进制转十进制的方法：乘权相加法。 例如： （11010110）2 = 1×27 + 1×26 + 0×25 + 1×24 + 0×23 + 1×22 + 1×21 + 0×20 = （214）10 （2365）8 = 2×83 + 3×82 + 6×81 + 5×80 = （1269）10 （4BF）16 = 4×162 + 11×161 + 15×160 = (1215)10 带小数的情况： （110.011）2 = 1×22 + 1×21 + 1×20 + 0×2-1 + 1×2-2 + 1×2-3 = （6.375）10（5.76）8= 5×80 + 7×8-1 + 6×8-2 = （5.96875）10 （D.1C）16= 13×160+ 1×16-1 + 12*16-2 = （13.109375）10 二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。例一：（43）10 = （101011）2例二：（0.375）10 = （0.011）2

信息学奥赛考试大纲

信息学奥赛考试大纲 一、竞赛形式和成绩评定 联赛分两个等级组：普及组和提高组。每组竞赛分两轮：初试和复试。 l 初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。初试为资格测试，各省初试成绩在本赛区前15%的学生进入复赛。 l 复试形式为上机，着重考察学生对问题的分析理解能力，数学抽象能力，编程语言的能力和编程技巧、想象力和创造性等。各省联赛的等第奖在复试的优胜者中产生。 比赛中使用的程序设计语言是： l 2003年：初赛：BASIC、PASCAL或C/C++；复赛：BASIC、PASCAL或C/ C++。 l 2004年：初赛：BASIC、PASCAL或C/C++：复赛：PASCAL或C/C++。 l 2005年及之后：初赛：PASCAL或C/C++：复赛：PASCAL或C/C++。 每年复赛结束后，各省必须在指定时间内将本省一等奖候选人的有关情况、源程序和可执行程序报送科学委员会。经复审确认后，由中国计算机学会报送中国科协和教育部备案。中国计算机学会对各省获NOIP二等奖和三等奖的分数线或比例提出指导性意见，各省可按照成绩确定获奖名单。 二、试题形式 每次联赛的试题分四组：普及组初赛题A1、普及组复赛题A2、提高组初赛题B 1和提高组复赛题B2。其中，A1和B1类型相同，A2和B2类型相同，但题目不完全相同，提高组难度高于普及组。 l 初赛：初赛全部为笔试，满分100分。试题由四部分组成： 1、选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。 2、问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分；否则不得分。 3、程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。 4、程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。 l 复赛：复赛的题型和考试形式与NOI类似，全部为上机编程题，但难度比NO I低。题目包括4道题，每题100分，共计400分。每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得10－20分，累计分即为该道题的得分。 三、试题的知识范围一) 初赛内容与要求：计算机的基本常识 1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化） 2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方

信息学奥赛基础知识讲义.doc

百度文库- 让每个人平等地提升自我 [ 信息学奥赛基础知识讲义] 基础部分 一、进制： 2 进制数与8 进制、 10 进制、 16 进制数的换算 换算 1：将 N 进制数换算成10 进制数（ N 可以为 2,8,16或其它自然数） 换算 2：将 10 进制数换算成N进制数（ N 可以为 2,8,16或其它自然数） 1. 下列无符号数中，最小的数是（） A.（）2 B.（75）10 C.（ 37）8 D.（2A）16 7、小张用十六进制，八进制和十进制写下了如下一个等式： 52-19=33 式中三个数是各不相同进位制的数，试问52,19,33 ，分别为 ______。 （ A） 8， 10， 16 （ B） 10, 16, 8 (c) 8, 16, 10 (D) 10, 8, 16 二、数据的存储和编码 所有的数据都是以二进制存储在计算机的存储器中的，数据的传送、存储、加工、处理或指令都是以二进制形式进行 的。 对于数值 : 弄清原码、反码、补码以及定点数和浮点数。负数在计算机中以补码形式存放，小数在计算机中是以浮 点数形式存放。 0 的原码表示法有两种，+0和—0 8 位定点整数的补码表示范围为 -128_____+127 14、计算机中的数有浮点数与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。 A. 指数与基数 B. 尾数与小数 C. 阶码与尾数 D. 整数与小数 8、如果用一个字节表示一个整数，最高位用作符号位，其他位表示数值，例如 00000001 表示 +1，表示 -1 （ 1）试问这样表示法的整数 a 的范围应是———————— A、 -127<=a<=127 B、-128<=a<=128 C、 -128<=a<127 D、-128