北京航空航天大学 2008 年
硕士研究生入学考试试题和巨代码 961
计算机专业综合 （共 6 页）
.,
考生注意：所有答题务必书写在考场提供的答题纸上，写在本试
题单的答题一律无效（本题单不参与阅卷）。
一、综合题（本题共 20 分，每小题各 4 分）
I. 请简要列出影响一个算法（或程序）时间效率的主要因素，并指出其中与算
法（或程序）本身直接有关的因素。
2. 若 5 个元素 A,B,C,D,E 按此先后次序进入一个初始为空的堆栈，请写出在所
有可能的出栈序列中，第一个元素为 C 、且第二个元素为 D 的出栈序列。
3. 已知长度为 12 的线性表(Nov,Dec,Jul,Feb,Oct,Sept,~ug,Apr,May,Jun,Jan,Mar),
请按照表中各数据元素的第一个字母在英文字母表中的先后顺序构造一棵二
叉排序树，然后求出在等概率情况下成功查找一个元素的 ASL 。
4. 证明：具有 n 个顶点的无向图最多有 nx(n-1)/2条边。
5. 有人说，采用折半查找法一定比采用顺序查找法的时间效率高，你认为如何？
请说明你的理由。
二、算法设计题（本题 1.0 分）
已知具有 n 个结点的非空完全二叉树采用顺序存储结构，结点的数据信息依
次存放于数组 BT[O ..n一 I] 中 3 请写出中序遍历该二叉树的非递归算法。
第 961- 1 页
三、算法设计题（本题 10 分）
直接插入排序法的基本思想是；对于参加排序的原始序列 (ko,1,ko,2, ?··,ko,n), 第
i 趟排序将序列的第 i+I 个元素插入到大小为 i 、且已经按值有序的子序列
(k凡1,k日，2, …，ki-1) 的合适位詈，得到一个大小为 i+l 、且仍然按值有序的子序列
(ki,1,k中... ,ki,i+l)' 其中， kij 表示第 i 趟排序结束时序列的第 j 个元素， l~i~~寸，
1 呴 ~n 。
已知一整数序列的各元素依次存放于无头结点的非循环双向链表的各链结点
的数据域中，链结点构造为
修改链结点数据域内容的动作。
j mnk -f data j西亚l 第一个链结点的指针为 list,
.
请写出直接插入排序算法。算法中不得使用任何新的链结点空间，也不允许出现
四、简答题（本题共 20 分，每小题各 4 分）
1. 数据传输控制方式有哪几种？
2. 在操作系统中为什么要引入线程？
3. 什么是文件系统？
4. 如何用 PN 操作实现进程互斥？
5. 什么是死锁？产生的原因是什么？
五、判断题（本题共 10 分，每小题各 1 分，请答 YIN)
l. 一级目录无法解决文件重名的问题，因此引入了二级目录。（）
2. 由于最优算法 (OPT) 造成缺页率最小，是非常实用的存储管理算法。() 3. 预防死锁的发生可以通过破坏产生死锁的四个必要条件之一来实现。() 4. 在有虚拟存储器的系统中，可以运行比主存容量还大的程序。（）
5. 进程被创建后的初始状态为“就绪状态”。()
6. 仅当一个进程退出临界区以后，另一进程才能进入相应的临界区。（） 7. 在中断处理的整个过程中，必须屏蔽中断。() 8. 虚拟存储器的最大存储空间为内存容量与硬盘容提之和。（）
第 961-2 页
9. 对于分页存储管理下的内存地址访问，用户需知道页面大小以及访问的页
面号和页面内相对位移。()
10. 进程调度算法“轮转法”仅适用于分时系统。()
六、内存管理（本题共 10 分） 一个系统采用段页式存储方式，有 16 位虚地址空间，每个进程包含两个段，
并且一页大小为 i12 字节。段表和页表如题八图所示（所有的值为二进制，并且段
长以页为单位）。下列哪些二进制虚地址会产生缺段中断，或缺页中断？哪些二进 制虚地址能转换为物理地址？如果可以转换，请写出物理地址。
1) 00010100 01010ll 1 2) II 100100 11111111 3) 11110100 11000 I 11 4) 00110010 11000111
(提示：产生缺段中断，或缺页中断？） (提示：转换后的物理地址是什么？） (提示：产生缺段中断，或缺页中断） (提示：转换后的物理地址是什么？）
5) 请问该系统最大物理内存是多少？
段表 页表 1 页号
I
i
巳i I 、111 i 指向页表 1
O
存储块
状态
．
0 的指针！
l
l
000 001 010 ?, 011 100 101 110 111
010100 110101 110100 011001 110011 001001 000101 100010
I
。
~I
l
。
I
1 I
I
七、简答题（本题共 16 分，每小题各 4 分）
l. 利用等值演算，给出命题逻辑公式主范式的求法。
2. 说明谓词逻辑中永假式、可满足式、重言式、永真式四个概念之间的关系。
3. 指出公式 'ixA 、玉A 与 A 的真值之间的联系。
第 961-3 页
4. 给出谓词逻辑公式中自出变元与约束变记的判别方法，并举例说明：一个
变元在一个公式中可以同时是自由的和约束的。
八、（本题共 14 分，第 1 小题 6 分，第 2 小题 8 分）
判断以下式子是否成立，并用两种不同的方法证明所给出的判断。
1. -,pvq,r 今 -,q 卜-,(p . ~ -ir) , 其中 p, q~r 是命题变元。
2. Vx(P(x) 分 Q(x)), \/x(Q(x)~R(x)) 户tx(P(x)~R(x)) , 其中 x 是变元，
P,Q,R 是一元谓词符号。
九、填空题（本题共 10 分，每空各 1 分）
1.
冯 蠡 诺依曼机是出＿＿尘
瑜出设备五大部件组成。
盆
、
@
以及输入设备、
2.
在链式查询、计数器定时查询 、 独立请求三种常见的集中式总线仲裁方式
中，
@
方式响应速度最快；＿且立＿方式对电路故障最敏感。
3.
在程序查询、程序中断、 DMA 三种常用的 I/0 控制方式中，
要求主存与 I/0 之间有直接数据通路；
于串行工作状态。
4. 在指令执行阶段，立即数寻址方式和寄存器直接寻址方式因操作数而需访
、
@
一方式
@
方式使 CPU 和 I/0 设备处
问内存的次数分别是
@
和
@
。
徇 原理。
5. 计算机存储器的层次化结构设计主要依据
十、简答题（本题共 10 分，第 1 小题 3 分，第 2 小题 7 分）
1.
假设：某 8 位机的地址码为 16 位，主存按字节编址，其中最高 8KB 主存
空间为系统 BIOS 程序区，其余为用户程序区。现有 4KX4 的 ROM 芯片
和 8KX4 的 ~RAM 芯片。问：该机所允许的最大主存空间是多少？构建
该机所允许的最大空间的主存，需用上述规格的 ROM 芯片和 SRAM 芯片
各多少？
第 961-4 页
?
才
2.
它
假设：呆机主存容枷为 2M 字节， CACHE 容最为 8K 字节，采用 2 路组相
联结构，每个数狩块大小为 128 字节 J 问：
(1) CACHE 共分为多少组？每组有多少个数据块？
(2) 主存共分为多少组？每组有多少个数据块?·
(3) 主存地址的格式（各字段名称及其位数）是什么？
(4) CACHE 中每个数据块对应的 Tag 至少应该有多少位？ (5) CACHE 中 Tag 的内容应该来自主存地址中的哪个字段？
十一、设计题（本题 10 分） 某机字长为 16 位，数据总线也为 ]6 位，内存容匮 64KB, 包含 8 个 16 位通
用寄存器 RO-R7 。指令系统基本要求是：
}-
128 条双操作数指令，且其中必有一操作数是寄存器直接寻址。 另一操作数的寻址方式有 4 种：立即寻址，寄存器直接寻址，寄存器间接
寻址，变址寻址。立即数和变址寻址时的位移量为 16 位。
> >
指令长度应满足 16 的倍数，且要求尽量短。
I
(1) 列出通常在指令系统格式设计过程中应考虑的主要因素。 (4 分）
(2) 给出该机指令系统的设计方案（提示：画出指令格式图，说明指令各字
段的位数和含义）。 (6 分）
十二、分析题（本题 10 分）
某计算机结构如题十二图所示，该机字长 16 位，图中所有寄存器均为 16 位，
控制器采用同步控制方式，每个机器周期包括 4 个节拍周期，数据总线及内总线
均为 16 位，存储器周期与 CPU 节拍周期时间相等。减法指令 SUB
RO, (Rl)
中，源操作数 (Rl) 为寄存器间接寻址，目的操作数 RO 为寄存器直接寻址，指令 编码长度 16 位。请给出该指令执行过程的微操作序列和时序安排，并详细列出每 个节拍周期对应处于有效状态的控制信号。
第 961-5 页
Control Bus Data Bus Addr~ss Bus
-CPMAR
RDGR
际GR
GRAd<l
题十 二 团
第 961 - 6 页
.
,
`
身
J
北京航空航天大学 2007 年
硕士研究生入学考试试题
计算机专业综合
（共 5 页）
科目代码： 461
考生注意：所有答题务必书写在考场提供的答题纸上，写在本试
题单的答题一律无效（本题单不参与阅卷）。
一、
（本题共 14 分，第 1 、 2 、 3 小题各 3 分，第 4 小题 5 分）
l. 设 a,b,c 三个元素的进栈次序是 a,b,c, 符号 PUSH 与 POP 分别表示对堆栈
进行一次进栈操作与一次出栈操作。
(1) 请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列；
(2) 指出不可能出现的出栈序列。
2. 对于一个有向图，除了进行拓扑排序，还可以采用什么方法判断图中是否
存在回路？请简述判断原则。
3. 请画出在下列 3 阶 B-树中插入关键字 64 以后的 B-树的状态。
r 一 .
55
. ..
...
4. 在长度为 n 的线性表中进行顺序查找。查找第 i 个数据元素的报率为 Pi,
且分布如下：
p1= - , p2= - , ??. , p兀 1=--;.i- ,
2
1 2
1 4
l
Pn= 一一
1 2n
请求出在该线性表中查找成功的平均查找长度（要求写成关千 n 的简单表达 式形式）。
第 461-1 页
二、（本题 6 分）
请 写 一非递 归算法，该算法在按值严格递增排 列 的顺序 表 A[l..n) 中 采用 折 半 查
找法查找值不小于 item 的最小元素。若表中存在这样的元素，则算法给出该最小 元素在表中的位置，否则，给出信息 0 。
三、（本题 10 分）
已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组
BT[O.. n-1] 中（假设每个结点的数据信息为一个非 0 整数；若数组元素值为 0, 则表
＿ 示该元素对应的结点在二叉树中不存在）。请写一算法，生成该二叉树的二叉链表
结构。
四、（本题共 15 分，第 1 小题 6 分，第 2 小题 9 分）
1. 假设 A 是命题逻辑中的任意公式。证明：存在一个合取范式 B, 使得 A!-B
且 B 1-A 。
2.
假设 A 是谓词逻辑中的公式， 1 是一个解释。假设 V1' 为是 1 的两个赋
值。： 考虑以下两个性质：
(1)
对于 A 中的每个自由变元 X' 都有 VJ (x) = vi (x) 。
A 在 I, V1 之下的真值等于 A 在 I, v2 之下的真值。
VJ,
(2)
构造 A , f,
V2 使得 (1) 不成立而 (2) 成立。判断当 (1) 成立时 (2) 是
否成立，并证明所给出的判断。
五、（本题 10 分）
假设 x 是变元符号， P,Q 是一元谓词符号，判断以下公式是否永真：
3x (P(x) AQ(x))~(3xP(x) A 3xQ(x)).
试分别使用解释赋值方法、公理化方法和归结方法证明所给出的判断。
第 461-2 页
六、简答题（本题共 15 分，每小题各 3 分）
-
,.、
1. 什么是 PCB, 它的三个主要组成部分是什么？
2. 进程与线程最根本的差别是什么？
（少千 15 个字，超出扣分）
3; - 在分区式存储管理中，什么是“地址重新定位”？动态与静态重新定位的 区别是什么？
4. 哪—种 RAID 保存两份数据? RAID4 与 RAIDS 的区别是什么？
5. 什么是 FCB., 它的三个主要组成部分是什么？
七、判断题（本题共 6 分，每小题各 1 分，请答 Y/N)
1. 实时操作系统必须比一般操作系统的速度快。
() ()
2. 分布式操作系统的可靠性要求比单机操作系统的高。
3. 中断是由 CPU 发出的。
() () ()
4. 缓存 (CACHE) 一定能提高速度。
5. 段页式存储管理可以用于虚拟存储器的管理。
6. 死锁是不可避免的。
八、（本题 9 分）
()
假设有 6 个作业正在等待运行，它们所需的运行时间分别是： 10, 8, 6, 4,
2 和 X 。不考虑并行、基于 X 、在追求最小平均相应时间 (Minimal average response time) 的前提下，请给出它们的运行顺序。（提示：共有六种顺序，先确定运行方法） 九、填空题（本题共 10 分，每空各 1 分）
l. 运算器的核心是
(i2
。
2. 常见的集中式总线判优控制方式有
＠—、
@
和——＠
@
三种。
3. CPU 响应中断时需要保护程序断点，这里断点指的是
一般被保存到~@—_中。
的内容，它
4.
浮点数加减法的基本运算过程是
@ @
、
@
寄存器。
和
@
。
5. 条件转移指令所依据的条件来自
第 461-3 页
十、 （ 本题共 20 分，第 1 小题 5 分，第 2 小题 10 分，第 3 题 5 分）
1.
用 16KX8 的 SRAM 芯片组成 64KX 16 的存储器，该存储器按 16 位字编
址，画出存储器扩展图? (5 分）
2.
某 8 位计算机主存容量 32K 字节，组相联 Cache 容量 2K 字节，每组 4 Blocks,
每 Block 64 个字节。假设 Cache 开始是空的， CPU 从主存存储单元 0 开始 顺序读取 2176 个字节数据（即按地址 O、 1 、 2 的顺序一直读取到地址单元
2175), 然后再重复这样的读数过程 7 遍（共 8 遍）， Cache 速度是主存速
度的 10 倍，采用 LRU 替换算法，假定块替换的时间忽略不计，计算采用
Cache 后的加速比。 (IO 分）
3. 某机字长为 16 位，采用定长指令格式，指令长度为 16 位，包含 32 条双地
址指令、 6~ 条单地址指令和 4 条无操作数指令；每个地址字段占 5 位，请 给出该机指令系统的操作码设计方案。 (5 分）
十一、（本题 10 分）
画出彶程序控制器的基本组成框图，说明其中各个部件的作用，并结合所画
框图，简要说明微程序控制器的基本工作原理。
十二、单项选择题（本题共 6 分，每小题各 1 分）
I. 一个信道每 1/8 秒采样一次，传输信号共有 16 种变化状态， 1 最大数据传输
率是（ ）。
A、 16bps
A 、交换器
B、 32bps
B 、网桥
C、 48bps
C 、集线器
·.
)。
D、 64bps
D 、路由器
2. 下列设备中，可能只具有一个冲突域的是(
3. 下列哪种说法是错误的？
(
)
A 、 1P 层可以屏蔽各个物理网络的差异
B 、 IP 层可以代替各个物理网络的数据链路层工作
C、 IP 层可以屏蔽各个物理网络的实现细节
D 、 IP 层可以为用户提供通用的服务
第 461-4 页
4. 在通常情况下，以太网交换机中的端口 /MAC 地址映射表(
A、是由交换机的生产厂商建立的
)。
B、是交换机在数据转发过程中通过学习动态建立的
C 、是由网络管理员建立的
·
D、是由网络用户利用特殊的命令建立的
5. IEEE802.3 采用的介质访问控制方法为（
A、 1-坚持算法的 CSM凶CD
C、 P埋坚持算法的 CSM幻CD
）。
B 、非坚持算法的 CSMA/CD D 、以上均不对
6. 采用 Go-Back-N 滑动窗口协议（顺序接收的滑动窗口协议），设序号位数为
n, 则发送窗口最大尺寸为(
A、 2~-1 B 、 2n·l
)
C 、 2n-l
D 、 2n
十三、（本题共 19 分，第 1 小题 6 分，第 2 小题 5 分，第 3 小题 8 分）
i.
A、 B 是位千同一局域网中的两台主机，使用 TCP/IP 协议进行通信。已知
主机 B 的 P 地址，主机 A 如何得知主机 B 的物理地址？
协议名称和协议的工作原理） (6 分）
（指出所使用的
2. 很多上层协议（如 TCP、 UDP 、 ICMP 等）都使用 IP 协议进行数据传输 3
当 IP 协议层收到一个完整的数据报后，它如何判断将其中的数据部分交给
哪一个上层协议 7· . (5 分）
3. 假设一台主机使用传统的 TCP 协议（用于标记字节的序号位为 32 位，报
文的生存时间为 120 秒）正在通过一条 lOGbps 的信递发送 65535 字节的满
窗口数据，该信道的往返延迟为 lms, 忽略各层协议对数据的处理时间。
请问：该 TCP 连接可达到的最大数据吞吐量是多少? (8 分）
第 461-5 页
, '、
仁、
·,
北京航空航天大学 2006 年 硕士研究生入学考试试题科目代码：
计算机专业技术基础 （共 7 页）
461
考生注意：所有答题务必书写在考场提供的答题纸上，写在本试
题单的答题一律无效（本题单不参与阅卷）。
表 一、填空题（本题共 10 分，每小题各 1 分）
I.
2.
删除长度为 n 的顺序表的第 i 个数据元之前需要移动表中＿＿＿个数据元
素。 (1 芍 ~n)
下面算法的功能是
·o
typedef struct node {
datatype data;
struct node *link; }*LinkList;
.,
.
void FUN(LinkList lista, LinkList listb) {
LinkL谅 p;
for(p=lista; P:>血k;p=p->link);
"'
今一
p->link=listb;
}
3. 若某堆栈初始为空， PUSH 与 POP 分别表示对堆栈进行一次进栈与出栈操
作，那么，对于输入序列 a,b,c,d,e, 经过 PUSH, PUSH., POP, PUSH,
POP'PUSH,
PUSH 以后，输出序列是
D
。
4. 5.
在具有 n 个元素的非空队列中插入一个元素或者删除一个元素的操作的时
间复杂度采用大O形式表示为
若一棵度为 7 的树中有 8 个度为 1 的结点，有 7 个度为 2 的结点，有 6 个 度为 3 的结点，有 5 个度为 4 的结点，有 4 个度为 5 的结点，有 3 个度为 6 的结点，有 2 个度为 7 的结点，则该树一共有＿＿＿个结点。
第 461-1 页
`
令，
6.
若某非空二叉树采用顺序存储结构，结点的数据信息依次存放于一个一维
数组中（假设数组的第一个元素的下标为 1)' 下标分别为 i 和 j 的两个结
点处在树中同一层的条件是 7. 。 (i =;t=j =r=-1)
若具有 n 个顶点的无向连通图采用邻接矩阵表示，则该邻接矩阵中至少
有＿＿＿个非零元素。
8.
在一个按值有序排列的顺序表中进行折半查找，其查找过程可以界一棵称
之为“判定树”的二叉树来描述。若顺序表的长度为 19, 则对应的“判
定树”的根结点的左孩子之值（元素在表中的位置）是
9.
,
0
设已知 n 个关键字具有相同的散列函数值，并且采用线性探测再散列方
法处理冲突，将这 n 个关键字散列到初始为空的地址空间中，一共发生
了＿＿＿次散列冲突。
10. 按照大顶堆积的定义，对序列 (26,5 ,77,1,61,l l,59, 15,48~19) 进行堆积排序，
第二趟排序结束时序列的状态是_o
?.
.、方＆
二、（本题 10 分）
假设长度为 n 的顺序表 A 中每一个数据元素均为整型数据，请写出在该顺序
表中采用顺序查找法查找值为 item 的数据元素的递归算法。若查找成功，算法返
回 item 在表中的位置，否则，返回信息-1 。（写成非递归算法不得分）
三、（本题 10 分） 选择排序法每一趟排序的基本原理是从当前未排好序的那些元素中选择一个
值最小的元素，将其与未排好序的那些元素的第一个元素交换位置。根据这个原
理，请写出对一个带有头结点的单链表按数据域值从小到大进行选择排序的算法。 约定：链结点构造为 I data link 每一个链结点的数据域中存放一个整型数，
I I,
但头结点数据域中不存放任何信息；设头结点指针为 I谅。
限制 ： 排序过程中不得申请任何链结点空间，也不得改变任何链结点的数据 域内容。
第 461 一 2 页
..
四、（本题共 17 分，第 1 小题 8 分，第 2 小题 9 分）
I. 写出 {EB,~, 今， A, V, -,}的 6 个极小完全集，并证明其中一个集的极小
完全性。
2. 用解释赋值方法、公理系统方法和归结方法三种方法证明以下公式是永真
的：
"if x(A 分 B)-4-(王认 ~3还）。
..
、
均，委岁.. "·
';..
．才又从
五、（本题共 8 分）
对于一般公式 A, 指出当变元 x 和项 t 与公式 A 之间满足什么关系时，公式
沁又仁响式是永真的，并证明相应的结论。用例子说明当所给出的条件不满足时，
上述公式可能不永真。
六、简答题（本题共 15 分，每小题各 3 分）
1.
进程的基本构成部分是什么？什么是线程？线程与进程最根本的区别是什
么？
2. 给出 3 状态的基本进程状态图，给出 5 状态进程的状态名称。
3. 产生死锁的基本原因是什么？产生死锁的必要条件是什么？
4.
存储管理系统的主要功能是什么？
5. 输入输出设备分为儿类？请举例说明。
七、判断题（本题共 7 分，每小题各 1 分，清答 YIN)
1.
在进程退出后，它的线程还可以继续占有内存。（
) )
2. 在存储管理中，可变式分区方法比固定式分区方法速度快。(
3. 无论用什么输入输出方法，申请 CPU 中断是必须的。(
)
4. 虚拟文件系统就是网络文件系统。
(
) ) ( )
5.
交换 (SWAP) 是由存储管理系统完成的。（
6. 输入输出的缓冲器 (BUFFER) 是为了提高外设的速度。
7.
在中断机制中，中断都是可以被再中断的。
第 461-3 页
(
)
1··
'··~
八、（本题共 8 分） 有 5 个进程如下表。时间从 0 开始，单位为 1, 最高优先级为 0 。
进程
到达时间
。
优先级
所需运行时间
A
.
·.
、“
'
..
B C ·D
2
2 . 3
3
. 4
· 、-~6 -
. ·?
4
, 'i . ..心
。
E
·-
t :6
`
、..
... .
、，
．，飞 节 ·:神
.;.
·.: . , .' ., 屯气仁 ，今屯. ..
....
名 于5 干·
令
俨'
,: ..
,·
·片，
．
.
令
J , 哀 卞
y ．二＇
,
少． “
,”
贮
8
4
绘阳说明以下进程调度过程： (lCPU 系统，所有进程只使用 CPU)a
请使用时间为横向坐标轴，并请在图中标明每个进程的”等待”和“运行”
两种状态。
"":·
1.
2. 3.
先来先服务 (FCFS) 。
.
时间片=2 。
时间片==2 。
轮转调度 (Round·Robin)
优先级轮转法 (Priority Round-Robin)
4.
最短进程轮转法<. Shortest Process Next) 。
九、（本题共 18 分，第 1 小题 10 分，第 2 、 3 小题各 4 分）
1. 某机字长 16 位， CPU 内有 16 个 16 位的通用寄存器，假设指令字长 32 位，
指令系统共包括 32 条“寄存器一存储器”型双操作数指令，存储器型操作
数分存储器直接、存储器间接和基址寻址三种寻址方式，任意一个通用寄 存器可作为基址寄存器，基址寻址的位移量采用补码表示。
{ 1) 设计并画出指令格式，并说明各个字段的含义。 (6 分）
(2) 存储器直接寻址和基础寻址的寻址空间各是多少?
(4 分）
2.
简要说明独立请求总线优先权仲裁方式的工作过程。 (4 分）
造 256K 字节的存储器，应使用多少芯片? (4 分）
J. 16KX4 的 DRAM 芯片，内部刷新地址计数器应该是多少位？用该芯片构
第 461 一4 页
?
十、（本题共 10 分）
某机主存容量 1MB, 两路组相联方式（每组仅有两块）的 CACHE容量为 64KB,
每个数据块为 256 字节。 CPU 要顺序访问地址为 20124H, 58130H, 201F5H 和
381FOH 等 4 个内存字节单元。已知访问开始前 CACHE 第 1组（组地址为 I) 的
两数据块均已被占用（如题十图，图中 T?的内容为二进制）， CACHE采用 LRU 替换策略。
Tag
lf\11)()
.·,: . . . ;·, ~.:;,.
之．．守？
Set 1 BiockO
.
.、 .. ,.
｀星畸
.,
Block 1
题十图
1. CACHE 分多少组~- (2 分）
2.
3.
给出主存的地址格式 ， 说明各部分的位数与含义； ·(3 分） 上述 4个数中哪些数能直接从 CACHE 中读取？若能，说明实际访问的是
CACHE 中哪一组的哪个数据块的哪一个字节 C _,(3 分）
4. 4 个数访问结束时 Tag 内容如何变化。 (2 分）
十一、（本题共 1 2 分）
某机结构如题十一图所示，该机字长 16 位，图中所有寄存器均为 16 位，控
制器采用同步控制方式，每个 CPU 周期包括 4 个节拍周期，数据总线及内总线均
为 16 位，存储器周期与 CPU 节拍周期时间相等。加法指令 ADD
Rl, 1000HCR2)
源操作数 1000H (R2) 是基址寻址，目的操作数 Rl 是寄存器直接寻址， 夕 指令编码
长度 32 位，第 1 个 16 位包含了操作码、寻址方式和寄存器编号等指令核心部分，
第 2 个 16 位是基址寻址的位移量 1000H。请给出该指令执行过程的微操作序列和
时序安排，并详细列出每个节拍周期对应处于有效状态的控制信号G
第 461 一5 页
气
心
.. . . i·,
' , 1 1 ·` . I··1
Control Bus
I .f ..
，
i_
? . .. , ??
， .I-
J.j
,1,
.. . .
.
：一： ·一 ：＇ 一， ．一 · ··
r
,
..
?
.j
长：， 气 ', i
`
-.
`
“ ,
..
.
..
~
、
1
.
. '?? ? '.... ... ...... . . .
一
____
...... . .. . .
十二、单项选择题（本题共 6 分 ， 每小题各 1 分）
一 一一 一一 一 一一 ， ＇ 一，
一 一
i_'
|
题十一图
1.
采用 8 种相位，每种相位各有两种幅度的 QAM 调制方法，在 1200Baud 的
信号传输速率下能达到的数据传输速率为（ ）。
A. 2400bps B. 3600bps .
·c.
9600bps
D. 4800bps
2 . 不同的网络在物理层互连时要求( ) 。 A. 数据传输率和 链路协议都相同
、
`
B. 数据传输率相同，链路协议可以不同 C. 数据传输率可以不同 ， 链路协议必须相同 D. 数据传输率和链路协议都可以不同 3. 若数据链路的发送窗口 =4: 在已发送 3 号帧并收到 2 号帧的确认帧后，发
送方还可连续发送()。
A. I 帧
B. 2 帧
c.
3 帧
D. 4 帧
第 461-6 页
it
",
..
./ `'
....,,
4. 在 TCP/IP 协议簇的层次中，解决不同计算机进程之间通信问题是在（）。
A. 网络接口层 B. 网络层
c.
传输层
D. 应用层
5. 一个 IP 地址段 200.100.50.0/24, 子网掩码固定为 255 .25 5:25-S .224, 最多可
以分成多少个子网，子网内最多具有多少个有效 IP 地址。()
.
· ·A. 8, 30
B. 4,62
C. 16, 14
. ·D. 32, 6
()
＄要控制网络上的广播风暴，可以采用哪种手段？
A. 用路由器将网络分段
.
·B. 用网桥将网络分段 D. 用集线器将网络分段
c.
用交换机将网络分段
十三、（本题共 19 分，第 1 、 3、 4 小题各 5 分，第 2 小题 4 分）
I. UDP 和 TCP 在递交信息时，都使用端口号来标识目标实体（进程）。请给
出两个理由说明为什么这两个协议都使用端口号而不直接使用进程号进行
通信。 (5 分）
2.
请给出某种操作系统下查看本机 IP 地址及子网掩码的两种方法（操作系统
不限）。 (4 分）
3.
简述 traceroute (UNIX 环境）或 tracert (Wmdows 环境）的实现原理。 (5
分）
4. 假设一个数据链路软件采用 3 比特序号，发送窗口大小为 7, 那么最大接
. i2
收窗口为多少？为什么? (5 分）
第 461 一7 页
`.
`
您现在的位置：首页 > >