初级程序员2009下半年下午试题.doc

全国计算机技术与软件专业技术资格(水平)考试2009年下半年试卷下午试题 1本试卷的试题中共有75个空格，需要全部解答。 2每个空格对应一个序号，有A、B、C、D四个选项，请选择一个最恰当的选项作为解答。 试题一 阅读以下说明和流程图，填补流程图中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 求连续函数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)中。因此，根的范围缩小了一半。 依此类推，将区间一半一半地分下去，当区间的长度很小(达到根的精度要求，例如 0.001)时，或者当区间中点处的函数值几乎接近于0(即绝对值小于预先规定的微小量，例如 0.001)时，近似计算就可以结束了。 以下流程图描述了用二分法近似计算区间(a,b)中f(x)的根的过程。 流程图 试题二 阅读以下说明和C函数，将应填入 (n) 处的字句写在答题纸的对应栏内。 说明1 函数Counter(int n, int w)的功能是计算整数n的二进制表示形式中1的个数，同时用数组w记录该二进制数中1所在位置的权。 例如，十进制数22的二进制表示为10110。对于该二进制数，1的个数为3，在w0中存入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、Aj都是奇数，则从前往后找出一个偶数，再与Aj进行交换；若Ai、Aj都是偶数，则从后往前找出一个奇数，再与Ai进行交换；若Ai是偶数而Aj是奇数，则交换两者，直到将所有的奇数都排在所有偶数之前为止。 C函数2 void Smove(int A,int n) int temp,i=0,j=n-1; if(n2) return; while (ij) if(Ai % 2=1 & Aj% 2 =1) (3) ; elseif(Ai% 2 =0 &Aj% 2 =0) (4) ; else if( (5) ) temp=Ai;Ai=Aj;Aj=temp; i+, j-; 试题三 阅读以下说明、C函数和问题，将解答写入答题纸的对应栏内。 说明1 函数test_f1(int m,int n)对整数m、n进行某种运算后返回一个整数值。 C函数1 int test_f1(int m,int n) int k; k=mn? m:n; for(;(k% m! =0) |(k% n! =0);k+); return k; 问题1 (1)请写出发生函数调用test_f1(9,6)时，函数的返回值； (2)请说明函数test_f1的功能。 说明2 设在某C系统中为每个字符分配1个字节，为每个指针分配4个字节，sizeof(x)计算为 x分配的字节数。 函数test_f2()用于测试并输出该C系统为某些数据分配的字节数。 C函数2 void test_f2( ) char str =NewWorld; char* p=str; char i =0; void* ptr =malloc(50); printf(% dt,sizeof(str); printf(% dn,sizeof(p); printf(% dt,sizeof(i); printf(% dn,sizeof(ptr); 问题2 请写出函数test_f2()的运行结果。 说明3 函数test_f3(char s)的功能是：将给定字符串s中的所有空格字符删除后形成的串保存在字符数组tstr中(串s的内容不变)，并返回结果串的首地址。 C函数3 char*test_f3 (const char s) char tstr50 = 0; unsigned int i, k=0; for (i =0;istrlen(s);i+) if(si! =) tstrk+=si; return tstr; 问题3 函数test_f3()对返回值的处理有缺陷，请指出该缺陷并说明修改方法。 试题四 阅读以下说明和C函数，将解答填入答题纸的对应栏内。 说明 函数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, 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 T.length) /* 在串S中查找与T才目同的子串*/ if(S-chi =T.chj) i+; j+; else i= (1) ;j=0; /*i值回退，为继续查找T做准备*/ if( (2) ) /*在s中找到与T相同的子串*/ i= (3) ; /*计算s中子串T的起始下标*/ for(k=i+T.length;kS-length;k+)/* 通过覆盖子串T进行删除*/ S-ch (4) =S-chk; S-length= (5) ; /* 更新S的长度*/ else break; /* 串S中不存在于串T*/ 试题五 阅读以下说明和C+代码，将应填入 (n) 处的字句写在答题纸的对应栏内。 说明 已知类LinkedList表示列表类，该类具有四个方法：addElement()、lastElement()、 numberOfElement()以及removeLastElement()。四个方法的含义分别为： void addElement(Object)：在列表尾部添加一个对象； Object lastElement()：返回列表尾部对象； int numberOfElement()：返回列表中对象个数； void removeLastElement()：删除列表尾部的对象。 现需要借助LinkedList来实现一个Stack栈类，C+代码1和C+代码2分别采用继承和组合的方式实现。 C+代码1 class Stack :public LinkedList public : void push (Object o) addElement (o); ; /压栈 Object peek() return (1) ; /获取栈顶元素 bool i sEmpty () /判断栈是否为空 return numberOfElement ( ) = 0; ); Object pop () /弹栈 Object o = lastElement(); (2) ; return o; ; ; C+代码2 class Stack private: (3) ; public: void push (Object o) /压栈 list. addElement (o); ; Object peek() /获取栈顶元素 return list. (4) ; ; bool isEmpty () /判断栈是否为空 return list. numberOfElement ( ) = = 0; Object pop() /弹栈 Object o = list. lastElement (); list. removeLastElement ( ); return o; ; 问题 若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第 index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)? (5) (A继承 B组合) 试题六 阅读以下说明和Java代码，将应填入 (n) 处的字句写在答题纸的对应栏内。 说明 已知类LinkedList表示列表类，该类具有四个方法：addElement()、lastElement()、 HumberOfElement()以及removeLastElement()。四个方法的含义分别为： void addElement(Object)：在列表尾部添加一个对象； Object lastElement()：返回列表尾部对象； int numberOfElement()：返回列表中对象个数； void removeLastElement()：删除列表尾部的对象。 现需要借助LinkeedList来实现一个Stack栈类，Java代码1和Java代码2分别采用继承和组合的方式实现。 Java代码1 public class Stack extends binkedList public void push(Object o) /压栈 addElement (o); public Object peek() /获取栈顶元素 return ( 1 ) ; public boolean isEmpty() /判断栈是否为空 return numberOfElement () =0; public Object pop() /弹栈 Object o=lastElement(); (2) ; return o; Java代码2 public class Stack private ( 3 ) ; public Stack() list = new LinkedList (); public void push (Object o) list. addElement (o); public Object peek() /获取栈顶元素 return list. (4) ; public boolean isEmpty () /判断栈是否为空 return list.numberOfElement()=0; public Object pop() /弹栈 Object o =list.lastElement(); list.removeLastElement(); return o; 问题 若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第 index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)? (5) (A继承 B组合)2009年下半年试卷下午试题 试题一 试题答案 (1) (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)就应该是将区间(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)的符号是否相反，如果符号相反，则说明“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，所以空(3)处在做判断的时候是需要绝对值小于0.001。 试题二 试题答案 (1) n!=0 (2) k*=2 (3) i+ (4) j+ (5) (Ai%2=0)&(Aj%2=1) 解析 根据函数1的例子看出while循环中就是要把十进制整数。转换为二进制，并对为1的位数进行保存，所以循环的条件就是“n!= 0”，一旦n=0，就说明n的二进制已经表示完毕，所以空(1)的答案为“n!=0”或者是“n0”。每执行一次“n=n/2”，二进制的数就增加一位，因为要保存二进制数中1所在位置的权，所以k的值就需要乘以2来记录当前位置的权，故空(2)的答案为“kk*2”或者“k*=2”。空(3)是满足条件Ai和Aj都是奇数时的处理过程，从“说明2”中我们知道这时候需要“从前往后找出一个偶数”，所以空(3)的答案为“i+”，向后寻找偶数；空(4)是满足条件Ai和Aj都是偶数时的操作，这时需要“从后往前找出一个奇数”，所以空(4)的答案为“j-”，从后面向前寻找奇数；满足空(5)的条件之后的操作是将ACi和Aj进行交换，从“若Ai是偶数而Aj是奇数，则交换两者”这句话，可以看出满足将Ai和Aj进行交换的条件是Ai是偶然而Aj是奇数，即空(5)的答案为“(Ai%2=0)&(Ai%2=1)”。 试题三 试题答案 问题1： (1) 18 (2) 求m和n的最小公倍数 问题2： 9 4 1 4 问题3： 局部数组存放字符串作为函数的返回值是不可取的。应使用 maloc动态分配函数来进行分配空间，存储字符串结果，返回其首指针。 解析 问题1： 阅读代码，我们可以看出k在的三行取得的是m和n中的最大值，for循环的循环主体为空，可是却要满足“(k%m!=0)，|(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个结束符0，所以长度为9； p是char型的指针，sizeof(p)求的是指针的长度，而不是p所指向的字符串的长度，指针的长度是固定的4个字节； i是char型的字符，系统为每个字符分配一个字节，故长度为1； ptr是类型为空的指针，虽然类型为空但只能说明ptr所指向的对象的类型，ptr自身是一个指针，是有固定长度4的。 问题3： tstr是一个char型数组，但它是在函数test_f3中定义的局部变量，在函数调用结束时内存空间就会被释放掉，返回的指针可能为空，也有可能是乱码，正确的修改方法就是使用malloc函数来动态地申请内存，然后返回这片内存的首指针，这样就会避免函数返回时内存被释放掉。 另外需要注意的是，本大题在一开始就指明是C函数，所以这里不可以使用new来动态申请内存。 试题四 试题答案 (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+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相同的子串，串S的长度就减少T.length，所以空(5)处填S-length-T.length。 试题五 试题答案 (1) lastElement() (2) removeLastElement() (3) LinkedList list (4) lastElement() (5) A 解析 根据代码注释，程序代码中空(1)处用来获取栈顶元素，而父类LinkedList提供的成员函数lastElement()可以实现此功能，因此此处调用该函数即可，所以空(1)处填写lastElement()。空(2)处主要执行“弹栈”操作，根据Object pop()函数的要求，元素弹出栈主要有两个步骤，一是获取栈顶元素，即返回队列尾部对象；二是删除栈顶元素，即删除队列尾部的对象，调用removeLastElement()函数即可实现，所以空(2)处应该填“removeLastElement()“。空(3)处要求定义一个对象，再根据后面程序代码的提示，可以知道该对象名字为list，类型为 LinkedList，所以空(3)处应填”LinkedList list”。空(4)处用于获取栈顶元素，即返回队列尾部的对象，类LinkedList的lastElement()函数即可实现该功能，所以空(4)处应填“lastEle