|
久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。
. L* k5 V4 q8 p S8 T6 {* N0 F9 Z: Y8 P4 n) D% K" ]$ `
一、单选题(共 20 道试题,共 60 分。)V 1. Chmosky的3型语言是这样一种语言,其产生式限制为什么()。
* u+ d- b' Y) X" j( B' R6 @A. A::=α
7 y; r' x! l, l0 t3 ~6 R, E9 M" NB. A::=a,A::=Ab; M$ u$ O, O% B; ]. D
C. α::=β
" A' I8 m* @/ n. DD. αAβ::=απβ
3 G0 Y5 _1 S3 [, A: N 满分:3 分
1 ?/ h( U9 H* F9 J2 z* a1 v2. DFA中定义了一个从K×Σ到K的单值映射f,指明若当前的状态为P,而输入字符为a时,则下一个状态是Q,f记为什么()。; v7 b9 U0 g+ J( t% Y
A. f(P,Q)=a
0 O5 {* b) u& i( j1 E mB. f(P,a)=Q
o# g3 m: f! Y$ [3 jC. f(Q,a)=P/ Q1 P" T2 u3 M, G+ ?! }: ?
D. f(a,P)=Q
- {1 t9 Z; e* O5 @$ e! a- v 满分:3 分
& Y6 h$ Q4 p \. F% {, T m' v3. 对于状态转换图中用矢线连接的任意两个结点,把靠箭尾一侧的结点称为该矢线的什么结点()。! A" q2 Z4 I, z+ e, ?3 K6 }, s& Y' }/ J
A. 进入* f5 A: g/ Y, Q* u" U0 W+ ?
B. 射出
& y, F$ v$ ]1 O# VC. 初态+ j% Z/ i. `) \' v
D. 终态
0 e1 Q6 C& @( D3 O% I, n6 X h 满分:3 分3 i: f2 X# N4 p S( m" u# w
4. 能将汇编语言翻译为机器语言的程序是什么()。3 \$ e5 o7 ^: x, Z6 X1 }
A. 汇编程序6 O1 w& x( X& q! R
B. 编译程序
7 `+ |( {0 }& b! fC. 解释程序& O; o' U5 w5 f% c) |1 ?
D. 语言程序
3 ~0 E: N3 v7 `. O+ G 满分:3 分
" q' T+ v9 c4 m# j% c5. NFA的要素中不包含哪个成分()。1 C/ l) [3 l8 t9 u# Q
A. 有穷字母表) }8 l6 C8 S8 ], D8 ^1 r. @
B. 初始状态集合
9 k! W* w* V% d/ ^. {C. 终止状态集合' A' R7 y6 f& f7 d: e% [; n+ S4 U# Y
D. 有限状态集合6 i) `, b; C: V4 N0 ?9 D' i# K
满分:3 分
3 @5 V' w6 q$ @( r) g9 r6. 正规文法和FA在描述同一语言类的意义下是什么关系()。) q$ U! I2 s: I' b
A. 同构: a6 D, c. w9 m3 v# z( k# X
B. 相互等价) S5 C: m \0 Q' i; X- v
C. 可区分1 d) V* }# Q, J3 _
D. 不可区分+ c4 ^# W3 [/ c2 H+ h$ [ l
满分:3 分
5 A& o1 s& m4 |- }" Y7. 对于自底向上的语法分析而言,须着重解决的问题是什么()。+ g, z' [( o8 b/ \) s
A. 如何确定一个规范句型的句柄3 Q( m( i& v/ p, ` Z
B. 应将句柄归约为哪个非终结符号
2 [ }' p/ C9 R( w- N6 @3 y1 A8 mC. 如何确定一个规范句型的句柄,以及应将句柄归约为哪个非终结符号
$ w8 t) }& I ^7 a1 ]5 dD. 以上都不是
: ]* Y* p. Q: ~: }) E' \7 b 满分:3 分% r) F" z8 P3 V# U
8. 通常把每个非终结符号的右部符号串称为该非终结符号的什么()。
3 I5 m% ?$ b6 }4 a$ J4 sA. 推导项
3 H9 d! Q$ [0 g5 J$ t5 s$ WB. 选择式
. \& u, b8 n( C& JC. 规则项8 _+ `) ]( a5 l8 i5 M4 {, z2 U
D. 候选式3 i( g5 p0 d" i+ o' Z
满分:3 分! q7 Q- w) `" l9 k, W
9. 在BNF表示方法中,“→”表示什么()。0 @* T' j7 J: w- T$ J
A. 恒等于' U% D2 N* L7 I5 Y7 u0 n; N
B. 不等于
4 a0 S# v- W0 A8 o4 L SC. 取决于
$ V, A! m8 _; O( {) X6 xD. 定义为 x5 N; U, `6 K$ g3 [7 B0 c
满分:3 分$ w* B3 `. Q4 b
10. 设有文法G[S]:S→aTS|b|(T),T→TSd|a,则该文法的左句型是哪个()。
7 D* Q% z& }0 {7 J. z6 IA. aT(T)3 ?0 \" L% F- B! n5 A) {% v
B. aTaaS2 d8 v- u4 B5 I6 I* l( Q
C. aT(T)Ds" H$ I% C( Q3 Q, d7 }# q# k+ F
D. aTSdS1 m7 o* q* ?5 t( \
满分:3 分
6 A0 b0 p. b" I11. 句型是由什么推导出的符号串()。' U0 L, h+ R4 ~* N+ \5 l. t7 p
A. 非终结符
% c: [) ~0 Q- N( r; |' R5 ], p" Y+ |% lB. 终结符
; h* E! \) `6 X3 b1 s& g* X9 lC. 任何符号
- B0 G5 M6 P( P0 XD. 开始符号( q7 S6 t, ^7 }7 ` }
满分:3 分
2 O( c3 F6 w" {2 x12. 什么问题对具体语言及编译程序的运行环境有很强的依赖性()。
4 \$ T& m& n' l- `A. 分遍* b: N0 U* R- x g4 Y- I
B. 覆盖
- p- N: H: }) G, G0 ?C. 扫描
0 ?: N. H, J2 I0 P8 k3 J- T& WD. 翻译' @ h! N, N: ~* A- c
满分:3 分
0 e. a$ u7 a$ j; {, O( ^13. 是否存在能被确定的有穷自动机识别,但不能用正则表达式表示的语言()。
: z$ f) r1 }* [+ J% s# X; p! cA. 存在- j; O" X) D7 d; v1 T3 I8 T
B. 不存在- u# N* H. A5 g7 y, B5 o! t, z9 |
C. 可能存在
* x& ?( n* E1 e2 p) TD. 无法判定是否存在* _% x2 X# C% r, [! H8 v2 Y* V
满分:3 分
6 q- l- R I+ L( t14. 即使A是一个有用的符号,如下哪一类产生式也是不必要的()。
! U( c' H7 W, Z; UA. A→A1 Z- M: u; h3 n0 }8 q
B. A→Aa
* q5 Q! m: Q# i( t# |- eC. A→aA
$ a: M% p' C8 A# o4 _, S3 U1 \: SD. A→aAb& X& V7 J' M8 a
满分:3 分
$ E9 x2 Q, y* Q9 d. ?15. 不属于编译程序组成部分的是什么()。
5 _. ?, ]0 s( ~* o5 uA. 词法分析程序
) p2 C* V7 q( o j; s9 oB. 代码生成程序
, e. {9 `+ Q6 |3 R% H2 RC. 设备管理程序
6 k& F! g: @$ D+ h& xD. 语法分析程序# E9 `, z: T) p' }8 L1 f
满分:3 分
# v* X( L1 ~% P8 X$ _16. 下述正规表达式中,能描述字母表{0,1}上所有长度不为3的符号串的是哪个()。
. @. |; @& n$ Y+ v5 s" k$ ]. R8 \A. (ε|0|1|00|11|10|01)((0|1)(0|1)*)
% m! I$ E2 J% y! rB. ε|0|1(00|11|10|01)*/ Q" U: }9 s- g' i5 _7 ~
C. ε|0|1(00|11|10|01)(0|1)*6 U @- l/ G# z" s6 r9 ~
D. 没有一个
/ i6 R& k3 }' R% m2 N2 ^( d 满分:3 分
# V1 R( K& K$ J' A17. 正规表达式最适合描述什么()。
& y# k' n% Z" Z! V3 f" oA. 语法
. l2 o8 I; w; h8 F0 P+ WB. 语义; l+ a7 D: }1 C( g* ?" S* L! {
C. 词法8 v, S9 t; `, y# Z2 o" d3 C
D. 程序变换
3 p" t( W2 x' F/ w" f. w0 q 满分:3 分
, Y& Q, c- D/ Y18. 设G是一右线性文法,并设G中的非终结符号的个数为k,则所要构造的状态转换图共有几个结点()。
5 p" T) I& y2 }0 f# v8 DA. k-1
; m- C$ f% M+ a4 Z6 lB. k
- ]: j! _: _2 C+ ~ l5 l* yC. k+1 w2 E5 U6 b( f- j
D. k+2: |0 Y9 |. A* o: v9 D
满分:3 分
4 r& m+ B9 x/ x6 w) P! f* `19. 描述语言L={a的m次方b的n次方|n≥m≥1}的文法是哪个()。
' b9 ^& S2 Q3 m4 n9 YA. Z::=Abb,A::=aA|a,B::=bB|b' ~( C& n' M8 u
B. Z::=AB|b,A::=Aa|a,B::=aBb|b
9 e3 ^2 v2 Q8 ^! q0 X5 dC. Z::=Ab,A::=aAb|a g* e, B- t( ]2 W
D. Z::=aAb,A::=Ab|aAb|ε9 a& \6 h( l: \/ W3 }6 r
满分:3 分1 m2 C$ I, D3 J1 V. B! L, n1 } R
20. 方程X=rX+t的解是什么()。: c( l: ^9 Q+ e1 |/ [9 q8 o& S
A. X=rt*
* m! e6 |' \, Y N) ]$ uB. X=t*r
/ ?1 Z' v# D7 F+ d$ t: x; t) rC. X=r*t
2 q7 g+ \. P' _% h! ?D. X=tr*, s. b3 q, l# Z
满分:3 分 $ _( i" D" n( z3 E6 M& L
; K: ]2 @* i( I; K% j5 q# v
二、判断题(共 20 道试题,共 40 分。)V 1. 每一个NFA都对应有唯一的一个最小化的DFA。& O- D$ R+ y: x3 W9 a
A. 错误% K8 w) H T7 a/ I9 R
B. 正确
, g6 f! l4 V- F' [ 满分:2 分
8 m! H3 Y3 F- C8 M1 m2. 计算机高级语言翻译成低级语言只有解释一种方式。
- E/ n" t. w. S5 \* z' FA. 错误
) ~! {; w& B9 C; ^: ~B. 正确
5 w) W, _$ W0 n# c/ [! \( o6 Q7 @ 满分:2 分( ~+ U; v+ K0 P) @
3. 在一个状态转换图中,规定从一个结点只能射出一条矢线。+ I& F6 ]# d; O" t8 u; P" F
A. 错误
! z% G, v( L' o: r: j3 zB. 正确; M9 ]2 p2 z( p% Q8 C4 p2 V$ V
满分:2 分0 u: \' E+ `( @* l+ C& S
4. 1型文法常用来描述一个程序设计语言的单词结构。
& D9 l! i: h6 l, xA. 错误2 a$ n( g/ l/ \1 X0 H. ~# ~
B. 正确3 E% a6 E v" @8 |- K
满分:2 分
8 x2 J7 U! p' q) A+ f5. 对于要求经一遍扫描就能完成从源程序到目标代码翻译的编译程序,不必产生中间代码。
; @* N& j% O* K" ~/ ZA. 错误
4 e$ K! w& O) x \B. 正确) s. Z- S4 U0 Y' a6 ^
满分:2 分1 w m0 V% V8 a' T
6. 上下文无关文法可以产生语言 L={anbncn|n≥l}。
4 Z: r( ]5 I% y# V$ ~A. 错误5 d2 u; O6 z& N7 }: ^5 P
B. 正确
( O$ z/ e3 O8 m# h/ e) x; q/ v7 d 满分:2 分; J" w/ _- T5 }6 q4 y# [
7. 编译程序生成的目标程序一定是可执行的程序。0 s( i* G/ L3 T1 E
A. 错误 I/ c, r# y2 o0 l$ X
B. 正确
. P5 Q+ e3 y2 U$ z6 e7 U6 B 满分:2 分7 D# l# L+ p% A+ Q+ Y9 g) N
8. 对程序语言来说,关键字、标识符、各种常数、各种运算符及分隔符都是单词。
8 Z3 T5 G* ?0 c$ L7 FA. 错误
; ^+ A0 s6 {) y! r4 Q* CB. 正确
! v8 {* \3 t* U8 m 满分:2 分
0 m' ]5 U" t# `1 {# C! y/ X9. 一个文法所有句子的集合构成该文法定义的语言。9 R# i5 E4 d1 B, l( x
A. 错误
3 _! x. Q0 B! N5 P2 R! SB. 正确' t3 Q/ p6 ]+ {3 g4 b6 Q: I' v
满分:2 分
; v8 S" M+ a7 d) M- o10. 根据文法等价的概念,可对文法进行等价改造,以期得到所需形式的文法。
$ l, Y- q$ z* W3 z3 V# t* AA. 错误# U5 @9 |( ?0 e# P4 h$ ~; @6 B, m
B. 正确
( ]9 S' D5 y7 c# h( v 满分:2 分
- C h/ d. u; U: r+ d: z11. 一个仅能处理绝对正确源程序的编译程序才具有实用价值。
4 a1 ~/ D/ n* EA. 错误
3 \2 m" c# z0 eB. 正确
8 @* {- i0 Z& D) F. [# c 满分:2 分
+ P8 q; L2 ^' z4 U12. 若消除文法中的ε-产生式,将会改变文法所定义的语言,故不能消除ε-产生式。
9 }3 X0 ~& v& q* GA. 错误% L. p, P9 }# f# c
B. 正确
# `4 @9 h) g4 O4 ~# V5 q# y- V 满分:2 分& j% o# X; t& v* u% t" ]2 Q
13. 每个句型不一定存在一个规范推导。, G4 j s9 Q, G4 h" t! [' s
A. 错误
/ I# f9 R+ Y9 A _5 tB. 正确
5 `% U. \# _) \: ] 满分:2 分) O! G# r$ D' w$ Y/ D3 ]1 L
14. 当ε∈L(G)时,则G中的ε-产生式肯定不能全部予以消除。
8 t3 O$ Y% m0 c6 FA. 错误0 A7 B3 X4 v! L" r3 K
B. 正确3 f4 t1 R# i7 {* t- _
满分:2 分8 I1 r$ W1 X9 r# _; _ Q
15. 状态转换矩阵的列标题表示状态图中的各个状态。
* v z! Q9 q! S W# `6 DA. 错误
3 R# a# Z0 k" @3 {6 L5 E9 nB. 正确6 ^* F; f0 i+ o5 c
满分:2 分
7 ]+ p! }, z- ~* M ]3 x) [; Y8 e16. 一个NFA对符号串的识别是一个试探的过程。不过,这种不确定性给识别过程带来的反复,不会影响到FA的工作效率。
2 K p$ _8 x$ E9 ZA. 错误
" p. @ |; S& H( I6 rB. 正确
: Q1 f% `1 l, P* _5 \ 满分:2 分) x$ q1 y# r1 ]2 t# w* ^6 F
17. 对于具有二义性的文法,其规范句型的句柄也是惟一的。2 H; X9 ?# a4 }; Z( u! W
A. 错误
3 C8 O v# q' u) eB. 正确- x+ J5 O" R3 K7 s' R
满分:2 分0 @8 `- i% T$ N/ ? {) e
18. 正规文法产生的语言都可以用上下文无关文法来描述。
: C& J8 G( D! XA. 错误
6 ]9 S) e- b% x1 Q+ D8 `) ~0 }B. 正确8 c) X$ @" i7 R1 b- S
满分:2 分
: j5 N* R! B7 ~6 i- c* A& m" ` w- E, N19. 一个句型对应的一棵语法树包括了该句型的所有推导。% D& ~! J$ H7 P- o- F! z; ?* }
A. 错误
1 w% {) {2 j( L% e/ k6 ^B. 正确
# w" E3 ]+ r9 z" h8 A 满分:2 分
8 t) @$ ~) _9 _4 ]20. 状态转换图不能作为有限自动机的直观图示。5 i, J; b# M, b! q
A. 错误
' P9 l M% A6 ^B. 正确* n" j! ], a4 I ?
满分:2 分 % w/ ^& y9 T: X* g6 a& `
% B" S$ o6 t4 D* g G
久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。 |
|