2000年春博题目(是99年秋天考的)。 +ANIm^@
\uIC<#o"N
计算理论 `g1~ya(MC
一、1、根据图灵机理论,说明现代计算机系统的理论基础。 zXPj7K*
2、说明按乔姆斯基分类,语言、文法、自动机的关系 5E(P,!-.
1k({(\>qq
一、 证明 HALT(X ` 1,X)不是可计算的。 [6qP;
N Uml"
三、1、证明递归集都是递归可枚举集。 +'
4 dP#
2、举例属于递归可枚举集但不是递归集的集合,并证明之。 j"=jK
^
bv];Gk*Z-
四、1、证明L={(a,b)*|a,b的个数相同}为上下文无关语言。 d7gSkna`5c
2、并证明其不是正则的。
bJ}+<##
hY9u
#3
8R D)
yRJ
2000年4月 >GRuS\B
人工智能 K.zs;^
1 什么是知识表示?用框架系统表示你的卧室。 KgSxF#
2 描述A算法(描述A*) bm?TMhC
3 专家系统模型?建立知识库(书上关于鸟类的例子)。
o`0H(\en
专家系统的模型。根据下述事实建立分类专家系统的知识库。见书上哺乳动物、鸟类的分类系统例子。 dj]N59<
4 什么是自然语言的理解?写出下列句子的句法分析树。 xb>+~5 9:
1)I WANTED YOU TO DO SOMTHING. Rw%KEUDm
2) I SAW SOME CHILDREN PLAYING BALL IN THE FIELD. Ca|;8ggf
2000年10月 tBQ>
p.
操作系统 WKML#U]5T
1 产生死锁的必要条件。 LOzKpvGl
2 写出生产者和消费者的互斥程序(书上的例子)。 .m51/X&*n
3 写出可对文件和目录进行的操作。 $!w%=
虚拟存储页面置换的几种算法。 @su,w,xLS
6 [E"
计算理论 +=4b5*+qG
1、 "Q4{6FH+mB
(1)给出图灵机的格局、计算及图灵机μ计算函数f的精确定义。 {lJpcS
(2 ) 对图灵机模型而言,church论题是什么? 471}'3
(3)当x是完全平方时值为3x,否则为3x+1证明其是原始递归函数。 cB^lSmu5
l:HuG!
2、证明φ(X,X)是不可计算的。 jT',+
ipG+qj/=
3、证明L={ambn|m,n>0,m≠n}是上下文无关的,但不是正则的。 .+sIjd
fJKOuFK
4、A为有穷字母表,L是A*的无穷子集, 9"TPDU7"
(1) 证明存在无穷序列ω0,ω1,ω2…,它由L的所有字组成,每个字恰好在其中只出现一次。 W#7c`nm
(2) 是否存在从L构造序列ω0,ω1,ω2…,的算法(即i由计算ωi),为什么? ;C'*Ui
bql6Z1l
人工智能 C4,W[L]4"
1 试构造一个描述你的办公室的语义网络表示系统。 vr$[
ko$R%W&T
2 何谓人工智能中的搜索问题?试采用宽度搜索方法解决机器人JACK搬运积木问题。 -L@=j
(初态:积木B、C放在桌上,积木A放在B上面 N{0 D <"
目标态:积木C放在桌上,B在C上面,A在B上面) :M16ijkx
?FyA2q!
3、描述基于规则的的系统结构?采用IF-THEN 规则形式,写出产生式系统的规则知识库。(书上关于哺乳动物的例子) ,O(uuq
L`
6`NYR
体系结构 utv.uwfat
1 CPU响应时间计算公式,列举可减少响应时间的相关技术。 eo!{rs@f
2 两种多发射技术的特点和异同。 PYGHN
T
3 关于循环体的相关性分析(书后习题)。 HXX"B,N
4 一段循环指令的循环展开及软件流水的实现(书中例子)。 rnUe/HjH
5 两种监听协议的性能差异。 }I"^WCyH
kq+L63fZ
2001。10月计算机考博专业课试题 hz!.|U@,{<
计算理论: Q =Z-vTD+
1。{a,b}上递归枚举语言是否可数?证明。 :7gIm|2"]
2。L={a,b,c数目相同的语言} 是否CFL.证明。 sqhM[u
k
3.被2,3整除的非负整数的十进制表示的集合是否正则。 o 0B`~7(
4。NonSelfAccepting 是否递归集合 \RJ428sxn
UWz<~Vy
#H|]F86 (
操作系统: #~"jo[
1。关于分页虚拟内存地址转换的题目。(20) kAMt8
2。为什么要引入“进程状态".画出进程状态转换图。(12) 0oD?4gn
3。通用操作系统可以用什么开发(选择题)(4) wNn6".S
a.汇编语言 b高级语言 c大部分高级语言与小部分用汇编语言 s<:J(gD
4.块设备和字符设备特点和区别(4) .M04n\
5。这道题目想不起来,呵呵(4) |X>:"
?4t
6.打开的文件,它的文件标识,保存在系统什么地方?为什么?(6) 8D-g%Aj-
uXXwMc<p
一、 非抢占式系统和抢占式操作系统的区别,实时OS为何要采用抢占式系统。 ]O^!P,l)"
BQsy)H`4E
二、按缺页率大小排列下述算法 8@ b8
3
1、LRU >Py=H+d!j
2、FIFO n<MH\.!tM
3、SECOND CHANCE HA| YLj?|g
4、OPTIMAL YDP<
6:Ra3!V"v
三、进程进入就绪队列后的等待时间+运行时间=周转时间,现有三个进程。 IL\#!|>
进程 t ;(kSg.
进入队列时间(s) {{j?3O //
执行时间(s) 2s~X
P1 0e&Vvl4DK
0 bUt?VR}P(
8 k \|Hd"T
P2 Pn0V{SJOJ%
0.4 ~nw]q<7r
4 D3$}S{Yw1
P3 M(xd:Fa?
1 XDU&Z2A
1 z>~Hc8*]3
1、对非抢占式系统,若采用最短任务优先,请计算三个进程的平均周转时间。 7Q2"]f,$CQ
2、若CPU空等1S后在执行进程,请计算三个进程的平均周转时间。 bmFnsqo
zxY
四、有三个作业对空间要求分别为250K,412K,523K,342K,现内存分区大小为200K, zGF_ c9X
300K,400K,500K,600K,若分别采用FIRST-FIT,BEST-FIT和WORST-FIT分配 ?J
io9Zr
结果如何 ? Gz@'W%6yaV
"*a^_tsT?i
五、若一个系统有4个同样的资源,可供三个进程共享,每个进程最多占用2个资源,根 gq!|0
据进程死锁的四个条件,说明此系统不会产生死锁。
hT]\*},
#}3$n/
六、某个操作系统共支持5000个用户,若通过对用户的权限和文件属性的控制来实现只 +Ccj@#M;
有其中4990个用户可以访问文件DEVLIST。可以采用两种控制策略,请比较其区别。 @Pb!:HeJE
f
0D9Mp
k%Jv%m}aB
高级计算机体系结构 1 :<f[l
1。CPUtime公式及其理解。如何减少CPUtime?(10) r&U