程序员考题讲授3.docx

试题一〔2005年11月试题1〕
阅读下列说明和流程图，将应填入___(n)___处的字句写在答题纸的对应栏内。[流程图说明]流程图1-1描述了一个算法，该算法将给定的原字符串中的所有前导空白和尾部空白都删除，但保留非空字符的空白。例如，原字符串"FileName"，处理变成"FileName"。流程图1-2、流程图1-3、流程图1-4分别详细描述了流程图1-1中的框A、B、C。假设原字符串中的各个字符依次存放在字符数组ch的各元素ch(1)、ch(2)、?、ch(n)中，字符常量KB表示空白字符。流程图1-1的处理过程是：先从头开始找出该字符串中的第一个非空白字符ch(i)，再从串尾开始向前找出位于最末位的非空白字符ch(j)，然后将ch(i)、?、ch(j)依次送入ch(1)、ch(2)、?中。如果字符串中没有字符或全是空白字符，则输出相应的说明。在流程图中，strlen是取字符串长度函数。[流程图1-1]

[流程图1-2]

[流程图1-3]

[流程图1-4]

[问题]在流程图1-1中，判断框P中的条件可表示为：i>___(5)___
答案：
i<=n(2)ch(j)=KB(3)k<=j(4)ch(k-i+1)(5)n
试题二〔2005年5月试题1〕
阅读以下说明和流程图，回答问题1至问题2将解答填入答题纸的对应栏内。[说明]设8位二进制代码B0B1...B7中的最高位B0为奇偶校验位。对于任何给定的代码B1B2...B7，可按下式计算偶校验位：B0=B1⊕B2⊕…⊕B7其中，""表示"异或"运算。下面的流程图描述了计算偶校验位的过程。[流程图]

注：流程图，循环开始的说明按照"循环变量名：循环初值，循环终值，增量"格式描述。[问题1]将流程图中的（1）～（4）处补充完整。[问题2]若按下式计算奇校验位，则上述流程图中的（1）处应填（5）。B0=B1⊕B2⊕…⊕B7⊕1
答案：
0（2）1，7，1（3）Bi（4）B0（5）1
注意：异或、奇偶校验
试题三〔2004年11月试题1〕阅读下列说明和流程图，将应填入__(n)__的字句写在答题纸的对应栏内。【流程图说明]下面的流程图描述了对8位二进制整数求补的算法。该算法的计算过程如下：从二进制数的低位（最右位）开始，依次向高位逐位查看，直到首次遇到“1”时，停止查看。然后，对该“1”位左面的更高位（如果有的话），逐位求反，所得的结果就是对原二进制数求补的结果。例如：对二进制整数10101000求补的结果时01011000。设8位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的BIT[1]～BIT[8]中。例如，二进制整数10101000存放在数组BIT后，就有BIT[1]＝0，BIT[2]=0,…,BIT[7]=0,BIT[8]=1。若流程图中存在空操作，则用NOP表示。

流程图中__(1)__处按“循环变量名：循环初值，增量，循环终值”格式描述。
答案：
i:1，1，8(2)1→sw(3)0→BIT[i](4)NOP，或空操作(5)1→BIT[i]
试题四〔2004年5月试题1〕阅读下列说明、流程图和算法，将应填入__(n)__处的字句写在答题纸的对应栏内．[流程图说明]下面的流程图用N—S盒图形式描述了数组A中的元素被划分的过程．其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动．当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大子i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：[流程图][算法说明]将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数intp(intA[]，intlow，inthigh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数voidsort(intA[]，ihtL，intH)的功能是实现数组A中元素的递增排序。[算法]voidsort(intA[]，intl，intH){if(L<H){k=p(A，L，R)；//p()返回基准数在数组A中的下标sort(__(4)__；//小于基准数的元素排序sort__(5)__)；//大于基准数的元素排序}
提示：这是排序中的快速排序法

答案：
(1)j←j-1(2)I←i+1(3)A[i]←pivot或A[j]←pivot(4)A，L，k-1
(5)A，k+1，H
试题五〔2006年11月试题1〕阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。[说明]假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，