đề 5
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
Bạn đang đọc truyện trên: Truyen2U.Pro