Mã đề 20

Câu 1 (1đ)

+ Một số cấu trúc dữ liệu như: mảng, bản ghi, tệp tin, danh sách, .....

+ Cài đặt:

Câu 2

+ Nội dung của ngăn xếp sau khi thực hiện các thao tác là: ON (1 đ)

+ Kết qua trên màn hình sau khi thực hiện các thao tác là: SYAEUQTSEI (1 đ)

+ Các thủ tục: thêm, lấy một phần tử ra khỏi ngăn xếp (1 đ)

Câu 3

1) Phương pháp chuyển một biểu thức trung tố sang hậu tố: (1,5 đ)

* Sử dụng ngăn xếp Sđể lưu các dấu mở ngoặc, các dấu phép toán, và dấu /. Ta đưa ký hiệu $ để đánh dấu đáy của ngăn xếp. Khi đỉnh của ngăn xếp chứa $, có nghĩa là ngăn xếp rỗng

* Trên tập các ký hiệu S, (, +, -, *, / ta xác định hàm ưu tiên Pri như sau:

Pri($)<Pri(( )<Pri(+)=Pri(-)<Pri(*)=Pri(/)

* Giả sử cần chuyển biểu thức rung tố E sang biểu thức hậu tố E1, ta thêm vào bên phải E dấu # để đánh dấu hết biẻu thức E. Cách chuyển E sang E1 như sau:

1. Đọc một thành phần của biểu thức E, lưu vào x ( đọc lần lượt từ trái qua phải)

1.1 Nếu x là toán hạng, thì viết nó vào bên phải E1

1.2 Nếu x là dấu ( thì đẩy nó vào ngăn xếp

1.3 Nếu x là một trong các dấu phép toán +, -, *, / thì:

a) Xét phần tử y ở đỉnh ngăn xếp

b) Nếu Pri(y)>= Pri(x) thì loại y khỏi ngăn xếp, viết y vào bên phải E1 và quay lại bước a)

c) Nếu Pri(y)<Pri(x) thì đẩy x vào ngăn xếp

1.4 nếu x là dấu ) thì:

a) Xét phần tử y ở đỉnh ngăn xếp

b) Nếu y là dấu phép toán thì loại y khỏi ngăn xếp, viết y vào bên phải E1 và quay lại a)

c) Nếu y là dấu ( thì loại nó khỏi ngăn xếp

2. Lặp lại bước 1 cho tới khi toàn bộ biểu thức E được đọc qua

3. Loại phần tử ở đỉnh ngăn xếp và viết nó vào bên phải E1. Lặp lại bước này cho đến khi ngăn xếp rỗng

2. Minh họa cụ thể trên biểu thức đã cho (1 đ)

Thành phần trong biểu thức E Ngăn xếp Biểu thức e1

$

a $ a

- $- a

b $- ab

* $-* ab

( $-*( ab

c $-*( abc

+ $-*(+ abc

e $-*(+ abce

) $-*( abce+

$-* abce+

/ $-* abce+

$- abce+*

15 $-/ abce+*15

$-/ abce+15/

$- Abce+*15/

$ abce+*15/-

3. Phác thảo giải thuật chuyển E thành E1 (1 đ)

Áp dụng ý 1 phác thảo giải thuật tương ứng