|
久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。
2 e+ w2 k& ^( \$ l2 O. K s$ k- y5 |8 N2 A8 e/ X( R0 c) M
一、单选题(共 20 道试题,共 60 分。)V 1. Chmosky的3型语言是这样一种语言,其产生式限制为什么()。- N5 F) R! i5 i# T2 I0 k
A. A::=α
8 H- ~+ l+ ?1 L3 iB. A::=a,A::=Ab/ n3 `4 ~4 v* b& \5 q
C. α::=β
- ~- s8 E* ]9 \ iD. αAβ::=απβ( A @8 D4 P* J9 o3 D/ b$ o( P* @! Z
满分:3 分 ?) J( t s% ~ t
2. DFA中定义了一个从K×Σ到K的单值映射f,指明若当前的状态为P,而输入字符为a时,则下一个状态是Q,f记为什么()。
3 S- S. s; g& ~8 tA. f(P,Q)=a+ t9 d- K# M4 c4 e& [
B. f(P,a)=Q6 |5 l2 J9 c$ g/ f% x7 w1 p4 R
C. f(Q,a)=P
5 Z; u! n3 N( |$ J8 I6 W+ tD. f(a,P)=Q% U# R2 V$ e v+ G8 b! H" G. V
满分:3 分) N. f {! H4 {
3. 对于状态转换图中用矢线连接的任意两个结点,把靠箭尾一侧的结点称为该矢线的什么结点()。8 v- L6 _4 E1 G& c
A. 进入
- g' M8 i& t8 m& i% @+ g3 O. Z8 Q% RB. 射出; i7 h$ F. k# o
C. 初态
+ h* C( G, F3 r$ eD. 终态
- ?$ \7 H0 n$ b/ M! Y 满分:3 分1 s B7 W- P! T0 \* P' D0 {: G
4. 能将汇编语言翻译为机器语言的程序是什么()。
9 @2 g9 n' D! v$ [: }( yA. 汇编程序3 p- N8 m9 q# V4 n
B. 编译程序4 W/ s! P+ O4 s$ H% w
C. 解释程序; J/ M5 l! y$ A% z" w) l
D. 语言程序0 {. ?0 s% q: u! ^( b# i: m
满分:3 分
& l6 {: `) e( j I d4 f5. NFA的要素中不包含哪个成分()。
2 D8 U* r: l A# ~A. 有穷字母表
, q4 P% v8 v9 N# Y1 m2 E4 s- vB. 初始状态集合
/ N, y' d# a3 S( ]C. 终止状态集合
3 ]& p" P/ q' T( \7 E$ hD. 有限状态集合
3 u' G1 S6 k& H5 `6 h- T 满分:3 分
; v' [8 ?! w# v# v1 ~6. 正规文法和FA在描述同一语言类的意义下是什么关系()。4 E' x$ Z. w& s' A8 ~* {5 x4 J
A. 同构
: {! \4 j Y1 N5 GB. 相互等价
, _9 i9 r4 F, z- }5 x6 ?C. 可区分
: J+ ]. `8 W E7 ~' GD. 不可区分
8 g$ c. U, O: g. P" O* b" b4 M 满分:3 分/ E$ d. P* j" ?$ O! w7 ]* a2 O. T8 W" M
7. 对于自底向上的语法分析而言,须着重解决的问题是什么()。7 A( _/ @ w e: V$ F5 N
A. 如何确定一个规范句型的句柄
* n. t+ [7 Q1 \4 B& eB. 应将句柄归约为哪个非终结符号
* N3 c" g9 g- s0 z* }3 n4 d) mC. 如何确定一个规范句型的句柄,以及应将句柄归约为哪个非终结符号
9 d W9 Q. z5 e) y8 AD. 以上都不是) ]% r) g% t0 J) q/ U; k/ g
满分:3 分1 D7 }- X7 d( O. N0 b5 [
8. 通常把每个非终结符号的右部符号串称为该非终结符号的什么()。
5 n$ R0 z0 } x$ \9 L- ]A. 推导项$ a: R& u3 a. a9 K& s! _' S1 a9 w: y
B. 选择式
* q6 G/ }' _/ a8 A Z+ ^# FC. 规则项9 x' a! n6 T, n7 H1 j" i
D. 候选式
. D7 r9 D; v; ` 满分:3 分6 [: H6 O' u; q1 f! [
9. 在BNF表示方法中,“→”表示什么()。
% u4 \7 p; ~& `& M# h, mA. 恒等于; ^( ?& N! W: O0 Z% O
B. 不等于0 k# ]$ L, b& _. t6 }
C. 取决于9 U0 n" V9 E9 c! ]8 z
D. 定义为
( d8 g/ C0 m6 Y3 d" F/ @ 满分:3 分
' l w0 y6 V) l4 I9 c8 K10. 设有文法G[S]:S→aTS|b|(T),T→TSd|a,则该文法的左句型是哪个()。
- z# M" X- o, R6 k, ?; cA. aT(T) k( D5 \+ Y/ f4 u
B. aTaaS
- ~2 D, e l" rC. aT(T)Ds
5 _3 p6 u" L; Q0 ?D. aTSdS$ F S; W5 p, I& c# n4 O" D$ i
满分:3 分
3 U; m( f v$ _/ [' B% r0 {11. 句型是由什么推导出的符号串()。 H% m0 C+ G& F6 w# o5 L! M
A. 非终结符
; d8 }- X, L" l6 `. S& r5 c5 MB. 终结符, C; p; i9 @2 `5 Z( I) X
C. 任何符号
, B# k5 Y S$ r RD. 开始符号: W4 Y6 E4 X4 b4 s" v# J) K
满分:3 分1 m( J2 }: ?2 @2 F
12. 什么问题对具体语言及编译程序的运行环境有很强的依赖性()。9 p- Y& l4 g0 u4 j1 T
A. 分遍$ y4 y6 Z, U6 s5 `+ |( ~/ J( A
B. 覆盖
L E5 D( h2 e! _* D2 J3 LC. 扫描
6 G' k3 E5 @5 K( ?( S9 x dD. 翻译
- e% t6 c5 q7 r 满分:3 分
) L% |3 U* [! q( ~13. 是否存在能被确定的有穷自动机识别,但不能用正则表达式表示的语言()。
, D/ f7 O/ ~0 `3 _' |+ A0 V; xA. 存在
3 `. U& V8 ?" L. N. sB. 不存在1 H) B6 J* r. G5 @+ u+ i. x5 I" b+ x
C. 可能存在
) u( X* O: \* Q. QD. 无法判定是否存在
3 s& y1 Z# \; y# n% H 满分:3 分! Y! T2 C1 Q' K! z' g0 Y
14. 即使A是一个有用的符号,如下哪一类产生式也是不必要的()。& |/ y9 i" l6 s
A. A→A
5 s$ ?; n' F3 I$ N+ T6 L; x* h# eB. A→Aa# u. m# b7 X I8 f9 P
C. A→aA
9 G: T I0 S- ]$ w" c+ ]D. A→aAb
, C- _ x9 y8 A O1 e 满分:3 分
+ y3 P( ~+ J$ i: m% D( {15. 不属于编译程序组成部分的是什么()。
* F9 j' h# ~, j7 s- iA. 词法分析程序$ W& {3 `1 N! S i' B1 n
B. 代码生成程序
8 \. S. s( a* S3 X9 AC. 设备管理程序) A8 \* H: g8 v% p( J/ N, r4 r
D. 语法分析程序% g* w+ K2 k4 U- }. F2 o( M& q
满分:3 分+ m) W9 X: I- o( ^+ r3 K
16. 下述正规表达式中,能描述字母表{0,1}上所有长度不为3的符号串的是哪个()。
3 K& a& a) t TA. (ε|0|1|00|11|10|01)((0|1)(0|1)*)
% {& N. ~* A. \ t# f# |& x8 W( ~5 mB. ε|0|1(00|11|10|01)*/ S9 ~. q3 ~ o( z" _% L) J4 k% m
C. ε|0|1(00|11|10|01)(0|1)*
. R- w. \! W" {2 dD. 没有一个
V5 ]! I% j3 {! \ 满分:3 分( }' I9 @0 ?+ B% z
17. 正规表达式最适合描述什么()。
0 p8 h: j1 y* J* U- H9 uA. 语法
" F& S+ f. i7 CB. 语义
[! q6 \& s& m2 ^0 e0 E0 V' U+ NC. 词法* T- F q; b j2 x! w8 ]
D. 程序变换
4 E5 f2 V+ f: {. i; B! Q. ^! Y 满分:3 分
# g4 q* p7 ]1 q! X G18. 设G是一右线性文法,并设G中的非终结符号的个数为k,则所要构造的状态转换图共有几个结点()。0 Z" O' r1 P1 d1 t
A. k-18 @7 L6 D3 b L2 v; p; K# E: \8 k8 G
B. k
7 A1 z9 y+ ?/ g1 V3 x* Q6 HC. k+1. } _5 c0 D0 x, K+ E
D. k+2
! s8 M! A( c% @8 @6 w" }( i 满分:3 分
* w/ a: Y; i8 ?( N/ d19. 描述语言L={a的m次方b的n次方|n≥m≥1}的文法是哪个()。
1 Y9 `( E5 g' [2 g$ G& A) [A. Z::=Abb,A::=aA|a,B::=bB|b
; j; H {1 S6 S/ G& OB. Z::=AB|b,A::=Aa|a,B::=aBb|b4 L0 Y! ?3 Z0 D% G9 @. v8 i! I
C. Z::=Ab,A::=aAb|a6 N, H& T4 b* }) m p
D. Z::=aAb,A::=Ab|aAb|ε
* g* t* Y Y) h9 `3 r2 ^( |, H- e$ } A 满分:3 分8 S' H+ J" e0 h, r8 F. V
20. 方程X=rX+t的解是什么()。" I8 a! u; m( f# f' A H8 h
A. X=rt*
" r' D! k/ z& U KB. X=t*r# z; v% ]' O) V" v, |. G; R
C. X=r*t1 j2 X7 b; L% u4 K }
D. X=tr*. ?9 N6 q5 e. l# L `( E
满分:3 分
+ p9 J' M: e! C! D6 K6 A. u6 y4 O+ p' H: \, O
二、判断题(共 20 道试题,共 40 分。)V 1. 每一个NFA都对应有唯一的一个最小化的DFA。
3 C1 }6 W) z1 vA. 错误
# @1 P; `% m9 m& y7 j( CB. 正确
" _- q" p' ?4 v3 n1 ] 满分:2 分9 f2 R3 P- Z3 P9 m& R
2. 计算机高级语言翻译成低级语言只有解释一种方式。
; ^. [# w) ?( a) m9 tA. 错误* l+ i% x& n! P1 _8 W" g0 @. @7 Y+ O
B. 正确
) V. n0 p; `4 y% p6 m" f 满分:2 分
t$ U+ P: p; b8 _( l3. 在一个状态转换图中,规定从一个结点只能射出一条矢线。
: x' s1 f6 k. t$ k! UA. 错误( O) N9 @2 L' }9 G( p$ j4 O* i9 W
B. 正确& |! K6 W( f! E& ]3 K' }0 ]
满分:2 分* j8 a* H& T) k$ n
4. 1型文法常用来描述一个程序设计语言的单词结构。! H3 s2 o# c4 Y
A. 错误# J3 ^9 a4 l1 K0 \" q+ a; y
B. 正确. `, z9 `9 m. S8 _
满分:2 分
5 P* G1 N7 c% n5 t! t5. 对于要求经一遍扫描就能完成从源程序到目标代码翻译的编译程序,不必产生中间代码。
+ ~" `# h, M- H# |9 wA. 错误$ W+ K. ]# `5 Y
B. 正确; w0 l2 n8 [( D6 \$ ~5 i4 t4 |
满分:2 分+ |4 ?8 Y$ \. D3 c
6. 上下文无关文法可以产生语言 L={anbncn|n≥l}。8 _6 \: u0 U2 A) ? O' V
A. 错误+ z$ Y/ p4 j% C0 B/ H
B. 正确
/ B) B0 s" s, |, e 满分:2 分
4 ~& g9 ~9 o5 x4 Z7. 编译程序生成的目标程序一定是可执行的程序。9 ]9 I. Y" u) I9 r
A. 错误
5 F. }6 g$ j3 ?: p5 E$ e M- EB. 正确% i2 d z( q% F- V0 L3 i
满分:2 分
6 A9 t [% k3 l8. 对程序语言来说,关键字、标识符、各种常数、各种运算符及分隔符都是单词。" n7 Q, k9 E/ \$ ^9 ?( e5 s& n
A. 错误' d- |3 T {% Q7 N( d6 i
B. 正确
2 G- h! a0 Z; { Q5 u$ V 满分:2 分
; g- X, R0 ?! o; } b9. 一个文法所有句子的集合构成该文法定义的语言。! \! V& [$ b' Q" u% ^ w5 @8 @( O* a
A. 错误1 V0 i" @+ R9 s6 o1 v% e5 s1 j
B. 正确
5 X6 |( Z: o& H/ q: _/ U 满分:2 分
7 W, Q- C0 U. D) u* v& Q3 k: M) }0 n# a10. 根据文法等价的概念,可对文法进行等价改造,以期得到所需形式的文法。
. s; x, ^9 f% a4 \$ I5 V7 }& uA. 错误1 s) ]$ I1 _% U
B. 正确
$ _5 i3 F5 d- e, Z% i4 n% v 满分:2 分8 ^8 K- h4 H% M Z
11. 一个仅能处理绝对正确源程序的编译程序才具有实用价值。; w& O6 O1 P8 ^4 S5 y) B3 G
A. 错误& C3 c X' g8 @
B. 正确% C" U4 D; K a+ l8 D
满分:2 分
! J1 J9 }, ?9 u- S2 `12. 若消除文法中的ε-产生式,将会改变文法所定义的语言,故不能消除ε-产生式。
7 B% z8 e }9 ^4 K) FA. 错误
# X5 x8 f, A1 l" J" U+ _7 N3 MB. 正确4 r5 j. _; n5 ]3 T2 Q
满分:2 分1 q8 _; F+ q7 C4 h1 e3 V5 v4 u
13. 每个句型不一定存在一个规范推导。" z" Y% ^, j+ O9 q! m# G
A. 错误& u1 f9 _& ~2 Y! S4 B3 O
B. 正确
7 `! w+ y. o1 `9 B 满分:2 分
5 s+ W8 x1 \; B. H' z0 @+ p6 ?14. 当ε∈L(G)时,则G中的ε-产生式肯定不能全部予以消除。0 w) I5 T9 H' X2 M7 k) P
A. 错误
2 B _+ J7 S( |7 v9 |& jB. 正确
+ E4 H& y! b' z4 T7 b$ e, c 满分:2 分
+ y$ y% B# T5 c% E4 W) `15. 状态转换矩阵的列标题表示状态图中的各个状态。
/ _6 s0 o) m; M- b) }A. 错误) M2 j" D* d' b# L% Y" A
B. 正确
0 O! ?" j6 |: p' j2 K& Y8 _ 满分:2 分
: t6 C- ]2 I4 x: D4 L16. 一个NFA对符号串的识别是一个试探的过程。不过,这种不确定性给识别过程带来的反复,不会影响到FA的工作效率。$ Z. x) T3 V; V& u7 w5 ~0 w
A. 错误
$ K4 o) ?. z3 {' y3 @! hB. 正确
: @: ^5 q1 F# n: w8 e, i1 N 满分:2 分2 L2 Y4 R+ e. n3 w- ^
17. 对于具有二义性的文法,其规范句型的句柄也是惟一的。6 T6 U" B# k/ I+ j1 W2 q6 |1 p
A. 错误
% Y. b; V5 v' ]+ ]B. 正确
1 K1 Q" s4 d% H5 n% i7 t+ L 满分:2 分% i) u& _" ?) C+ q y4 ?: Y
18. 正规文法产生的语言都可以用上下文无关文法来描述。 `7 V2 t% e0 Y, z9 P
A. 错误
# q7 i+ d, j1 R! dB. 正确6 n8 T# K9 M3 G- k n8 R) J& {
满分:2 分) r! p% x6 l/ v/ ^% m
19. 一个句型对应的一棵语法树包括了该句型的所有推导。
, S! X7 W7 [1 X7 jA. 错误- Y9 O% [9 O; t& a
B. 正确" ^1 p6 P3 ^- `8 {
满分:2 分4 k _* T% E1 }' {+ D
20. 状态转换图不能作为有限自动机的直观图示。7 V/ F' W6 [ {' R& g; k9 [
A. 错误1 ^9 u: N1 `) A
B. 正确8 m6 f4 `1 a5 M: l
满分:2 分 4 [: e4 V- d+ O/ t7 S
/ J. \. c7 a9 m- U# v+ h) C6 Z1 w+ R久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。 |
|