标题:
2008年北航计算机专业基础真题
[打印本页]
作者:
松花江里的鱼
时间:
2008-8-22 14:24
标题:
2008年北航计算机专业基础真题
2008
年北航计算机专业基础真题
2008
计算机专业基础
一、简答题
(4
’×
5)
1
、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。
2
、已知元素的入栈顺序为
A,B,C,D,E
，在所有可能的出栈顺序中，写出第一个出栈的元素为
C
且第二个出栈的元素为
D
的所有组合。
3
、根据单词
(Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr)
的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度
ASL
。
4
、证明：具有
n
个顶点的无向图最多有
条边。
5
、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法
?
为什么
?
二、算法设计题
(10
’
)
已知一非空完全二叉树存放于数组
中，请写出中序遍历该二叉树的非递归算法。
三、算法设计题
(10
’
)
写出不带头结点的双向链表的插入排序算法。
四、简答题
(4
’×
5)
1
、数据传输控制方式有哪些
?
2
、引入线程的目的是什么
?
3
、
P, V
操作是如何实现互斥的的
?
4
、什么是死锁
?
产生死锁的原因是什么
?
5
、什么是文件系统
?
五、判断题
(1
’×
10)
略。
(
基本上来自于历年真题
)
六、解答题
(10
’
)
某机器字长为
16
位，采用段页式存储管理算法，页内偏移为
12
位，段表和页表内容如下，给出
4
个虚拟地址
(
二进制形式
)
，问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。
(
地址格式中段号占
1
位，段内页号占
3
位，页内偏移为
12
位，另外，在给出的页表中，物理块号占
6
位，最后又问该机器的最大物理内存是多少
(
答案：
256 KB)
。
)
七、简答题
(4
’×
4)
1
、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。
2
、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么
?
3
、
之间的真值关系是什么
?
4
、如何判断公式中某个变元是约束变元还是自由变元
?
举例说明一个变元可以既是约束的又是自由的。
八、判断下列结论是否成立，并至少用两种方法证明你的判断
(6
’
+ 8
’
)
1
、
2
、
九、填空题
(1
’×
8)
1
、冯•诺依曼计算机体系包括存储器、运算器、控制器和输入输出设备。
2
、在总线同步控制方式种，哪一种速度最快，哪一种对电路故障最敏感
?
3
、在程序查询方式、程序中断方式和
DMA
方式中，哪一种方式主存与设备间有数据通路，哪一种方式使
CPU
与外设串行化
?
4
、指令中的操作数分别为立即寻址和寄存器直接寻址时
CPU
访问主存的次数分别为多少次
?
5
、存储器分层体系是根据程序访问的局部性原理提出的。
十、存储器扩展的题
(6
’
)
某机器字长为
16
位，最大物理内存为
64 KB
，最低地址的
8 KB
存放
BIOS
程序，其他空间存放用户程序，现有
4K
×
4
的
ROM
和
4K
×
4
的
SRAM
，问各需要多少片
?
十一、
Cache
题
(8
’
)
主存大小为
2 MB
，
Cache
大小为
8 KB
，采用
2
路组相联方式，每个
Cache
块大小为
128
字节。
(1)
求主存地址格式及各字段的位数和含义
(2)Cache
的格式
(3)Cache
的
Tag
需多少位
?
十二、指令系统的设计
(8
’
)
欢迎光临 工程家园 (http://heubbs.cn/)
Powered by Discuz! 7.2
