2009年下半年程序员下午试卷案例

【说明】
求连续函数f(x)的根（方程f(x)=o的解）的最简单方法是二分法。为此，首先需要在若干点上检查函数值的符号，如果发现f(a)与f(b)符号相反（a<b)，则在区间（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)的根的过程。

问题：1.1 【流程图】

【说明1】
函数Counter(intn，int w[])的功能是计算整数n的二进制表示形式中1的个数，同时用数组w记录该二进制数中1所在位置的权。
例如，十进制数22的二进制表示为10110。对于该二进制数，1的个数为3,在w[0]中存入2 (即2¹)、w[1]中存入4 (即2²)、w[2]中存入16 (即2⁴)。
【说明2】
函数Sm0Ve(int A[], int n)的功能是将数组中所有的奇数都放到所有偶数之前。其过程为：设置数组元素下标索引i (初值为0)和j (初值为n-1)，从数组的两端开始检查元素的奇偶性。若A[i]、A[j]都是奇数，则从前往后找出一个偶数，再与A[j]进行交换; 若A[i]、A[j]都是偶It则从后往前找出一个奇数，再与A[i]进行交换；若A[i]是偶数而A[j]是奇数，则交换两者，直到将所有的奇数都排在所有偶数之前为止。

问题：2.1

【说明1】
函数test_f1(int m, int n)对整数m、n进行某种运算后返回一个整数值。
【C函数1】

问题：3.1 (1)请写出发生函数调用test_f1(9,6)时，函数的返回值；
(2)请说明函数test_f1的功能。

问题：3.2 请写出函数test_f2()的运行结果。

问题：3.3 函数test_f3()对返回值的处理有缺陷，请指出该缺陷并说明修改方法。

【说明1】
函数test_f1(int m, int n)对整数m、n进行某种运算后返回一个整数值。
【C函数1】

问题：3.1 (1)请写出发生函数调用test_f1(9,6)时，函数的返回值；
(2)请说明函数test_f1的功能。

问题：3.2 请写出函数test_f2()的运行结果。

问题：3.3 函数test_f3()对返回值的处理有缺陷，请指出该缺陷并说明修改方法。

【说明1】
函数test_f1(int m, int n)对整数m、n进行某种运算后返回一个整数值。
【C函数1】

问题：3.1 (1)请写出发生函数调用test_f1(9,6)时，函数的返回值；
(2)请说明函数test_f1的功能。

问题：3.2 请写出函数test_f2()的运行结果。

问题：3.3 函数test_f3()对返回值的处理有缺陷，请指出该缺陷并说明修改方法。

【说明】
函数del_substr(S，T)的功能是从头至尾扫描字符串S，删除其中与字符串T相同的所有子串，其处理过程为：首先从串S的第一个字符开始查找子串T，若找到，则将后面的字符向前移动将子串T覆盖掉，然后继续查找子串T;否则从串S的第二个字符开始查找，依此类推，重复该过程，直到串S的结尾为止。该函数中字符串的存储类型SString定义如下：

问题：4.1

【说明】
已知类LinkedList表示列表类，该类具有四个方法:addElement()、lastElement()、number-OfElement()以及removeLastElement()。四个方法的含义分别为：
void addElement(Object)：在列表尾部添加一个对象；
Object lastElement()：返回列表尾部对象；
int numberOfElement()：返回列表中对象个数；
void removeLastElement()：删除列表尾部的对象。
现需要借助LinkedList来实现一个Stack栈类，C++代码1和C++代码2分别采用继承和组合的方式实现。

问题：5.1

若类LinkedList新增加了一个公有的方法removeElement(int. index),用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)? (5) (A.继承B.组合）

【说明】
己知类LinkedList表示列表类，该类具有四个方法:addElement()、lastElement()、number-Offilement()以及removeLastElement()。四个方法的含义分别为：
void addElement(Object)：在列表尾部添加一个对象；
Object lastElement()：返回列表尾部对象；
int numberOfElement()：返回列表中对象个数；
void removeLastElement()：删除列表尾部的对象。
现需要借助LinkedList来实现一个Stack栈类，Java代码1和Java代码2分别采用继承和组合的方式实现。

问题：6.1

若类LinkedList新增加了一个公有的方法removeElement(int index),用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(intindex)? (5) (A.继承B.组合）