程序员考题讲授3.doc

试题一2005年11月试题1阅读下列说明和流程图，将应填入_(n)_处的字句写在答题纸的对应栏内。流程图说明流程图1-1描述了一个算法，该算法将给定的原字符串中的所有前导空白和尾部空白都删除，但保留非空字符的空白。例如，原字符串 File Name ，处理变成File Name 。流程图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)_ 答案：(1) 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= B1B2B7其中， 表示异或运算。下面的流程图描述了计算偶校验位的过程。流程图 注：流程图，循环开始的说明按照循环变量名：循环初值，循环终值，增量格式描述。问题1将流程图中的（1）（4）处补充完整。问题2若按下式计算奇校验位，则上述流程图中的（1）处应填（5） 。B0= B1B2B71答案：（1） 0（2） 1，7，1（3） Bi（4） B0（5） 1注意：异或、奇偶校验试题三2004年11月试题1阅读下列说明和流程图，将应填入_(n)_的字句写在答题纸的对应栏内。【流程图说明下面的流程图描述了对8位二进制整数求补的算法。该算法的计算过程如下：从二进制数的低位（最右位）开始，依次向高位逐位查看，直到首次遇到“1”时，停止查看。然后，对该“1”位左面的更高位（如果有的话），逐位求反，所得的结果就是对原二进制数求补的结果。例如：对二进制整数10101000求补的结果时01011000。设8位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的BIT1BIT8中。例如，二进制整数10101000存放在数组BIT后，就有BIT10，BIT2=0,BIT7=0,BIT8=1。若流程图中存在空操作，则用NOP表示。流程图中_(1)_处按“循环变量名：循环初值，增量，循环终值”格式描述。答案：(1) i:1，1，8(2)1sw(3) 0BITi(4)NOP，或空操作(5)1BITi试题四2004年5月试题1阅读下列说明、流程图和算法，将应填入_(n)_处的字句写在答题纸的对应栏内流程图说明下面的流程图用NS盒图形式描述了数组A中的元素被划分的过程其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动当划分结束时，基准数定位于Ai，并且数组中下标小于i的元素的值均小于基准数，下标大子i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：流程图算法说明将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A，iht L，int H)的功能是实现数组A中元素的递增排序。算法void sort(int A，int l，int H)if ( L H ) k=p(A，L，R)；/p()返回基准数在数组A中的下标sort(_ (4)_； /小于基准数的元素排序sort_ (5)_)；/大于基准数的元素排序提示：这是排序中的快速排序法答案：(1)j j-1(2)I i+1(3)Aipivot 或 A jpivot(4)A，L，k-1 (5)A，k+1，H 试题五2006年11月试题1阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。说明假设以二维数组 G1.m,1.n表示一幅图像各像素的颜色，则 Gi,j表示区域中 点(i,j)处的颜色，颜色值为 0 到 k 的整数。下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定 所有与点(i0,j0)同色的上、下、左、右可连通的点组成同色邻接区域。例如，一幅 89 像素的图像如图 1-1 所示。设用户指定点(3,5)，其颜色值为 0，此时其上方 (2,5)、下方 (4,5)、右方 (3,6)邻接点的颜色值都为 0，因此这些点属于 点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色 邻接区域的其他点（见图 1-1 中的阴影部分）。将上述同色区域的颜色替换为颜色值 7 所得的新图像如图 1-2 所示。算法输入：矩阵 G，点的坐标(i0,j0)，新颜色值 newcolor。输出：点(i0,j0)所在同色邻接区域的颜色置换为 newcolor 之后的矩阵 G。算法步骤(为规范算法，规定该算法只在第七步后结束)：第一步：若点(i0,j0)的颜色值与新颜色值 newcolor 相同,则 (1) ；第二步：点(i0,j0)的颜色值oldcolor；创建栈 S，并将点坐标(i0,j0)入栈；第三步：若 (2) ，则转第七步；第四步：栈顶元素出栈(x,y)，并 (3) ；第五步：1) 若点(x,y-1)在图像中且 Gx,y-1等于 oldcolor，则(x,y-1)入栈 S；2) 若点(x,y+1)在图像中且 Gx,y+1等于 oldcolor，则(x,y+1)入栈 S；3) 若点(x-1,y)在图像中且 Gx-1,y等于 oldcolor，则(x-1,y)入栈 S；4) 若点(x+1,y)在图像中且 Gx+1,y等于 oldcolor，则(x+1,y)入栈 S；第六步：转 (4) ；第七步：算法结束。问题是否可以将算法中的栈换成队列？回答： (5) 。答案：（1） 转第七步（2） 栈空（3） Gx,y newcolor（4） 第三步（5） 可以试题六2007年11月试题1阅读以下说明和流程图，填补流程图中的空缺（1）（5），将解答填入答题纸的对应栏内。说明某单位动态收集的数据中常包含重复的数据，所以需要进行处理，使得重复的数据仅出现一次。下面流程图的功能是：在n（n1）个数据D1、D2、Dn中，选出其中所有不重复的k个数据，置于原来前k个数据的位置上。该流程图的算法如下：第1个数据必然被选出，然后从第2个数据开始，逐个考察其余的数据。假设D1、D2、Dm（m1）是已经选出的、不重复的数据，则对于数据Di（min），将其依次与Dm、Dm-1、D1进行比较，若没有发现与之相同者，则Di被选出并置于Dm+1的位置上；否则对Di不做处理。 例如，如下10个数据：5，2，2，7，4，4，7，1，9，1 （n=10）经过上述算法处理后的结果为：5，2，7，4，1，9 （k=6）流程图注：循环开始的说明按照“循环变量名：循环初值，循环终值，增量”格式描述。答案：（1）1 （2）2 （3）m （4）Dm+1 （5）mm+1试题三2007年11月试题3阅读以下说明和C语言程序，将应填入 （n） 处的字句写在答题纸的对应栏内。说明某电信公司记录了每个用户的详细通话情况（每次通话数据记录在一行），现将某用户某月的通话数据存入一个文本文件“dial.txt”，其数据格式如下： 拨入或拨出标记 通话开始时间 通话结束时间 对方号码注1：数据字段以一个空格作为分隔符。注2：拨入和拨出标记均为小写字母。拨入标记为“i”，表示其他用户呼叫本机，本机用户不需付费；拨出标记为“o”，表示本机呼叫其他用户，此时本机用户需要付费。注3：通话开始和结束时间的格式均为：HH:MM:SS。其中HH表示小时，取值0023；MM表示分钟，取值0059；SS表示秒，取值0059。从通话开始到结束这段时间称为通话时间，假定每次通话时间以秒为单位，最短为1秒，最长不超过24小时。注4：跨月的通话记录计入下个月的通话数据文件。例如“o 23:01:12 00:12:15 ”表示本次通话是本机呼叫其他用户，时间从23时01分12秒至次日的0时12分15秒，通话时间为71分03秒。下面程序的功能是计算并输出该用户本月电话费(单位:元)。通话计费规则为：1. 月通话费按每次通话费累加；2. 每次的通话费按通话时间每分钟0.08元计算，不足1分钟时按1分钟计费。对于每次的拨出通话，程序中先分别计算出通话开始和结束时间相对于当日0点0分0秒的时间长度（以秒为单位），然后算出本次通话时间和通话费。例如，若输入文件dial.txt的数据如下所示，则输出fee = 7.44。o 14:05:23 14:11:25 82346789i 15:10:00 16:01:15 10:53:12 11:07:05 63000123o 23:01:12 00:12:15案： C程序代码#include FILE *fin;int main() char str80; int h1,h2,m1,m2,s1,s2; long t_start,t_end, interval; int c; double fee = 0; fin = fopen(dial.txt,r); if (!fin) return -1; while (!feof(fin) if (!fgets(str,80,fin) break; if ( （1） ) continue; h1 = (str2 - 48) * 10 + str3 - 48; m1 = (str5 - 48) * 10 + str6 - 48; s1 = (str8 - 48) * 10 + str9 - 48; h2 = (str11 - 48) * 10 + str12 - 48; m2 = (str14 - 48) * 10 + str15 - 48; s2 = (str17 - 48) * 10 + str18 - 48; t_start = h1*60*60 + m1*60 + s1; /* 通话开始时间 */ t_end = h2*60*60 + m2*60 + s2; /* 通话结束时间 */ if ( （2） ) /* 若通话开始和结束时间跨日 */ interval = （3） - t_start + t