1、计算机水平考试初级程序员 2009 年下半年下午真题及答案解析(总分:90.00,做题时间:90 分钟)一、B试题一/B(总题数:1,分数:15.00)1.阅读以下说明和流程图,填补流程图中的空缺(1)(5),将解答填入答题纸的对应栏内。 B/B说明B/B 求连续函数 f(x)的根(方程 f(x)=0 的解)的最简单方法是二分法。为此,首先需要在若干点上检查函数值的符号,如果发现 f(a)与 f(b)符号相反(ab),则在区间(a,b)中必然存在 f(x)的根。因为当 x 从 a 变到 b 时,连续函数的值将从正变到负(或从负变到正),必然要经过 0。区间(a,b)就是根的初始范围。 取该区间
2、的中点 m,如果 f(m)=0,则根就是 m。如果 f(a)与 f(m)符号相反,则根一定在区间(a,m)中;如果 f(m)与 f(b)符号相反,则根一定在区间(m,b)中。因此,根的范围缩小了一半。 依此类推,将区间一半一半地分下去,当区间的长度很小(达到根的精度要求,例如 0.001)时,或者当区间中点处的函数值几乎接近于 0(即绝对值小于预先规定的微小量,例如 0.001)时,近似计算就可以结束了。 以下流程图描述了用二分法近似计算区间(a,b)中 f(x)的根的过程。 B/B流程图B/B (分数:15.00)_二、B试题二/B(总题数:1,分数:15.00)2.阅读以下说明和 C 函数
3、,将应填入U (n) /U处的字句写在答题纸的对应栏内。B/B说明 1B/B函数 Counter(int n, int w)的功能是计算整数 n 的二进制表示形式中 1 的个数,同时用数组 w 记录该二进制数中 1 所在位置的权。例如,十进制数 22 的二进制表示为 10110。对于该二进制数,1 的个数为 3,在 w0中存入 2(即 21)、w1中存入 4(即 22)、w2中存入 16(即 24)。B/BC 函数 1B/Bint Counter(int n,int w) int i =0,k=1;while(U (1) /U) if (n% 2) wi + =k;n=n/2;U (2) /U
4、;return i;B/B说明 2B/B函数 Smove(int A,int n)的功能是将数组中所有的奇数都放到所有偶数之前。其过程为:设置数组元素下标索引 i(初值为 0)和 j(初值为 n-1),从数组的两端开始检查元素的奇偶性。若 Ai、Aj都是奇数,则从前往后找出一个偶数,再与 Aj进行交换;若 Ai、Aj都是偶数,则从后往前找出一个奇数,再与 Ai进行交换;若 Ai是偶数而 Aj是奇数,则交换两者,直到将所有的奇数都排在所有偶数之前为止。B/BC 函数 2B/Bvoid Smove(int A,int n) int temp,i=0,j=n-1;if(n2) return;whil
5、e (ij)if(Ai % 2=1 elseif(Ai% 2 =0 else if(U (5) /U) temp=Ai;Ai=Aj;Aj=temp;i+, j-;(分数:15.00)_三、B试题三/B(总题数:1,分数:15.00)3.阅读以下说明、C 函数和问题,将解答写入答题纸的对应栏内。 B/B说明 1B/B 函数 test_f1(int m,int n)对整数 m、n 进行某种运算后返回一个整数值。 B/BC 函数 1B/B int test_f1(int m,int n) int k; k=mn? m:n; for(;(k% m! =0) |(k% n! =0);k+); retur
6、n k; B/B问题 1B/B (1)请写出发生函数调用 test_f1(9,6)时,函数的返回值;(2)请说明函数 test_f1 的功能。 B/B说明 2B/B 设在某 C 系统中为每个字符分配 1个字节,为每个指针分配 4 个字节,sizeof(x)计算为 x 分配的字节数。 函数 test_f2()用于测试并输出该 C 系统为某些数据分配的字节数。 B/BC 函数 2B/B void test_f2( ) char str =“NewWorld“; char* p=str; char i =/0; void* ptr =malloc(50); printf(“% d/t“,sizeof
7、(str); printf(“% d/n“,sizeof(p); printf(“% d/t“,sizeof(i); printf(“% d/n“,sizeof(ptr); B/B问题 2B/B 请写出函数 test_f2()的运行结果。 B/B说明 3B/B 函数 test_f3(char s)的功能是:将给定字符串 s 中的所有空格字符删除后形成的串保存在字符数组tstr 中(串 s 的内容不变),并返回结果串的首地址。 B/BC 函数 3B/B char*test_f3 (const char s) char tstr50 = /0; unsigned int i, k=0; for (
8、i =0;istrlen(s);i+) if(si! =“) tstrk+=si; return tstr; B/B问题 3B/B 函数 test_f3()对返回值的处理有缺陷,请指出该缺陷并说明修改方法。(分数:15.00)_四、B试题四/B(总题数:1,分数:15.00)4.阅读以下说明和 C 函数,将解答填入答题纸的对应栏内。 说明 函数 del_substr(S,T)的功能是从头至尾扫描字符串 S,删除其中与字符串 T 相同的所有子串,其处理过程为:首先从串 S 的第一个字符开始查找子串 T,若找到,则将后面的字符向前移动将子串 T 覆盖掉,然后继续查找子串 T,否则从串 S 的第二个
9、字符开始查找,依此类推,重复该过程,直到串 S 的结尾为止。该函数中字符串的存储类型 SString定义如下: typedef struct char* ch; /*串空间的首地址*/ int length; /*串长*/ SString; C函数 void del_substr(SString* S, SString T) iht i, j; if(S-length1 |T.length1 |S-lengthT.length) return; i=0; /* i 为串 S 中字符的下标*/ for (;) j =0; /*j 为串 T 中字符的下标*/ while(iS-length j+;
10、 else i=U (1) /U;j=0; /*i 值回退,为继续查找 T 做准备*/ if(U (2) /U) /*在 s 中找到与 T 相同的子串*/ i=U (3) /U; /*计算 s 中子串 T 的起始下标*/ for(k=i+T.length;kS-length;k+)/* 通过覆盖子串 T 进行删除*/ S-chU (4) /U =S-chk; S-length=U (5) /U; /* 更新 S 的长度*/ else break; /* 串 S 中不存在于串 T*/ (分数:15.00)_五、B试题五/B(总题数:1,分数:15.00)5.阅读以下说明和 C+代码,将应填入U
11、(n) /U处的字句写在答题纸的对应栏内。 B/B说明B/B 已知类 LinkedList 表示列表类,该类具有四个方法:addElement()、lastElement()、 numberOfElement()以及 removeLastElement()。四个方法的含义分别为: void addElement(Object):在列表尾部添加一个对象; Object lastElement():返回列表尾部对象; int numberOfElement():返回列表中对象个数; void removeLastElement():删除列表尾部的对象。 现需要借助 LinkedList 来实现一个
12、 Stack 栈类,C+代码 1 和 C+代码 2 分别采用继承和组合的方式实现。 B/BC+代码1B/B class Stack :public LinkedList public : void push (Object o) addElement (o); ; /压栈 Object peek() returnU (1) /U; /获取栈顶元素 bool i sEmpty () /判断栈是否为空 return numberOfElement ( ) = 0; ); Object pop () /弹栈 Object o = lastElement(); U (2) /U; return o;
13、; ; B/BC+代码 2B/B class Stack private: U (3) /U; public: void push (Object o) /压栈 list. addElement (o); ; Object peek() /获取栈顶元素 return list.U (4) /U; ; bool isEmpty () /判断栈是否为空 return list. numberOfElement ( ) = = 0; Object pop() /弹栈 Object o = list. lastElement ();list. removeLastElement ( ); return
14、 o; ; B/B问题B/B 若类 LinkedList 新增加了一个公有的方法 removeElement(int index),用于删除列表中第 index 个元素,则在用继承和组合两种实现栈类 Stack 的方式中,哪种方式下 Stack 对象可访问方法 removeElement(int index)?U (5) /U(A继承 B组合)(分数:15.00)_六、B试题六/B(总题数:1,分数:15.00)6.阅读以下说明和 Java 代码,将应填入U (n) /U处的字句写在答题纸的对应栏内。 B/B说明B/B 已知类 LinkedList 表示列表类,该类具有四个方法:addElem
15、ent()、lastElement()、HumberOfElement()以及 removeLastElement()。四个方法的含义分别为: void addElement(Object):在列表尾部添加一个对象; Object lastElement():返回列表尾部对象; int numberOfElement():返回列表中对象个数; void removeLastElement():删除列表尾部的对象。 现需要借助 LinkeedList 来实现一个 Stack 栈类,Java 代码 1 和 Java 代码 2 分别采用继承和组合的方式实现。 B/BJava 代码 1B/B publ
16、ic class Stack extends binkedList public void push(Object o) /压栈 addElement (o); public Object peek() /获取栈顶元素 returnU (1) /U; public boolean isEmpty() /判断栈是否为空 return numberOfElement () =0; public Object pop() /弹栈 Object o=lastElement(); U (2) /U; return o; B/BJava 代码 2B/B public class Stack private
17、U ( 3 ) /U; public Stack() list = new LinkedList (); public void push (Object o) list. addElement (o); public Object peek() /获取栈顶元素 return list.U (4) /U; public boolean isEmpty () /判断栈是否为空 return list.numberOfElement()=0; public Object pop() /弹栈 Object o =list.lastElement(); list.removeLastElement()
18、; return o; B/B问题B/B 若类LinkedList 新增加了一个公有的方法 removeElement(int index),用于删除列表中第 index 个元素,则在用继承和组合两种实现栈类 Stack 的方式中,哪种方式下 Stack 对象可访问方法 removeElement(int index)?U (5) /U(A继承 B组合)(分数:15.00)_计算机水平考试初级程序员 2009 年下半年下午真题答案解析(总分:90.00,做题时间:90 分钟)一、B试题一/B(总题数:1,分数:15.00)1.阅读以下说明和流程图,填补流程图中的空缺(1)(5),将解答填入答题
19、纸的对应栏内。 B/B说明B/B 求连续函数 f(x)的根(方程 f(x)=0 的解)的最简单方法是二分法。为此,首先需要在若干点上检查函数值的符号,如果发现 f(a)与 f(b)符号相反(ab),则在区间(a,b)中必然存在 f(x)的根。因为当 x 从 a 变到 b 时,连续函数的值将从正变到负(或从负变到正),必然要经过 0。区间(a,b)就是根的初始范围。 取该区间的中点 m,如果 f(m)=0,则根就是 m。如果 f(a)与 f(m)符号相反,则根一定在区间(a,m)中;如果 f(m)与 f(b)符号相反,则根一定在区间(m,b)中。因此,根的范围缩小了一半。 依此类推,将区间一半一
20、半地分下去,当区间的长度很小(达到根的精度要求,例如 0.001)时,或者当区间中点处的函数值几乎接近于 0(即绝对值小于预先规定的微小量,例如 0.001)时,近似计算就可以结束了。 以下流程图描述了用二分法近似计算区间(a,b)中 f(x)的根的过程。 B/B流程图B/B (分数:15.00)_正确答案:()解析:(a+b)/2 (2) f(x) (3) fabs(y) (4) b (5) a 解析 根据“说明”中对二分法的说明,我们知道当 f(a)*f(b) 0(即 y1*y20)的时候,在区间(a,b)中必然存在 f(x)的根。下一步就应该“取该区间的中点 m”,所以空(1)就应该是将
21、区间(a,b)的中点 m 赋值给 x,即答案为“(a+b)/2”;空(2)则应该是判断这个新的 x 带进函数中看结果 y 是否满足条件“f(x) =0”,所以空(2)的答案为“f(x)”或者是“f(a+b)/2)”等其他等价的值。 得到新的 f(x)值之后,首先判断其绝对值是否满足条件(几乎接近于 0)小于 0.001,所以空(3)的答案为“fabs(y)”或者“fabs(f(x)”、“fabs(f(a+b)/2)”都可以。 如果满足求解的条件(几乎接近于 0)就说明 x 为函数 f(x)的根,直接输出根 x。如果不满足条件,根据题意我们需要判断 f(a)与 f(m)的符号是否相反,如果符号相
22、反,则说明“f(x)=0”的根存在于新的区间(a,m)之间,就需要把 m 的值(也是 x 的值)赋值给 b,创建新的 (a,b)区间用来求解,所以空(4)应该是将 x 的值赋给“b”;如果符号相同,则 f(b)与 f(m)的符号是相反的,说明“f(x)=0”的根存在于新的区间(m,b)之间,就需要把 m 的值(也是 x 的值)赋值给 a,创建新的 (a,b)区间用来求解,所以空(5)的答案为“a”。 在做这道题的时候需要注意两点: (1)已知的条件“ab”,如果忽略了这点,后面的空(4)和空(5)就很难做出正确的答案; (2)x 为 f(x)的根的条件是“几乎接近于 0”,可能大于或者小于 0
23、,所以空(3)处在做判断的时候是需要绝对值小于 0.001。二、B试题二/B(总题数:1,分数:15.00)2.阅读以下说明和 C 函数,将应填入U (n) /U处的字句写在答题纸的对应栏内。B/B说明 1B/B函数 Counter(int n, int w)的功能是计算整数 n 的二进制表示形式中 1 的个数,同时用数组 w 记录该二进制数中 1 所在位置的权。例如,十进制数 22 的二进制表示为 10110。对于该二进制数,1 的个数为 3,在 w0中存入 2(即 21)、w1中存入 4(即 22)、w2中存入 16(即 24)。B/BC 函数 1B/Bint Counter(int n,
24、int w) int i =0,k=1;while(U (1) /U) if (n% 2) wi + =k;n=n/2;U (2) /U;return i;B/B说明 2B/B函数 Smove(int A,int n)的功能是将数组中所有的奇数都放到所有偶数之前。其过程为:设置数组元素下标索引 i(初值为 0)和 j(初值为 n-1),从数组的两端开始检查元素的奇偶性。若 Ai、Aj都是奇数,则从前往后找出一个偶数,再与 Aj进行交换;若 Ai、Aj都是偶数,则从后往前找出一个奇数,再与 Ai进行交换;若 Ai是偶数而 Aj是奇数,则交换两者,直到将所有的奇数都排在所有偶数之前为止。B/BC
25、函数 2B/Bvoid Smove(int A,int n) int temp,i=0,j=n-1;if(n2) return;while (ij)if(Ai % 2=1 elseif(Ai% 2 =0 else if(U (5) /U) temp=Ai;Ai=Aj;Aj=temp;i+, j-;(分数:15.00)_正确答案:()解析:(1) n!=0 (2) k*=2 (3) i+ (4) j+ (5) (Ai%2=0) k=mn? m:n; for(;(k% m! =0) |(k% n! =0);k+); return k; B/B问题 1B/B (1)请写出发生函数调用 test_f1
26、(9,6)时,函数的返回值;(2)请说明函数 test_f1 的功能。 B/B说明 2B/B 设在某 C 系统中为每个字符分配 1个字节,为每个指针分配 4 个字节,sizeof(x)计算为 x 分配的字节数。 函数 test_f2()用于测试并输出该 C 系统为某些数据分配的字节数。 B/BC 函数 2B/B void test_f2( ) char str =“NewWorld“; char* p=str; char i =/0; void* ptr =malloc(50); printf(“% d/t“,sizeof(str); printf(“% d/n“,sizeof(p); pri
27、ntf(“% d/t“,sizeof(i); printf(“% d/n“,sizeof(ptr); B/B问题 2B/B 请写出函数 test_f2()的运行结果。 B/B说明 3B/B 函数 test_f3(char s)的功能是:将给定字符串 s 中的所有空格字符删除后形成的串保存在字符数组tstr 中(串 s 的内容不变),并返回结果串的首地址。 B/BC 函数 3B/B char*test_f3 (const char s) char tstr50 = /0; unsigned int i, k=0; for (i =0;istrlen(s);i+) if(si! =“) tstrk
28、+=si; return tstr; B/B问题 3B/B 函数 test_f3()对返回值的处理有缺陷,请指出该缺陷并说明修改方法。(分数:15.00)_正确答案:()解析:问题 1: (1) 18 (2) 求 m 和 n 的最小公倍数 问题 2: 9 4 1 4 问题 3: 局部数组存放字符串作为函数的返回值是不可取的。应使用 maloc动态分配函数来进行分配空间,存储字符串结果,返回其首指针。 解析 问题 1: 阅读代码,我们可以看出 k 在的三行取得的是 m 和 n 中的最大值,for 循环的循环主体为空,可是却要满足“(k%m!=0),|(k%n!= 0)”的条件才能退出循环,即要求
29、 k 既是 m 的倍数也是 n 的倍数,而且 k 是通过自增得到的,即遇到第一个满足条件的值就立即退出循环返回 k 值,所以 k是 m 和 n 的最小公倍数。 调用 test_f1(9,6)时,返回 9 和 6 的最小公倍数 18。 问题 2: 9 4 1 4 str是 char 型数组,sizeof(str)求的是整个数组的长度,数组中总共保存了 8 个字符和 1 个结束符/0,所以长度为 9; p 是 char 型的指针,sizeof(p)求的是指针的长度,而不是 p 所指向的字符串的长度,指针的长度是固定的 4 个字节; i 是 char 型的字符,系统为每个字符分配一个字节,故长度为
30、1; ptr 是类型为空的指针,虽然类型为空但只能说明 ptr 所指向的对象的类型,ptr 自身是一个指针,是有固定长度4 的。 问题 3: tstr 是一个 char 型数组,但它是在函数 test_f3 中定义的局部变量,在函数调用结束时内存空间就会被释放掉,返回的指针可能为空,也有可能是乱码,正确的修改方法就是使用 malloc 函数来动态地申请内存,然后返回这片内存的首指针,这样就会避免函数返回时内存被释放掉。 另外需要注意的是,本大题在一开始就指明是 C 函数,所以这里不可以使用 new 来动态申请内存。四、B试题四/B(总题数:1,分数:15.00)4.阅读以下说明和 C 函数,将
31、解答填入答题纸的对应栏内。 说明 函数 del_substr(S,T)的功能是从头至尾扫描字符串 S,删除其中与字符串 T 相同的所有子串,其处理过程为:首先从串 S 的第一个字符开始查找子串 T,若找到,则将后面的字符向前移动将子串 T 覆盖掉,然后继续查找子串 T,否则从串 S 的第二个字符开始查找,依此类推,重复该过程,直到串 S 的结尾为止。该函数中字符串的存储类型 SString定义如下: typedef struct char* ch; /*串空间的首地址*/ int length; /*串长*/ SString; C函数 void del_substr(SString* S, S
32、String T) iht i, j; if(S-length1 |T.length1 |S-lengthT.length) return; i=0; /* i 为串 S 中字符的下标*/ for (;) j =0; /*j 为串 T 中字符的下标*/ while(iS-length j+; else i=U (1) /U;j=0; /*i 值回退,为继续查找 T 做准备*/ if(U (2) /U) /*在 s 中找到与 T 相同的子串*/ i=U (3) /U; /*计算 s 中子串 T 的起始下标*/ for(k=i+T.length;kS-length;k+)/* 通过覆盖子串 T 进
33、行删除*/ S-chU (4) /U =S-chk; S-length=U (5) /U; /* 更新 S 的长度*/ else break; /* 串 S 中不存在于串 T*/ (分数:15.00)_正确答案:()解析:(1) i-j+1 (2) j=T.length (3)i-T.length (4) i+ (5) S-length-T.length 解析 空(1)处主要实现的功能是当串 S 和串 T 中有字母不相同时,串 S 下标需要返回至上一次串 S 和串 T 字符不同的位置,为继续查找串 T 做准备,串 S 的下标 i 返回的位置是串 T 的下标走过的长度,所以空(1)处应填“i-j
34、+1”。因为 j 表示串 S 与串 T 比较中串 T 的下标,如果 j 的值等于串 T 的长度,则表示串 S 中有与串 T相同的子串,所以空 (2)处应该填写 j=T.length。因为串 S 和串 T 在比较时,若字符一样,i 和 j 同时加 1,所以,串 S 在子串 T 的起始下标,应该为 S 的当前下标 i 减去串 T 的长度,即 i-T.length,所以空(3)处应填“i-T.length”。删除与串 T 相同的子串的方法是将后面的元素向前移动进行覆盖,应该从串S 在子串 T 的起始下标 i 开始,将后面的元素依次向前移动,最终覆盖子串,所以空(4)处填 i+。每当删除一个与串 T
35、相同的子串,串 S 的长度就减少 T.length,所以空(5)处填 S-length-T.length。五、B试题五/B(总题数:1,分数:15.00)5.阅读以下说明和 C+代码,将应填入U (n) /U处的字句写在答题纸的对应栏内。 B/B说明B/B 已知类 LinkedList 表示列表类,该类具有四个方法:addElement()、lastElement()、 numberOfElement()以及 removeLastElement()。四个方法的含义分别为: void addElement(Object):在列表尾部添加一个对象; Object lastElement():返回列
36、表尾部对象; int numberOfElement():返回列表中对象个数; void removeLastElement():删除列表尾部的对象。 现需要借助 LinkedList 来实现一个 Stack 栈类,C+代码 1 和 C+代码 2 分别采用继承和组合的方式实现。 B/BC+代码1B/B class Stack :public LinkedList public : void push (Object o) addElement (o); ; /压栈 Object peek() returnU (1) /U; /获取栈顶元素 bool i sEmpty () /判断栈是否为空 r
37、eturn numberOfElement ( ) = 0; ); Object pop () /弹栈 Object o = lastElement(); U (2) /U; return o; ; ; B/BC+代码 2B/B class Stack private: U (3) /U; public: void push (Object o) /压栈 list. addElement (o); ; Object peek() /获取栈顶元素 return list.U (4) /U; ; bool isEmpty () /判断栈是否为空 return list. numberOfEleme
38、nt ( ) = = 0; Object pop() /弹栈 Object o = list. lastElement ();list. removeLastElement ( ); return o; ; B/B问题B/B 若类 LinkedList 新增加了一个公有的方法 removeElement(int index),用于删除列表中第 index 个元素,则在用继承和组合两种实现栈类 Stack 的方式中,哪种方式下 Stack 对象可访问方法 removeElement(int index)?U (5) /U(A继承 B组合)(分数:15.00)_正确答案:()解析:(1)lastE
39、lement() (2) removeLastElement() (3) LinkedList list (4) lastElement() (5) A 解析 根据代码注释,程序代码中空(1)处用来获取栈顶元素,而父类 LinkedList 提供的成员函数lastElement()可以实现此功能,因此此处调用该函数即可,所以空(1)处填写 lastElement()。空(2)处主要执行“弹栈”操作,根据 Object pop()函数的要求,元素弹出栈主要有两个步骤,一是获取栈顶元素,即返回队列尾部对象;二是删除栈顶元素,即删除队列尾部的对象,调用 removeLastElement()函数即可
40、实现,所以空(2)处应该填“removeLastElement()“。空(3)处要求定义一个对象,再根据后面程序代码的提示,可以知道该对象名字为 list,类型为 LinkedList,所以空(3)处应填”LinkedList list”。空(4)处用于获取栈顶元素,即返回队列尾部的对象,类 LinkedList 的 lastElement()函数即可实现该功能,所以空(4)处应填“lastElement()”。类的继承是指子类的对象拥有对父类的成员和属性进行访问的权限,通过继承可以使用父类提供的 removeElement()方法,类的组合描述的是一个类内嵌其他类的对象作为成员的情况,描述的
41、是一种包含和被包含的关系,所以通过组合 Stack 对象并不能访问 LinkedList提供的方法 removeElement(int index),所以空(5)应填 A。六、B试题六/B(总题数:1,分数:15.00)6.阅读以下说明和 Java 代码,将应填入U (n) /U处的字句写在答题纸的对应栏内。 B/B说明B/B 已知类 LinkedList 表示列表类,该类具有四个方法:addElement()、lastElement()、HumberOfElement()以及 removeLastElement()。四个方法的含义分别为: void addElement(Object):在列表尾部添加一个对象; Object lastElement():返回列表尾部对象; int numberOfElement():返回列表中对象个数; void removeLastElement():删除列表尾部的对象。 现需要借助 Link