Cho mảng gồm có các giá trị sau: 17, 72, 99, 32, 58, 70, 44, 12, 23, 32 Hãy trình bày chi tiết các bước sắp xếp mảng trên tăng dần bằng giải thuật shell sort.

Cho dãy số: 10, 6, 17, 3, 1, 5, 8, 9, 7, 15, 21, 19, 25

a. Vẽ cây nhị phân tìm kiếm cân bằng (AVL) tạo thành khi nhập lần lượt các số ở dãy trên.

b. Vẽ lại cây AVL khi xóa node có key 8.

Lời giải:

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 3:

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.

Lời giải:

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.

Câu 4:

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.

Lời giải:

Câu hỏi yêu cầu thiết kế và triển khai một chương trình quản lý thông tin bàn của quán cà phê sử dụng cấu trúc dữ liệu cây nhị phân tìm kiếm (BST). Các yêu cầu bao gồm nhập, xuất, đếm bàn có khách, tìm kiếm bàn theo mã, xuất bàn có khách và xóa bàn trống đã thanh toán. Việc sử dụng BST giúp tối ưu hóa các thao tác tìm kiếm và xóa, đặc biệt khi số lượng bàn lớn. Việc triển khai cần định nghĩa cấu trúc dữ liệu cho bàn, xây dựng các hàm tương ứng cho từng thao tác theo yêu cầu của BST và logic nghiệp vụ của quán cà phê. Cụ thể:

a. Nhập danh sách thông tin các bàn: Người dùng sẽ nhập thông tin cho từng bàn (Mã bàn, Trạng thái, Tên đồ uống, Số lượng, Đơn giá, Phương thức thanh toán). Mã bàn sẽ được sử dụng làm khóa để chèn vào BST. Trong quá trình chèn, cần cập nhật thông tin về thành tiền dựa trên số lượng và đơn giá.

b. Xuất danh sách thông tin các bàn: Duyệt cây BST theo thứ tự inorder (hoặc preorder/postorder tùy mục đích trình bày) để in ra thông tin của tất cả các bàn.

c. Đếm số lượng bàn có khách: Duyệt qua tất cả các nút trong cây BST. Tại mỗi nút, kiểm tra trạng thái của bàn. Nếu trạng thái là 'có khách sử dụng đồ uống', tăng biến đếm.

d. Tìm kiếm một bàn theo mã và trả về thông tin đầy đủ: Sử dụng thuật toán tìm kiếm trong BST. Bắt đầu từ gốc cây, so sánh mã bàn cần tìm với mã bàn tại nút hiện tại. Nếu bằng nhau, trả về thông tin bàn đó. Nếu nhỏ hơn, sang cây con trái. Nếu lớn hơn, sang cây con phải. Nếu hết cây mà không tìm thấy, thông báo không tìm thấy.

e. Xuất thông tin ra màn hình các bàn ở trạng thái có khách: Tương tự như đếm bàn có khách, nhưng thay vì đếm, chúng ta sẽ in thông tin chi tiết của bàn đó ra màn hình khi trạng thái là 'có khách sử dụng đồ uống'. Việc này đòi hỏi một phép duyệt cây.

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: Đây là thao tác phức tạp nhất. Cần duyệt cây để xác định các bàn thỏa mãn điều kiện xóa (trạng thái trống VÀ đã thanh toán tiền). Sau đó, thực hiện phép xóa nút trong BST cho từng bàn đó. Lưu ý rằng việc xóa nhiều nút trong BST có thể làm mất cân bằng cây, tuy nhiên, bài toán không yêu cầu duy trì cân bằng cây (ví dụ: AVL, Red-Black Tree).

Do đây là một bài toán lập trình yêu cầu triển khai cụ thể bằng mã nguồn, nên không có một đáp án trắc nghiệm duy nhất mà là một giải pháp lập trình hoàn chỉnh. Tuy nhiên, nếu câu hỏi được diễn đạt theo hướng lựa chọn phương án triển khai, thì đáp án đúng sẽ là phương án mô tả chính xác việc sử dụng BST và logic xử lý các yêu cầu trên.