文档介绍：试题5(1996年试题4)
在COMET型计算机上可以使用试卷上所附的CASL汇编语言,阅读下列程序说明和CASL程序,将应填入(n)处的字句,写在答卷的对应栏内。
[程序说明]
子程序OFFSET用二分法,查找无符号整数M在一个长度为N的有序(升序)无符号整数列表NTABLE中的位置。
程序中标号为LOW和UP的两个存储字分别用作存放查找区间的上下限。
进入子程序时,在GR1中给出存放子程序所需参数的起始地址。参数的次序如下:
(GR1)+0
 
M
N
NTABLER的首址
1
 
2
 
从子程序返回时,GR0中存放查找结果,即M在此有序表中的位置序数。如果表中找不到M,则GR0返回0,其他寄存器的内容保持不变。
[程序]
 
START
OFFSET
PUSH 0, GR2
PUSH 0, GR3
LD GR0, 0, GR1
LEA GR2, 0
ST GR2, LOW
(1)
(2)
ST GR2, P
ADD GR2, LOW
SRL GR2, 1
LEA GR3, 0, GR2
(3)
(4)
JZE FOUND
JPZ INCLOW
LEA GR2, -1, GR2
ST
GR2, UP
JMP CMPLU
LEA GR2, 1, GR2
ST GR2, LOW
(5)
CPL GR2, LOW
(6)
(7)
LEA GR0, 1, GR2
POP GR3
POP GR2
RET
DS 1
DS 1
END
 
 
 
 
 
 
 
LOOP
 
 
 
 
 
 
 
 
 
INCLOW
 
 
CMPLU
 
 
FOUND
 
 
 
LOW
UP
 
[解析]
试题说明没有提供更多的信息,在这里我们只能了解程序中一些变量的含义。所以问题只能通过两点来解答,一是对程序结构的理解,一是对二分法的掌握程序。二分法的查找过程为:先将待查记录所在的范围(区间)分成两个区间,然后确定待查的记录所在的区间。如此循环往复,直到查找成功或失败。这样,无论如何实现二分法,有些工作是必须的,例如确定查找的上限和下限,确认待查询记录所在的区间。
考察试题所提供的程序,可以推断出程序的对二分法的具体实现过程:首选设指针LOW和UP分别指向NTABLE的第一个元素和最后一个元素,比较M与表的第[(LOW+UP)/2]个元素([ ])表示取整),即与区间的蹭元素相比较。若相等,则找到;若M大,则说明要找的元素在区间的上半部,所以下一次比较将LOW值置为[(LOW+UP)/2]+1,UP值不变;若M小,则说明要找的元素在区间的下半部,所以下一次比较将LUP值置[(LOW+UP)/2]-1,LOW值不变。循环的结束条件是LOW>UP,此时查找失败。
结合算法来阅读程序。程序在完成了一些例行工作之后,语句"LD GR0,0,GR1"将要查找的值M放入GR0中,接下来是设置查找的下限LOW,显然下面该初始化指针UP了。由以上LOW的初值为0,可以推断UP的正确初值应该是N-1。从填空(2)的下一行"ST GR2,UP"来看,UP的初值是经GR2传入的,而且填空(1)、(2)完成对UP的