程序员考试试题及答案_2003年程序员下午试题及答案

【shitiku.jxxyjl.com--计算机技术】

试题一

阅读下列算法说明和算法，将应填入__(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<L则

对I = N，L，-1(始值，终值，增量)循环执行：

ENG(I) --> 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)__;     `/*p指向字符串s的结束标志*/

while( --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；

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中的元素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

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

                                  (a) 

65

76

41

25

38

47

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

                                                  (b)
[函数4]

void 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 < 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)

{

PNODE p = (PNODE)malloc(sizeof(NODE));

if(!p)  return –1;

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;

)

参考答案

试题一

(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 < p->no 或 v->no <= p->no

(4)      base = v

(5)      v->next = p

试题四

(1)      k !=  0 或 k

(2)      (j-k+n)  %  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

 

 

本文来源：https://shitiku.jxxyjl.com/jisuanjijishu/966.html