1、三级 PC 技术机试-142 及答案解析(总分：100.00，做题时间：90 分钟)一、上机题(总题数：1，分数：100.00)1.请编制程序 PROG1.ASM，其功能是：内存中连续存放着由 20 个无符号字节组成的一个序列，请将它们排成升序(从小到大)。程序中，COUNT 为序列元素个数，OFFL 为序列偏移量，BX 为交换标志寄存器(BX =1，说明此趟排序扫描后未发生交换操作，表示序列中的元素已排好序)。例如：内存中有 01H,04H，02H，(假设后十七个字节均大于 04H)结果为 01H，02H，04H，(后跟十七个字节，按从小到大的顺序排列)部分程序已给出，其中原始数据由过程 L
2、OAD 从文件 INPUT1.DAT 中读入 SOURCE 开始的内存单元中。运算结果要求从 RESULT 开始存放，由过程 SAVE 保存到文件 OUTPUT1.DAT 中。请编写 BEGIM 到 END 之间代码。对程序必须进行汇编，并与 IO.OBJ 连接产生 PROG1.EXE 执行文件，最终运行程序产生结果(无结果或结果不正确者均不得分)；部分源程序如下：EXTRN LOAD:FAR,SAVE:FARN EQU 20STAC SEGMENT STACKDB 128 DUP (?)STAC ENDS DATA SEGMENT SOURCE DB N DUP (?)RESULT DB N
3、 DUP (0)NAME0 DB INPUT1. DAT, 0NAME1 DB OUTPUT1. DAT, 0COUNT DW ?OFFL DW ?DATA ENDS CODE SEGMENTASSUME CS:CODE, DS:DATA, SS:STACSTART PROC FARPUSH DSXOR AX,AXPUSH AXMOV AX,DATAMOV DS, AXLEA DX, SOURCE ; 数据区起始地址LEA SI,NAMEO ; 原始数据文件名MOV CX,N ; 字节数CALL LOAD ; 从INPUT1.DAT中读取数据* BEGIN * * END * LEA DX,R
4、ESULT ; 结果数据区首地址 LEA SI,NAME1 ; 结果文件名MOV CX,N ; 结果字节数CALL SAVE ; 保存结果到文件RETSTART ENDPCODE ENDSEND START相关知识：无符号数比较大小。有符号数和无符号数比较大小采用的是不同的指令，本题目要求将无符号数进行排序，这里仅介绍无符号数的比较指令。(1)“高于”或“不低于等于”条件转移指令指令格式：JA/JNBE 短标号地址(2)“高于等于”或“不低于”条件转移指令指令格式：JAE/JNB 短标号地址(3)“等于”条件转移指令指令格式：JE 短标号地址(4)“不等于”条件转移指令指令格式：JNE 短标号
5、地址(5)“低于等于”或“不高于”条件转移指令指令格式：JBE/JNA 短标号地址(6)“低于”或“不高于等于”条件转移指令指令格式：JB/JNAE 短标号地址数组的排序数组的排序的方法有很多种，可以采用“冒泡排序”、“直接插入排序”、“简单选择排序”等算法复杂度为 O(n2)的简单排序算法，也可采用那些算法复杂度为 O(nlog2n)或 O(d (n+rd)的算法，但简单排序算法比较容易理解，编程比较方便。通过阅读我们发现出题者的意愿就是采用冒泡排序方法，因为它要多次扫描数组，而且有一个标志指明一趟扫描是否发生数据交换，这是典型冒泡排序方法。当然大家也可采用别的排序算法，作为题目的分析者我们
6、就不采用别的方法了。串的移动冒泡排序是在原地进行的排序方法，所以需要事先将数据移到结果地址中，或将排序后的结果移到结果地址中。(1)串的移动我们可以考虑使用字符串传送指令和无条件重复前缀。(i)字符串传送指令指令格式：MOVSB 或 MOVSW需要设置源地址寄存器 SI 和目的地址寄存器 DI 中的地址内容，还需要设置传送字符的个数到寄存器 CX中，以及方向标志位 D 以决定地址变换方向，D=0 时，SI 和 DI 内容加 1，D=1 时，SI 和 DI 内容减 1。(ii)无条件重复前缀指令格式：REP 字符串操作指令此条指令根据 CX 中的内容决定重复操作的次数。(2)如果对于串的传送指令
7、不熟悉的话，也可用循环的方式，用 MOV 命令，从源地址将数据传送到目的地址。编程思路：第一步：分析本程序要求完成的功能。本程序要求完成以下功能：(1)从数据文件 INPUT1.DAT 中读取 20 个 8 位无符号整数存放在 SOURCE 开始的内存单元中。(2)将 SOURCE 开始的 20 个内存单元中的无符号整数进行排序后依次放在 RESULT 开始的内存单元中。(3)将排序结果存入到 OUTPUT1.DAT。第二步：用相应汇编程序来实现其功能。数据的读取和存入题目中已经给出，只要完成 20 个有符号整数的排序操作即可。对于一个数组的排序操作可按下面的方法进行。(i)依次将相邻的两个数
8、比较，每次将较小的数调换到前面。那么经过一趟比较后，最大的数排在第 n 个位置；再将剩下的 n-1 个数两两进行比较，排在第 n-1 个位置上的为次大数；重复比较共 n-1 趟，完成排序操作。(ii)第 i 趟比较，进行 n-i 次两两比较，得到第 i 大的数。(iii)可能对数组扫描若干次后，数组已经成为有序状态，再对数组进行扫描，就不会出现数据交换的现象。为节约程序运行时间，用一个标志来指明当前的扫描是否发生数据交换，若无数据交换，则结束排序过程。（分数：100.00）_三级 PC 技术机试-142 答案解析(总分：100.00，做题时间：90 分钟)一、上机题(总题数：1，分数：100.
9、00)1.请编制程序 PROG1.ASM，其功能是：内存中连续存放着由 20 个无符号字节组成的一个序列，请将它们排成升序(从小到大)。程序中，COUNT 为序列元素个数，OFFL 为序列偏移量，BX 为交换标志寄存器(BX =1，说明此趟排序扫描后未发生交换操作，表示序列中的元素已排好序)。例如：内存中有 01H,04H，02H，(假设后十七个字节均大于 04H)结果为 01H，02H，04H，(后跟十七个字节，按从小到大的顺序排列)部分程序已给出，其中原始数据由过程 LOAD 从文件 INPUT1.DAT 中读入 SOURCE 开始的内存单元中。运算结果要求从 RESULT 开始存放，由过
10、程 SAVE 保存到文件 OUTPUT1.DAT 中。请编写 BEGIM 到 END 之间代码。对程序必须进行汇编，并与 IO.OBJ 连接产生 PROG1.EXE 执行文件，最终运行程序产生结果(无结果或结果不正确者均不得分)；部分源程序如下：EXTRN LOAD:FAR,SAVE:FARN EQU 20STAC SEGMENT STACKDB 128 DUP (?)STAC ENDS DATA SEGMENT SOURCE DB N DUP (?)RESULT DB N DUP (0)NAME0 DB INPUT1. DAT, 0NAME1 DB OUTPUT1. DAT, 0COUNT
11、DW ?OFFL DW ?DATA ENDS CODE SEGMENTASSUME CS:CODE, DS:DATA, SS:STACSTART PROC FARPUSH DSXOR AX,AXPUSH AXMOV AX,DATAMOV DS, AXLEA DX, SOURCE ; 数据区起始地址LEA SI,NAMEO ; 原始数据文件名MOV CX,N ; 字节数CALL LOAD ; 从INPUT1.DAT中读取数据* BEGIN * * END * LEA DX,RESULT ; 结果数据区首地址 LEA SI,NAME1 ; 结果文件名MOV CX,N ; 结果字节数CALL SAV
12、E ; 保存结果到文件RETSTART ENDPCODE ENDSEND START相关知识：无符号数比较大小。有符号数和无符号数比较大小采用的是不同的指令，本题目要求将无符号数进行排序，这里仅介绍无符号数的比较指令。(1)“高于”或“不低于等于”条件转移指令指令格式：JA/JNBE 短标号地址(2)“高于等于”或“不低于”条件转移指令指令格式：JAE/JNB 短标号地址(3)“等于”条件转移指令指令格式：JE 短标号地址(4)“不等于”条件转移指令指令格式：JNE 短标号地址(5)“低于等于”或“不高于”条件转移指令指令格式：JBE/JNA 短标号地址(6)“低于”或“不高于等于”条件转移指
13、令指令格式：JB/JNAE 短标号地址数组的排序数组的排序的方法有很多种，可以采用“冒泡排序”、“直接插入排序”、“简单选择排序”等算法复杂度为 O(n2)的简单排序算法，也可采用那些算法复杂度为 O(nlog2n)或 O(d (n+rd)的算法，但简单排序算法比较容易理解，编程比较方便。通过阅读我们发现出题者的意愿就是采用冒泡排序方法，因为它要多次扫描数组，而且有一个标志指明一趟扫描是否发生数据交换，这是典型冒泡排序方法。当然大家也可采用别的排序算法，作为题目的分析者我们就不采用别的方法了。串的移动冒泡排序是在原地进行的排序方法，所以需要事先将数据移到结果地址中，或将排序后的结果移到结果地址
14、中。(1)串的移动我们可以考虑使用字符串传送指令和无条件重复前缀。(i)字符串传送指令指令格式：MOVSB 或 MOVSW需要设置源地址寄存器 SI 和目的地址寄存器 DI 中的地址内容，还需要设置传送字符的个数到寄存器 CX中，以及方向标志位 D 以决定地址变换方向，D=0 时，SI 和 DI 内容加 1，D=1 时，SI 和 DI 内容减 1。(ii)无条件重复前缀指令格式：REP 字符串操作指令此条指令根据 CX 中的内容决定重复操作的次数。(2)如果对于串的传送指令不熟悉的话，也可用循环的方式，用 MOV 命令，从源地址将数据传送到目的地址。编程思路：第一步：分析本程序要求完成的功能。
15、本程序要求完成以下功能：(1)从数据文件 INPUT1.DAT 中读取 20 个 8 位无符号整数存放在 SOURCE 开始的内存单元中。(2)将 SOURCE 开始的 20 个内存单元中的无符号整数进行排序后依次放在 RESULT 开始的内存单元中。(3)将排序结果存入到 OUTPUT1.DAT。第二步：用相应汇编程序来实现其功能。数据的读取和存入题目中已经给出，只要完成 20 个有符号整数的排序操作即可。对于一个数组的排序操作可按下面的方法进行。(i)依次将相邻的两个数比较，每次将较小的数调换到前面。那么经过一趟比较后，最大的数排在第 n 个位置；再将剩下的 n-1 个数两两进行比较，排在
16、第 n-1 个位置上的为次大数；重复比较共 n-1 趟，完成排序操作。(ii)第 i 趟比较，进行 n-i 次两两比较，得到第 i 大的数。(iii)可能对数组扫描若干次后，数组已经成为有序状态，再对数组进行扫描，就不会出现数据交换的现象。为节约程序运行时间，用一个标志来指明当前的扫描是否发生数据交换，若无数据交换，则结束排序过程。（分数：100.00）_正确答案：(LEA SI，SOURCELEA DI，RESULTMOV CX，NNEXTO: MOV AL，SIMOV DI，ALINC SIINC DILOOP NEXTO ; 将待排序数组移到目的单元CLD LEA SI, RESULTMOV CX, NMOV OFFL, SIMOV COUNT, CXINIT: MOV BX, 1 ; 一趟比较之前，标志寄存器置DEC COUNTJZ SORTED ; 如果进行 n 次扫描，结束排序MOV CX, COUNTMOV SI, OFFLNEXT: LODSB CMP SI ,AL ; 两两比较JAE CONTXCHG SI, ALMOV SI-1 ,ALSUB BX, BX ; 发生数据交换，交换标志清零CONT: LOOP NEXTCMP BX,OJE INIT ; 如果有数据交换发生，再进行一趟扫描SORTED: NOP)解析：
