2002年程序员试卷（下）

考试总分：5分

考试类型：模拟试题

作答时间：60分钟

已答人数：967

试卷答案：有

试卷介绍： 2002年程序员试卷（下）

开始答题

试卷预览

1. 试题五阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。设二叉树的结点数据类型为：typedefstructnode{chardata；structnode*left；structnode*right：}BTREE；[函数5.1说明]函数voidSortTreelnsert(BTREE**tree，BTREE*s)采用递归方法，将结点s插入以*tree为根结点指针的二叉排序树(二叉查找树)中。[函数5.1)voidSortTreelnsert(BTREE**tree，BTREE*S){if(*tree==NULL)*tree=S;elseif(S->datadata)SortTreelnsert((1)，S)；elseif(S->data>(*tree)->data)SortTreelnsert((2)，S)；}[函数5．2说明]函数voidTraversalTree(BTREE*tree)用非递归方法，对以tree为根结点指针的二叉树进行后序遍历。[函数5，2]voidTraversalTree(BTREE*tree){BTREE*stack[1000]，*p；inttag[1000]，top=0；p=tree；do{while(p!=NULL){stack[++top]=p；(3)；tag[hop]=0；／*标志栈顶结点的左子树已进行过后序遍历*／：}while(top>0&&(4)){/*栈顶结点的右子树是否被后序遍历过*／p=stack[top--];putchar(p->data)；}if(top>0){/*对栈顶结点的右子树进行后序遍历*／(5)；tag[top]=1；}}while(top>0)；}[15分]

A(1)，S)；elseif(S->data>(*tree)->data)SortTreelnsert(

B(2)，S)；}[函数5．2说明]函数voidTraversalTree(BTREE*tree)用非递归方法，对以tree为根结点指针的二叉树进行后序遍历。[函数5，2]voidTraversalTree(BTREE*tree){BTREE*stack[1000]，*p；inttag[1000]，top=0；p=tree；do{while(p!=NULL){stack[++top]=p；

C(3)；tag[hop]=0；／*标志栈顶结点的左子树已进行过后序遍历*／：}while(top>0&&

D(4)){/*栈顶结点的右子树是否被后序遍历过*／p=stack[top--];putchar(p->data)；}if(top>0){/*对栈顶结点的右子树进行后序遍历*／

E(5)；tag[top]=1；}}while(top>0)；}[15分]

2. 试题一阅读下列算法说明和算法，将应填入(n)处的字句写在答题纸的对应栏内。[算法说明]为便于描述屏幕上每个像素的位置，在屏幕上建立平面直角坐标系。屏幕左上角的像素设为原点，水平向右方向设为x轴，垂直向下方向设为y轴。设某种显示器的像素有128X128，即在每条水平线和每条垂直线上都有128个像素。这样，屏幕上的每个像素可用坐标(x，y)来描述其位置，其中x和y都是整数，0≤x≤127，0≤y≤127。现用一维数组MAP来存储整个一屏显示的位图信息。数组的每个元素有16位二进位，其中每位对应一个像素，“1”表示该像素“亮”，“0”表示该像素“暗”。数组MAP的各个元素与屏幕上的像素相对应后，其位置可排列如下：MAP(0)，MAP(1)，……，MAP(7)MAP(8)，MAP(9)，……，MAP(15)……MAP(1016)，MAP(1017)，……，MAP(1023)下述算法可根据用户要求，将指定坐标(x，y)上的像素置为“亮”或“暗”。在该算法中，变量X，Y，V，S，K都是16位无符号的二进制整数。数组BIT中的每个元素BIT(K)(K=0，…，15)的值是左起第K位为1，其余位均为0的16位无符号二进制整数，即BIT(K)的值为2l5-k。[算法]第1步根据用户指定像素的位置坐标(x，y)，算出该像素的位置所属的数组元素MAP(V)。这一步的具体实现过程如下：1、将x送变量X，将y送变量Y；2、将Y左移(1)位，仍存入变量Y；3、将X右移(2)位，并存入变量S；4、计算Y+S，存入变量V，得到像素的位置所属的数组元素MAP(V)。第2步算出指定像素在MAP(V)中所对应的位置K(K=0，…，15)。这一步的具体实现过程如下：将变量X与二进制数(3)进行逻辑乘运算，并存入变量K。第3步根据用户要求将数组元素MAP(V)左起第K位设置为”1”或”0”。这一步的具体实现过程如下：，1、为在指定像素置“亮”，应将MAP(V)与BIT(K)进行逻辑(4)运算，并存入MAP(V)。2、为在指定像素置“暗”，应先将BIT(K)各位取反，再将MAP(V)与BIT(K)进行逻辑(5)运算，并存入MAP(V)。[15分]

A(1)，……，MAP(7)MAP(8)，MAP(9)，……，MAP(15)……MAP(1016)，MAP(1017)，……，MAP(1023)下述算法可根据用户要求，将指定坐标(x，y)上的像素置为“亮”或“暗”。在该算法中，变量X，Y，V，S，K都是16位无符号的二进制整数。数组BIT中的每个元素BIT(K)(K=0，…，15)的值是左起第K位为1，其余位均为0的16位无符号二进制整数，即BIT(K)的值为2l5-k。[算法]第1步根据用户指定像素的位置坐标(x，y)，算出该像素的位置所属的数组元素MAP(V)。这一步的具体实现过程如下：1、将x送变量X，将y送变量Y；2、将Y左移(1)位，仍存入变量Y；3、将X右移

B(2)位，并存入变量S；4、计算Y+S，存入变量V，得到像素的位置所属的数组元素MAP(V)。第2步算出指定像素在MAP(V)中所对应的位置K(K=0，…，15)。这一步的具体实现过程如下：将变量X与二进制数

C(3)进行逻辑乘运算，并存入变量K。第3步根据用户要求将数组元素MAP(V)左起第K位设置为”1”或”0”。这一步的具体实现过程如下：，1、为在指定像素置“亮”，应将MAP(V)与BIT(K)进行逻辑

D(4)运算，并存入MAP(V)。2、为在指定像素置“暗”，应先将BIT(K)各位取反，再将MAP(V)与BIT(K)进行逻辑

E(5)运算，并存入MAP(V)。[15分]

3. 试题三阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。[函数3．1说明]函数insert_sort(inta[]，intcount)是用直接插入排序法对指定数组的前count个元素从小到大排序。直接插入排序法的基本思想是：将整个数组(count个元素)看成是由有序的(a[0]，…，a[i-1])和无序的(a[i]，…，a[Count-1))两个部分组成；初始时i等于1，每趟排序时将无序部分中的第一个元素a[i]插入到有序部分中的恰当位置，共需进行count-1趟，最终使整个数组有序。[函数3.1]voidinsert_sort(inta[],intcount){inti,j,t;for(i=1;i=0&&t<a[j]){/*在有序部分中寻找元素a[i]的插入位置*/(2);j--;}(3);}}[函数3．2说明]递归函数invert(inta[]，intk)将指定数组中的前k个元素逆置。[函数3．2]voidinvert(inta[],intk);{intt;if((4)){invert((5));t=a[0];a[0]=a[k-1];a[k-1]=t;}}[15分]

A(1);while(j>=0&&t<a[j]){/*在有序部分中寻找元素a[i]的插入位置*/

B(2);j--;}

C(3);}}[函数3．2说明]递归函数invert(inta[]，intk)将指定数组中的前k个元素逆置。[函数3．2]voidinvert(inta[],intk);{intt;if(

D(4)){invert(

E(5));t=a[0];a[0]=a[k-1];a[k-1]=t;}}[15分]

4. 试题二阅读下列函数说明和C代码，将应填入—匹l处的字句写在答题纸的对应栏内。[函数2．1说明]函数strcat(char*si，char*s2)是将字符串s2连接在字符串si之后，构成一个首指针为s1的字符串。[函数2.1]voidstrcat(char*sl，char*s2){while(*s1!='\0')；(1)：for(；(2)；s1++，s2++)；}[函数2．2说明]．本函数输入n(#defineMAXLINE1000intmaxindex(inta[]，int*index){inti，n；do{printf("Pleaseinputn＼n")；scanf("％d"，&n)；}while((3))；/*保证输入的n在限定范围内*/for(i=0;i<n;i++)scanf("%d"，&a[i])；*index=0；for(i=1;i<n;i++)if((4))*index=i；return(5)；}[15分]

A(1)：for(；

B(2)；s1++，s2++)；}[函数2．2说明]．本函数输入n(#defineMAXLINE1000intmaxindex(inta[]，int*index){inti，n；do{printf("Pleaseinputn＼n")；scanf("％d"，&n)；}while(

C(3))；/*保证输入的n在限定范围内*/for(i=0;i<n;i++)scanf("%d"，&a[i])；*index=0；for(i=1;i<n;i++)if(

D(4))*index=i；return

E(5)；}[15分]

5. 试题四阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。[程序4说明]本程序用古典的Eratosthenes的筛法求从2起到指定范围内的素数。如果要找出2至10中的素数，开始时筛中有2到10的数，然后取走筛中的最小的数2，宣布它是素数，并把该素数的倍数都取走。这样，第一步以后，筛子中还留下奇数3、5、7、9：重复上述步骤，再取走最小数3，宣布它为素数，并取走3的倍数，于是留下5、7。反复重复上述步骤，直至筛中为空时，工作结束，求得2至10中的全部素数。程序中用数组sieve表示筛子，数组元素sieve[i]的值为1时，表示数i在筛子中，值为-1时表示数i已被取走。[程序4]#include#defineMAX22500main(){unsignedinti,range,factor,k;intsieve[MAX];printf(“pleaseinputtherange:”);scanf(“%d”,&range);/*range指出在多大的范围内寻找素数*/for(i=2;i<=range;i++)/*筛子初始化*/(1);factor=2;while(factor<=range){if((2)){/*筛子最小数是素数*/printf(“%d\t”,factor);k=factor;while(k<=range){/*移走素数的倍数*/(3);/*筛中的个数减一*/k=(4);}}(5);}[15分]

A(1);factor=2;while(factor<=range){if(

B(2)){/*筛子最小数是素数*/printf(“%d\t”,factor);k=factor;while(k<=range){/*移走素数的倍数*/

C(3);/*筛中的个数减一*/k=

D(4);}}

E(5);}[15分]