# 2010年全国硕士研究生入学统一考试
# 计算机科学与技术学科联考
# 计算机学科专业基础综合试题
# 一、单项选择题：第1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试
# 题要求。
1. 若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是________。
A. dcebfa
B. c b d a e f
C. bcaefd
D. a f e d c b
2. 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作，则不可能得到的出队序列是________。
A.bace de
B. dbace
C. d b c a e
D. ecbad
3. 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是________。
A.
B.
C.
D.
4. 在右图所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是______。
A. 13, 48
B. 24, 48
C. 24, 53
D、24，90
5. 在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是 ________。
A. 41
B. 82
C. 113
D. 122
6. 对 $\mathbf{n}(\mathbf{n}\geq 2)$ 个权值均不相同的字符构造成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是
A. 该树一定是一棵完全二叉树。
B. 树中一定没有度为 1 的结点。
C. 树中两个权值最小的结点一定是兄弟结点。
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值。
7. 若无向图 $\mathrm{G} = (\mathrm{V}, \mathrm{E})$ 中含有 7 个顶点，要保证图 $\mathrm{G}$ 在任何情况下都是连通的，则需要的边数最少是
A. 6
B. 15
C. 16
D. 21
8. 对右图进行拓扑排序，可以得到不同的拓扑序列的个数是____。
A. 4
B. 3
C. 2
D. 1
9. 已知一个长度为 16 的顺序表 L, 其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素, 则关键字的比较次数最多的是______。
A. 4
B. 5
C. 6
D. 7
10. 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是______。
A. 递归次数与初始数据的排列次序无关。
B. 每次划分后，先处理较长的分区可以减少递归次数。
C. 每次划分后, 先处理较短的分区可以减少递归次数。
D. 递归次数与每次划分后得到的分区的处理顺序无关。
11．对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下：
第一趟排序结果：2，12，16，5，10，88
第二趟排序结果：2，12，5，10，16，88
第三趟排序结果：2，5，10，12，16，88
则采用的排序方法可能是
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
12. 下列选项中，能缩短程序执行时间的措施是
I. 提高CPU时钟频率
II.优化数据通路结构
III. 对程序进行编译优化
A. 仅 I 和 II
B. 仅 I 和 III
C. 仅II和III
D. I 、II 和III
13. 假定有 4 个整数用 8 位补码分别表示 $\mathrm{r}1 = \mathrm{FEH}$ , $\mathrm{r}2 = \mathrm{F}2\mathrm{H}$ , $\mathrm{r}3 = 90\mathrm{H}$ , $\mathrm{r}4 = \mathrm{F}8\mathrm{H}$ , 若将运算结果存放在一个 8 位寄存器中, 则下列运算中会发生溢出的是
A. r1 x r2
B. r2 x r3
C. r1 x r4
D. r2 x r4
14. 假定变量 i、f 和 d 的数据类型分别为 int, float 和 double（int 用补码表示，float 和 double 分别用 IEEE754 单精度和双精度浮点数格式表示），已知 $i = 785, f = 1.5678 \mathrm{e}3, d = 1.5 \mathrm{e}100$ 。若在 32 位机器中执行下列关系表达式，则结果为“真”的是 ________。
(I) $\mathrm{i} = = (\mathrm{int})(\mathrm{float})\mathrm{i}$
$(\Pi)\mathbf{f} = = (\mathrm{float})(\mathrm{int})\mathbf{f}$
$(\mathrm{III})\mathrm{f} =$ (float)(double)f
$(\mathrm{IV})(\mathrm{d} + \mathrm{f}) - \mathrm{d} = = \mathrm{f}$
A. 仅 I 和 II
B. 仅 I 和 III
C. 仅 II 和 III
D. 仅 III 和 IV
15. 15. 假定用若干个 $2 \mathrm{~k} \times 4$ 位的芯片组成一个 $8 \mathrm{~k} \times 8$ 位的存储器, 则地址 0B1FH 所在芯片的最小地址是
A. 0000H
B. $0600\mathrm{H}$
C. ${0700}\mathrm{H}$
D. $0800 \mathrm{H}$
16. 下列有关 RAM 和 ROM 的叙述中，正确的是________。
IRAM是易失性存储器，ROM是非易失性存储器
II RAM 和 ROM 都采用随机存取方式进行信息访问
III RAM 和 ROM 都可用作 Cache
IV RAM 和 ROM 都需要进行刷新
A. 仅 I 和 II
B. 仅 II 和 III
C. 仅 I,II 和 IV
D. 仅 II, III 和 IV
17. 下列命中组合情况中，一次访存过程中不可能发生的是________。
A. TLB 未命中，Cache 未命中，Page 未命中
B. TLB 未命中, Cache 命中, Page 命中
C. TLB 命中, Cache 未命中, Page 命中
D. TLB 命中, Cache 命中, Page 未命中
18. 下列寄存器中，汇编语言程序员可见的是________。
A. 存储器地址寄存器(MAR)
B. 程序计数器(PC)
C. 存储器数据寄存器(MDR)
D. 指令寄存器(IR)
19. 下列选项中，不会引起指令流水线阻塞的是________。
A. 数据旁路（转发）
B. 数据相关
C. 条件转移
D. 资源冲突
20. 下列选项中的英文缩写均为总线标准的是________。
A. PCI、CRT、USB、EISA
B.ISA、CPI、VESA、EISA
C.ISA、SCSI、RAM、MIPS
D.ISA、EISA、PCI、PCI-Express
21. 单级中断系统中，中断服务程序内的执行顺序是________。
I保护现场
II开中断
III关中断
IV 保存断点
V中断事件处理
VI恢复现场
VII中断返回
A. $\mathrm{I} > \mathrm{V} - > \mathrm{VI} - > \mathrm{II} - > \mathrm{VII}$
B. III->I->V->VII
C. III->IV->V->VI->VII
D. IV->I->V->VI->VII
22. 假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为 $1600*1200$ ，颜色深度为24位，帧频为85HZ，显存总带宽的 $50\%$ 用来刷新屏幕，则需要的显存总带宽至少约为________。
A. 245Mbps
B. 979Mbps
C. 1958Mbps
D. 7834Mbps
23. 下列选项中，操作系统提供给应用程序的接口是____。
A. 系统调用
B. 中断
C. 库函数
D. 原语
24. 下列选项中，导致创建新进程的操作是________。
I 用户登录成功
II 设备分配
III 启动程序执行
A. 仅 I 和 II
B. 仅 II 和 III
C. 仅 I 和 III
D. I 、II 和III
25. 设与某资源关联的信号量初值为 3 , 当前值为 1 。若 M 表示该资源的可用个数, N 表示等待该资源的进程数, 则 M、N 分别是_____。
A. 0、1
B. 1、0
C. 1、2
D. 2、0
26. 下列选项中，降低进程优先级的合理时机是______。
A. 进程的时间片用完
B. 进程刚完成 I/O, 进入就绪列队
C. 进程长期处于就绪列队中
D. 进程从就绪态转为运行态
27. 进程 P0 和 P1 的共享变量定义及其初值为
boolean flag[2];
int turn $= 0$
$\mathrm{flag}[0] = \mathrm{FA}$ LSE; flag[1] $=$ FA LSE;
若进程P0和P1访问临界资源的类C伪代码实现如下：
```c
void P0() // 进程P0
{
while (TRUE)
{
flag[0] = TRUE; turn=1;
while (flag[1] && (turn==1))
{
临界区；
flag[0] = FALSE;
}
}
```
```c
void P1() // 进程P1
{
while (TRUE)
{
flag[1] = TRUE; turn = 0;
while (flag[0] && (turn == 0))
;
临界区；
flag[1] = FALSE;
}
}
```
则并发执行进程P0和P1时产生的情形是______。
A. 不能保证进程互斥进入临界区，会出现“饥饿”现象
B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象
C. 能保证进程互斥进入临界区, 会出现“饥饿”现象
D. 能保证进程互斥进入临界区，不会出现“饥饿”现象
28. 某基于动态分区存储管理的计算机, 其主存容量为 $55 \mathrm{MB}$ (初始为空闲), 采用最佳适配 (Best Fit) 算法, 分配和释放的顺序为: 分配 $15 \mathrm{MB}$ , 分配 $30 \mathrm{MB}$ , 释放 $15 \mathrm{MB}$ , 分配 $8 \mathrm{MB}$ , 分配 $6 \mathrm{MB}$ , 此时主存中最大空闲分区的大小是______。
A. 7MB
B. 9MB
C. 10MB
D. 15MB
29. 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 $2^{10}$ 字节，页表项大小为 2 字节，逻辑地址结构为：
逻辑地址空间大小为 $2^{16}$ 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是
A. 64
B. 128
C. 256
D. 512
30. 设文件索引节点中有 7 个地址项，其中 4 个地址项是直接地址索引，2 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4 字节。若磁盘索引块和磁盘数据块大小均为 256 字节，则可表示的单个文件最大长度是 ________。
A. ${33}\mathrm{{KB}}$
B. $519\mathrm{KB}$
C. $1057 \mathrm{~KB}$
D. ${16513}\mathrm{{KB}}$
31. 设置当前工作目录的主要目的是
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
32. 本地用户通过键盘登陆系统时，首先获得键盘输入信息的程序是________。
A. 命令解释程序
B. 中断处理程序
C. 系统调用服务程序
D. 用户登录程序
33. 下列选项中，不属于网络体系结构所描述的内容是________。
A. 网络的层次
B. 每一层使用的协议
C. 协议的内部实现细节
D. 每一层必须完成的功能
34. 在下图所示的采用“存储-转发”方式的分组交换网络中，所有链路的数据传输速率为 $100\mathrm{Mbps}$ ，分组大小为 $1000\mathrm{B}$ ，其中分组头大小为 $20\mathrm{B}$ 。若主机 H1 向主机 H2 发送一个大小为 $980000\mathrm{B}$ 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从 H1 发送开始到 H2 接收完为止，需要的时间至少是
A. $80 \mathrm{~ms}$
B. $80.08 \mathrm{~ms}$
C. $80.16 \mathrm{~ms}$
D. $80.24 \mathrm{~ms}$
35. 某自治系统内采用 RIP 协议，若该自治系统内的路由器 R1 收到其邻居路由器 R2 的距离矢量，距离矢量中包含信息 ，则能得出的结论是 ______。
A. R2 可以经过 R1 到达 net1, 跳数为 17
B. R2可以到达net1，跳数为16
C. R1 可以经过 R2 到达 net1, 跳数为 17
D. R1 不能经过 R2 到达 net1
36. 若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP报文类型是
A. 路由重定向
B. 目的不可达
C. 源点抑制
D. 超时
37. 某网络的 IP 地址空间为 192.168.5.0/24，采用定长子网划分，子网掩码为 255.255.255.248，则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是____。
A. 32, 8
B. 32, 6
C. 8, 32
D. 8, 30
38. 下列网络设备中，能够抑制广播风暴的是________。
I中继器
II 集线器
III 网桥
IV路由器
A. 仅 I 和 II
B. 仅III
C. 仅III 和IV
D. 仅IV
39. 主机甲和主机乙之间已建立了一个 TCP 连接, TCP 最大段长度为 1000 字节。若主机甲的当前拥塞窗口为 4000 字节, 在主机甲向主机乙连续发送两个最大段后, 成功收到主机乙发送的第一个段的确认段, 确认段中通告的接收窗口大小为 2000 字节, 则此时主机甲还可以向主机乙发送的最大字节数是______。
A. 1000
B. 2000
C. 3000
D. 4000
40. 如果本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为________。
A. 一条、一条
B. 一条、多条
C. 多条、一条
D. 多条、多条
# 二、综合应用题：第41~47题，共70分。
41. (10 分) 将关键字序列 (7、8、30、11、18、9、14) 散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组, 散列函数为: $\mathrm{H}\left( \text {key }\right) = \left( {\text{key} \times 3}\right) \mathrm{{MOD}}7$ ,处理冲突采用线性探测再散列法, 要求装填 (载) 因子为 0.7 。
(1) 请画出所构造的散列表。
(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或 $\mathbf{C} + +$ 或JAVA语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
43.（11分）某计算机字长为16位，主存地址空间大小为 $128\mathrm{KB}$ ，按字编址。采用单字长指令格式，指令各字段定义如下：
源操作数
目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：
| Ms/Md | 寻址方式 | 助记符 | 含义 |
| 000B | 寄存器直接 | Rn | 操作数=（Rn） |
| 001B | 寄存器间接 | (Rn) | 操作数=(Rn) |
| 010B | 寄存器间接、自增 | (Rn)+ | 操作数=((Rn),(Rn)+1→Rn |
| 011B | 相对 | D(Rn) | 转移目标地址=(PC)+(Rn) |
注：（X）表示存储器地址X或寄存器X的内容。
请回答下列问题：
(1) 该指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存器（MAR）和存储器数据寄存器（MDR）至少各需要多少位？
(2）转移指令的目标地址范围是多少？
(3) 若操作码0010B表示加法操作（助记符为add），寄存器R4和R5的编号分别为100B和101B，R4的内容为1234H，R5的内容为5678H，地址1234H中的内容为5678H，地址5678H中的内容为1234H，则汇编语言为“add（R4），（R5）+”（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（用十六进制表示）？该指令执行后，哪些寄存器和存储单元中的内容会改变？改变后的内容是什么？
44.（12分）某计算机的主存地址空间大小为 $256\mathrm{MB}$ ，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示：
```c
程序A:
int a[256][256]
......
int sum_array1()
{
int i, j, sum = 0;
for (i = 0; i < 256; i++)
for (j = 0; j < 256; j++)
sum += a[i][j];
return sum;
}
```
```txt
程序B:
int a[256][256]
......
int sum_array2()
{
int i, j, sum = 0;
for (j = 0; j < 256; j++)
for (i = 0; i < 256; i++)
sum += a[i][j];
return sum;
}
```
假定int类型数据用32位补码表示，程序编译时i，j，sum均分配在寄存器中，数组a按行优先方式存放，其首地址为320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。
(1) 若不考虑用于 cache 一致性维护和替换算法的控制位，则数据 Cache 的总容量为多少？
(2) 数组元素 a[0][31] 和 a[1][1] 各自所在的主存块对应的 Cache 行号分别是多少（Cache 行号从 0 开始）？
(3) 程序 A 和 B 的数据访问命中率各是多少？哪个程序的执行时间更短？
45.（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。
(1) 请说明在上述条件下如何进行磁盘块空闲状态的管理。
(2) 设某单面磁盘旋转速度为每分钟 6000 转, 每个磁道有 100 个扇区, 相邻磁道间的平均移动时间为 $1 \mathrm{~ms}$ 。若在某时刻, 磁头位于 100 号磁道处, 并沿着磁道号增大的方向移动 (如下图所示), 磁道号请求队列为 50, 90, 30, 120, 对请求队列中的每个磁道需读取 1 个随机分布的扇区, 则读完这 4 个扇区点共需要多少时间? 要求给出计算过程。
(3) 如果将磁盘替换为随机访问的 Flash 半导体存储器（如 U 盘、SSD 等），是否有比 CSCAN 更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。
46. (8 分) 设某计算机的逻辑地址空间和物理地址空间均为 64KB, 按字节编址。若某进程最多需要 6 页 (Page) 数据存储空间, 页的大小为 1KB, 操作系统采用固定分配局部置换策略为此进程分配 4 个页框 (Page Frame)。在时刻 260 前的该进程访问情况如下表所示（访问位即使用位）。
| 页号 | 页框号 | 装入时刻 | 访问位 |
| 0 | 7 | 130 | 1 |
| 1 | 4 | 230 | 1 |
| 2 | 2 | 200 | 1 |
| 3 | 9 | 160 | 1 |
当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：
(1) 该逻辑地址对应的页号是多少？
(2) 若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
(3) 若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针沿顺时针方向移动，且当前指向 2 号页框，示意图如下）。
图3.15 页框示意图
47. (9 分) 某局域网采用 CSMA/CD 协议实现介质访问控制, 数据传输速率为 $10 \mathrm{Mbps}$ , 主机甲和主机乙之间的距离为 $2 \mathrm{~km}$ , 信号传播速度是 $200000 \mathrm{~km} / \mathrm{s}$ 。请回答下列问题, 要求说明理由或写出计算过程。
(1) 若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间？最长需经过多长时间（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）？
(2) 若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网的前导码）？
# 参考答案
# 一、单项选择题（后附有解析）
1. D
2. C
3. D
4. C
5. B
6. A
7. C
8. B
9. B
10. D
11. A
12. D
13. B
14. B
15. D
16. A
17. D
18. B
19. A
20. D
21. A
22. D
23. A
24. C
25. B
26. A
27. D
28. B
29. B
30. C
31. C
32. B
33. C
34. C
35. D
36. C
37. B
38. D
39. A
40. A
# 二、综合应用题
# 41. 解答：
(1) 由装载因子0.7，数据总数为7，得一维数组大小为 $7 / 0.7 = 10$ ，数组下标为 $0\sim 9$ 。所构造的散列函数值如下所示：
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
| H(key) | 0 | 3 | 6 | 5 | 5 | 6 | 0 |
采用线性探测再散列法处理冲突，所构造的散列表为：
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 关键字 | 7 | 14 | | 8 | | 11 | 30 | 18 | 9 | |
(2) 查找成功时，是根据每个元素查找次数来计算平均长度，在等概率的情况下，各关键字的查找次数为：
故， $\mathrm{ASL}_{\text{成功}} =$ 查找次数 / 元素个数 $= (1 + 2 + 1 + 1 + 1 + 3 + 3) / 7 = 12 / 7$
这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数 MOD 7，初始只可能在 0~6 的位置。等概率情况下，查找 0~6 位置查找失败的查找次数为：
故， $\mathrm{ASL}_{\text{不成功}} =$ 查找次数/散列后的地址个数 $= (3 + 2 + 1 + 2 + 1 + 5 + 4) / 7 = 18 / 7$
# 42. 解答：
（1）算法的基本设计思想：
可以将这个问题看做是把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到 $\mathbf{a}^{-1}\mathbf{b}$ ，再将b逆置得到 $\mathrm{a^{-1}b^{-1}}$ ，最后将整个 $\mathrm{a^{-1}b^{-1}}$ 逆置得到 $(\mathrm{a^{-1}b^{-1}})^{-1} = \mathrm{ba}$ 。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（ $p = 3$ ）个位置的过程如下：
Reverse(0,p-1)得到cbadefgh;
Reverse(p,n-1)得到cbahgfed;
Reverse(0,n-1)得到defghabc;
注：Reverse中，两个参数分别表示数组中待转换元素的始末位置。
（2）使用c语言描述算法如下：
void Reverse(int R[],int from,int to) $\{$
int i, temp;
for $(\mathrm{i} = 0;\mathrm{i} < (\mathrm{to - from} + 1) / 2;\mathrm{i} + + )$
```txt
$\{\mathrm{temp} = \mathrm{R[from + i]};\mathrm{R[from + i]} = \mathrm{R[to - i]};\mathrm{R[to - i]} = \mathrm{temp};\}$
} // Reverse
void Converse(int R[],int n,int p){ Reverse(R,0,p-1); Reverse(R,p,n-1); Reverse(R,0,n-1);
```
（3）上述算法中三个Reverse函数的时间复杂度分别为 $\mathrm{O}(p / 2)$ 、 $\mathrm{O}((n - p) / 2)$ 和 $\mathrm{O}(n / 2)$ ，故所设计的算法的时间复杂度为 $\mathrm{O}(n)$ ，空间复杂度为 $\mathrm{O}(1)$ 。
另解，借助辅助数组来实现：
算法思想：创建大小为 $p$ 的辅助数组 $S$ ，将 $R$ 中前 $p$ 个整数依次暂存在 $S$ 中，同时将 $R$ 中后 $n - p$ 个整数左移，然后将 $S$ 中暂存的 $p$ 个数依次放回到 $R$ 中的后续单元。
时间复杂度为 $O(n)$ , 空间复杂度为 $O(p)$ 。
# 43. 解答：
(1) 操作码占4位，则该指令系统最多可有 $2^{4} = 16$ 条指令；操作数占6位，寻址方式占3位，于是寄存器编号占3位，则该机最多有 $2^{3} = 8$ 个通用寄存器；主存容量128KB，按字编址，计算机字长为16位，划分为 $128\mathrm{KB} / 2\mathrm{B} = 2^{16}$ 个存储单元，故MDR和MAR至少各需16位。
(2)PC和Rn可表示的地址范围均为 $0\sim 2^{16} - 1$ ，而主存地址空间为 $2^{16}$ ，故转移指令的目标地址范围是 $0000\mathrm{H}\sim$ FFFFH（ $0\sim 2^{16} - 1$ ）。
(3) 汇编语句“add(R4), (R5)+”，对应的机器码为0010001100010101B=2315H。
该指令执行后，寄存器R5和存储单元 $5678\mathrm{H}$ 的内容会改变。执行后，R5的内容从 $5678\mathrm{H}$ 变成 $5679\mathrm{H}$ 。存储单元 $5678\mathrm{H}$ 中的内容变成该加法指令计算的结果 $5678\mathrm{H} + 1234\mathrm{H} = 68\mathrm{ACH}$ 。
# 44. 解答：
(1) 数据 Cache 有 8 个 Cache 行，每个 Cache 行大小为 64B，Cache 中每个字块的 Tag 字段的位数是 $28 - 9 = 19$ 位，此外还需使用一个有效位，合计 20 位。因此，数据 Cache 的总容量应为： $8 \times (64 + 20 / 8)\mathrm{B} = 532\mathrm{B}$ 。
(2) 数组 a 在主存的存放位置及其与 Cache 之间的映射关系如下图所示：
数组按行优先方式存放，首地址为320，数组元素占四个字节。a[0][31]所在的主存块对应的Cache行号为：
```txt
$(320 + 31 \times 4)$ DIV $64 = 6$
```
a[1][1]所在的主存块对应的Cache行号为：
```txt
$(320 + 256 \times 4 + 1 \times 4)$ DIV 64 MOD $8 = 5$ 。
```
(3) 编译时 i、j、sum 均分配在寄存器中，故数据访问命中率仅考虑数组 a 的情况。
① 该程序的特点是数组中的每一个元素仅被使用一次。数组a按行优先存放，数据Cache正好放下数组半行中的全部元素，即元素的存储顺序与使用次序高度的吻合，每个字块的16个int型元素中，除访问的第一个不会命中，接下来的15个都会命中。访问全部字块都符合这一规律，故命中率为 $15 / 16$ ，即程序A的数据访问命中率是 $93.75\%$ 。
② 程序 B 按照数组的列执行外层循环，在执行内层循环的过程中，将连续访问不同行的同一列的数据，不同行的同一列数组使用的是同一个 Cache 单元，每次都不会命中，故命中率是 0
由于从 Cache 读数据比从主存读数据快很多，所以程序 A 的执行比程序 B 快得多。
注意：本题考查 Cache 容量计算，直接映射方式的地址计算，以及命中率计算（注意：行优先遍历与列优先遍历命中率差别很大）。
# 45. 解答：
(1) 用位图表示磁盘的空闲状态。每一位表示一个磁盘块的空闲状态，共需要 $16384 / 32 = 512$ 个字 $= 512 \times 4$ 个字节 $= 2\mathrm{KB}$ ，正好可放在系统提供的内存中。
(2)采用CSCAN调度算法，访问磁道的顺序和移动的磁道数如下表所示：
| 被访问的下一个磁道号 | 移动距离（磁道数） |
| 120 | 20 |
| 30 | 90 |
| 50 | 20 |
| 90 | 40 |
移动的磁道数为 $20 + 90 + 20 + 40 = 170$ ，故总的移动磁道时间为 $170\mathrm{ms}$ 。
由于转速为 $6000\mathrm{r / m}$ ，则平均旋转延迟为 $5\mathrm{ms}$ ，总的旋转延迟时间 $= 20\mathrm{ms}$ 。
由于转速为 $6000\mathrm{r / m}$ ，则读取一个磁道上一个扇区的平均读取时间为 $0.1\mathrm{ms}$ ，总的读取扇区的时间平均读取时间为 $0.1\mathrm{ms}$ ，总的读取扇区的时间为 $0.4\mathrm{ms}$ 。
综上，读取上述磁道上所有扇区所花的总时间为 $190.4\mathrm{ms}$ 。
(3) 采用 FCFS（先来先服务）调度策略更高效。因为 Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按 I/O 请求的先后顺序服务。
# 46. 解答：
(1) 由于该计算机的逻辑地址空间和物理地址空间均为 $64\mathrm{KB} = 2^{16}\mathrm{B}$ , 按字节编址, 且页的大小为 $1\mathrm{K} = 2^{10}$ , 故逻辑地址和物理地址的地址格式均为:
17CAH=000101111001010B，可知该逻辑地址的页号为 $000101\mathrm{B} = 5$
(2) 根据 FIFO 算法，需要替换装入时间最早的页，故需要置换装入时间最早的 0 号页，即将 5 号页装入 7 号页框中，所以物理地址为 000111111001010B = 1FCAH。
(3) 根据 CLOCK 算法，如果当前指针所指页框的使用位为 0，则替换该页；否则将使用位清零，并将指针指向下一个页框，继续查找。根据题设和示意图，将从 2 号页框开始，前 4 次查找页框号的顺序为
$2 \rightarrow 4 \rightarrow 7 \rightarrow 9$ ，并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位为0，故淘汰2号页框对应的2号页，把5号页装入2号页框中，并将对应使用位设置为1，所以对应的物理地址为 $0000101111001010B = 0\mathrm{BCAH}$ 。
# 47. 解答：
(1) 当主机甲和主机乙同时向对方发送数据时，信号在信道中发生冲突后，冲突信号继续向两个方向传播。这种情况下两台主机均检测到冲突需要经过的时间最短，等于单程的传播时延 $t_0 = 2km / 200000km / s = 0.01ms$ 。
主机甲（或主机乙）先发送一个数据帧，当该数据帧即将到达主机乙（或主机乙）时，主机乙（或主机甲）也开始发送一个数据帧，这时，主机乙（或主机甲）将立刻检测到冲突，而主机甲（或主机乙）要检测到冲突，冲突信号还需要从主机乙（或主机甲）传播到主机甲（或主机乙），因此甲乙两台主机均检测到冲突所需的最长时间等于双程的传播时延 $2^{*}t0 = 0.02ms$ 。
(2) 主机甲发送一个数据帧的时间，即发送时延 $t1 = 1518 \times 8b / 10\text{Mbps} = 1.2144 \text{ms}$ ；主机乙每成功收到一个数据帧后，向主机甲发送确认帧，确认帧的发送时延 $t2 = 64 \times 8b / 10\text{Mbps} = 0.0512\text{ms}$ ；主机甲收到确认帧后，即发送下一数据帧，故主机甲的发送周期 $T =$ 数据帧发送时延 $t1 +$ 确认帧发送时延 $t2 +$ 双程传播时延 $= t1 + t2 + 2*t0 = 1.2856 \text{ms}$ ；于是主机甲的有效数据传输率为
$1500 \times 8 / T = 12000 b / 1.2856 m s \approx 9.33 M b p s$ （以太网有效数据1500字节，即以太网帧的数据部分）
# 2010年全国硕士研究生入学统一考试计算机学科专业基础综合试题——选择题部分解析
# 一、单项选择题
1. 考查限定条件的出栈序列。
A 可由 in, in, in, in, out, out, in, out, out, in, out, out 得到;
B 可由 in, in, in, out, out, in, out, out, in, out 得到;
C 可由 in, in, out, in, out, out, in, in, out, in, out, out 得到;
D 可由 in, out, in, in, in, in, in, out, out, out, out, out 得到，但题意要求不允许连续三次退栈操作，故 D 错。
2. 考查受限的双端队列的出队序列。
A 可由左入，左入，右入，右入，右入得到 B 可由 左入，左入，右入，左入，右入得到。
D 可由左入, 左入, 左入, 右入, 左入得到 所以不可能得到 C。
3. 考查线索二叉树的基本概念和构造。
题中所给二叉树的后序序列为 dbca。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。
4. 考查平衡二叉树的插入算法。
插入48以后，该二叉树根结点的平衡因子由-1变为-2，失去平衡，需进行两次旋转（先右旋后左旋）操作。
5. 考查树结点数的特性。
设树中度为 $i$ （ $i = 0, 1, 2, 3, 4$ ）的结点数分别为 $N_{i}$ ，树中结点总数为 $N$ ，则树中各结点的度之和等于 $N - 1$ ，即 $N = 1 + N_{1} + 2N_{2} + 3N_{3} + 4N_{4} = N_{0} + N_{1} + N_{2} + N_{3} + N_{4}$ ，根据题设中的数据，即可得到 $N_{0} = 82$ ，即树 $T$ 的叶结点的个数是 82。
6. 考查哈弗曼树的特性。
哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为1的结点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。
7. 考查图的连通性。
要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通，首先需要 G 的任意六个结点构成完全连通子图 G1，需 15 条边，然后再添一条边将第 7 个结点与 G1 连接起来，共需 16 条边。
8. 考查拓扑排序序列。
题中图有三个不同的拓扑排序序列，分别为abcd，abcd，aebcd。
9. 考查折半查找的过程。
具有 $n$ 个结点的判定树的高度为 $\left\lfloor \log_2 n \right\rfloor + 1$ ，长度为 16，高度为 5，所以最多比较 5 次。
10. 考查快速排序。
递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少，如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。
11. 考查各种排序算法的过程。
看第一趟可知仅有88被移到最后
如果是希尔排序，则12，88，10应变为10，12，88。因此排除希尔排序。
如果是归并排序，则应长度为2的子序列是有序的，由此可排除归并。
如果是基数排序，则16，5，10应变为10，5，16，由此排除基数。
可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。
12. 考查计算机的性能指标。
I.CPU的时钟频率，也就是CPU主频率，一般说来，一个时钟周期内完成的指令数是固定的，所以主频越高，CPU的速度也就快，程序的执行时间就越短。
II. 数据在功能部件之间传送的路径称为数据通路，数据通路的功能是实现 CPU 内部的运算器和寄存器以及寄存器之间的数据交换。优化数据通路结构，可以有效提高计算机系统的吞吐量，从而加快程序的执行。
III.计算机程序需要先转化成机器指令序列才能最终得到执行，通过对程序进行编译优化可以得到更优的指令序列，从而使得程序的执行时间也越短。
13. 考查定点数的运算。
用补码表示时8位寄存器所能表示的整数范围为-128~+127。由于 $r1 = -2$ ， $r2 = -14$ ， $r3 = -112$ ， $r4 = -8$ ，则 $r2 \times r3 = 1568$ ，结果溢出。
14. 考查不同精度的数在计算机中的表示方法及其相互装换。
由于（int） $f = 1$ ，小数点后面4位丢失，故Ⅱ错。IV的计算过程是先将f转化为双精度浮点数据格式，然后进行加法运算，故（d+f）-d得到的结果为双精度浮点数据格式，而f为单精度浮点数据格式，故Ⅳ错。
15. 考查存储器的组成和设计。
用 $2 \mathrm{~K} \times 4$ 位的芯片组成一个 $8 \mathrm{~K} \times 8$ 位存储器，每行中所需芯片数为 2，每列中所需芯片数为 4，各行芯片的地址分配为：
第一行（2个芯片并联） 0000H~07FFH
第二行（2个芯片并联） 0800H~0FFFH
第三行（2个芯片并联） 1000H~17FFH
第四行（2个芯片并联） 1800H~1FFFH
于是地址0B1FH所在芯片的最小地址即为0800H。
16. 考查半导体随机存取存储器。
一般 Cache 采用高速的 SRAM 制作，比 ROM 速度快很多，因此 III 是错误的，排除法即可选 A。RAM 需要刷新，而 ROM 不需要刷新。
17. 考查 TLB、Cache 及 Page 之间的关系。
TLB 即为快表，快表只是慢表（Page）的小小副本，因此 TLB 命中，必然 Page 也命中，而当 Page 命中，TLB 则未必命中，故 D 不可能发生；而 Cache 的命中与否与 TLB、Page 的命中与否并无必然联系。
18. 考查CPU内部寄存器的特性。
汇编程序员可以通过指定待执行指令的地址来设置PC的值，而IR，MAR，MDR是CPU的内部工作寄存器，对程序员不可见。
19. 考查指令流水线的基本概念。
有三种相关可能引起指令流水线阻塞：1. 结构相关，又称资源相关；2. 数据相关；3. 控制相关，主要由转移指令引起。
数据旁路技术，其主要思想是不必待某条指令的执行结果送回到寄存器，再从寄存器中取出该结果，作为下一条指令的源操作数，而是直接将执行结果送到其他指令所需要的地方，这样可以使流水线不发生停顿。
20. 考查典型的总线标准，
目前典型的总线标准有：ISA、EISA、VESA、PCI、PCI-Express、AGP、USB、RS-232C等。
21. 考查中断处理过程。
单级中断系统中，不允许中断嵌套。中断的处理过程为：1. 关中断；2. 保存断点；3. 识别中断源；4. 保存现场；5. 中断事件处理；（开中断、执行中断服务程序、关中断）6. 恢复现场；7. 开中断；8. 中断返回。其中，1~3步由硬件完成，4~8由中断服务程序完成。
22. 考查显示器相关概念。
刷新所需带宽 = 分辨率×色深×帧频 = 1600×1200×24b×85HZ = 3916.8Mbps，显存总带宽的 $50\%$ 用来刷屏，于是需要的显存总带宽为 $3916.8 / 0.5 = 7833.6\mathrm{Mbps} \approx 7834\mathrm{Mbps}$ 。
23. 考查操作系统的接口。
系统调用是能完成特定功能的子程序，当应用程序要求操作系统提供某种服务时，便调用具有相应功能的系统调用。库函数则是高级语言中提供的与系统调用对应的函数（也有些库函数与系统调用无关），目的是隐藏访管指令的细节，使系统调用更为方便抽象。但要注意，库函数属于用户程序而非系统调用，是系统调用的上层。
24. 考查引起创建进程的事件。
引起进程创建的事件有：用户登录、作业调度、提供服务、应用请求等，本题的选项分别对应：I用户登录成功在分时系统中，用户登录成功，系统将为终端建立一个进程。II设备分配设备分配是通过在系统中设置相应的数据结构实现的，不需要创建进程。III启动程序执行典型的引起创建进程的事件。
25. 考查信号量的原理。
信号量表示当前的可用相关资源数。当信号量 $K > 0$ 时，表示还有 $K$ 个相关资源可用；而当信号量 $K < 0$ 时，表示有 $|K|$ 个进程在等待该资源。所以该资源可用数是 1，等待该资源的进程数是 0。
26. 考查进程调度。
进程时间片用完，从执行态进入就绪态应降低优先级以让别的进程被调度进入执行状态。B 中进程刚完成 I/O，进入就绪队列后应该等待被处理机调度，故应提高优先权；C 中有类似的情况；D 中不应该在此时降低，应该在时间片用完后降低。
27. 考查进程间通信与Peterson算法。
此算法实现互斥的主要思想在于设置了一个 tum 变量，用于进程间的互相“谦让”。
一般情况下，如果进程 p0 试图访问临界资源，设置 flag[0] = true，表示希望访问。此时如果进程 p1 还未试图访问临界资源，则 flag[1] 在进程上一次访问完临界资源退出临界区后已设置为 false。所以进程 p0 在执行循环判断条件时，第一个条件不满足，进程 p0 可以正常进入临界区，且满足互斥条件。
我们需要考虑的是两个进程同时试图访问临界资源的情况。注意 turn 变量的含义：进程在试图访问时，首先设置自己的 flag 变量为 true，表示希望访问；但又设置 turn 变量为对方的进程编号，表示“谦让”，因为在循环判断条件中 turn 变量不是自己编号时就循环等待。这时两个进程就会互相“谦让”一番，但是这不会造成饥饿的局面，因为 turn 变量会有一个最终值，所以必定有进程可以结束循环进入临界区。实际的情况是，先作出“谦让”的进程先进入临界区，后作出“谦让”的进程则需要循环等待。
其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“你走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大进门。
# 28. 考查动态分区分配。
考生需对动态分区分配的四种算法加以理解。最佳适配算法是指：每次为作业分配内存空间时，总是找到能满足空间大小需要的最小的空闲分区给作业。可以产生最小的内存空闲分区。下图显示了这个过程的主存空间的变化：
图2010-28 最佳适配算法分配示意图
图中，灰色部分为分配出去的空间，白色部分为空闲区。这样，容易发现,此时主存中最大空闲分区的大小为9Mb。
# 29. 考查非连续分配的分页存储管理方式。
页大小为 $2^{10}$ 字节，页表项大小为 2 字节，采用二级页表，一页可存放 $2^{9}$ 个页表项，逻辑地址空间大小为 $2^{16}$ 页，要使表示整个逻辑地址空间的页目录表中包含的的个数最少，则需要 $2^{16} / 2^{9} = 2^{7} = 128$ 个页面保存页表项，即页目录表中包含的个数最少为 128。
# 30. 考查磁盘文件的大小性质。
因每个磁盘索引块和磁盘数据块大小均为256字节。所以4个直接地址索引指向的数据块大小为 $4\times 256$ 字节。2个一级间接索引共包括 $2\times (256\div 4)$ 个直接地址索引，既其指向的数据块大小为 $2\times (256\div 4)$ $\times 256$ 字节。1个二级间接地址索引所包含的直接地址索引数为 $(256\div 4)\times (256\div 4)$ ，即其所指向的数据块大小为 $(256\div 4)\times (256\div 4)\times 256$ 字节。即7个地址项所指向的数据块总大小为 $4\times 256 + 2\times (256\div 4)$ $\times 256 + (256\div 4)\times (256\div 4)\times 256 = 1082368$ 字节 $= 1057KB$
# 31. 考查当前目录的作用。
一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶为止，包括各中间节点名的全路径名。当前目录又称工作目录，进程对各个文件的访问都相对于当前目录进行，所以检索速度要快于检索全路径名。
# 32. 考查中断处理。
键盘是典型的通过中断I/O方式工作的外设，当用户输入信息时，计算机响应中断并通过中断处理程序获得输入信息。
# 33. 考查计算机网络体系结构的基本概念。
我们把计算机网络的各层及其协议的集合称为体系结构。因此A、B、D正确，而体系结构是抽象的，它不包括各层协议及功能的具体实现细节。
# 34. 考查存储转发机制。
由题设可知，分组携带的数据长度为980B，文件长度为980000B，需拆分为1000个分组，加上头
部后，每个分组大小为1000B，总共需要传送的数据量大小为1MB。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过2个分组交换机。
当 $t = 1M \times 8 / 100M$ bps = 80ms 时，H1 发送完最后一个 bit；
由于传输延时，当H1发完所有数据后，还有两个分组未到达目的地，其中最后一个分组，需经过2个分组交换机的转发，在两次转发完成后，所有分组均到达目的主机。每次转发的时间为 $t0 = 1K \times 8 / 100 \, \text{Mbps} = 0.08 \, \text{ms}$ 。
所以，在不考虑分组拆装时间和等待延时的情况下，当 $t = 80 \, \text{ms} + 2t0 = 80.16 \, \text{ms}$ 时，H2接收完文件，即所需的时间至少为 $80.16 \, \text{ms}$ 。
35. 考查 RIP 路由协议。
RIP 使用距离向量算法的工作过程参见内容精讲部分。
R1在收到信息并更新路由表后，若需要经过R2到达net1，则其跳数为17，由于距离为16表示不可达，因此R1不能经过R2到达net1，R2也不可能到达net1。B、C错误，D正确。而题目中并未给出R1向R2发送的信息，因此A也不正确。
36. 考查ICMP协议。
ICMP差错报告报文有5种，终点不可达、源点抑制、时间超过、参数问题、改变路由（重定向），其中源点抑制是当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道应当把数据报的发送速率放慢。
37. 考查子网划分与子网掩码、CIDR。
由于该网络的IP地址为192.168.5.0/24，因此其网络号为前24位。第25-32位为子网位+主机位。而子网掩码为255.255.255.248，其第25-32位的248用二进制表示为11111000，因此后8位中，前5位用于子网号，后3位用于主机号。
RFC 950 文档规定，对分类的 IPv4 地址进行子网划分时，子网号不能为全 1 或全 0。但随着无分类域间路由选择 CIDR 的广泛使用，现在全 1 和全 0 的子网号也可以使用了，但一定要谨慎使用，要弄清你的路由器所有的路由选择软件是否支持全 0 或全 1 的子网号这种用法。但不论是分类的 IPv4 地址还是无分类域间路由选择 CIDR，其子网中的主机号均不能为全 1 或全 0。因此该网络空间的最大子网个数为 $2^{5} = 32$ 个，每个子网内的最大可分配地址个数为 $2^{3} - 2 = 6$ 个。
38. 考查网络设备与网络风暴。
物理层设备中继器和集线器既不隔离冲突域也不隔离广播域；网桥可隔离冲突域，但不隔离广播域；网络层的路由器既隔离冲突域，也隔离广播域；VLAN即虚拟局域网也可隔离广播域。对于不隔离广播域的设备，他们互连的不同网络都属于同一个广播域，因此扩大了广播域的范围，更容易产生网络风暴。
39. 考查TCP流量控制与拥塞控制。
发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为 MIN{4000, 2000} = 2000 字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为 2000 - 1000 = 1000 字节。
40. 考查DNS系统域名解析过程。
当采用递归查询的方法解析域名时，如果主机所询问的本地域名服务器不知道被查询域名的 IP 地址，那么本地域名服务器就以 DNS 客户的身份，向其他根域名服务器继续发出查询请求报文，这种方法用户主机和本地域名服务器发送的域名请求条数均为 1 条。