2003年程序员下午试题及答案(1)

试题一

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