Câu 1

+ "Phép đệ quy phản ánh chiến thuật "chia để trị" trong cách giải bài toán " điều đó là đúng, nó thể hiện ở chỗ: Để giải bài toán với số lượng dữ liệu đầu vào lớn, ta giải bài toán với số lượng dữ liệu đầu vào nhỏ hơn, và nhỏ hơn nữa, cứ thế gọi đệ quy cho đến gọi đến trường hợp bài toán xảy ra suy biến (trường hợp này bài toán được xử lý). Đây chính là tư tưởng của chiến thuật chia để trị (1 đ)

+ Ví dụ: (1 đ)

Chạy chậm một giải thuật đệ quy, ví dụ tính n ! :

Để tính n! Ta tính (n-1)!, .......(n-n+1) = 1! = 1.(vẽ hình minh họa)

Câu 2

+ Dạng cài đặt cây bằng cha của mỗi đỉnh: (1 đ)

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

Type Node = Record

Info: Integer;

parent: 0..n;

End;

Tree = Array [1..n ] of Node;

Var T: Tree;

+ Tìm cha của đỉnh thứ k: (1 đ)

parent (T, k) := T[k].parent;

+ Tìm con cả của đỉnh thứ k trên cây T (1 đ)

Duyệt các đỉnh trên cây T, xuất phát từ đỉnh gốc(i:=1), kiểm tra xem cha của đỉnh i có = k không, nếu = k, kết luận i là con cả, dừng giải thuật, nếu cha của i <>k thì duyệt đỉnh tiếp theo trên cây T bằng cách cho i:= i+1. Lặp đi lặp lại phép duyệt các đỉnh trên T cho đến khi tìm thấy thì dừng (found = true), hoặc duyệt hết các đỉnh trên T (i>n với n là số đỉnh trên cây) thì cũng dừng và kết luận không tim thấy

Câu 3

+ Dạng cài đặt cây bằng con trưởng và em liền kề của mỗi đỉnh: (1 đ)

Type Tree = ^Nut;

Nut = record

Tenthumuc: string;

Kichco:integer;

EldestChild, Nextsibling:Tree;

End;

Var T: Tree;

+ Duyệt cây theo thứ tự sau để xác định tổng kích thước của cây thư mục (1 đ)

+ Mô tả cách tính tổng kích thước cây thư mục T trên: (1 đ)

- Biến: tong:= 0; {tong lưu tổng kích thước toàn bộ cây thư mục}

- Procedure postOder(T : tree, var tong:integer);

Var C: tree;

Begin

if (T=nil) then exit;

else

begin

C:=t^.eldestChild;

postOrder(C);

C:=C^.nextsibling;

While (C<>nil) do

Begin

postOrder(C);

C:= C^.nextsibling;

End;

Tong:=tong+T^.kichco;

end;

End;