1、初级程序员下午试题-17 及答案解析(总分：90.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 实现连通图 G的深度优先遍历(从顶点 v出发)的非递归过程。 【算法】 第一步：首先访问连通图 G的指定起始顶点 v； 第二步：从 V出发，访问一个与 vU (1) /Up，再从顶点 P出发，访问与 pU (2) /U顶点 q，然后从 q出发，重复上述过程，直到找不到存在U (3) /U的邻接顶点为止。 第三步：回退到尚有U (4) /U顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。 因此，在这个算法中应设一个栈保存被U
2、 (5) /U的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。（分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)2.【函数 1说明】 函数 palindrome(char s)的功能是：判断字符串 s是否为回文字符串。若是，则返回 0，否则返回-1。若一个字符串顺读和倒读都一样时，则可称该字符串是回文字符串。例如，“LEVEL”是回文字符串，而“LEVAL”不是。 【函数 1】 int palindrome(char s char *pi, *pj; pi=s; pj=s+strlen(s)-1; while(pipj pj-; if(U (2) /U)return-
3、1; else return 0; 【函数 2说明】 函数 f(char *str, char del)的功能是：将非空字符串str分割成若干个子字符串并输出，del 表示分割时的标志字符。 例如，若 str的值为“33123333435”，del的值为“3”，调用此函数后，将输出三个子字符串，分别为“12”、“4”和“5”。 【函数 2】 void f(char *str, char del) int i,j, len; len=strlen(str); i=0; while(ilen) While(U (3) /U) i+; /*忽略连续的标志字符*/ /*寻找从 stri开始直到标志字符
4、出现的一个子字符串*/ j=i+1; while(strj!=del U (4) /U=/0; /*给找到的字符序列置字符串结束标志*/ printf(“%s/t“, U (5) /U; （分数：15.00）_三、B试题三/B(总题数：1，分数：15.00)3.【说明】 本题中的函数 encode()和 decode()分别实现对字符串的变换和复原。其中变换函数 encode()顺序考查已知字符串的字符，按以下规则逐组生成新字符串： (1)若已知字符串的当前字符不是数字字符，则将该字符复制在新字符串中。 (2)若已知字符串的当前字符是一个数字字符，且它之后没有后继字符，则简单地将它复制到新字符
5、串中。 (3)若已知字符串的当前字符是一个数字字符，并且还有后继字符，设该数字字符的面值为 n，则将它的后继字符(包括后继字符是一个数字字符)重复复制 n+1次到新字符串中。(4)以上述一次变换为一组，在不同组之间另插入一个下划线“_”用于分隔。例如，encode()函数对字符串 26a3t2的变换结果为 666_a_tttt_2。 复原函数 decode()做与变换函数 encode()相反的工作。即复制不连续相同的单个字符，而将一组连续相同的字符(不超过 10个)变换成一个用于表示重复次数的数字符和一个重复出现的字符，并在复原过程中略过变换函数，为不同组之间添加的一个下划线字符。 假定调用
6、变换函数 encode()时的已知字符串中不含下划线字符。 【函数】 int encode(char *instr, char *outstr) char *ip, *op, c; int k,n; ip=instr; op=outstr; while(*ip) if(*ip=0 c=U (2) /U; for(k=0; kn;k+) *op+=c; elseU (3) /U; *op+=_; ip+; if(opoutstr)op-; U (4) /U; return op-outstr; int decode(char *instr, char *outstr) char *ip, *op
7、, c; int n; ip=instr; op=outstr; while(*ip) c=*ip; n=0; while(*ip=c n+; if(U (5) /U)*op+=0+n-1; *op+=c; if(U (6) /U)ip+; *op=/0; return op-outstr; （分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)4.【说明】 编写程序，利用带参数的主函数 main()，实现二进制文件的复制。比如，若该程序已生成可执行文件 filebin.exe，在 DOS操作系统命令状态下键入如下命令行： filebin f0.fil f1.fil 则实现将已
8、存在的二进制文件 f1.fil依原样复制给名为 f0.fil的二进制文件。 【函数】 #includestdio.h void fcopy(FILE *fout, FILE *fin) char k; do k=fgetc(U (1) /U);if(feof(fin) break; fputc(U (2) /U); while(1); void main(int argc,char *argv) FILE *fin,*fout; if(argc!=U (3) /U) return; if(fin=fopen(argv2,“rb“)=NULL) return; fout=U (4) /U; fc
9、opy(U (5) /U); fclose(fin); fclose(fout); （分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)5.【说明】 在矩形类中重载关系运算符“=”，采用友元，比较的依据是矩形面积的大小。重载算术运算符“+=”，采用成员函数，更新矩形对象的长与宽，分别加上形参矩形的长与宽。重载算术运算符+，利用构造函数，采用友元。 【代码】 class Crect int length,witdth; public; CRect(int l,int w) length=l; width=w; friend int operator=(CRect/比较面积 vo
10、id operator+=(CRect/求长 U (4) /U;/求宽 friend operater+(CRect /利用构造函数 （分数：15.00）_六、B试题六/B(总题数：1，分数：15.00)6.【说明】 下面程序完成从键盘读入一个字符串，然后采用 parseInt方法将其转换为一个相应的整数。 import java.io.*; public class testThrows public staticU (1) /UreadString()U (2) /UIOException int ch; String r=“; boolean done=false; while(U (3
11、) /U) ch=System.in.read(); if(ch0 | ch=0xd) /处理回车符中第一个符号 done=true; else r=r+(char)ch; return r; public static void main(Stling args) String str; U (4) /U str=readString(); U (5) /U(IOException e) System.out.println(“error“); return; System.out.println(“input integer: “+Integer.parselnt(str); （分数：15
12、.00）_初级程序员下午试题-17 答案解析(总分：90.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 实现连通图 G的深度优先遍历(从顶点 v出发)的非递归过程。 【算法】 第一步：首先访问连通图 G的指定起始顶点 v； 第二步：从 V出发，访问一个与 vU (1) /Up，再从顶点 P出发，访问与 pU (2) /U顶点 q，然后从 q出发，重复上述过程，直到找不到存在U (3) /U的邻接顶点为止。 第三步：回退到尚有U (4) /U顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。 因此，在这个算法中应设一个栈
13、保存被U (5) /U的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。（分数：15.00）_正确答案：()解析：(1)邻接的顶点 (2)邻接的且未被访问的 (3)未访问过 (4)未被访问过的邻接点的 (5)访问过 分析 本题考查连通图的深度优先遍历算法的非递归过程。 在做题前，我们首先来了解一下图的遍历。和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。 连通图的深度优先遍历可定义如下：首先访问出发点 v，并将其标记为已访问过；然后依次从 v出发搜索 v的每个邻接点 w。若 w未曾访问过，则以 w为新的出发点继续进行深度优先遍历，直至图中所
14、有和源点 v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。其关键是每次遍历都是往下直到最后再往回搜索，找到还未被访问过的邻接点的顶点，然后从该顶点出发，对它及下面的顶点进行深度优先遍历。下面来具体分析其算法。 第(1)空在第二步中，在访问起始顶点 v后应该访问的结点，那么这个结点肯定是与起始顶点 v邻接的顶点，因此此空答案为“邻接的顶点”。 第(2)空是在访问 p顶点后应该访问的顶点，接下来应该也是访问与 p顶点邻接的顶点，但这个时候 p顶点的邻接顶点中有已经被访问过了的顶点，因此在访问前还需判断此顶点是否被访问过了，所以此空答案为“邻接的且未被访问的”。 第(3)空也在第二步中，
15、结合前后的内容，可以知道此空是要判断是否还可以找到与当前访问顶点邻接而未被访问的顶点，根据上面分析，如果找不到，才往回搜索，因此此空答案为“未访问过”。 第(4)空是回退过程中要注意的地方，一般回退到还未被访问过的邻接点的顶点，接着访问这个未被访问过的邻接点。因此此空答案为“未被访问过的邻接点的”。 第(5)空是存放在栈中的内容，栈具有后进先出的特点，根据上面对深度优先遍历的分析可以知道，在回退的过程中需要用到被访问过的顶点，而且回退的过程是按遍历的顶点的顺序回退的，越后被访问的顶点越先被回退，因此此空答案是“访问过”。二、B试题二/B(总题数：1，分数：15.00)2.【函数 1说明】 函数
16、 palindrome(char s)的功能是：判断字符串 s是否为回文字符串。若是，则返回 0，否则返回-1。若一个字符串顺读和倒读都一样时，则可称该字符串是回文字符串。例如，“LEVEL”是回文字符串，而“LEVAL”不是。 【函数 1】 int palindrome(char s char *pi, *pj; pi=s; pj=s+strlen(s)-1; while(pipj pj-; if(U (2) /U)return-1; else return 0; 【函数 2说明】 函数 f(char *str, char del)的功能是：将非空字符串str分割成若干个子字符串并输出，de
17、l 表示分割时的标志字符。 例如，若 str的值为“33123333435”，del的值为“3”，调用此函数后，将输出三个子字符串，分别为“12”、“4”和“5”。 【函数 2】 void f(char *str, char del) int i,j, len; len=strlen(str); i=0; while(ilen) While(U (3) /U) i+; /*忽略连续的标志字符*/ /*寻找从 stri开始直到标志字符出现的一个子字符串*/ j=i+1; while(strj!=del U (4) /U=/0; /*给找到的字符序列置字符串结束标志*/ printf(“%s/t“
18、, U (5) /U; （分数：15.00）_正确答案：()解析：(1)*pi=*pi (2)pipj 或*pi!=*pj (3)stri=del (4)strj (5)i=j+1 分析 本题考查在 C语言中对字符串的处理。 【函数 1】 使用数组 sn来存储一个字符串，因为要根据回文字符串的定义来判断一个串是否是回文字符串，所以需要循环比较。 (1)拿该字符串的第一个元素 s0和最后一个元素sn-1比较，如果 s0不等于 sn-1，则 s不是回文字符串。 (2)如果 s0等于 sn-1，则拿第二个元素 s1和倒数第二个元素 sn-2比较，如果 s1不等于 sn-2，则 s不是回文字符串。 (
19、3)依次类推，直到最中间的两个元素也比较完毕(如果 s有偶数个元素)，或者只剩下中间的一个元素(如果 s有奇数个元素)。 当上述循环结束时，如果最中间的元素没有进行比较，就说明 s不是回文字符串；如果进行了比较，则 s是回文字符串。 在函数 1中，pi 和 pj是两个指向字符的指针，程序首先将 s的首地址赋给pi(即*pi =a0)，将元素 sstrlen(s)-1的地址赋给 pj(即*pj=sstrlen(s)-1)，当 pipj 并且 pi和 pj所指向的值相等时进行循环：pi 自增，pj 自减。 退出循环后，如果 pipj，则 s是回文字符串(如果 s有偶数个元素，则为 pipj；如果
20、s有奇数个元素，则为 pi=pj)；如果 pipj，则 s不是回文字符串。 【函数 2】 由函数 2说明可知，此函数对给定的字符串进行从左至右的扫描，找出不包含标志字符的子字符串。 在函数 2中，i 的初值为 0，len 表示字符串的长度。当 ilen 时进行循环：如果当前字符是标志字符，则不作处理，继续扫描。当退出该循环时，当前字符 stri不是标志字符，这时从stri开始寻找，直到找到在标志字符中出现的一个子字符串(i 保持不变，用 i标记寻找的过程)，给找到的字符序列置字符串结束标志，以便于后面语句的输出。 输出语句结束后，就要继续寻找后面的不包含标志字符的子字符串，这时，需要把指针 i
21、移动至 j的后面，继续扫描。三、B试题三/B(总题数：1，分数：15.00)3.【说明】 本题中的函数 encode()和 decode()分别实现对字符串的变换和复原。其中变换函数 encode()顺序考查已知字符串的字符，按以下规则逐组生成新字符串： (1)若已知字符串的当前字符不是数字字符，则将该字符复制在新字符串中。 (2)若已知字符串的当前字符是一个数字字符，且它之后没有后继字符，则简单地将它复制到新字符串中。 (3)若已知字符串的当前字符是一个数字字符，并且还有后继字符，设该数字字符的面值为 n，则将它的后继字符(包括后继字符是一个数字字符)重复复制 n+1次到新字符串中。(4)以
22、上述一次变换为一组，在不同组之间另插入一个下划线“_”用于分隔。例如，encode()函数对字符串 26a3t2的变换结果为 666_a_tttt_2。 复原函数 decode()做与变换函数 encode()相反的工作。即复制不连续相同的单个字符，而将一组连续相同的字符(不超过 10个)变换成一个用于表示重复次数的数字符和一个重复出现的字符，并在复原过程中略过变换函数，为不同组之间添加的一个下划线字符。 假定调用变换函数 encode()时的已知字符串中不含下划线字符。 【函数】 int encode(char *instr, char *outstr) char *ip, *op, c;
23、int k,n; ip=instr; op=outstr; while(*ip) if(*ip=0 c=U (2) /U; for(k=0; kn;k+) *op+=c; elseU (3) /U; *op+=_; ip+; if(opoutstr)op-; U (4) /U; return op-outstr; int decode(char *instr, char *outstr) char *ip, *op, c; int n; ip=instr; op=outstr; while(*ip) c=*ip; n=0; while(*ip=c n+; if(U (5) /U)*op+=0+
24、n-1; *op+=c; if(U (6) /U)ip+; *op=/0; return op-outstr; （分数：15.00）_正确答案：()解析：(1)*ip-0+1 (2)*+ip (3)*op+=*ip (4)*op=/0 (5)n1 (6)*ip=_ 分析 本题考查 C语言对字符串的处理。 本题对字符串按一定要求进行编码解码，所以编码规则至关重要。在做题前一定要看清规则，并按规则对程序说明中所举的例子进行手动的编码解码工作。必要时，可以将其和程序比较着看。 下面我们来开始分析程序。 int encode(char *instr, char *outstr) char *ip, *
25、op, c; int k, n; ip=instr; op=outstr; while(*ip) if(*ip=0 kn;k+) *op+=c; elseU (3) /U; 这里对应规则(1)和(2)直接把字符拷贝到新串。所以(3)空应填*op+=*ip。 *op+=_; ip+; if(opoutstr)op-; U (4) /U; 这里应是给新串 outstr加上字符串结束符/0。因为如果执行了上面的 while循环，则会把字符串 26a3t2变换结果为 666_a_tttt_2_，而不是程序说明中的666_a_tttt_2。因为上面的 while循环中有“while()(.*op+=_;
26、ip+;”。所以要把最后一个_用字符串结束符/0替换掉，刚好“if(opoutstr)op-；”把 op指针定位到了最后的_。所以(4)空应填*op=/0。这里要注意一点，“if(opoutstr)op-”不能直接写成 op-。因为当输入串 instr为空时，outstr 也为空，while()不作处理，则 op=outstr。这种情况下，直接把/0写到*outstr，表示outstr是一个空串。 return op-outstr; 接下来我们分析解码程序 decode()。 int decode(char *instr, char *outstr) char *ip, *op, c; int
27、 n; ip=instr; op=outstr; while(*ip) c=*ip;n=0; while(*ip=c n+; 上面的循环用于统计字符 c的个数。 if(U (5) /U)*op+=0+n-1; 此处把统计个数存到输出串，则表示当前情况符合编码规则(3)。所以(5)空应填 n1。 *op+=c; if(U (6) /U)ip+; 因为解码规则中有“并在复原过程中略过变换函数，为不同组之间添加的一个下划线字符”。所以(6)空应填*ip=_。四、B试题四/B(总题数：1，分数：15.00)4.【说明】 编写程序，利用带参数的主函数 main()，实现二进制文件的复制。比如，若该程序已
28、生成可执行文件 filebin.exe，在 DOS操作系统命令状态下键入如下命令行： filebin f0.fil f1.fil 则实现将已存在的二进制文件 f1.fil依原样复制给名为 f0.fil的二进制文件。 【函数】 #includestdio.h void fcopy(FILE *fout, FILE *fin) char k; do k=fgetc(U (1) /U);if(feof(fin) break; fputc(U (2) /U); while(1); void main(int argc,char *argv) FILE *fin,*fout; if(argc!=U (3
29、) /U) return; if(fin=fopen(argv2,“rb“)=NULL) return; fout=U (4) /U; fcopy(U (5) /U); fclose(fin); fclose(fout); （分数：15.00）_正确答案：()解析：(1)fin (2)k,fout (3)3 (4)fopen(argv1,“wb“) (5)fout,fin 分析 本题考查用 C语言对二进制文件的操作。 题目要求程序实现二进制文件的复制。此题的关键是我们对文件基本操作的掌握，如文件的打开，对文件内容进行读/写等。下面来具体分析程序。 第(1)空是在复制函数 fcopy()中，这个
30、函数的功能是对文件进行复制，函数中的两个参数分别是指向被操作的两个文件的指针。此空是函数fgetc()的参数，这个函数的作用是从文件中逐个读字符，其参数是文件要读的地址，结合后面的if(feof(fin)，可以很清楚地知道，当前操作的文件是指针 fin指向的文件，因此此空答案为 fin。 第(2)空也在复制函数 fcopy()中，是函数 fputc()的参数，这个函数的作用与函数 fgetc()相反，是往文件中写内容，其参数是当前文件中要写的内容和地址。根据题目的意思，应该是往另一个文件中写内容，因此此空答案为 k,fout。 第(3)空在主函数中，此空是一个条件判断语句的条件，看它的内容是否
31、等于变量 argc的内容，如果不等，则程序返回。题目中要求在 DOS操作系统命令状态下键入命令行“filebin f0.fil f1.fil”后，实现将已存在的二进制文件 f1.fil依原样复制给名为 f0.fil的二进制文件。那么主函数参数 argc的值应该等于 3，是后面 argv指针数组中内容的个数，而数组中的内容分别是 argv0=“filebin“，argv1=“f0.fil“，argv2=“f1.fil“，因此此空答案为 3。 第(4)空是给指针变量 fout赋一个值，或者说是让指针变量 fout指向该地方，从上面的程序中知道指针变量 fout指向一个文件，那么此空的任务就是打开一
32、个文件，在 C 语言中打开一个文件用函数 fopen()，这个函数一般有两个参数，第一个参数是要打开的文件名(指针数组 argv的第二个元素)，第二个参数是对文件的操作属性，这里要往文件中写数据，因此此空答案为 fopen(argv1，“wb“)。 第(5)空是复制函数 fcopy()的两个参数，程序到这里，这两个参数应该很好确定了，第一个参数是指向被写文件的指针变量 fout，而第二个参数是指向被读文件的指针变量 fin，因此此空答案为 fout,fin。五、B试题五/B(总题数：1，分数：15.00)5.【说明】 在矩形类中重载关系运算符“=”，采用友元，比较的依据是矩形面积的大小。重载算
33、术运算符“+=”，采用成员函数，更新矩形对象的长与宽，分别加上形参矩形的长与宽。重载算术运算符+，利用构造函数，采用友元。 【代码】 class Crect int length,witdth; public; CRect(int l,int w) length=l; width=w; friend int operator=(CRect/比较面积 void operator+=(CRect/求长 U (4) /U;/求宽 friend operater+(CRect /利用构造函数 （分数：15.00）_正确答案：()解析：(1)r1.length*r1.width (2)r1.length
34、*r1.width (3)length+=r.length (4)width+=r.width (5)r1.length+r2.length,r1.width+r2.width 分析 本题考查 C+中的函数重载与友元。 题目要求在矩形类中采用友元重载关系运算符“=”，比较的依据是矩形面积的大小；采用成员函数重载算术运算符“+=”来更新矩形对象的长与宽，其功能是分别加上形参矩形的长与宽；重载算术运算符“+”，利用构造函数，也采用友元的方式。首先我们要了解一下友元的作用。 需要在类的外部直接访问类的私有数据成员，在不改变类的数据成员安全性的前提下，使得类外部的函数或类能够访问类中的私有成员数据，这
35、一功能可以通过友元的方式来实现。下面来具体分析程序。 第(1)空与第(2)空要结合起来完成，它们是重载关系运算符“=”的两个操作数，而根据题目要求，这个关系运算符的比较依据是矩形面积的大小，求矩形的面积是通过矩形的长和宽来实现的，这个函数的参数是两个矩形类对象，在定义矩形类时，分别把矩形的长和宽定义成了默认的私有成员变量。根据程序中函数的定义可以知道，这个函数被定义为友元函数，可以访问矩形类中的私有成员变量，因此这两个空的答案分别是用对象的长和宽计算其面积，即答案分别为 r1.length*r1.width与 r2.length*r2.width。 第(3)空与第(4)空要结合起来完成，它们是
36、重载算术运算符“+=”函数下面的操作，根据题目要求，这个算术运算符的作用是用来根据形参矩形的长与宽更新该矩形对象的长与宽，是该矩形对象的长与宽分别加上形参矩形对象的长与宽，根据注释，第 (3)空用来更新其长，因此此空答案为 length+=r.length；而第(4)空用来更新其宽，因此答案为width+=r.width。 第(5)空在重载算术运算符“+”的函数下面，根据题目要求，此函数的实现是利用矩形类的构造函数和友元共同实现的。从程序中可以明显知道，此空是构造函数的参数，而构造函数的两个参数分别是矩形的长与宽。算术运算符“+”的作用我们大家也都非常熟悉，是用来计算两个操作数的和。重载算术运
37、算符“+”的函数参数是两个矩形对象，那么构造函数中的两个参数应该分别是这两个矩形对象的长与宽的和。所以此空答案为 r1.length+r2.length，r1.width+r2.width。六、B试题六/B(总题数：1，分数：15.00)6.【说明】 下面程序完成从键盘读入一个字符串，然后采用 parseInt方法将其转换为一个相应的整数。 import java.io.*; public class testThrows public staticU (1) /UreadString()U (2) /UIOException int ch; String r=“; boolean done=
38、false; while(U (3) /U) ch=System.in.read(); if(ch0 | ch=0xd) /处理回车符中第一个符号 done=true; else r=r+(char)ch; return r; public static void main(Stling args) String str; U (4) /U str=readString(); U (5) /U(IOException e) System.out.println(“error“); return; System.out.println(“input integer: “+Integer.pars
39、elnt(str); （分数：15.00）_正确答案：()解析：(1)String (2)throws (3)!done (4)try (5)catch 分析 本题考查 Java中字符串的处理。 题目要求程序完成从键盘读入一个字符串，然后采用 parseInt方法将其转换为一个相应的整数。这里的关键是如何将一个字符串转换为一个相应的整数，而这个过程在 parseInt 方法中实现了，我们要做的工作主要是如何对字符串进行操作。下面来具体分析程序。 第(1)空在类 testThrows下面，从程序中不难看出，此空的作用是定义函数 readString()的返回类型，再从程序后面的语句 return
40、 r可以知道这个函数返回的是变量 r的值，而变量 r是一个字符串型的变量，因此此空答案为 String。 第(2)空也是函数readString()定义的内容，从此空后面的内容不难推断出，此处是要显式生成异常来处理程序中的异常。而在 Java中，一般用关键字 throws来显式生成异常，因此此空答案为 throws。 第(3)空很明显是循环的判断条件，从程序中可以看出，这个循环是用来对输入的字符串进行相关的处理的，如果一直可以取到有效字符，循环肯定不会结束，而判断是否取到有效字符，是通过布尔变量 done来实现的，那么只要布尔变量 done的值为真循环则结束，因此此空答案为!done。 第(4)空与第(5)空需要结合起来看，它们都在入口函数中，如果我们对 Java中的异常处理非常了解的话，这两个空应该很简单，从第(5)空后面的(IOException e)很明显地看出是要处理异常操作。在 Java中，一般 try与 catch结合起来使用，如果在 try中产生了异常，那么在 catch中对异常进行处理。因此这两个空的答案分别为 try和catch。
