Một quán cà phê có nhu cầu quản lý các bàn. Gồm các thông tin sau:

- Mã bàn.

- Trạng thái (trống/có khách sử dụng đồ uống).

- Tên đồ uống.

- Số lượng mỗi loại đồ uống có trên bàn.

- Đơn giá mỗi loại đồ uống.

- Thành tiền mỗi bàn.

- Phương thức thanh toán.

Sử dụng cấu trúc dữ liệu cây nhị phân tìm kiếm (BST), viết chương trình cho phép thực hiện các thao tác sau:

a. Nhập danh sách thông tin các bàn từ bàn phím.

b. Xuất danh sách thông tin các bàn ra màn hình.

c. Đếm số lượng bàn có khách.

d. Tìm kiếm một bàn theo mã và trả về thông tin đầy đủ.

e. Xuất thông tin ra màn hình các bàn ở trạng thái có khách.

f. Xóa tất cả các thông tin bàn ở trạng thái trống và đã thanh toán tiền.

Câu hỏi yêu cầu trình bày chi tiết các bước sắp xếp mảng số nguyên tăng dần bằng thuật toán Shell Sort. Mảng cho trước là: [17, 72, 99, 32, 58, 70, 44, 12, 23, 32].

Shell Sort là một cải tiến của Insertion Sort. Nó hoạt động bằng cách sắp xếp các cặp phần tử cách nhau một khoảng (gọi là gap) nhất định, sau đó giảm dần khoảng cách này cho đến khi khoảng cách bằng 1. Khi khoảng cách bằng 1, thuật toán trở thành Insertion Sort thông thường, nhưng lúc này mảng đã gần như được sắp xếp, do đó việc hoàn thành sắp xếp sẽ rất nhanh.

Các bước thực hiện với mảng [17, 72, 99, 32, 58, 70, 44, 12, 23, 32]:

1. Chọn các khoảng (gaps): Một chuỗi các khoảng phổ biến là n/2, n/4, n/8, ..., 1. Với n=10, ta có thể dùng chuỗi khoảng: 5, 2, 1.

2. Sắp xếp với gap = 5:
* So sánh và hoán vị các cặp (index i, index i+5).
* Cặp 1: (0, 5) -> (17, 70). 17 < 70, không đổi.
* Cặp 2: (1, 6) -> (72, 44). 72 > 44, hoán vị. Mảng: [17, 44, 99, 32, 58, 70, 72, 12, 23, 32]
* Cặp 3: (2, 7) -> (99, 12). 99 > 12, hoán vị. Mảng: [17, 44, 12, 32, 58, 70, 72, 99, 23, 32]
* Cặp 4: (3, 8) -> (32, 23). 32 > 23, hoán vị. Mảng: [17, 44, 12, 23, 58, 70, 72, 99, 32, 32]
* Cặp 5: (4, 9) -> (58, 32). 58 > 32, hoán vị. Mảng: [17, 44, 12, 23, 32, 70, 72, 99, 32, 58]
* Sau bước gap = 5: [17, 44, 12, 23, 32, 70, 72, 99, 32, 58]

3. Sắp xếp với gap = 2:
* Thực hiện sắp xếp Insertion Sort cho các mảng con cách nhau 2 phần tử.
* Mảng con 1 (chỉ số lẻ): [44, 23, 70, 99, 58]
* [44, 23] -> [23, 44]
* [44, 70] -> [44, 70]
* [70, 99] -> [70, 99]
* [99, 58] -> [58, 99]
* Mảng con 1 sau sắp xếp: [23, 44, 70, 58, 99]
* Mảng con 2 (chỉ số chẵn): [17, 12, 32, 72, 32]
* [17, 12] -> [12, 17]
* [17, 32] -> [17, 32]
* [32, 72] -> [32, 72]
* [72, 32] -> [32, 72]
* Mảng con 2 sau sắp xếp: [12, 17, 32, 32, 72]
* Ghép lại mảng: [12, 23, 17, 44, 32, 70, 32, 99, 72, 58]
* Sau bước gap = 2: [12, 23, 17, 44, 32, 70, 32, 99, 72, 58]

4. Sắp xếp với gap = 1:
* Đây là Insertion Sort trên mảng gần như đã sắp xếp: [12, 23, 17, 44, 32, 70, 32, 99, 72, 58]
* [12]
* [12, 23]
* [17, 23, 12] -> [12, 17, 23]
* [12, 17, 23, 44]
* [32, 44, 23, 17, 12] -> [12, 17, 23, 32, 44]
* [12, 17, 23, 32, 44, 70]
* [32, 70, 44, 32, 23, 17, 12] -> [12, 17, 23, 32, 32, 44, 70]
* [12, 17, 23, 32, 32, 44, 70, 99]
* [72, 99, 70, 44, 32, 32, 23, 17, 12] -> [12, 17, 23, 32, 32, 44, 70, 72, 99]
* [58, 72, 99, 70, 44, 32, 32, 23, 17, 12] -> [12, 17, 23, 32, 32, 44, 58, 70, 72, 99]
* Sau bước gap = 1: [12, 17, 23, 32, 32, 44, 58, 70, 72, 99]

Vì câu hỏi chỉ yêu cầu trình bày các bước thực hiện và không có đáp án trắc nghiệm đi kèm để đánh giá tính đúng sai, nên trường `answer_iscorrect` được đặt là "null" để thể hiện sự không áp dụng hoặc không có câu trả lời đúng sai cụ thể.

Câu hỏi này yêu cầu thực hiện hai thao tác trên cây nhị phân tìm kiếm cân bằng (AVL): chèn một dãy số và sau đó xóa một phần tử. Để trả lời, cần thực hiện các bước sau:

Phần a: Chèn các số vào cây AVL.

Ta sẽ chèn lần lượt các số vào cây và thực hiện các phép quay (LL, RR, LR, RL) khi cần thiết để duy trì tính cân bằng (hiệu độ cao giữa hai cây con của mỗi nút không quá 1).

1. Chèn 10: Cây có gốc là 10.
2. Chèn 6: 6 < 10, đặt 6 làm con trái của 10. Cây cân bằng.
3. Chèn 17: 17 > 10, đặt 17 làm con phải của 10. Cây cân bằng.
4. Chèn 3: 3 < 6, đặt 3 làm con trái của 6. Nút 10 mất cân bằng (hệ số cân bằng +2). Thực hiện phép quay Right trên 10. Cây mới có gốc là 6, con trái là 3, con phải là 10. Con phải của 10 là 17.
5. Chèn 1: 1 < 3, đặt 1 làm con trái của 3. Nút 10 mất cân bằng (hệ số cân bằng +2). Nút 6 mất cân bằng (hệ số cân bằng +2). Thực hiện phép quay Right trên 6. Cây mới có gốc là 3, con trái là 1, con phải là 6. Con phải của 6 là 10, con phải của 10 là 17.
6. Chèn 5: 5 > 3 và 5 < 6, đặt 5 làm con phải của 3. Nút 10 mất cân bằng (hệ số cân bằng -2). Nút 6 mất cân bằng (hệ số cân bằng -2). Thực hiện phép quay Left trên 10. Sau đó, nút 6 mất cân bằng (hệ số cân bằng -2). Thực hiện phép quay Left trên 6. Cây có gốc là 5, con trái là 3 (con trái là 1), con phải là 6 (con phải là 10, con phải của 10 là 17).
7. Chèn 8: 8 > 6 và 8 < 10, đặt 8 làm con trái của 10. Nút 10 mất cân bằng (hệ số cân bằng -2). Thực hiện phép quay Left trên 10. Cây có gốc là 8, con trái là 6 (con trái là 5, con trái của 5 là 3, con trái của 3 là 1), con phải là 17 (con trái là 15, con phải là 21).
8. Chèn 9: 9 > 8 và 9 < 10, đặt 9 làm con phải của 10. Nút 17 mất cân bằng (hệ số cân bằng +2). Nút 10 mất cân bằng (+2). Thực hiện phép quay Right trên 10. Cây có gốc là 9, con trái là 8 (con trái là 6, con trái của 6 là 5, con trái của 5 là 3, con trái của 3 là 1), con phải là 17 (con trái là 15, con phải là 21).
9. Chèn 7: 7 > 6 và 7 < 8, đặt 7 làm con phải của 6. Nút 10 mất cân bằng (-2). Nút 17 mất cân bằng (-2). Thực hiện phép quay Left trên 17. Cây có gốc là 9, con trái là 8 (con trái là 6, con trái của 6 là 5, con trái của 5 là 3, con trái của 3 là 1, con phải của 6 là 7), con phải là 15.
10. Chèn 15: 15 > 9 và 15 < 17, đặt 15 làm con trái của 17. Nút 17 mất cân bằng (+2). Nút 9 mất cân bằng (+2). Thực hiện phép quay Right trên 9. Cây có gốc là 15, con trái là 8 (con trái là 6, con trái của 6 là 5, con trái của 5 là 3, con trái của 3 là 1, con phải của 6 là 7), con phải là 17 (con trái là 16, con phải là 21).
11. Chèn 21: 21 > 15 và 21 > 17, đặt 21 làm con phải của 17. Nút 17 mất cân bằng (-2). Nút 15 mất cân bằng (-2). Thực hiện phép quay Left trên 17. Cây có gốc là 15, con trái là 8 (...), con phải là 21 (con trái là 17, con phải là 25).
12. Chèn 19: 19 > 17 và 19 < 21, đặt 19 làm con trái của 21. Nút 21 mất cân bằng (+2). Nút 17 mất cân bằng (+2). Thực hiện phép quay Right trên 21. Cây có gốc là 15, con trái là 8 (...), con phải là 19 (con trái là 17, con phải là 21, con phải của 21 là 25).
13. Chèn 25: 25 > 19 và 25 > 21, đặt 25 làm con phải của 21. Nút 19 mất cân bằng (-2). Nút 15 mất cân bằng (-2). Thực hiện phép quay Left trên 19. Cây có gốc là 15, con trái là 8 (...), con phải là 21 (con trái là 19, con trái của 19 là 17, con phải của 21 là 25).

Phần b: Xóa node có key 8.

Sau khi cây AVL được hình thành từ phần a, ta tiến hành xóa nút 8. Việc xóa một nút có thể làm mất cân bằng cây.

* Tìm nút 8. Nút 8 là con trái của nút 9.
* Vì 8 có hai con (là 6 và 7), ta tìm phần tử nhỏ nhất ở cây con bên phải của 8, đó là 6. Tuy nhiên, 6 có con phải là 7. Do đó, ta sẽ tìm phần tử nhỏ nhất ở cây con bên phải của 8. Tìm cây con bên phải của 8: nút 9. Cây con bên phải của 8 là cây con của 9. Phần tử nhỏ nhất ở cây con bên phải của 8 không tồn tại vì 8 không có cây con bên phải trực tiếp. Theo quy tắc xóa, nếu nút có hai con, ta thay thế nó bằng phần tử nhỏ nhất của cây con bên phải (hoặc lớn nhất của cây con bên trái).

Để chính xác hơn, ta tìm phần tử nhỏ nhất ở cây con bên phải của 8. Cây con bên phải của 8 bắt đầu từ 9. Cây con bên phải của 8 là: 9 (con trái là 7), 15, 17, 19, 21, 25. Phần tử nhỏ nhất là 7.

Thay thế 8 bằng 7. Sau đó xóa 7 khỏi vị trí ban đầu.

* Ban đầu, cây có gốc là 15. Cây con trái của 15 là 8 (con trái 6, con trái 5, con trái 3, con trái 1, con phải 7), con phải là 21 (con trái 19, con trái 17, con phải 25).
* Ta xóa 8, thay thế nó bằng phần tử nhỏ nhất của cây con bên phải của 8. Cây con bên phải của 8 không tồn tại. Cây con bên trái của 8 có 6 (con trái 5, con trái 3, con trái 1) và 7 (con phải của 6).

Quy tắc xóa: Nếu nút cần xóa có hai con, thay thế nút đó bằng phần tử nhỏ nhất của cây con bên phải của nó. Phần tử nhỏ nhất của cây con bên phải của 8 là 9. Tuy nhiên, 9 không phải là con trực tiếp của 8.

Trong trường hợp này, ta tìm phần tử nhỏ nhất của cây con bên phải của 8. Cây con bên phải của 8 là cây con của 9. Do đó ta tìm phần tử nhỏ nhất của cây con của 9. Cây con của 9 bao gồm 7. Vậy ta thay 8 bằng 7.

Sau khi xóa 8, cây có thể mất cân bằng. Cần kiểm tra và thực hiện các phép quay nếu cần.

Cây AVL cuối cùng sau khi chèn: Gốc 15. Con trái: 6 (con trái 5, con trái 3, con trái 1, con phải 7). Con phải: 21 (con trái 19, con trái 17, con phải 25).

Xóa 8: Nút 8 không còn trong cây. Cây sẽ có cấu trúc mới và có thể cần cân bằng lại.

Do yêu cầu là vẽ, nên đáp án sẽ là hình ảnh của cây.

* Sau khi chèn: Gốc 15. Con trái: 6 (con trái 5, con trái 3, con trái 1, con phải 7). Con phải: 21 (con trái 19, con trái 17, con phải 25).
* Sau khi xóa 8: Nút 8 không còn. Ta tìm phần tử nhỏ nhất ở cây con bên phải của 8. Cây con bên phải của 8 là cây con bắt đầu từ 9. Cây con này bao gồm 7. Vì vậy, 7 sẽ thay thế 8. Sau đó, ta xóa 7 khỏi vị trí cũ. Cây có gốc là 15. Cây con trái của 15 là 6 (con trái 5, con trái 3, con trái 1, con phải 7). Cây con phải của 15 là 21 (con trái 19, con trái 17, con phải 25). Cây vẫn cân bằ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.