Câu 1

+ Đệ quy: Một đối tượng được gọi là đệ quy nếu nó bao gồm chính nó như là một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó (0.5 đ)

+ Giải thuật đệ quy: là giải thuật có chứa lời giải đệ quy. Lời giải đệ quy là lời giải của bài toán T được thực hiện bởi lời giải của bài toán T' có dạng như T (cỡ của T'< T). Ví dụ: Tính n! (0.5 đ)

Câu 2

a) Tiêu chuẩn gốc ứng với trường hợp suy biến ở đây là m = 0, nếu m = 0 thì Acker(m,n) = n+1 (1 đ)

b) Ta có:

Acker (1,3) = Acker (0, Acker(1,2));

Acker (1,2) = Acker (0, Acker(1,1));

Acker (1,1) = Acker (0, Acker(1,0));

Acker (1,0) = Acker (0,1)=2;

Vậy => Acker (1,3) = 5 (1 đ)

c) Viết giải thuật để tính giá trị hàm Acker(m,n) (1 đ)

Function Acker(m,n: integer):integer;

Begin

If(m=0)then Acker:= n+1

Else

If(n=0)then Acker:=Acker(m-1,1)

Else Acker:= Acker(m-1, Acker(m,n-1));

End;

Câu 3

1) Dạng cài đặt danh sách: (0.5 đ)

Type Thisinh = Record

SDB, Hoten, Lop: String;

Toan, ly, hoa, ngoaingu: real;

End;

List = ^ node;

Node = Record

Info: Sinhvien;

Next: list;

End;

Var L: list

2) Các chương trình con

a) Nhập danh sách thí sinh (1 đ)

procedure taoDS(var l:list);

var M: hocsinh, SBD: string, i: integer;;

begin

write('nhap so bao danh của hoc sinh dau tiên, SBD = '); readln(SBD);

while SDB<>'' do

begin

i:=1;

writeln('Nhap hoc sinh thu i : ');

M^.info.SBD:=SBD;

write('Nhạp ho ten: '); readln(M^.info.Hoten);

write('Nhạp Lớp: '); readln(M^.info.lop);

write('Nhạp Điem toan: '); readln(M^.info.toan);

write('Nhạp Điemly: '); readln(M^.infor.ly);

write('Nhạp Điem hoa: '); readln(M^.infor.hoa);

write('Nhạp Điem NgoaiNgu: '); readln(M^.info.ngoaingu);

M^.next := L;

L:= M;

i:= i+1;

end;

end;

b) Sắp xếp thí sinh theo từng lớp, in danh sách sinh viên theo từng lớp: Tương tự ý c), d) câu 2 mã đề 01 (1 đ)

c) Loại bỏ tất cả các học sinh có điểm trung bình <5 ra khỏi danh sách, biết rằng điểm trung bình = (toan + ly+ hoa+ ngoaingu)/4: (1 đ)

Cách làm: b1) Tìm học sinh đầu tiên trong danh sách có điểm trung bình <5, giả sử vị trí k

b2) Loại bỏ học sinh ở vị trí k

b3) Lặp đi lặp lại b1); b2) cho đến khi hết vị trí tìm thấy

Chú ý: - để tìm học sinh thỏa mãn điều kiện ta duyệt từ đầu danh sách k:=1 đến khi tìm thấy thì dừng

- để loại bỏ học sinh ở vị trí k, ta di chuyển con trỏ p đến vị trí k, q đến vị trí trước K, thực hiện loại bỏ: q^.next:=p^.next; dispose(p);

d) tìm thí sinh theo số báo danh nhập vào: (0.5 đ)

- Nhập số báo danh cần tìm

- Duyệt từ đầu đến cuối danh sách mà vẫn không tìm thấy, hoặc duyệt đến khi tìm thấy thì dừng. Duyệt đến thí sinh nào thì so sánh số báo danh của thí sinh đó với số báo danh cần tìm, nếu bằng nhau thì kết luận tìm thấy, nếu không bằng nhau thì duyệt thí sinh tiếp theo trong danh sách