主题:[原创]NOIP初赛谈
QQ331373582
[专家分:1500] 发布于 2005-10-12 20:03:00
NOIP初赛谈
Ø 知识是基础,能力最重要
NOIP初赛考的知识点,大纲上有3块:计算机基本常识、计算机基本操作、程序设计基本知识。具体来说:选择题考查的是计算机基本常识、基本操作和程序设计中的一些基本数据结构与基本算法;而填空题更加重视能力(尤其是队列、栈、二叉树等数据结构、数学问题、归纳法、数列和逻辑推理等)的考查;读程序写运行结果考察的是对程序的理解和跟踪,重在分析推理能力。读程序的4条题目往往有一定的层次,试卷中给出程序的并不复杂,语句的含义容易明白,但是悟性好的选手总是很快就能体会到程序的设计思路并得出正确的答案,机械模仿计算机手工逐步算出结果的同学往往做的很慢,造成时间不够,而且容易失误;完善程序更是考察程序设计能力,尤其是在明确算法和数据结构的条件下,如何编程。读程序和完善程序,需要在平时的学习中提高,经常阅读、讨论和研究别人的优秀程序,提高自己的理解力和速度。
Ø 各种题型的解题经验(以2002、2001年试题为例)
l 选择题(30分=20*1.5)
一般是比较容易得分的,不可错过!
程序设计方面的知识多是平时计算机课堂教学或课外活动中学到的,建议大家找全国计算机等级考试(一、二级)的题目做做,一般不超过二级的知识点,知识要复习的系统一些。新大纲和最近两年的考试不再考DOS,但有DOS经验的选手可能会占一点便宜,因为有些题目可以根据经验判断。另外,往更高层次发展的过程中,必要的DOS知识和命令还是必须的。
Ø 分布:5-6个数据结构或算法方面的基本知识(高中组更多一些!!!);
2002年初中组(16):一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是( B )
A) 110 B) 108 C) 100 D) 109
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应放在第几号格中( B ) 。
A) 5 B) 9 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 6 1 -1 7 3 2
A)6 B)0 C)5 D)3
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)2h-1 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 ) 。
A) (2048)10 B) (2049)10 C) (3746)8 D) (1AF7)16
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 ]补 =( C )2 。
A)0.1011101 B)11110110 C)0.0101101 D)0.100110
2002年高中组(15):已知A = 35H,A /\ 05H \/ A /\ 30H 的结果是:( C )。
A)30H B)05H C)35H D)53H
2001年初中组(7):与二进制数101.01011等值的十六进制数为( D )。
A)A.B B)5.51 C)A.51 D)5.58
2001年初中组(9):2KB的内存能存储( A )个汉字的机内码。
A)1024 B)516 C)2048 D)218
2001年高中组(3):64KB的存储器用十六进制表示,它的最大的地址码是( B )。
A)10000 B)FFFF C)1FFFF D)EFFFF
回复列表 (共14个回复)
沙发
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:04:00
Ø 3-4个计算机的基本知识题(如CPU、内存、总线、字长、体系结构、外设等);
2002年初中组(1):微型计算机的问世是由于( C ) 的出现。
A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 D) 电子管电路
2002年初中组(2):下列说法中正确的是( B ) 。
A) 计算机体积越大,其功能就越强
B) CPU的主频越高,其运行速度越快
C) 两个显示器屏幕大小相同,则它们的分辨率必定相同
D)点阵打印机的针数越多,则能打印的汉字字体越多
2002年初中组(4):CPU处理数据的基本单位是字,一个字的字长( D ) 。
A) 为8个二进制位 B) 为16个二进制位
C) 为32个二进制位 D) 与芯片的型号有关
2002年高中组(2):中央处理器(CPU)能访问的最大存储器容量取决于( A )。
A) 地址总线 B)数据总线 C)控制总线 D)实际内存容量
2002年高中组(11):微型计算机中,( C )的存取速度最快。
A)高速缓存 B)外存储器 C)寄存器 D)内存储器
2001年初中组(8):断电后计算机信息依然存在的部件为( C )。
A)寄存器 B)RAM存储器 C)ROM存储 D)运算器
2001年初中组(11):说一台微机的CPU是用的PII300,此处的300确切指的是( A )。
A)CPU的主时钟频率 B)CPU产品的系列号
C)每秒执行300百万条指令 D)此种CPU允许最大内存容量
2001年初中组(17):下列设备哪一项不是计算机输入设备( C )。
A)鼠标 B)扫描仪 C)数字化仪 D)绘图仪
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地址中用户名和邮件所在服务器名之间的分隔符号是( B ) 。
A) # B) @ C) & D) $
13)IP v4地址是由( B ) 位二进制数码表示的。
A) 16 B) 32 c) 24 D) 8
2001年试题:
12)TCP/IP协议共有( C )层协议。
A)3 B)4 C)5 D)6
Ø 2-3个WIN98及自带的基本工具软件(查找、磁盘工具)
和资源管理器方面(文件名、通配符等)的题目;
2002年试题:
3)在Windows98中,通过查找命令查找文件时,若输入F*.? , 则下列文件( C ) 可以被查到。
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)在磁盘上建立子目录有许多优点,下列描述中不属于建立子目录优点的是( D )。
A)便于文件管理 B)解决根目录中目录项个数有限问题
C)加快文件查找速度 D)节省磁盘使用空间
13)在WORD文档编辑中实现图文混合排版时,关于文本框的下列叙述正确的是( C )。
A)文本框中的图形没有办法和文档中输入文字叠加在一起,只能在文档的不同位置
B)文本框中的图形不可以衬于文档中输入的文字的下方
C)通过文本框,可以实现图形和文档中输入的文字的叠加,也可以实现文字环绕
D)将图形放入文本框后,文档中输入的文字不能环绕图形
2001年试题:
14)以下对Windows的叙述中,正确的是( A )。
A)从软盘上删除的文件和文件夹,不送到回收站
B)在同一个文件夹中,可以创建两个同类、同名的文件
C)删除了某个应用程序的快捷方式,将删除该应用程序对应的文件
D)不能打开两个写字板应用程序
Ø 其他:软件、病毒、使用习惯、ASCII码和汉字编码等;
2002年试题:
6)下列哪一种程序设计语言是解释执行的( B )。
A) Pascal B) GWBASIC C) C++ D) FORTRAN
7)计算机病毒传染的必要条件是:( B )。
A)在内存中运行病毒程序 B)对磁盘进行读写操作
C)在内存中运行含有病毒的可执行的程序 D)复制文件
2001年试题:
4)计算机软件保护法是用来保护软件( D )的。
A)编写权 B)复制权 C)使用权 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)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒
板凳
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:05:00
Ø 3-4个计算机的基本知识题(如CPU、内存、总线、字长、体系结构、外设等);
2002年初中组(1):微型计算机的问世是由于( C ) 的出现。
A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 D) 电子管电路
2002年初中组(2):下列说法中正确的是( B ) 。
A) 计算机体积越大,其功能就越强
B) CPU的主频越高,其运行速度越快
C) 两个显示器屏幕大小相同,则它们的分辨率必定相同
D)点阵打印机的针数越多,则能打印的汉字字体越多
2002年初中组(4):CPU处理数据的基本单位是字,一个字的字长( D ) 。
A) 为8个二进制位 B) 为16个二进制位
C) 为32个二进制位 D) 与芯片的型号有关
2002年高中组(2):中央处理器(CPU)能访问的最大存储器容量取决于( A )。
A) 地址总线 B)数据总线 C)控制总线 D)实际内存容量
2002年高中组(11):微型计算机中,( C )的存取速度最快。
A)高速缓存 B)外存储器 C)寄存器 D)内存储器
2001年初中组(8):断电后计算机信息依然存在的部件为( C )。
A)寄存器 B)RAM存储器 C)ROM存储 D)运算器
2001年初中组(11):说一台微机的CPU是用的PII300,此处的300确切指的是( A )。
A)CPU的主时钟频率 B)CPU产品的系列号
C)每秒执行300百万条指令 D)此种CPU允许最大内存容量
2001年初中组(17):下列设备哪一项不是计算机输入设备( C )。
A)鼠标 B)扫描仪 C)数字化仪 D)绘图仪
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地址中用户名和邮件所在服务器名之间的分隔符号是( B ) 。
A) # B) @ C) & D) $
13)IP v4地址是由( B ) 位二进制数码表示的。
A) 16 B) 32 c) 24 D) 8
2001年试题:
12)TCP/IP协议共有( C )层协议。
A)3 B)4 C)5 D)6
Ø 2-3个WIN98及自带的基本工具软件(查找、磁盘工具)
和资源管理器方面(文件名、通配符等)的题目;
2002年试题:
3)在Windows98中,通过查找命令查找文件时,若输入F*.? , 则下列文件( C ) 可以被查到。
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)在磁盘上建立子目录有许多优点,下列描述中不属于建立子目录优点的是( D )。
A)便于文件管理 B)解决根目录中目录项个数有限问题
C)加快文件查找速度 D)节省磁盘使用空间
13)在WORD文档编辑中实现图文混合排版时,关于文本框的下列叙述正确的是( C )。
A)文本框中的图形没有办法和文档中输入文字叠加在一起,只能在文档的不同位置
B)文本框中的图形不可以衬于文档中输入的文字的下方
C)通过文本框,可以实现图形和文档中输入的文字的叠加,也可以实现文字环绕
D)将图形放入文本框后,文档中输入的文字不能环绕图形
2001年试题:
14)以下对Windows的叙述中,正确的是( A )。
A)从软盘上删除的文件和文件夹,不送到回收站
B)在同一个文件夹中,可以创建两个同类、同名的文件
C)删除了某个应用程序的快捷方式,将删除该应用程序对应的文件
D)不能打开两个写字板应用程序
Ø 其他:软件、病毒、使用习惯、ASCII码和汉字编码等;
2002年试题:
6)下列哪一种程序设计语言是解释执行的( B )。
A) Pascal B) GWBASIC C) C++ D) FORTRAN
7)计算机病毒传染的必要条件是:( B )。
A)在内存中运行病毒程序 B)对磁盘进行读写操作
C)在内存中运行含有病毒的可执行的程序 D)复制文件
2001年试题:
4)计算机软件保护法是用来保护软件( D )的。
A)编写权 B)复制权 C)使用权 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)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒
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,列出方程组:
a1*12+a2*22=32
a1*22+a2*32=42
以上方程组无整数解。再设K=3,列出方程组:
a1*02+a2*12+a3*22=32
a1*12+a2*22+a3*32=42
a1*22+a2*32+a3*42=52
以上方程的整数解为: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,问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。
10.(1999年初中组)在磁盘的目录结构中,我们将与某个子目录有关联的目录数称为度。
该图表达了A盘的目录结构:D1,Dll,…,D2均表示子目录的名字。在这里,根目录的度为2,D1子目录的度为3,D11子目录的度为4,D12,D2,D111,D112,D113的度均为1。不考虑子目录的名字,则可简单的图示为如下所示的树结构:
3 楼
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:06:00
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的人数是 (2)一本书也没有读过的人数是 。
解答:(1)12人 (2)30人
方法:推理或集合表示如下:
下图中: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
4 楼
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:07:00
Ø 逻辑推理+集合运算及变形!
Ø 近两年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号车厢,请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。
出口← ← 1 2 3 4 5
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。
l 阅读程序,写运行结果(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.
程序运行结果为:___________________________。
5 楼
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:07:00
解答:
程序不长,但是有一定的难度。高手最多半分钟就看懂了程序的意思,但初学者往往算了很久得出了结果却是错的。下面我们还是先以一个初学者的身份分析一下这个程序。记住,不要一开始就模拟电脑来一个个语句“执行”-------你算过自己是多少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!
它执行了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.
6 楼
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:08:00
解答过程:
(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
总结:灵感来源于丰富的数学基础和经验!
l 完善程序(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位的二进制数最多能表示多少状态?答案为:20+21+22+23+24+25=1+2+4+8+16+32。不要激动,看题目④填什么?累加:t+a[i]。
7 楼
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:09:00
那么④怎么填呢?它表示能组成的不同整数的个数,那为什么要扫描一遍数组呢?感觉也应该是累加!其实我们应该充分发挥上面已填好的程序段,发现:6个数为:1 2 4 8 16 32(哦,难怪说小于33!让我更加坚信上面做的是对的!),很明显是二进制数的问题吗?本质上就是一个求一个6位的二进制数最多能表示多少状态?答案为:20+21+22+23+24+25=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。
图形之间的相邻关系用下面的邻接矩阵表示
8 楼
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:10:00
其中:1——相邻,0——不相邻。
[程序要求] 将上面图形的每一个部分涂上红(1),黄(2),蓝(3),绿(4)四种颜色之一,要求相邻的部分有不同颜色。
输入方式:邻接矩阵。
输出方式:区域、颜色。
[算法描述] 用数组R:ARRAY[1..N,1..N] OF 0..1表示相邻关系,S:ARRAY[1..N] OF INTEGER 表示颜色。
采用回溯的方法,首先给第一个图形涂上红色(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
④ ; I:=I+1; J:=1
END
END;
IF J>4 THEN BEGIN
I:=I-1; ⑤
END;
END;
FOR I:=1 TO N DO WRITELN(I,'à',S[I])
END.
解答:邻接矩阵+回溯法,步骤略,答案如下:
① 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.
9 楼
QQ331373582 [专家分:1500] 发布于 2005-10-12 20:11:00
解题步骤:
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 0
2 5 6 7 0
3 8 0 0 0
4 9 10 0 0
5 0 0 0 0
6 0 0 0 0
7 11 12 0 0
8 0 0 0 0
9 0 0 0 0
10 0 0 0 0
11 0 0 0 0
12 13 0 0 0
13 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年高中组试题)问题与上一样,只是写程序的人不一样,具体的风格不同而已。
小结:本题其实很重要的是队列的操作,经常出现的还有:堆栈操作、模拟法(解决递归等问题的现场保护和恢复)。
10 楼
天空飞雪 [专家分:960] 发布于 2005-10-12 20:38:00
谢谢,但不懂noip是什么??
我来回复