Câu 1

1) Định nghĩa, tư tưởng, cài đặt ( 1 đ)

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

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).

+ Tư tưởng của bảng băm mở:

- 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ở

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

const N= ..

Type pointer = ^ ele;

Ele= Record

Key: keytype;

Next: pointer;

End;

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

Var T: Dictionary;

2) + Tìm xem trong từ điển T có chứa từ có khóa là x hay không? ( 1 đ)

Fuction member(x: keytype; T: dictionary): boolean;

Var p: pointer; found: boolean;

Begin

P:= T[h(x)];

Found:= false;

While p<>nil do

If p^.key=x then found:= true

Else p:=p^.next;

Member:= found;

End;

Câu 2

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

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

Type Pointer = ^ Member;

Member = Record

Id: 1..n;

Next : Pointer; // trỏ tới em liền kề

End;

Node = Record

Info: Integer;

Child: Pointer;

End;

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

Var T: Tree;

+ Dựng cây có 12 đỉnh và minh họa cách cài đặt trên bằng hình ảnh cụ thể với cây vừa dựng ( 1 đ)

+ Nêu cách tạo cây: ( 1 đ)

b1) Nhập gốc cây, lưu vào hàng đợi

b2) Lấy một đỉnh từ hàng đợi ra, nhập các con của nó, mỗi khi nhập một con, lại đưa con đó vào hàng đợi

b3) lặp đi lặp lại b2) cho đến khi hàng đợi rỗng. Ta thu được cây cần tạo