温故而知新，下笔如有神近三上半年程序员考试专项习题训练及答案-下午卷试题一阅读下列算法说明和算法，将应填入_(n)_处的字句写在答卷的对应栏内。算法说明某英汉词典文件包含N个记录(N1)，每个记录有两个字段：一个是英文单词，另一个是相应的汉语解释。各个记录按英文单词的词典顺序排列，各英文单词并不重复。本算法用于维护、更新该英汉词典文件。维护、更新的方法是：首先输入一个英文单词及其汉语解释，然后在该词典中查找输入的英文单词，若找到，则用输入的汉语解释更新原有的解释；若找不到，则需要将输入的英文单词及其汉语解释插入到该词典的适当位置，使各记录仍按英文单词的词典顺序排列。算法第一步 读入英汉词典文件，并将读入的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)若H ENG(I+1)CN(I) -CN(I+1)然后，将E和C分别存入_(3)_和_(4)_，N+1 - N 最后转向第二步否则，转向_(5)_第四步 将数组ENG和CN输出，形成新的英汉词典文件，算法结束.试题二阅读下列函数说明和C代码，将应填入_(n)_处的字句写在答题纸的对应栏内。函数2.1说明函数char *strrchr(char*s，char ch)的功能是在字符串s中寻找字符ch若ch出现在字符串s中，则返回最后一次出现时的位置，否则返回NULL。函数2.1char *strrchr(char *s，char ch)char*p；p = _(1)_;/*p指向字符串s的结束标志*/while( -p = s)if(_(2)_) return p;return NULL;函数2.2说明函数BTREE *SortTreeSearch(BTREE *tree，int d)采用非递归方法，在二叉排序 树(二叉查找树)中查找键值为d的结点。若找到，则返回键值所在结点的指针，否则 返回NULL。二叉查找树的结点类型为：typedef struct nodeint data；*结点的键值*struct node *left；struct node *right；BTREE；函数2.2BTREE *SortTreeSearch(BTREE *tree，int d) BTREE *ptr = tree;while(ptr != NULL & d != ptr-data)if(d data)_(3)_;else_(4)_;return_(5)_;试题三阅读下列函数说明和C代码，将应填入_(n)_处的字句写在答题纸的对应栏内。函数3说明函数ELEM *proc(FILE *fp)从文件fp中逐个读入职工的工号及其完成的产品数量，对相同工号的产品数量计入该职工完成的产品总数，并且按照产品总数降序排列，若多个职工完成的产品总数相同，则按工号升序排列。函数中建立了一个有序链表，来存储每个职工的工号和完成产品总数等数据，其结点类型为：typedef struct ELEint no；/*职工工号*int num；/*完成的产品总数*struct ELE *next；ELEM;函数3ELEM *proc(FILE *fp) int m，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;else u-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)_;else u-next = v;_(5)_;return base;试题四阅读下列函数说明和C代码，将应填入_(n)_处的字句写在答题纸的对应栏内。函数4说明函数void rcr(int a，int n,int k)的功能是：将数组a中的元素a0an-1循环向右平移k个位置。为了达到总移动次数不超过n的要求，每个元素都必须只经过一次移动到达目标位置。在函数rcr中用如下算法实现：首先备份a0的值，然后计算应移动到a0的元素的下标p，并将ap的值移至a0；接着计算应移动到ap的元素的下标q，并将aq的值移至ap;依次类推，直到将a0的备份值移到正确位置。若此时移动到位的元素个数已经为n，则结束；否则，再备份a1的值，然后计算应移动到a1的元素的下标p，并将ap的值移至a1；接着计算应移动到ap的元素的下标q，并将aq的值移至ap;依次类推，直到将a1的备份值移到正确位置。若此时移动到位的元素个数已经为n，则结束；否则，从a2开始，重复上述过程，直至将所有的元素都移动到目标位置时为止。例如，数组a中的6个元素如下图(a)所示，循环向右平移2个位置后元素的排列情况如图(b)所示。412538476576657641253847a0a1a2a3a4a5a0a1a2a3a4a5(a)(b)函数4void rcr(int a，int n，int k) int i，j，t，temp，count;count = 0；*记录移动元素的次数*k = k n;if(_(1)_) /*若k是n的倍数，则元素无须移动；否则，每个元素都要移动*i = 0;while(count value = e;_(1)_;*top = p;return 0;函数int pop(PNODE *top，int *e)PNODE p = *top;if(p = NULL) return 1;*e = p-value;_(2)_;free(p);return 0;函数int enQueue(PNODE *tail，int e) PNODE p，t；t = *tail;p = (PNODE)malloc(sizeof(NODE)；if(!p) return l;pvalue = e;pnext = tnext;_(3)_;*tail = p;return 0;函数int deQueue(PNODE *tail，int *e) PNODE p，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);return 0;)参考答案试题一(1) H(2) L(3) ENG(L) 或 ENG(I+1)(4) CN(L) 或 CN（I+1）(5) 试题二(1) strlen(s) + s(2) *p = ch(3) ptr = ptr -left(4) ptr = ptr-right(5) ptr试题三(1) u = v，v = v-next 或 u = v，v = u-next(2) v = base 或 base-no = n(3) v-no no 或 v-no no(4) base = v(5) v-next = p试题四(1) k != 0 或 k(2) (j-k+n) % n