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) (a+b)/2
(2) f(x),或f((a+b)/2)
(3) |y|,或abs(y)，其中y 可由f(x)或f((a+b)/2)代替
(4) b
本题描述了求函数根（0点）的二分法，题中还详细说明了二分法的原理。
假设a和b是区间两端点值的变量。流程图中，一开始就将函数两端的值分别送y1和y2,接着判断yl与y2符号是否相反（同号时该算法不能往下进行)。若相反，则应将a与b的中点值(a+b)/2送x。此时的函数值f(x)，即f((a+b)/2)应送y。因此，（1)处应填(a+b)/2，(2)处可填f(x)或f((a+b)/2)。
接着需要判断新的函数值是否已经接近0,因此，（3)处应填丨y丨或abs(y)。
令数组全部的值为0如果这个新函数值已经接近0,则可以直接输出变量x的值（刚取的中点值）作为函数的近似根;如果该函数值尚未接近0,则需要将该区间进行二分，即需要判断选用左半区间还是右半区间，继续进行迭代计算。
如果y*y1<0,则说明新的函数值与原区间的左端函数值符号相反，因此应取左半区间；否则应取右半区间。
若取左半区间，则原来的区间左端点a没有变化，左端点的函数值yl也没有变化，只要将中点值x送右端点变量b就可以。因此，（4)处填b。
若取右半区间，则区间的右端点没有变化，右端点的函数值y2也没有变化，这时需要将中点值x送左端点变量a。因此，（5)处应填a。由于每次迭代都需要判断y*y1的符号，因此y1的改变将影响下次迭代。因此，此时还需要将中点处的函数值y送y1，作为新区间的左端点函数值。
当新的区间(a，b)长度ha很小时，迭代计算就可以结束，输出已经得到的近似根x就可以了。
试题二
【说明1】
函数Counter(intn，int w[])的功能是计算整数n的二进制表示形式中1的个数，同时用数组w记录该二进制数中1所在位置的权。
例如，十进制数22的二进制表示为10110。对于该二进制数，1的个数为3,在w[0]中存入2 (即21)、w[1]中存入4 (即22)、w[2]中存入16 (即24)。
【说明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)n!=0,或其等价形式
(2)k=k*2，或k*=2，或k+=k，或k=k+k,或其等价形式
(3)i++,或++i,或i+=1,或i=i+1，或其等价形式
(4)j--，或--j，或j-=1，或j=j-1，或其等价形式
(5)A[i]%2=0&&A[j]%2!=1，或A[i]%2!=0&&A[j]%2，或!(A[i]%2)&&A[j]%2,或其等价形式

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。