一、简答题(4’×5)
清泽论坛-太原理工大学网络家园9 I# ]1 J, F2 L! L" Z7 j- N( g ?; B
1、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。
www.tyutbbs.com: l4 u' q! H- q. s7 D
2、已知元素的入栈顺序为A,B,C,D,E，在所有可能的出栈顺序中，写出第一个出栈的元素为C且第二个出栈的元素为D的所有组合。
太原理工大学,太原理工大学论坛# w! g/ _/ V& W) y3 K( r
3、根据单词(Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr)的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度ASL。
, G* ~; l3 z3 e; O- q' d% a s' j清泽论坛-太原理工大学网络家园 4、证明：具有n个顶点的无向图最多有 条边。
. J3 p" m$ Y6 s2 v5 T# z 5、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法?为什么?
www.tyutbbs.com$ F+ ~" I% u3 j7 s( y
二、算法设计题(10’)
& {0 P$ K6 N: G2 q, l6 C4 A. A太原理工大学,太原理工大学论坛 已知一非空完全二叉树存放于数组 中，请写出中序遍历该二叉树的非递归算法。
" [5 P F6 z5 O, ?1 ] S' B3 j6 R% d 三、算法设计题(10’)
* P4 ^" t$ i3 [+ u+ V
写出不带头结点的双向链表的插入排序算法。
' h( j* X7 k$ j& C# N5 ]太原理工大学,太原理工大学论坛 四、简答题(4’×5)
+ S, G4 l$ ]7 O清泽论坛-太原理工大学网络家园 1、数据传输控制方式有哪些?
清泽论坛-太原理工大学网络家园+ U$ @: u; f! u1 X3 z% G
2、引入线程的目的是什么?
) R0 x5 R- E7 Z& @7 K太原理工大学|太原理工大学论坛|太原理工大学BBS 3、P, V操作是如何实现互斥的的?
" C8 ^) I( V) O: E7 i太原理工大学,太原理工大学论坛 4、什么是死锁?产生死锁的原因是什么?
太原理工大学论坛[龙城水秀]; C. N/ m4 A; ?# p
5、什么是文件系统?
r. n6 Z3 {$ t+ d& Hwww.tyutbbs.com 五、判断题(1’×10)
: v9 D5 i3 Z7 y2 i
略。(基本上来自于历年真题)
www.tyutbbs.com5 J4 J3 ]2 C$ ]- p7 N
六、解答题(10’)
www.tyutbbs.com9 Y2 X: I I. W m: {( U6 @4 }+ W2 {
某机器字长为16位，采用段页式存储管理算法，页内偏移为12位，段表和页表内容如下，给出4个虚拟地址(二进制形式)，问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。(地址格式中段号占1位，段内页号占3位，页内偏移为12位，另外，在给出的页表中，物理块号占6位，最后又问该机器的最大物理内存是多少(答案：256 KB)。)
www.tyutbbs.com! k' J6 |5 i+ k' m: G1 |3 K, }/ |
七、简答题(4’×4)
$ w: C8 O6 i5 a; h1 v. r; {1 t太原理工大学|太原理工大学论坛|太原理工大学BBS 1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。
太原理工大学,太原理工大学论坛% o; G3 Q8 |# l8 n$ R
2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么?
; @. k0 D& G* o) U- x, H5 t 3、 之间的真值关系是什么?
7 [! |& g$ T/ L1 {) p) _
4、如何判断公式中某个变元是约束变元还是自由变元?举例说明一个变元可以既是约束的又是自由的。
太原理工大学|太原理工大学论坛|太原理工大学BBS0 b2 ^+ s. Q! U; |% {
八、判断下列结论是否成立，并至少用两种方法证明你的判断(6’ + 8’)
& U9 v Q3 C9 G太原理工大学,太原理工大学论坛 1、
清泽论坛-太原理工大学网络家园2 W; e& s! q% y* f* J* c% w
2、
清泽论坛-太原理工大学网络家园! ` M6 h* ? K
九、填空题(1’×8)
太原理工大学|太原理工大学论坛|太原理工大学BBS( I0 w, E Q* \& X# p
1、冯•诺依曼计算机体系包括存储器、运算器、控制器和输入输出设备。
太原理工大学论坛[龙城水秀]0 n$ r0 P) Y/ s" k! i
2、在总线同步控制方式种，哪一种速度最快，哪一种对电路故障最敏感?
太原理工大学|太原理工大学论坛|太原理工大学BBS) \' |, t; ^) _# [! |5 R& `. F- S
3、在程序查询方式、程序中断方式和DMA方式中，哪一种方式主存与设备间有数据通路，哪一种方式使CPU与外设串行化?
太原理工大学,太原理工大学论坛; |& b2 d t0 k1 S# q" i7 k7 s5 Q
4、指令中的操作数分别为立即寻址和寄存器直接寻址时CPU访问主存的次数分别为多少次?
太原理工大学,太原理工大学论坛0 ]: m+ ?6 |5 I
5、存储器分层体系是根据程序访问的局部性原理提出的。
- \ j2 v- ?; ^+ R1 Q. D* E太原理工大学|太原理工大学论坛|太原理工大学BBS 十、存储器扩展的题(6’)
& \0 n: T6 R( L 某机器字长为16位，最大物理内存为64 KB，最低地址的8 KB存放BIOS程序，其他空间存放用户程序，现有4K×4的ROM和4K×4的SRAM，问各需要多少片?
! u8 n" W7 a: P# T* c) Z清泽论坛-太原理工大学网络家园 十一、Cache题(8’)
太原理工大学|太原理工大学论坛|太原理工大学BBS) e, t9 g- N; F3 t3 R
主存大小为2 MB，Cache大小为8 KB，采用2路组相联方式，每个Cache块大小为128字节。
太原理工大学|太原理工大学论坛|太原理工大学BBS6 S, W$ M; r x, o& ?/ z
(1)求主存地址格式及各字段的位数和含义
; b& H+ I) x2 g2 u/ d
(2)Cache的格式
太原理工大学,太原理工大学论坛7 ^7 j7 c" }% n/ R
(3)Cache的Tag需多少位?
太原理工大学论坛[龙城水秀]# U" @, P! m+ P* i9 {- ?
十二、指令系统的设计(8’)
5 ]& @; O7 t/ }+ x太原理工大学,太原理工大学论坛 某机器字长为16位，有8个16位的通用寄存器，请设计一指令系统，要求：
/ p& B" Z# b3 |$ \. i清泽论坛-太原理工大学网络家园 (1)共有128条双操作数指令，且必有一操作数为寄存器直接寻址，另一个操作数有4种寻址方式，可以是立即寻址、寄存器直接寻址、寄存器间接寻址或变址寻址，其中立即寻址和变址寻址的偏移量均为16位;
' M! x2 r% W5 y: c/ z$ G清泽论坛-太原理工大学网络家园 (2)指令所占的位数必须是16的倍数且要尽可能地短。
www.tyutbbs.com& a5 ?, h) [6 u
要求：
+ Q+ e, D- ~/ ]# ?* ~* X
(1)写出影响指令系统设计的因素;
太原理工大学|太原理工大学论坛|太原理工大学BBS% G/ k6 [$ Y- e: Z9 ^
(2)设计该机器的指令系统，写出各字段的位数和含义。
www.tyutbbs.com) |7 P3 e6 }; ?
十三、微程序设计题(10’)
4 R% P! E6 T' }3 e1 a' q太原理工大学论坛[龙城水秀] 指令为SUB R0, (R1)，其中R0为目的操作数，采用寄存器直接寻址，R1为源操作数，寻址方式为寄存器间接寻址，每个机器周期包含4个节拍周期，写出该指令执行的详细微操作流程和对应处于有效状态的控制信号。
清泽论坛-太原理工大学网络家园! Z( C9 N! C" }* l
海文专业课
http://www.VIPkaoyan.com/
