问答题
给定序列{3，5，7，9，11，13，15，17}，
问答题
按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。
【正确答案】
【答案解析】按表中元素的顺序依次插入的二叉排序树如下图所示，其在等概率情况下查找成功的平均查找长度为：ASL:(1+2+3+4+5+6+7+8)/8=9/2。
问答题
按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度。
【正确答案】
【答案解析】按表中元素的顺序依次插入的平衡二叉树如下图所示，其在等概率情况下查找成功的平均查找长度为：ASI:(1+2*2+3*4+5)/8=11/4。
问答题
按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。
【正确答案】
【答案解析】题目要求能够发现两位错并纠正一位错，故需要在海明码的基础上增加1位全局的奇偶校验位，此时的编码方式称为“扩展的海明码”。
普通海明码编码计算如下：首先计算所需校验位的位数k，根据2k≥4+k+1，可知应取3位校验位，数据位与校验位的位置安排如下：
7
6
5
4
3
2
1
D3
D2
D3
C4
D0
C2
C1
1
0
1
0
各校验位的数值计算如下：
C1校验的比特位包含1、3、5、7位，按配偶原则

C2校验的比特位包含2、3、6、7位，按配偶原则

C4校验的比特位包含4、5、6、7位，按配偶原则

综上，将1010编码扩展为海明码为1010010，为了能够发现两位错并纠正一位错，在最左端增加1位全局偶校验位C8，

故，将有效信息1010编码扩展的海明码为11010010。
问答题
将其编码为循环冗余校验码，生成多项式G(x)=1011。
【正确答案】
【答案解析】将待编码的有效信息1010表示为多项式M(x)：
M(x)=X3+x=1010
由于生成多项式G(x)为4位，故将M(x)左移3位，得M(x)×X3，目的是空出3位，以便拼装余数(校验位)：
M(x)×x3=x6+x4=1010000
用M(x)×x3模2除生成多项式G(x)：

将左移后的待编码有效信息与余数R(x)作模2加，即形成循环冗余校验码：
M(x)×x3+R(x)=1010000+011=1010011
即用生成多项式G(x)=1011将有效信息1010编码，得循环冗余校验码1010011。
问答题
分别画出寻址方式由操作码指出和寻址方式由专用字段指出时的指令格式。
【正确答案】
【答案解析】100条指令需7位操作码，当寻址方式由操作码指出时，指令格式如下：
操作码(7位)
形式地址A(25位)
当寻址方式由专用字段指出时，指令格式如下：
操作码(7位)
寻址方式(2位)
形式地址(23位)

问答题
当指令寻址方式由操作码指出时，直接和间接寻址可寻址的主存空间大小为多少?
【正确答案】
【答案解析】当指令方式由操作码指出时，形式地址A为25位，又存储器按字节编址，故直接寻址可寻址的主存空间大小为225B=32MB；由于机器字长为32位，间接寻址可寻址的主存空间大小为232B=4GB。
问答题
写出4种寻址方式下，有效地址EA的表达式。
【正确答案】
【答案解析】四种寻址方式下有效地址EA的表达式为 直接寻址EA=A； 间接寻址EA=(A)； 变址寻址EA=(IX)+A，其中IX为变址寄存器； 相对寻址EA=(PC)+A，其中PC为程序计数器。