1、软件水平考试（初级）程序员下午（应用技术）模拟试卷 30 及答案与解析 1 阅读下列算法说明和算法，将应填入 (n)处的语句写在对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数，本算法使用了二分 (折半 )插入法对一个无序数组 R1n进行排序。排序思想是对一个待插入元素，先通过二分法 (折半 )找到插入位置，后移元素后将该元素插入到恰当位置。 (假设 R中的元素互不相同 ) 算法 1变量声明 X: Data Type i,j,low, high,mid,r:0n 2每循环一次插入一个 Ri 循环： i以 1为步长，从 2到 n，反复执行。 (1)准备 XRi;(1); highi -
2、1; (2)找插入位置 循环：当 (2)时，反复执行。 (3) 若 X.key Rmid.key 则 highmid -1; 否则 (4) (3)后移 循环： j以 -1为步长，从 (5)，反复执行。 Rj+1Rj (4)插入 RlowX 3算法结束 2 阅读以下函数说明和 C语言函数，将应填入 (n)处的语句写在对应栏内。 【函数 2.1说明】 有 1、 2、 3、 4四个数字，输出由这些数字组成的互不相同且无重、复数字的三位数。 【函数 2.1】 main() int i,j,k; printf(“n“); for(1) /*以下为三重循环 */ for(j=1; j 5;j+) for
3、(k=1;k 5;k+) if (2) /*确保 i, j, k 三位互不相同 */ printf(“%d,%d,%dn“,i,j,k); 【函数 2.2说明】 计算并输出 100之内的素数，每行输出 10个，超过 10个则换行。 【函数 2.2】 #include stdio.h #include “math.h“ #define N 101 main() int i,j,line,aN; for(i=2;i N;i+)(3); for(i=2;i sqrt(N);i+) for(j=i+1;j N;j+) if(ai!=0 printfCn“); for(i=2,line=0;i N;i+
4、) if(ai!=0) prinff(“%5d“,ai); (5); if(line=10) prinff(“n“); line=0; 3 阅读以下说明和 C语言函数，将应填入 (n)处 的语句写在对应栏内。 【说明】 设串 s和串 t采用顺序存储结构，编写函数实现串 s和串 t的比较操作，要求比较结果包括大于、小于和等于 3种情况。 【函数】 int StrCompare(SStrType s, SStrType t) int n=s.length, m=(1), i,j,tag; i=0; j=0; while(2) if(3) i+; j+; else if(s.stri t.strj)
5、 tag=1; return tag; else tag=-1; return tag; if(n=m) tag=0; else if(4) tag=1; else if(n m) tag=-1; (5); 4 阅读以下说明和 C语言函数，将应填入 (n)处的语句写在对应栏内。 【说 明】 著名的四色定理指出任何平面区域均可以用 4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过 4种颜色的着色方案。 【函数】 # include stdio.h #define N 10 /*要着色的 N个区域 */ void output(int color) /*输出一种着色方
6、案 colori的值为区域 i所着颜色 */ 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+) i
7、f (2) return 0; return 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) i
8、f (c=(4)=0) c=back( if (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
9、, 1, 1, 1, 1, 0, 0, 1, 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 阅读以下说明及 C+程序代码，将应填入 (n)处的语句写在对应栏内。 【说明】 本程序的功能是实现任意两个大整数的乘法运算，例如： 输入整数 1： 8934793850094505800243958034985058 输入整数 2： 234584950989689084
10、095803583095820923 二者之积： 209596817742739508050978890737675662366433464256830959194834854876 8534 【 C+代码】 #include iostream.h const int MAXINPUTBIT=100; const int MAXRESULTBIT=500; class LargeNumber int i,j; int temp; int oneMAXINPUTBIT+1; int onebit; /one的位数 int twoMAXINPUTBIT+1; int twobit; /two的位数
11、 int resultMAXRESULTBIT+1; public: LargeNumber(); LargeNumber(); int inputone(); /出错返叫 0，否则返回 1 int inputtwo(); /同上 void multiplication(); /乘 void clearresult(); /清零 void showresult(); /显示 ; LargeNumber LargeNumber() for(i=0;i =MAXINPUTBIT;i+) onei=0; twoi=0; onebit=0; twobit=0; inputone(); inputtwo
12、(); LargeNumber LargeNumber() int LargeNumber inputone() char NumberMAXINPUTBIT+1; cout “Please enter one:“; cin Number; i=0; j=MAXINPUTBIT; while(Numberi!=0) i+; onebit=i; for(i-;i =0;i-,j-) if(int(Numberi) =48 /由字符转换为数字 else return 0; return 1; int LargeNumber inputtwo() char NumberMAXINPUTBIT+1;
13、cout “Please enter two:“; cin Number; i=0; j=MAXINPUTBIT; while(Numberi!=0) i+; twobit=i; for(i-;i =0;i-,j-) if(int(Numberi) =48 /由字符转换为数字 else return 0; return 1; void LargeNumber multiplication() /乘法 clearresult(); int m; for(i=MAXINPUTBIT;i =0;i-) temp=twoi; for(j=(2),m=MAXINPUTBIT;m =0;m-,j-) re
14、sultj+=temp*onem; if(resultj 9) resultj-1+=resultj/10; (3); cout “one*two=“; showresult(); void LargeNumber showresult() i=0; while(resulti=0 if(i MAXRESULTBIT) cout “0“; /输出 0 for(;i =MAXRESULTBIT;i+) cout (4); cout endl; void LargeNumber clearresult() for(i=0;i =MAXRESULTBIT;i+) (5); void main() L
15、argeNumber a; a.multiplication(); 6 阅读以下说明和 Java代码，回答问题 1和问题 2，将解答填写在对应栏内。 【 Java代码】 class usethread implements (1) int num usethread(int n) num=n; public void (2) for(int i=0;i 3;i+) System.out.println(“running:“+num); System.out.println(“finished:“+num); public class multhread public static void m
16、ain(String args) (3) InterruptedException Thread m1=new Thread(new usethread(1); Thread m2=new Thread(new usethread(2); m1.start(); m2.start(); m1.join(); m2.join(); 【问题 1】 补充完整上面 Java代码中 (n)处。 【问题 2】 写出上面 Java代码运行的结果。 软件水平考试（初级）程序员下午（应用技术）模拟试卷 30 答案与解析 1 【正确答案】 (1)low1 (2)low =high (3)midint(low+hi
17、gh)/2) (4)lowmid+1 (5)i -1到 low 【试题解析】 本题考查使用二分插入法对无序数组排序的伪码实现。 在做题前，我们需要先大概明白二分插入法的基本思想和步骤，其基本思想是(设 Rlow， ， high是当前的插入区间 )： (1)将要插入的数取出放在 X中； (2)确定区间的中点位置： mid=(low+high)/2； (3)确定插入位置，将待插入的 k值与 Rmid.key比较，具体方法如下： 若 Rmid.key k，则由排序后表的有序性可知 Rmid, ， n.key均大于 k，因此，插入区间是左子表 Rlow, ， high，其中 high=mid-1。 若
18、 Rmid.key k，则要插入的 k必在 mid 的右子表 Rmid+1， ， high中，其中 low=mid+1。 (4)在上面的过程中， low 逐步增加，而 high逐步减少，直到 high low，则找到插入位置为 low，然后循环移 动位置 low后面的元素，再插入数值。 (5)重复上述过程，直到所有数都被插入。 有了上面的分析，我们再来看程序伪代码，第 (1)空处在准备阶段，准备阶段要完成的任务是给变量赋初值， highi -1将数组中的最后一个位置赋给了插入指针high，因为插入的范围是数组的整个范围，那么第 (1)空应该用来将数组的第一个位置赋给插入指针 low，因此答案为
19、 low1 。 第 (2)空是找插入位置用的循环条件，根据我们上面的分析，要直到 high low时，才能确定插入的位置；而在 low =high时，循环一直执 行，结合程序的内容，知道此空答案为 low =high。 第 (3)空很明显是用来确定区间的中间位置，但 mid 有可能为小数，在程序中我们用取整的方法来去掉小数部分，因此，此空答案为 mid -int(low+high)/2)。 第 (4)空是条件 X.key Rmid.key不成立的情况下执行的语句，如果条件为假，则说明要插入的数大于中间位置的数，应该在其右区间里进行插入，根据分析知道，这时左指针 low 应该改变，这个空就是用来
20、实现这个功能的，因此，答案为lowmid+1 。 第 (5)空在后移的 循环操作中，作为后移的循环判断条件，在找到插入位置后，进行插入前，我们需要一个空间来存放插入的值。从程序中不难看出，是将待插入位置后面的所有元素向后移动一位，而待插入位置存放在 low中，因此，此空答案为 i-1到 low。 2 【正确答案】 (1)i=1;i 5;i+ (2)i!=k&i!=j&j!=k (3)ai=I (4)aj=0 (5)line+ 【试题解析】 本题考查用 C语言程序对组合数和素数的求解。 在函数 2.1中，要求输出由 1、 2、 3、 4这些数字组成的互不相同且无重 复数字的三位数。程序中是用三重
21、循环来实现的。 第 (1)空是三重循环中第一重循环的循环条件，三位数的最高位可以取题目给出的任意一个数，那么应该和其他循环的条件一样，结合程序中变量的应用情况，不难知道这重循环是用变量 i，因此，此空答案为 i=1； i 5； i+。 第 (2)空是条件判断语句的条件，此条件判断语句的作用注释中已经给出，是用来确保 i， j， k 三位互不相同的，即所组成的三位数中无重复数字。因此，此空答案为 i!=k&i!=j&j!=k。 在函数 2.2中，题目要求计算并输出 100之内的素数 ，且每行只能输出 10个数，从试题一中我们应该很清楚素数的定义了，最小的素数是 2。下面我们来分析程序。 第 (3
22、)空是第一个循环下面的执行语句，此循环是从 2开始一直到 100，结合程序不难发现程序中用了一个数组来存放要参加运算的 100个数，但是并没有对数组进行赋初值操作，那么此空的作用应该就是对数组进行赋初值，因此，此空答案为 ai=i。 第 (4)空是在循环中的两个条件判断语句下面，从条件判断语句 if(aj%ai=0)不难推断出此循环是用来求当前最小素数的倍数的，此空是对当前最小素数倍数的 处理，结合后面的程序可以知道，如果是素数的倍数，那么在数组中的值要被变为 0，因此，此空答案为 aj=0。 第 (5)空是在循环输出语句下面，从条件判断语句 if(line=10)及下面的操作可以推断出变量
23、line是用来记录一行中输出素数的个数的，在此空的上面一行程序是输出一个素数，那么接下来应该是将变量 line加 1，因此，此空答案为 line+。 3 【正确答案】 (1)t.length (2)i n&j m (3)s.stri=t.strj (4)n m (5)retrun tag 【试题解析】 本题考查用 C语言程序实现对串的操作。 题目要求对顺序存储的串 s和串 t进行比较，且比较结果可能是大于、小于和等于 3种情况。对串的操作是考试中容易出现的内容，串是指由任意个字符构成的有限序列。要判断两个串的大小是通过串中元素的比较来实现的。 第 (1)空是对刚声明的变量进行赋初值操作，前面的
24、 n 中存放了串 s的长度，而对于串 t的长度在程序中一直没求过，而是用 m来表示，那么此空是将串 t的长度存放到变量 m中。因此，此空答案为 t.length。 第 (2)空是循环的判断条件，从程序不难看 出此循环的作用是实现对串 s和串 t的比较，在进行比较串时，需要对串中逐个元素进行比较，只要串中还有元素，比较就需继续，而判断串中是否还有元素是通过串的长度来实现的。两个串中元素的长度分别存放在变量 n 和变量 m中，因此，此空答案为 i n&j m。 第 (3)空是条件判断语句的条件，如果这个条件成立，则两个串中的元素都往后移动一个，再结合下面的程序，不难看出此条件的作用是判断当前两个元
25、素是否相等，如果相等，则执行下面语句。因此，此空答案为 s.stri=t.strj。 第 (4)空也是条件判断语句 的条件，题目要求比较结果可能是大于、小于和等于三种情况，程序中已经考虑了其中小于和等于的情况，那么此空应该是考虑大于的情况，因此，此空答案为 n m。 第 (5)空在程序的最后，题目中要求函数能返回运算的结果，而根据程序的内容，我们知道结果存放在变量 tag中，因此，此空答案为 return tag。 4 【正确答案】 (1)color*ip (2)adjij=1&colorj=c (3)i， k， aaj， color (4)select(i， c+1， adj， color)
26、 (5)colori=c 【试题解析】 本题考查四色定理在 C语言中的实现。 题目对四色定理做了解释，是指任何平面区域均可以用 4种颜色着色，使相邻区域着不同的颜色。而题目中给定了区域图，要求找出所有可能的不超过 4种颜色的着色方案。下面我们来分析程序。 第 (1)空在函数 back()中，这个函数的作用在注释中已经给出，是回溯，通过回溯，我们可以搜索出问题的所有解。此空是给变量 c赋一个值，从程序中我们可以推断出变量 c中存放的是区域中当前选中的颜色，而表示区域中当前选中的颜色的是数组 color的当前值，因此，此 空答案为 “color*ip”。 第 (2)空在函数 colorOK()中，
27、这个函数的作用在注释中也给出了，是检查区域i，考查 c种颜色的可能性，这就要求判断每种颜色是否适合区域 i，如果适合，则返回真。此空是函数体中一个条件判断语句的条件，如果条件不成立，则返回真，那么条件应该不能确定该颜色是否适合区域 i。如果比较的是两个不相邻的位置，且两个位置的颜色都为当前色，那么肯定不能确定当前色是否适合区域 i。因此，此空答案为 “adjij=1 &colorj=c”。 第 (3)空在函数 select()中，这个函数是为区域 i选一种可着色，此空是函数colorOK()的参数，而这个函数有 4个参数，分别是当前位置 i、当前颜色和两个数组，因此，此空答案为 “i,k,ad
28、j,color”。 第 (4)空是给变量 c赋值，变量 c中存放的是当前要处理的颜色，而这条语句是条件判断执行语句，如果条件成立，则要回溯，那么说明不能确定当前区域的颜色，而为当前区域 i选一种可着色是函数 select()的功能，它返回 0时，说明不能确定区域 i的颜色。因此，此空答案为 “select(i,c+1,adj,color)”。 第 (5)空是在上空中条件不成立的情况下执行的语句，条件不成立说明确定了当前区域 i的颜色，然后应该将该区域存为这种颜色，而变量 c中存放的就是当前处理的颜色，因此，此空答案为 “colori=c”。 5 【正确答案】 (1)onej=int(Numbe
29、ri-48) (2)MAXRESULTBIT-(MAXINPUTBIT-i) (3)resultj%=10 (4)resulti (5)resulti=0 【试题解析】 本题考查用 C+实现大整数的乘法运算。 题目要求程序能实 现从键盘任意输入的两个大整数的乘法运算。在程序中定义了一个大整数类，在类中抽象了大整数的一些属性，如长度等，还声明了一些操作，有对大整数输入的操作和对大整数求乘积的操作等。下面来具体 分析 程序。 第 (1)空在第一个大整数的输入函数中，根据此空后面的注释我们知道，其功能是把字符转换为数字。在这里需要注意的是，从键盘输入的是字符型的一串字符，此空所在的条件判断语句是用来
30、把这串字符中的数字找出来，接下来就是此空，要求把字符型的数字转换为整型的数字，而字符型数字与整型数字之间的ASC 码值相差 48。从第二个 大整数的输入函数中，我们也可以很容易知道此空答案为 onej=int(Numberi-48)。 第 (2)空在对大整数求乘积的函数中，是一个循环的初始条件，从程序中不难看出，这个二重循环是用来实现对两个大整数求乘积的，而变量 j是用来存放计算结果数组的当前下标的，根据乘法的规则，不难得出此空答案为 MAXRESULTBIT-(MAXINPUTBIT-i)。 第 (3)空也在求积的二重循环中，它是在语句 if(resultj 9)为真的情况下执行的语句，如果
31、这个条件为真，说明当前需要进位，但到底是 进几位，进位后余下的数又应该是多少呢 ?这就是这个条件判断语句下要完成的任务，从程序中不难看出，对于到底进几位这个问题已经解决，剩下的就是对进位后余数的处理，此空的任务就是求出进位后的余数并存放到数组的当前位置。所以，此空答案为resultj%=10。 第 (4)空在输出计算结果的函数中，从程序中可以看出，此空在 _个循环中，循环的作用是输出计算结果，而计算结果存放在数组中，因此，这个循环是用来输出数组中的所有元素。因此，此空答案为 resulti。 第 (5)空是在清除计算结果的函数中，函数中只有一个 循环，此空就在循环下面，计算结果存放在数组中，要
32、清除计算结果就是把数组清零，那么此空的任务是把数组中的每个元素变成零，因此，此空答案为 resulti=0。 6 【正确答案】 (1)Runnable (2)run() (3)throws 程序输出结果： running:1 running:2 running:1 running:2 running:1 running:2 finished:1 finished:2 【试题解析】 本 题考查 Java中线程的相关知识。 题目要求按照程序给出的内容来完成填空和输出程序的运行结果。本题的关键是考查我们对线程的了解程度。线程的创建方法有两种，即通过类 Thread 和接口Runnable创建的方法。
33、刚刚创建的线程还不能与其他的线程并发运行，当调用了方法 start后，线程进入就绪态，在被 Java虚拟机调度后才进入运行态。进入运行态的线程自动执行成员方法 run()，在执行完这个成员方法后线程就又自动进入死亡态。下面来具体分析程序。 第 (1)空在定义类 usethread 语句中，从后面的关键字 implements 可以推断出类继承了一个接口，而在 Java中，接口一般只有成员变量和成员方法的定义而没有成员方法的具体实现。根据后面的程序 new Thread(new usethread(1)可以知道创建了线程对象，而这种创建线程对象的方法是通过接口 Runnable 来实现的，因此类
34、 usethread 肯定是继承了接口 Runnable，所以此空答案为 Runnable。 第 (2)空是一个函数体的函数名，而函数体的作用是循环进行输出，从上面对线程的分析可以知道，此函数一定是 run()函数，因此此空答案为 run()。 第 (3)空是入口函数后面的语句，结合 Java程序的特点，再从此空后面的内容不难推断出，此处是要显式生成异常来处理程序中的异常。而在 Java中，一般用关键字 throws来显式生成异常，因此此空答案为 throws。 对于问题 2，我们可以根据程序来分析，程序中创建了两个线程，根据上面的分析我们可以知道，这两个线程都自动调用了函数 run()，因此程序输出结果为： running:1 running:2 running:1 running:2 running:1 running:2 finished:1 finished:2
