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