问答题

已知散列函数为H(key)=key%11，处理冲突的方法为二次探测法，探测的序列为：1，-1.4，-4，…，j²，-j²(j＜-m/2)：
当d_i＞O时，H_i=(H(key)+d_i)%m
当d_i＜0时，H_i=(H(key)+d_i+m)%m
散列表如下表所示，试回答下面的问题：

问答题

对表中每个关键字进行查找时，各需要进行的比较次数；

【正确答案】

【答案解析】查找成功的比较次数分为： 21:2 57:2 45:3 37:1 50:2

问答题

在等概率情况下查找时，查找成功的平均查找长度。

【正确答案】

【答案解析】查找成功的平均查找长度为(2+2+3+1+2)/5=2

问答题

原码定点小数；

【正确答案】

【答案解析】该32位二进制机器数为原码定点小数时，其真值为
-1×2^-1=-0.5；

问答题

补码定点小数；

【正确答案】

【答案解析】该32位二进制机器数为补码定点小数时，根据其符号位为1可知其为负数，为方便计算，将其连符号位在内取反加1，得其相反数的补码机器数为
0.1000 0000 0000 0000 0000 0000 0000 000
相反数真值为1×2^-1=0.5，故原机器数真值为-0.5；

问答题

反码定点小数；

【正确答案】

【答案解析】该32位二进制机器数为反码定点小数时，根据其符号位为1可知其为负数，故将其数值位取反即可得其真值对应的原码机器数为
1.0111 1111 1111 1111 1111 1111 1111 111
其真值为-(0×2^-1+1×2^-2+…+1×2^-31)=-(2^-1-2^-31)；

问答题

IBEE754标准短实数。
[注]题中机器数中间加空格是为了度写方便，并非机器数的一部分，答题时如有需要可类似表示。

【正确答案】

【答案解析】该32位二进制机器数表示IEEE754标准短实数时，根据IEEE754标准的格式，知其为负数，写出隐藏位，得其尾数的形式如下
-1.0000 0000 0000 0000 0000 000
尾数真值为-1，又IEEE754标准短实数阶码采用偏移量为7FH的移码，故其阶码真值为
1000 0000₂-0111 1111₂=0000 0001₂=1₁₀，又基数为2，故题目所求真值为
-1×2¹=-2。

问答题

主存地址位数为多少?

【正确答案】

【答案解析】主存按字节编址，容量为32MB=2²⁵B，故主存地址位数为25。

问答题

画出主存地址格式示意图，注明各字段名称及位数。

【正确答案】

【答案解析】主存字长32位，按字节编址，块长为4个字，即4字×4B/字=16B=2⁴B，故字块内地址需4位；Cache采用四路组相联映射，故每组容量为16B×4=64B，Cache共分16KB/64B=256=2⁸组，故组地址需8位；主存字块标记位数为25-4-8=13位。
主存地址格式如下表所示：

主存字块标记(13位)

组地址(8位)

字块内地址(4位)

问答题

设该Cache的命中率为98%，如果Cache的速度是主存的5倍，则该机采用Cache时存储系统的速度是不采用Cache时的多少倍(设CPU访存时同时访问Cache和主存，若Cache命中则中断主存访问)?

【正确答案】

【答案解析】设Cache访问时间为t，则主存访问时间为5t，采用Cache时存储系统的平均访问时间 T=t×0.98+5t×(1-0.98)=1.08t 故采用Cache存储系统的速度是不采用Cache时的5/1.08≈4.6倍。