程序填空专练一答案

《程序填空专练一答案》由会员分享，可在线阅读，更多相关《程序填空专练一答案（10页珍藏版）》请在金锄头文库上搜索。

1、程序填空程序填空 这部分题目得分率很低。没关系，尽量做吧。实在不会把一些简单的填好就行了。有 些题目即使不懂也能填出来：）比如：i:=i+1；i:=0； 注意经常问自己程序中有没有做下面的事：注意经常问自己程序中有没有做下面的事： 1）初始化(i:=0; j:=0; for i:=1 to n do ai:=0 之类的) 2）一些明显的动作： a.结果没有储存在需要的地方。 b.累加器没有做加法 c.输出 3)关键动作。 例如交换排序程序的“交换”操作等很明显需要完成的操作。 分析方法和写运行结果类似，注意分析变量和程序结构，理解变量和模块的作用是解 题的关键。 不熟练是不妨用自然语言描述一下

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

3、那些最基本的事。 5. 做完后，不要忘了把程序从前往后读两遍，看看是否完成了题目的任务；还要检查 一些细节性的问题，如“”还是“=” ，是 n-i，还是 n-i+1？ 下面举例给予说明。下面举例给予说明。 1.1.基础题（算法、数据结构很清楚、很朴素，送分！）基础题（算法、数据结构很清楚、很朴素，送分！） 程序的说明 本程序对随机产生的 100 个 0 到 50 之间的随机数用一个数组存放后进行排序，然后再 将其中重复出现的数进行删除，只保留一个，使得剩下的数中任何两个都不相同且连续存 储在原数组中。 const maxn=100; type arraytype=array 1maxn of

4、integer; var i,j,temp,current,tail:integer; a:arraytype; begin randomize; for i:=1 to maxn do ai:=random(51); for i:=1 to _ do for j:= _ _ to maxn do if aiai-1而 ai还要尽可能小；假设现在已求出了 a1ai-1， 那么为了满足“能组成尽可能多的不同整数” ，则 ai应该取 a1+a2+ai-1+1,这 样必然要设一个累加器，再看看程序：）还真是！所以得到：初始化 s:=0; 累加 s+aj; 赋值，注意多加 1：s+1； 那么怎么填呢？

5、它表示能组成的不同整数的个数，那为什么要扫描一遍数组呢？感 觉也应该是累加！其实我们应该充分发挥上面已填好的程序段，发现：6 个数为：1 2 4 8 16 32（哦，难怪说小于 33！让我更加坚信上面做的是对的！） ，很明显是二 进制数的问题吗？本质上就是一个求一个 6 位的二进制数最多能表示多少状态？答案为： 20+21+22+23+24+25=1+2+4+8+16+32。不要激动，看题目填什么？累加：t+ai。 3.3.复杂的问题描述复杂的问题描述+ +简单的程序简单的程序+ +细心地处理细节问题（细心地处理细节问题（19951995 年高中组年高中组 3 3） 设有一个实数，以字符串形式

6、存放于数组 x 中，用 x：array1Nof char 表示。其 中 x1若为-，表示负数；若为+、.或 ，则表示正数。若为数字，也认为是正 数。 例如 x=( ,2,0, ,3,.,5,%) 则表示 203.5 x=(-,1,., ,2,0,%) 则表示-1.2 约定：在字符串 x 中，除 x1外，其后可以包含有若干个.与 ，但仅以第一次出 现的为准，空格不起任何作用，并以字符%作为结束标志。 程序要求：将输入的字符串还原成实数输出（小数点后无用的 0 应除去） ，还原的结果 以下列形式存放（不需要输出） 。 F：数符。正数放 0，负数放 1。 A：array1N of integer;

7、存放数字，不放小数点。 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 : array110 of char;可放长度定为 10；首先读入字符串，然后处 理数的符号，在还原的过程中，需要判定整数部分与小数部分，同时去除多余的空格和小 数点，并约定输入是正确的，不用作出错检查。 只要程序段： For I := 1 to 10 do aI := 0; For I

8、 := 1 to 10 do read(xI); J := 0; f := 0; k := 0; b := 0; If x1 = - then begin _; _; End Else if x1 := then I := 2 Else I := 1; While _ do I := I + 1; While _ do BEGIN If (xI= 0) and (xI0 then while ak=0 do begin _ _ End; 解答：显然，蓝色的程序段是用来处理实数的符号的，所以根据约定应该是设置负 数标记，即 f:=1;根据 else 后面的句子，发现 i 为循环扫描的指针，所以应

9、该是确定下 一位置，即 i:=2； 很明显是过滤掉空格！所以填：（xi= ）and（iaj-1) and (ai1ak，显然是从小到大冒泡排序用。 小结：重视题目给出的每一个信息与程序中的哪些语句对应；如果没有样例，自己找小结：重视题目给出的每一个信息与程序中的哪些语句对应；如果没有样例，自己找 一个典型的，运行运行找出规律；程序的分块！一个典型的，运行运行找出规律；程序的分块！ 7.7.数据结构题（数据结构题（19991999 年高中组试题）年高中组试题） 问题描述求一棵树的深度与宽度。 算法说明树可用数组 tree:array1n,15of integer; 其中：treeI,1表示结点号

10、；treeI,2treeI,5所属结点 如上图可表示为： 12340 25670 38000 （1） （2）（3）（4） （5） （6） （7）（8）（9）（10） （11） （12） （13） 491000 50000 60000 7111200 80000 90000 100000 110000 12 13 0 0 0 13 0 0 0 0 在求解的过程中，用到数组 G:ARRAY1N,17OF INTEGER； 其中：GI,1表示父结点，GI,2表示层次， GI,3表示本结点号，GI,4GI,7表示子女结点； 同时，设 2 个指针 SP1（取数指针） ，SP2（存数指针） 程序清单： p

11、rogram exp3; const n=13; var i,j,k,sp1,sp2,n1,n2,jmax,p:integer; tree:array1n,15of integer; g :array1n,17of integer; begin for i:=1 to n do begin treei,1:=i; for j:=2 to 5 do read (treei,j);readln; end; sp1:=1;sp2:=1;g1,1:=0;g1,2:=1;g1,3:=1; for i:=4 to 7 do g1,i:=tree1,i-2; while_do begin p:=gsp1,2

12、;n2:=gsp1,3;_;j:=4; while _do begin n1:=gsp1,j;j:=j+1;_; gsp2,1:=n2;gsp2,2:=p;gsp2,3:=n1; for i:=1 to 4 do gsp2,i+3:=treen1,i+1; end; _; end; writeln(maxd=,gsp2,2); j:=1;k:=g1,2;jmax:=0; for i:=2 to sp2 do if _then j:=j+1 else begin if jjmax then jmax:=j; _;k:=g,2; end; if jjmax then jmax:=j; writel

13、n(max1=,jmax); end. 解答： 1） 本题的数据结构含义，首先要搞清楚：treei,j存储编号为 i 的结点的第 j 号孩子（2=j=5,即最多 4 个孩子） ，treei,j=0 表示不存在；gi,k是一个 队列，sp1 为读取队列用的指针,sp2 为存储队列用的指针。gi,1 存储 i 的 父结点，gi,2存储 i 所在的层次，gi,3存储本结点的编号 i，gi,4, gi,5,gi,6,gi,7存储 i 的孩子结点编号。列出 g 的表格形式，以便更加 直观！ 2） 程序关键在红色和蓝色的两段。先看红色段，显然表示队列非空时做， 所以应该填：sp1=sp2；变量 p 是用来

14、存放层次的，所以填：p:=p+1；为该 结点的孩子结点准备好层次；n2 是表示当前处理的结点号，n1 是表示 n2 的孩 子结点号(用 j 循环)，这个地方的循环是为了遍历本结点的所有孩子，所以 填：gsp1,j0；那么干什么呢？不要忘记一个重要的事情，队列的 读取都需要移动指针（sp1,sp2） ，所以正好，为下面的存入操作作准备，即 sp2:=sp2+1;为下一个结点的遍历操作作准备，即读指针下移： sp1:=sp1+1； 3） 下面看看蓝色的程序段，目的很明显是为了输出。再注意题目的目的：输出树 的宽度和深度！深度简单，其实就是 gsp2,2。题目也没有考你！那么剩 下的问题显然就是为了求宽度。方法也很简单，就是求每一层的宽度（即 gI,4gI,7中的非 0 个数，或者按本题的方法是看 gI,2中最多有几个数 相同） ，然后打擂台找出最大值。因此，填：gI,2=k，计算层次相同的元 素个数放在 j 中，用 j 与 jmax 打擂台，注意一层完了，j 值要还原，宽度至少 为 1,所以填：j:=1； （20002000 年高中组试题）问题与上一样，只是写程序的人不一样，具体的风格不同而已。年高中组试题）问题与上一样，只是写程序的人不一样，具体的风格不同而已。 小结：本