2003年程序员下午试题

考试总分：5分

考试类型：模拟试题

作答时间：60分钟

已答人数：967

试卷答案：有

试卷介绍： 2003年程序员下午试题

开始答题

试卷预览

1. 试题一阅读下列算法说明和算法，将应填入__(n)__处的字句写在答卷的对应栏内。[算法说明]某英汉词典文件包含N个记录(N>1)，每个记录有两个字段：一个是英文单词，另一个是相应的汉语解释。各个记录按英文单词的词典顺序排列，各英文单词并不重复。本算法用于维护、更新该英汉词典文件。维护、更新的方法是：首先输入一个英文单词及其汉语解释，然后在该词典中查找输入的英文单词，若找到，则用输入的汉语解释更新原有的解释；若找不到，则需要将输入的英文单词及其汉语解释插入到该词典的适当位置，使各记录仍按英文单词的词典顺序排列。[算法]第一步读入英汉词典文件，并将读入的N个英文单词依次存放在字符串数组ENG中，将相应的汉语解释依次存放在字符串数组CN中。数组元素CN(i)给出了数组元素ENG(i)的解释。第二步输入英文单词及其汉语解释，将它们分别存放在字符串变量E和C中。若E为空串或都是空格，则转向第四步。第三步根据变量E的值，用二分法在数组ENG中查找。具体步骤如下：(1)1-->L，N-->H(2)INT((L+H)／2)-->K(3)若E=ENG(K)，则C-->CN(K)，转向第二步若E__(1)__；若E>ENG(K)，则K+1-->__(2)__(4)若HENG(I+1)CN(I)-->CN(I+1)然后，将E和C分别存入__(3)__和__(4)__，N+1-->N最后转向第二步否则，转向___(5)___第四步将数组ENG和CN输出，形成新的英汉词典文件，算法结束.[15分]

A(1)1-->L，N-->H

B(2)INT((L+H)／2)-->K

C(3)若E=ENG(K)，则C-->CN(K)，转向第二步若E__(1)__；若E>ENG(K)，则K+1-->__(2)__

D(4)若HENG(I+1)CN(I)-->CN(I+1)然后，将E和C分别存入__(3)__和__(4)__，N+1-->N最后转向第二步否则，转向___

E(5)___第四步将数组ENG和CN输出，形成新的英汉词典文件，算法结束.[15分]

2. 试题二阅读下列函数说明和C代码，将应填入__(n)___处的字句写在答题纸的对应栏内。[函数2.1说明]函数char*strrchr(char*s，charch)的功能是在字符串s中寻找字符ch若ch出现在字符串s中，则返回最后一次出现时的位置，否则返回NULL。[函数2.1]char*strrchr(char*s，charch){char*p；p=__(1)__;`/*p指向字符串s的结束标志*/while(--p>=s)if(__(2)__)returnp;returnNULL;}[函数2.2说明]函数BTREE*SortTreeSearch(BTREE*tree，intd)采用非递归方法，在二叉排序树(二叉查找树)中查找键值为d的结点。若找到，则返回键值所在结点的指针，否则返回NULL。二叉查找树的结点类型为：typedefstructnode{intdata；／*结点的键值*／structnode*left；structnode*right；}BTREE；[函数2.2]BTREE*SortTreeSearch(BTREE*tree，intd){BTREE*ptr=tree;while(ptr!=NULL&&d!=ptr->data){if(ddata)__(3)__;else__(4)__;}return__(5)___;}[15分]

A(1)__;`/*p指向字符串s的结束标志*/while(--p>=s)if(__

B(2)__)returnp;returnNULL;}[函数2.2说明]函数BTREE*SortTreeSearch(BTREE*tree，intd)采用非递归方法，在二叉排序树(二叉查找树)中查找键值为d的结点。若找到，则返回键值所在结点的指针，否则返回NULL。二叉查找树的结点类型为：typedefstructnode{intdata；／*结点的键值*／structnode*left；structnode*right；}BTREE；[函数2.2]BTREE*SortTreeSearch(BTREE*tree，intd){BTREE*ptr=tree;while(ptr!=NULL&&d!=ptr->data){if(ddata)__

C(3)__;else__

D(4)__;}return__

E(5)___;}[15分]

3. 试题三阅读下列函数说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。[函数3说明]函数ELEM*proc(FILE*fp)从文件fp中逐个读入职工的工号及其完成的产品数量，对相同工号的产品数量计入该职工完成的产品总数，并且按照产品总数降序排列，若多个职工完成的产品总数相同，则按工号升序排列。函数中建立了一个有序链表，来存储每个职工的工号和完成产品总数等数据，其结点类型为：typedefstructELE{intno；/*职工工号*／intnum；/*完成的产品总数*／structELE*next；}ELEM;[函数3]ELEM*proc(FILE*fp){intm，n；ELEM*u,*v,*p,*base;base=NULL;/*base是链表的首指针*／while(fscanf(fp，"%d%d",&n，&m)==2){／*链表中是否存在工号为n的结点*／for(v=base；v!=NULL&&v->no!=n;__(1)___);if(v!=NULL){／*若链表中已有工号为n的结点v，则将其从链表中脱钩*／if(__(2)__base=v->next;elseu->next=v->next;v->num+=m;/*累加工号为n的职工完成的产品数量*／}else{／*创建一个工号为n的结点*／v=(ELEM*)malloc(sizeof(ELEM));v->no=n；v->num=m；}/*寻找结点v的插入位置*／p=base;while(p!=NULL)if(v->num>p->num||v->num==p->num&&___(3)___)break;else{u=p;p=p->next;}/*将结点v插入链表*／if(p==base)__(4)__;elseu->next=v;__(5)__;}returnbase;}[15分]

A(1)___);if(v!=NULL){／*若链表中已有工号为n的结点v，则将其从链表中脱钩*／if(__

B(2)__base=v->next;elseu->next=v->next;v->num+=m;/*累加工号为n的职工完成的产品数量*／}else{／*创建一个工号为n的结点*／v=(ELEM*)malloc(sizeof(ELEM));v->no=n；v->num=m；}/*寻找结点v的插入位置*／p=base;while(p!=NULL)if(v->num>p->num||v->num==p->num&&___

C(3)___)break;else{u=p;p=p->next;}/*将结点v插入链表*／if(p==base)__

D(4)__;elseu->next=v;__

E(5)__;}returnbase;}[15分]

4. 试题四阅读下列函数说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。[函数4说明]函数voidrcr(inta[]，intn,intk)的功能是：将数组a中的元素a[0]～a[n-1]循环向右平移k个位置。为了达到总移动次数不超过n的要求，每个元素都必须只经过一次移动到达目标位置。在函数rcr中用如下算法实现：首先备份a[0]的值，然后计算应移动到a[0]的元素的下标p，并将a[p]的值移至a[0]；接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p];依次类推，直到将a[0]的备份值移到正确位置。若此时移动到位的元素个数已经为n，则结束；否则，再备份a[1]的值，然后计算应移动到a[1]的元素的下标p，并将a[p]的值移至a[1]；接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p];依次类推，直到将a[1]的备份值移到正确位置。若此时移动到位的元素个数已经为n，则结束；否则，从a[2]开始，重复上述过程，直至将所有的元素都移动到目标位置时为止。例如，数组a中的6个元素如下图(a)所示，循环向右平移2个位置后元素的排列情况如图(b)所示。412538476576657641253847a[0]a[1]a[2]a[3]a[4]a[5]a[0]a[1]a[2]a[3]a[4]a[5](a)(b)[函数4]voidrcr(inta[]，intn，intk){inti，j，t，temp，count;count=0；／*记录移动元素的次数*／k=k％n;if(__(1)__){/*若k是n的倍数，则元素无须移动；否则，每个元素都要移动*／i=0;while(count<n){j=i;t=i;temp=a[i];／*备份a[i]的值*／/*移动相关元素，直到计算出a[i]应移动到的目标位置*／while((j=__(2)__)!=i){a[t]=a[j];t=__(3)___;count++;}__(4)___=temp;count++;__(5)___;}}}[15分]

A(1)__){/*若k是n的倍数，则元素无须移动；否则，每个元素都要移动*／i=0;while(count<n){j=i;t=i;temp=a[i];／*备份a[i]的值*／/*移动相关元素，直到计算出a[i]应移动到的目标位置*／while((j=__

B(2)__)!=i){a[t]=a[j];t=__

C(3)___;count++;}__

D(4)___=temp;count++;__

E(5)___;}}}[15分]

5. 试题五阅读下列说明和C代码，将应填／k_(n)—处的字句写在答题纸的对应栏内。[说明]本题给出四个函数，它们的功能分别是：①intpush(PNODE*top，inte)是进栈函数，形参top是栈顶指针的指针，形参e是入栈元素。②intpop(PNODE*top，intoe)是出栈函数，形参top是栈顶指针的指针，形参e作为返回出栈元素使用。③intenQueue(PNODE*tail，inte)是入队函数，形参tail是队尾指针的指针，形参e是入队元素。④intdeQueue(PNODE*tail，int*e)是出队函数，形参tail是队尾指针的指针，形参e作为返回出队元素使用。以上四个函数中，返回值为0表示操作成功，返回值为-1表示操作失败。栈是用链表实现的；队是用带有辅助结点(头结点)的单向循环链表实现的。两种链表的结点类型均为：typedefstructnode{intvalue;structnode*next;}NODE，*PNODE;[函数①]intpush(PNODE*top，inte){PNODEp=(PNODE)malloc(sizeof(NODE));if(!p)return–1;p->value=e;___(1)___;*top=p;return0;}[函数②]intpop(PNODE*top，int*e){PNODEp=*top;if(p==NULL)return–1;*e=p->value;___(2)____;free(p);return0;}[函数③]intenQueue(PNODE*tail，inte){PNODEp，t；t=*tail;p=(PNODE)malloc(sizeof(NODE))；if(!p)return–l;p—>value=e;p—>next=t—>next;____(3)____;*tail=p;return0;}[函数④]intdeQueue(PNODE*tail，int*e){PNODEp，q；if((*tail)->next==*tail)return–1;p=(*tail)->next;q=p->next;*e=q->value;___(4)___=q->next;if(*tail=q)___(5)___;free(q);return0;}[15分]

A(1)___;*top=p;return0;}[函数②]intpop(PNODE*top，int*e){PNODEp=*top;if(p==NULL)return–1;*e=p->value;___

B(2)____;free(p);return0;}[函数③]intenQueue(PNODE*tail，inte){PNODEp，t；t=*tail;p=(PNODE)malloc(sizeof(NODE))；if(!p)return–l;p—>value=e;p—>next=t—>next;____

C(3)____;*tail=p;return0;}[函数④]intdeQueue(PNODE*tail，int*e){PNODEp，q；if((*tail)->next==*tail)return–1;p=(*tail)->next;q=p->next;*e=q->value;___

D(4)___=q->next;if(*tail=q)___

E(5)___;free(q);return0;}[15分]