Câu 1

+ Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng, xác định một dãy các thao tác trên một số đối tượng nào(dữ liệu) đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn (0.5 đ)

+ Cách thức tổ chức biểu diễn dữ liệu mà theo đó dữ liệu được lưu trữ và được xử lý trong MTĐT, được gọi là cấu trúc dữ liệu (0.5 đ)

+ CTDL & GT đóng vai trò quan trọng trong việc giải quyết một bài toán, ta thấy:

CTDL+GT= chương trình

=> muốn viết được chương trình tốt ta phải có cấu trúc dữ liệu tốt và giải thuật tốt, không có CTDL, GT thì không có chương trình để giải quyết bài toán (0.5 đ)

+ Ví dụ: (0.5 đ)

Câu 2

a) Các giá trị của p, q, r được ghi nhận trong bảng sau: (1 đ)

p q r

1260 198 72

198 72 54

72 54 18

54 18 0

= > Vậy USCLN (1260, 198) = 18

b) (1 đ)

Ta thấy việc tính USCLN của p, q sẽ dẫn tới việc tính USCLN của q và r khi r ≠ 0 (q và r rõ ràng là nhỏ hơn p và q), thể hiện tính đệ quy trong cách tính. Công thức đệ quy là:

USCLN(p.q) =

c) Giải thuật đệ quy (1 đ)

Function USCLN1(p,q)

1. if ((p mod q)=0) then USCLN1 := q

else USCLN1 := USCLN1(q, p mod q);

d) Giải thuật lặp (1 đ)

Function USCLN2(p,q)

{x,y,z ở đây là các biến cục bộ}

1. x :=p; y:= q;

2. repeat

z := x mod y;

x := y;

y := z;

until z = 0;

3. USCLN1 := x;

Câu 3

1) Cài đặt cây bằng danh sách các con của mỗi đỉnh (1 đ)

* Dạng cài đặt

Const n= 50;

Type Member = Record

Id: 0..n;

Next:^Member;

End;

Node = Record

Infor: Item;

Child: ^Member;

End;

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

Var T: Tree;

Trong đó:

Id: Lưu chỉ danh của đỉnh;

Item: kiểu dữ liệu của thông tin lưu tại đỉnh

* Hình ảnh cây trên trong MT với cách cài đặt trên:

infor Child

15

10

21

12

31

45

9

..

..

2) Dựng cây NPTK từ cây trên: (1 đ)