试题一

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

对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)___;

}

答案解析