Câu 1

Tương tự câu 3 đề 16

Câu 2

+ Cài đặt cây nhị phân bằng mảng các nút: (0.5 đ)

Const n = <số đỉnh tối đa trên cây> ;

Type Nut = Record

Infor: Integer;

Left, Right: 0 .. n;

End;

TreeBina = array[1..n] of Nut;

Var T : TreeBina;

+ Giải thuật duyệt cây theo thứ tự trước: (0.5 đ)

PreOrder(T):

1) Visit (T);

2) preOrder(T.Left);

3) preOrder (T, Right);

+ Giải thuật duyệt cây theo thứ tự giữa (0.5 đ)

InOrder(T):

InOrder(T.Left);

Visit (T);

InOrder (T, Right);

+ Giải thuật duyệt cây theo thứ tự sau: (0.5 đ)

postOrder(T):

InOrder(T.Left);

InOrder (T, Right);

Visit (T);

+ Ưu nhược điểm của cây NP cài đặt bởi mảng (1 đ)

Ưu điểm:

- Truy cập đến các nút là trực tiếp, do đó tốc độ truy cập là nhanh

- Dễ thực hiện các thao tác

Nhược điểm:

- Tốn bộ nhớ khi cài đặt, vì có hiện tượng giữ chỗ để đấy mà không dùng đến

- bị quy định bởi không gian nhớ kế tiếp của mảng

Câu 3

a) (1 đ)

Biểu thức tiền tố: //A+bc-d*ef

Biểu thức hậu tố: Abc+/def*-/

b) (1 đ)

Biểu thức tiền tố: v^x1x2^x1x2

Biểu thức hậu tố: x1x2^x1x2^v