Cho tập địa chỉ M = {0,1,2,3,4,5,6,7,8,9}, tập khóa K = {32, 53, 22, 92, 17, 34, 24, 37, 56}, và hàm băm h(k) = k%10.
a. Giải quyết đụng độ bằng phương pháp kết nối trực tiếp.
b. Giải quyết đụng độ bằng phương pháp dò tuyến tính.
Trả lời:
Đáp án đúng:
Câu hỏi yêu cầu áp dụng hai phương pháp giải quyết xung đột trong cấu trúc dữ liệu bảng băm: kết nối trực tiếp (separate chaining) và dò tuyến tính (linear probing).
a. Giải quyết đụng độ bằng phương pháp kết nối trực tiếp:
Phương pháp này sử dụng danh sách liên kết (hoặc một cấu trúc dữ liệu tương tự như mảng động) tại mỗi vị trí của bảng băm để lưu trữ các khóa có cùng giá trị băm. Khi xảy ra xung đột, khóa mới sẽ được thêm vào danh sách tại vị trí tương ứng.
Các bước thực hiện:
1. Khởi tạo một mảng (bảng băm) có kích thước bằng tập địa chỉ M, mỗi phần tử là một danh sách rỗng.
2. Với mỗi khóa trong tập K, tính giá trị băm h(k) = k % 10.
3. Thêm khóa vào danh sách tại vị trí tương ứng với giá trị băm.
Áp dụng với K = {32, 53, 22, 92, 17, 34, 24, 37, 56} và h(k) = k % 10:
- h(32) = 32 % 10 = 2. Thêm 32 vào danh sách tại index 2.
- h(53) = 53 % 10 = 3. Thêm 53 vào danh sách tại index 3.
- h(22) = 22 % 10 = 2. Xung đột tại index 2. Thêm 22 vào danh sách tại index 2 (ví dụ: 32 -> 22).
- h(92) = 92 % 10 = 2. Xung đột tại index 2. Thêm 92 vào danh sách tại index 2 (ví dụ: 32 -> 22 -> 92).
- h(17) = 17 % 10 = 7. Thêm 17 vào danh sách tại index 7.
- h(34) = 34 % 10 = 4. Thêm 34 vào danh sách tại index 4.
- h(24) = 24 % 10 = 4. Xung đột tại index 4. Thêm 24 vào danh sách tại index 4 (ví dụ: 34 -> 24).
- h(37) = 37 % 10 = 7. Xung đột tại index 7. Thêm 37 vào danh sách tại index 7 (ví dụ: 17 -> 37).
- h(56) = 56 % 10 = 6. Thêm 56 vào danh sách tại index 6.
Kết quả bảng băm (minh họa): index 2: [32, 22, 92], index 3: [53], index 4: [34, 24], index 7: [17, 37], index 6: [56]. Các index còn lại rỗng.
b. Giải quyết đụng độ bằng phương pháp dò tuyến tính:
Phương pháp này tìm kiếm vị trí trống tiếp theo trong bảng băm theo một trình tự tuyến tính (ví dụ: i+1, i+2, ...) khi xảy ra xung đột tại vị trí băm ban đầu. Công thức dò là h'(k, i) = (h(k) + i) % |M|, với i = 0, 1, 2, ...
Các bước thực hiện:
1. Khởi tạo một mảng (bảng băm) có kích thước bằng tập địa chỉ M, ban đầu rỗng.
2. Với mỗi khóa trong tập K, tính giá trị băm h(k) = k % 10.
3. Nếu vị trí h(k) trống, đặt khóa vào đó.
4. Nếu vị trí h(k) đã có khóa khác, tìm vị trí trống tiếp theo theo quy tắc dò tuyến tính.
Áp dụng với K = {32, 53, 22, 92, 17, 34, 24, 37, 56} và h(k) = k % 10:
- 32: h(32) = 2. Index 2 trống. Bảng: [_, _, 32, _, _, _, _, _, _, _]
- 53: h(53) = 3. Index 3 trống. Bảng: [_, _, 32, 53, _, _, _, _, _, _]
- 22: h(22) = 2. Index 2 có 32. Dò tuyến tính: (2+1)%10 = 3. Index 3 có 53. Dò tuyến tính: (2+2)%10 = 4. Index 4 trống. Bảng: [_, _, 32, 53, 22, _, _, _, _, _]
- 92: h(92) = 2. Index 2 có 32. Dò: (2+1)%10=3 (có 53). Dò: (2+2)%10=4 (có 22). Dò: (2+3)%10=5. Index 5 trống. Bảng: [_, _, 32, 53, 22, 92, _, _, _, _]
- 17: h(17) = 7. Index 7 trống. Bảng: [_, _, 32, 53, 22, 92, _, 17, _, _]
- 34: h(34) = 4. Index 4 có 22. Dò: (4+1)%10=5 (có 92). Dò: (4+2)%10=6. Index 6 trống. Bảng: [_, _, 32, 53, 22, 92, 34, 17, _, _]
- 24: h(24) = 4. Index 4 có 22. Dò: (4+1)%10=5 (có 92). Dò: (4+2)%10=6 (có 34). Dò: (4+3)%10=7 (có 17). Dò: (4+4)%10=8. Index 8 trống. Bảng: [_, _, 32, 53, 22, 92, 34, 17, 24, _]
- 37: h(37) = 7. Index 7 có 17. Dò: (7+1)%10=8 (có 24). Dò: (7+2)%10=9. Index 9 trống. Bảng: [_, _, 32, 53, 22, 92, 34, 17, 24, 37]
- 56: h(56) = 6. Index 6 có 34. Dò: (6+1)%10=7 (có 17). Dò: (6+2)%10=8 (có 24). Dò: (6+3)%10=9 (có 37). Dò: (6+4)%10=0. Index 0 trống. Bảng: [56, _, 32, 53, 22, 92, 34, 17, 24, 37]
Kết quả bảng băm cuối cùng:
Index 0: 56
Index 1: trống
Index 2: 32
Index 3: 53
Index 4: 22
Index 5: 92
Index 6: 34
Index 7: 17
Index 8: 24
Index 9: 37
Do câu hỏi có hai phần (a và b) và không có lựa chọn A, B, C, D để chọn đáp án đúng, nên không áp dụng 'answer_iscorrect'. Thay vào đó, đây là một câu hỏi tự luận yêu cầu trình bày cách giải chi tiết cho cả hai phần.
Đề thi kết thúc học phần môn Cấu trúc dữ liệu và giải thuật, bao gồm các câu hỏi về thuật toán sắp xếp Shell sort, cây AVL, hàm băm với các phương pháp giải quyết đụng độ, và ứng dụng cây nhị phân tìm kiếm (BST) để quản lý thông tin bàn trong một quán cà phê.
4 câu hỏi 90 phút
