Câu 1

+ Tác dụng của hàm băm h(hash function) : Phân chia các phần tử của tập hợp vào trong các lớp. Nếu x là giá trị khóa của môt phần tử nào đó của tập hợp thì h(x) là chỉ số nào đó của mảng T, h(x) được gọi là giá trị băm của x, ta nói x thuộc lớp h(x); (1 đ)

+ Các tiêu chuẩn để lựa chọn một hàm băm: (0.5 đ)

- Hàm băm phải cho phép tính được dễ dàng và nhanh chóng giá trị băm của mỗi khóa

- Phân bố đều các khóa vào các lớp

+ Một số phương pháp băm:

phương pháp băm gấp: (0.5 đ)

Giả sử khóa là số nguyên, ta phân chia khóa thành một số phần, sau đoa kết hợp các phần lại bằng một phương pháp nào đó(có thể dùng phép cộng hoặc phép nhân) để nhận được giá trị băm

Ví dụ: Nếu khóa là số nguyên gồm 10 chữ số, N= 1000, ta phân thành các nhóm 3,3,2,2 chữ số từ bên trái và công các nhòm lại, sau đó cắt cụt nếu cần thiết, ta sẽ nhận được giá trị băm 1229876087 được biến đổi thành: 122+987+60+87=1256, do ó ta có giá trị băm là: 256

Phương pháp băm cắt bỏ: (0.5 đ)

Giả sử khóa là số nguyên ( nếu khóa không là số nguyên ta xét đến mã của chúng). Ta sẽ bỏ đi một phần nào đó của khóa và lấy phần còn lại làm giá trị băm của khóa

Ví dụ:: Nếu khóa là số nguyên gồm 10 chữ số, N= 1000, ta lấy các chữ số thứ nhất, thứ 3, thứ 6 làm giá trị băm, giả sử khóa x= 1229876087 ta có h(x) = 126 là giá trị băm

Phương pháp băm lấy phần dư(0.5 đ)

Giả sử khóa là số nguyên, và giả sử ta muốn chia tập hợp các khóa thành N lớp. Ta chia khóa cho N, rồi lấy phần dư làm giá trị băm.

Ví dụ: Viết một hàm băm để băm các khóa là các xâu ký tự có độ dài 10 thành các giá trị từ 0 đến N-1

Type keytype= string[10];

Function h(x: keytype): 0..N-1;

Var I,sum:integer;

Begin

Sum:=0;

For i:=1 to 10 do Sum:=Sum+ord(x[i]);

H:= Sum mod N;

End;

Câu 2

+ Dạng cài đặt cây: (1 đ)

Type TreeBSearch = ^Nut;

Nut = Record

Infor: Integer;

Left, Right: TreeBSearch;

End;

Var T : TreeBSearch;

1) Tạo cây nhị phân tìm kiếm: (1 đ)

- Viết thủ tục thêm một đỉnh x vào cây T: Insert(x, T):

* Sử dụng con trỏ phụ M chứa địa chỉ của nút cần thêm

* Xin MT cấp phát ô nhớ cho M

* Đổ dữ liệu cần thêm vào ô nhớ có địa chỉ M

* Gắn M vào cây:

Nếu Cây rỗng (T = nil): T := M

Nếu cây không rỗng: Xác định vị trí thêm M:

If (x<T^.info) then Insert (x, T^.Left)

Else if (x>T^.info) then Insert(x, T^.right);

else thông báo x đã có trên cây

- Trong khi điều kiện nhập chưa thỏa mãn tính dừng (x<>0):

• Nhập dữ liệu mới cần thêm x,

• Liên tiếp gọi thủ tục thêm đỉnh mới vào cây: Insert(x,T);

2) Tìm xem trên cây T có nút chứa thông tin = x không: Search(x, T) (1 đ)

- Nhâp x = ?

- Nếu cây rỗng (T = nil): Thông báo không tìm thấy

- Nếu cây không rỗng:

a) Sử dụng con trỏ phụ M di chuyển đến các đỉnh trên cây bắt đầu từ gốc:

b) Nếu M^.info = x: thông báo tìm thấy(found := true), thoát

c) Nếu (x<M^.info) thì tìm x trên cây con trái của M: M := M^.Left, ngược lại tìm x trên cây con phải của M : M := M^.Right;

d) Phép di chuyển M kết thúc khi m = nil(duyệt hết cây mà vẫn không thấy) hoặc found = true (tìm thấy) thì dừng

3) Thủ tục loại bỏ đỉnh x = 39 ra khỏi cây sao cho cây sau khi laọi bỏ vẫn là cây NPTK: (1 đ)

- Tìm xem x có trên cây không:?

- Nếu không có thì thông báo và thoát khỏi chương trình

- Nếu x có trên cây:

• Di con trỏ P đến vị trí loại bỏ

• Nếu p không có con: giải phóng p

• Nếu p có 1 cây con khác rỗng: treo cây con khác rỗng vào vị trí loại bỏ, giải phóng p

• Nếu p có cả hai cây con khác rỗng: treo cây con trái vào vị trí trái nhất của cây con phải, treo cây con phải vào vị trí loại bỏ, giải phóng p

5) Hủy cây: Duyệt cây theo thứ tự sau để hủy các đỉnh có trên cây, Duyệt đến đỉnh nào gọi thủ tục loại bỏ đỉnh đó (1 đ)