2003上半年程序员考试真题及答案-下午卷.doc-资料库

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

2003 上半年程序员考试真题及答案-下午卷试题一阅读下列算法说明和算法，将应填入__(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 < ENG(K)，则 K-1 -->__(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.1] char *strrchr(char *s，char ch) { char*p； p = __(1)__; while( --p >= s) `/*p 指向字符串 s 的结束标志*/ if(__(2)__) return p; return NULL; }

[函数 2.2 说明] 函数 BTREE *SortTreeSearch(BTREE *tree，int d)采用非递归方法，在二叉排序树(二叉查找树)中查找键值为 d 的结点。若找到，则返回键值所在结点的指针，否则返回 NULL。二叉查找树的结点类型为： typedef struct node{ int data；／*结点的键值*／ struct node *left； struct node *right； }BTREE； [函数 2.2] BTREE *SortTreeSearch(BTREE *tree，int d) { BTREE *ptr = tree; while(ptr != NULL && d != ptr->data){ if(d < ptr->data) __(3)__; else __(4)__; } return__(5)___; } 试题三阅读下列函数说明和 C 代码，将应填入__(n)__处的字句写在答题纸的对应栏内。 [函数 3 说明] 函数 ELEM *proc(FILE *fp)从文件 fp 中逐个读入职工的工号及其完成的产品数量，对相同工号的产品数量计入该职工完成的产品总数，并且按照产品总数降序排列，若多个职工完成的产品总数相同，则按工号升序排列。函数中建立了一个有序链表，来存储每个职工的工号和完成产品总数等数据，其结点类型为： typedef struct ELE{ int no； /*职工工号*／ int num； /*完成的产品总数*／ struct ELE *next； }ELEM; [函数 3] ELEM *proc(FILE *fp) { int m，n； *u,*v,*p,*base; ELEM 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 __(5)__; u->next = v; } return base; } 试题四阅读下列函数说明和 C 代码，将应填入__(n)__处的字句写在答题纸的对应栏内。 [函数 4 说明] 函数 void rcr(int a[]，int n,int k)的功能是：将数组 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)所示。 41 25 38 47 65 76 65 76 41 25 38 47 a[0] a[1] a[2] a[3] a[4] a[5] a[0] a[1] a[2] a[3] a[4] a[5] (a) [函数 4] void rcr(int a[]，int n，int k) { int i，j，t，temp，count; count = 0；／*记录移动元素的次数*／ k = k ％ n; (b)

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)___; } } } 试题五阅读下列说明和 C 代码，将应填／k_(n)—处的字句写在答题纸的对应栏内。 [说明] 本题给出四个函数，它们的功能分别是： ①int push(PNODE *top，int e)是进栈函数，形参 top 是栈顶指针的指针，形参 e 是入栈元素。 ②int pop(PNODE *top，int oe)是出栈函数，形参 top 是栈顶指针的指针，形参 e 作为返回出栈元素使用。 ③int enQueue(PNODE *tail，int e)是入队函数，形参 tail 是队尾指针的指针，形参 e 是入队元素。 ④int deQueue(PNODE *tail，int *e)是出队函数，形参 tail 是队尾指针的指针，形参 e 作为返回出队元素使用。以上四个函数中，返回值为 0 表示操作成功，返回值为-1 表示操作失败。栈是用链表实现的；队是用带有辅助结点(头结点)的单向循环链表实现的。两种链表的结点类型均为： typedef struct node{ int value; struct node *next; }NODE，*PNODE; [函数①] int push(PNODE *top，int e) { return –1; PNODE p = (PNODE)malloc(sizeof(NODE)); if(!p) p->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; p—>value = e; p—>next = t—>next; ____(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; ) 参考答案

ptr ->left ptr->right 试题一 (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 (4) ptr (5) ptr 试题三 (1) u = v，v = v->next 或 u = v，v = u->next (2) v == base 或 base->no == n (3) v->no < p->no 或 v->no <= p->no (4) base = v (5) v->next = p 试题四 (1) k != (2) (j-k+n) (3) j (4) a[t] 或 *(a+t) (5) i++ 试题五 (1) p->next = *top (2) *top = p->next 或 *top = (*top)->next (3) t->next = p 或 (*tail)->next = p (4) p->next 或 (*tail)->next->next (5) *tail = p 或 *tail = (*tail)->next 0 或 k = = % n

资料库

2003上半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料