试题一
阅读下列算法说明和算法，将应填入__(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 |
|
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) (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;
)
