Câu 1

+ Ba đặc điểm của giải thuật đệ quy: (1 đ)

- Trong giải thuật đệ quy bao giờ cũng có lời gọi đến chính nó

- Sau mỗi lời gọi đệ quy, kích thước của bài toán được thu nhỏ hơn trước

- Bao giờ cũng có một trường hợp suy biến (trường hợp đặc biệt để đãm bảo tính dừng của giải thuật): bài toán được giải quyết theo một cách khác hẳn và giải thuật cũng kết thúc

+ Tính : Q(2,3) =0; Q(14, 5) = 2 (1 đ)

Câu 2

+ Dạng cài đặt danh sách bởi mảng: (0.5 đ)

Const n=maxlist;

Type list = record

Ele: array[1..n]of integer;

Count: 0..n;

end;

Var L: list;

+ Các thủ tục tương ứng với các yêu cầu:

1) Tính trung bình cộng của các số lưu trong danh sách (0.5 đ)

function Trungbinh(l:list): integer;

var i, tam: integer;

Begin

for i:=1 to n do tam:= tam+L.Ele[i];

Trungbinh:=tam;

End;

2) Loại bỏ số 3 đầu tiên tìm thấy trong danh sách (1 đ)

procedure Loaibo(var L: list);

var k,i:integer; found: boolean;

Begin

found:= false;

k:=1;

while (not found)and(k<=L.count) do

if(L.Ele[k]=3) then

begin

for i:=k to L.count-1 do L.Ele[i]:=L.Ele[i+1];

L.count:= L.count -1;

end;

if (not found) then writeln('So 3 khong co trong danh sách để loại bỏ');

End;

3) Hiển thị danh sách lên màn hình (1 đ)

procedure Hienthi(l:list);

var i: integer;

begin

writeln('Danh sách cac so nguyen la:');

for i:=1 to l.count do write(l.Ele[i]:6);

end;

Câu 3

Dựng cây: (0.5 đ)

1) Dạng cài đặt: (0.5 đ)

Type Tree=^nut;

Nut= record

Info: string;

Left, right: Tree;

End;

Var T: Tree;

2) Các thủ tục duyệt cây theo thứ tự trước, sau:

Giả sử xét cây gốc T, các thủ tục duyệt cây T

• Thủ tục duyệt cây theo thứ tự trước: (0.5 đ)

Procedure Preorder(T: Tree);

Begin

Write(T^.info);

Preorder(T^.left);

Preorder(T^.right);

End;

• Thủ tục duyệt cây T theo thứ tự sau: (0.5 đ)

Procedure postorder(T: Tree);

Begin

Postorder(T^.left);

Postorder(T^.right);

Write(T^.info);

End;

2) Biểu thức tiền tố , hậu tố và nhận xét:

b) + Biểu thức tiền tố: (0.5 đ)

+*34/+12b6 => Biểu thức trùng với kết quả duyệt cây theo thứ tự trước

+ Biểu thức hậu tố: (0.5 đ)

34*+12b+6/ => Biểu thức trùng với kết quả duyệt cây theo thứ tự sau