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

NOIP知识点总览


NOIP 基础知识要点一

NOIP 复习总览
第一部分 计算机组成原理与信息技术发展 一、数制与编码
几种常用的数制及它们之间的相互转换: 进制 十进制 二进制 八进制 十六进制 基数 0、1、2、3、4、5、6、7、8、9 0、1 0、1、2、3、4、5、6、7 基数个数 10 2 8 权 10 2 8
i i i


进数规律 逢十进一 逢二进一 逢八进一

0、1、2、3、4、5、6、7、8、9、 i 16 16 逢十六进一 A、B、C、D、E、F 十进制数转换为二进制数、八进制数、十六进制数的方法: 二进制数、八进制数、十六进制数转换为十进制数的方法:按权展开求和法 1.二进制与十进制间的相互转换: (1)二进制转十进制 方法: “按权展开求和” 3 2 1 0 -1 -2 例: (1011.01)2 =(1×2 +0×2 +1×2 +1×2 +0×2 +1×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 0.5 0 X 2 1.0 1 2.八进制与二进制的转换: 二进制数转换成八进制数:从小数点开始,整数部分向左、小数部分向右,每 3 位为 一组用一位八进制数的数字表示,不足 3 位的要用“0”补足 3 位,就得到一个八进制数。
By-SHBF 1

NOIP 基础知识要点一

八进制数转换成二进制数: 把每一个八进制数转换成 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 3.十六进制与二进制的转换: 二进制数转换成十六进制数:从小数点开始,整数部分向左、小数部分向右,每 4 位 为一组用一位十六进制数的数字表示,不足 4 位的要用“0”补足 4 位,就得到一个十六进 制数。 十六进制数转换成二进制数:把每一个八进制数转换成 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

进制转换对照表
二进制 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 10000 10001 10010 八进制 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21 22 十进制 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12
By-SHBF 2

NOIP 基础知识要点一

10011 ?

23 ?

19 ?

13 ?

注意:以上所说的二进制数均是无符号的数。这些数的范围如下表: 无符号位二进制数位数 数值范围 十六进制范围表示法 8 位二进制数 16 位二进制数 32 位二进制数 0~255 (255=2 -1)
16 8

00~0FFH 00000000H~0FFFFFFFFH

0~65535 (65535=2 -1) 0000H~0FFFFH 0~2 -1
32

带符号数的机器码表示方法 1.带符号二进制数的表示方法: 带符号二进制数用最高位的一位数来表示符号:0 表示正,1 表示负。 含符号位二进制数位数 数值范围 十六进制范围表示法 8 位二进制数 16 位二进制数 32 位二进制数 -128 ~ +127 -32768 ~ +32767 -2147483648 +2147483647 ~ 80H~7FH 8000H~7FFFH 80000000H~7FFFFFFFH

2、符号位的表示:最常用的表示方法有原码、反码和补码。 (1)原码表示法:一个机器数 x 由符号位和有效数值两部分组成,设符号位为 x0,x 真值的绝对值|x|=x1x2x3...xn,则 x 的机器数原码可表示为:
n ,当 x>=0 时,x0=0,当 x<0 时,x0=1。 [x]原= 0 1 2 例如:已知:x1=-1011B,x2= +1001B,则 x1,x2 有原码分别是 [x1] 原=11011B,[x2]原=01001B 规律:正数的原码是它本身,负数的原码是取绝对值后,在最高位(左端)补“1” 。 (2)反码表示法:一个负数的原码符号位不变,其余各位按位取反就是机器数的反码 表示法。正数的反码与原码相同。 按位取反的意思是该位上是 1 的,就变成 0,该位上是 0 的就变成 1。即 1=0,0=1

x x x ...x

[x ] [x ] B B 例: x1 ? ?1011 , x2 ? ?1001 ,求 1 反 和 2 反 。
解:

[ x1 ]反 = 10100 B , [ x2 ]反 = 01001 B

(3)补码表示法: 首先分析两个十进制数的运算:78-38=41,79+62=141 如果使用两位数的运算器,做 79+62 时,多余的 100 因为超出了运算器两位数的范围 而自动丢弃,这样在做 78-38 的减法时,用 79+62 的加法同样可以得到正确结果。 模是批一个计量系统的测量范围,其大小以计量进位制的基数为底数,位数为指数的 2 幂。如两位十进制数的测量范围是 1——9,溢出量是 100,模就是 10 =100,上述运算称为 模运算,可以写作: 79+(-38)=79+62 (mod 100) 进一步写为 -38=62,此时就说 –38 的补法(对模 100 而言)是 62。计算机是一种 有限字长的数字系统,因此它的运算都是有模运算,超出模的运算结果都将溢出。n 位二进 n 制的模是 2 , 一 个 数 的 补 码 记 作 [x] 补 , 设 模 是 M , x 是 真 值 , 则 补 码 的 定 义 如 下 :

( x ? 0) ?[ x]原 [ x ]补 ? ? ?M ? x ( x ? 0)
例:设字长 n=8 位,x=-1011011B,求[x]补。 8 解:因为 n=8,所以模 M=2 =100000000B,x<0,所以
By-SHBF 3

NOIP 基础知识要点一

[x]补=M+x=100000000B-1011011B=10100101B 注意:这个 x 的补码的最高位是“1” ,表明它是一个负数。对于二进制数还有一种更 加简单的方法由原码求出补码: (1)正数的补码表示与原码相同; (2)负数的补码是将原码符号位保持“1”之后,其余各位按位取反,末位再加 1 便 得到补码,即取其原码的反码再加“1” :[x]补=[x]反+1。 下表列出 ? 0,?39,?127及 ? 128 的 8 位二进制原码,反码和补码并将补码用十六进制 表示。 真值 原码(B) 反码(B) 补码(B) 补码(H) +127 +39 +0 -0 -39 -127 0 111 1111 0 010 0111 0 000 0000 1 000 0000 1 010 0111 1 111 1111 0 111 1111 0 010 0111 0 000 0000 1 111 1111 1 101 1000 1 000 0000 0 111 1111 0 010 0111 0 000 0000 0 000 0000 1 101 1001 1 000 0001 7F 27 00 00 D9 81

-128 无法表示 无法表示 1 000 0000 80 从上可看出, 真值+0 和-0 的补码表示是一致的, 但在原码和反码表示中具有不同形式。 8 位补码机器数可以表示-128,但不存在+128 的补码与之对应,由此可知,8 位二进制补码 能表示数的范围是-128——+127。还要注意,不存在-128 的 8 位原码和反码形式。 逻辑运算 运算规则 0∧0=0 0∨0=0 0∨0=0 ∧(and)-并且 0∧1=0 0∨1=1 0∨1=1 1∧0=0 1∨0=1 1∨0=1 ∨(or)-或 1∧1=1 1∨1=1 1∨1=0 ∨Xor -异或

定点数和浮点数 (一)定点数(Fixed-Point Number) 计算机处理的数据不仅有符号, 而且大量的数据带有小数, 小数点不占有二进制一位而 是隐含在机器数里某个固定位置上。 通常采取两种简单的约定: 一种是约定所有机器数的小 数的小数点位置隐含在机器数的最低位之后,叫定点纯整机器数,简称定点整数。另一种约 定所有机器数的小数点隐含在符号位之后、有效部分最高位之前,叫定点纯小数机器数,简 称定点小数。无论是定点整数,还是定点小数,都可以有原码、反码和补码三种形式。 (二)浮点数(Floating-Point Number) 计算机多数情况下采作浮点数表示数值, 它与科学计数法相似, 把一个二进制数通过移 动小数点位置表示成阶码和尾数两部分: N ? 2 ? S 其中:E——N 的阶码(Expoent) ,是有符号的整数 S——N 的尾数(Mantissa) ,是数值的有效数字部分,一般规定取二进制定点纯 小数形式。 +7 +3 -1 例:1011101B=2 *0.1011101,101.1101B=2 *0.1011101,0.01011101B=2 *0.1011101 浮点数的格式如下: E0 E1E2?????En E0 E1E2?????En
E

阶符 阶 尾符 尾数 浮点数由阶码和尾数两部分组成,底数 2 不出现,是隐含的。阶码的正负符号 E0,在最 前位,阶反映了数 N 小数点的位置,常用补码表示。二进制数 N 小数点每左移一位,阶增加
By-SHBF 4

NOIP 基础知识要点一

1。尾数是这点小数,常取补码或原码,码制不一定与阶码相同,数 N 的小数点右移一位, 在浮点数中表现为尾数左移一位。尾数的长度决定了数 N 的精度。尾数符号叫尾符,是数 N 的符号,也占一位。 例:写出二进制数-101.1101B 的浮点数形式,设阶码取 4 位补码,尾数是 8 位原码。 +3 -101.1101=-0.1011101*2 浮点形式为: 阶码 0011 尾数 11011101 补充:阶码 0011 中的最高位“0”表示指数的符号是正号,后面的“011”表示指数是 “3” ;尾数 11011101 的最高位“1”表明整个小数是负数,余下的 1011101 是真正的尾数。 例:计算机浮点数格式如下,写出 x=0.0001101B 的规格化形式,阶码是补码,尾数是原码。 -3 x=0.0001101=0.1101*10 又[-3]补=[-001B]补=[1011]补=1101B 所以 浮点数形式是 1 101 0 1101000 ASCII 码 ( American Standard Code for Information Interchange ) 美国标准信息交换代码 将每个字符用 7 位的二进制数来表示,共有 128 种状态 大小字母、0?9、其它符号、控制符 ‘ 0 '―― 48 ‘ A ’ ―― 汉字信息编码 1. 汉字输入码

65 ‘ a ’―― 97

汉字输入方法大体可分为:区位码(数字码) 、音码、形码、音形码。 · 区位码:优点是无重码或重码率低,缺点是难于记忆; · 音码:优点是大多数人都易于掌握,但同音字多,重码率高,影响输入的速度; · 形码:根据汉字的字型进行编码,编码的规则较多,难于记忆,必须经过训练才能较好 地掌握;重码率低; ·音形码:将音码和形码结合起来,输入汉字,减少重码率,提高汉字输入速度。 2.汉字交换码 汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用 的代码标准。GB2312-80 是我国统一的汉字信息交换码的标准。 GB2312-80 标准包括了 6763 个汉字,按其使用频度分为一级汉字 3755 个和二级汉字 3008 个。一级汉字按拼音排序,二级汉字按部首排序。此外,该标准还包括标点符号、数 种西文字母、图形、数码等符号 682 个。 由于 GB2312-80 是 80 年代制定的标准, 在实际应用时常常感到不够, 后来采用新颁布 的 GB18030 信息交换用汉字编码字符集,这个标准繁、简字均处同一平台,可解决两岸三地 间 GB 码与 BIG5 码间的字码转换不便的问题。
国标 GB2312-80 规定,全部国标汉字及符号组成 94*94 的矩阵,在这矩阵中,每一行称为一 个“区”,每一列称为一个“位”。这样,就组成了 94 个区(01~94 区),每个区内有 94 个 位(01~94)的汉字字符集。区码和位码简单地组合在一起(即两位区码居高位,两位位码居低 位)就形成了“区位码”。区位码可唯一确定某一个汉字或汉字符号,反之,一个汉字或汉字符 号都对应唯一的区位码,如汉字“玻”的区位码为“1803”(即在 18 区的第 3 位)。 所有汉字及符号的 94 个区划分成如下四个组: 1~15 区为图形符号区,其中,1~9 区为标准 区, 10~15 区为自定义符号区。 16~55 区为一级常用汉字区,共有 3755 个汉字,该区的汉字按拼音排序。 56~87 区为二级非常用汉字区,共有 3008 个汉字,该区的汉字按部首排序。 88~94 区为用户自定义汉字区。 汉字的内码是从上述区位码的基础上演变而来的。它是在计算机内部进行存储、传输所使用

By-SHBF

5

NOIP 基础知识要点一

的汉字代码。 区码和位码的范围都在 01~94 内,如果直接用它作为内码就会与基本 ASCII 码发生冲突, 因此汉字的内码采用如下的运算规定: 高位内码=区码十 20H+80H 低位内码=位码十 20H+80H 在上述运算规则中加 20H 应理解为基本 ASCII 的控制码;加 80H 意在把最高二进制位置 “1”,以与基本 ASCII 码相区别,或者说是识别是否汉字的标志位。 例:将汉字“玻”的区位码转换成机内码: 高位内码=(18)10+(20)16+(80)16 =(00010010)2+(00100000)2+(10000000)2 =(10110010)2 =(B2)16=B2H 低位内码=(3)10+(20)16+(80)16 =(00000011)2+(00100000)2+(10 000 000)2=(10100011)2=(A3)16=A3H 内码=区码+20H+80H+位码+20H+80H =(1011001010100011)2=B2A3H

3.字形存储码 字形存储码是指供计算机输出汉字(显示或打印)用的二进制信息,也称字模。通常, 采用的是数字化点阵字模。如下图: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 一般的点阵规模有 16×16,24×24,32×32,64×64 等,每一个点在存储器中用一个 二进制位(bit)存储。例如,在 16×16 的点阵中,需 16×16bit=32 byte 的存储空间。 在相同点阵中,不管其笔划繁简,每个汉字所占的字节数相等。 为了节省存储空间, 普遍采用了字形数据压缩技术。 所谓的矢量汉字是指用矢量方法将 汉字点阵字模进行压缩后得到的汉字字形的数字化信息。
16×16 点表示

题例
ASCII 码 (07)ASCII 码的含义
By-SHBF

6

NOIP 基础知识要点一

(09)关于 ASCII,下面哪个说法是正确的: A 、ASCII 码就是键盘上所有键的唯一编码。 B、 一个 ASCII 码使用一个字节的内存空间就能够存放。 C、 最新扩展的 ASCII 编码方案包含了汉字和其他欧洲语言的编码。 D、 ASCII 码是英国人主持制定并推广使用的。 (09)已知字母 A 的 ASCII 编码为 65(十进制) ,则大写字母 J 的十进制 ASCII 编码为

汉字编码: (08)在 32*32 点阵的“字库”中,汉字“北”与“京”的字模占用字节数之和是
在 24*24 点阵的“字库”中,汉字“一”与“编”的字模占用字节数分别是(C) A.32,32 B.32,72 C.72,72 D.72,32 组成’教授’ (jiao shou )’副教授’ (fu jiao shou )与’讲师’ jiang shi)这三个 ( 词的汉字,在 GB2312-80 字符集中都是一级汉字.对这三个词排序的结果是(D) . A 教授,副教授,讲师 B.副教授,教授,讲师 C 讲师,副教授,教授 D.副教授,讲师,教授 GB2312-80 规定了一级汉字 3755 个,二级汉字 3008 个,其中二级汉字字库中的汉字是以 ( B )为序排列的。 A.以笔划多少 B.以部首 C.以 ASCⅡ码 D.以机内码

逻辑运算
(07)在 Pascal 语言中,表达式 (23 or 2 xor 5)的值是: A. 18 B. 1 C.23 D.32 (07)在 Pascal 语言中,判断整数 a 等于 0 或 b 等于 0 或 c 等于 0 的正确的条件表达 式是( ) A. not ((a<>0) or (b<>0) or (c<>0)) B. not ((a<>0) and (b<>0) and (c<>0)) C. not ((a=0) and (b=0)) or (c=0) D.(a=0) and (b=0) and (c=0) (07)设 A=B=true,C=D=false,以下逻辑运算表达式值为真的有( )。 A. (﹁A∧B)∨(C∧D∨A) B. ﹁ ( ( (A∧B)∨C)∧D) C. A∧(B∨C∨D)∨D D. (A∧(D∨C)) ∧B (08) 设A=true, B=false, C=true, D=false, 以下逻辑运算表达式值为真的是 ( ) 。 A. (A∧B)∨(C∧D∨ ? A) B. (( ? A∧B)∨C)∧ ? D C. (B∨C∨D)∧D∧A D. A∧(D∨ ? C)∧B (08)在PASCAL程序中,表达式(200 or 10)的值是 已知 A=35H,则 A∧05H∨A∧3OH 的结果是:( C ) 。 A)3OH B)05H C) 35H D) 53H

数制问题
(07)与十进制数 1770 相对应的 8 进制数 (07)(2070)16+(34)8 的结果是 (08)与十进制数 28.5625 相等的四进制数 (08)(2008)10 + (5B)16 的结果是 (09)十进制小数 125.125 对应的八进制数
By-SHBF 7

NOIP 基础知识要点一

算式(2047)10-(3FF)16+(2000)8 的结果是( A ) 。 A)(2048)10 B)(2049)10 C) (3746)8
2

D) (1AF7)16

已知 x=(0.1011010)2,则[x/2] =( C ) A) 0.1011101. B) 11110110

。 D) 0.100110

C) 0.0101101

[x]补码=10011000,其原码为(B ) A)011001111 B)11101000 C)11100110 D)01100101 (10)设 x、y、z 分别代表三进制下的一位数字,若等式 xy+zx=xyx 在三进制下成立,那么同 样在三进制下,等式 xy*zx=( )也成立。 (A)YXZ (B)ZXY (C)XYZ (D) XZY 下列无符号数中,最小的数是( C ) A.(11011001)2 B.(75)10 C.(37)8 D.(2A)16 计算机中的数有浮点数与定点数两种, 其中用浮点数表示的数, 通常由 (C ) 这两部分组成。 A.指数与基数 B. 尾数与小数 C. 阶码与尾数 D.整数与小数 十进制算术表达式:3*512+7*64+4*8+5 的运算结果,用二进制表示为(B) . A. 10111100101 B.11111100101 C1111l0100101 D.11111101101 十进制数 2004 等值于八进制数( B ) 。 A. 3077 B. 3724 C. 2766 D. 4002

E. 3755

十进制数 100.625 等值于二进制数( B ) 。 A. 1001100.101 B. 1100100.101 C. 1100100.011

D. 1001100.11

E. 1001100.01

以下二进制数的值与十进制数23.456 的值最接近的是(D )。 A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111

二、 计算机系统
(一)计算机发展:
年代 第一代 第二代 第三代 第四代 1946-1958 1959-1964 1965-1970 1971-? 元件 电子管 晶体管 集成电路 大规模集成电路

1946 年 2 月, 在美国宾夕法尼亚大学诞生了世界上第一台电子计算机 ENIAC Electronic ( Numerical Integrator And Computer) ,这台计算机占地 170 平方米,重 30 吨,用了 18000 多个电子管,每秒能进行 5000 次加法运算。 我国的计算机发展情况
By-SHBF 8

NOIP 基础知识要点一

·我国从 1956 年开始计算机的科研和教学工作; ·1960 年我国第一台自行设计的通用电子计算机 107 机诞生; 1964 年我国研制成大型通用电子计算机 119 机; ·1983 年每秒运行一亿次的银河巨型计算机在国防科技大学诞生; 1992 年研制成功每秒运行 10 亿次的“银河Ⅱ”巨型计算机; 1997 年又研制成功每秒运行 130 亿次的“银河Ⅲ”巨型计算机;

(二)计算机的主要技术指标
1、字长:知己算计能够直接处理的二进制数据的位数。单位为位(BIT) 2、主频:指计算机主时钟在一秒钟内发出的脉冲数,在很大程度上决定了计算机的运 算速度。 3、内存容量:是标志计算机处理信息能力强弱的一向技术指标。单位为字节(BYTE)。 8BIT=1BYTE 1024B=1KB 1024KB=1MB 4、外存容量:一般指软盘、硬盘、光盘。

计算机的特点: 运算速度快,运算精度高,具有记忆能力,具有逻辑判断能力,具有自动控制能力;

(三)计算机系统组成及工作原理
0、冯·诺依曼理论
1944 年,美籍匈牙利数学家 冯·诺依曼 提出计算机基本结构和工作方式的设想,为 计算机的诞生和发展提供了理论基础。时至今日,尽管计算机软硬件技术飞速发展,但计算 机本身的体系结构并没有明显的突破,当今的计算机仍属于冯·诺依曼架构。 其理论要点如下: (1) 、计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备 5 部分组成。 (2) 存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序, 、 然后把 程序和数据一起输入计算机,计算机对已存入的程序和数据处理后,输出结果。 (3) 、二进制思想----计算机内部所有的处理都是通过 2 进制来实现

1.计算机的系统组成

By-SHBF

9

NOIP 基础知识要点一

运算器 控制器 硬件系统 存储器 输入设备 输出设备 系统软件 软件系统 应用软件

中央处理器(CPU) 内(主)存储器 外(辅助)存储器 随机存储器(RAM) 只读存储器(ROM)

计 算 机 系 统

操作系统、标准程序库、服务性程序、语言 处理程序、数据库管理系统、网络软件等 专家系统、 科学计算、 数据处理、 工程设计、 事务管理、过程控制等程序

图 1 计算机系统结构示意图 计算机硬件又称为“冯·诺依曼结构” (如图 1 所示) 。由五个部分组成:输入设备、输 出设备、存储器、运算器、控制器。其中计算机中央处理器(CPU)由运算器和控制器组 成;输入、输出设备(I/O 设备)又被人们称为外围(部)设备。 计算机软件又可分为系统软件和应用软件两大类。 计算机存储容量以字节为单位,它们是:字节 B(1Byte=8bit) 、千字节(1KB=1024B) 、 兆字节(1MB=1024KB)、千兆字节(1GB=1024MB) 外存又称辅助存储器,它容量更大,常用的外部存储器有软盘、硬盘、光盘、磁带。 运算器:对信息进行加工处理的部件。它在控制器的控制下与内存交换信息,负责进行 各类基本的算术运算和与、或、非、比较、移位等各种逻辑判断和操作。此外,在运算 器中还有能暂时存放数据或结果的寄存器。 控制器:是整个计算机的指挥中心。它对指令进行分析、判断,发出控制信号,使计算 机的有关设备协调工作,确保系统自动运行。

2.计算机的工作原理

计算机的基本原理是存贮程序和程序控制。 即预先要把指挥计算机如何进行操作的指令 序列(称为程序)和原始数据通过输入设备输送到计算机内存储器中。每一条指令中明 确规定了计算机从哪个地址取数,进行什么操作,然后送到什么地址去等步骤。 程序与数据一样存贮,按程序编排的顺序,一步一步地取出指令,自动地完成指令规定 的操作是计算机最基本的工作原理。 这一原理最初是由美籍匈牙利数学家冯· 诺依曼于 1945 年提出来的,故称为冯·诺依曼原理。
By-SHBF 10

NOIP 基础知识要点一

3. 计算机软件系统:可分为系统软件和应用软件两大类。 ·系统软件:用来支持应用软件的开发和运行的,主要是操作系统软件,如: DOS、Windows95/98/2000、Unix、Linux、WindowsNT; ·应用软件:为了某个应用目的而编写的软件,主要有文字处理软件、电子表格软件、 数据库管理软件等。

3、中央处理器的组成
中央处理器简称 CPU,由控制器、运算器 组成。 运算器及控制器的基本功能:运算器是计 算机进行算术和逻辑运算的部件, 控制器是整 个计算机中统一指挥和控制计算机各部件进 行工作的控制中心。

4、运算器
运算器是负责对数据进行算术运算或逻辑 运算的部件。运算器由算术逻辑单元(ALU)、累 加器、状态寄存器、通用寄存器组等组成。如图: 算术逻辑运算单元、 累加器和通用寄存器的位 数决定了 CPU 的字长。

5、控制器
是计算机的指令执行部件,其工作是取指令、 解释指令以及完成指令的执行。 控制器由指令指针寄存器、 指令寄存器、控制 逻辑电路和时钟控制电路等组成。 指令指针寄存器(IP)用于 产生及存放一条待取指令的地址。 指令寄存器用于存放指令。指令从内存取出后放入指令寄存器。

6、寄存器
寄存器数量增多可以提高 CPU 运行速度, 但是不能太多, 太多会使地址编码和指令长度变长, 增加复杂度。由累加器、通用寄存器组、状态寄存器、指令寄存器、地址寄存器、其他寄存器等 组成。

7、指令基本格式
单目运算:操作码 地址码 二目运算:操作码 第一地址 第二地址

8、指令的执行过程
1、CPU 发出指令地址 2、读取指令 3、指令送指令寄存器 4、指令译码 5、按指令操作码执行 6、形成下条要执行的指令的地址
By-SHBF 11

NOIP 基础知识要点一

9、时钟周期
一个指令执行的时间称为指令周期 计算机完成一个操作(如读取指令等)所需 时间称为总线周期 计算机中最基本的时间单位是时钟周期,有 CPU 的主频决定。

(四)存储器系统
1、存储器体系:

2、主存储器

1、特点:容量小、读写速度快、价格高 2、编址方式:存储容量与地址线条数相对应,64M 的存储器至少需要 26 跟地址线 26 (2 =64M) 注:我们目前的计算机大都是 32 位,也就是地址线条数有 32 条,所以其支持的最大内 存容量为 4G 3、分类: ① 随机存储器(RAM):就是我们通常称的内存,主要参数是存储容量和工作频率。 例如:一条 64M×8 的内存条表示该内存条有 64M 个单元,每个单元 8 位。 ② 只读存储器(ROM):只能读不能写,一般用于存放计算机启动所需的最基本程序。 ③ 缓冲存储器(Cache):速度最快,一般集成于 CPU 中。 3、寄存器也是存储器,cpu 内部的存储单元,数量有限,但速度快,分通用寄存器和特殊 功能寄存器(比如 pc,sp 等)。不同的处理器有不同的寄存器配置方案。 4、辅助存储器

1、磁带:顺序存储,一般只用在小型机以上的计算机中,用作数据备份。
2、U 盘: 3、硬盘:硬盘由多个盘面组成一个柱形结构,其原来跟软盘类似,但是磁道更多。 4、光盘:利用光信号读取或写入的存储器。 ① CD-ROM:只读,容量 650MB 左右,一倍速为 150KB/s ② DVD-ROM:只读,容量 4.7GB 左右,一倍速为 1200KB/s ③ CD-RW、DVD-RW:可擦写的光盘,但必须专门的刻录机。

(五)输入输出(I/O)系统
(1)I/O 接口 1、显卡:分辨率、颜色数决定显示效果和所需显存 例如:显示分辨率为 1280×1024 的 32 位真彩色,所需显卡显存最少为 1280×1024×32÷8 = 5MB 2、硬盘接口: ① IDE、EIDE

By-SHBF

12

NOIP 基础知识要点一

② Ultra DMA ③ SCSI ④ SATA 3、串行口 4、并行口:通常接针式打印机 5、USB 接口:通用串行总线 (2) 输入设备、输出设备 显示器的有关知识 1、屏幕尺寸:15 寸、17 寸、19 寸等 2、点间距:屏幕上象素与象素之间的距离,决定了显示器能显示的最大分辨率。 越小表示 能显示的最大分辨率越大。 打印机:针式打印机、喷墨打印机、激光打印机。 激光打印机速度最快,针式打印机可以打印票据。 (3)系统总线 分类:数据总线、地址总线、控制总线 总线标准:ISA 总线、PCI 局部总线、MCA 总线

(六)软件系统
计算机软件可分为系统软件和应用软件两大类。 ·系统软件:1、操作系统软件,如: DOS、Windows95/98/2000、Unix、Linux、WindowsNT; 2、数据库系统:MySQL 、SQL Server 、 Oracle 、 Foxpro 3、计算机语言系统,如:PASCAL、C 系列、 ·应用软件:为了某个应用目的而编写的软件,主要有文字处理软件、电子表格软件、 数据库管理软件、网络应用软件等。 如:即时通信软件:A. 网易泡泡 B. MSN Messenger C. Google Talk D. QQ 计算机中软件以文件的形式存储在计算机的存储器中。文件可以是文本文档、图片、程 序等等。文件通常具有三个字母的文件扩展名,用于指示文件类,各种文件的后缀名: 可执行文件:com、exe 压缩文件:zip、RAR 图像图形文件:bmp、gif、jpg、psd 文本文件:txt 声音文件:wav、mp3 影像文件:avi、mpeg、mov、swf 其他常见文件:bat、sys、tmp、doc、xls、htm、?? 下列哪个软件属于操作系统软件( ) 。 A. Microsoft Word B. Foxmail C. WinRAR D. Red Hat Linux 下列哪个不是数据库软件的名称( D ) 。 A. MySQL B. SQL Server C. Oracle D. 金山影霸 E. Foxpro

三、计算机网络基础
(一)计算机网络的相关定义
By-SHBF 13

NOIP 基础知识要点一

计算机网络是以各种通信设备和传输介质将处于不同位置的多台独立计算机连接起来, 并在相应网络软件的管理下实现多台计算机之间信息传递和资源共享的系统。 简单的说计算机网络指相互连接的独立自主的计算机的集合。 网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。 1、 TCP/IP: 用于网络的一组通讯协议。 包括 IP(Internet Protocol)和 TCP(Transmission Control Protocol)。 TCP/IP是一组协议,包括上百个各种功能的协议,其中TCP 和IP是最核心的两个协议。 TCP/IP 协议把Internet网络系统描 述成具有四个层次功能的网络模型。 (1) 链路层:这是TCP/IP 结构 的第一层,也叫网络接口层,其功能 是提供网络相邻节点间的信息传输以 及网络硬件和设备驱动。 (2) 网络层:(IP协议层)其 功能是提供源节点和目的节点之间的 信息传输服务,包括寻址和路由器选 择等功能。 (3) 传输屋:(TCP 协议)其 功能是提供网络上的各应用程序之间 的通信服务。 (4) 应用层:这是TCP/IP最高 层,其功能是为用户提供访问网络环 境的手段,主要提供FTP、TELNET、GOPHER等功能软件。 IP协议适用于所有类型网络。 TCP 协议则处理IP协议所遗留的通信问题, 为应用程序提 供可靠的通信连接,并能自动适应网络的变化。TCP/IP 目前成为最为成功的网络体系结构 和协议规范。 2.网络的发展 计算机网络的发展过程大致可以分为三个阶段: 远程终端联机阶段:主机—终端 计算机网络阶段:计算机—计算机 Internet 阶段: Internet 3.网络的主要功能: (1)资源共享 (2)信息传输 (3)分布处理 (4)综合信息服务 (二)计算机网络的分类 ·按网络的规模及覆盖范围分:,可分为局域网(Local Area Network,LAN)、广

域网(Wide Area Network,WAN)和城域网(Metropolitan Area Network, MAN)。
·按网络的拓扑结构分: ①总线型拓扑结构。 ②星型拓扑结构。 ③环型拓扑结构。 ④树型拓扑结构。 ·按传输介质:有线网、无线网
By-SHBF 14

NOIP 基础知识要点一

(三)网络的基本应用: 1、远程登录、 2、文件传输、 3、电子邮件 E-mail 的地址是由用户使用的网络服务器在 Internet 上的域名地址决定的,它的格式 是:username@host.domain username : 用户名 host: 机器名 domain:域名 通常 Internet 上的个人用户不能直接接收电子邮件,而是通过申请 ISP 主机的一个电子 信箱,由 ISP 主机负责电子邮件的接收。一旦有用户的电子邮件到来,ISP 主机就将邮件移 到用户的电子信箱内, 并通知用户有新邮件。 因此, 当发送一条电子邮件给一另一个客户时, 电子邮件首先从用户计算机发送到 ISP 主机,再到 Internet,再到收件人的 ISP 主机,最后 到收件人的个人计算机 电子邮件在发送与接收过程中都要遵循 SMTP、POP3 等协议,这些协议确保了电子邮 件在各种不同系统之间的传输。其中,SMTP 负责电子邮件的发送,而 POP3 则用于接收 Internet 上的电子邮件。 4、万维网

(四)计算机网络的组成
从逻辑功能上分为两部分:通信子网和用户资源子网。 · 通信子网: 负责信息通信, 由一些专用的节点交换机和连接这些节点的通信链路组成。 通信子网分两种类型:点对点通信子网和广播式通信子网; ·用户资源子网:负责全网的信息处理,包括主机和其他信息资源设备。 (五)IP 地址和域名 1.IP 地址 I P 地址:所有 Interet 上的计算机都必须有一个 Internet 上唯一的编号作为其在 Internet 的标识,这个编号称为 I P 地址。 IP 地址是一个 3 2 位二进制数,即四个字节,为方便起见,通常将其表示为 w. x . y. z 的形式。其中 w、x、y、z 分别为一个 0~2 5 5 的十进制整数,对应二进制表示法中 的一个字节。这样的表示叫做点分十进制表示。 例某台机器的 I P 地址为: 11001010 011100010 01000000 00000010 则写成点分十进制表示形式是: 2 0 2 . 1 1 4 . 6 4 . 2 IPV4:IPv4,是互联网协议(Internet Protocol,IP)的第四版,也是第一个被广泛使用, 构成现今互联网技术的基石的协议。 IPV6:IPv6 是 IETF(互联网工程任务组,Internet Engineering Task Force)设计的用于 替代现行版本 IP 协议(IPv4)的下一代 IP 协议。目前 IP 协议的版本号是 4(简称为 IPv4) , 它的下一个版本就是 IPv6。IPV6 地址长度为 128 比特,地址空间增大了 2 的 96 次方倍 2.域名: 网络是基于 TCP/IP 协议进行通信和连接的,每一台主机都有一个唯一的标识固 定的 IP 地址,以区别在网络上成千上万个用户和计算机。IP 地址用二进制数来表示, 每个 IP 地址长 32 比特,由 4 个小于 256 的数字组成,数字之间用点间隔,例如 100.10.0.1 表示一个 IP 地址。由于 IP 地址是数字标识,使用时难以记忆和书写,因 此在 IP 地址的基础上又发展出一种符号化的地址方案,来代替数字型的 IP 地址。每 一个符号化的地址都与特定的 IP 地址对应,这样网络上的资源访问起来就容易得多 了。这个与网络上的数字型 IP 地址相对应的字符型地址,就被称为域名。
By-SHBF 15

NOIP 基础知识要点一

域名的构成:以一个常见的域名为例说明,baidu 网址是由二部分组成,标号―baidu‖ 是这个域名的主体,而最后的标号―com‖则是该域名的后缀,代表的这是一个 com 国 际域名,是顶级域名。而前面的 www.是网络名, 为 www 的域名。

我国的域名体系也遵照国际惯例,包括类别域名和行政区域名两套。 类别域名是指前面的六个域名,分别依照申请机构的性质依次分为: ac --- 科研机构 com --- Commercial organizations, 工、商、金融等企业 edu --- Educational institutions 教育机构 gov --- Governmental entities 政府部门 mil --- Military ,军事机构 net --- Network operations and service centers, 互联网络、接 入网络的信息中心(NIC)和运行中心(NOC) org --- Other organizations,各种非盈利性的组织 cn hk (六)常见缩写
TCP/IP 网络传输控制协议 HTTP 超文本协议 FTP 是英文 File Transfer Protocol 的缩写,文件传输协议 Pop3 邮局协议 TELNET 虚拟终端协议—远程登录 BBS:电子公告板 Web

ADSL: ADSL(Asymmetrical Digital Subscriber Loop)技术, 即非对称数字用户环路技术,
就是利用现有的一对电话铜线, 为用户提供上、 下行非对称的传输速率(带宽): 上行(从 用户到网络)为低速的传输,可达 640Kbps;下行(从网络到用户)为高速传输,可达 7Mbps。 DIY: Do It Yourself 的首字母缩写,自己动手制作的意思,硬件爱好者也被俗称 DIYer. 是 OEM 是英文 Original Equipment Manufacturer 的缩写,意思是原设备制造商。 ID 是英文 IDentity 的缩写,ID 是身份标识号码的意思. URL 是英文 Uniform Resoure Locator 的缩写,即统一资源定位器,它是 WWW 网页的地 址,如 http://www.qq.com BPS 位/秒,衡量调制解调器速度的单位。 ISP:网络服务运营商 www:万维网 (七)HTML 语言和网页制作 1、HTML 语言:Hypertext Markup Language,称为超文本标记语言。 HTML 标记的基本格式:<标记> 页面内容 </标记> 开始标记:<html> 标题(Heading)是通过 <h1> - <h6> 等标签进行定义的。数字是标题的级别

By-SHBF

16

NOIP 基础知识要点一

如:<h1>大家好!</h1> 段落标记:是通过 <p> 标签进行定义的。 颜色标记:<body bgcolor=green>

超级链接是网页的核心,链接标记:<a href='链接地址'>显示内容</a>
如:<a href="http://www.w3school.com.cn">This is a link</a> 图像是通过 <img> 标签进行定义的 <img src="w3school.jpg" width="104" height="142" /> <title>页头标题 例: <html> <head> <title>Hwllo!</title> </head> <body bgcolor=green> <div align="center"> <font color=yellow> <h1>大家好!</h1> </font> <a href="http://www.noi.cn">欢迎来到 NOI</a> </div> </body> </html>

2、网页制作工具 FRONTPAGE
Dreamweaver Flash

Fireworks--是 Macromedia 公司网页设计“三剑客”之“火焰”,它以处理网页图 片为特长,并可以轻松创作 GIF 动画。
photoshop 图像处理软件

(八)信息安全
计算机安全(computer security)是指防范与保护计算机系统及其信息资源在生存过程 中免受蓄意攻击、人为失误和自然灾害等引起的损失和破坏。 计算机病毒是人类自己想像和发明出来的, 它是一种特殊的程序, 有着与生物病毒极为 相似的特点。一是寄生性,它们大多依附在别的程序上面。二是隐蔽性,它们是悄然进入系 统的,人们很难察觉。三是潜伏性,它们通常是潜伏在计算机程序中,只在一定条件下才发 作的。四是传染性,它们能够自我复制繁殖,通过传输媒介蔓延。五是破坏性,轻则占用一

By-SHBF

17

NOIP 基础知识要点一

定数量的系统资源,重则破坏整个系统。 20 世纪 50、60 年代,黑客(hacker)曾是编程高手的代名词。后来,黑客成为一个独特 的群体,他们通过各种渠道交流技艺,不少人以攻击计算机及其网络系统为乐趣。黑客们的 胆大妄为已经给社会造成了很大的影响, 一些黑客已经蜕变为威胁社会安全的罪犯。 要防止 “黑客”攻击,主要方法是加强安全措施,例如设置防火墙(见图 3.1.1) 。防火墙是一种 计算机设备,它设置在内部网络与外部网络之间,起一个隔离的作用,既可以阻止外部信息 非法进入内部系统,也可以阻止内部人员非法访问外部系统。

例题 计算机病毒传染的必要条件是( B ) 。 A)在内存中运行病毒程序 B)对磁盘进行读写操作 D) 复制文件 C)在内存中运行含有病毒的程序

计算机病毒是(B ) A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 计算机病毒的特点是( C ) A. 传播性、潜伏性、易读性与隐蔽性 C. 传播性、潜伏性、破坏性与隐蔽性

B. 破坏性、传播性、潜伏性与安全性 D. 传播性、潜伏性、破坏性与易读性

一台计算机如果要利用电话线上网, 就必须配置能够对数字信号和模拟信号进行相互转换的 设备,这种设备是( A ) 。 A. 调制解调器 B. 路由器 C. 网卡 D. 网关 E. 网桥

第二部分

数据结构

简单的解释: 相互之间存在一种或多种特定关系的数据元素的集合。 数据间的联系有逻 辑关系、存储联系,通常的数据结构指的是逻辑结构。数据结构通常有如下四种关系: (1) 集合结构 (2)线性结构 (3)树形结构 (4)图状结构 一、 线性表(一)――N 个数据元素的有限序列 (1) 12 (2) 13 (3) 15 (4) 22 20 当在这种线性表中插入一个数据元素时,需要顺序移动后续的元素以“腾”出某个合适 的位置放置新元素。删除元素呢?
By-SHBF 18

(5) 34

(6) 38

(7) 43

(8)

NOIP 基础知识要点一

二、线性表(二)――链表 插入新元素的时候只需要改变指针所指向的地址。

☆ 二维数组与线性表 如果某一线性表,它的每一个数据元素分别是一个线 性表, 这样的二维表在数据实现上通常使用二维数组。 二维数组的一个形象比喻—— m * n 的队列方块 ☆ 数组地址计算问题 题目描述:已知 N*(N+1) / 2 个数据,按行的顺序存入 数组 b[1],b[2],?中。第一个下标表示行,第二个下标 表示列。若 aij (i>=j ,j=1,2,?,,n)存于 b[k]中,问:k,i,j 之间的关系如何表示? 三、栈的定义及其运算
1、栈的定义

堆栈(Stack)可以看成是一种―特殊的‖线性表,这种线性表上 的插入和删除运算限定在表的某一端进行的。 (1)通常称插入、删除的这一端为 栈顶 (Top) ,另一端称为 栈底 (Bottom) 。 (2)当表中没有元素时称为空栈。 (3)栈为后进先出(Last In First Out)的线性表,简称为 LIFO 表。 栈的修改是按后进先出的原则进行。 每次删除 退栈) ( 的总是当前栈中"最新"的元素, 即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。 图中元素是以 a1,a2,…,an 的顺序进栈,退栈的次序却是 an,an-1,…,a1。
2、栈的基本运算 (1)InitStack(S) 初始化操作,设定一个空栈 S。 : (2)EmptyStack(S) 判空栈操作,若 S 为空栈,则返回 TRUE,否则返回 FALSE。 : (3)FullStack(S) 判栈满。若 S 为满栈,则返回 TRUE,否则返回 FALSE。 : 注意: 该运算只适用于栈的顺序存储结构。 (4)Push(S,e) 进栈。若栈 S 不满,在栈顶插入一个元素 e,栈顶位置由 top 指针指出。 : (5)Pop(S) 退栈。若栈 S 非空,则将 S 的栈顶元素删去,并返回该元素。 : (6)GetTop(S) 取栈顶元素。若栈 S 非空,则返回栈顶元素,但不改变栈的状态。 : (7)ClearStack(S) 置栈空操作,已知 S 为栈,不论操作之前的栈是否为空栈,本操作的 :

结果都是将 S 置为空栈。 (8)CurrentStack(S) 求当前栈中元素的个数。 : (9)DestroyStack(S) 销毁 S 栈。 : 3、栈的应用 (1) 表达式的计算 表达式的二种形式

By-SHBF

19

NOIP 基础知识要点一

1、中缀表达式:运算符放在两个运算对象中间,如:(2+1)*3; 2、后缀表达式(逆波兰表示法) :运算符紧跟在两个操作数之后,实现无括号和无优先 处理,只须从左到右完成计算。如:表达式(2+1)*3 表示为后缀表达式为 2 1 + 3 *; 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。 我们把运算符和界限符统称为算符,它们构成的集合命名为 OP。根据上述三条运算规则, 在运算的每一步中, 任意两个相继出现的算符 θ1 和 θ2 之间的优先关系至多是下面三种关系 之一; θ1<θ2 θ1 的优先权低于 θ2 θ1=θ2 θ1 的优先权等于 θ2 θ1>θ2 θ1 的优先权高于 θ2

例:利用算法 EvaluteExpression 对算术表达式 3*(7-2)求值,操作过程如下所示:

(2) 子程序嵌套调用 在各种程序设计语言中都有子程序(或称函数、过程)调用功能。一个子程序还可以调 用另一子程序。图 3.5(a)展示的是由主程序开始的三层嵌套调用关系。

主函数 main 调函数 func1 时需记下返回地址 R,func1 调用 func2 需记下返回地址 S? , func2 调用 func3 时需记下返回地址 T。func3 执行结束时返回 func2 的地址 T,? 依次返回 到 func1 的地址 S,最终返回到 main 的地址 R。? 在编译软件内就设立一个栈专用于存放返

By-SHBF

20

NOIP 基础知识要点一

回地址, 在嵌套调时返回地址一一入栈, 调用结束时返回地址一一出栈, 如图 3.5(b)所示。 这是一个典型的先进后出结构 1、递归调用 所谓递归是指:若在一个函数、过程或者数据结构定义的内部,直接(或间接)出现 定义本身的应用,则称它们是递归的,或者是递归定义的。 递归是一种强有力的数学工具,它可使问题的描述和求解变得简洁和清晰。 递归算法常常比非递归算法更易设计, 尤其是当问题本身或所涉及的数据结构是递归定 义的时候,使用递归算法特别合适。 递归方法思路: 第一步骤(递归步骤) :将规模较大的原问题分解为一个或多个规模更小、但具有类似 于原问题特性的子问题。 即较大的问题递归地用较小的子问题来描述, 解原问题的方法同样 可用来解这些子问题。 第二步骤: 确定一个或多个无须分解、 可直接求解的最小子问题 (称为递归的终止条件) 。 【例】非负整数 n 的阶乘可递归定义为:

与之相应的函数框架是: function fac(n:integer):integer begin if ( (n=0) or (n=1) ) then fac:=1 else fac=n*fac(n-1); end; 在此函数中可理解为求 n!用 fac(n)来表示,那么 fac(n-1)就表示求(n-1)!。图 3.6(a)展示 了递归调用中执行情况。 从图 3.6(a)可以看到 fac 函数共被调用 5 次, fac(5)、 即 fac(4)、 fac(3)、 fac(2)、fac(1)。其中 fac(5)main 函数调用的,其余 4 次是在 fac 函数中调用的。在某一层递 归调用时,并未立即得到结果,而是进一步向深度递归调用。直到最内层函数执行 n=1 或 n=0 时,fac(n)才有结果。然后再一一返回时,不断得到中间结果,直到回到主程序就可得 到 n!的最终结果。

调用时把处在调用层的不同 n 值入栈, 返回时再一一出栈参加计算。 存放不同 n 值的栈 如图 3.6(b)所示。当然这里也用到了返回地址栈,在此不再重复。 练习:1、编号分别为 1~4 的 4 辆列车进入一个栈式结构的站台。可使得开出车站列车的 次序为 2431,如何进行进出操作 ② 将 8-(3+2*6)/5+4 表示为后缀表达式

四、队列

By-SHBF

21

NOIP 基础知识要点一

1.队列的特点:
队列也是一种线性表, 对于它所有的插入都在队列的一端进行, 所有的删除都在另一端 进行,进行删除的一端叫队列的―头‖(front),进行插入的一端叫队列的―尾‖(rear),其操作特 点是―先进先出‖。 (FIFO, First In First Out)

2.队列的基本操作:
(1)队列的插入 enq(q,x):在队列 q 中插入一个值为 x 的元素,也称为进队; (2)队列的删除 deq(q):从队列 q 中删除一个元素,也称为出队; (3)读队头元素 front(q,x): 将队列 q 中头部元素的值读 到 x 中;

3、 循环队列
头指针指向队列中队头元素的前一个位置,尾指针指示队 尾元素在队列中的当前位置。

五、树及其应用
1、树的定义
树是由 n (n >= 0)个结点组成的有限集合。如果 n = 0,称为空树;如果 n > 0,则 (1)有一个特定的称之为根(root)的结点,它只有直接后继,但没有直接前驱; (2)除根以外的其它结点划分为 m (m >=0)个互不相交的有限集合 T0, T1, ?, Tm-1, 每个集合又是一棵树,并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直 接前驱,但可以有 0 个或多个直接后继。

结点(node):各元素及其子树的分支 结点的度(degree):子树的数目 分支(branch)结点:度不为 0 的结点 叶(leaf)结点:度为 0 的结点 子女(child)、双亲(parent)结点:如 B、C、D 为 A 的子女,A 是 B、C、D 的双亲 兄弟(sibling)、祖先(ancestor)、子孙(descendant)结点:EF 为兄弟,L 的祖先是 EBA, 结点所处层次(level) 树的高度(depth):树的最大层次数 树的度(degree):各结点度的最大值

2、二叉树 (Binary Tree)
一棵二叉树是结点的一个 有限集合,该集合或者为空,或 者是由一个根结点加上两棵分 别称为左子树和右子树的、 互不 相交的二叉树组成。

二叉树的五种基本形态

二叉树的性质 性质 1 :若二叉树的层次从 0 开始, 则在二叉树的第 i 层最多有 2i 个结点。(i>=0)
By-SHBF 22

NOIP 基础知识要点一

性质 2 :高度为 k 的二叉树最多有 2k+1-1 个结点。(k >=1) 性质 3 : 任何一棵二叉树, 如果其叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则 对 有 n0=n2+1 两种特殊的二叉树: 满二叉树(Full Binary Tree) 完全二叉树(Complete Binary Tree)

3、二叉树的抽象数据表示
数组表示

链表表示

4、二叉树遍历(Binary Tree Traversal)
所谓树的遍历, 是按某种次序访问树中的结点, 求每个结点访问一次且仅访问一次。 就 要 其目标是通过完整而有规则的遍历方法, 得对非线性的二叉树结构能获得其中各结点信息 使 的一个线性排列。 现设访问根结点记作 V 、访问根的左子树记作 L 、访问根的右子树 记作 R 则可能的遍历次序有 6 种:前序:VLR/VRL 中序:LVR/RVL 后序:LRV/RLV 1、中根遍历 (Inorder Traversal) 中根遍历二叉树的方法是:左-根-右 右图所示树的中根遍历结果: a + b * c - d - e / f 2、前序遍历 (Preorder Traversal) 前根遍历二叉树的方法是:根-左-右 遍历结果: - + a * b - c d / e f 3、后根遍历 (Postorder Traversal) 后根遍历二叉树的方法是:左-右-根 如右图所示树的遍历结果:a b c d - * + e f / -

5、哈夫曼树
1. 哈夫曼树的基本概念

By-SHBF

23

NOIP 基础知识要点一

哈夫曼树( Huffman )又称最优二叉树,是一类带权路径长度最短的树,有着广泛的 应用。 在讨论哈夫曼树之前首先需要弄清楚关于路径和路径长度的概念。 树中两个结点之间的 路径由一个结点到另一结点的分支构成。 两结点之间的路径长度是路径上分支的数目。 树的 路径长度是从根结点到每一个结点的路径长度之和。 设一棵二叉树有 n 个叶子结点, 每个叶子结点拥有一个权值W 1 , 2 ,...... W n , W 从根结点到每个叶子结点的路径长度分别为 L1 , L2......Ln ,那么树的带权路径长度为每 个叶子的路径长度与该叶子权值乘积之各。 通常记作 WPL = L k. W k 。 为了直观其见, 在图中把带权的叶子结点画成方形,其他非叶子结点仍为圆形。请看图 6.21 中的三棵二叉 树以及它们的带权路径长。

(a) wpl=38 (b) wpl=49 (c) wpl=36 图具有不同带权路径长度的二叉树
注意:

这三棵二叉树叶子结点数相同,它们的权值也相同,但是它们的 wpl 带权路径长各不 相同。图 6.21(c)wpl 最小。它就是哈曼树,最优树。哈夫曼树是,在具有同一组权值的叶 子结点的不同二叉树中,带权路径长度最短的树。也称最优树。 2. 哈夫曼树的构造 对于已知的一组叶子的权值W 1 ,W 2...... ,W n ①首先把 n 个叶子结点看做 n 棵树(仅有一个结点的二叉树) ,把它们看做一个森林。 ②在森林中把权值最小和次小的两棵树合并成一棵树, 该树根结点的权值是两棵子树权值之 和。这时森林中还有 n-1 棵树。 ③重复第②步直到森林中只有一棵为止。此树就是哈夫曼树。现给一组 (n=4) 具体的权值 2 , 4 , 5 , 8 ,下边是构造具体过程:

图 哈夫曼树构造过程 图(a) 是一个拥有 4 棵小树的森林,图(b) 森林中还有 3 子棵树,图(c) 森林中剩下 2 棵 树,图(d) 森林只有一棵树,这棵树就是哈夫曼树。这里或许会提出疑问, n 个叶子构成 的哈夫曼树其带权路径长度唯一吗?确实唯一。 树形唯一吗?不唯一。 因为将森林中两棵权 值最小和次小的子棵合并时,哪棵做左子树,哪棵做右子树并不严格限制。图 6.22 之中的

By-SHBF

24

NOIP 基础知识要点一

做法是把权值较小的当做左子树 , 权值较大的当做右子树。如果反过来也可以,画出的树 形有所不同,但 WPL 值相同。为了便于讨论交流在此提倡权值较小的做左子树 , 权值较 大的做右子。 A. 哈夫曼树的应用
(1) 用于最佳判断过程。

在考查课记分时往往把百分制转换成优( x>=90 ) 、良 (80<x<90) 、中 (70<=x80) 、 及格 (60<=x<70) 、不及格 (x<60) 五个等级。若不考虑学生考试分数的分布概率,程序判 定过程很容易写成图 6.23(a) 所示的方法。我们知道,一般来讲学生考分大多分布在 70 至 80 分之间,从图 6.23(a) 可看出这种情的 x 值要比较 2 至 3 次才能确定等级。而学生中 考试不及格的人数很少, x 值比较一次即可定等级。能否使出现次数多的在 70 至 80 分 之间的 x 值比较次数减少些, 而使很少出现的低于 60 分的 x 值比较次数多一些, 以便提 高程序的运行效率呢?假设学生成绩对于不及格、及格、中等、良好和优秀的分布概率分别 为 5 %, 15 %, 40 %, 30 %, 10 %,以它们做为叶子的权值来构造哈夫曼树,如 图 6.23(b) 所示。此时带权路径长最短,其值为 205 %。它可以使大部分的分数值经过较 少的比较次数得到相应的等级。但是,事务往往不是绝对的,此时每个判断柜内的条件较为 复杂, 比较两次, 反而降低运行效率。 所以我们采用折衷作法, 调整后得图 6.23(c) 判定树。 它更加切合实际。

(2) 用于通信编码

在通信及数据传输中多采用二进制编码。 为了使电文尽可能的缩短, 可以对电文中每个 字符出现的次数进行统计。 设法让出现次数多 的字符的二进制码短些, 而让那些很少出现的 字符的二进制码长一些。 假设有一段电文, 其 中用到 4 个不同字符A,C,S,T,它们 在电文中出现的次数分别为 7 , 2 , 4 , 5 。把 7 , 2 , 4 , 5 当做 4 个叶子的 权值构造哈夫曼树如图 6.24(a) 所示。 在树中 令所有左分支取编码为 0 ,令所有右分支取 编码为 1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列,就得这个

By-SHBF

25

NOIP 基础知识要点一

叶子结点所代表的字符的二进制编码,如图 6.24(b) 所示。 这些编码拼成的电文不会混淆, 因为每个字符的编码均不是其他编码的前缀, 这种编码 称做前缀编码。 关于信息编码是一个复杂的问题, 还应考虑其他一些因素。 比如前缀编码每个编码的长 度不相等,译码时较困难。还有检测、纠错问题都应考虑在内。这里仅对哈夫曼树举了一个 应用实例。 6、二叉排序树
1. 二叉排序的定义和特点

定义:二叉排序树 (binary sort tree) 或是空树;或是非空树。 对于非空树: ①若它的左子树不空,则左子树上各结点的值均小于它的根结点的值; ②若它的右子树不空,则右子树上各结点的值均大于等于它的根结点的值; ③它的左、右子树又分别是二叉排序树。 例如如图所示为一棵二叉排序树, 这种二叉排序树具有左小右大的特点。 根据需要也可以构 造左大右小的二叉排序树。

特点:

对二叉排序树进行中序遍历,可得到一个由小到大的序例。例如对图 6.18 的二叉排序树进 行中根遍历,则得到序列: 2 , 3 , 6 , 8 , 9 , 10 , 15 , 18 , 19 。 *2. 建立二叉排序树的算法 建立二叉排序树,实质上是不断地进行插入结点的操作。设有一组数据:K ={k 1 k 2 ,…… k n } ,将它们一一输入建成二叉排序树。 建立二叉排序树的思路 : ①让 k 1 做根; ②对于 k 2 ,若 k 2 <k 1 ,令 k 2 做 k 1 的左孩子;否则令 k 2 做 k 1 的右孩子; ③对于 k 3 , k 4 ,……, k n ,重复第四步,直到 k n 处理完为止。 在建立过程之中,每输入一个数据元素就插入一次。现把插入一个结点的算法单独编写,而 在建立过程中对其进行调用。 在二叉排树上插入结点不需要遍历二叉树, 仅需从根结点出发, 走一条根到某个具有空 子树的结点的路径,使该结点的空指针指向被插入结点,使被插入结点成为新的叶子结点。 习题 1、一棵二叉树的中根遍历为 DBGEACHFI 后根遍历为 DGEBHIFCA ,画出此二叉树。 2、已知某二叉树的前根遍历为 ABDEGCFHIJ,中根遍历为 DBGEAHFIJC,试给出它的后 根遍历。 3、按中根遍历二叉树所得的结点序列为 ABC,试给出所有可能的二叉树。 4、对于表达式(a+b)*(c+d)*(e-f),要求 (1)给出它的中根二叉树; (2)给出它的前缀表达式; (3) 给出它的后缀表达式。

By-SHBF

26

NOIP 基础知识要点一

六、图的问题
1、图的定义:图( Graph )是由一个用线或边连接在一起的顶点或节点的集合。是一 种比线性表和树更为复杂的非线性数据结构, 可称为图状结构或网状结构, 前面讨论的线性 表和树都可以看成是图的简单情况。 图 G 由两个集合 V 和 E 组成,记为:G=(V,E) 其中: V 是顶点的有穷非空集合,E 是 V 中顶点偶对(称为边)的有穷集。 通常,也将图 G 的顶点集和边集分别记为 V(G)和 E(G)。E(G)可以是空集。若 E(G)为 空,则图 G 只有顶点而没有边。 2、有向图 如图所示每条边都是有方向的,则称 G 为有向图(Digraph)。

(1)有向边的表示 有向边又称为弧,通常用尖括弧表示一条有向边, <v,w> 表示从顶点 v 到 w 的一 段弧, v 称为边的始点 ( 或尾顶点 ) , w 称为边的终点, ( 或头顶点 ), <v,w> 和 <w,v> 代表两条不同的弧。 【例】<vi,vj>表示一条有向边,vi 是边的始点(起点),vj 是边的终点。 注意: <vi,vj>和<vj,vi>是两条不同的有向边。 (2)有向图的表示 【例】上面7.1图中 G2是一个有向图。图中边的方向是用从始点指向终点的箭头表示的, 该图的顶点集和边集分别为: 顶点集 V={v 1 ,v 2 ,v 3 } 弧集 E={< v 1 ,v 2 >,<v 1 ,v 3 >,< v 2 ,v 3 >,<v 3 ,v 2 >} 。 注意: <v 3 ,v 2 > 与<v 3 ,v 2 > 表示两条不同的边。 3.无向图 如图7.1G1中所示的每条边都是没有方向的,则称 G 为无向图(Undigraph)。 (1)无向边的表示 通常用圆括号表示无向边, (v,w) 表示顶点 v 和 w 间相连的边。在无向图中 (v,w) 和 (w,v) 表示同一条边,如果顶点 v,w 之间有边 (v,w) ,则 v,w 互称为邻接点。 【例】无序对(vi,vj)和(vj,vi)表示同一条边。 (2)无向图的表示
By-SHBF 27

NOIP 基础知识要点一

【例】上面7.1图中的 G1是无向图,它们的顶点集和边集分别为: 顶点集:V={v 1 ,v 2 ,v 3 ,v 4 } 边集:E={(v 1 ,v 2 ), (v 1 ,v 3 ), (v 1 ,v 4 ), (v 2 ,v 3 ), (v 3 ,v 4 )} 注意: (v 2 ,v 1 ) 与( v 1 ,v 2 )表示同一条边, (v 2 ,v 3 ) 与 (v 3 ,v 2 ) 也表示同一条边,等等。 3.图 G 的顶点数 n 和边数 e 的关系 (1)若 G 是无向图,则0≤e≤n(n-1)/2 恰有 n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph) (2)若 G 是有向图,则0≤e≤n(n-1)。 恰有 n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。 注意: 完全图具有最多的边数。任意一对顶点间均有边相连。 4.对图的讨论中我们对图作一些限制: 第一,图中不能有从顶点自身到自身的边(即自身环) ,就是说不应有形如(vx,vx)的边或 <vx,vx> 的弧。 第二,两个顶点 vt 和 vu 之相关联的边不能多于一条。 5、图的基本术语 (1)完全图(complete graph): 完全无向图: 有 n 个顶点无向图,若有 n(n-1)/2条边,则称。如图7.3所示的图 G1 完全有向图: 有 n 个顶点有向图,若有 n(n-1)条边,则称。如图7.3所示的图 G2

(2)权(weight): 边(弧)上具有与它相关的系数,称之为权。 这些权可以表示从一个顶点到另一个顶 点的距离、花费的代价、所需的时间和次数等。这种带权图也被称为网络(network)。 (3)邻接顶点(adjacent vertex): 在无向图中,若(u,v)是 E(G)中的一条边,则称 u 和 v 互为邻接顶点。 边(u,v)依附于顶点 u 和 v。 边<u,v>与顶点 u 和顶点 v 相关联。 (4)顶点的度(Degree) ①无向图中顶点 v 的度(Degree) 无向图中顶点 v 的度(Degree)是关联于该顶点的边的数目,记为 D(v)。

By-SHBF

28

NOIP 基础知识要点一

【例】图 G2中顶点 v1的度为3 ②有向图顶点 v 的入度(InDegree) 有向图中,以顶点 v 为终点的边的数目称为 v 的入度(Indegree),记为 ID(v)。 ③有向图顶点 v 的出度(Outdegree) 有向图中,以顶点 v 为始点的边的数目,称为 v 的出度(Outdegree),记为 OD(v) 【例】上图 G1中顶点 v2的出度为2 注意: 1.有向图中,顶点 v 的度定义为该顶点的入度和出度之和,即 D(v)=ID(v)+OD(v)。 【例】上图 G1中顶点 v2的人度为 l,出度为2,则度为3。 2.无论有向图还是无向图,顶点数 n、边数 e 和度数之间有如下关系:

(5)路径 无向图的路径:在无向图 G 中,若存在一个顶点序列 vp,vi1,vi2,…,vim,vq,使得(vp,vi1), (vi1,vi2),…,(vim,vq)均属于 E(G),则称顶点 vp 到 vq 存在一条路径(Path)。 有向图的路径: 在有向图 G 中, 路径也是有向的,它由 E(G)中的有向边<vp,i1>, i1, i2>, v <v v …, <vim,vq>组成。 路径长度 对于不带权的图,路径长度是指路径上边的数目。 对于带权图,路径长度是指路径上各边的权之和。如下图所示的有向图中,路 径 <v1,v2,v3>的长度为2。

简单路径 对于一路径(v1, v2,…, vm),若路径上各顶点均不相同,则称这条路径为简单路径。 【例】在下图 G2中顶点序列 vl,v2,v3,v4是一条从顶点 v1到顶点 v4的长度为3的简单路径 【例】在下图 G2中,顶点序列 v1,v2,v4,v1,v3是一条从顶点 v1到顶点 v3的长度为4的路 径,但不是简单路径; 简单回路或简单环(Cycle) 起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。 【例】上图 G2中,顶点序列 v1,v2,v4,v1是一个长度为3的简单环 【例】有向图 G1中,顶点序列 v1,v2,v1是一长度为2的有向简单环。 有根图和图的根 在一个有向图中,若存在一个顶点 v,从该顶点有路径可以到达图中其它所有顶点,

By-SHBF

29

NOIP 基础知识要点一

则称此有向图为有根图,v 称作图的根。 6、连通图与连通分量 若从顶点 v i 到顶点 v j (i ≠ j) 有路径,则 v i 和 v j 是连通的。 如果无向图中任意两个顶点 v i 和 v j 都是连通的,则称无向图是连通的。无向图中极大连 通子图称为连通分量。 【例】下图中的 G 3 有两个连通分量,见图 7.4(a) 。

图7.3

对于有向图来说,图中任意一对顶点 v i 和 v j (i ≠ j) 均有从 v i 到 v j 及从 v j 到 v i 的有向路径,则称该有向图是强连通的。有向图中的极大强连通子图称为该有向图的强 连 通分 量。图 7.1G 2 不是强连通的,但它有一个强连通分量,见图 7.4(b) 。 7、最短路径 所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径 可能不止一条,如何找到一条路径似的沿此路径上各边的权值总和(称为路径长度)达到最 小。 8、拓扑排序 一个无环的有向图称为无环图(Directed Acyclic Graph) ,简称 DAG 图。 所有的 工程或者某种流程都可以分为若干个小的工程或者阶段,称这些小的工程或阶段为―活动‖。 这些子程序之间存在一定的约束, 其中某种子工程的开始必须在另一些子工程完成之后。 因 此 DAG 图表示一个工程,其中有向边表示约束关系。这种有向图必须是无环的。如果出现

By-SHBF

30

NOIP 基础知识要点一

了环(有向环) ,那么向前递推,环路上的任一子工程开始的先决条件必然是自己,显然矛 盾的。 如果设计出这样的工程图, 工程无法进行。 拓扑排序就是测试一个工程能否顺利进行。 【例】 计算机专业的学生必须完成一系列规定的专业基础课和专业课才能毕业, 这个过程就 可以被看成是一个大的工程, 而活动就是学习每一门课程。 我们不妨把这些课程的名称与相 应的代号列于表 7.2 。
表 7.2 计算机专业的学生必须完成课程的名称与相应代号

课程代号 C1 C2 C3 C4 C5 C6 C7 C8

课程名 程序设计导论 数值分析 数据结构 汇编语言 自动机理论 人工智能 计算机原理

先行课程名 无 C 1 , C 14 C 1 , C 14 C 1 , C 13 C 15 C3 C4

课程代号 C9 C 10 C 11 C 12 C 13 C 14

课程名 算法分析

先行课程名 C3 C3,C4 C 10 C 11 无 C 13 C 14

高级语言 编译系统 操作系统 解析几何 微积分 线性代数

计算机图形学 C 3 ,C 4 ,C 10 C 15

若以图中的顶点来表示活动,有向边表示活动之间的优先关系,则这样的有向图称为 AOV(Activity On Vertex network) 网。在 AOV 网中,若从顶点 v i 到顶点 v j 之间存在一 条有向路径,称顶点 v i 是顶点 v j 的前趋,或者称顶点 v j 是顶点 v i 的后继。若 是图
中的弧,则称顶点 v i 是顶点 v j 的直接前趋,顶点 v j 是顶点 v i 的直接后继。 这种优先关系可以用图 7.18 所示的有向图来表示。其中,顶点表示课程,有向边表示前提 条件,若课程 v i 为课程 v j 的前行课,则必然存在有向边 &v i ,v j > 。

对 AOV 网进行拓扑排序的方法和步骤如下:

1. 从 AOV 网中选择一个没有前趋的顶点(该顶点的入度为 0 )并且输出它; 2. 从网中删去该顶点,并且删去从该顶点发出的全部有向边; 3. 重复上述两步,直到剩余网中不再存在没有前趋的顶点为止。
操作的结果有两种:

一种是网中全部顶点都被输出,这说明网中不存在有向回路,拓扑排序成功; 另一种是网中顶点未被全部输出,剩余的顶点均有前趋顶点,这说明网中存在有向回路,不 存在拓扑有序序列。 【例】图 7.19 给出了一个 AOV 网实施上述步骤的例子。
By-SHBF 31

NOIP 基础知识要点一

这样得到一个拓朴序列 v 1 , v 6 , v 4 , v 3 , v 2 , v 5 。 为了避免在每一步选入度为零的顶点时重复扫描表头数组, 利用表头数组中入度为零的 顶点域作为链栈域,存放下一个入度为零的顶点序号,零表示栈底,栈顶指针为 top ,寄 生在表头数组的入度域中的入度为零的顶点链表如图 7.20(b) 所示。

9、关键路径 若在带权的有向图中,以顶点表示事件,以有向边表示活动,边上的权值表示活动的开 销(如该活动持续时间) ,则此带权的有向图称为边表示活动的网 (Activity on Edge Network) ,简称 AOE 网。 【例】图 7.21 是一个网。其中有 9 个事件 v 1 , v 2 , … , v 9 ; 11 项活动 a 1 , a 2 , … , a 11 。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如 v 1 表示整个 工程开始, v 9 表示整个工程结束。 V 5 表示活动 a 4 和 a 5 已经完成,活动 a 7 和 a 8 可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动 a 1 需要 6 天时间 可以完成。

(1)AOV 网具有的性质

⒈ 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。

By-SHBF

32

NOIP 基础知识要点一

⒉ 只有在进入某一顶点的各有向边所代表的活动都已经结束,该顶点所代表的事件才能发 生。 ⒊ 表示实际工程计划的 AOE 网应该是无环的,并且存在唯一的入度过为 0 的开始顶点 和唯一的出度为 0 的完成顶点。
(2)由事件 v j 的最早发生时间和最晚发生 时间的定义 , 可以采取如下步骤求得关键 活动 :

1. 从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早 发生时间。 Ve(k)=max{ve(j)+dut(<j,k>)} ( 7.1 ) j ∈ T 其中 T 是以顶点 v k 为尾的所有弧的头 顶点的集合 (2 ≤ k ≤ n) 。 如果得到的拓朴有序序列中顶点的个数小于网中顶点个数 n ,则说明网中有环,不能求出 关键路径,算法结束。 2. 从完成顶点 v n 出发,令 vl(n)=ve(n) ,按逆拓朴有序求其余各顶点的允许的最晚发生 时间 : vl(j)=min{vl(k)-dut(<j,k>)} k ∈ S 其中 S 是以顶点 v j 是头的所有弧的尾顶点集合 (1 ≤ j ≤ n-1) 。 3. 求每一项活动 a i (1 ≤ i ≤ m) 的最早开始时间 e(i)=ve(j) ;最晚开始时间 l(i)=vl(k)-dut(<j,k>) 。若某条弧满足 e(i)=l(i) ,则它是关键活动。
(3) 求出 AOE 网中所有关键活动后, 只要删去 AOE 网中所有的非关键活动, 即可得到 AOE 网的关键路径。

这时从开始顶点到达完成顶点的所有路径 都是关键路径。一个 AOE 网的关键路径可 以不止一条, 如图 7.21 的 AOE 网中有二条关键路径, ( v 1 , v 2 , v 5 , v 7 , v 9 ) 和 ( v 1 , v 2 , v 5 , v 8 , v 9 ) 它们的路径长度都是 16 。如图所示。
注意:

并不是加快任何一个关键活动都可以缩短整个工程完成的时间, 只有加快那些包括在所 有的关键路径上的关键活动才能达到这个目的。只有在不改变 AOE 网的关键路径的前提 下,加快包含在关键路径上的关键活动才可以缩短整个工程的完成时间 部分初赛数据结构相关 NOIP 试题 一.选择题: 1. 一个向量第一个元素的存储地址是 100,每个元素的长度是 2,则第 5 个元素的地址是( ) A)110 B)108 C) 100 D) 109 2.已知数组中 A 中,每个元素 A(I,J)在存贮时要占 3 个字节,设 I 从 1 变化到 8,J 从 1 变化到 10,分配内存时是从地址 SA 开始连续按行存贮分配的。试问:A(5,8)的起始 地址为( ) A.SA+141 B. SA+180 C. SA+222 D. SA+225 3.要使 1...8 号格子的访问顺序为:8、 6、 7、 1、 2、 5、 3、 4,则下图中的空格中应填入( 1 4 A) 6 2 6 B) O C) 7 3 1 D) 3 4 -1 5 6 5 7 3 8 2 ) 。

By-SHBF

33

NOIP 基础知识要点一

4.线性表若采用链表存贮结构,要求内存中可用存贮单元地址( ) A.必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可 5.下列叙述中,正确的是( ) A.线性表的线性存贮结构优于链表存贮结构 B.队列的操作方式是先进后出 C.栈的操作方式是先进先出 D. 二维数组是指它的每个数据元素为一个线性表的线性表 6.已知一个栈的入栈顺序是 1,2,3,?,n,其输出序列为 P1,P2,P3,?,Pn,若 P1 是 n,则 Pi 是( ) A)i B)n-1 C)n-i+1 D)不确定 7.以下哪一个不是栈的基本运算( ) A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈 8.设找 S 和队列 Q 的初始状态为空,元素 e1,e2,e3,e4,e5,e6 依次通过钱 S,一个元素出栈后 即进入队列 Q,若出队的顺序为 e2,e4,e3,e6,e5,e1,则钱 S 的容量至少应该为( A) 2 B) 3 C) 4 D) 5 ) 。

9.某个车站呈狭长形,宽度只能容下一台车,并且只有一个出口。一直某时刻该车站状态为 空,从这一时刻开始的出入记录为:“进,出,进,进,出,进,进,进,出,出,进, 出”。假设车辆入站的顺序为 1,2,3??,则车辆的顺序为( )。 A.1,2,3,4,5 B.1,2,4,5,7, C.1,3,5,4,6 D.1,3,5,6,7 E.1,3,6,5,7 10. 设栈S的初始状态为空, 元素a, b, c, d, e, f, g依次入栈, 以下出栈序列不可能出现的有 ) ( 。 A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a 11.表达式(1+34)*5-56/7 的后缀表达式为( ) 。 A) 1+34*5-56/7 B) -*+1 34 5/56 7 C) 1 34 +5*56 7/D) 1 34 5* +56 7/- E) 1 34+5 56 7-*/ 12.一棵二叉树的高度为h,所有结点的度为0或为2,则此树最少有( )个结点 A)2h-1 B)2h-1 C)2h+1 D)h+1 13.按照二叉树的定义,具有 3 个结点的二叉树有( A) 3 14. B) 4 C) 5 D) 6 ) 。 D) 2h E) 2h-1 ) 种。

一个高度为 h 的二叉树最小元素数目是( A) 2h+1 B) h C) 2h-1

15.满二叉树的叶节点个数为 N,则它的节点总数为( )。 A.N B.2*N C.2*N-1 D.2*N+1 E.2N-1 16.二叉树 T 已知其前序遍历序列为 1243576, 中序遍历序列为 4215736, 则其后序遍历为 ) ( 。 A.4257631 B.4275631 C.4275361 D.4723561 E.4526371 17.完全二叉树的结点个数为4 * N + 3,则它的叶结点个数为( )。 A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2 18.二叉树T的宽度优先遍历序列为A B C D E F G H I,已知A是C的父结点,D 是G 的父 结点,F 是I 的父结点,树中所有结点的最大深度为3(根结点深度设为0),可知E的父结 点可能是( )。 A. A B. B C. C D. D E. F 19.无向图 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)}
By-SHBF 34

NOIP 基础知识要点一

对该图进行深度优先遍历,得到的顶点序列正确的是( ) 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 20.设有一个含有 13 个元素的 Hash 表(0~12),Hash 函数是:H(key)=key % 13,其中% 是求余 数运算。用线性探查法解决冲突,则对于序列(2、8、31、20、19、18、53、27),18 应放 在第几号格中( A) 5 B) 9 ) 。 C) 4 D) 0 ) 倍。

21.在一个有向图中,所有顶点的人度之和等于所有顶点的出度之和的( A) 1/2 B)1 C) 2 D) 4

22.假设我们用 d=(a1,a2,…,a5),表示无向图 G 的 5 个顶点的度数,下面哪(些)组 d 值合 理 ( )的。 A){5,4,4,3,1} D){5,4,3,2,1} B){4,2,2,1,1} E){2,2,2,2,2} C){3,3,3,2,2}

23. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点, 每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的所有边的权值综合 为( )。 A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 5 24.电线上停着两种鸟(A,B),可以看出两只相邻的鸟就将电线分为了一个线段。这些线 段可分为两类;一类是两端的小鸟相同;另一类则是两端的小鸟不相同。已知:电线两 个顶点上正好停着相同的小鸟,试问两端为不同小鸟的线段数目一定是( )。 A.奇数 B.偶数 C.不确定奇偶 25. 地面上有标号为 A、 C 的 3 根细柱, 在 A 柱上放有 10 个直径相同中间有孔的圆盘, 从 B、 上到下次依次编号为 1, 2, 3, ??,将 A 柱上的部分盘子经过 B 柱移入 C 柱, 也可以在 B 柱上暂存。如果 B 柱上的操作记录为:“进,进,出,进,进,出,出,进,进,出,进, 出,出”。那么, 在 C 柱上, 从下到上的盘子的编号为( )。 A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 26. 已知 7 个节点的二叉树的先根遍历是 1 2 4 5 6 3 7(数字为结点的编号,以下同), 后 根遍历是 4 6 5 2 7 3 1, 则该二叉树的可能的中根遍历是( ) A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 二.问题求解: 1. 已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为: CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序遍历的顺序为: 2. 设有一棵 k 叉树,其中只有度为 0 和 k 两种结点,设 n0,nk 分别表示度为 0 和度为 k 的结 点个数,试求出 n0,nk 之间的关系(n0=数学表达式,数学表达式仅含 nk,k 和数字) 3. 无向图 G 有 16 条边,有 3 个 4 度顶点、4 个 3 度顶点,其余顶点的度均小于 3,则 G 至少______个顶点。 4. 已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。

数据结构练习题
1、链表不具有的特点是( )

By-SHBF

35

NOIP 基础知识要点一

A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比 2、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采 用( )存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 3、若长度为 n 的线性表采用顺序存储结构,在其第 i 个位置插入一个新元素的算法的时间 复杂度为( )(1<=i<=n+1)。 2 A. O(0) B. O(1) C. O(n) D. O(n ) 4、在单链表指针为 p 的结点之后插入指针为 s 的结点,正确的操作是: ( ) 。 A.p^next=s;s^next=p^next; B. s^next=p^next;p^next=s; C.p^next=s;p^next=s^next; D. p^next=s^next;p^next=s; 5、具有 10 个叶结点的二叉树中有( )个度为 2 的结点, A.8 B.9 C.10 D.ll 6、一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是( ) A. 250 B. 500 C.254 D.505 E.以上答案都不对 7、有 n 个叶子的哈夫曼树的结点总数为( ) 。 A.不确定 B.2n C.2n+1 D.2n-1 8、有关二叉树下列说法正确的是( ) A.二叉树的度为 2 B.一棵二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 2 D.二叉树中任何一个结点的度都为 2 9、一个具有 1025 个结点的二叉树的高 h 为( ) A.11 B.10 C.11 至 1025 之间 D.10 至 1024 之间 10、一棵树高为 K 的完全二叉树至少有( )个结点 k k-1 k-1 k A.2 –1 B. 2 –1 C. 2 D. 2 11、一棵二叉树的前序遍历序列为 ABCDEFG,它的中序遍历序列可能是( ) A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG 12、 已知某二叉树的后序遍历序列 dabec, 中序遍历序列是 debac ,它的前序遍历是 ( ) 。 A.acbed B.decab C.deabc D.cedba 13、由 3 个结点可以构造出多少种不同的二叉树?( ) A.2 B.3 C.4 D.5 14、一个栈的输入序列为 123?n,若输出序列的第一个元素是 n,输出第 i(1<=i<=n)个 元素是( ) 。 A. 不确定 B. n-i+1 C. i D. n-i 15、一个栈的输入序列为 1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( ) 。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 16、输入序列为 ABC,可以变为 CBA 时,经过的栈操作为( ) A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 17、表达式 a*(b+c)-d 的后缀表达式是( )。 A.abcd*+B. abc+*dC. abc*+dD. -+*abcd 18、设栈 S 和队列 Q 的初始状态为空,元素 e1,e2,e3,e4,e5 和 e6 依次通过栈 S,一个 元素出栈后即进队列 Q,若 6 个元素出队的序列是 e2,e4,e3,e6,e5,e1 则栈 S 的容量至少 应该是( )。 A. 6 B. 4 C. 3 D. 2

By-SHBF

36

NOIP 基础知识要点一

19、数组 A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为 1000 的内存单元中,则元素 A[5,5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 20、设 G 是由 5 个顶点构成的完全图,则从 G 中删去( )边可以得到树。 A.6 B.5 C.8 D.4 21、设图 G 有 n 个结点,m 条边,且 G 中每个结点的度数不是 k,就是 k+1,则 G 中度数 为 k 的节点数是( ) A.n/2 B.n(n+1) C.nk-2m D.n(k+1)-2m 22、在有 n 个结点的连通图中,其边数( ) A.最多有 n-1 条 B.至少有 n-1 条 C.最多有 n 条 D.至少有 n 条 23、在一个无向图中,所有顶点的度数之和等于所有边数( )倍。 A.1/2 B.2 C.1 D.4 24、设有 33 盏灯,拟公用一个电源,则至少需有 5 插头的接线板数( ) 。 A.7 B.8 C.9 D.14 25、设简单连通无向图 G 有 9 条边,G 中有 4 个 3 度结点,2 个 1 度结点,其余结点度数为 2.求 G 中有多少个结点. 26、求下图中 A 到 F 的最短路径。

27、求右图的关键路径 28、给定权 1,4,9,16,25,36,49,64,81, 100,利用 Huffman 算法构造一棵最优二叉树,并求出其 W(T)。

第三部分 算法概述
一、什么是算法 算法是程序设计的精髓, 程序设计的实质就是构造解决问题的算法, 将其解释为计算机 语言。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计 算机解题的过程。 在这个过程中, 无论是形成解题思路还是编写程序, 都是在实施某种算法。 前者是推理实现的算法,后者是操作实现的算法。 一个算法应该具有以下五个重要的特征: 1. 有穷性: 一个算法必须保证执行有限步之后结束; 2. 确切性: 算法的每一步骤必须有确切的定义; 3. 输入:一个算法有 0 个或多个输入,以刻画运算对象的初始情况; 4. 输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的 算法是毫无意义的; 5.可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。 二、算法的表示方法
By-SHBF 37

NOIP 基础知识要点一

算法通常有三种表示方法:自然语言法、程序流程图法、程序法。 结构化程序设计三种程序结构的流程图(N-S 图)如下: 1.顺序结构 2.选择结构

3.循环结构 当型循环

直到型循环

三、算法的复杂性分析 算法的复杂性是算法效率的度量, 是评价算法优劣的重要依据。 一个算法的复杂性的高 低体现在运行该算法所需要的计算机资源的多少上面, 所需的资源越多, 我们就说该算法的 复杂性越高;反之,所需的资源越低,则该算法的复杂性越低。 计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复杂性有时间复杂 性和空间复杂性之分。 不言而喻, 对于任意给定的问题, 设计出复杂性尽可能低的算法是我们在设计算法时追求的 一个重要目标;另一方面,当给定的问题已有多种算法时,选择其中复杂性最低者,是我们 在选用算法适应遵循的一个重要准则。 因此, 算法的复杂性分析对算法的设计或选用有着重 要的指导意义和实用价值。 简言之,在算法学习过程中,我们必须首先学会对算法的分析,以确定或判断算法的优劣。 1.时间复杂性:是指 例 1:设一程序段如下(为讨论方便,每行前加一行号) (1) for i:=1 to n do (2) for j:=1 to n do (3) x:=x+1 ...... 试问在程序运行中各步执行的次数各为多少? 解答: 行号 次数(频度) (1) n+1 (2) n*(n+1) (3) n*n 2 可见,这段程序总的执行次数是:f(n)=2n +2n+1。在这里,n 可以表示问题的规模,当 n 趋向无穷大时,如果 f(n)的值很小,则算法优。作为初学者,我们可以用 f(n)的数量 2 级 O 来粗略地判断算法的时间复杂性,如上例中的时间复杂性可粗略地表示为 T(n)=O(n )。 算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式(n 为问题的规模,c 为一常 量): Ο (1)称为常数

By-SHBF

38

NOIP 基础知识要点一

Ο (logn)称为对数级 Ο (n)称为线性级 Ο (nc)称为多项式级 Ο (cn)称为指数级 Ο (n!)称为阶乘级 常见算法时间复杂度: O(1): 表示算法的运行时间为常量 O(n): 表示该算法是线性算法 O(㏒ 2n): 二分查找算法 O(n2): 对数组进行排序的各种简单算法,例如选择排序。 O(n3): 做两个 n 阶矩阵的乘法运算 O(2n): 求具有 n 个元素集合的所有子集的算法 O(n!): 求具有 N 个元素的全排列的算法

O(1)<O(㏒ 2n)<O(n)<O(n2)<O(2n)
2.空间复杂性: 一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间,就是 程序执行过程中由于需要所申请的内存空间, 即所“需”空间, 而非指程序所“占”空间指 的仅仅是代码长度,也就是你理解的占存储器空间 例 2:将一一维数组的数据(n 个)逆序存放到原数组中,下面是实现该问题的两种算法: 算法 1:for i:=1 to n do b[i]:=a[n-i+1]; for i:=1 to n do a[i]:=b[i]; 算法 2:for i:=1 to n div 2 do begin t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t end; 算法 1 的时间复杂度为 2n,空间复杂度为 2n 算法 2 的时间复杂度为 3*n/2,空间复杂度为 n+1 显然算法 2 比算法 1 优,这两种算法的空间复杂度可粗略地表示为 S(n)=O(n) 信息学比赛中,经常是:只要不超过内存,尽可能用空间换时间。时间第一。

四、基本程序及常用算法
求最大最小值 程序 1 const n=7; var a:array[1..n] of integer; i,j,k,:integer; begin for i:= 1 to n do read(a[i]); k:=1; for j:=2 to n do if a[j]<a[k] then k:=j; writeln(a(k); ) end. 程序 2 const n=7; var a:array[1..n] of integer; i,j,m:integer; begin for i:= 1 to n do read(a[i]); m:=a[1]; for j:=2 to n do if a[j]<m then m:=a[j]; writeln(m) ; end.

By-SHBF

39

NOIP 基础知识要点一

质数问题
判断质数的程序 Var x,i:integer; F:Boolean; Begin Readln(x) ; f:=true; For i:=2 to trunc(sqrt(x) )do If x mod i=0 then f:=false; If f=true then write( ‘YES’ ) else write( ‘NO’ ) End. 穷举法求质数 var n,i,j,k:integer; flag:boolean; begin readln(n);Write(2:5); for i:=3 to n do begin flag:=true; for j:=2 to round(sqrt(i)) do if i mod j=0 then flag:=flase; if flag then write(i:5); end; end. 程序 3、用筛法求出 30000 以内的全部素数,并按每行五个数显示。 const N=30000; Var a: array[1..n] of integer; i,j: integer; Begin a[1] := 0; For i:=2 to n do a[i]:=i; for i:=2 to Trunc(sqrt(N)) do if a[i]<>0 then for j := 2 to N div i do a[i*j]:= 0; t:=0; for i:=2 to N do if a[i]<>0 then Begin write(a[ i ]:5); inc(t); if t mod 5=0 then writeln end; readln End.

By-SHBF

40

NOIP 基础知识要点一

最大公约数问题
var m,n,i:integer; begin readln(m,n) if m>n then i:=n else i:=m; while not((m mod i=0)and (n mod i=0)) do i:=i-1; writeln(i); end. var m,n,r:integer; begin readln(m,n); r:=m; repeat r:=m mod n; m:=n; n:=r; until r=0; writeln(m); end.

排序算法

插入排序 选择排序 const n=7; const n=7; var a:array[1..n] of integer; var a:array[1..n] of integer; i,j,k,t:integer; i,j,k,t:integer; begin begin for i:= 1 to n do read(a[i]); for i:= 1 to n do read(a[i]); writeln; writeln; for i:=2 to n do for i:=1 to n-1 do begin begin k:=i; k:=a[i];j:=i-1; for j:=i+1 to n do while (k<a[j]) and (j>0) do if a[j]<a[k] then k:=j; begin a[j+1]:=a[j];j:=j-1 end; if k<>i then a[j+1]:=k; begin t:=a[i];a[i]:=a[k];a[k]:=t;end; end; end; for i:= 1 to n do write(a[i]:6); for i:= 1 to n do write(a[i]:6); writeln; end. end. 冒泡排序 冒泡排序又称交换排序其基本思想是:对相邻的关键字进行两两比较,如发现是反序的,则进 行交换,直到无反序的记录为止。 程序 1: program mppx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin for i:= 1 to n do read(a[i]); for i:=1 to n -1 do for j:=n downto i+1 do if a[j-1]<a[j] then begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t end;

By-SHBF

41

NOIP 基础知识要点一

for i:= 1 to n do write(a[i]:6); end. 程序 2: program mppx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; bool:boolean; begin for i:= 1 to n do read(a[i]); i:=1;bool:=true; while (i<n) and bool do begin bool:=false; for j:=n downto i+1 do if a[j-1]<a[j] then begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=true end; i:=i+1; end; for i:= 1 to n do write(a[i]:6); end.

快速排序:算法思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都
放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度 为 1, 处理结束. Var a:array[1..100] of integer; procedure sort(l,r:longint); var i,j,x,y:longint; begin i:=l;j:=r;x:=a[i]; repeat while (x<=a[j])and(i<j) do dec(j); {在右边找一个比 x 小的数} If (i<j) Then begin {已找到 a[j] > X} a[i] := a[j]; i:=i+1; end; {相当于交换 a[i]和 a[j]} while (a[i]<=x)and(i<j) do inc(i); {在左边找一个比 x 大的数} If (i<j) Then begin {已找到 a[i]〈 X} a[j] := a[i]; j:=j-1; end; {相当于交换 a[i]和 a[j]} until i=j; {循环后保证有 a[i]左边的数都比右边的小} a[i]:=x; if l<i-1 then sort(l,i-1); if i+1<r then sort(i+1,r); {递归继续排} end; 希尔排序 基本思想:将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。 序列分割方法:将相隔某个增量 h 的元素构成一个子序列。在排序过程中,逐次减小这个增

By-SHBF

42

NOIP 基础知识要点一

量,最后当 h 减到 1 时,进行一次插入排序或冒泡排序,排序就完成。 桶排序 桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有 序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。 各种排序算法的比较 1.稳定性比较 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的 选择排序、希尔排序、快速排序、堆排序是不稳定的 2.时间复杂性比较 2 插入排序、冒泡排序、选择排序的时间复杂性为 O(n ) 其它非线形排序的时间复杂性为 O(nlog2n) 线形排序的时间复杂性为 O(n); 3.辅助空间的比较 线形排序、二路归并排序的辅助空间为 O(n),其它排序的辅助空间为 O(1); 4.其它比较 插入、冒泡排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能达到较快的 速度。 反而在这种情况下,快速排序反而慢了。 当 n 较小时,对稳定性不作要求时宜用选择排序,对稳定性有要求时宜用插入或冒泡排序。 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。 当 n 较大时,关键字元素比较随机,对稳定性没要求宜用快速排序。 当 n 较大时,关键字元素可能出现本身是有序的,对稳定性有要求时,空间允许的情况下。 宜用归并排序。 当 n 较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序。 顺序查找 思想是:将查找值顺序逐个与结点值进行比较,相等即为查找成功,否则查找失败. 二分查找 基本思想:首先将结点按关键字排序,其次将查找值与中间位置的值比较,相等,查找成功;不 等,则中间数据大于或小于查找值,无论怎样查找将在一半的数据中查找。 程序: const n=100; type arr=array[1..n] of integer; var x1,i:integer; a:arr; place:integer; procedure search(r:arr;m,x:integer; var p:integer); var low,high,mid:integer; begin p:=0;low:=1;high:=m; while low<=high do begin mid:=(low+high) div 2; if x>r[mid] then low:=mid+1 else

By-SHBF

43

NOIP 基础知识要点一

if x<r[mid] then high:=mid-1 else begin p:=mid;exit;end; end; end; 枚举法 也称之为穷举法,是指从可能的集合中一一枚举各个元素,用题目给定的约束条件 判定哪些是无用的,哪些是有用的。能使命题成立者,即为问题的解 【程序举例】把一元钞票换成一分、二分、五分硬币(每种至少一枚) ,有哪些种换法? 【答案】461 种, 【参考程序】 var i,j,k,total:integer; begin total:=0; {总数设为0} for j:=1 to 49 do {j:二分硬币最多 49 枚} for k:=1 to 19 do {k:五分硬币最多 19 枚} if j*2+k*5<100 then begin writeln(i:3,j:3,k:3); inc(total); {总数加1} end; writeln(total); end. 贪心策略是:指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的 一种解题方法。 典型例题:背包问题: 有一个背包,背包容量是 M=150。有 7 个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品 重量 价值 A 35 10 B 30 40 C 60 30 D 50 50 E 40 35 F 10 40 G 25 30

递归算法: 一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函 数). 【题例】利用递归把一个十进制 x 转化为 n 进制。 终止条件:商为 0 递归式:x:=x div n (szzh:=szzh(x div n) ) 【参考程序】 Var X,n,y:integer; Function szzh(k:integer); Var a:0..17; Begin if x< >0 then begin a:=x mod n; szzh:=szzh(x div n); write(a);
By-SHBF 44

NOIP 基础知识要点一

end; end; begin readln(x,n); y:=szzh(x); end. 回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索. 在一般情况下可用递归函数来实现回溯法如下: procedure try(i:integer); var begin if i>n then 输出结果 else for j:=下界 to 上界 do begin if 可行{满足限界函数和约束条件} then begin 保存结果;try(i+1); 回溯;end; end; end; 说明: i 是递归深度;n 是深度控制,即解空间树的的高度; 可行性判断有两方面的内容:不满约束条件则剪去相应子树;若限界函数越界,也剪去相应 子树;两者均满足则进入下一层; 回溯算法的要点: (1)确定递归参数 (2)回溯终止、约束条件 (3)试探搜索中应用枚举,确定枚举范围 【题例】 中国象棋半张棋盘如下, 马自左下角往右上角跳。 现规定只许往右跳, 不许往左跳。 比如下图所示为一种跳行路线。编程输出所有的跳行路线,打印格式如下: <1> (0,0)—(1,2)—(3,3)—(4,1)—(5,3)—(7,2)—(8,4) 解:按象棋规则,马往右跳行的方向如下表和图所示:

By-SHBF

45

NOIP 基础知识要点一

y
方 向

x y

① 1 2

② 2 1

③ 2 -1

④ 1 -2

2 1 0 -1 -2

① ②
1 2

x

③ ④

4 3 2 1 0 1 2 3 4 5 6 7 8

按象棋规则,马往右跳行的方向如下表和图所示: 水平方向用 x 表示; 垂直方向用 y 表示。右上角点为 x=8, y=4, 记为(8, 4) ; 用数组 tt 存放 x 方向能成行到达的点坐标;用数组 t 存放 y 方向能成行到达的点坐标; ①以(tt(K), t(k))为起点,按顺序用四个方向试探,找到下一个可行的点(x1, y1); ②判断找到的点是否合理 (不出界),若合理,就存入 tt 和 t 中;如果到达目的就打印,否则 重复第?步骤; ③如果不合理,则换一个方向试探,如果四个方向都已试过,就退回一步(回溯),用未试过 的方向继续试探。重复步骤?; ④如果已退回到原点,则程序结束。 【程序】Const xx: array[1..4] of 1..2 =(1,2,2,1); yy: array[1..4] of -2..2=(2,1,-1,-2); Var p: integer; t, tt : array[0..10] of integer; procedure Prn(k: integer); Var i: integer; Begin inc(p); write(‘< ‘, p: 2, ’ > ‘, ’ ‘:4, ’0,0’); for i:=1 to k do write(‘— ( ‘, tt[ I ], ’ , ’, t[ I ], ’)’ ); writeln End; Procedure Sub(k: integer); Var x1, y1, i: integer; Begin for I:=1 to 4 do Begin x1:=tt[k-1]+xx[ i ]; y1:=t[k-1]+yy[ i ];

By-SHBF

46

NOIP 基础知识要点一

if not( (x1 > 8) or (y1 < 0) or (y1 > 4) ) then Begin tt[k]:=x1; t[k]=y1; if (y1=4) and (x1=8) then prn(k); sub(k+1); end; end; end; Begin p:=0; tt[0]:=0; t[0]:=0; sub(1); writeln( ‘ From 0,0 to 8,4 All of the ways are ’, p); readln end.

附录 2:历届全国竞赛试题

第九届分区联赛普及组初赛试题(03)
一. 选择一个正确答案代码(A/B/C/D/E), 填入每题的括号内(每题 1. 分, 30 分) 5 共 1.下列计算机设备中,既是输入设备,又是输出设备的是( )。 A)键盘 B)触摸屏 C)扫描仪 D)投影仪 E)数字化仪 2.下列分辨率的显示器所显示出的图像,最清晰的是( )。 A)800*600 B)1024*768 C)640*480 D)1280*1024 E)800*1000 3.下列说法中,正确的是( )。 A)在内存中,可执行程序用二进制码表示,源程序用八进制表示。 B)程序和数据在内存中都是用二进制码表示的。 C)内存中数据的存取是以二进制位为单位的。 D)中央处理器 CPU 执行的每条指令的长度都不同。 E)一般来说, 在计算机内部, 中文信息用十六进制表示, 英文信息用八进制表示。 4.下列说法中,错误的是( )。 A)程序是指令的序列,它有三种结构:顺序、分支和循环。 B)地址总线决定了中央处理器 CPU 所能访问的最大内存空间的大小。 C)中央处理器 CPU 内部有寄存器组,用来存储数据。 D)不同厂家生产的 CPU 所能处理的指令集不一定相同。 E)数据传输过程中不可能会出错。 5.CPU 访问内存的速度比访问下列哪个存储设备要慢( )。 A)寄存器 B)硬盘 C)软盘 D)磁带 E)光盘 6.下列电子邮件地址,正确的是( )。 A)wang@hotmail.com B)cai@jcc.pc.tool@rf.edu.jp C)162.105.111.22 D)ccf.edu.cn E)http://www.sina.com 7.数字图像文件可以用下列哪个软件来编辑( )。
By-SHBF 47

NOIP 基础知识要点一

A)画笔(Paintbrush) B)记事簿(Notepad) C)Recorder D)WinRAR E)MidiSoft 8.下列哪个软件不是操作系统软件的名字( )。 A)Windows XP B)DOS C)Linux D)OS/2 E)Arch/Info 9.下列哪个不是个人计算机的硬件组成部分( )。 A)主板 B)操作系统 C)电源 D)硬盘 E)软驱 10.图灵(Alan Turing)是( )。 A)美国人 B)英国人 C)德国人 D)匈牙利人 E)法国人 11.第一个给计算机写程序的人是( )。 A)Alan Mathison Turing B)Ada Lovelace C)John von Neumann D)John McCarthy E)Edsger Wybe Dijkstra 12.十进制数 2003 等值于二进制数( )。 A)11111010011 B)10000011 C)110000111 D)010000011l E)1111010011 13.运算式(2008)10-(3723)8 的结果是( )。 A) (-1715)10 B) (5)10 C) (-5)16 D) (111)2 E) (3263)8 14.下列关于程序语言的叙述,不正确的是( )。 A)编写机器代码不比编写汇编代码容易。 B)高级语言需要编译成目标代码或通过解释器解释后才能被 CPU 执行。 C)同样一段高级语言程序通过不同的编译器可能产生不同的可执行程序。 D)汇编代码可被 CPU 直接运行。 E)不同的高级语言语法略有不同。 15. 假设 A=true, B=false, C=true, D=true, 逻辑运算表达式 A∧B∨C∧D 的值是( )。 A)true B)false C)0 D)1 E)NULL 16.一个高度为 h 的二叉树最小元素数目是( )。 A)2h+l B)h C)2h-1 D)2h E)2h-l 17.已知队列(13,2,11,34,41,77,5,7,18,26,15),第一个进入队列的元素是 13,则第五个出队列的元素是( )。 A)5 B)41 C)77 D)13 E)18 18.下列关于文件的叙述,不正确的是( )。 A)一个可执行程序其实也是一个文件。 B)文件可大可小,大的文件一张软盘装不下。 C)一个文件夹下面可以有两个同名的文件,只要它们的大小不同就行了。 D)文件的创建日期和最新修改日期可以在资源管理器中看到。 E)某些文件的内容可以用记事本(Notepad)看到。 19.活动硬盘的容量比固定硬盘的容量( )。 A)大 B)小 C)相等 D)不一定大 E)大致相等 20.IP 地址是一个( )位二进制码。 A)8 B)16 C)32 D)64 E)12 二.问题求解(每题 5 分,共 10 分)

By-SHBF

48

NOIP 基础知识要点一

1.现在市场上有一款汽车 A 很热销,售价是 2 万美元。汽车 A 每加仑汽油可以行驶 20 英里。普通汽车每年大约行驶 12000 英里。油价是每加仑 1 美元。不久我公司就要推出新款 节油汽车 B,汽车 B 每加仑汽油可以行驶 30 英里。现在我们要为 B 制定价格(它的价格略高 于 A):我们预计如果用户能够在两年内通过节省油钱把 B 高出 A 的价钱弥补回来,则他们 就会购买 B,否则就不会购买 B。那么 B 的最高价格应为 万美元。 2.无向图 G 有 16 条边,有 3 个 4 度顶点、4 个 3 度顶点,其余顶点的度均小于 3,则 G 至少有 个顶点。 三.阅读程序(每题 8 分,共 32 分) 1.program Programl; var a,x,y,okl,ok2:integer; begin a :=100: x:=l0; y:=20; okl:=5: ok2:=0; if ((x>y) or ((y<>20) and (okl=0)) and (ok2<>0)) then a:=1 else if ((okl<>0) and (ok2=、0)) then a:=-1 else a:=0; writeln(a); end. 输出: 2.program Program2; var a,t:string; i,j:integer; begin a:=`morning`; j:= l; for i:=2 to 7 do if (a[j]<a[i])then j:= i; j:= j-1; for i:=1 to j do

By-SHBF

49

NOIP 基础知识要点一

write (a[i]); end. 输出: 3.program Program3; Var a,b,c,d,sum:longint; begin read (a,b,c,d); a:=a mod 23: b:=b mod 28; c:=c mod 33; sum:=a*5544+b* 14421+c*1288-d; sum:=sum+21252; sum:=sum mod 21252; if (sum=0)then sum:=21252; writeln(sum); end. 输入:283 102 23 320 输出: 4.program program4; var a: array[0..5] of integer; sum,n,max,i,j,k:integer; cover:array[0..22000]of boolean; begin read (a[5],a[4],a[3],a[2],a[1],a[0]); if ((a[5]=0) and (a[3]=0) and (a[1]=0)) then begin a[5]:=a[4];a[4]:=a[2]; a[3]:=a[0]; a[2]:=0 a[0]:=0; end: for i:=0 to 5 do if (a[i]>10) then a[i]:=10+(a[i] mod 2); sum:=0: for i:=0 to 5 do sum:=sum+a[i]*(6-i); if ((sum mod 2) <>0) then begin writeln(`Can``t be divided.`); Exit; End;
By-SHBF 50

NOIP 基础知识要点一

sum:=sum div 2; max:=0; cover[0]:=True; for i:=1 to sum*2 do cover[i]:=False; for i:=0 to 5 do begin j:=0; while (j<a[i])do begin for k:=max downto 0 do begin if (cover[k]) then cover[k+6-i]:=True;end; max:=max+6-i: j:=j+1; end; end; if (cover[sum]) then writeln (`Can be divided.`) else writeln(`can``t be divided.`); end. 输入:4 7 9 20 56 48 输入:1000 7 101 20 55 1 输入:2000 5 l 1 0 0 输出: 输出: 输出: 四、完善程序(第 l 空 2 分,其余每空 3 分共 28 分) 1.一元二次方程 题目描述: 方程 ax^2+bx+c=0,要求给出它的实数解. 输 入: 三个实数:a,b,c,是方程的三个系数(a≠0). 输 出: 如果无实数解,则输出"No solution"; 如果有两个相等的实数解,则输出其中一个,四舍五入到小数点后面 3 位; 如果有两个不等的实数解, 则解与解之间用逗号隔开, 同样要四舍五入到小数点后 3 位。 输入样例: l 2 1 输出样例: -1.000 程 序: program Program41; var a,b,c,m:real; begin read (a,b,c); m:=b*b -4*a*c; if ( ① )then begin write ( ② :0:3);
By-SHBF 51

NOIP 基础知识要点一

write( ` , ` ); write ((-1*b-sqrt(m))/(2*a):0: ③ ); end else if ( ④ )then write( ⑤ ) else begin write (`No solution`); end end. 2.翻硬币 题目描述: 一摞硬币共有 m 枚,每一枚都是正面朝上。取下最上面的一枚硬币,将它 翻面后放回原处。然后取下最上面的 2 枚硬币,将他们一起翻面后再放回原处。再取 3 枚, 取 4 枚??直至 m 枚。然后再从这摞硬币最上面的一枚开始,重复刚才的做法。这样一直做 下去,直到这摞硬币中的每一枚又都是正面朝上为止。例如,m 为 1 时,翻两次即可。m 为 2 时,翻 3 次即可;m 为 3 时,翻 9 次即可;m 为 4 时,翻 11 次即可;m 为 5 时,翻 24 次即 可;?;m 为 30 时,翻 899 次即可;? 输 入:仅有的一个数字是这摞硬币的枚数 m,0<m<1000。 输 出:为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数。 输入样例: 30 输出样例: 899 程 序: program Programl; var m:integer; function solve (m:integer):integer; vat i,t,d:integer; flag:boolean; begin if (m=1)then so1ve:= ① else begin d:=2*m+1;t:= 2; i:= 1; flag:=False; repeat if (t=1)then begin solve:= ② ;flag:=True; end else if ( ③ )then begin solve:=i*m-1;flag:=True; end else t:= ④ ; i:=i+1;

By-SHBF

52

NOIP 基础知识要点一

until flag; end end; begin read (m); if ((m>0) and (m<1000)) then writeln ( ⑤ ); end.

By-SHBF

53

NOIP 基础知识要点一

第十届全国青少年信息学奥林匹克联赛初赛试题(04)
一.选择一个正确答案代码(A/B/C/D/E),填入每题的括号内 (每题 1.5 分, 共 30 分) 美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是( ) 。 A. 提出理想计算机的数学模型,成为计算机科学的理论基础。 B. 是世界上第一个编写计算机程序的人。 C. 提出存储程序工作原理,并设计出第一台具有存储程序功能的计算机 EDVAC。 D. 采用集成电路作为计算机的主要功能部件。 E. 指出计算机性能将以每两年翻一番的速度向前发展。 2. 下列哪个不是 CPU(中央处理单元) ) ( 。 A. Intel Itanium B. DDR SDRAM C. AMD Athlon64 D. AMD Opteron E. IBM Power 5 3. 下列网络上常用的名字缩写对应的中文解释错误的是( ) 。 A. WWW(World Wide Web) :万维网。 B. URL(Uniform Resource Locator) :统一资源定位器。 C. HTTP(Hypertext Transfer Protocol) :超文本传输协议。 D. FTP(File Transfer Protocol) :快速传输协议。 E. TCP(Transfer Control Protocol) :传输控制协议。 4. 下面哪个部件对于个人桌面电脑的正常运行不是必需的( ) 。 A. CPU B. 图形卡(显卡) C. 光驱 D. 主板 E. 内存 5. 下列哪个软件属于操作系统软件( ) 。 A. Microsoft Word B. 金山词霸 C. Foxmail D. WinRAR E. Red Hat Linux 6. 下列哪个不是计算机的存储设备( ) 。 A. 文件管理器 B. 内存 C. 高速缓存 D. 硬盘 E. U 盘 7. 下列说法中错误的是( ) 。 A. CPU 的基本功能就是执行指令。 B. CPU 访问内存的速度快于访问高速缓存的速度。 C. CPU 的主频是指 CPU 在 1 秒内完成的指令周期数。 D. 在一台计算机内部,一个内存地址编码对应唯一的一个内存单元。 E. 数据总线的宽度决定了一次传递数据量的大小,是影响计算机性能的因素之一。 8. 彩色显示器所显示的五彩斑斓的色彩,是由红色、蓝色和( )色混合而成的。 A. 紫 B. 白 C. 黑 D. 绿 E. 橙 9. 用静电吸附墨粉后转移到纸张上,是哪种输出设备的工作方式( ) 。 A. 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪 10. 一台计算机如果要利用电话线上网,就必须配置能够对数字信号和模拟信号进行相互 转换的设备,这种设备是( ) 。 A. 调制解调器 B. 路由器 C. 网卡 D. 网关 E. 网桥 11. 下列哪个不是数据库软件的名称( ) 。 A. MySQL B. SQL Server C. Oracle D. 金山影霸 E. Foxpro 12. 下列哪个程序设计语言不支持面向对象程序设计方法( ) 。 A. C++ B. Object Pascal C. C D. Smalltalk E. Java 1. 13. 由 3 个 a,1 个 b 和 2 个 c 构成的所有字符串中,包含子串“abc”的共有( )个。

By-SHBF

54

NOIP 基础知识要点一

A. 20 B. 8 C. 16 D. 12 E. 24 14. 某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站 状态为空,从这一时刻开始的出入记录为: “进,出,进,进,出,进,进,进,出,出, 进,出” 。假设车辆入站的顺序为 1,2,3,??,则车辆出站的顺序为( ) 。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7 15. 二叉树 T,已知其前序遍历序列为 1 2 4 3 5 7 6,中序遍历序列为 4 2 1 5 7 3 6,则其后 序遍历序列为( ) 。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1 16. 满二叉树的叶结点个数为 N,则它的结点总数为( ) 。 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1 17. 十进制数 2004 等值于八进制数( ) 。 A. 3077 B. 3724 C. 2766 D. 4002 E. 3755 18. (2004)10 + (32)16 的结果是( ) 。 A. (2036)10 B. (2054)16 C. (4006)10 D. (100000000110)2 E. (2036)16 19. 在下图中,从顶点( )出发存在一条路径可以遍历图中的每条边一次,而且仅遍历 一次。

A. A 点 B. B 点 C. C 点 D. D 点 E. E 点 20. 某大学计算机专业的必修课及其先修课程如下表所示: 课程代 号 课程名 称 先修课 程 C0 高等数 学 C1 程序设计 语言 C2 离散数 学 C0, C1 C3 数据结 构 C1, C2 C4 编译技 术 C3 C5 操作系 统 C3, C7 C6 普通物 理 C0 C7 计算机原 理 C6

请你判断下列课程安排方案哪个是不合理的( ) 。 A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1, C2, C3, C4, C6, C7, C5 C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4 E. C0, C1, C2, C3, C6, C7, C5, C4

二.问题求解 (每题 5 分,共 10 分) 1. 一个家具公司生产桌子和椅子。现在有 113 个单位的木材。每张桌子要使用 20 个单

位的木材,售价是 30 元;每张椅子要使用 16 个单位的木材,售价是 20 元。使用已有的木 材生产桌椅(不一定要把木材用光) ,最多可以卖 1. 元钱。

2. 75 名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知 其中 20 人这三种东西都玩过,55 人至少玩过其中的两种。若每样乘坐一次的费用是 5
By-SHBF 55

NOIP 基础知识要点一

元,游乐场总共收入 700,可知有

名儿童没有玩过其中任何一种。

三.阅读程序 (每题 8 分,共 32 分) 1.program program1; var a, b, c, d, e: integer; begin a := 79; b := 34; c := 57; d := 0; e := -1; if (a < c) or (b > c) then d := d + e else if (d + 10 < e) then d := e + 10 else d := e - a; writeln(d); end. 输出: 。

2.program program2; var i, j: integer; str1, str2: string; begin str1 := 'pig-is-stupid'; str2 := 'clever'; str1[1] := 'd'; str1[2] := 'o'; i := 8; for j := 1 to 6 do begin str1[i] := str2[j]; inc(i); end; writeln(str1); end. 输出: 。

3.program progam3; var u: array [0..3] of integer; a, b, c, x, y, z: integer; begin read(u[0], u[1], u[2], u[3]); a := u[0] + u[1] + u[2] + u[3] - 5; b := u[0] * (u[1] - u[2] div u[3] + 8); c := u[0] * u[1] div u[2] * u[3]; x := (a + b + 2) * 3 - u[(c + 3) mod 4]; y := (c * 100 - 13) div a div (u[b mod 3] * 5);

By-SHBF

56

NOIP 基础知识要点一

if((x+y) mod 2 = 0) then z := (a + b + c + x + y) div 2; z := (a + b + c – x - y) * 2; writeln(x + y - z); end 输入:2 5 7 4 输出: 。

4.program program4; var c: array[1..3] of string[200]; s: array[1..10] of integer; m, n, i: integer; procedure numara; var cod: boolean; i, j, nr: integer; begin for j := 1 to n do begin nr := 0; cod := true; for i := 1 to m do if c[i, j] = '1' then begin if not cod then begin cod := true; inc(s[nr]); nr := 0; end end else begin if cod then begin nr := 1; cod := false; end else inc(nr); end; if not cod then inc(s[nr]); end; end; begin readln(m, n); for i := 1 to m do readln(c[i]); numara; for i := 1 to m do if s[i] <> 0 then write(i, ' ', s[i], ' '); end. 输入: 3 10 1110000111 1100001111 1000000011

By-SHBF

57

NOIP 基础知识要点一

输出:



四、完善程序 (前 4 空,每空 2 分,后 5 空,每空 4 分,共 28 分) 1.三角形内切圆的面积 题目描述: 给出三角形三边的边长,求此三角形内切圆(如下图所示,三角形的内切圆是和三角形 三边都相切的圆)的面积。

输入: 三个正实数 a、b、c(满足 a+b>c,b+c>a,c+a>b), 表示三角形三边的边长。 输出: 三角形内切圆的面积,结果四舍五入到小数点后面 2 位。 输入样例: 3 4 5 输出样例: 3.14 程序: program program1; var a, b, c, r, s, t: real; begin read(a, b, c); s := ( ① ) / 2; t := ② (s * (s - a) * (s - b) * (s - c)); r := t / s; writeln(3.1415927 * r * end. ③ : 0 : ④ );

2.Joseph 题目描述: 原始的 Joseph 问题的描述如下:有 n 个人围坐在一个圆桌周围,把这 n 个人依次编号 为 1,…,n。从编号是 1 的人开始报数,数到第 m 个人出列,然后从出列的下一个人重新 开始报数,数到第 m 个人又出列,…,如此反复直到所有的人全部出列为止。比如当 n=6, m=5 的时候,出列的顺序依次是 5,4,6,2,3,1。 现在的问题是:假设有 k 个好人和 k 个坏人。好人的编号的 1 到 k,坏人的编号是 k+1 到 2k。我们希望求出 m 的最小值,使得最先出列的 k 个人都是坏人。 输入: 仅有的一个数字是 k(0 < k <14) 。

By-SHBF

58

NOIP 基础知识要点一

输出: 使得最先出列的 k 个人都是坏人的 m 的最小值。 输入样例: 4 输出样例: 30 程序: program program2; var i, k, m, start: longint; find: boolean; function check(remain: integer): boolean; var result: integer; begin result:=( ① ) mod remain; if( ② )then begin start := result; check := true; end else check := false; end; begin find := false; read(k); m := k; while ( ③ ) do begin find := true; start := 0; for i := 0 to k-1 do if( not check( ④ )) then begin find := false; break; end; inc(m); end; writeln( ⑤ ); end.

By-SHBF

59

NOIP 基础知识要点一

第十一届全国青少年信息学奥林匹克联赛初赛试题(05)
一.选择一个正确的答案代码(A/B/C/D/E),填入括号内(每题 1.5 分,共 30 分) 1.在字符串“ababacbabcbdecced”中出现次数最多的字母出现了( )次。 A.6 B.5 C.4 D.3 E.2 2.设全集 I={a,b,c,d,e,f,g,h},集合 A={a,b,c,d,e,f},B={c,d,e},C={a,d},那么集合 A∩B∩~C 为( )。 A.{c,e} B.{d,e} C.{e} D.{c,d,e} E.{d,f} 3.和十进制数 23 的值相等的二进制数是( )。 A.10110 B.11011 C.11011 D.10111 E.10011 4.完全二叉树的交点个数为 11,则它的叶结点个数为( )。 A.4 B.3 C.5 D.2 E.6 5.平面上有五个点 A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图 G 的顶点,每两 点之间的直线距离是图 G 中对应边的权值。 以下哪条边不是图 G 的最小生成树中的边 ) ( 。 A.AD B.BD C.CD D.DE E.EA 6.Intel 的首颗 16 位处理器是( )。 A.8088 B.80386 C.80486 D.8086 E.Pentium 7.处理器 A 每秒处理的指令时处理器 B 的 2 倍。某一特定程序 P 分别编译为处理器 A 和处 理器 B 的指令,编译结果处理器 A 的指令数是处理器 B 的 4 倍。已知程序 P 在处理器 A 上 执行需要 1 个小时,那么在输入相同的情况下,程序 P 在处理器 B 上执行需要( )小时。 A.4 B.2 C.1 D.1/2 E.1/4 8.以下哪个不是计算机的输出设备( )。 A.音箱 B.显示器 C.打印机 D.扫描仪 E.绘图仪 9.下列活动中不属于信息学奥赛的系列活动的是( )。 A.NOIP B.NOI C.IOI D.冬令营 E.程序员等级考试 10.以下断电之后仍能保存数据的是( )。 A.硬盘 B.寄存器 C.显存 D.内存 E.高速缓存 11.以下哪个软件不是及时通信软件( )。 A.网易泡泡 B.MSN Messenger C.Google Talk D.3DS Max E.QQ 12.下列关于高级语言的说法错误的是( )。 A.Fortan 是历史上的第一个面向科学计算的高级语言 B.Pascal 和 C 都是编译执行的高级语言 C.C++是历史上的第一个支持面向对象的语言 D.编译器将高级语言程序转变为目标代码 E.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 13.下列设备不具有计算功能的是( )。 A.笔记本电脑 B.掌上电脑 C.智能手机 D.电子计算机 E.液晶显示器 14.常见的邮件传输服务器使用( )协议接收邮件。 A.HTTP B.SMTP C.TCP D.FTP E.POP3 15.下列浏览器中,由微软公司开发的浏览器是( ) A.Internet Explore B.Netcape C.Opera D.Firefox E.Mozilla 16.一位艺术史学家有 2000 幅真彩色图像,每幅图像约占 3M 空间。如果将这些图像以位图 形式保存在 CD 光盘上(一张 CD 光盘的容量按 600M 计算),大约需要( )张 CD 光盘。

By-SHBF

60

NOIP 基础知识要点一

A.1 B.10 C.100 D.1000 E.10000 17.设 A=true,B=false,C=false,D=true,以下逻辑运算表达式值为真的是( )。 A.(A∧B)∨(C∧D) B.((A∧B)∨C)∧D C.A∧((B∨C)∧D) D.(A∧(B∨C))∨D E.(A∨B)∧(C∧D) 18.(3725)8+(B)16 的运算结果是( )。 A.(3736)8 B.(2016)10 C.(1111110000)2 D.(3006)10 E.(7B0)16 19.二叉树 T 的宽度优先遍历序列为 A B C D E F G H I,已知 A 是 C 的父交点,D 是 G 的父 交点,F 是 I 的父交点,数中所有结点的最大深度为 3,(根结点深度设为 0),可知 F 的 父结点是( )。 A.无法确定 B.B C.C D.D E.E 20.设栈 S 的初始状态为空, 元素 a,b,c,d,e,f,g 依次入栈, 以下出栈序列不可能出现的是 ) ( 。 A.a,b,c,e,d,f,g B.b,c,a,f,e,g,d C.a,e,d,c,b,f,g D.d,c,f,e,b,a,g E.g,e,f,d,c,b,a 二.问题求解(请在空格处填上答案,每空 5 分,共 10 分) 1.将数组{32,74,25,53,28,43,86,47}中的元素按从小到大的顺序排列,每次可以交换任意两个 元素,最少需要交换___次。 2.有 3 个课外小组:物理组,化学组和生物组。今有张、王、李、赵、陈、5 名同学,已知 张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员。如果要在 3 个小组分别选出 3 位组长,一位同学最多只能担任一个小组的组长,共有___种选择方案。 三.阅读程序(共 4 题,每题 8 分,共计 32 分) 1. var a,b : integer; begin read(a); b:=(a*(a*a))+1; if b mod 3 = 0 then b := b div 3; if b mod 5 = 0 then b := b div 5; if b mod 7 = 0 then b := b div 7; if b mod 9 = 0 then b := b div 9; if b mod 11 = 0 then b := b div 11; if b mod 13 = 0 then b := b div 13; if b mod 15 = 0 then b := b div 15; writeln((100*a-b) div 2); end. 输入:10 输出:_____ 2. var str : string; i : integer; begin str := 'Today-is-terrible!'; for i := 7 to 11 do if str[i] = '-' then str[i-1] := 'x'; for i := 13 downto 1 do
By-SHBF 61

NOIP 基础知识要点一

if str[i] = 't' then str[i+1] := 'e'; writeln(str); end. 输出:_____ 3. var a,b,c,p,q : integer; r : array[0..2] of integer; begin read(a,b,c); p := a div b div c; q := b - c + a + p; r[0] := a * p div q *q; r[1] := r[0] * (r[0] - 300); if (3 * q - p mod 3 <= r[0]) and (r[2] =r[2]) then r[1] := r[r[0] div p mod 2] else r[1] := r[r[0] div p mod 2]; writeln(r[0] - r[1]); end. 输入:100 7 3 输出:_____ 4. var str : string; len,i,j : integer; nchr : array[0..25] of integer; mmin : char; begin mmin := 'z'; readln(str); len := length(str); i := len; while i>= 2 do begin if str[i - 1] < str[i] then break; dec(i); end; if i = 1 then begin writeln('No result!'); exit; end; for j := 1 to i - 2 do write (str[j] < mmin) then fillchar(nchr,sizeof(nchr),0); for j := i to len do begin if (str[j] > str[i - 1]) and (str[j] < mmin) then mmin := str[j]; inc(nchr[ord(str[j]) - ord('a')]); end; dec(nchr[ord(mmin) - ord('a')]); inc(nchr[ord(str[i - 1]) - ord('a')]); write(mmin);

By-SHBF

62

NOIP 基础知识要点一

for i := 0 to 25 do for j := 1 to nchr[i] do write(chr(i + ord('a'))); writeln; end. 输入:zzyzcccbbbaaa 输出:_____

四.完善程序(前 4 空,每空 2 分,后 5 空,每空 4 分,共 28 分) 1.判断质数 题目描述: 给出一个正整数,判断这个数是否是质数。 输入: 一个正整数 n(1 ≤ n ≤ 10000)。 输出:如果 n 是质数,输出"YES";否则,输出"NO"。 输入样例: 10 输出样例: NO 程序: var ① : integer; begin read(n); if n = 2 then writeln( ② ) else if ( ③ ) or (n mod 2 = 0) then writeln('NO') else begin i := 3; while i * i <= n do begin if ④ then begin writeln('NO'); exit; end; i := i + 2; end; writeln('YES'); end; end. 2.木材加工 题目描述: 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头(木头有可能有 剩余),需要得到的小段的数目是给定的。当然,我们希望得到的小段越长越好,你的任务 是计算能够得到的小段木头的最大长度。木头长度的单位是 cm。原木的长度都是正整数, 我们要求得到的小段木头的长度也是正整数。 输入: 第一行是两个正整数 N 和 K(1 ≤ N ≤ 100000,1 ≤ K ≤ 10000),N 是原木的数 目,K 是需要得到的小段的数目。

By-SHBF

63

NOIP 基础知识要点一

接下来的 N 行,每行有一个 1 到 10000 之间的正整数,表示一根原木的长度。 输出: 输出能够切割得到的小段的最大长度。如果连 1cm 长的小段都切不出来,输出"0"。 输入样例: 37 232 124 456 输出样例: 114 程序: var n,k :integer; len : array[1..10000] of integer; i,left,right,mid : integer; function isok(t : integer) : boolean; var num,i : integer; begin num := 0; for i := 1 to n do begin if num >= k then break; num := ① ; end; if ② then isok := true else isok :=false; end; begin readln(n,k); right := 0; for i := 1 to n do begin readln(len[i]); if right < len[i] then right := len[i]; end; inc(right); ③ ; while ④ < right do begin mid := (left + right) div 2; if ⑤ then right := mid else left := mid; end; writeln(left); end.

By-SHBF

64

NOIP 基础知识要点一

第十二届全国青少年信息学奥林匹克联赛初赛试题(06)
一、 单项选择题 (共 20题,每题 1.5分,共计 30分。每题有且仅有一个正确答案.) 。 1.在下面各世界顶级的奖项中, 为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是 ( 。 ) A. 沃尔夫奖 B. 诺贝尔奖 C. 菲尔兹奖 D. 图灵奖 2. 在下列各软件中,不属于 NOIP竞赛(复赛)推荐使用的语言环境有( 。 ) A. gcc/g++ B. Turbo Pascal C. RHIDE D. free pascal 3. 以下断电之后仍能保存数据的有( )。 A. 寄存器 B. ROM C. RAM D. 高速缓存 4.Linux是一种( )。 A. 绘图软件 B. 程序设计语言 C. 操作系统 D. 网络浏览器 5. CPU是( )的简称。 A. 硬盘 B. 中央处理器 C. 高级程序语言 D. 核心寄存器 6. 在计算机中,防火墙的作用是( 。 ) A. 防止火灾蔓延 B.防止网络攻击 C. 防止计算机死机 D. 防止使用者误删除数据 7. 在下列关于计算机语言的说法中,不正确的是( )。 A. Pascal 和 C 都是编译执行的高级语言 B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C++是历史上的第一个支持面向对象的计算机语言 D. 与汇编语言相比,高级语言程序更容易阅读 8. 在下列关于计算机算法的说法中,不正确的是( )。 A. 一个正确的算法至少要有一个输入 B. 算法的改进,在很大程度上推动了计算机科学与技术 的进步 C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性
由 OIFans. cn 收 集 由 OIFans.cn 收集

D. 目前仍然存在许多涉及到国计民生的重大课题,还没有找到能够在计算机上实施的有效算法 9. 在下列各种排序算法中,不是以“比较”作为主要操作的算法是( )。 A. 选择排序 B. 冒泡排序 C. 插入排序 D. 基数排序 10. 在编程时 (使用任一种高级语言, 不一定是 Pascal) , 如果需要从磁盘文件中输入一个很大的二 维 数组(例如 1000*1000的 double型数组)按行读(即外层循环是关于行的)与按列读(即外层 循环 , 是关于列的)相比,在输入效率上( ) 。 A. 没有区别 B. 按行读的方式要高一些 C. 按列读的方式要高一些 D. 取决于数组的存储方式。 11.在 Pascal语言中,表达式 (21 xor 2)的值是( ) A. 441 B. 42 C.23 D.24 12.在 Pascal语言中,判断 a不等于 0且 b不等于 0的正确的条件表达式是( )
.cn 收集

A. not a=0 or not b=0 B. not((a=0)and(b=0)) C. not(a=0 and b=0) D. (a<>0)and (b<>0) 13. 某个车站呈狭长形, 宽度只能容下一台车, 并且只有一个出入口。 已知某时刻该车站状态为空, 这 从 一时刻开始的出入记录为:进,出,进,进,进,出,出,进,进,进,出,出”假设车辆入站的 顺序 “ 。 为 1,2,3,??,则车辆出站的顺序为( ) 。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 14. 高度为 n的均衡的二叉树是指: 如果去掉叶结点及相应的树枝, 它应该是高度为 n-1的满二叉树。 在这里, 树高等于叶结点的最大深度, 根结点的深度为 0, 如果某个均衡的二叉树共有 2381个结点,则 该树的树高为( 。 )
By-SHBF 65

NOIP 基础知识要点一

A. 10 B. 11 C. 12 D. 13 15. 与十进制数 1770 对应的八进制数是( 。 ) A. 3350 B. 3351 C. 3352 D. 3540 16. 5个数的序列排序, 将 不论原先的顺序如何, 最少都可以通过 ( ) 次比较, 完成从小到大的 排序。 A. 6 B. 7 C. 8 D. 9 17. 设A=B=D=true,C=false,以下逻辑运算表达式值为真的有( )。 A. (? A∧B)∨(C∧D) B.? ((A∨B∨D)∧C) C.
由 OIFans.cn 收集

? A∧(B∨C∨D)

D. (A∧B∧C)∨ ? D

18. (2010)16 + (32)8 的结果是( 。 ) A. (8234)10 B. (202B)16 C. (20056)8 D. (100000000110)2 19. 设栈S 的初始状态为空,元素a, b, c, d, e 依次入栈,以下出栈序列不可能出现的有 ( )。 A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a 20. 已知 6个结点的二叉树的先根遍历是 1 2 3 4 5 6(数字为结点的编号,以下同)后根遍历是 , 3 2 5 6 4 1,则该二叉树的可能的中根遍历是( ) A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 2 3 1 4 6 5 二.问题求解(共 2题,每题 5分,共计 10分) 1. (寻找假币) 现有 80枚硬币, 其中有一枚是假币, 其重量稍轻, 所有真币的重量都相同, 如果使 用 不带砝码的天平称重, 最少需要称几次, 就可以找出假币?你还要指出第 1次的称重方法。 请写出你的 结 果:_________________________________________________。 2.取石子游戏) 现有 5堆石子,石子数依次为 3,5,7,19,50,甲乙两人轮流从任一堆中任取 ( (每次只能取自一堆,不能不取),取最后一颗石子的一方获胜。甲先取,问甲有没有获胜策略(即无 论 乙怎样取,甲只要不失误,都能获胜)?如果有,甲第一步应该在哪一堆里取多少?请写出你的结 果: _________________________________________________。 三.阅读程序写结果(共 4题,每题 8分,共计 32分) 1. Program ex301; var u:array[0..3] of integer; i,a,b,x,y:integer; begin y:=10; for i:=0 to 3 do read(u[i]); a:=(u[0]+u[1]+u[2]+u[3]) div 7; b:=u[0] div ((u[1]-u[2]) div u[3]); x:=(u[0]+a+2)-u[(u[3]+3) mod 4]; if (x>10) then y:=y+(b*100-u[3]) div (u[u[0] mod 3]*5) else y:=y+20+(b*100-u[3]) div (u[u[0] mod 3]*5); writeln (x,',',y); end. {*注:本例中,给定的输入数据可以避免分母为 0或下标越界。 } 输入:9 3 9 4 输出:_______________ 2.Program ex302; const m:array[0..4] of integer=(2,3,5,7,13);
由 OIFans.cn 收集

By-SHBF

66

NOIP 基础知识要点一

var i,j:integer; t: longint; begin for i:=0 to 4 do begin t:=1; for j:=1 to m[i]-1 do t:=t*2; t:=(t*2-1)*t; write (t,' '); end; writeln; end. 输出:____________________ 3.Program ex303; Const NN=7; Type Arr1=array[0..30] of char; var s:arr1; k,p:integer; Function fun(s:arr1; a:char;n:integer):integer; var j:integer; begin j:=n; while (a<s[j])and(j>0) do dec(j); fun:=j; end; begin for k:=1 to NN do s[k]:=chr(ord('A')+2*k+1); k:=fun(s,'M',NN); writeln(k); end. 输出:_____________ 4.program ex304; var x,x2:longint; procedure digit(n,m:longint); var n2:integer; begin if(m>0) then begin n2:=n mod 10; write(n2:2); if(m>1) then digit(n div 10,m div 10); n2:=n mod 10; write(n2:2); end; end; begin writeln('Input a number:'); readln(x);
由 OIFans.cn 收集 由 OIFans.cn 收集

By-SHBF

67

NOIP 基础知识要点一

x2:=1; while(x2<x) do x2:=x2*10; x2:=x2 div 10; digit(x,x2); writeln; end. 输入:9734526 输出:______________________________ 四.完善程序 (前 4空,每空 2.5分,后 6空,每空 3分,共 28分) 1. (全排列) 下面程序的功能是利用递归方法生成从 1到 n(n<10)的 n个数的全部可能的排列 (不一 定 按升序输出)例如,输入 3,则应该输出(每行输出 5个排列) 。 : 123 132 213 231 321 312 程序: Program ex401; Var i,n,k:integer; a:array[1..10] of integer; count:longint; {变量 count记录不同排列的个数,这里用于控制换行} Procedure perm(k:integer); var j,p,t:integer; begin if ① then begin inc(count); for p:=1 to k do write(a[p]:1); write(' '); if ( ② ) then writeln; exit; end; for j:=k to n do begin t:=a[k]; a[k]:=a[j]; a[j]:=t; ③ ; t:=a[k]; ④ ; end end; begin writeln('Entry n:'); read(n); count:=0; for i:=1 to n do a[i]:=i; ⑤ ; end. 2. 由键盘输入一个奇数 P (P<100,000,000),其个位数字不是 5,求一个整数 S,使 P×S = 1111...1 ( 在给定的条件下,解 S 必存在)。要求在屏幕上依次输出以下结果:
由 OIFans.cn 收 集

By-SHBF

68

NOIP 基础知识要点一

(1)S 的全部数字。除最后一行外,每行输出 50 位数字。 (2) 乘积的数字位数。 例 1:输入 p=13, 由于 13*8547=111111, 则应输出 (1) 8547, 6 例 2: (2) 输入 p=147, 则输出结果应为 (1) 755857898715041572184429327286470143613 (2)42,即等式的右端有 42个 1。 程序: program ex402; var p,a,b,c,t,n:longint; begin while (true) do begin writeln ('Input p, the last digit is 1 or 3 or 7 or 9:'); readln(p); if (p mod 2<>0)and(p mod 5<>0) then ⑥ ; {如果输入的数符合要求,结束循环 } end; a:=0; n:=0; while (a<p) do begin a:=a*10+1; inc(n); end; t:=0; repeat b:=a div p; write(b:1); inc(t); if ( ⑦ ) then writeln; c:= ⑧ ; a:= ⑨ ; inc(n); until c<=0; dec(n); writeln; writeln('n=', ⑩ ); end.
由 OIFans.cn 收 集

By-SHBF

69

NOIP 基础知识要点一

2007 全国青少年信息学奥林匹克竞赛试题(初中组)
一、 单项选择题 (共 10 题, 每题 1.5 分, 共计 15 分。 每题有且仅有一个正确答案.) 。 1. 在以下各项中。( )不是 CPU 的组成部分。 A. 控制器 B. 运算器 C. 寄存器 D. 主板 2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( )为主。 A. 二叉树 B. 多叉树 C. 哈希表 D. 二维表 3.在下列各项中,只有( )不是计算机存储容量的常用单位。 A. Byte B. KB C. UB D. TB 4.ASCII 码的含义是( )。 A. 二—十进制转换码 B. 美国信息交换标准代码 C. 数字的二进制数码 D. 计算机可处理字符的唯一编码 5.一个完整的计算机系统应包括( ) A.系统硬件和系统软件 B. 硬件系统和软件系统 C.主机和外部设备 D.主机、键盘、显示器和辅助存储器 6.IT 的含义是( ) A.通信技术 B. 信息技术 C. 网络技术 D. 信息学 7. LAN 的含义是( )。 A. 因特网 B. 局域网 C. 广域网 D. 城域网 8. 冗余数据是指可以由以他数据导出的数据,例如,数据库中已存放了学生的数学、语文、 和英语的三科成绩,如果还存放三科成绩的总分,则总分就可以看做冗余数据。冗余数据往 往会造成数据的不一致, 例如上面 4 个数据如果都是输入的, 由于操作错误使总分不等于三 科成绩之和,就会产生矛盾。下面关于冗余数据的说法中, 正确的是( )。 A. 应该在数据库中消除一切冗余数据 B.用高级语言编写的数据处理系统, 通常比用关系数据库编写的系统更容易消除冗余数据 C. 为了提高查询效率, 在数据库中可以适当保留一些冗余数据, 但更新时要做相容性检 验 D. 做相容性检验会降低效率, 可以不理睬数据库中的冗余数据 9. 在下列各软件中,属于 NOIP 竞赛(复赛)推荐使用的语言环境有( )。 A. gcc B. g++ C. Turbo C D. free pascal 10. 以下断电之后将仍能保存数据的有( )。 A. 硬盘 B. 高速缓存 C. 显存 D. RAM 11. 在下列关于计算机语言的说法中,正确的有( )。 A. 高级语言比汇编语言更高级, 是因为它的程序的运行效率更高 B. 随着 Pascal、C 等高级语言的出现, 机器语言和汇编语言已经退出了历史舞台 C. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 D. C 是一种面向过程的高级计算机语言 12. 近 20 年来, 许多计算机专家都大力推崇递归算法, 认为它是解决较复杂问题的强有力 的工具. 在下列关于递归的说法中, 正确的是( )。 A. 在 1977 年前后形成标准的计算机高级语言"FORTRAN77"禁止在程序使用递归, 原因之一 是该方法可能会占用更多的内存空间. B. 和非递归算法相比, 解决同一个问题, 递归算法一般运行得更快一些

By-SHBF

70

NOIP 基础知识要点一

C. 对于较复杂的问题, 用递归方式编程往往比非递归方式更容易一些 D. 对于已定义好的标准数学函数 sin(x), 应用程序中的语句“y=sin(sin(x));”就是一 种递归调用 13. 一个无法靠自身的控制终止的循环称为“死循环”,例如在 C 语言程序中,语句 “while(1)printf("*");”就是一个死循环,运行它将无休止地打印*号。下面关于死循环 的说法中, 只有( )是正确的。 A. 不存在一种算法, 对任何一个程序及相应的输入数据, 都可以判断是否会出现死循环, 因而, 任何编译系统都不做死循环检查 B. 有些编译系统可以检测出死循环 C. 死循环属于语法错误, 既然编译系统能检查各种语法错误, 当然也能检查出死循环 D. 死循环与多进程中出现的“死锁”差不多,而死锁是可以检测的,因而,死循环也是可 以检测的 14. 在 Pascal 语言中,表达式 (23 or 2 xor 5)的值是( ) A. 18 B. 1 C.23 D.32 15. 在 Pascal 语言中,判断整数 a 等于 0 或 b 等于 0 或 c 等于 0 的正确的条件表达式 是( ) A. not ((a<>0) or (b<>0) or (c<>0)) B. not ((a<>0) and (b<>0) and (c<>0)) C. not ((a=0) and (b=0)) or (c=0) D.(a=0) and (b=0) and (c=0) 16. 地面上有标号为 A、 C 的 3 根细柱, 在 A 柱上放有 10 个直径相同中间有孔的圆盘, 从 B、 上到下次依次编号为 1, 2, 3, ??,将 A 柱上的部分盘子经过 B 柱移入 C 柱, 也可以在 B 柱上暂存。如果 B 柱上的操作记录为:“进,进,出,进,进,出,出,进,进,出,进, 出,出”。那么, 在 C 柱上, 从下到上的盘子的编号为( )。 A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 17. 与十进制数 1770 相对应的 8 进制数是( )。 A. 3350 B. 3351 C. 3352 D. 3540 18. 设 A=B=true,C=D=false,以下逻辑运算表达式值为真的有( )。 A. (﹁A∧B)∨(C∧D∨A) B. ﹁ ( ( (A∧B)∨C)∧D) C. A∧(B∨C∨D)∨D D. (A∧(D∨C)) ∧B 19. (2070)16+(34)8 的结果是( )。 A. (8332)10 B. (208C)16 C. (100000000110)2 D. (20214)8 20. 已知 7 个节点的二叉树的先根遍历是 1 2 4 5 6 3 7(数字为结点的编号,以下同), 后 根遍历是 4 6 5 2 7 3 1, 则该二叉树的可能的中根遍历是( ) A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 二.问题求解(共 2 题,每题 5 分,共计 10 分) 1. (子集划分)将 n 个数{1,2,3,?,n}划分成 r 个子集。每个数都恰好属于一个子集, 任何两个不同的子集没有共同的数,也没有空集。将不同划分方法的总数记为 S(n,r)。 例如,S(4,2)=7,这 7 种不同的划分方法依次为{(1), (234)}, {(2), (134)}, {(3),(123)},{(4),(123)},{(12),(34)},{(13),(24)}, {(14),(23)}。当 n=6, r=3 时,S(6,3)= 。

By-SHBF

71

NOIP 基础知识要点一

提示:先固定一个数,对于其余的 5 个数考虑 S(5,3)与 S(5,2),再分这两种情况固定 的数进行分析。 2.(最短路线)某城市的街道是一个很规整的矩形网络(见下图),有 7 条南北向的纵街, 5 条东西向的横街。现要从西南的 A 走到东北角的 B,最短的走法共有多少 种? 。 三.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1.program j301; var i,a,b,c,x,y:integer; p:array[0..4] of integer; begin y:=20; for i:=0 to 4 do read(p[i]); readln; a:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7; b:=p[0]+p[1] div ((p[2]+p[3])div p[4]); c:=p[0]*p[1] div p[2]; x:=a+b-p[(p[3]+3)mod 4]; if(x>10) then y:=y+ (b*100-a) div(p[p[4] mod 3]*5) else y:=y+20+(b*100-c)div (p[p[4] mod 3]*5); writeln(x,',',y); end. {注:本例中,给定的输入数据可以避免分母为 0 或下标越界。} 输入:6 6 5 5 3 输出:_______________ 2.program j302; var a,b:integer; var x,y:^integer; procedure fun(a,b:integer); var k:integer; begin k:=a;a:=b;b:=k; end; begin a:=3;b:=6; x:=@a;y:=@b; fun(x^,y^); writeln(a,',',b); end. 输出:_____________________________ 3.program j303; var a1:array[1..50] of integer; var i,j,t,t2,n,n2:integer;

By-SHBF

72

NOIP 基础知识要点一

begin n:=50; for i:=1 to n do a1[i]:=0; n2:=round(sqrt(n)); for i:=2 to n2 do if(a1[i]=0) then begin t2:=n div i; for j:=2 to t2 do a1[i*j]:=1; end; t:=0; for i:=2 to n do if (a1[i]=0) then begin write(i:4); inc(t); if(t mod 10=0) then writeln; end; writeln; end. 输出: 4.program j304; type str1=string[100]; str2=string[200]; var s1:str1; s2:str2; function isalpha(c:char):boolean; var i:integer; begin i:=ord(c); if ((i>=65) and (i<=90)) or ((i>=97) and (i<=122)) then isalpha:=true else isalpha:=false; end; function isdigit(c:char):boolean; var i:integer; begin i:=ord(c); if (i>=48) and (i<=57) then isdigit:=true else isdigit:=false; end; procedure expand(s1:str1;var s2:str2); var i,j:integer; a,b,c:char;

By-SHBF

73

NOIP 基础知识要点一

begin j:=1; c:=char(1); i:=0; while(i<=ord(s1[0])) do begin inc(i); c:=s1[i]; if c='-' then begin{1} writeln('i=',i); a:=s1[i-1]; b:=s1[i+1]; if (isalpha(a) and isalpha(b))or (isdigit(a) and isdigit(b)) then begin writeln('*****',a,'&',b); dec(j); while(ord(upcase(a))<ord(upcase(s1[i+1])))do begin s2[j]:=a;inc(j);inc(a); end; end else begin s2[j]:=c;inc(j); end; end{1} else begin s2[j]:=c;inc(j); end; end; s2[0]:=char(j-2); end; begin writeln('input s1:'); readln(s1); expand(s1,s2); writeln(s2); end. 输入:wer2345d-h454-82qqq 输出: 四.完善程序 (前 4 空,每空 2.5 分,后 6 空,每空 3 分,共 28 分) 1.(求字符串的逆序) 下面的程序的功能是输入若干行字符串,每输入一行,就按逆序输 出该行,最后键入-1 终止程序。 请将程序补充完整。 program j401; type str1=string[100]; var line:str1; kz:integer; procedure reverse(var s:str1); var i,j:integer; t:char; begin i:=1; j:=length(s); while (i<j) do

By-SHBF

74

NOIP 基础知识要点一

begin t:=s[i]; s[i]:=s[j]; s[j]:=t; ①; ② ; end; end; begin writeln('continue? -1 for end.'); readln(kz); while ( ③ ) do begin readln(line); ④; writeln(line); writeln('continue? -1 for end.'); readln(kz); end; end. 2.(棋盘覆盖问题)在一个 2K×2K 个方格组成的棋盘中恰好有一个方格与其他方格 不同(图中标记为-1 的方格),称之为特殊方格。现用 L 型(占有 3 个小格)纸片覆盖棋 盘上除特殊方格的所有部分,各纸片不得重叠,于是,用到的纸片数恰好是(4K-1)/3. 在下表给出的一个覆盖方案中,K=2,相同的 3 个数字构成一个纸片。 下面给出的程序是用分治法设计的,将棋盘一分为四,依次处理左上角、右上角、左 下角、右下角,递归进行。请将程序补充完整。 program j402; type arr1=array[1..65] of integer; arr2=array[1..65] of arr1; var board:arr2; tile:integer; size,dr,dc:integer; procedure chessboard(tr,tc:integer;dr,dc:integer;var size:integer); var t,s:integer; begin if (size=1) then ⑤; t:=tile; inc(tile); s:=size div 2; if ⑥then chessboard(tr,tc,dr,dc,s) else begin board[tr+s-1][tc+s-1]:=t; ⑦; end; if(dr<tr+s) and (dc>=tc+s) then chessboard(tr,tc+s,dr,dc,s) else begin board[tr+s-1][tc+s]:=t; ⑧; end; 2 2 3 if(dr>=tr+s) and(dc<tc+s) then 2 -1 1 chessboard(tr+s,tc,dr,dc,s) else begin 4 4 1 4
By-SHBF

3 3 5 5
75

1 5

NOIP 基础知识要点一

board[tr+s][tc+s-1]:=t; ⑨; if (dr>=tr+s) and (dc>=tc+s) then chessboard(tr+s,tc+s,dr,dc,s) else begin board[tr+s][tc+s]:=t; ⑩; end;

end;

end;

procedure prt1(n:integer); var i,j:integer; begin for i:=1 to n do begin for j:=1 to n do write(board[i][j]:3); writeln; end; end; begin writeln('input size(4/8/16/64):'); readln(size); writeln('input the position of special block(x,y):'); readln(dr,dc); board[dr][dc]:=-1; tile:=1; chessboard(1,1,dr,dc,size); prt1(size); end.

By-SHBF

76

NOIP 基础知识要点一

第十四届全国青少年信息学奥林匹克联赛初赛试题(08)
一、 单项选择题 (共 20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确答案.) 。 1.微型计算机中,控制器的基本功能是( ) 。 A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 获取外部信息 D. 存放程序和数据 2. 设A=true,B=false,C=true,D=false,以下逻辑运算表达式值为真的是( )。 A. (A∧B)∨(C∧D∨ ? A) B. (( ? A∧B)∨C)∧ ? D C. (B∨C∨D)∧D∧A D. A∧(D∨ ? C)∧B 3. 在下列关于图灵奖的说法中,不正确的是( )。 A. 图灵奖是美国计算机协会于1966年设立的,专门奖励那些对计算机事业作出重要贡 献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止,还没有华裔计算机科学家获此殊荣 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵 4.计算机在工作过程中,若突然停电, ( )中的信息不会丢失。 A. ROM 和 RAM B. CPU C.ROM D. RAM 5.完全二叉树共有 2*N-1 个结点,则它的叶节点数是( ) 。 A. N-1 B. N C. 2*N D. 2N-1 6. 在以下各项中, )不是操作系统软件。 ( A. Solaris B. Linux C. Windows Vista D. Sybase 7.设栈 S 的初始状态为空,元素 a,b,c,d,e,f 依次入栈 S,出栈的序列为 b,d,f, e,c,a,则栈 S 的容量至少应该是( ) 。 A. 6 B. 5 C. 4 D. 3 8. 与十进制数 28.5625 相等的四进制数是( ) 。 A. 123.21 B. 131.22 C. 130.22 D. 130.21 9. 设字符串S=”Olympic”,S的非空子串的数目是( )。 A. 28 B. 29 C. 16 D. 17 10. Web2.0 是近年来互联网的热门概念之一, 其核心思想是互动与分享。 下列网站中, ) ( 是典型的 Web2.0 应用。 A. Sina B. Flickr C. Yahoo D. Google 11. 递归过程或函数调用时,处理参数和返回地址,通常使用一种称为( )的数据结 构。 A. 队列 B. 多维数组 C. 线性表 D. 栈 12. (2008)10 + (5B)16 的结果是( ) 。 A. (833)16 B. (2089)10 C. (4163)8 D. (100001100011)2 13. 二叉树 T,已知其先根遍历是 1 2 4 3 5 7 6(数字为结点的编号,以下同) ,中根 遍历是 2 4 1 5 7 3 6,则该二叉树的后根遍历是( ) 。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1 14.将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列,每 次可以交换任意两个元素,最少需要交换( )次。 A. 4 B. 5 C. 6 D. 7 15. 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88,92,100}进行二分查找, 成功查找元素 19 的查找长度(比较次数)是( ) 。
By-SHBF 77

NOIP 基础知识要点一

A. 1 B. 2 C. 3 D. 4 16. 面向对象程序设计(Object-Oriented Programming)是一种程序设计的方法论, 它将对象作为程序的基本单元,将数据和程序封装在对象中,以提高软件的重用性、灵活性 和扩展性。下面关于面向对象程序设计的说法中,不正确的是( ) 。 A. 面向对象程序设计通常采用自顶向下设计方法进行设计。 B. 面向对象程序设计方法具有继承性(inheritance) 、封装性(encapsulation) 、 多态性(polymorphism)等几大特点。 C. 支持面向对象特性的语言称为面向对象的编程语言,目前较为流行的有 C++、JAVA、 C#等。 D. 面向对象的程序设计的雏形来自于 Simula 语言,后来在 SmallTalk 语言的完善和 标准化的过程中得到更多的扩展和对以前思想的重新注解。 至今 SmallTalk 语言仍然被视 为面向对象语言的基础。 17. 在 32*32 点阵的“字库”中,汉字“北”与“京”的字模占用字节数之和是( ) 。 A. 512 B. 256 C. 384 D. 128 18. 设 T 是一棵有 n 个顶点的树,下列说法不正确的是( ) 。 A. T 有 n 条边 B. T 是连通的 C. T 是无环的 D. T 有 n-1 条边 19. 下列不属于NOIP竞赛推荐使用的语言环境的是( )。 A. Dev-C++ B. Visual C++ C. free pascal D. Lazarus 20.在 PASCAL 程序中,表达式(200 or 10)的值是( ) A. 20 B. 1 C. 220 D. 202 二.问题求解(共 2 题,每题 5 分,共计 10 分) 1. 书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的,C 和 D 是黑皮的。把 这 4 本书摆在书架上,满足所有黑皮的书都排在一起的摆法有_____种。满足 A 必须比 C 靠左,所有红皮的书要摆放在一起,所有黑皮的书要摆放在一起,共有______种摆法。 2.有 6 个城市,任何两个城市之间都有一条道路连接,6 个城市两两之间的距离如下表 所示,则城市 1 到城市 6 的最短距离为_____________。 城市 1 城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 0 2 3 1 12 15 城市 2 2 0 2 5 3 12 城市 3 3 2 0 3 6 5 城市 4 1 5 3 0 7 9 城市 5 12 3 6 7 0 2 城市 6 15 12 5 9 2 0

三.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. var i,a,b,c,d:integer; f:array[0..3] of integer; begin for i:=0 to 3 do read(f[i]); a := f[0] + f[1] + f[2] + f[3]; a := a div f[0];
By-SHBF 78

NOIP 基础知识要点一

b := f[0] + f[2] b := b div a; c := (b * f[1] + d := f[(b div c) if (f[(a + b + c begin a := a + b; writeln(a); end else begin c := c + d; writeln(c); end;

+ f[3]; a) div f[2]; mod 4]; + d) mod 4] > f[2]) then

end. 输入:9 19 29 39 输出:_______________ 2.procedure foo(a,b,c:integer); begin if a>b then foo(c,a,b) else writeln(a, ',', b, ',', c); end; var a,b,c:integer; begin read(a, b, c); foo(a,b,c); end. 输入: 3 1 2 输出: __________ 3.type TT= array[0..20]of integer; procedure func(var ary:TT; n:integer); var i,j,x:integer; begin i:=0;j:=n-1; while i<j do begin while (i<j) and (ary[i]>0) do inc(i); while (i<j) and (ary[j]<0) do dec(j); if i<j then begin x:=ary[i]; ary[i]:=ary[j]; ary[j]:=x; inc(i); dec(j); end; end; end;
By-SHBF 79

NOIP 基础知识要点一

var a:TT; i,m:integer; begin m:=10; for i:=0 to m-1 do func(a,m); for i:=0 to m-1 do writeln; read(a[i]); write(a[i], ' ');

end. 输入:5 4 -6 -11 6 -59 22 -6 1 10 输出:____________________________________ 4. procedure solve(first:string; mid:string;spos_m,epos_m:integer); var i,root_m:integer; begin if spos_f > epos_f then exit; for i:=spos_m to epos_m do if first[spos_f] = mid[i] then begin root_m:=i; break; end;

spos_f,epos_f:integer;

solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1); solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m); write(first[spos_f]); end; var first,mid:string; len:integer; begin readln(len); readln(first); readln(mid); solve(first,1,len,mid,1,len); writeln; end. 输入: 7 ABDCEGF BDAGECF 输出:____________________________________ 四.完善程序 (前 4 空,每空 2.5 分,后 6 空,每空 3 分,共 28 分) 1.(字符串替换)给定一个字符串 S(S 仅包含大小写字母),下面的程序将 S 中的每个 字母用规定的字母替换,并输出 S 经过替换后的结果。程序的输入是两个字符串,第一个
By-SHBF 80

NOIP 基础知识要点一

字符串是给定的字符串 S,第二个字符串 S’由 26 个字母组成,它是 a-z 的任一排列,大 小写不定,S’规定了每个字母对应的替换字母:S’中的第一个字母是字母 A 和 a 的替换字 母,即 S 中的 A 用该字母的大写替换,S 中的 a 用该字母的小写替换;S’中的第二个字母 是字母 B 和 b 的替换字母,即 S 中的 B 用该字母的大写替换,S 中的 b 用该字母的小写替 换;?? 以此类推。 var change:string; str:string; procedure CheckChangeRule; var i:integer; begin for i:=1 to 26 do begin if ① then change[i]:= chr(ord(change[i]) - ord('A') + ord('a')); end; end; procedure ChangeString; var len,i:integer; begin len := length(str); for i:=1 to len do begin if ② then begin str[i] := upcase(change[ord(str[i]) – ord(‘A’) + 1]); end else begin ③ end; end; end; begin readln(str); readln(change); CheckChangeRule; ④ writeln(str); end. 2. (找第 k 大的数) 给定一个长度为 1,000,000 的无序正整数序列, 以及另一个数 n (1<=n<=1000000), 然后以类似快速排序的方法找到序列中第 n 大的数(关于第 n 大的数:例如序列{1,2,3,4,5,6}中第 3 大的数是 4)。 var a:array[1..1000000] of integer;
By-SHBF 81

NOIP 基础知识要点一

n,m,ans:integer; procedure swap(var a,b:integer); var t:integer; begin if (a <> b) then begin t := a; a := b; b := t; end; end; function FindKth(left,right,n:integer):integer; var tmp,value,i,j:integer; begin if left = right then exit(left); tmp:= random(right-left) + left; swap(a[tmp],a[left]); value := ① ; i := left; j := right; while i<j do begin while (i<j) and ( ② ) do dec(j); if i<j then begin a[i] := a[j]; inc(i); end else break; while (i<j) and ( ③ ) do inc(i); if i<j then begin a[j] := a[i]; dec(j); end else break; end; ④ if i<n then begin inc(i); exit(FindKth( ⑤ if i>n then begin dec(i); exit( ⑥ end; exit(i); end; var i:integer; begin randomize; m:=1000000; for i:=1 to m do read(a[i]); read(n); ans:= FindKth(1,m,n); writeln(a[ans]); end.
By-SHBF

));end; );

82

NOIP 基础知识要点一

第十五届全国青少年信息学奥林匹克联赛初赛试题(09)
一. 单项选择题(共 20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确答案。 ) 1、 关于图灵机下面的说法哪个是正确的: A) 图灵机是世界上最早的电子计算机 B) 由于大量使用磁带操作,图灵机运行速度很慢。 C) 图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。 D) 图灵机只是一个理论上的计算模型。 2、 关于计算机内存,下列说法哪个是正确的: A) 随机存储器(RAM)的意思是当程序运行时,每次具体分配给程序的内存位置是 随机而不确定的。 B) 1MB 内存通常是指 1024*1024 字节大小的内存。 C) 计算机内存严格说来包括主存(memory) 、高速缓存(cache)和寄存器(register) 三个部分。 D) 一般内存中的数据即使在断电的情况下也能保留 2 个小时以上。 3、 下列关于 BIOS 的说法哪个是正确的: A) BIOS 是计算机基本输入输出系统软件的简称。 B) BIOS 包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。 C) BIOS 一般由操作系统厂商来开发完成。 D) BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 4、 关于 CPU 下面那个说法是正确的: A) CPU 全称为中央处理器(或中央处理单元) 。 B) CPU 可以直接运行汇编语言。 C) 同样主频下,32 位的 CPU 比 16 位的 CPU 运行速度快一倍。 D) CPU 最早是由 Intel 公司发明的。 5、 关于 ASCII,下面哪个说法是正确的: A) ASCII 码就是键盘上所有键的唯一编码。 B) 一个 ASCII 码使用一个字节的内存空间就能够存放。 C) 最新扩展的 ASCII 编码方案包含了汉字和其他欧洲语言的编码。 D) ASCII 码是英国人主持制定并推广使用的。 6、 下列软件中不是计算机操作系统的是: A) Windows B) Linux C) OS/2 D) WPS 7、 关于互联网,下面的说法哪一个是正确的: A) 新一代互联网使用的 IPv6 标准是 IPv5 标准的升级与补充。 B) 互联网的入网主机如果有了域名就不再需要 IP 地址。 C) 互联网的基础协议为 TCP/IP 协议。 D) 互联网上所有可下载的软件及数据资源都是可以合法免费使用的。 8、 关于 HTML 语言下面哪种说法是正确的: A) HTML 实现了文本、图形、声音乃至视频信息的统一编码。 B) HTML 全称为超文本标记语言。 C) 网上广泛使用的 Flash 动画都是由 HTML 编写的。 D) HTML 也是一种高级程序设计语言。 9、 关于程序设计语言,下面哪种说法是正确的: A) 加了注释的程序一般会比同样的没有加注释的程序运行速度慢。

By-SHBF

83

NOIP 基础知识要点一

B) 高级语言开发的程序不能使用在低层次的硬件系统 (如: 自控机床) 或低端手机上。 C) 高级语言相对于低级语言更容易实现跨平台的移植。 D) 以上说法都不对。 10、已知大写字母 A 的 ASCII 编码为 65(十进制) ,则大写字母 J 的十进制 ASCII 编码为: A) 71 B) 72 C) 73 D) 以上都不是 11、十进制小数 125.125 对应的八进制数是 A) 100.1 B) 175.175 C) 175.1 D) 100.175 12、有六个元素 FEDCBA 从左到右依次顺序进栈, 在进栈过程中会有元素被弹出栈。 问下列 哪一个不可能是合法的出栈序列? A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF 13、表达式 a*(b+c)-d 的后缀表达式是 A) abcd*+B) abc+*dC) abc*+dD) -+*abcd

14、一个包含 n 个分支节点(非叶节点)的非空二叉树,它的叶节点数目最多为: A) 2n + 1 B) 2n - 1 C) n - 1 D) n + 1 15、快速排序最坏情况下的算法复杂度为: A) O (log2n) B) O (n) C) O (nlog2n) D) O (n2) 16、又一个由 4000 个整数构成的顺序表,假定表中的元素已经按升序排列,采用二分查找 定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素: A) 11 次 B) 12 次 C) 13 次 D) 14 次 17、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变, 下列哪种排 序算法是不稳定的: A) 冒泡排序 B) 插入排序 C) 归并排序 D) 快速排序 18、已知 n 个顶点的有向图,若该图是强连通的(从所有顶点都存在路径到达其他顶点) , 则该图中最少有多少条有向边? A) n B) n + 1 C) n - 1 D) n* (n - 1) 19、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资 源,请问全国信息学奥林匹克官方网站的网址是: A) http://www.noi.com/ B) http://www.noi.org/ C) http://www.noi.cn/ D) http://www.xinxixue.com/ 20、在参加 NOI 系列竞赛过程中,下面哪一种行为是 不 被严格禁止的: A) 携带书写工具,手表和不具有通讯功能的电子词典进入赛场。 B) 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 C) 通过互联网搜索取得解题思路。 D) 在提交的程序中启动多个进程以提高程序的执行效果。 二. 问题求解(共 2 题,每空 5 分,共 10 分) 1. 小陈现有 2 个任务 A,B 要完成,每个任务分别有若干步骤如下:A=a1->a2->a3, B=b1->b2->b3->b4->b5。在任何时候,小陈只能专心做某个任务的一个步骤。但是如果愿意, 他可以在做完手中任务的当前步骤后, 切换至另一个任务, 从上次此任务第一个未做的步骤 继续。每个任务的步骤顺序不能打乱,例如??a2->b2->a3->b3??是合法的,而?? a2->b3->a3->b2??是不合法的。 小陈从 B 任务的 b1 步骤开始做, 当恰做完某个任务的某个 步骤后,就停工回家吃饭了。当他回来时,只记得自己已经完成了整个任务 A,其他的都忘 了。使计算小陈饭前已做的可能的任务步骤序列共有 __________ 种。 2. 有如下的一段程序:

By-SHBF

84

NOIP 基础知识要点一

1. a:=1; 2. b:=a; 3. d:=-a; 4. e:=a+d; 5. c:=2*d; 6. f:=b+e-d; 7. g:=a*f+c; 现在要把这段程序分配到若干台(数量充足)用电缆连接的 PC 上做并行执行。每台 PC 执 行其中的某几个语句, 并可随时通过电缆与其他 PC 通讯, 交换一些中间结果。 假设每台 PC 每单位时间可以执行一个语句,且通讯花费的时间不计。则这段程序最快可以在_______单 位时间内执行完毕。注意:任意中间结果只有在某台 PC 上已经得到,才可以被其他 PC 引 用。例如若语句 4 和 6 被分别分配到两台 PC 上执行,则因为语句 6 需要引用语句 4 的计算 结果,语句 6 必须在语句 4 之后执行。 三. 阅读程序写结果(共 4 题,每题 8 分,共 32 分) 1. var a, b: integer; function work(a, b: integer): integer; begin if a mod b <> 0 then work := work(b, a mod b) else work := b; end; begin read(a, b); writeln(work(a, b)); end. 输入:20 12 输出:_____ 2. var a, b: array[0..2] of integer; i, j, tmp: integer; begin for i := 0 to 2 do read(b[i]); for i := 0 to 2 do begin a[i] := 0; for j := 0 to i do

By-SHBF

85

NOIP 基础知识要点一

begin inc(a[i], b[j]); inc(b[a[i] mod 3], a[j]); end; end; tmp := 1; for i := 0 to 2 do begin a[i] := a[i] mod 10; b[i] := b[i] mod 10; tmp := tmp * (a[i] + b[i]) end; writeln(tmp); end. 输入:2 3 5 输出:_______ 3. const c = 2009; var n, p, s, i, j, t: integer; begin read(n, p); s := 0; t := 1; for i := 1 to n do begin t := t * p mod c; for j := 1 to i do s := (s + t) mod c; end; writeln(s); end. 输入:11 2 输出:______ 4. var a: string; n: integer; procedure getnext(var str: string); var

By-SHBF

86

NOIP 基础知识要点一

l, i, j, k: integer; temp: char; begin l := length(str); k := l - 1; while (k >= 1) and (str[k] > str[k + 1]) do dec(k); i := k + 1; while (i <= l) and (str[i] > str[k]) do inc(i); temp := str[k]; str[k] := str[i - 1]; str[i - 1] := temp; for i := l downto k + 1 do for j := k + 1 to i - 1 do if str[j] > str[j + 1] then begin temp := str[j]; str[j] := str[j + 1]; str[j + 1] := temp; end; end; begin read(a); read(n); while n > 0 do begin getnext(a); dec(n); end; write(a); end. 输入:NOIP 3 输出:_______ 四. 完善程序(前 8 空,每空 3 分,后 2 空,每空 2 分,共 28 分) 1. (最大连续子段和)给出一个数列(元素个数不超过 100) ,数列元素均为负整数、 正整数、0。请找出数列中的一个连续子数列,使得这个子数列中包含的所有元素之和最大, 在和最大的前提下还要求该子数列包含的元素个数最多, 并输出这个最大和以及该连续子数 列中元素的个数。例如数列为 4,-5,3,2,4 时,输出 9 和 3;数列为 1 2 3 -5 0 7 8 时, 输出 16 和 7。 var a: array[1..100] of integer;

By-SHBF

87

NOIP 基础知识要点一

n, i, ans, len, tmp, beg: integer; begin read(n); for i := 1 to n do read(a[i]); tmp := 0;ans := 0;len := 0; beg := ① ; for i := 1 to n do begin if tmp + a[i] > ans then begin ans := tmp + a[i]; len := i - beg; end else if ( ② ) and (i - beg > len) then len := i - beg; if tmp + a[i] begin beg := ④ tmp := 0; end else ⑤ ; end; writeln(ans, ' ', len); end. 2. (国王放置)在 n*m 的棋盘上放置 k 个国王,要求 k 个国王互相不攻击,有多少 种不同的放置方法。假设国王放置在第(x, y)格,国王的攻击的区域是:(x-1,y-1), (x-1,y), (x-1,y+1), (x, y-1), (x,y+1), (x+1,y-1), (x+1,y), (x+1,y+1)。 读入三个数 n,m,k,输出答案。题目利用回溯法求解。棋盘行标号为 0~n-1,列标号为 0~m-1。 var n, m, k, ans: integer; hash: array[0..4, 0..4] of integer; procedure work(x, y, tot: integer); var i, j: integer; begin if tot = k then begin inc(ans); exit; end; ③ ; then

By-SHBF

88

NOIP 基础知识要点一

repeat while hash[x, y] <> 0 do begin inc(y); if y = m then begin inc(x); y := ① ; end; if x = n then exit; end; for i := x - 1 to x + 1 do if (i >= 0) and (i < n) then for j := y - 1 to y + 1 do if (j >= 0) and (j <= m) then ② ; ③ ; for i := x - 1 to x + 1 do if (i >= 0) and (i < n) then for j := y - 1 to y + 1 do if (j >= 0) and (j <= m) then ④ inc(y); if y = m then begin inc(x); y := 0; end; if x = n then exit; until false; end; begin read(n, m, k); ans := 0; fillchar(hash, sizeof(hash), 0); ⑤ ; writeln(ans); end. ;

By-SHBF

89

NOIP 基础知识要点一

十六届全国青少年信息学奥林匹克联赛初赛试题 (普及组 Pascal 语言 两小时完成)
●●全部试题答案均要求卸载答卷纸上,写在试卷上一律无效●● 一、单项选择题(共 20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确选项。) 1. 2E+03 表示( )。 A.2.03 B.5 C.8 D.2000 2.一个字节(byte)由( A.8 B.16 )个二进制组成。 C.32 D.以上都有可能 )。

3.以下逻辑表达式的值恒为真的是( A.P∨(┓P∧Q)∨(┓P∧┓Q) B.Q∨(┓P∧Q)∨(P∧┓Q) C.P∨Q∨(P∧┓Q)∨(┓P∧Q) D.P∨┓Q∨(P∧┓Q)∨(┓P∧┓Q)

4.Linux 下可执行文件的默认扩展名是( )。 A. exe B. com C. dll

D.以上都不是 )个结点。

5.如果树根算第 1 层,那么一颗 n 层的二叉树最多有( n n n n+1 A. 2 -1 B. 2 C. 2 +1 D. 2 6.提出“存储程序”的计算机工作原理的是( )。 A. 克劳德?香农 B. 戈登?摩尔 C. 查尔斯?巴比奇

D.冯?诺依曼

7.设 X、Y、Z 分别代表三进制下的一个数字,若等式 XY + ZX = XYX 在三进制下成立,那么 同样在三进制下,等式 XY * ZX = ( )也成立。 A. YXZ B. ZXY C. XYZ D.XZY 8.Pascal 语言、C 语言和 C++语言都属于( )。 A. 面向对象语言 B. 脚本语言 C. 解释性语言 9.前缀表达式“+ 3 * 2 + 5 12 ” 的值是( )。 A. 23 B. 25 C. 37

D.编译性语言

D.

65

10.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多, 从而使得后者的效率受到影 响。而根据局部性原理,CPU 所访问的存储单元通常都趋于一个较小的连续区域中。于是, 为了提高系统整体的执行效率,在 CPU 中引入了( )。 A. 寄存器 B. 高速缓存 C. 闪存 D. 外存 11.一个字长为 8 位的整数的补码是 11111001,则它的原码是( )。 A. 00000111 B. 01111001 C. 11111001 D.10000111

By-SHBF

90

NOIP 基础知识要点一

12.基于比较的排序时间复杂度的下限是( ),其中 n 表示待排序的元素个数。 2 A. O(n) B. O(n log n) C. O(log n) D. O(n ) 13.一个自然数在十进制下有 n 位,则它在二进制下的位数与( )最接近。 n A. 5n B. n*log210 C. 10*log2 n D. 10 log2 n 14.在下列 HTML 语句中,可以正确产生一个指向 NOI 官方网站的超链接的是( A. <a url=http://www.noi,cn>欢迎访问 NOI 网站</a> B. <a href=http://www.noi,cn>欢迎访问 NOI 网站</a> C. <a> http://www.noi,cn </a> D. <a name=http://www.noi,cn>欢迎访问 NOI 网站</a> )。

15.元素 R1、R2、R3、R4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如果第 1 个出栈的是 R3, 那么第 5 个出栈的不可能是( )。 A. R1 B. R2 C. R4 D. R5 16. 双向链表中有两个指针域 llink 和 rlink,分别指向该结点的前驱及后继。设 p 指向链 表中的一个结点,它的左右结点均为非空。现要求删除结点 p,则下列语句序列中错误的是 ( )。 A.p^.rlink^.llink=p^.rlink; p^.llink^.rlink=p^.llink; delete p; B.p^.llink^.rlink=p^.rlink; p^.rlink^.llink = p^.llink; delete p; C.p^.rlink^.llink = p^.llink; p^.rlink^.llink ^.rlink = p^.rlink; delete p; D.p^.llink^.rlink = p^.rlink; p^.llink^.rlink^.link = p^.llink; delete p; 17. 一棵二叉树的前序遍历序列是 ABCDEFG,后序遍历序列是 CBFEGDA,则根结点的左子树 的结点个数可能是( )。 A.2 B. 3 C. 4 D. 5 18. 关于拓扑排序,下列说法正确的是( )。 A.所有连通的有向图都可以实现拓扑排序 B.对同一个图而言,拓扑排序的结果是唯一的 C.拓扑排序中入度为 0 的结点总会排在入度大于 0 的结点的前面 D.拓扑排序结果序列中的第一个结点一定是入度大于 0 的点 19.完全二叉树的顺序存储方案,是指将完全二叉树的结点从上到下、从左到右依次存放到 一个顺序结构的数组中。 假定根结点存放在数组的 1 号位置上, 则第 k 号结点的父结点如果 存在的话,应当存放在数组中的( )号位置。 A. 2k B. 2k+1 C. k/2 下取整 D. (k+1)/2

By-SHBF

91

NOIP 基础知识要点一

20. 全国青少年信息学奥林匹克系列活动的主办单位是( )。 A. 教育部 B. 科技部 C. 共青团中央 D. 中国计算机学会

三、问题求解(共 2 题,每题 5 分,共计 10 分) 1.LZW 编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编 码词典, 如果在编码的过程中遇到一个新的词条, 则该词条及一个新的编码会被追加到词典 中,并用于后继信息的编码。 举例说明,考虑一个待编码的信息串:“xyx yy yy xyx”。初始词典只有 3 个条目, 第一个为 x,编码为 1;第二个为 y,编码为 2;第三个为空格,编码为 3;于是串“xyx”的 编码为 1-2-1(其中-为编码分隔符),加上后面的一个空格就是 1-2-1-3。但由于有了一个 空格,我们就知道前面的“xyx”是一个单词,而由于该单词没有在词典中,我们就可以自 适应的把这个词条添加到词典里,编码为 4,然后按照新的词典对后继信息进行编码,以此 类推。于是,最后得到编码:1-2-1-3-2-2-3-5-3-4。 现在已知初始词典的 3 个条目如上述,则信息串“yyxy xx yyxy xyx xx xyx”的编码 是 2. 队列快照是指在某一时刻队列中的元素组成的有序序列。 现有 3 个正整数元素依次入队、 出队。已知它们的和为 8,则共有_________种可能的不同的队列快照(不同队列的相同快 照只计一次)。例如,"5 1"、"4 2 2"、""都是可能的队列快照;而"7"不是可能的队列快 照,因为剩下的 2 个正整数的和不可能是 1。 四、阅读程序写结果(共 4 题,每题 8 分,其中第 4 题(1)(2)各 4 分,共计 32 分) 1. var a1,a2,a3,x:integer; procedure swap(var a,b:integer); var t:integer; begin t:=a; a:=b; b:=t; end; begin readln(a1,a2,a3); if a1>a2 then swap(a1,a2); if a2>a3 then swap(a2,a3); if a1>a2 then swap(a1,a2); readln(x); if x<a2 then if x<a1 then writeln(x,‘ ’,a1, ‘ ’, a3, ‘ ’,a3) else writeln(a1,‘ ’,x, ‘ ’, a2, ‘ ’,a3) else if x<a3 then writeln(a1,‘ ’,a2, ‘ ’, x, ‘ ’,a3)

By-SHBF

92

NOIP 基础知识要点一

else end.

writeln(a1,‘ ’,a2, ‘ ’, a3, ‘ ’,x)

输入 91 2 20 77 输出:__________ 2. Var n,m,i:integer; function rSum(j:integer):integer; var sum:integer; begin sum:=0; while j<>0 do begin sum:=sum*10+(j mod 10); j:=j div 10; end; rSum:=sum; end; begin readln(n,m); for i:=n to m do if i=rSum(i) then write(I,’’); end. 输入:90 120 输出:__________ 3. var s:string; i:integer; m1,m2:char; begin readln(s); m1:=’’; m2:=’’; for i:=1 to length(s) do if s[i]>m1 then begin m2:=m1;

By-SHBF

93

NOIP 基础知识要点一

m1:=s[i]; end else if s[i]>m2 then m2:=s[i]; writeln(ord(m1),’ ’,ord(m2)); end. 输入:Expo 2010 Shanghai China 输出: 提示: 字符 ASCII 码 空格 32 ‘0’ 48 ‘A’ 65 ‘a’ 97

4. const num = 5; var n: integer; function r(n : integer) : integer; var i : integer; begin if n <= num then begin r := n; exit; end; for i :=1 to num do if r(n-i) < 0 then begin r:=i; exit; end; r:=-1; end; begin readln(n); writeln(r(n)); end. (1) 输入:7 输出:__________(4 分) (2) 输入 16 输出:__________(4 分)

By-SHBF

94

NOIP 基础知识要点一

五、完善程序 1.(哥德巴赫猜想)哥德巴赫猜想是指,任一大于 2 的偶数都可写成两个质数的和。迄今为 止,这仍然是一个著名的世界难题,被誉为数学王冠上的明珠。试编写程序,验证任一大于 2 且不超过 n 的偶数都能写成两个质数之和。 const size=1000; var n,r,I,j,k,ans:integer; p:array[1..size] of integer; tmp:Boolean; begin readln(n); r:=1; p[1]:=2; for i:=3 to n do begin ① ; for j:=1 to r do if I mod ② begin tmp:=false; break; end; if tmp then begin inc(r); ③ ; end; end;

=0 then

ans:=0; for i:=2 to (n div 2) do begin tmp:=false; for j:=1 to r do for k:=j to r do if i+i= ④ then tmp:=true; break; end; if tmp then inc(ans); end; writeln(ans); end.

begin

By-SHBF

95

NOIP 基础知识要点一

若输入 n 为 2010,则输出 都满足哥德巴赫猜想。



时表示验证成功,即大于 2 且不超过 2010 的偶数

2.(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到 河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏 灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要 一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需 要的时间是较慢的那个人单独过桥所花费的时间.现在输入 N(2<=N<1000)和这 N 个人单独过 桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸. 例如,有 3 个人甲、乙、丙,他们单独过桥的时间分别为 1 2 4,则总共最少需要 的时间为 7.具体方法是:甲 乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后 甲,丙在一起过桥到河的左岸,总时间为 2+1+4=7. CONST SIZE = 100; INFINITY = 10000; LEFT = true; RIGHT = false; LEFT_TO_RIGHT = true; RIGHT_TO_LEFT = false; var n, i : integer; time : array[1..Size] of integer; pos :array[1..Size] of Boolean; function max(a, b :integer) : integer; begin if a > b then max := a else max := b; end; function go(stage : boolean) : integer; var i, j, num, tmp, ans : integer; begin if (stage = RIGHT_TO_LEFT) then begin num := 0; ans :=0; for i := 1 to n do if pos[i] = Rignt then begin inc(num); if time[i] > ans then ans := time[i]; end;

By-SHBF

96

NOIP 基础知识要点一

if __________ then begin go := ans; exit; end; ans := INFINITY; for i := 1 to n – 1 do if pos[i] = RIGHT then for j := i+1 to n do if pos[j] = RIGHT then begin pos[i] := LEFT; pos[j] := LEFT; tmp := max(time[i], time[j]) + _______; if tmp < ans then ans := tmp; pos[i] := RIGHT; pos[j] := RIGHT; end; go := ans; end else if (stage = LEFT_TO_RIGHT) then begin ans := INFINITY; for i := 1 to n do if _______ then begin pos[i] := RIGHT; tmp := ________; if tmp < ans then ans := tmp; _________; end; go := ans; end else go := 0; end; begin readln(n); for i := 1 to n do begin read(time[i]); pos[i] := RIGHT; end; writeln(go(RIGHT_TO_LEFT)); end.

By-SHBF

97

NOIP 基础知识要点一

第十七届全国青少年信息学奥林匹克联赛初赛试题
( 普及组 pascal语言 两小时完成 )
一、单项选择题(共 20 题,每题 1.5 分,共计 30 分.每题有且仅有一个正确选项。) 1.在二进制下,1100011+( )=1110000。 A.1011 B.1101 C.1010 D.1111 2.字符“O”的 ASCII 码为 48,则字符“9”的 ASCII 码为( )。 A.39 B.57 C.120 D.视具体的计算机而定 3.一片容量为 8GB 的 SD 卡能存储大约( )张大小为 2MB 的数码照片。 A.1600 B.2000 C.4 000 D.16000 4.摩尔定律(Moore’s law)是由英特尔创始入之一戈登·摩尔(Gordon Moore)提出来的。 根据摩尔定律, 在过去几十年以及在可预测的未来几年, 单块集成电路的集成度大约每( ) 个月翻一番。 A.1 B.6 C.18 D.36 5. 无向完全图是图中每对顶点之间都恰有一条边的简单图。 己知无向完全图 G 有 7 个顶点, 则它共有( )条边。 A.7 B.21 C.42 D.49 6.寄存器是( )的重要组成部分。 A.硬盘 B.高速缓存 C.内存 D.中央处理器(CPU) 7.如果根结点的深度记为 1,则一棵恰有 2011 个叶结点的二叉树的深度最少是( )。 A.10 B.11 C.12 D.13 8.体育课的铃声响了,同学们都陆续地奔向操场,按老师的要求从高到矮站成一排。每个 同学按顺序来到操场时, 都从排尾走向排头, 找到第一个比自己高的同学, 并站在他的后面。 这种站队的方法类似于( )算法。 A.快速排序 B.插入排序 c.冒泡排序 D.归并排序 9.一个正整数在二进制下有 i00 位,则它在十六进制下有( )位。 A.7 B.13 C.25 D.不能确定 10.有人认为,在个人电脑送修前,将文件放入回收站中就是已经将其删除了。这种想法是 ( )。 A.正确的,将文件放入回收站意味着彻底删除、无法恢复 B.不正确的,只有将回收站清空后,才意味着彻底删除、无法恢复 c.不正确的,即使将回收站清空,文件只是被标记为删除,仍可能通过恢复软件找回 D.不正确的,只要在硬盘上出现过的文件,永远不可能被彻底删除 11.广度优先搜索时,需要用到的数据结构是( )。 A.链表 B.队列 C.栈 D.散列表 12.在使用高级语言编写程序时,一般提到的“空间复杂度”中的“空间”是指( )。 A.程序运行时理论上所占的内存空间 B。程序运行时理论上所占的数组空间 c.程序运行时理论上所占的硬盘空间 D.程序源文件理论上所占的硬盘空间 13. 在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素, 最坏情况下运行的时间 复杂度是( )。 A.O(I) B.O(10g n) C.O(n) D.O(n log n)

By-SHBF

98

NOIP 基础知识要点一

14. 生物特征识别, 是利用人体本身的生物特征进行身份认证的一种技术。 目前, 指纹识别、 虹膜识别、人脸识别等技术己广泛应用于政府、银行、安全防卫等领域。以下不属于生物特 征识别技术及其应用的是( )。

15.现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为 700、600、300、 200。那么,“也”字的编码长度是( )。 A.1 B.2 C.3 D.4 16.关于汇编语言,下列说法错误的是( )。 A.是一种与具体硬件相关的程序设计语言 B.在编写复杂程序时,相对于高级语言而言代码量较大,且不易调试 c.可以直接访问寄存器、内存单元、以及 I/O 端口 D.随着高级语言的诞生,如今己完全被淘汰,不再使用 17. ( )是一种选优搜索法,按选优条件向前搜索,以达到目标。当探索到某一步时,发 现原先选择并不优或达不到目标,就退回一步重新选择。 A.回溯法 B.枚举法 c.动态规划 D.贪心法 18.1956 年( )授予肖克利(William Shockley)、巴丁(John Bardeen)和布拉顿(Walter Brattain),以表彰他们对半导体的研究和晶体管效应的发现。 A.诺贝尔物理学奖 B.约翰·冯·诺依曼奖 C.图灵奖 D.高德纳奖(Donald E.Knuth Prize) 19.对一个有向图而言,如果每个节点都存在到达其他任何节点的路径,那么就称它是强连 通的。例如,右图就是一个强连通图。事实上,在删掉边( )后,它依然是强连通的。 A.a B.b C.c D.d

20.从 ENIAC 到当前最先进的计算机,冯·诺依曼体系结构始终占有重要的地位。冯·诺依 曼体系结构的核心内容是、( )。 A.采用开关电路 B.采用半导体器件 C.采用存储程序和程序控制原理 D.采用键盘输入 二、问题求解(共 2 题,每题 5 分,共计 10 分) 1.每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时,它才是有 效的。例如,00000000、01010011 都是有效的序列号,而 11111110 不是。那么,有效的序 列号共有______________个。 2.定义字符串的基本操作为:删除一个字符、插入一个字符和将一个字符修改成另一个字 符这三种操作。 将字符串 A 变成字符串 B 的最少操作步数, 称为字符串 A 到字符串 B 的编辑

By-SHBF

99

NOIP 基础知识要点一

距离。字符串“ABCDEFG”到字符串“BADECG”的编辑距离为_____________。 三、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. Var n,m,I,ans:integer; begin readln(n,m); ans:=O; i:=n; while i<=m d0 begin ans:=ans+i; inc(i); end; writeln(ans); end. 输入:10 20 输出: 2. Var map,tel:string; i:integer; begin map:=’22233344455566677778889999’; readln(tel); for i:=1 to length(tel) do if (tel[i] >= ’O’) and (tel[i] <= ’9’) then write(tel[i]) else if (tel[i]>=’A’) and (tel[i] <= ’Z’) then write(map[ord(tel[i])-0rd(’A’) +1]); end. 输入:CCF-NOIP-2011 输出:________________________ 3. const SIZE=100; Var n,i,sum,x:integer; a:array[1. .SIZE] of integer; begin readln(n); fillchar(a,sizeof(a),O); for i:=1 to n do begin read(x); inc(a[x]); end; i:=O; sum:=0; while sum<(n div 2 + 1) do begin inc(i);

By-SHBF

100

NOIP 基础知识要点一

sum:=sum+a[i]; end; writeln(i); end. 输入: 11 4 5 6 6 4 3 3 2 3 2 1 输出:_____________________ 4. Var n,m:integer; function solve(n,m:integer):integer; Var i,sum:integer; begin if m=1 then begin solve:=1; exit; end; sum:=O; for i:=1 to n-1 do sum:=sum+solve(i,m-1); solve:=sum; end; begin readln(n,m); writeln(solve(n,m)); end. 输入:7 4 输出:________________________ 四、完善程序(前 11 空,每空 2 分,后 2 空,每空 3 分,共计 28 分) 1. (子矩阵)输入一个 n1+m1 的矩阵 a,和 n2+m2 的矩阵 b,问 a 中是否存在子矩阵和 b 相等。若存在,输出所有子矩阵左上角的坐标;若不存在输出“There is no answer”。 const SIZE=50; var n1,m1,n2,m2,i,j,k1,k2:integer; a,b:array[1. .SIZE,1. .SIZE] of integer; good,haveAns:boolean; begin readln(n1,m1); for i :=1 to n1 do for j :=1 t0 m1 do read(a[i][j]); readln(n2,m2);

By-SHBF

101

NOIP 基础知识要点一

for i:=1 to n2 do for j:=1 to m2 do ① ; haveAns:=false; for i:=1 to n1-n2+1 do for j:=1 to ② do begin ③ ; for k1:=1 to n2 do for k2:=1 to ④ do if a[i+k1-1][j+k2-1]<>b[k1][k2】then good:=false; if good then begin writeln(i,’ ’,j); ⑤ ; end; end; if not haveAns then writeln(’There is no answer’); end. 2.(大整数开方)输入一个正整数 n(1<n<10100),试用二分法计算它的平方根的整数部分。 const SIZE=200; type hugeint=record len:integer; num:array[1. .SIZE]of integer; end; //len 表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推 var s:string; i:integer; target,left,middle,right:hugeint; function times(a,b:hugeint):hugeint; //计算大整数 a 和 b 的乘积 var i,j:integer; ans:hugeint; begin fillchar(ans,sizeof(ans),O); for i:=1 to a.1en do for j:=1 to b.1en do ① :=ans.num[i+j-1] +a.num[i] *b.num[j]; for i:=1 to a.1en+b.1en do begin

By-SHBF

102

NOIP 基础知识要点一

ans.num[i+1]:=ans.num[i+1] +ans.num[i] div 10; ② ; if ans.num[a.1en+b.1en]>0 then ans.1en:=a.1en+b.1en else ans.1en:=a.1en+b.1en-1; end; times:=ans; end; function add(a,b :hugeint) :hugeint; //计算大整数 a 和 b 的和 var i:integer; ans:hugeint; begin fillchar(ans.num,sizeof(ans.num),0); if a.1en>b.1en then ans.1en:=a.1en else ans.1en:=b.1en; for i:=1 to ans.1en do begin ans.num[i]:= ③ ; ans.num[i+1]:=ans.num[i+1]+ans.num[i]div 10; ans.num[i]:=ans.num[i]mod 10; end; if ans.num[ans.1en+1]>O then inc(ans.1en); add:=ans; end; function average(a,b:hugeint) :hugeint; //计算大整数 a 和 b 的平均数的整数部分 Var i:integer; ans:hugeint; begin ans:=add(a,b); for i :=ans.1en down to 2 do begin ans.num[i-1] :=ans.num[i-1] + ( ④ ) * 10; ans.num[i]:=ans.num[i] div 2; end; ans.num[1]:=ans.num[1] div 2; if ans.num[ans.1en]=0 then dec(ans.1en); average:=ans; end; function plustwo(a:hugeint):hugeint;

By-SHBF

103

NOIP 基础知识要点一

//计算大整数 a 加 2 后的结果 Var i:integer; ans:hugeint; begin ans:=a; ans.num[1]:=ans.num[1] +2; i:=1; while (i<=ans.1en) and (ans.num[i] >=10) do begin ans.num[i+1]:=ans.num[i+1] +ans.num[i] div 10; ans.num[i]:=ans.num[i] mod 10; inc(i); end; if_ans.num[ans.1en+1]>O then ⑤ ; plustwo:=ans; end; function over(a,b:hugeint):boolean; //若大整数 a>b 则返回 1,否则返回 O var i:integer; begin if( ⑥ )then begin over:=false; exit; end; if a.1en>b.1en then begin over:=true; exit; end; for i:=a.1en downto 1 do begin if a.num[i] <b.num[i] then begin over:=false; exit; end; if a.num[i] >b.num[i] then begin over:=true; exit; end;

By-SHBF

104

NOIP 基础知识要点一

end; over:=false; end; begin readln(s); fillchar(target.num,sizeof(target.num),O); target.1en:=length(s); for i:=1 to target.1en do target.num[i]:=ord(s[target.1en-i+1])⑦ ; fillchar(1eft.num,sizeof(1eft.num),0); left.1en:=1; left.num[1]:=1; right:=target; repeat middle:=average(1eft,right); if over( ⑧ ) then right:=middle else left:=middle; until over(plustwo(1eft),right); for i:=left.1en downto 1 do write(1eft.num[i]); writeln;

end.

By-SHBF

105


相关文章:
Noi知识点总提纲
Noi知识点总提纲_从业资格考试_资格考试/认证_教育专区。0. 算法的时空分析 0...和块 9.4.1 最小环 O 9.4.2 负权环 O 9.4.3 连通块 O /noip 10...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A:被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯 ·诺依曼 于 1945 年发表了一个 全新的...
NOIP初赛相关知识点及参考答案
相关知识点与参考答案一.单项选择题 1、操作系统是系统软件的核心,是有效利用...NOIP2010普及组初赛试题... 12页 2下载券 NOIP知识点总览 105页 5下载券 ...
信息学奥赛NOIP初赛复习知识点+基本函数
信息学奥赛 NOIP 初赛复习知识点+基本函数 1 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个全新的 " 存储程序...
NOIP初赛试题分析及知识点
NOIP初赛试题分析及知识点_IT/计算机_专业资料。NOIP初赛试题分析及知识点,初高中...NOIP知识点总览 105页 免费 NOIP初赛谈 29页 免费 NOIP初赛辅导 69页 1下载券...
noip复习提纲
noip复习提纲_IT/计算机_专业资料。noip复习提纲NOIP 初赛复习提纲综述:初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考 查的是知识,而...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: :被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 ...
NOIP NOI知识点与部分标程
NOIP NOI知识点与部分标程_IT/计算机_专业资料。NOIP NOI知识点与部分标程目录Contents 第一章 基本算法与数论 GCD & 扩展欧几里德算法 筛法求素数 欧拉函数 Ga...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》(推荐指数:4 颗星) 曹文,吴涛编著,知识点大杂烩,部分内容由学生...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(...知识点大杂烩,部分内容由学生撰写,但是对初赛知识点的覆盖还是做得 相当不错的...
更多相关标签:
noip初赛知识点 | noip复赛知识点 | noip知识点 | noip提高组初赛知识点 | noip提高组复赛知识点 | 中文核心期刊要目总览 | 中文核心期刊总览 | 北京skp品牌总览 |