1、2009年下半年软件水平考试（初级）程序员下午（应用技术）试题真题试卷及答案与解析 1 阅读以下说明和流程图，填补流程图中的空缺 (1)一 (5)，将解答填入答题纸的对应栏内。【说明】 求连续函数 f(x)的根 (方程 f(x)=0的解 )的最简单方法是二分法。为此，首先需要在若干点上检查函数值的符号，如果发现 f(a)与 f(b)符号相反(a 2 阅读以下说明和 c函数，将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明1】 函数 Counter(int n， int w)的功能是计算整数 n的二进制表示形式中 1的个数，同时用数组 w记录该二进制数中 1所在位置的权。例如，十进制数
2、22的二进制表示为 10110。对于该二进制数， l的个数为 3，在 wO中存入 2(即 21)、 w1中存人 4(即 22)、 w2中存入 16(即 24)。 【 C函数 1】 int counter(int n， int w)( int i=0， k=1 ； while( (1) ) if(n 2)wi+ =k； n=n 2； (2) ； ) return i； ) 【说明2】 函数 smove(int A， int n)的功能是将数组中所有 的奇数都放到所有偶数之前。其过程为：设置数组元素下标索引 i(初值为 0)和 j(初值为 n-1)，从数组的两端开始检查元素的奇偶性。若 Ai、 A
3、j都是奇数，则从前往后找出一个偶数，再与 Aj进行交换；若 Ai、 Aj都是偶数，则从后往前找出一个奇数，再与 Ai进行交换；若 Ai是偶数而 Aj是奇数，则交换两者，直到将所有的奇数都排在所有偶数之前为止。 【 c函数 2】 void Smove(int A， in七 n)( int temp， i=0， j=n-1 ； if(n 3 阅读以下说明、 C函数 和问题，将解答写入答题纸的对应栏内。 【说明 1】 函数 test_fl(int m， im n)对整数 m、 n进行某种运算后返回一个整数值。 【 c函数 1】 int test_f1 (int m， int n) int k； k=
4、mn?m： n； for(； (k m! =O) I I (k n! =0)； k+)； return k； ) 【问题 1】 (5分 )(1)请写出发生函数调用 test_fl(9， 6)时，函数的返回值； (2)请说明函数 test_f1的功能。 【说明 2】 设在某 c系统中为每 个字符分配 1个字节，为每个指针分配 4个字节， sizeof(x)计算为 x分配的字节数。 函数 test_12Q用于测试并输出该 c系统为某些数据分配的字节数。 【 c函数 2】 void test_f2() char str =“NewWorld”； char*p=str； char i= 0； VOid
5、*ptr=malloc(50)； printf(” d t”， sizeof(str)； printf(“ d n”， sizeof(p)， printf(” d t”， sizeof(i)； printf(” d n”， sizeof(ptr)； 【问题 2】 (4分 ) 请写出函数 test_f2()的运行结果。 【说明 3】 函数 test_f3(char S)的功能是：将给定字符串 S中的所有空格字符删除后形成的串保存在字符数组 tstr中 (串 S的内容不变 )，并返回结果串的首地址。 【 C函数 3】 char*test_f3(const char s)( char tstr50=
6、( 0)； unslgned int i， k=0； for(i=0； i(strlen(s)； i+) if(si!=)tstrk+=si； return tStr ； ) 【问题 3】 (6分 ) 函数 test_f3()对返回值的处理有缺陷，请指出该缺陷并说明修改方法。 4 阅读以下说明和 C函数，将解答填入答题纸的对应栏内。 【说明】 函数 del_substr(S， T)的功能是从头至尾扫描字符串 S，删除其中与字符串 T相同的所有子串，其处理过程为：首先从串 S的第一个字符开始查找子串 T，若找到，则将后面的字符向前移动将子串 T覆盖掉，然后继续查找子串 T，否则从串 S的第二个字
7、符开始查找，依此 类推，重复该过程，直到串 S的结尾为止。该函数中字符串的存储类型 SString定义如下： typedef struct char*ch； *串空间的首地址 * int length； *串长 * SString； 【 c函数】 void del_substr(SString*S， SString T)( int i， j ； if(S-lengthlength(T length) return； i=0： *i为串 S中字符的下标 * for(； ) J=0 ； *j为串 T中字符的下标 * while(ilength jchi=T chj) i+； J+； ) else
8、i= (1) ； j=0； *i值回退，为继续查找 T做准备 * ) ) if( (2) )( *在 S中找到与 T相同的子串 * i= (3 ) ； *计算 S 中子串 T的起始下标 * for(k=i+T 1ength； klength； k+) *通过覆盖子串 T进行删除 * S-ch (4) =S-chk； S-)length= (5； ) ； *更新 S的长度 * ) else break； *串 S中不存在子串 T* ) ) 5 阅读以下说明和 C+代码，将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 已知类 LinkedList表示列表类，该类具有四个方法： addE
9、lement()、 lastElement()、 numberOfElement()以及 removeLastElement()。四个方法的含义分别为： void addElement(Object)：在列表尾部添加一个对象； Object lastElement()：返回列表尾部对象； int numberOfElement()：返回列表中对象个数； void removeLastElement()：删除列表尾部的对象。 现需要借助 LinkedList 来实现一个 Stack栈类， c+代码 1和 c+代码 2分别采用继承和组合的方式实现。 【 C+代码 1】 Class Stack： p
10、ubliC LinkedList public： void push(Object.o)(addElement(o)； )； 压栈 Object peek()return (1)； )； 获取栈顶元素 bool isEmpty()- 判断栈是否为空 return numberOfElement() =0 ； )； Object pop() 弹栈 Object o=lastElement()； (2) ； return o； ； ： 【 c+代码 2】 Class Stack private： (3) ； publiC： void push(Object O) 压栈 list addElemen
11、t(o)； )； ObjeCt peek() 获取栈顶元素 return list (4)； )； bool isEmpty() 判断栈是否为空 return 1ist numberOfElement()=0； )； Object pop() 弹栈 Object O=list lastElement()； 1ist removeLastElemen七 ()； return 0； )； )； 【问题】 若类 LinkedList新增加了一个公有的方法 removeElement(int index)，用于删除列表中第 index个元素，则在用继承和组合两种实现栈类 Stack的方式中，哪种方式下
12、Stack对象可访问方法 removeElement(int index)? (5) (A继承 B组合 ) 6 阅读以下说明和 Java代码，将应填入 (n) 处的字句 写在答题纸的对应栏内。 【说明】 已知类 LinkedList表示列表类，该类具有四个方法： addElement()、 lastElemcnt()、 numberOfElement()以及 removeLastElement()。四个方法的含义分别为： void addElement(Object)：在列表尾部添加一个对象； Object lastElement()：返回列表尾部对象； int numberOfElement
13、()：返回列表中对象个数； void removeLastElement()：删除列表尾部 的对象。 现需要借助 LinkedList 来实现一个 Stack栈类， Java代码 1和 Java代码 2分别采用继承和组合的方式实现。 【 Java代码 1】 public class Stack extends LinkedList public void push(Object o) 压栈 addElement(O)； ) public Object peek() 获取栈顶元素 return (1 ) ； ) public boolean isEmpty()( 判断栈是否为空 return n
14、umberOfElement()=0 ； ) public Object pop()( 弹栈 Object o=lastElement()； (2)； return o； ) ) 【 Java代码 2】 public clasB Stack private ( 3) ； public Stack() list=new LinkedList()； public void push(Object o) 1ist addElement(o)； public Object peek() 获取栈顶元素 return list (2) ； public boolean isEmpty() t,1断栈是否为
15、空 return 1ist numberOfElement()=0； public Object pop()( 弹栈 Object o=list 1astElement()； 1ist removeLastElement()； return o； 【问题】 若类 LinkedList新增加了一个公有的方法 removeElement(int index)，用于删除列表中第 index个元素，则在用继承和组合两种实现栈类 Stack的方式中，哪种方式下Stack对象可访问方法 removeElement(int index)? (5) (A继承 B组合 ) 2009年下半年软件水平考试（初级）程
16、序员下午（应用技术）试题真题试卷答案与解析 1 【正确答案】 (1)(a+b) 2 (2)f(x) (3)fabs(y) (4)b (5)a 【 试题解析】 根据 “说明 ”中对二分法的说明，我们知道当 f(a)*f(b)0”。每执行一次“n=n 2”，二进制的数就增加一位，因为要保存二进制数中 l 所在位置的权，所以 k 的值就需要乘以 2来记录当前位置的权，故空 (2)的答案为 “k=k * 2”或者“k*=2”。空 (3)是满足条件 Ai和 Aj都是奇数时的处理过程，从 “说明 2”中我们知道 这时候需要 “从前往后找出一个偶数 ”，所以空 (3)的答案为 “i+”，向后寻找偶数；空 (
17、4)是满足条件 Ai和 Aj都是偶数时的操作，这时需要 “从后往前找出一个奇数 ”，所以空 (4)的答案为 “j-”，从后面向前寻找奇数；满足空 (5)的条件之后的操作是将 Ai和 Aj进行交换，从 “若 Ai是偶数而 Aj是奇数，则交换两者 ”这句话，可以看出满足将 Ai和 Aj进行交换的条件是 Ai是偶数而 Aj是奇数，即空(5)的答案为 “(Ai 2=0) &(Aj 2=1)”。 3 【正确答案 】 问题 l： (1)18 (2)求 m和 n的最小公倍数 问题 2： 9 4 1 4 问题 3： 局部数组存放字符串作为函数的返回值是不可取的。应使用 malloc 动态分配函数来进行分配空间
18、，存储字符串结果，返回其首指针。 【试题解析】 问题 l： 阅读代码，我们可以看出 k 在的三行取得的是 m和 n 中的最大值， for循环的循环主体为空，可是却要满足 “(k m!=O)I I(k n!=0)”的条件才能退出循环，即要求 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个结
19、束符 O，所以长度为 9； p是 char-型的指针， sizeof(p)求的是指针的长度，而不是 p所指向的字符串的长度，指针的长度是固定的 4个字节； i是char型的字符，系统为每个字符分配一个字节，故长度为 1； ptr是类型为空的指针，虽然类型为空但只能说明 ptr所指向的对象的类型， ptr自身是一个指针，是有固定长度 4的。 问题 3： tstr是一个 char型数组，但它是在函数 test_f3中定义的局部变量，在函数调用结束时内存空间就会被释放掉，返回的指针可能为空，也有可能是乱码，正确的修改方法就是使用 malloc函数来动态地申请内存，然后返回这片内存的首指针，这样就会避
20、免函数返回时内存被释放掉。另外需要注意的是，本大题在一开始就指明是 C函数，所以这里不可以使用 new来动态申请内存。 4 【正确答案】 (1)i-j+l (2)j=T length (3)i-T 1ength (4)i+(5)S-length-T length 【试题解析】 空 (1)处主要实现的功能是当串 s和串 T中有字母不相同时，串 s下标需要返回至上一次串 s和串 T字符不同的位置，为继续查找串 T做准备，串 s的下标 i返回的位置是串 T 的下标走过的长度，所以空 (1)处应填 “i-j+1”。因为 j表示串 s与串 T比较中串 T 的下标，如果 j的值等于串 T的长度，则表示串
21、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 相同的子串，串 s的长度就减少 T length，所以空 (5)处填 S-length-T length。 5
22、 【正确答案】 (1)lastElement： () (2)removeL,astElement() (3)LinkedList list(4)lastElement() (5)A 【试题解析】 根据代码注释，程序代码中空 (1)处用来获取栈顶元素，而父类L inkedlist提供的成员函数 lastElement()可以实现此功能，因此此处调用该函数即可，所以空 (1)处填写 lastElement ()。空 (2)处主要执行 “弹栈 ”操作，根据 Object pop()函数的要求，元素弹出栈主要有两个步骤，一是获取栈顶元素，即返回队列尾部对象；二是删除栈顶元素，即删除队列尾部的对象，调用
23、removeLastElement()函数即可实现，所以空 (2)处应该填 “removeLast。Element()”。空 (3)处要求定义一个对象，再根据后面程序代码的提示，可以知道该对象名字为 list，类型为 LinkedList，所以空 (3)处应填 ”LinkedList list”。空 (4)处用于获取栈顶元素，即返回队列尾部的对象，类 LinkedlList 的 lastElement()函数即可实现该功能，所以空 (4)处应填 “lastElement()”。类的继承是指子类的对象拥有对父类的成员和属性进行访问的权限，通过继承可以使用父类提供 的removeElement()
24、方法，类的组合描述的是一个类内嵌其他类的对象作为成员的情况，描述的是一种包含和被包含的关系，所以通过组合 Stack 对象并不能访问IinkedList 提供的方法 removeElement(int index)，所以空 (5)应填 A。 6 【正确答案】 (1)lastElement() (2)removeLast Element() (3)LinkedList list(4)lastElement() (5)A 【试题解析】 根据代码注释，程序代码中空 (1)处用来获取栈顶元素，而父类LinkedIjst提供的成员函数。 lastElement()可以实现此功能，因此此处调用该函数即可，
25、所以空 (1)处填写 lastElement()。空 (2)处主要执行 “弹栈 ”操作，根据 Object pop()函数的要求，元素弹出栈主要有两个步骤，一是获取栈顶元素，即返回队列尾部对象；二是删除栈顶元素，即删除队列尾部的对象，调用removeLastElement()函数即可实现，所以空 (2)处应该填 “removeLastElemeNt()”。空 (3)处要求定义一个对象，再根据后面 程序代码的提示，可以知道该对象名字为list，类型为 IinkedIjst，所以空 (3)处应填 “LinkedList list”。空 (4)处用于获取栈顶元素，即返回队列尾部的对象，类 LinkedList 的 lastElement()函数即可实现该功能，所以空 (4)处应填 “lastElement()”。类的继承是指子类的对象拥有对父类的成员和属性进行访问的权限，通过继承可以使用父类提供的 removeElement()方法，类的组合描述的是一个类内嵌其他类的对象作为成员的情况，描述的是一种包含和被包含的关系，所以通 过组合 Stack 对象并不能访问 LinkedList 提供的方法removeElement(int index)，所以空 (5)应填 A。
