南京大学石头论坛
标题:
2008年北航计算机专业基础真题
[打印本页]
作者:
不那么
时间:
2008-8-22 13:18
标题:
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
’
)
某机器字长为
16
位,有
8
个
16
位的通用寄存器,请设计一指令系统,要求:
(1)
共有
128
条双操作数指令,且必有一操作数为寄存器直接寻址,另一个操作数有
4
种寻址方式,可以是立即寻址、寄存器直接寻址、寄存器间接寻址或变址寻址,其中立即寻址和变址寻址的偏移量均为
16
位
;
(2)
指令所占的位数必须是
16
的倍数且要尽可能地短。
要求:
(1)
写出影响指令系统设计的因素
;
(2)
设计该机器的指令系统,写出各字段的位数和含义。
十三、微程序设计题
(10
’
)
指令为
SUB R0, (R1)
,其中
R0
为目的操作数,采用寄存器直接寻址,
R1
为源操作数,寻址方式为寄存器间接寻址,每个机器周期包含
4
个节拍周期,写出该指令执行的详细微操作流程和对应处于有效状态的控制信号。
作者:
不那么
时间:
2008-8-22 13:19
hao ding ding ding
欢迎光临 南京大学石头论坛 (http://www.mynju.cn/)
Powered by Discuz! X3.3