Câu 1

+ Có thể cài đặt cây NPTK bởi con trỏ như sau: (0.5 đ)

Dạng cài đặt cây:

Type TreeBSearch = ^Nut;

Nut = Record

Infor: Integer;

Left, Right: TreeBSearch;

End;

Var T : TreeBSearch;

+ Dựng một cây NPTK có 13 nút, lưu các số nguyên chẵn, cây sau khi thêm đỉnh 13 như hình vẽ: (0.5 đ)

+ Thủ tục thêm đỉnh x= 13 vào cây T: Insert(x, T): (1 đ)

* 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

+ Kết quả duyệt cây theo thứ tự trước, giữa, sau: (1 đ)

- Trước: 26 14 8 2 10 13 16 40 36 32 30 34 28 42

- Giữa: 2 8 10 13 14 16 26 30 32 34 36 38 40 42

- Sau: 2 13 10 8 16 14 30 34 32 38 36 42 40 26

Câu 2

+ Dạng cài đặt từ điển bởi bảng băm đóng: (0.5 đ)

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

var T: dictionary;

+ Đụng khóa, giải quyết đụng khóa(1 đ)

- Dụng khóa xảy ra khi thêm một phần tử vào từ điển: Giả sử muồn thêm phần tử có khóa x và từ điển T, ta muốn đặt khóa x vào thành phần T[h(x)] của mảng, như ở vị trí đó đã lưu giữ một giá trị khóa khác, hoàn cảnh này còn gọi là sự va chạm (đụng khóa)

Ví dụ: N=10, các khóa a,b,c,d,e có các giá trị băm như sau: h(a)=7, h(b)=1, h(c)=4, h(d)=3, h(e)=3, Giả sử ban đầu bảng rỗng, tức là tất cả các thành phần của bảng đều chứa giá trị rỗng.ta đưa lần lượt các giá trị khóa a,b,c,d,e vào bảng, khi đó a,b,c,d lần lượt được đặt vào vị trí 7,1,4,3. Vì h(e)=3,ta tìm đến vị trí thứ 3 của mảng, ta thấy vị trí này đã chứa d => xẩy ra hiện tượng đụng khóa khi thêm e vào bảng.

- Khi xảy ra hiện tượng đụng khóa ta cần băm lại: ta lần lượt xét các vị trí h1(x), h2(x),.....hi(x) - băm lại lần thứ i cho đến khi nào tìm thấy vị trí trống để đặt x vào. Nếu không tìm được vị trí trống, ta nói bảng đã đầy không thể thêm x được nữa ,

+ Một số phương pháp băm lại: (1.5 đ)

a) Băm lại tuyến tính

Các hàm hi(x) được xác định như sau:

hi(x) = (h(x) = i ) mod N

Tức ta xem mảng là mảng vòng tròn và lần lượt xét đến các vị trí h(x)+1, h(x)+2, ......

b) Băm lại bình phương

hi(x) = (h(x) + i2) mod N

Câu 3

Tương tự câu 3 mã đề 04