| tangtangtoy |
2008-03-10 10:58 |
2000年春博题目（是99年秋天考的）。 Rgb EBw
Hr0isgw
计算理论 p! ;sq
一、1、根据图灵机理论,说明现代计算机系统的理论基础。 3}o|U"x4
2、说明按乔姆斯基分类，语言、文法、自动机的关系 j`G Z/F?:
Rv7q LXa
一、 证明 HALT(X ` 1,X)不是可计算的。 e|& eI"H
+<mai K6
三、1、证明递归集都是递归可枚举集。 F bNNIDK[`
2、举例属于递归可枚举集但不是递归集的集合，并证明之。 _m?W]n
|vP?Fuv
四、1、证明L={（a，b）*|a，b的个数相同}为上下文无关语言。 fDROC54
r
2、并证明其不是正则的。 K 0d_Mg)
OmEB_XbL
C
qi_8h6
2000年4月 % 0=dM^+m
人工智能 9lt^7[L9bP
1 什么是知识表示？用框架系统表示你的卧室。 U
C)_,
2 描述A算法(描述A*) yvG3rdX|
3 专家系统模型？建立知识库（书上关于鸟类的例子）。 >%'=zbN
专家系统的模型。根据下述事实建立分类专家系统的知识库。见书上哺乳动物、鸟类的分类系统例子。 /v#fY..m
4 什么是自然语言的理解？写出下列句子的句法分析树。 ZZZnL~
1）I WANTED YOU TO DO SOMTHING. txQ{Aqg k\
2) I SAW SOME CHILDREN PLAYING BALL IN THE FIELD. Gbl% r(U
2000年10月 A(\N8$V
操作系统 8ZW4%g{_
1 产生死锁的必要条件。 pPI EU AT
2 写出生产者和消费者的互斥程序（书上的例子）。 }_)u)hMuod
3 写出可对文件和目录进行的操作。 E)jDQ|O&
虚拟存储页面置换的几种算法。 #M{`2!r+
1 *Kfo?P#
计算理论 <ILgQ/c>:
1、 I h{dd,x
（1）给出图灵机的格局、计算及图灵机μ计算函数f的精确定义。 +L,._c
(2 ) 对图灵机模型而言，church论题是什么？ WI?oF K1
（3）当x是完全平方时值为3x，否则为3x+1证明其是原始递归函数。 LC =,6nnw
sRrp6o=b
2、证明φ（X，X）是不可计算的。 0/5_
hRo-4t1d
3、证明L={ambn|m,n>0,m≠n}是上下文无关的，但不是正则的。 "pb}dF$
I:mDO-94?{
4、A为有穷字母表，L是A*的无穷子集， # sI%rZ/"<
（1） 证明存在无穷序列ω0,ω1,ω2…，它由L的所有字组成，每个字恰好在其中只出现一次。 "R(( i:
（2） 是否存在从L构造序列ω0,ω1,ω2…,的算法（即i由计算ωi），为什么？ X+bT;*#2
&eWmJZ22;
人工智能 OWT(:zhX
1 试构造一个描述你的办公室的语义网络表示系统。 c~ r`1R
VZViW8W(Uc
2 何谓人工智能中的搜索问题？试采用宽度搜索方法解决机器人JACK搬运积木问题。 K 56!G>_
（初态：积木B、C放在桌上，积木A放在B上面 E+.LWD C
目标态：积木C放在桌上，B在C上面，A在B上面） CBJ' A\g
zK aZ^ k
3、描述基于规则的的系统结构？采用IF-THEN 规则形式，写出产生式系统的规则知识库。（书上关于哺乳动物的例子） }i; (P
_lwd Te8
体系结构 BrOS16E.w)
1 CPU响应时间计算公式，列举可减少响应时间的相关技术。 D"q r
%2 d
2 两种多发射技术的特点和异同。 eHCz`s}#k
3 关于循环体的相关性分析（书后习题）。 Utd_)P ~%
4 一段循环指令的循环展开及软件流水的实现（书中例子）。 B{"`" Wub
5 两种监听协议的性能差异。 :4%kG xfG`
{ao~A~
2001。10月计算机考博专业课试题 _ 0oJ* ,#
计算理论： bmR Ip,l
1。{a,b}上递归枚举语言是否可数？证明。 >wz.Dg9K
2。L={a,b,c数目相同的语言} 是否CFL.证明。 Yk Y 1BE
3.被2，3整除的非负整数的十进制表示的集合是否正则。 mTG+D e
4。NonSelfAccepting 是否递归集合 L 6K#sJwN
K0Znm_-M&9
`~,t.Qf
操作系统： J QMc
1。关于分页虚拟内存地址转换的题目。(20) 8{ywUQ8Xj[
2。为什么要引入“进程状态".画出进程状态转换图。(12) z!)gEQ,
3。通用操作系统可以用什么开发（选择题）(4) f g/fPtTP
a.汇编语言 b高级语言 c大部分高级语言与小部分用汇编语言 B } ]xh;|
4.块设备和字符设备特点和区别（4） ct*L (-:
5。这道题目想不起来,呵呵（4） {3JO_o{pb
6.打开的文件，它的文件标识，保存在系统什么地方？为什么？（6） 7ygieEa`C
^W *{% 5;
一、 非抢占式系统和抢占式操作系统的区别，实时OS为何要采用抢占式系统。 GKWwRz{L;=
XmMI.&F?
二、按缺页率大小排列下述算法 | T#\fYy"
1、LRU e9Rf8ikqb=
2、FIFO E *=[UK7
3、SECOND CHANCE
dvH{U
4、OPTIMAL ?/<eW KG
>3e4'6F
三、进程进入就绪队列后的等待时间+运行时间=周转时间，现有三个进程。 0U j"Ae<a
进程 zwRtR_Rn
进入队列时间（s） WuK
kh(h
执行时间（s） -MWK?/J
P1 `}CZ#8k?
0 /Qr?b~r %
8 gk8ks+,34
P2 i4zmz"V
0．4 ~ L1.5
4 fo~9I M5
P3 \Oq[K&[
1 CL2>DgpH
1 1Ty@RF]m.
1、对非抢占式系统，若采用最短任务优先，请计算三个进程的平均周转时间。 H 1}Y=oh]
2、若CPU空等1S后在执行进程，请计算三个进程的平均周转时间。 ,@9DGhy
uY,GvxzWM
四、有三个作业对空间要求分别为250K，412K，523K，342K，现内存分区大小为200K， Bdt|==J
300K，400K，500K，600K，若分别采用FIRST-FIT，BEST-FIT和WORST-FIT分配 # =@NAVq
结果如何 ？ N%]%:@#{
"L 21N*
五、若一个系统有4个同样的资源，可供三个进程共享，每个进程最多占用2个资源，根 zL.s9$RV
据进程死锁的四个条件，说明此系统不会产生死锁。 |9W,_F
Y7
530Uy?c
六、某个操作系统共支持5000个用户，若通过对用户的权限和文件属性的控制来实现只 r.;`c 'N
有其中4990个用户可以访问文件DEVLIST。可以采用两种控制策略，请比较其区别。 r yn`9J
|4BB#oB:k
gnyK;&U0
高级计算机体系结构 Rhy@|`m
1。CPUtime公式及其理解。如何减少CPUtime？(10) \J#I
G{IA
2。一段循环相关性分析。(10) IZ"X*^"~
3。DLX机器一段代码的数据竞争，结构竞争分析及其解决方法。(10) X/DS~
|DKl
4。并行处理的两个障碍是什么(10) kUSH:(0"
5。关于cache直接映射的实现细节题目。(10) -iy<S3
JiQ 1nX
一、1、写出三条计算机设计的定量定理 RBem.)
2、若CACHE速度比内存高十倍，若内存利用率是90%，请问系统的加速比为多少？ M\t86bW
9T,HuX
二、CPU的操作数有三中存储方式，是区别不同体系计算机的重要标志。 04xN&'0
1、是哪三种 3SBt~{_
2、对于C=A+B，请写出三种方式的实现程序。 !{P,^ r6
>UHV$sVJ:
三、1、流水线中结构、数据、控制竞争产生的原因 ulJZ 6t
2、写出有停顿周期的流水线系统的性能公司 _{YQI
*TY
?FCb96WB
四、1、什么是ILP [Y|w^55p
2、ILP的必要性和实现技术 ;fq4qjU{TZ
i/J1d,#lP
五、某cache容量为8KBYTES，块大小为32BYTES，字长为64BITS，地址长度为34BITS，对 于直接映象系统，请分别写出构成地址的索引（INDEX）、标志（TAG）和块地址的长度。说明并行计算面临的两大障碍 wv2yh&'
`Gr+ 4rE
*********************************** Q 8n& L}
注：操作系统每年的试题差别很大，但是虚拟内存好象都有的。 >^-/X2K3t
体系结构前面三道都也是必考的题目。 Yqh/gFU
括号内是分值。 P1'Br~\g
zn[{&?fo
zga 6"_
人工智能： v/!yfTb
1。语义网络表示你的计算机硬件。 ]0{-'};?
2。什么是搜索问题。用宽度优先搜索算法解一道题。 .U?{1n9dW
3。一道演绎推理题。 A 2#vp |u
4。专家系统的结构与建造步骤。书上动物分类的例子。 J?LD<<(3>
}d[V8#*F}
一、什么是知识表示，用框架系统表示你的卧室。 rqBG-NBO
二、描述A*。 ) VW<:+
三、专家系统的模型。根据下述事实建立分类专家系统的知识库。见书上哺乳动物、鸟 b<1X'2VP
类的分类系统例子。 _PIV
QnU
四、什么是自然语言理解？写出下列句子的句法分析树 gxEI0`i>
1、I WANTED YOU TO DO SOMETHING。 :@?>]eU
2、I SAW SOME CHILDREN PLAYING BALL IN THE FILED。 mju|PvX~KX
e' -qa[%
7| L 3$7Nd
多媒体 uVJ"ZB[-0
1、什么是媒体？什么是计算机媒体？举例5个计算机媒体 8' Au ^ .K^ZT
2、对下面的消息进行Huffman编码，说明过程 8' {) QOg-0
3、说明网络的几个性能参数，及其对多媒体网络的影响 8' t:>a
4、超文本/超媒体的基本概念是？说明为什么WWW这么风靡全球。 8' x>.s@BI5
5、JPEG的基本原理，写出基于DCT的JPEG压缩算法框图。 18' W t`8-![`
rm#> '}`
计算机图形学考博试题 /idF"Tv6CF
1 什么是计算机图形学？它的主要应用？ m@4`iB He
2 什么是种子填色算法？ 0v<p li
3 图段的特点及其结构。 1HoL2"E*
4 忘了，呵呵 {c`) rX^a
5 Z-Buffer消隐算法。 gVV|:
(7
^A% Bi
\g;&?QzCV
2001年4月 yj&9;;LMHa
操作系统 bDr ~a\]/s
1 逻辑地址空间为32位，物理地址空间为24位，页大小为64K。 CZ]O{;DRaJ
（1） 页内地址为多少？ 0A -`no<r`
（2） 物理地址有多少页架？ &%La-|X?4:
（3） 页表的页表项有多少位？ @N(eRN =
（4） 物理地址有多少页？ M/"'$V^sC
（5） 用简图示意地址转换过程？ Xnw|on=qr
8# $=~U@=
2 用SHORTEST—TOB，SHORTEST—REMAINING，RR（时间片为3分钟）三种算法来计算各进程周转时间。 rM !Cm[
各进程 总共所需时间 到达时间 h#r|gY.k>h
P1 10 3 -;#^7!i N
P2 1 1 VLh%$O_2
P3 2 4 S2"1;j@AJ
P4 1 3 {pEmZ 5
P5 5 0 uq\ESP[T |
io"^
3 用一两句话解释下列句子正确性： EX(gb
}wzs
要改变进程优先权，只要改变PCB中某些值即可。 xrUS( #q*
ya:i~R
4改进RR算法，两个数据块同指一个PCB，有什么后果及该算法的优缺点。 y}]<N(9
]W? R)
计算理论 t "9 "
1、 le37K03
（1）当x是完全平方时值为2x，否则为2x+1证明其是原始递归函数。 2oHme-c4
（2）对图灵机模型而言，church论题是什么？ *Nr<x@h
（3）通用图灵机的描述。 rH6TWE x
M> dN
2、 fY/
*#G=
（1）用有穷自动机构造正则语言，以a2b结尾的字符串组成的正则语言L gW1cZM
（2）L={a3n bn |n>0}为上下文无关,但不是正则。 )X$HDp
9F&5%F
3、A为字母表，L为A*上任意的语言。阐述其乔姆斯基层次及用可计算性表述它们的关系。 , [RCITA;
&p'd]!W&
4、证明不存在可计算函数h(x)，使φ(x,x)↓时h(x,x)= φ(x,x)+a,a∈N,φ(x,y)是编号为y输入为x时的程序。 Rig5WAIk>
%<xfjxr
人工智能 $T3F'
1 用框架表示你的软件工作室。 >.~GHF|+
fQ8GKNGw
2 搜索原理？试采用深度搜索方法解决机器人JACK搬运积木问题 66BnQ:Q I
（初态：积木A放在桌上，积木B放在C上面 D,Oi.!#gh
目标态：积木C放在桌上，B在C上面，A在B上面）。 =EZu[U}
W3}9u.tEr
3、家系统模型？用语义网络表示下面五个句子。（书后习题中的句子） +`av;=yV
7mr
}\2j
体系结构 =Qe U:D
1 写出计算机设计所遵从的三种定量原理（有公式的写出公式）。 k1 SP]w6@
1_v5 z:{M
2 计算机CPU--TIME减少技术（重点描述减少CPI）。 s*# ]mm.MD
3;e~t7
3 分析相关性及是否是可并联的？为什么？ >.: [%O r
For （i=2；i〈=100；i++〉 'ly~ (j_R
{ +_`K.Bw
a[ I ]=a[I]+b[I]; s1 V^@Dxf3HB
c[I]=a[I]+d[I]; s2 (p2D*z$x
a[I-1]=2*b[I]; s3 @79k).FE
B[I-1]=2*b[I]; s4 ')/u5Y{fp
} GiCGP?B6Y
,}s\ wu4]
4、写出两种监听协议的优缺点及用图表示他们的工作状态表(书上例子). ?J9BLqL8hw
2002年考博试题 HsPHH=5F
avw(S OB
计算理论 ~{j >6X3d
1． 能被5整除的字符串是正则集吗 uCk0oV vg7
2． 用图灵机表示下列字符串。Φ，e，{a},{a}* &skWYFq<w
3． s->ss, s->asb, s->abs, 证明由s推得的字符串不可能以abb开头。（可能记忆有误，具体形式就是这样）。 &a;`L,Nr
证明不是所有的递归可枚举集都是递归的。 1BcK$DAA
<CG5Ui>JB
面向对象 m0UsPMW~v
1． UML中的几种图及其意义。（9种） CT hC2J
2． 用状态图画出电梯的运行情况 nTuTL^9N
3． 写出图书售货系统的用例。（和书上例子类事） jCE}F]WkI
4． OOA和OOD的区别 |
|