实际吞吐率TP=7/（15Δt） η=32%
4. 计算多级立方体互连网络。 见图N=8多级立方体互连网络，求当输入端级控制信号为S2S1S0=010时，输入端为0 1 2 3 4 5 6 7时，输出端为： 23016745 。
0 0 1 A E I 1 2 2 B 3 F J 3 4 4 C 5 G K 5 6 6 7 D H L 7 s0 s1 s2 输入 输出
23
5. 由表达式：E= a +bx+cx+dx，利用减少树高的办法来加速运算，要求（1）画出树形流程图；（2）确定TP、P、SP、EP诸值
+
+ *
d
+ * *
a c x *
* *
11
b x x x x x
p=3 , TP =4, SP =3/2, EP =1/2
计算机系统结构试题 第一部分 选择题
一、单项选择题(每小题1分，共10分)在每小题的四个备答案中有一个正
确的答案，将正确答案的序号写在题干后的括号内) 1.计算机使用的语言是( )
A.专属软件范畴，与计算机体系结构无关 B.分属于计算机系统各个层次
C.属于用以建立一个用户的应用环境 D.属于符号化的机器指令
2.动态数据流机最突出的特点是使( ) A.数据流令牌无标号 B.需要程序记数器来实现 C.令牌带上标号
D.同步由门(Latch)寄存器来实现
3.多处理机上两个程序段之间若有先写后读的数据相关，则( ) A.可以并行执行 B.不可能并行
C.任何情况均可交换串行 D.必须并行执行
4.多处理机的各自独立型操作系统( ) A.要求管理程序不必是可再入的 B.适合于紧耦合多处理机 C.工作负荷较平衡 D.有较高的可靠性
5.输入输出系统硬件的功能对( )是透明的。 A.操作系统程序员 B.应用程序员
C.系统结构设计人员 D.机器语言程序设计员
12
6.“启动I/O”指令是主要的输入输出指令，是属于( ) A.目态指令 B.管态指令
C.目态、管态都能用的指令 D.编译程序只能用的指令 7.全相联地址映象是指( )
A.任何虚页都可装入主存中任何实页的位置 B.一个虚页只装进固定的主存实页位置
C.组之间是固定的，而组内任何虚页可以装入任何实页位置 D.组间可任意装入，组内是固定装入 8.( )属于MIMD系统结构。
A.各处理单元同时受同一个控制单元的管理
B.各处理单元同时接受同一个控制单元送来的指令 C.松耦合多处理机和多计算机 D.阵列处理机
9.设16个处理器编号分别为0，1，2，?，15用Cube3互联函数时，第10号处理机与第( )号处理机相联。
A.11 B.8 C.14 D.2
10.若输入流水线的指令既无局部性相关，也不存在全局性相关，则( ) A.可获得高的吞吐率和效率 B.流水线的效率和吞吐率恶化 C.出现瓶颈 D.可靠性提高
第二部分 非选择题
二、填空题(每空1分，共20分) 11.标志符与每个数据相连，合存于_______，用于描述单个数据的_______。 12.总线仲裁算法有：静态优先级算法、固定时间片算法、_______算法和_______算法。
13.计算机仿真用_______解释，计算机模拟用_______解释。
14.按弗林(Michael J.Flynn)的观点，计算机系统可分为单指令流单数据流、_______、多指令流单数据流和_______四大类。
15.要实现两条指令在时间上重叠解释，首先需要付出_______，其次，要处理好指令之间可能存在的_______。 16.与重叠机器一样，流水机器在遇到_______指令，尤其是_______指令时，效率也会显著下降。
17.超长指令字(VLIW)结构是将_______和_______两者相结合。
18.互连网络的交换方法主要有线路交换、包交换、线路/包交换，SIMD互
13
连网络多采用_______交换，多处理机常采用_______交换。
19.数据流机采用_______，执行的操作序列取决于输入数据的可用性；归约机则采用_______，执行的操作序列取决于对数据的要求，对数据的需求又来源于函数式程序设计语言对表达式的归纳。
20.输入输出系统包括输入输出设备、设备_______及与输入输出操作有关的_______件。
三、改错题(每小题2分，共10分)(下列每小题划线部分A、B、C中有一
处错误，请先写出错处，并在括号中写出正确文字)
21.对操作码进行优化编码时，在了解每种指令在程序中出现的概率后，使用Huffman算
A B 法构造Huffman树，这样获得的Huffman编码是唯一的。( ) C
22.多处理机中，两个程序段之间若同时有先写后读和先读后写2种相关，以交换数据为目的时，则必须并行执行，读写要完全同步，允许顺序串行和交换串行。( )
A B C 23.计算机仿真适合在两种结构差距大的机器间运用。( ) A B C
24.主存空间数相关是相间隔的两条指令之间出现对主存同一单元要求先写而后读的关联。
A B C
( )
25.由于Cache存贮器的地址变换和块替换算法是用软件实现的，因此Cache存贮器对应用
A
程序员是透明的，而且Cache对处理机和主存间的信息交往也是透明的。( )
B C 四、简答题(每小题6分，共30分) 26.简述标志符数据表示的主要优点。
27.简述设计RISC结构用了哪些基本技术?
28.设Pi和Pj程序段都是一条语句，且Pi在Pj之前执行，试举出Pi和Pj间存在3种可能的数据相关。
29.简述控制驱动的控制流方式的特点?
14
30.模拟与仿真的主要区别和适合场合是什么? 五、应用题(共30分)
31.(12分)假设某模型机共有7条指令，7条指令I1—I7使用的频度分别为：
0.35,0.25,0.20,0.10,0.04,0.03,0.03。 (1)利用Huffman算法，构造Huffman树，并给出Huffman编码和平均码长。
2)给出Huffman扩展码编码。 32.(10分)多级混洗交换网络是如何组成的？它与间接二进制n立方体网络有何差异?并画出N=8时的多级混洗交换网络图。
33.(8分)设向量A和B各有4个元素在下图所示的静态双功能流水线上计
算向量点积A·B=
?aibi，其中1→2→3→5组成加法流水线，1→4
i?14→5组成乘法流水线。若假定流水线的各段所经过的时间均为△t=2.5，流水线输出可直接送回输入或暂存于相应缓冲寄存器中，其延迟时间
和功能切换所需的时间都可忽略。求出吞吐率和加速比。
计算机系统结构试题参考答案
一、单项选择题(每小题1分，共10分)
1.B 2.C 3.B 4.D 5.B 6.B 7.A 8.C 9.D 10.A 二、填空题(每空1分，共20分) 11.同一存储单元 类型特征 12.动态优先级 先来先服务 13.微程序 机器语言
14.单指令流多数据流 多指令流多数据流 15.空间代价 关联 16.转移 条件转移
17.水平型微码 超标量处理 18.线路 包
19.数据驱动 需求驱动 20.控制器 软硬
三、改错题(每小题2分，共10分) 21.(C错 改为“不是唯一的”)
15