Mã đề 23

Câu 1

+ Định nghĩa từ điển: (0.5 đ)

Mô hình dữ liệu tập hợp, nhưng chi xét đến các phép toán thêm, xóa, tìm kiếm được gọi là kiểu dữ liệu trừu tượng từ điển (dictionary).

+ Cài đặt từ điển bởi bảng băm mở: (0.5 đ)

const N= ..

Type pointer = ^ ele;

Ele= Record

Key: keytype;

Next: pointer;

End;

Dictionary = array[0..N-1] of pointer;

Var T: Dictionary;

+ Tư tưởng của bảng băm mở trong việc cài đặt từ điển: (0.5 đ)

- Phân chia tập hợp đã cho thành một số cố định các lớp(giả sử N lớp được đánh số từ 0 -> N-1)

- Sử dụng một mảng T có chỉ số chạy từ 0 đến N-1 để chứa các phần tử trong tập hợp, mỗi thành phần T[i] là một "rổ" đựng các phần tử thuộc lớp thứ I, các phần tư trong mỗi lớp được tổ chức thành một danh sách liên kết, T[i] là con trỏ trỏ tới phần tử đầu tiên trong lớp thứ i. T chính là bảng băm mở

+ Ví dụ: Tự cho (0.5 đ)

Câu 2

+ Cây bao gồm một tập hợp hữư hạn các đỉnh, giữa các đỉnh có một mối quan hệ gọi là quan hệ phân cấp cha - con (0.5 đ)

+ Cài đặt cây bởi con trưởng và em liền kề của mỗi đỉnh sử dụng mảng: (0.5 đ)

const n= 50;

type nut= record

eldest, nextsibling: 0..n;

infor:Item;

end;

tree=array[1..n]of nut;

var T: tree;

+ Vẽ một cây, minh hoạ bằng hình ảnh: (1 đ)

2 a 0

5 b 3

0 c 4

0 d 0

0 e 6

0 f 0

===>hình ảnh cây trong bộ nhớ:

+ Thủ tục tìm con trưởng của đỉnh k trên cây T: Contruong:=T[k].eldest; (1 đ)

+ Thủ tục tìm em liền kề của đỉnh thứ k trên cây T: Emlienke:=T[k].nextsibling; (1 đ)

Câu 3

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

b) Ghép L2 vào sau L1, L trỏ tới danh sách kết quả: (1 đ)

Procedure Ghep1(L1, L2, var L):

if (L2 = nil) then L:=L

else if(L1 = nil) then L:= L2

else Begin

M:=L1;

While(M^.next<>nil)do M:=M^.next;

M^.next := L2;

L:= L1;

End;

c) Ghép L3 vào trước L2, L1 vào sau L2, L trỏ tới danh sách kết quả(1 đ)

Procedure Ghep2(L1, L2, L3, var L):

Begin

Ghep1(L2, L1, M);

Ghep1(L3, M, L );

End;