1、综合模拟试卷 13 及答案与解析一、计算题1 请写一非递归算法，该算法在按值严格递增排列的顺序表 A1,n中采用折半查找法查找值不小于 item 的最小元素。若表中存在这样的，己素，则算法给出该最小元素在表中的位置，否则，给出信息 0。2 已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组BT0n1 中(假设每个结点的数据信息为一个非 0 整数；若数组元素值为 0，则表示该元素对应的结点在二叉树中不存在)。请写一算法，生成该二又树的二义链表结构。二、综合题2 设 a、b、c 三个元素的进栈次序足 a、b、c，符号 push 与 pop 分别表示对堆栈进行一次进栈操作与一次出栈操作
2、。3 请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列。4 指出不可能出现的出栈序列。5 对于一个有向图，除了进行拓扑排序，还可以采用什么方法判断图巾是否存在回路?请简述判断原则。6 请画出在下列 3 阶 B 一树中插入关键宁 10 以后的 B 一树的状态。7 在长度为 n 的线性表中进行顺序查找。查找第 i 个数据元素的概率为 Pi，且分布如下：P=12 i 请求出在该线性表中查找成功的平均查找长度(要求写成若干 n 的简单表达式形式)。综合模拟试卷 13 答案与解析一、填空题1 【正确答案】 并行空间并行时间并行2 【正确答案】 浮点指数对阶3 【正确答案】 先进后出 寄存器存储器
3、4 【正确答案】 优先级 公平总线控制5 【正确答案】 时间空间时间+空间二、简答题6 【正确答案】 取指周期中从内存读出的信息流是指令流，它流向控制器；而在执行器周期中从内存渎出的信息流是数据流，它由内存流向运算器。区分取出的数据是指令还是操作数，是根据取出该数据时处于哪一个指令周期，如果处于取指周期，那么取出的就是指令，如果处于取操作数周期，则取出的是操作数。三、计算题7 【正确答案】 设最高位为符号位，输入数据为x 补 =10001、y 补 =01101。乘积符号位运算：x 0 y0=1 1=1。算前求补器输出：x=1111 ， y=1101。11111101=11000011 算后求补
4、器输出为 00111101，加上乘积符号位 l，最后得补码乘积值为 100111101。利用补码与其值的换算公式，补码二进制数的真值是 xy=一 128+128+18 【正确答案】 证明：假设： (1)存储器模块字长等于数据总线宽度。 (2)模块存取一个字的存储周期等于 T。 (3)总线传送周期为 T。 (4)交叉存储器的交叉模块数为m，交叉存储器为了实现流水线方式存储，即每经过丁时间延迟后启动下一模块，应满足 T=mT。 1交叉存储器要求其模块数m ，以保证启动某模块后经过 mT 时间后再次启动该模块时，它的上次存取操作已经完成。这样连续读取 m 个字所需要的时间为 t1=T+(m 一 1)
5、T=mT+mT 一 T=(2m1)T。故交叉存储器带宽为W1=1t四、分析题9 【正确答案】 8341H=(1000001101000001)。X=11，相对寻址，D=41H，有效地址 E=(PC)+D=5431H+41H=5472H。10 【正确答案】 1438H=(0001010000111000)。X=00，直接寻址，D=38H，有效地址 E=D=0038H。11 【正确答案】 8134H=(1000000100110100)2X=01，用变址寄存器 RX1 寻址，D=34H，有效地址 E=(RX1)+D=3515H+34H=3549H。12 【正确答案】 6228H=(0110001000101000)，X=10，用变址寄存器 RX2 寻址，D=28H，有效地址 E=(RX2)+D=6766H+34H=679AH。13 【正确答案】 假设执行一条指令的时间也为 TM。当 3 个设备同时发出中断请求时，依次分别处理设备 A、B、C、D 的时间如下： tA=2TM+TDC+TS+TA+TRtB=2TM+2TDC+TS+TB+TRtC=2T14 【正确答案】 15 【正确答案】 16 【正确答案】
