阅读以下说明和x86汇编语言代码,根据要求回答问题1至问题3。表6-3所示为 x86系统指令及寄存器说明表。 [说明] 在计算机控制中,有些数据补偿、计算及转换等参数的计算非常复杂,编程难,程序长且运算费时,但是用数表却比较容易实现。 设有

admin2009-02-15  43

问题 阅读以下说明和x86汇编语言代码,根据要求回答问题1至问题3。表6-3所示为 x86系统指令及寄存器说明表。
  [说明]
   在计算机控制中,有些数据补偿、计算及转换等参数的计算非常复杂,编程难,程序长且运算费时,但是用数表却比较容易实现。
   设有256个字节的数据,已按从小到大的顺序存放在以BINTAB为首地址的数据区单元中,现要求查找其中值为126的数据,用对分查表法查询的汇编程序如下:
   [汇编程序代码]
DATA     SEGMENT
BINTAB   DBl8,25,32,46,56,78,…             ;第1~100个数据
        DB 90,95,99,100,106,126,…         ;第101~200个数据
        DB 189,195,197,202,206,216,…      ;第201~256个数据
COUNT     EQU    256
FLAG       DW        ?
KEY      EQU    (1)  
DATA     ENDS

STAK     SEGMENT
STPN     DB 20  DUP(?)
STAK     ENDS

CODE     SEGMENT
         ASSUME CS,CODE, DS,DATA, ES:DATA, SS:STAK
BINSEAT PROC FAR
START,   MOV     AX, DATA
        MOV     DS, AX
        MOV     ES, AX
        LEA     SI, BINTAB
        MOV     CX, COUNT
        MOV     DX, 1
        MOV     AX, SI
        ADD     AX, CX
        MOV     DI, AX
        MOV     AL, KEY
LOP0,    MOV    BX, SI
        ADD    BX, DI
        SHR    BX, 1
        CMP    AL, [BX]
        JZ     FOUND
        PUSHF
       (2)  
        JZ     NFOUND
        POPF
        JL     LESS
        MOV    SI, BX
        JMP    NEXT
LESS,    (3)  
NEXT,    (4)  
         JMP    LOP0
NFOUND: MOV    AX, DX          ;未找到,标志全1送DX
FOUND:  MOV    AX, DX
       MOV    FLAG, AX
       RET
BINSEAT ENDP
CODE ENDS
             (5)  

选项

答案(1)126,或其对应的二进制数形式 (2)CMP BX,SI (3)MOV DI,BX (4)INC DX (5)END START 这是一道要求读者掌握对分查表法算法的程序分析题。本题的解答思路如下: ①对分查表法用于有序表的查找。对一个字节长度为N的有序表(从小到大排列),先取N/2处的值与待找的数据X进行比较,若X大于N/2处的值,则下一次取N/2至N的中间值即3N/4处的值进行比较,反之下一次取0至N/2的中间值即N/4处的值进行比较。如此不断对分查找,直到找出所需要的数据X。 ②结合以上算法思想,仔细分析试题的程序段。以下给出该程序段的每条语句的详细解析。 DATA SEGMENT ;DATA段定义伪指令 BINTAB DB 18,25,32,46,56,78,… ;第1~100个数据 DB 90,95,99,100,106,126,… ;第101~200个数据 DB 189,195,197,202,206,216,… ;第201~256个数据 COUNT EQU 256 ; 数据块长度 FLAG DW? ;查到所找数据需要查找次数的存储单元 KEY EQU 100 ; 所查找的数据 DATA ENDS ;DATA段定义结束伪指令 STAK SEGMENT ;STAK段定义伪指令 STPN DB 20 DUP(?) STAK ENDS ;STAK段定义结束伪指令 CODE SKGMENT ;CODE段定义伪指令 ASSUME CS:CODE,DS:DATA,ES;DATA,SS:STAK ;段寄存器说明伪指令 BINSEAT PROC FAR ;过程(子程序)定义伪指令 START:MOV AX,DATA MOV DS,AX MOV ES,AX LEA SI,BINTAB ;SI←数据表上指针 MOV CX,COUNT ;CS←数据块长度 MOV DX,1 ;立即数1送DX,表示第1次查询 MOV AX,SI ;数据表首地址送AX ADD AX,CX ;AX←数据表首地址十数据块长度 MOV DI,AX ;DI←数据表下指针(AX) MOV AL,KEY ;AL←要查询的数据 LOP0: MOV BX,SI ;数据表首地址送BX ADD BX,DI ;BX←数据表首地址+数据表尾地址 SHR BX,1 ;BX←中项指针=(SI+D1)/2,操作数逻辑右移 ;移一位相当对其除2 CMP AL,[BX] ;要查询的数据与中项数据比较 J2 FOUND ;结果相同,找到则转至FOUND PUSHF ;保存状态标志 CMP BX,SI ;比较中项指针=上指针? JZ NFOUND ;相等表示未找到,转至NFOUND POPF ;恢复状态标志 JL LESS ;要查询的数据小于中项数据时,转至 LESS MOV SI,BX ;要查询的数据大于中项数据时,修改上指针 JMP NEXT ;表示在后一半继续查找 LESS: MOV DI,BX ;要查询的数据小于中项数据时,修改下指针 ;表示在前一半继续查找 NEXT; INC DX ;查找次数加1 JMP LOP0 ;重新计算中项指针继续查找 NFOUND:MOV AX,DX ;未找到,标志全1送DX FOUND; MOV AK,DX ;查找次数送AX MOV FLAG,AX ;查找次数送FLAG单元 RET :返回主程序 BINSEATENDP ;过程(子程序)定义结束伪指令 CODE ENDS ;CODE段定义结束伪指令 END START ; 模块结束伪指令 ③由以上分析可知,根据“MOV AL,KE Y”、“CMP AL,[BX]”两条语句可推理出, (1)空缺处应填入题干中要求查询的数据126。 ④“CMP AL,[BX]”语句用于所查询的数据与中项数据比较,“JZ FOUND”语句表示如果比较结果相同,则转至找到后的处理标号FOUND处,由此可判断(2)空缺处填写的内容与所查询的数据不等于中项数据处理过程相关。 ⑤(2)空缺处的后一条语句“JZ NFOUND”语句表示如果比较结果相等,则转至未找到处理标号NFOUND处,由此可判断,该空缺处填写的内容用于判断查找过程是否可以结束,可通过比较中项指针是否等于数据表上指针的语句“CMP BX,SI”来完成此功能。 ⑥由(3)空缺处所在语句的标号“LESS”可知,(3)空缺处填写的内容与“JL LESS”语句(判断所查询的数据是否小于中项数据)相关。由对分查表法算法可知,当所查询的数据小于中项数据时,需修改数据表下指针,以使查找过程在前一半继续进行。因此该空缺处需填入与数据表下指针DI相关的语句“MOV DI,BX”。 ⑦同理,由(4)空缺处所在语句的标号“NEXT”可知,(4)空缺处填写的内容也与“JL LESS”语句(判断所查询的数据是否小于中项数据)相关。由对分查表法算法可知,当所查询的数据大于中项数据时,通过“MOV SI,BX”语句修改数据表上指针,以使查找过程在后一半继续进行。可见该空缺处是修改数据表下指针或上指针后继续查找的公共执行语句。再由“MOV DX,1”语句及“MOV AX,DX”、“MOV FLAG,AX”语句可推理出,(4)空缺处填写的内容是查找次数加1的“INC DX”语句。 ⑧由于(5)空缺处所填写的语句是程序模块的最后一条语句,因此由程序中启动标号“START”可推理出,该空缺处是一条与之相对应的模块结束伪指令“END START”,用于告诉汇编程序源文件结束,并给出执行程序的入口位置。 ⑨另外,为了使读者更深入掌握对分查表法的应用,下面给出用对分查表法进行子程序设计的步骤: a.表的长度放在CX寄存器中。 b.将BINTAB表的首地址放人SI寄存器中。 c.将要搜索的关键字放在AL中。 d.计算中点元素的地址(中项指针),并放入BX寄存器中。 e.将关键字AL与中点元素的值进行比较, 若(AL)<[BX),则选低值的半个表(即SI为首地址,[BX]为尾地址),并转步骤d; 若(AL)>[BX],则选高值的半个表(即[BX]为首地址,DI为尾地址),并转步骤d; 若(AL)=[BX],则找到并将查找次数送人FLAG存储单元。

解析
转载请注明原文地址:https://kaotiyun.com/show/KmWZ777K
0

相关试题推荐
最新回复(0)