1、软件水平考试（初级）程序员下午（应用技术）模拟试卷 47及答案与解析 1 阅读下列算法说明和算法，将应填入 (n)处的语句写在对应栏内。 1. 【说明】 实现连通图 G的深度优先遍历 (从顶点 v出发 )的非递归过程。 【算法】 第一步：首先访问连通图 G的指定起始顶点 v； 第二步：从 V出发，访问一个与 v(1)p，再从顶点 P出发，访问与 p(2)顶点 q，然后从 q出发，重复上述过程，直到找不到存在 (3)的邻接顶点为止。 第三步：回退到尚有 (4)顶点，从该顶点出发，重复第二、三步，直到所 有被访问过的顶点的邻接点都已被访问为止。 因此，在这个算法中应设一个栈保存被 (5)的顶点，以
2、便回溯查找被访问过顶点的未被访问过的邻接点。 2 阅读以下函数说明和 C语言函数，将应填入 (n)处的字句写在对应栏内。 【程序 2.1说明】 已知一个排好序的数组，现输入一个数，要求按原来的顺序规律，将它插入到数组中。 【程序 2.1】 #include stdioh #define N 100 void main() float aN+l,x; int i,p; printf(“输入已经排好序的数列： “); for(i=0; i N; i+) scanf(%f“, printf(“输入要插入的数： “); scanf(“%f“, for(i=0,p=N; i N; i+) if(x ai
3、) (1) break; for(i=N-1; i =p; i-) (2) (3) for(i=0; i =N; i+) prinff(“%ft“,ai); 【程序 2.2说明】 本程序用变量 count统计文件中字符的个数。 【程序 2.2】 #include stdio.h #include stdlib.h void main() FILE *fp; long count=0; if(fp=fopen(“letter.txt“,“r“)=NULL) printf(“can not open filen“); exit(0); while(!feof(fp) (4) count+; pri
4、ntf(“count=%dn“,count); (5) 3 阅读以下说明和 C语言函数，将应填入 (n)处的语句写在对应栏内。 【说明】 下面的程序构造一棵以二叉链表为存储结构的二叉树。 【函数】 BitTree *createbt(BitTree *bt) BitTree *q; struct node *s30; int j,i; char x; printf(“i,x=“); scant(“%d,%c“, while(i!=0 /生成一个结点 (1); q- lchild=NULL; q- rchild=NULL; (2) ; if (3) j=i/2; / j为 i的双亲结点 if(i
5、%2=0) (4); /i为 j的左孩子 else (5); /i为 j的右孩子 printf(“i,x=“); scanf(“%d,%c“, return si; 4 阅读以下说明和 C语言函数，将应填入 (n)处的语句写在 对应栏内。 【说明】 著名的四色定理指出任何平面区域均可以用 4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过 4种颜色的着色方案。 【函数】 # include stdio.h #define N 10 /*要着色的 N个区域 */ void output(int color) /*输出一种着色方案 colori的值为区域 i所着颜色 *
6、/ int i; for (i=0; i N; i+) printf(“%4d“, colori); printf(“n“); int back(int *ip, int colorj /*回溯 */ int c=4; while (c=4) if (*ip =0) return 0: -(*ip); c=(1); color*ip=-1; return c; /*检查区域 i，考查 c种颜色的可能性 */ int colorOK(iht i, int c, int adjN, int color) int j; for(j=0; j i; j+) if (2) return 0; retur
7、n 1; /*为区域 i选一种可着的颜色 */ int select(int i, int c, int adjN, int color) /*寻找各种着色方案 adjij=1表示区域 i与区域 j不相邻 */ int k; for (k=c; k =4; k+) /*4种颜色 */ if (colorOK(3) return k; return 0; int coloring(int adjN) int colorN, i, c, cnt; for (i=0; i N; i+) colori=-1: i=c=0; cnt=0; while (1) if (c=(4)=0) c=back( i
8、f (c=0) return cnt; else (5); i+; if(i=N) output(color); +cnt; c=back( else c=0; void main() int adjNN= 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1
9、, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0 ; printf(“共有 %d 组解 .n“, coloring(adj); 5 阅读下列说明和 Visual Basic代码，将应填入 (n)处的字句写在对应栏内。 说明 某小型家电超市开发了下面的程序，用以实现商品提货信息的汇总和输出功能。程序的运行界面如下图所示： 程序界面包含两个控件数组，分别是提货商品复选框控件数组 Check1以及提货数量文本框控件数组Text1(相同下标的复选框
10、和文本框相对应 )，提货清单的显示由 List控件实现，按钮 “打印清单 ”和 “清除 ”分别名为 Command1和 Command2。 Visual Basic代码 提货商品复选框的单击事件响应代码 Private Sub Check1_Click(Index As Integer)If Check1 (Index). Value = 1 Then (1). SetFocusEnd Sub按钮 “打印清单 ”的单击事件响应代码 Private Sub Command1_Click() Dim i, n, price As Integer, sum As Long, title As Str
11、ing sum = 0 For i = O To 4 Select Case i Case 0: title =“电视机 “: price = 3580 Case 1: title =“微波炉 “: price = 660 Case 2: title =“电冰箱 “: price = 1850 Case 3: title =“DVD“: price = 2880 Case 4: title =“空调 “: price = 2500 End Select If (2)= 1 And Textl(i). Text “ “ Then (3) title i =n;i+) /(1) if( listi
12、 = key)/(2) return i; return -1; void main( ) int A10 int key,count=0,pos; cout “ Enter a list of 10 integers:“; for(pos=0;pos 10;pos+) cin A; /(3) cout “ Enter a key; “; cin key; pos=0; while( pos = SeqSearch ( A, pos, 10, key) !=-1 ) count +; pos +; cout key “occurs“ count (count!=1?“ times“:“ tim
13、e“) “ in the list,“ endl; 第一种情况：输入 2 3 12 6 8 45 8 33 7输入 key： 8 输出： (4) 第二种情况：输入 2 3 126 8 45 8 33 7输入 k6y： 9 输出： (5) 7 阅读以下说明和 Java代码，将解答写入对应栏内。 【说明】 下面的程序中定义了两个方法求自然数 1 100的和。具体如下： int suml(int n)；利用循环求 1 n的和， int sum2(int n)；利用递归方法求和 1 n的和；在 main()方法中调用这两个方法求 1 100的和并显示。在程序的每条横线处填写一个适当的语句，使程序的功能
14、完整。 public class Sum public static void main (1) /1. 调用 sum1(int n),求 1 100的和 /标准输出 (2) (“1 100的和 :“ +sum1(100); /2. 调用 sum2(int n),求 1 100的和 /标准输出 (2) (“1 100的和 :“+sum2(100); static iht sum1( int n) int result=0; for(int i=1;i =n;i+) (3) retrun result; static int sum2(int n) if (4) return 1 else (5
15、) 软件水平考试（初级）程序员下午（应用技术）模拟试卷 47答案与解析 1 【正确答案】 (1)邻接的顶点 (2)邻接的且未被访问的 (3)未访问过 (4)未被访问过的 邻接点的 (5)访问过 【试题解析】 本题考查连通图的深度优先遍历算法的非递归过程。 在做题前，我们首先来了解一下图的遍历。和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。 连通图的深度优先遍历可定义如下：首先访问出发点 v，并将其标记为已访问过；然后依次从 v出发搜索 v的每个邻接点 w。若 w未曾访问过，则以 w为新的出发点继续进行深度优先遍历，直至图中所有和源点 v有路径
16、相通的顶点 (亦称为从源点可达的顶点 )均已被访问为止。其关键是每次遍历都是往下直 到最后再往回搜索，找到还未被访问过的邻接点的顶点，然后从该顶点出发，对它及下面的顶点进行深度优先遍历。下面来具体分析其算法。 第 (1)空在第二步中，在访问起始顶点 v后应该访问的结点，那么这个结点肯定是与起始顶点 v邻接的顶点，因此此空答案为 “邻接的顶点 ”。 第 (2)空是在访问 p顶点后应该访问的顶点，接下来应该也是访问与 p顶点邻接的顶点，但这个时候 p顶点的邻接顶点中有已经被访问过了的顶点，因此在访问前还需判断此顶点是否被访问过了，所以此空答案为 “邻接的且未被访问的 ”。 第 (3)空也在第二步中
17、， 结合前后的内容，可以知道此空是要判断是否还可以找到与当前访问顶点邻接而未被访问的顶点，根据上面分析，如果找不到，才往回搜索，因此此空答案为 “未访问过 ”。 第 (4)空是回退过程中要注意的地方，一般回退到还未被访问过的邻接点的顶点，接着访问这个未被访问过的邻接点。因此此空答案为 “未被访问过的邻接点的 ”。 第 (5)空是存放在栈中的内容，栈具有后进先出的特点，根据上面对深度优先遍历的分析可以知道，在回退的过程中需要用到被访问过的顶点，而且回退的过程是按遍历的顶点的顺序回退的，越后被访问的顶点越先被回退， 因此此空答案是“访问过 ”。 2 【正确答案】 (1)p=i (2)ai+1=ai
18、; (3)ap=x; (4)fgetc(fp); (5)fclose(fp); 【试题解析】 本题考查在 C语言中实现对数组的插入和对文件中字符个数的统计。 我们先来看程序 2.1。题目要求在程序 2.1中实现在排好序的数组中插入一个数，但不能改变数组中数字排序的规律。由于数组是已经排好序的，它有可能是按不递减的方法排序，也有可能是按不递增的方法排序。在插入时，从数组中第一个数开始，逐个进 行比较，直到找到比其大或相等的数，在其前面进行插入，在插入前应该先将数组中的元素逐个后移。 下面我们来看代码。代码中有三个循环，第 (1)空在第一个循环体下面的条件判断语句里，条件判断语句是判断要插入的数
19、J与数组中元素的大小，如果数 x小于数组中的元素，就执行第 (1)空的语句。从上面的分析，再结合第二个循环语句的条件，我们可以知道，此空的作用是记录数要插入的位置，并把这个结果存放在变量 p中，所以，答案为 p=i。 第 (2)空所在的位置是第二个循环体下面，根据分析，要完成的任务应该是将数组中要插入位置后 的元素逐个往后移动。所以，此空的答案为 ai+1=ai。 在完成了上述两空之后，再结合整个程序来看，很明显还有一个功能没有完成，那就是插入数 x，第 (3)空就是用于完成这个任务的。由于在代码的前面已经记录下了要插入的位置，所以，此空答案为 ap=x。 在程序 2.2中，题目要求完成的任务
20、是用变量 count统计文件中字符的个数，要实现对文件中字符个数的统计，首先需要我们判断出哪些是字符，这就涉及 C语言中对文件中字符的判定。此外，还需要我们掌握对文件的基本操作。 下面，我们来看程序 2.2的 代码。首先用一个条件判断语句来打开一个文件，如果打开成功，则执行下面的 while循环语句，循环体的功能是对文件中的内容逐个判断，如果是字符，则统计变量 count加 1，因此，第 (4)空的功能就是要找出文件中的所有字符。这里没有条件判断语句来判段是否是字符，需要用到 C语言中对文件处理的一个函数 fgetc()，其作用是可以取出文件中所有的字符，因此，此空答案为 fgetc(fp)。
21、 第 (5)空在代码的最后面，如果我们对文件操作很熟悉的话，不难发现文件在打开后还没有关闭，此空要实现的功能是关闭文件，因此，此空答 案为 fclose(fp)。 3 【正确答案】 (1)q- data=x (2)si=q (3)i!=1 (4)sj- lchild=q (5)sj-rchild=q 【试题解析】 本题考查二叉树的构造。 题目要求构造一棵二叉树，而二叉树的性质如下：如果对一棵有 n个结点的完全二叉树的结点按层序编号 (从第 1层到第 log2n+1层，每层从左到右 )，则对任一结点 i(1in)，有： (1)如果 i=1，则结点 i无双亲，是二叉树的根；如果 i 1，则其双亲是
22、结点i/2。 (2)如果 2i n，则结点 i为叶子结点，无左孩子：否则，其左孩子是结点 2i。 (3)如果 2i+1 n，则结点 i无右孩子；否则，其右孩子是结点 2i+1。 下面我们来看程序。程序中声明了一个结点指针数组，用来保存生成的树中结点。用从键盘输入的方式来确定要插入的字符 x和此结点在二叉树中的位置 i(这个位置是指在完全二叉树中编号的位置 )。 第 (1)空是在生成一个新结点后的操作，生成了一个新结点后，自然要将从键盘输入的字符 x值存放进来，以及修改结点的两个指针域。程序中指针域都赋了空 ，因此，第 (1)空的任务应该是将字符 x写进来，因此，此空答案为 q-data=x。
23、第 (2)空是在对结点完成操作后的操作，根据题目意思，生成的结点应该要保存到数组 s中，此数组是一个指针数组，保存结点时，是将结点的地址保存进数组中相应的位置，因此，此空答案为 sil=q。 第 (3)空是条件判断语句的条件，结合下面的程序可以知道，此条件语句用来判断当前结点是不是根结点，如果不是，才执行条件语句中的内容。根据上面的分析，如果 i=1，则结点 i无双亲，是二叉树的根，因此，此空的答案为 i!=1。 第 (4)空处后面有注释，说明 i是 j的左孩子结点，这个时候我们应该让 j结点的左孩子指针指向结点 i，此空就是要实现这一功能。而结点， j被存放在数组 s中的第 j个位置，因此，此空答案为 si- lchild=q。 从程序中很容易看出，第 (5)空与第 (4)空功能相似，只是说 i是 j的右孩子结点，因此，让 j结点的右孩子指针指向结点乙此空答案为 sj- rchild=q。 4 【正确答案】 (1)color*ip (2)adjij=1或等价形式 (4)n=1; (5)return n+sum2 (n-1); 【试题解析 】 此处为 Java主函数的参数，是固定写法。 Java程序的标准输出是调用 System包的 out对象的函数。循环累加。这是递归调用的结束条件。对 n-1进行递归调用，并返回 n和 n-1个整数和的和。
