41.（10分）将关键字序列（7、8、11、18、9、14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列函数维：H（key）=（key×3）MODT，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7 问题：
（1）请画出所构造的散列表；
（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 解答：
（1）由装载因子0.7，数据总数7个→存储空间长度为10→P=10 所以，构造的散列表为： 0 30
1 7
2 14
3 11
4 8
5 18
6 .
7 9
8 .
9 .
H（7）=（7×3）MOD10=1
（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7
查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2
42.（13分）设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P（0﹤P﹤n）个位置，即将R中的数据由（X0 X1 ……Xn-1）变换为（Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1）要求： （1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度 解答：
（1）前P个数依次进队，while（1﹤n-p）A{i}-{i+p}：p个数依次出对，进入数组末尾
（2）详细程序略
（3）时间复杂度O（N）;空间复杂度o(p)
31
43.(11分)某计算机字长为16q位，主存地址空间大小为128KB，按字编址，采用字长指令格式，指令名字段定义如下：
转移指令采用相对寻址方式，相对偏移是用补码表示，寻址方式定义如下： Ms/Md 寻址方式 000B 001B 010B 011B 注：
（X）表示有储蓄地址X或寄存器X的内容，请回答下列问题：
（1）该指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存器（MDR）至少各需多少位？ （2）转移指令的目标地址范围是多少？
（3）若操作码0010B表示加法操作（助记符为a d d），寄存器R4和R5的编号分别为100B和101B，R4的内容为1 2 3 4 H，R5的内容为5 6 7 8 H，地址1 2 3 4 H中的内容为5 6 7 8 H中的内容为1 2 3 4 H，则汇编语言为a d d（R4）.（R5）+（逗号前原操作数，都号后为目的操作数）对应的机器码是什么（用十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变？改变后的内容是什么？
32
助记符 Rn （Rn）
含义
操作数=（Rn） 操作数=（(Rn)）
寄存器直接 寄存器间接
寄存器间接、自增 相对
（Rn）+ 操作数=（(Rn)），（Rn）+1→Rn D（Rn） 转移目标地址=（PC）+（Rn）
解答：
该题的考点是指令系统设计，注意操作位数与指令条数的关系，地址码与寄存器数的关系，指令字长与MOR的关系，存储容量与MAR的关系，注意补码计算的偏移地址。
44.（12分）某计算机的主存地址空间为256MB，按字节编址，指令Cache分离?均有8个Cache行，每个Cache行的大小为64MB，数据Cache采用直接映射方式，现有两个功能相同的程序A和B,其伪代码如下所示：
假定int 类型数据用32位补码表示，程序编译时i,j, sum 均分配在寄存器中，数据a按行优先方式存放，其地址为320（十进制数），请回答下列问题，要求说明理由或给出计算过程。
（1）、若不考虑用于cache一致性维护和替换算法的控制位，则数据Cache的总容量是多少？
（2）、要组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少（Cache行号从0开始）？
33
（3）、程序A和B的数据访问命令中各是多少？那个程序的执行时间更短？
简答：考点：Cache容量计算，直接映射方式的地址计算，以及命中率计算（行优先遍历与列优先遍历命中率分别很大）
45、（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空间状态
（1）、请说明在上述条件下如何进行磁盘块空闲状态管理。
（2）、设某单面磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相临磁道间的平均移动时间为1ms.
若在某时刻，磁头位于100号磁道处，并沿着磁道号大的方向移动（如下图所示），磁道号请求队列为50.90.30.120.对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这个扇区点共需要多少时间？要求给出计算过程。
34
46.（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB.按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB.操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）. 页号 0 1 2 3
页根号 7 4 2 9
装入时刻 130 230 200 160
访问位 1 1 1 1
当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题： （1）、该逻辑地址对应的页号是多少？
（2）、若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
（3）、若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下。）
35