A：1000
B：2000
C：3000
D：4000
40、如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机本地域名服务器发送的域名请求条数分别为（ A ）
A：1条，1条
B：1条，多条
C：多条，1条
D：多条，多条
二、综合应用题：41-47小题，共计70分
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 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 30 |
7 |
14 |
11 |
8 |
18 |
. |
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)
43.(11分)某计算机字长为16q位，主存地址空间大小为128KB，按字编址，采用字长指令格式，指令名字段定义如下：
转移指令采用相对寻址方式，相对偏移是用补码表示，寻址方式定义如下：
| Ms/Md |
寻址方式 |
助记符 |
含义 |
| 000B |
寄存器直接 |
Rn |
操作数=（Rn） |
| 001B |
寄存器间接 |
（Rn） |
操作数=（(Rn)） |
| 010B |
寄存器间接、自增 |
（Rn）+ |
操作数=（(Rn)），（Rn）+1→Rn |
| 011B |
相对 |
D（Rn） |
转移目标地址=（PC）+（Rn） |
注：
（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）+（逗号前原操作数，都号后为目的操作数）对应的机器码是什么（用十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变？改变后的内容是什么？
解答：
该题的考点是指令系统设计，注意操作位数与指令条数的关系，地址码与寄存器数的关系，指令字长与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开始）？
（3）、程序A和B的数据访问命令中各是多少？那个程序的执行时间更短？
简答：考点：Cache容量计算，直接映射方式的地址计算，以及命中率计算（行优先遍历与列优先遍历命中率分别很大）
45、（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空间状态
（1）、请说明在上述条件下如何进行磁盘块空闲状态管理。
（2）、设某单面磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相临磁道间的平均移动时间为1ms.
若在某时刻，磁头位于100号磁道处，并沿着磁道号大的方向移动（如下图所示），磁道号请求队列为50.90.30.120.对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这个扇区点共需要多少时间？要求给出计算过程。
46.（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB.按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB.操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）.
| 页号 |
页根号 |
装入时刻 |
访问位 |
| 0 |
7 |
130 |
1 |
| 1 |
4 |
230 |
1 |
| 2 |
2 |
200 |
1 |
| 3 |
9 |
160 |
1 |
当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：
（1）、该逻辑地址对应的页号是多少？
（2）、若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
（3）、若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下。）
解答：17CAH=(0001 0111 1100 1010)2
（1）页大小为1K，所以页内偏移地址为10位，于是前6位是页号，所以第一间的解为：5
（2）FIFO，则被置换的页面所在页框为7，所以对应的物理地址为（0001 1111 1100 1010）2-IFCAH
（3）CLOCK,则被置换的页面所在页框为2，所以对应的物理地址为（0000 1011 1100 1010）2-OBCAH
47、（9分）某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10MBPS,主机甲和主机乙之间的距离为2KM，信号传播速度是200 000KMS.请回答下列问题，并给出计算过程。
（1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经多长时间？最长需经过多长时间？（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）
（2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以大网数据锁（1518字节）向主机乙发送数据，主机乙每成功收到一个数据锁后，立即发送下一个数据锁，此时主机甲的有效数据传输速率是多少？（不考虑以大网锁的前导码）
解答：
（1）当甲乙同时向对方发送数据时，两台主机均检测到冲突所需时间最短；
1KM/200000KM/S*2=1*10(-5)S
当一方发送的数据马上要到达另一方时，另一方开始发送数据，两台主机均检测到冲突所需时间最长；
2KM/2000000KM/S*2=2*10(-5)S
（2）发送一锁所需时间；1518B/10MBPS=1.2144MS
数据传播时间；2KM/200 000KM/S=1*10（-5）S=0.01MS
有效的数据传输速率=10MBPS*1.2144MS/1.2244MS=9.92MBPS
