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

noip初赛谈


NOIP 初赛谈
? 知识是基础,能力最重要
NOIP 初赛考的知识点,大纲上有 3 块:计算机基本常识、计算机基本操作、程序设计 基本知识。具体来说:选择题考查的是计算机基本常识、基本操作和程序设计中的一些基 本数据结构与基本算法;而填空题更加重视能力(尤其是队列、栈、二叉树等数据结构、 数学问题、归纳法、数列和逻辑推理等)的考查;读程序写运行结果考察的是对

程序的理 解和跟踪,重在分析推理能力。读程序的 4 条题目往往有一定的层次,试卷中给出程序的 并不复杂,语句的含义容易明白,但是悟性好的选手总是很快就能体会到程序的设计思路 并得出正确的答案,机械模仿计算机手工逐步算出结果的同学往往做的很慢,造成时间不 够,而且容易失误;完善程序更是考察程序设计能力,尤其是在明确算法和数据结构的条 件下,如何编程。读程序和完善程序,需要在平时的学习中提高,经常阅读、讨论和研究 别人的优秀程序,提高自己的理解力和速度。

? 各种题型的解题经验(以 2002、2001 年试题为例)
选择题(30 分=20*1.5)
一般是比较容易得分的,不可错过! 程序设计方面的知识多是平时计算机课堂教学或课外活动中学到的,建议大家找全国 计算机等级考试(一、二级)的题目做做,一般不超过二级的知识点,知识要复习的系统 一些。新大纲和最近两年的考试不再考 DOS,但有 DOS 经验的选手可能会占一点便宜,因为 有些题目可以根据经验判断。另外,往更高层次发展的过程中,必要的 DOS 知识和命令还 是必须的。

? 分布:5-6 个数据结构或算法方面的基本知识(高中组更多一些! ! ! ) ;
2002 年初中组(16) :一个向量第一个元素的存储地址是 100,每个元素的长度是 2,则第 5 个元素的地址是( A) 110 B ) C) 100 D) 109 B) 108

2002 年初中组(17) :在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的 是( D ) A) 希尔排序 B) 起泡排序 C) 插入排序 D) 选择排序

2002 年初中组(19) :设有一个含有 13 个元素的 Hash 表(O~12),Hash 函数是:H(key)=key %

13,其中%是求余数运算。用线性探查法解决冲突,则对于序列(2、8、31、20、19、18、53、 27),18 应放在第几号格中( A) 5 B) 9 B ) 。 C) 4 D) 0

2002 年高中组(17) :按照二叉数的定义,具有 3 个结点的二叉树有( C )种。 A)3 B)4 C)5 D)6 2002 年高中组(18) :在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 ( B )倍。 A)1/2 B)1 C)2 D)4 2002 年高中组(19) :要使 1 . . .8 号格字的访问顺序为:8、2、6、5、7、3、1、4,则下 图中的空格中应填入( C ) 。 1 2 3 4 5 6 7 8 4 A)6 B)0 6 C)5 1 D)3 -1 7 3 2

2002 年高中组(20) :设栈 S 和队列 Q 初始状态为空,元素 e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6 依次通过栈 S,一个元素出栈后即进入队列 Q,若出队的顺序为 e 2 ,e 4 ,e 3 ,e 6 , e 5 ,e 1 ,则栈 S 的容量至少应该为( B ) 。 A)2 B)3 C)4 D)5 2001 年初中组(19) :在顺序表(2,5,7,10,14,15,18,23,35,41,52)中,用二分 法查找 12,所需的关键码比较的次数为( C )。 A)2 B)3 C)4 D)5 2001 年初中组(20) :若已知一个栈的入栈顺序是 1,2,3,?,n,其输出序列为 P1,P2, P3,?,Pn,若 P1 是 n,则 Pi 是( C )。 A)i B)n-1 C)n-i+1 D)不确定 2001 年高中组(17) :以下哪一个不是栈的基本运算( B )。 A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空

D)将栈置为空栈

2001 年高中组 (19) : 一棵二叉树的高度为 h, 所有结点的度为 0 或 2, 则此树最少有( B ) 个结点。 A)2 -1
h

B)2h-1

C)2h+1

D)h+1

2001 年高中组(20) :无向图 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)},对该图进行深度优先遍历,得到的顶点序列正确的是( D )。

A)a,b,e,c,d,f

B)a,c,f,e,b,d

C)a,e,b,c,f,d

D)a,b,e,d,f,c

? 2-3 个计算机中数的表示(补码、反码等)和进制问题;
2002 年初中组(12) :(0.5)10=( C )16。 A) 0.1 B) 0.75 C) 0.8 D) 0.25 2002 年初中组(14) :算式(2047)10 一(3FF)16+(2000)8 的结果是( A) (2048)10 B) (2049)10 C) (3746)8 D) (1AF7)16 A ) 。

2002 年高中组(3) :十进制书 11/128 可用二进制数码序列表示为: ( D A)1011/1000000 B)1011/100000000 C)0.001011 D)0.0001011 2002 年高中组(5) :已知 x =(0.1011010)2 ,则[ x / 2 ]补 =( A)0.1011101 B)11110110 C)0.0101101 D)0.100110 C

) 。

)2 。

2002 年高中组(15) :已知 A = 35H,A /\ 05H \/ A /\ 30H 的结果是: ( A)30H B)05H C)35H D)53H 2001 年初中组(7) :与二进制数 101.01011 等值的十六进制数为( A)A.B B)5.51 D)5.58 D

C

) 。

)。

C)A.51

2001 年初中组(9) :2KB 的内存能存储( A A)1024 B)516 C)2048 D)218

)个汉字的机内码。

2001 年高中组(3) :64KB 的存储器用十六进制表示,它的最大的地址码是( A)10000 B)FFFF C)1FFFF D)EFFFF

B

)。

? 3-4 个计算机的基本知识题(如 CPU、内存、总线、字长、体系结构、 外设等) ;
2002 年初中组(1) :微型计算机的问世是由于( C ) 的出现。 A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 2002 年初中组(2) :下列说法中正确的是( B ) 。 A) 计算机体积越大,其功能就越强 B) CPU 的主频越高,其运行速度越快 C) 两个显示器屏幕大小相同,则它们的分辨率必定相同 D)点阵打印机的针数越多,则能打印的汉字字体越多 2002 年初中组(4) :CPU 处理数据的基本单位是字,一个字的字长( D ) 。 D) 电子管电路

A) 为 8 个二进制位 C) 为 32 个二进制位

B) 为 16 个二进制位 D) 与芯片的型号有关 A ) 。

2002 年高中组(2) :中央处理器(CPU)能访问的最大存储器容量取决于( A) 地址总线 B)数据总线 C)控制总线 D)实际内存容量 2002 年高中组(11) :微型计算机中, ( C )的存取速度最快。 A)高速缓存 B)外存储器 C)寄存器 D)内存储器 2001 年初中组(8) :断电后计算机信息依然存在的部件为( A) 寄 存 器 B)RAM 存 储 器 储 D)运算器 C )。

C)ROM



2001 年初中组 (11) :说一台微机的 CPU 是用的 PII300,此处的 300 确切指的是( A)CPU 的主时钟频率 B)CPU 产品的系列号 C)每秒执行 300 百万条指令 D)此种 CPU 允许最大内存容量 2001 年初中组(17) :下列设备哪一项不是计算机输入设备( A)鼠标 B)扫描仪 C)数字化仪 D)绘图仪 C )。

A

)。

2001 年初中组(18) :在计算机硬件系统中,cache 是( D )存储器。 A)只读 B)可编程只读 C)可擦除可编程只读 D)高速缓冲

? 2-3 个多媒体(概念、组成、图片文件格式和相关软件使用知识等) 和网络方面(IP 地址、域名、EMAIL、协议等)的题目;
2002 年试题: 8)多媒体计算机是指( D ) 计算机。 A) 专供家庭使用的 B) 装有 CDROM 的 C) 连接在网络上的高级 D) 具有处理文字、图形、声音、影像等信息的 9) 在使用 E-mail 前, 需要对 Outlook 进行设置, 其中 ISP 接收电子邮件的服务器称为 ( A ) 服务器。 A)POP3 B)SMTP C)DNS D)FTP 10) 用画笔 (Paintbrush) 绘制图形并存储在文件中 , 该图形文件的文件名缺省的后缀为 ( B ) 。 A) .jpg B) .bmp C) .gif D).tiff 11)E-mail 地址中用户名和邮件所在服务器名之间的分隔符号是( A) # B) @ C) & D) $ B ) 。

13)IP v4 地址是由( B A) 16 B) 32 2001 年试题: 12)TCP/IP 协议共有( A)3 B)4

) 位二进制数码表示的。 c) 24 D) 8

C C)5

)层协议。 D)6

? 2-3 个 WIN98 及自带的基本工具软件(查找、磁盘工具) 和资源管理器方面(文件名、通配符等)的题目;
2002 年试题: 3)在 Windows98 中,通过查找命令查找文件时,若输入 F*.? , 则下列文件( 以被查到。 A) F.BAS B) FABC.BAS C) F.C D) EF. 5)资源管理器的目录前图标中增加"+"号,这个符号的意思是( B ) 。 A) 该目录下的子目录已经展开 B) 该目录下还有子目录未展开 C) 该目录下没有子目录 D) 该目录为空目录, 7)启动 WORD 的不正确方法是( C ) 。 A) 单击 Office 工具栏上的 Word 图标 B) 单击"开始"→"程序"→Word C) 单击"开始"→"运行",并输入 Word 按回车 D) 双击桌面上的"Word 快捷图标" 9)在树型目录结构中,不允许两个文件名相同主要是指( D ) 。 A) 同一个磁盘的不同目录下 B) 不同磁盘的同一个目录下 C) 不同磁盘的不同目录下 D) 同一个磁盘的同一个目录下 15)下列叙述中,错误的是( C ) 。 A) Excel 中编辑的表格可以在 Word 中使用 B) 用 Word 编辑的文本可以存成纯文本文件 C) 用记事本(Notepad)编辑文本时可以插入图片 D) 用画笔(Paintbrush)绘图时可以输入文字 8)在磁盘上建立子目录有许多优点, 下列描述中不属于建立子目录优点的是 ( A)便于文件管理 B)解决根目录中目录项个数有限问题 C)加快文件查找速度 D)节省磁盘使用空间 D ) 。 C ) 可

13) 在 WORD 文档编辑中实现图文混合排版时, 关于文本框的下列叙述正确的是 ( C ) 。 A)文本框中的图形没有办法和文档中输入文字叠加在一起,只能在文档的不同位置 B)文本框中的图形不可以衬于文档中输入的文字的下方

C)通过文本框,可以实现图形和文档中输入的文字的叠加,也可以实现文字环绕 D)将图形放入文本框后,文档中输入的文字不能环绕图形 2001 年试题: 14)以下对 Windows 的叙述中,正确的是( A )。 A)从软盘上删除的文件和文件夹,不送到回收站 B)在同一个文件夹中,可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式,将删除该应用程序对应的文件 D)不能打开两个写字板应用程序

?

其他:软件、病毒、使用习惯、ASCII 码和汉字编码等;
)。 D) FORTRAN

2002 年试题: 6)下列哪一种程序设计语言是解释执行的( B A) Pascal B) GWBASIC C) C++ 7)计算机病毒传染的必要条件是: ( B ) 。 A)在内存中运行病毒程序 C)在内存中运行含有病毒的可执行的程序 2001 年试题: 4)计算机软件保护法是用来保护软件( D A)编写权 B)复制权 C)使用权

B)对磁盘进行读写操作 D)复制文件

)的。 D)著作权

5)下面关于算法的错误说法是( B )。 A)算法必须有输出 B)算法必须在计算机上用某种语言实现 C)算法不一定有输入 D)算法必须在有限步执行后能结束 6)解释程序的功能是( C )。 A)将高级语言程序转换为目标程序 B)将汇编语言程序转换为目标程序 C)解释执行高级语言程序 D)解释执行汇编语言程序 13)应用软件和系统软件的相互关系是( B )。 A)后者以前为基础 B)前者以后者为基础 C)每一类都以另一类为基础 D)每一类都不以另一类为基础 16)计算机病毒是( B )。 A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒

填空(15 分左右,2-3 题)
这部分题目对数学要求要高一点,往往考查的是数学问题(如代数变形、组合、概论 统计等) ,数列(一般是考递推、递归、归纳法等) ,逻辑推理;也考查一些算法和数据结 构知识(如队列、栈、二叉树) 。建议大家多花一点时间做,尽量做对。 1.数组 A[30..100,20..100]以行优先的方式存储,每个元素占 8 个字节,且已知 A[40,30]的 地 址 为 20000, 则 A[60,90] 的 地 址 为 :_________________ 。 如 果 以 列 优 先 存 储 , 则 为:_________________。 解答:设数组首地址为 X,则:X+( (40-30)*(100-20+1)+(30-20) )* 8 = 20000 前面的行数 每行的列数 本行中序号 每个元素的基 则:X=13340,用上述的式子,不难算出: A[60,90]的地址:33340 列优先存储,只要稍微改动上述公式,结果略; ? 考查了数据结构中数组存储方式。还可以考数组基类型为记录的情况,可以问你同样 的问题;或者问你共占用多少空间! 2.(1998 年初中组)设栈 S 的初始状态为空,现有 5 个元素组成的序列{1,2,3,4,5},对该序 列在 S 栈上依次进行如下操作(从序列中的 1 开始,出栈后不在进栈):进栈,进栈,进栈,出栈, 进栈 , 出栈 , 进栈 , 问出栈的元素序列是 :_________, 栈顶指针的值为 ______ ,栈顶元素 为:___________________。 解答:出栈序列为{3,4},栈顶指针值为 3,栈顶元素为 5。 ? 考查了数据结构中的栈。还可以把栈和队列结合起来考!如下题: 3.如 2002 年高中组:设栈 S 和队列 Q 初始状态为空,元素 e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6 依次通过栈 S,一个元素出栈后即进入队列 Q,若出队顺序为 e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 , 则栈 S 的容量至少应该为______________。 解答:为 3。 4. (2000 年初中组)设循环队列中数组的下标范围是 1..n,其头尾指针分别为 f 和 r,则 其元素个数为:_____________________。 解答: (r-f+n)mod n ? 考查了数据结构中的队列。 5.中缀表达式、前缀表达式、后缀表达式(1997 年初中组) (1) 已知中缀表达式:A+B*C/D 求它的前缀表达式和后缀表达式? (2)已知前缀表达式:+△A*B△C {注△表示一元运算符负号,即△A 表示-A} 求它的中缀表达式和后缀表达式? 解答:画(二叉)表达式树。 (1)的结果:+A*B/CD;ABCD/*+

(2)的结果: (-A)+B*(-C) ;A△BC△*+

?

考查了数据结构中的表达式树。

6.(1998 年初中组) 已知一个数列 U1,U2,U3...Un...,往往可以找到一个最小的 K 值和 K 个数 a1,a2,..,ak,使得数列从某项开始都满足:U(n+k)=a1*U(n+k-1)+a2*U(n+k-2)+...... +akUn (式 A) 例如数列 1,1,2,3,5......可以发现:当 K=2,a1=1,a2=1 时,从第 3 项起(N>=1)满足: U(n+2)=U(n+1) + Un 试对数列 1^3 ,2^3 ,3^3 ,......,N^3,??,求 K 和 a1,a2,...ak,使得式 A 成立。 解答:解方程,先设 K=2,列出方程组: 2 2 2 a1*1 +a2*2 =3 2 2 2 a1*2 +a2*3 =4 以上方程组无整数解。再设 K=3,列出方程组: 2 2 2 2 a1*0 +a2*1 +a3*2 =3 2 2 2 2 a1*1 +a2*2 +a3*3 =4 2 2 2 2 a1*2 +a2*3 +a3*4 =5 以上方程的整数解为:a1=1,a2=-3,a3=3,此时 K=3。 ? 实质是考数学。 7.(1998 年高中组)给出一棵二叉树的中序遍历:DBGEACHFI 与后序遍历:DGEBHIFCA,画出 此二叉树。 8.(1996 年高中组)下面是一个利用完全二叉树特性,用顺序表来存储的一个二叉树,结点 数据为字符型(结点层次从小到大,同一层从左到右顺序存储,#表示空结点,@表示存储数据 结束)。 结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 数据 A B C # # D E # # # # # G F @ 请画出对应的二叉树。 解答:以上两题的图分别如下:

?

以上两题实质是考数据结构中的二叉树。还经常考二叉树的计数!如下题:

9.如: (2000 年初中组)已知按中序遍历二叉树的结果为:abc,问:有多少种不同形态的 二叉树可以得到这一遍历结果,并画出这些二叉树。 解答:5 种,形态如下:

10. (1999 年初中组)在磁盘的目录结构中,我们将与某个子目录有关联的目录数称为度。 例如下图

该图表达了 A 盘的目录结构:D1,Dll,…,D2 均表示子目录的名字。在这里,根目 录的度为 2,D1 子目录的度为 3,D11 子目录的度为 4,D12,D2,D111,D112,D113 的 度均为 1。不考虑子目录的名字,则可简单的图示为如下所示的树结构:

若知道一个磁盘的目录结构中,度为 2 的子目录有 2 个,度为 3 的子目录有 1 个,度 为 4 的子目录有 3 个。 试问:度为 1 的子目录有几个?

解答:一种方法是画图;另外,可以根据整棵树的入度=出度(因为任一根关联边连接 两个结点)这一性质推导,除根结点外的每个结点入度都是 1,所以总的入度 =1*x+1*2+1*1+1*3-1;每个叶结点的出度为 0,分支结点的出度为度数-1,根结点的出度就 是它的度,所以总的出度=0*x+(2-1)*2+(3-1)*1+(4-1)*3+1;算出:x=9。 ? 考查了计算机中的目录结构和树结构中的“度”的概念和性质。 11. (1998 年高中组)用邻接矩阵/邻接表表示下面的无向/有向图(略) 。 ? 考查了数据结构中的图的表示。 12.(1999 年初中)根据 Nocomachns 定理,任何一个正整数 n 的立方一定可以表示成 n 个 连续的奇数的和。 例如: 3 1 =1 3 2 =3+5 3 3 =7+9+11 3 4 =13+15+17+19 在这里,若将每一个式中的最小奇数称为 X,那么当给出 n 之后,请写出 X 与 n 之间的 关系表达式:_________________________。 解答:X=n*(n-1)+1 ? 考查代数和递推能力! 13. (2000 年高中组)设有一个共有 n 级的楼梯,某人每步可走 1 级,也可走 2 级,也可走 3 级,用递推公式给出某人从底层开始走完全部楼梯的走法。例如:当 n=3 时,共有 4 种走 法,即 1+1+1,1+2,2+1,3。 解答:两种方法,一是“猜”+“凑” ,从具体的 n=1,2,3……算起,只能算比较简单的, 容易错;二是用组合数学和归纳法进行推导,一般先假设 F(n)= a*F(n-1)+b*F(n-2) +c*F(n-3)+……,然后算 a,b,c……直到某个系数=0 就结束,再代入式子中。 F(1)=1 F(2)=2 F(3)=4 F(N)=F(N-3)+F(N-2)+F(N-1) (N≥4) 14. (2000 年初中组)有 2×n 的一个长方形方格,用一个 1×2 的骨牌铺满方格。例如 n=3 时,为 2×3 方格。此时用一个 1×2 的骨牌铺满方格,共有 3 种铺法:

?

试对给出的任意一个 n(n>0) ,求出铺法总数的递推公式。 解答:F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1) (n≥3) 以上两题,考察了归纳+加法原理+乘法原理+递归关系式!这是近年来的常见题。

15.(2002 年初中组) 将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 6 种排 法:红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红。 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法) 解答:35 排列组合和概率统计!

?

16. (1999 年高中组)将 Ln 定义为求在一个平面中用 n 条直线所能确定的最大区域数目。 例如:当 n=1 时,L1=2,进一步考虑,用 n 条折成角的直线(角度任意) ,放在平面上,能确 定的最大区域数目 Zn 是多少?例如:当 n=1 时,Z1=2(如下图所示) 当给出 n 后,请写出以下的表达式: 1 Ln = ______________ 2 Zn = _______________ 解答:本题实质是求直线或折线将一个平面分成的最大区域数,从两个方面考虑: (1) 求在一个平面中用 n 条直线所能确定的最大区域数; n=1,L1=2, F(1)=2 n=2,L2=4, F(2)=F(1)+2 n=3,L3=7, F(3)=F(2)+3 n=4,L4=11, F(4)=F(3)+4 ?? 所以, F(n)=F(n-1)+n 把上面的 n 个等式左右相加,化简得出:F(n)=2+2+3+4+??+n 即:L(n)=n*(n+1)/2+1 (2) 求在一个平面中用 n 条折线所能确定的最大区域数; n=1,Z1=2, F(1)=0+2 n=2,Z2=7, F(2)=1*(2*2-1)+4 n=3,Z3=16, F(3)=2*(2*3-1)+6 n=4,Z4=29, F(4)=3*(2*4-1)+8 ?? 所以, F(n)=(n-1)*(2*n-1)+2*n 即:Z(n)=(n-1)*(2*n-1)+2*n ? 几何+归纳+组合数学! 17.(1998 年初中组)某班有 50 名学生,每位学生发一张调查卡,上写 a,b,c 三本书的书 名,将读过的书打?,结果统计数字如下: 只读 a 者 8 人;只读 b 者 4 人;只读 c 者 3 人; 全部读过的有 2 人;读过 a,b 两本书的有 4 人;读过 a,c 两本书的有 2 人;读过 b,c 两 本书的有 3 人;问: (1)读过 a 的人数是 解答: (1)12 人 (2)30 人 (2)一本书也没有读过的人数是 。

方法:推理或集合表示如下: 下图中:a=8;b=4;c=3;abc=2;ab=4-abc=2;ac=2-abc=0;bc=3-abc=1; 读过 a 的人数为:a+ab+abc+ac=8+2+2+0=12 一本未读过的人:50-a-b-c-abc-ab-ac-bc=30

?

逻辑推理+集合运算及变形!

? 近两年 NOIP 初赛填空题举例:
2002 年高中(1) 在书架上放有编号为 1 ,2 , . . . ,n 的 n 本书。现将 n 本书全部取下然后再放回去, 当放回去时要求每本书都不能放在原来的位置上。例如:n = 3 时: 原来位置为:1 2 3 放回去时只能为:3 1 2 或 2 3 1 这两种 问题:求当 n = 5 时满足以上条件的放法共有多少种?(不用列出每种放法) 解答:f(n)=n*f(n-1)+- 1(n>1,且 n 为偶数时取+,n 为奇数时取-) f(1)=0 所以,当 n=5 时,满足以上条件的方法共有 44 种。 2002 年高中(2) 设有一棵 k 叉树,其中只有度为 0 和 k 两种结点,设 n 0 ,n k ,分别表示度为 0 和度 为 k 的结点个数,试求出 n 0 和 n k 之间的关系(n 0 = 数学表达式,数学表达式仅含 n k 、 k 和数字) 。 解答:n0 和 nk 之间的关系为:n0=(k-1) nk+1。 2002 年初中(1) 如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5 共五个车厢。 其中每个车 厢可以向左行走,也可以进入栈 S 让后面的车厢通过。 现已知第一个到达出口的是 3 号车厢,

请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。 出口← ← S↓ 解答:9 2002 年初中(2) 将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 6 种排法:红红黄黄黄 红 黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法) 解答:35 2001 年高中(1) 已 知 一棵 二叉 树 的结 点名 为 大写 英文 字 母, 其中 序 与后 序遍 历 的顺 序分 别 为: CBGEAFHDIJ 与 CGEBHFJIDA,则该二叉树的先序遍历的顺序为: 解答:ABCEGDFHIJ 2001 年高中(2) 平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不 在同一条直线上。问用这些点为顶点,能组成多少个不同四边形? 解答:2250 2001 年初中(1) 在 a,b,c,d,e,f 六 件 物 品 中 , 按 下 面 的 条 件 能 选 出 的 物 品 是: 。 (1)a,b 两样至少有一样 (2)a,d 不能同时取 (3)a,e,f 中必须有 2 样 (4)b,c 要么都选,要么都不选 (5)c,d 两样中选一样 (6)若 d 不选,则 e 也不选 解答: a,b,c,f 2001 年初中(2) 平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不 在同一条直线上。问用这些点为顶点,能组成多少个不同三角形? 解答:751。 1 2 3 4 5

阅读程序,写运行结果(25 分左右,3-4 题)

其实很容易,目的几乎是送分,而且占的分数很多,但得分率却不见得高。很容易不明 不白的就把分(全)丢了!!!

这部分程序考 3 个方面:
1. 程序设计语言本身,如循环、递归、值型参和变量型参数、跟踪变量等; 2. 归纳和数学运算能力; 3. 是否掌握了一些常用算法(程序段)的框架; 4. 细心、耐心等心理品质;灵感+编程的量等;

一般做这类题目的核心是找程序目的:
即这个程序想干什么。迄今为止考过的题目还没有“乱写”的,总有一点“写作目的” 的。抓住了它,不仅得出答案变得很容易了,而且对自己的结果也会比较有信心。

一般的解题步骤如下:
1. 从总体上通读程序,大致把握程序的目的和算法; 2. 猜测变量的作用,跟踪主要变量值的变化(列表) ,找出规律; 3. 将程序分段,理清每一小段的作用和目的(灵感+关键表达式和语句的领会) ; 4. 看清输入、按照输出格式,写出结果; 5. 带着得到的结果回到程序进行检查;

下面举几个例子。 ? 1.基本题(考语言本身,尤其是循环嵌套。1999 年初中组)
Program excpl; var x,y,y1,jk,j1,g,e:Integer; a:array[1..20] of 0..9; begin x:=3465; y:=264; jk:=20; for j1:=1 to 20 do a[j1]:=0; while y<>0 do begin y1:=y mod 10; y:=y div 10; while y1<>0 do begin g:=x; for e:=Jk downto 1 do begin g:=g+a[e]; a[e]:=g mod 10; g:=g div 10 end; y1:=y1-1 end;

jk:=jk-1 end; j1:=1; while a[j1]=0 do j1:=j1+1; for Jk:=j1 to 20 do write(a[jk]:4); writeln end. 程序运行结果为:___________________________。

解答:
程序不长,但是有一定的难度。高手最多半分钟就看懂了程序的意思,但初学者往往 算了很久得出了结果却是错的。下面我们还是先以一个初学者的身份分析一下这个程序。 记住,不要一开始就模拟电脑来一个个语句“执行”-------你算过自己是多少 Hz 的 CPU 没有?! 首先是看看变量的名字,可惜分区联赛题目中的变量不是 i 就是 j,很讨厌。i 和 j 一 般作为循环计数器,没有什么意思,因此不要管它了。然后要看变量在程序的哪里出现过, 着重看它与其它变量的相互引用关系,猜测它的作用。例如上题:x 只在 g:=x 中出现,暂 时不要管它,因为它很可能只是一个初始数据。y 有三处:1) while y<>0 do 2) y1:=y mod 10; 3) y:=y div 10; 很明显,y 每次少了最后一位数字,把这位数字给了 y1。有经验的选手应该体会到了什 么,不过我们继续。 现在我们知道了:y 对程序的作用是:每次提供最后一位给 y1,即 y1 每次的值依次是: 4,6,2 那么再看 y1,它出现在两个地方: 1)while y1<>0 do 2)y1=y1-1 很明显就是一个循环次数嘛!循环 y1 次! 再看 jk: 1)for e:=jk downto 1 do 2)jk:=jk-1 jk 作为循环初始值,居然一次比一次少...其原因有待进一步分析。 再看 j1: 1)for j1:=1 to 20 do a[j1]:=0; 2)j1:=1; 3)while a[j1]=0 do j1:=j1+1; 4)for Jk:=j1 to 20 do write(a[jk]:4); 显然,j1 和其它变量没有什么联系。1)是初始化,2)3)4)是输出数组 a。 再看 g: 出现的位置是几层循环之内了,应该很重要!一会儿再分析! 再看 e: 作为循环变量,没有什么意思。 通过变量分析,我们知道了:x,y 是数据,y 每次提供最后一位给 y1,循环 y1 次。j1

和 g 的作用有待分析。 下面根据程序结构,把程序分成几块,逐个研究。最主要的程序段是两个 WHILE 循环 中套一个 FOR 循环,三重循环! ! !其实,最外面一层很明确:判断什么时候结束(y=0) 。 前后都很简单,是一些变量和数组的初始化、输入、输出等,下面重点剖析核心程序段。 1) x:=3465; y:=264; jk:=20; for j1:=1 to 20 do a[j1]:=0; 输入与变量、数组的初始化,不要管它。 2)while y<>0 do begin y1:=y mod 10; y:=y div 10; while y1<>0 do begin << g:=x; for e:=Jk downto 1 do begin g:=g+a[e]; a[e]:=g mod 10; g:=g div 10 end; >> y1:=y1-1 end; jk:=jk-1 end; 3) j1:=1; while a[j1]=0 do j1:=j1+1; for Jk:=j1 to 20 do write(a[jk]:4); writeln 从前往后,找到<>0 的位置开始,输出数组元素的值(输出结果) ,也不要管它。 块 2 最重要。 它的思想是:每次取 Y 的最第位 y1,执行<<运算>>y1 次,每次把 jk 减 1。 现在最重要的是<<运算>>中的在干什么? 注意到最后输出的 a[],要留意 a[]的变化! a[e]总是取个位(g mod 10),g 每次少一位,和 a[e-1](别忘了 e 在循环!)相加... 难道是...高精度加法???RIGHT!

<<>>中只有 6 行,你可以模拟电脑“执行”几个语句在 找规律。方法是:把循环“展开” ,再写一个变量值表 即: 语句 执行后变量情况: g:=x; g:=g+a[e]; g=x+a[e]; a[e]:=g mod 10; a[e]:=x+a[e]的个位 g:=g div 10; g=(x+a[e])的前几位 g:=g+a[e-1]; g=(x+a[e])的前几位+a[e-1]; a[e-1]:=g mod 10; a[e-1]=a[e-1]+(x+a[e])的进位 ??

它执行了 y1 次,y1 每次都是 y 的个位!对了。程序就是在做 x*y 所以答案就是 3465*264=914760 再看它的输出格式,输出的应该是:___9___1___4___7___6___0

其实有经验的话,看到 g 这个变量名和 g:=g+a[e]; a[e]:=g mod 10;这几 个标志句子。就可以一下子知道程序的用意了。 总结一下本题:重点考循环嵌套的执行过程以及对除法运算中的商、余数的 基本方法;主要程序段可以通过列表了解变量的变化情况;要细心、耐心;题 目的本身没有多少值得研究的价值! ! !但有些题目纯粹考算法思路,如下面的 例子: ? 2. 算法题
program ex2; var i,j,n:longint; b:array [0..31] of 0..1; begin n=1999; i:=0; while n<>0 do begin b[i]:=n mod 2; i:=i+1; n:=n div 2 end; for j:=i-1 downto 0 do write(b[j]); end. 输出什么? 解答:很明显,是把十进制整数转换成二进制数,所以输出 11111001111

? 3.有些题目则是考数学,或根据一些基本规则重复地做某个操作。如:
program exp1 (imput,output); var i,,s,max: integer; a:array [1..10] of integer; begin for i:=1 to 10 do read (a[i]); max:=a[1] ;s:=a[1]; for i:=2 to 10 do begin if s<0 then s:=0; s:= s+a[i]; if s>max then max:=s

end; writeln(‘max=’, max) end. 输入:8 9 -1 24 6 5 11 15 -28 9 输出:max= 解答:本题主要做累加:s:= s+a[i];再根据结果打擂台。 但最关键的语句是:if s<0 then s:=0;它的作用是把 s<0 的前若干个元素 的和值屏蔽掉(置 0) 。了解了这一点,题目就很简单了。步骤如下: s<0? s=8 s>max? max=8; I=2 N 8+9=17 Y max=17; I=3 N 17-1=16 N max=17; I=4 N 16+24=40 Y max=40; I=5 N 10+6=46 Y max=46; I=6 N 46+5=51 Y max=51; I=7 N 51+11=62 Y max=62; I=8 N 62+15=77 Y max=77; I=9 N 77-28=49 N max=77; I=10 N 49+9=58 N max=77; 所以结果为:77。 小结:本质是求一个 n 长的整数数列的连续 x 长的子序列,要求子序列的和最大! 注意:s 和 max! ! !另外本题给的输入数据比较简单,所以有很多人没有完全懂 也算对了结果,把数据改成如下:-1 12 -103 65 34 -4 -27 8 -1234 9,问结 果是多少呢?答:9! ! !

? 4.考子程序的调用,尤其是递归或带参数(值参与变量型参数) ,如:
PROGRAM EX3; CONST N=10; VAR S,I : INTEGER; FUNCTION CO(I1:INTEGER) : INTEGER; VAR J1,S1 : INTEGER; BEGIN S1:=N; FOR J1:= (N-1) DOWNTO (N-I1+1) DO S1:= S1*J1 DIV (N-J1+1); CO:=S1 END; BEGIN S:=N+1; FOR I:= 2 TO N DO S:=S + CO(I); WRITELN(‘S=’,S); END.

解答过程: (1) 如果有子程序,一般先读主程序,了解主程序什么时候调用子程序?干什 么的?调用了多少次?本题调用了 n-1 次,并且累加函数的返回值! (2) 再单独阅读子程序,分析变量、参数和返回值,确定它的功能。本题函数 猛一看好象比较复杂,不过是通过一个循环结构完成累乘和累除,下面再 具体分析! (3) 通过列表,观察子程序中的变量变化情况,以便找出规律,确定子程序的 作用。本题如下: CO(2)=10*9/2 CO(3)=10*9*8/2/3 CO(4)=10*9*8*7/2/3/4 ?? 发现,好象是组合数学的公式:CO(i)=10!/(i!*(10-i)!) 即:C(m,n)=m!/(n!*(m-n)!)=m*(m-1)*??*(m-n+1)/n! (4) 所以结果很明确:C(10,0)+ C(10,1)+??+C(10,9)+ C(10,10)=722 总结:灵感来源于丰富的数学基础和经验!

完善程序(30 分=2*15)
这部分题目得分率很低。没关系,尽量做吧。实在不会把一些简单的填好就行了。有 些题目即使不懂也能填出来: )比如:i:=i+1;i:=0;

注意经常问自己程序中有没有做下面的事:
1)初始化(i:=0; j:=0; for i:=1 to n do a[i]:=0 之类的) 2)一些明显的动作: a.结果没有储存在需要的地方。 b.累加器没有做加法 c.输出 3)关键动作。 例如交换排序程序的“交换”操作等很明显需要完成的操作。 分析方法和写运行结果类似,注意分析变量和程序结构,理解变量和模块的作用是解 题的关键。 不熟练是不妨用自然语言描述一下。

一般的解题步骤:
1. 仔细阅读程序的目的和算法、数据结构的描述! 千万不要一激动一紧张,题目都没看透彻! ! ! 2. 把程序中的变量和题目中数据结构描述结合起来,记住关键变量的作用! 有时就能填出一些简单的空! ! !不信?! ! ! 3. 结合问题的算法描述和要求及步骤,把程序划分成几段,每段完成指定的功能! 千万不要忘记:这是完善程序,不是让你自己编! ! !一定要不断地结合题意和程序。 4. 逐步解决每段! 注意不要因为个别空而影响你对整个程序的把握,不知道的,先空在那儿,把知道

的填好,最后再收拾那些难点! ! ! 注意一定要提醒自己:程序中有没有做那些最基本的事。 5. 做完后,不要忘了把程序从前往后读两遍,看看是否完成了题目的任务;还要检查一 些细节性的问题,如“>”还是“>=” ,是 n-i,还是 n-i+1? 下面举例给予说明。

? 1.基础题(算法、数据结构很清楚、很朴素,送分! )
[程序的说明] 本程序对随机产生的 100 个 0 到 50 之间的随机数用一个数组存放后进行排序,然后再 将其中重复出现的数进行删除,只保留一个,使得剩下的数中任何两个都不相同且连续存 储在原数组中。 const maxn=100; type arraytype=array [1..maxn] of integer; var i,j,temp,current,tail:integer; a:arraytype; begin randomize; for i:=1 to maxn do a[i]:=random(51); for i:=1 to __ ① do for j:= _ ② _ to maxn do if a[i]<a[j] then begin temp:=a[i];a[i]:=a[j];a[j]:=temp end; for i:=2 to maxn do if __ ③ __ then a[i]:=-a[i]; tail:=0;current:=1; while _____ ④ _____ do begin while a[current]<0 do current:=current+1; tail:=tail+1; a[tail]:= __⑤__ ; current:=current+1 end; if ___⑥__ then begin tail:=tail+1; a[tail]:=0 end; for i:=1 to tail do write(a[i]:5); writeln end. [解答] 程序的思想已经不能再清楚了,因为要排序(很明显是冒泡排序) ,所以: ①maxn-1 ②i+1 那么如何删除呢?先分析一下变量的含义, current 和 tail 分别表示队列的头尾指针。

再看删的过程:好象是先做标记(置为负! ) ,然后从队首 current 开始找第 1 个没被做标 记(>0)的数,把它放到当前队尾 tail 的下一个位置。所以: ③a[i]=abs(a[i-1]) ④(current<=maxn) and (a[current]<>0) ⑤a[current] ⑥(a[tail]<>0) and (a[current]=0)

? 2.关键变量+特定的思想方法+灵感(1995 年初中组 2)
找出小于 33 的 6 个正整数,用这些整数进行加法运算,使得包括原来的整数在内能组 成尽可能多的不同整数。 例如:用 2,3,5 这三个数能可组成下面的数: 2, 3, 5, 2 + 3 = 5(但 5 已经存在) 2 + 5 = 7, 3 + 5 = 8, 2 + 3 + 5 = 10 所以用 2,3,5 能组成 6 个不同的数。 程序要求:输出所选的这 6 个数,以及能组成不同整数的个数。 算法提要:选择的这 6 个数,用来组成数时应该尽可能不重复,引入数组 A 保存找出 的这 6 个整数。 主要程序段: A[1] := 1; t := 0; For i := 2 to 6 do begin _________①________; for j := 1 to i - 1 do s := ______②_______; a[i] := _______③_______; end; For i:=1 to 6 do Begin t:= ______④______ ; WRITE(a[i], ' '); End; Writeln('能组成不同整数的个数:', t) 解答: 首先, 根据蓝色的程序段, 我们应该判断出③应该和 s 相关, 而②是为了计算 s, 所以本题的关键是变量 s 的含义。 不要着急,我们研究一下题目的例子和算法提要,发现:选择的 6 个数(a[i])应该 尽可能不重复;且 a[i]>a[i-1]而 a[i]还要尽可能小;假设现在已求出了 a[1]?a[i-1], 那么为了满足“能组成尽可能多的不同整数” ,则 a[i]应该取 a[1]+a[2]+?+a[i-1]+1,这 样必然要设一个累加器, 再看看程序: ) 还真是! ! ! 所以得到: ①初始化 s:=0; ②累加 s+a[j]; ③赋值,注意多加 1:s+1; 那么④怎么填呢?它表示能组成的不同整数的个数,那为什么要扫描一遍数组呢?感 觉也应该是累加! 其实我们应该充分发挥上面已填好的程序段, 发现: 6 个数为: 1 2 4

8 16 32(哦,难怪说小于 33!让我更加坚信上面做的是对的! ) ,很明显是二进制数 的问题吗?本质上就是一个求一个 6 位的二进制数最多能表示多少状态?答案为: 0 1 2 3 4 5 2 +2 +2 +2 +2 +2 =1+2+4+8+16+32。不要激动,看题目④填什么?累加:t+a[i]。

? 3.复杂的问题描述+简单的程序+细心地处理细节问题(1995 年高中组 3)
设有一个实数,以字符串形式存放于数组 x 中,用 x:array[1..N]of char 表示。其 中 x[1]若为'-',表示负数;若为'+'、'.'或' ',则表示正数。若为数字,也认为是正数。 例如 x=(' ','2','0',' ','3','.','5','%') 则表示 203.5 x=('-','1','.',' ','2','0','%') 则表示-1.2 约定:在字符串 x 中,除 x[1]外,其后可以包含有若干个'.'与' ',但仅以第一次出 现的为准,空格不起任何作用,并以字符'%'作为结束标志。 程序要求:将输入的字符串还原成实数输出(小数点后无用的 0 应除去) ,还原的结果 以下列形式存放(不需要输出) 。 F:数符。正数放 0,负数放 1。 A:array[1..N] of integer; 存放数字,不放小数点。 K:表示 A 中有效数字的个数。 J:表示小数点后的位数。 例如:数 203.24,还原后结果的存放是: F=0 A=(2, 0, 3, 2, 4) K=5 J=2 又如:数-33.0740,还原后结果的存放是: F=1 A=(3, 3, 0, 7, 4) K=5 J=3 算法提要:x : array[1..10] of char;可放长度定为 10;首先读入字符串,然后处理 数的符号,在还原的过程中,需要判定整数部分与小数部分,同时去除多余的空格和小数 点,并约定输入是正确的,不用作出错检查。 只要程序段: For I := 1 to 10 do a[I] := 0; For I := 1 to 10 do read(x[I]); J := 0; f := 0; k := 0; b := 0; If x[1] = '-' then begin ____________①____________; ____________②____________; End Else if x[1] := ' ' then I := 2 Else I := 1; While ________③_________ do I := I + 1;

While __________④___________ do BEGIN If (x[I]>= '0') and (x[I]<= '9') Then begin k:=k+1; ________⑤_______; If b=1 then ______⑥_______; end Else if (x[I]='.') and (b=0) then b := 1; I:=I+1 END; If j>0 then while a[k]=0 do begin __________⑦_________ __________⑧_________ End; 解答:显然,蓝色的程序段是用来处理实数的符号的,所以根据约定①应该是设置负 数标记,即 f:=1;根据 else 后面的句子,发现 i 为循环扫描的指针,所以②应该是确定下 一位置,即 i:=2; ③很明显是过滤掉空格!所以填: (x[i]=’ ’)and(i<10); ④也很明显,一个大循环,判断字符串是否扫描结束,即:x[i]<>’%’ 再看看 b 变量的含义:根据 else 子句,发现 b=1 表示整数部分结束!所以⑤是把一个 数字字符转换成数字填到数组 a 中(a[k]:=ord(x[i])-48) ;⑥填 j:=j+1;(j 表示小数点后 的位数); ⑦⑧很明显,是处理有小数、并且有多余的 0 的情况,所以为:j:=j-1;k:=k-1; 小结:注意程序前前后后看,发现变量的作用和含义! ! !

? 4.典型算法+数据结构(1996 年高中组 1/初中组 3)
四色问题: 设有下列形状的图形: (N=8) ,其编号 为 1,2,??,N。

图形之间的相邻关系用下面的邻接矩阵表示:

其中:1——相邻,0——不相邻。 1 [ 程序要求 ] 将上面图形的每一个部分涂上红 1 0 (1) ,黄(2) ,蓝(3) ,绿(4)四种颜色之一,要求 2 1 相邻的部分有不同颜色。 3 0 输入方式:邻接矩阵。 4 0 输出方式:区域、颜色。 5 0 [ 算 法 描 述 ] 用 数 组 R:ARRAY[1..N,1..N] OF 6 0 0..1 表示相邻关系,S:ARRAY[1..N] OF INTEGER 表示 7 1 颜色。 8 1 采用回溯的方法, 首先给第一个图形涂上红色 (1) , 然后在下面的图形中依次涂上其他颜色,当有矛盾时回溯解决。 [程 序] PROGRAM EXP2(INPUT,OUTPUT); CONST N=8; VAR I,J,K:INTEGER; R:ARRAY[1..N,1..N] OF 0..1; S:ARRAY[1..N] OF INTEGER; BEGIN FOR I:=1 TO N DO BEGIN FOR J:=1 TO N DO READ(R[I,J]); READLN END; ① ;I:=2; J:=1; WHILE I<=N DO BEGIN WHILE (J<=4) AND (I<=N) DO BEGIN K:=1; WHILE ② DO K:=K+1; IF K<I THEN ③ ELSE BEGIN ④ ; END END; IF J>4 THEN BEGIN I:=I-1; ⑤ END; END; FOR I:=1 TO N DO WRITELN(I,'?',S[I]) END. 解答:邻接矩阵+回溯法,步骤略,答案如下:

2 1 0 1 0 0 1 1 0

3 0 1 0 1 0 1 0 0

4 0 0 1 0 1 1 0 0

5 0 0 0 1 0 1 0 0

6 0 1 1 1 1 0 1 0

7 1 1 0 0 0 1 0 1

8 1 0 0 0 0 0 1 0

I:=I+1; J:=1

① ② ③ ④ ⑤

S[1]:=1; (K<I) AND (S[K]*R[I,J])<>J J:=J+1; S[I]:=J; J:=S[I]+1;

? 5.子程序及参数(1999 年初中组)
[问题描述] 下面程序的功能是从键盘读取 A,B 数组的元素,A,B 数组均已从小到大排好序(无相 同元素) ,现将 A,B 合并为数组 C,同样要求数组 C 也是从小到大排好序(有相同元素时只 保留一个) 。 程序中 N 表示数组 A,B 的长度,i,j,k 分别表示数组 A,B,C 的取数或存数的指针。 [程序清单] program excp3; const n=8;m=2*n; type arr1=array[1..n]of integer; arr2=array[1..m]of integer; var a,b:arr1;c:arr2;i,j,k:integer; procedure copy(x:arr1;var y:arr2;var i,j:integer); begin i:=i+1; y[i]:=x[j]; j:=j+1; end; begin for i:=1 to n do read(a[i]);readln; for i:=1 to n do read(b[i]);readln; i:=1;j:=1;___________①________ while__________②__________do if a[i]<b[j] then copy (a,c,k,i) else if b[j]<a[i] then copy (b,c,k,j) else begin copy(a,c,k,i); __________③__________ end; while__________④___________do copy(a,c,k,i); while__________⑤___________do copy(b,c,k,j); for i:=1 to k do write (c[i]:4); writeln; end. 解答:就本题而言,算法和题目本身对选手很清楚!线性表的归并操作在 NOIP 中考过

多次,不管是用数组来操作还是用链表操作;甚至还有一些题目是它的变形(比如多项式 的加法) 。 本题中的 copy 过程是关键, 好在题目并没有考到过程调用的语句 (关键是参数的书写) , 所以下面只要理解了过程的作用和 4 个参数的含义,题目就会很容易了。 答案:① k:=0 ② (i<=n)and (j<=n) ③ j:=j+1 ④ i<=n ⑤ j<=n

? 6.特定的算法(1999 年高中组 2)
[问题描述] 用生成法求出 1,2,?,r 的全排列(r<=8) [算法过程] 用数组:a:array[1..r]of integer ;表示排列; 初始化时,a[I]:=1(I=1,2,?.f) 设中间的某一个排列为 a[1],a[2],?a[r],则求出下一个排列的算法为: (1) 从后面向前找,直到找到一个顺序为止(设下标为 j,则 a[j-1]<a[j]) (2) 从 a[j]- a[r]中,找出一个 a[k]比 a[j-1]大的最小元素 (3) 将 a[j-1]与 a[K]交换 (4) 将 a[j],a[j+1]??a[r]由小到大排序。 [程序清单] program exp4; const r=7; var n,i,s,k,j,i1,t:intger; a:array[1..r]of integer; procedure print1; var ik:integer; begin for ik:=1 to r do write(a[ik]:8);writeln; end begin for i:=1 to r do __________①__________; print1; s:=1; for i:=2 to r do s:=s*i; s:=s-1; for i:=__________②__________do begin j:=r; while__________③_________do j:=j-1; 步骤 1 k:=j; for i1:=j+1 to r do

if __________④_________then k:=i1; 步骤 2 t:=a[j-1];a[j-1]:=a[k];a[k]:=t; 步骤 3 for i1:=j to r-1 do for k:=i1+1 to r do if __________⑤___________then 步骤 4 begin t:=a[i1];a[i1]:=a[k];a[k]:=t; end; print1; end; end. 解题步骤: 1) 首先,本题给出了关键而详细的算法说明,但没有给一个样例,下面我们结 合一个中间状态数据,看看如何生成下一个状态数据。 1 8 7 3 4 6 5 2 经过 4 步后得到:1 8 7 3 5 2 4 6 这样,你对程序的逻辑过程就很清楚了! ! ! 2) 把程序分段:如上 4 中颜色。 红色的过程表示输出,没问题! 蓝色的显然是初始化,所以①填:a[i]:=i; 绿色的表示统计总的方案数(并且已经输出了一个,所以-1) ; 紫色的程序段很明显是解决算法说明的 4 个步骤的,下面重点解决! 3) 看看 4 个步骤分别对应着哪些语句?注意对应和找关键动作! ! ! ②应该填:1 to s 或 s downto 1,但不能写成 2 to s; ③填:a[j-1]>a[j] ④填:(a[i1]>a[j-1]) and (a[i1]<a[k]) 复合条件缺一不可,经常考! ⑤填:a[i1]>a[k],显然是从小到大冒泡排序用。 小结:重视题目给出的每一个信息与程序中的哪些语句对应;如果没有样例,自己找 一个典型的,运行运行找出规律;程序的分块! ! !

? 7.数据结构题(1999 年高中组试题)
[问题描述]求一棵树的深度与宽度。 [算法说明]树可用数组 tree:array[1..n,1..5]of integer; 其中:tree[I,1]表示结点号;tree[I,2]——tree[I,5]所属结点 (1) (2) (3) (4)

(5) (6) (7) (8) (9) (10) (11) (12) (13)

如上图可表示为: 1 2 3 2 5 6 3 8 0 4 9 10 5 0 0 6 0 0 7 11 12 8 0 0 9 0 0 10 0 0 11 0 0 12 13 0 13 0 0

4 7 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

在求解的过程中,用到数组 G:ARRAY[1..N,1..7]OF INTEGER; 其中:G[I,1]表示父结点,G[I,2]表示层次, G[I,3]表示本结点号,G[I,4]——G[I,7]表示子女结点; 同时,设 2 个指针 SP1(取数指针) ,SP2(存数指针) [程序清单]: program exGp3; const n=13; var i,j,k,sp1,sp2,n1,n2,jmax,p:integer; tree:array[1..n,1..5]of integer; g :array[1..n,1..7]of integer; begin for i:=1 to n do begin tree[i,1]:=i; for j:=2 to 5 do read (tree[i,j]);readln; end; sp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1; for i:=4 to 7 do g[1,i]:=tree[1,i-2]; while__________①_________do begin p:=g[sp1,2];n2:=g[sp1,3];_________②________;j:=4; while _________③_________do begin n1:=g[sp1,j];j:=j+1;__________④_________; g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1; for i:=1 to 4 do g[sp2,i+3]:=tree[n1,i+1];

end; __________⑤_________; end; writeln('maxd=',g[sp2,2]); j:=1;k:=g[1,2];jmax:=0; for i:=2 to sp2 do if __________⑥__________then j:=j+1 else begin if j>jmax then jmax:=j; __________⑦________;k:=g[I,2]; end; if j>jmax then jmax:=j; writeln('max1=',jmax); end. 解答: 1) 本题的数据结构含义,首先要搞清楚:tree[i,j]存储编号为 i 的结点的第 j 号 孩子(2<=j<=5,即最多 4 个孩子) ,tree[i,j]=0 表示不存在;g[i,k]是一个队 列,sp1 为读取队列用的指针,sp2 为存储队列用的指针。g[i,1] 存储 i 的父结 点 , g[i,2] 存 储 i 所 在 的 层 次 , g[i,3] 存 储 本 结 点 的 编 号 i , g[i,4],g[i,5],g[i,6],g[i,7]存储 i 的孩子结点编号。列出 g 的表格形式,以 便更加直观! ! ! 2) 程序关键在红色和蓝色的两段。先看红色段,①显然表示队列非空时做??, 所以应该填:sp1<=sp2;变量 p 是用来存放层次的,所以②填:p:=p+1;为该 结点的孩子结点准备好层次;n2 是表示当前处理的结点号,n1 是表示 n2 的孩 子结点号(用 j 循环),③这个地方的循环是为了遍历本结点的所有孩子,所以 ③填:g[sp1,j]<>0;那么④⑤干什么呢?不要忘记一个重要的事情,队列的读 取都需要移动指针( sp1,sp2 ) ,所以正好,④为下面的存入操作作准备,即 sp2:=sp2+1;⑤为下一个结点的遍历操作作准备,即读指针下移:sp1:=sp1+1; 3) 下面看看蓝色的程序段,目的很明显是为了输出。再注意题目的目的:输出树 的宽度和深度!深度简单,其实就是 g[sp2,2]。题目也没有考你! ! !那么剩下 的 问 题 显 然 就 是 为 了 求宽 度 。 方 法 也 很 简 单 ,就 是 求 每 一 层 的 宽 度(即 g[I,4]~g[I,7]中的非 0 个数,或者按本题的方法是看 g[I,2]中最多有几个数 相同) ,然后打擂台找出最大值。因此,⑥填:g[I,2]=k,计算层次相同的元素 个数放在 j 中,用 j 与 jmax 打擂台,注意一层完了,j 值要还原,宽度至少为 1,所以⑦填:j:=1; (2000 年高中组试题)问题与上一样,只是写程序的人不一样,具体的风格不同而已。 小结:本题其实很重要的是队列的操作,经常出现的还有:堆栈操作、模拟法(解决 递归等问题的现场保护和恢复) 。

? 2001-2002 完善程序题目介绍!
略。

返回上页

(完)


更多相关文档:

noip初赛谈

noip初赛谈_学科竞赛_高中教育_教育专区。NOIP 初赛谈 ? 知识是基础,能力最重要 NOIP 初赛考的知识点,大纲上有 3 块:计算机基本常识、计算机基本操作、程序设计 ...

NOIP初赛谈

NOIP初赛谈_学科竞赛_初中教育_教育专区。NOIP 初赛谈 NOIP 初赛谈 知识是基础,能力最重要 NOIP 初赛考的知识点,大纲上有 3 块:计算机基本常识、计算机基本操作、...

NOIP初赛谈

NOIP初赛谈NOIP初赛谈隐藏>> NOIP 初赛谈知识是基础,能力最重要 知识是基础, NOIP 初赛考的知识点,大纲上有 3 块:计算机基本常识、计算机基本操作、程序设计 基本...

NOIP初赛谈

NOIP问题求解集合 10页 8财富值 NOIP初赛复习指南 30页 10财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

NOIP初赛谈3 阅读程序

NOIP 初赛谈 3 阅读程序 Page 1 of 8 NOIP 初赛谈 3 阅读程序 阅读程序,写运行结果(25 分左右,3-4 题) 其实很容易,目的几乎是送分,而且占的分数很多,但...

NOIP复赛谈

NOIP复赛谈_计算机软件及应用_IT/计算机_专业资料。NOIP 复赛谈 ? 复赛的命题 1. 准循大纲:考察常用的数据结构和基本算法; 2. 考察能力:包括阅读理解能力、构建...

NOIP2015提高组初赛C++试题

NOIP2015提高组初赛C++试题_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP2015提高组初赛C++试题_学科竞赛_高中教育_教育专区。 ...

NOIP复赛谈

NOIP复赛谈_学科竞赛_高中教育_教育专区。NOIP 复赛谈 ? 复赛的命题 1. 准循大纲:考察常用的数据结构和基本算法; 2. 考察能力:包括阅读理解能力、构建数学模型...

NOIP初赛复习(提高组)--精华版

NOIP初赛复习(提高组)--精华版_IT/计算机_专业资料。分区联赛初赛复习材料初赛...对于计算机病毒,我们不必谈虎变色,而应采取积极的防治态度。首先,要防止“病从 ...

noip初赛复习资料(全)

noip初赛复习资料(全)_学科竞赛_高中教育_教育专区。noip初赛复习资料(全) ...对于计算机病毒,我们不必谈虎变色,而应采取积极的防治态度。首先,要防止“病从 ...
更多相关标签:
noip2016初赛 | noip2015提高组初赛 | noip2016提高组初赛 | noip2016普及组初赛 | noip2016初赛试题 | noip2016初赛成绩 | noip2016浙江初赛成绩 | noip2015普及组初赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com