Phân tích sâu trong kỹ thuật lập trình
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (78.1 KB, 6 trang )
Câu 1
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Từ gốc của
cây áp dụng suy dẫn (1) để triển khai, sau đó áp dụng suy dẫn (1) để
triển khai bước sau thì cây suy dẫn tại thời điểm này có bao nhiêu
nút?
A)
6
B)
7
C)
8
D)
9
Đáp án D
Câu 2
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Cây suy dẫn
tại thời điểm bắt đầu có bao nhiêu nút?
A)
1
B)
2
C)
3
D)
4
Đáp án A
Câu 3
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn sản xuất
(1) liên tiếp để phân tích thì tới khi phải quay lui, cây suy dẫn tại thời
điểm này có bao nhiêu nút?
A)
10
B)
11
C)
12
D)
13
Đáp án D
Câu 4
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn sản xuất
(1) liên tiếp để phân tích thì tới khi phải quay lui, cây suy dẫn tại thời
điểm này có bao nhiêu nút?
A)
10
G = {S→ aSbS | aS | c}
(1) (2) (3)
G = {S→ aSbS | aS | c}
(1) (2) (3)
G = {S→ aSbS | aS | c}
(1) (2) (3)
G = {S→ aSbS | aS | c}
(1) (2) (3)
B)
11
C)
12
D)
13
Đáp án D
Câu 5
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn lần lượt
các sản xuất (1) (1) (1) (2) (3) (1) (2) (3) để phân tích thì phải quay
lui bao nhiêu lần?
A)
3
B)
4
C)
5
D)
6
Đáp án B
Câu 6
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn lần lượt
các sản xuất (1) (1) (1) (2) (3) (1) (2) (3) để phân tích thì tại thời
điểm này của quá trình phân tích thì đầu đọc trên xâu vào đang trỏ tới
kí tự thứ bao nhiêu?
A)
3
B)
4
C)
5
D)
6
Đáp án D
Câu 7
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn lần lượt
các sản xuất (1) (2) (2) (3) (1) (2) (3) để phân tích thì tại thời điểm
này của quá trình phân tích thì đầu đọc trên xâu vào đang trỏ tới kí tự
nào?
A)
A
B)
B
C)
C
D)
$
Đáp án D
Câu 8
Cho văn phạm
G = {S→ aSbS | aS | c}
(1) (2) (3)
G = {S→ aSbS | aS | c}
(1) (2) (3)
G = {S→ aSbS | aS | c}
(1) (2) (3)
G = {S→ aSbS | aS | c}
(1) (2) (3)
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn lần lượt
các sản xuất (1) (2) (2) (3) (1) (2) (3) để phân tích thì tại thời điểm
này bộ phân tích phải quay lui bao nhiêu lần?
A)
1
B)
2
C)
3
D)
4
Đáp án C
Câu 9
Cho văn phạm
phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn lần lượt
các sản xuất (1) (2) (2) (3) (1) (2) (3) để phân tích thì tại thời điểm
này cây suy dẫn có bao nhiêu nút?
A)
8
B)
9
C)
10
D)
11
Đáp án A
Câu 10
Cho Văn phạm
phân tích xâu vào “0111” bằng thuật toán Topdown. Chọn lần lượt
các sản xuất (1) (2) (2) (3) (5) (4) (3) để phân tích thì tại thời điểm
này cây suy dẫn có bao nhiêu nút?
A)
8
B)
9
C)
10
D)
11
Đáp án B
Câu 11
Cho văn phạm G = {S → AB; A → A0| B0|1; B → A1|0} Sau khi
loại bỏ đệ quy trái cho văn phạm G thu được văn phạm G’ tương
đương. Trong G’ có bao nhiêu luật sinh có vế trái là B?
A)
2
B)
4
C)
6
D)
8
Đáp án XXX
Câu 12
Cho văn phạm
G = {S→ aSbS | aS | c}
(1) (2) (3)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
(1) (2) (3) (4) (5)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
(1) (2) (3) (4) (5)
phân tích xâu vào “0111” bằng thuật toán Topdown. Bộ phân tích
thực hiện theo các Hành động của bộ phân tích lần lượt là: gạt, thu
gọn theo (4), gạt, thu gọn theo (2), gạt, thu gọn theo (4) thì trạng thái
phân tích tại thời điểm này là gì?
A)
Ngăn xếp: $A; Xâu vào: 11$
B)
Ngăn xếp: $1; Xâu vào: 11$
C)
Ngăn xếp: $AA; Xâu vào: 1$
D)
Ngăn xếp: $A1; Xâu vào: 011$
Đáp án XXX
Câu 13
Cho văn phạm
phân tích xâu vào “1011” bằng thuật toán Topdown. Chọn lần lượt
các sản xuất (1) (2) (2) (3) (5) (4) (3) để phân tích thì phải quay lui
bao nhiêu lần mới đạt trạng thái thành công?
A)
0
B)
1
C)
2
D)
3
Đáp án C
Câu 14
Cho văn phạm
phân tích xâu vào “0111” bằng thuật toán topdown. Chọn lần lượt các
sản xuất (1) (2) (3) (4) (3) để phân tích thì phải quay lui bao nhiêu lần
mới đạt trạng thía thành công?
A)
0
B)
1
C)
2
D)
3
Đáp án A
Câu 15
Cho văn phạm
phân tích xâu vào “1011” bằng thuật toán Bottom-up. Quá trình phân
tích nào sau đây đạt trạng thái thành công?
A)
Phân tích lần lượt theo các sản xuất (1)(3)(2) (2)(3)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
(1) (2) (3) (4) (5)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
(1) (2) (3) (4) (5)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
(1) (2) (3) (4) (5)
B)
Phân tích lần lượt theo các sản xuất (1)(3)(4)(2)(3)
C)
Phân tích lần lượt theo các sản xuất (3)(4)(2) (2) (3)
D)
Phân tích lần lượt theo các sản xuất (1)(3)(4)(3)(2)
Đáp án B
Câu 16
Cho văn phạm
phân tích xâu vào “0111” bằng thuật toán topdown. Quá trình phân
tích nào sau đây đạt trạng thái thành công?
A)
Phân tích lần lượt theo các sản xuất (1) (2) (2) (4) (5)
B)
Phân tích lần lượt theo các sản xuất (1) (2) (2) (3) (4) (3)
C)
Phân tích lần lượt theo các sản xuất (2) (2) (3) (4) (3)
D)
Phân tích lần lượt theo các sản xuất (1) (2) (3) (3) (4)
Đáp án B
Câu 17
Văn phạm nào sau đây phân tích được theo phương pháp Topdown?
A)
G = {S→ ΑΒ; Α → 0Α|S1; Β → 1A| 0}
B)
G = {S→ ΑΒ; Α → 0Α| Β1|1; Β → A1| 0}
C)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
D)
G = {S → AB; A → A0| B0|1; B → A1|0}
Đáp án C
Câu 18
Văn phạm nào sau đây KHÔNG phân tích được theo phương pháp
Topdown?
A)
G = {S→ ΑΒ; Α → 0Α|S1; Β → 1A| 0}
B)
G = {S→ ΑΒ; Α → 0Α| Β1|1; Β → 1A| 0}
C)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
D)
G = {S → AB; A → B0|1; B → 1A|0}
Đáp án A
Câu 19
Cho văn phạm
phân tích xâu vào “1011” bằng thuật toán Bottom-up. Chọn lần lượt
các sản xuất (1) (2) (3) (4) (2) (3) để phân tích thì cây suy dẫn thu
được có bao nhiêu nút?
A)
7
B)
8
C)
9
D)
10
Đáp án
XXX
Câu 20
Cho văn phạm
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
(1) (2) (3) (4) (5)
G = {S→ ΑΒ; Α → 0Α| 1; Β → 1A| 0}
(1) (2) (3) (4) (5)
