Câu 1

1) Khái niệm cây, cài đặt cây (1 đ)

+ Khái niệm cây: Cây là một đồ thị vô hướng liên thông phi chu trình

+ Cài đặt cây bằng danh sách cha của mỗi đỉnh:

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

Type Node = Record

Info: Item;

Parent: 0..n;

End;

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

Var T: Tree;

Trong đó:

- Info: Chứa thông tin của đỉnh

- Item: Kiểu dữ liệu của dữ liệu lưu tại đỉnh của cây

2) Viết hàm tìm số thứ tự của đỉnh là cha của đỉnh thứ k trên cây T (1 đ)

Procedure Tim(k: byte; T: Tree):0..n;

Begin

Parent := T[k].parent;

End;

Câu 2

+ Có hai phương pháp để xác định một tập hợp trong toán học: (0.5 đ)

- Liệt kê tất cả các phần tử trong tập hợp (nếu tập hợp đó là hữu hạn)

- Nêu lên các đặc trưng chung của các phần tử trong tập hợp

1) Viết dạng cài đặt tập hợp bởi véc tơ bít: (0.5 đ)

const n = <số phần tử tối đa trong tập hợp>;

type set = array[1..n] of boolean;

var A, B: Set;

2) Viết các thủ tục tương ứng với các yêu cầu:

a) Nhập giá trị cho tập A, B: (0.5 đ)

procedure Nhap(var A: set);

var i: integer; c: char;

Begin

Writeln('Nhap giá trj cho các phần tử của tập hợp!');

Repeat

Write('Nhap giá trị I = '); readln(i);

A[i]:= true;

Write('Co nhap nua khong? (c/k)'); read(c);

Until (c='k')or(c='K');

End;

Gọi thủ tục nhập trên, đối số truyền vào là B, để nhập dữ liệu cho tập B

b)Tìm hợp, giao, trừ của hai tập hợp A,B (0.5 đ)

* giao của A và B

procedure Giao(A,B: set; var C: set);

var i: integer;

Begin

For i:=1 to n do

C[i]:= A[i] and B[i];

End;

* Tìm hợp của A và B:

procedure Hop(A,B: set; var C: set);

var i: integer;

Begin

For i:=1 to n do

C[i]:= A[i]or B[i];

End;

* Tìm hiệu A\B

procedure Hieu(A,B: set; var C: set);

var i: integer;

Begin

For i:=1 to n do

C[i]:= A[i] and notB[i];

End;

a) Tìm x trong tập A: Cách làm: kiểm tra xem a[x] = true hay false, nếu = true, kết luận tìm thấy, ngược lại kết luận không tìm thấy (0.5 đ)

b) Thêm số nguyên x và tập hợp A: Đặt A[x]:= true; (0.5 đ)

c) Loại bỏ x ra khỏi tập hợp A: Đặt A[x]:= false; (0.5 đ)

3) Các phần tử trong tập hợp phải là các số nguyên hoặc được mã hóa bởi các số nguyên thì mới có thể cài đặt tập hợp bởi véc tơ bít (0.5 đ)

Câu 3

Tương tự câu 3 đề 12