JavaScript is required
Danh sách đề

Đề thi học kì 2 môn Cấu trúc dữ liệu và giải thuật có đáp án chi tiết - Đề 1

5 câu hỏi 90 phút

Thẻ ghi nhớ
Nhấn để lật thẻ
1 / 5

Hãy cho biết độ phức tạp của thuật toán Insertion sort (chèn trực tiếp) theo định nghĩa Big-O (O lớn).

b. Viết hàm sắp xếp mảng 1 chiều gồm N phần tử giảm dần với thuật toán Insertion sort.

c. Hãy cho biết dãy số sẽ thay đổi qua từng bước như thế nào khi áp dụng thuật toán ở câu 1b, biết rằng dãy số cho như sau: 3, 8, 4, 5, 9, 1, 2, 6

Đáp án
Đáp án đúng:
Thuật toán Sắp xếp chèn (Insertion Sort) có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất và trung bình, do trong mỗi lần chèn một phần tử, ta có thể phải duyệt qua tất cả các phần tử đã được sắp xếp trước đó để tìm vị trí thích hợp. Trong trường hợp tốt nhất (mảng đã sắp xếp), độ phức tạp là O(n). Để sắp xếp mảng giảm dần, ta cần thay đổi điều kiện so sánh trong vòng lặp `while` từ `key < arr[j]` sang `key > arr[j]` (trong trường hợp tăng dần) để đảm bảo các phần tử lớn hơn được dịch sang phải, tạo không gian cho phần tử hiện tại được chèn vào đúng vị trí để có thứ tự giảm dần. Minh họa từng bước với dãy `3, 8, 4, 5, 9, 1, 2, 6` cho việc sắp xếp giảm dần như sau:

1. Khởi tạo: Mảng con đã sắp xếp `[3]`. Phần tử đang xét: `8`.
* `8 > 3`. Chèn `8` vào sau `3`. Mảng con: `[8, 3]`.
2. Phần tử đang xét: `4`.
* `4 < 8`. `4 > 3`. Chèn `4` vào giữa `8` và `3`. Mảng con: `[8, 4, 3]`.
3. Phần tử đang xét: `5`.
* `5 < 8`. `5 > 4`. Chèn `5` vào giữa `8` và `4`. Mảng con: `[8, 5, 4, 3]`.
4. Phần tử đang xét: `9`.
* `9 > 8`. Chèn `9` vào đầu. Mảng con: `[9, 8, 5, 4, 3]`.
5. Phần tử đang xét: `1`.
* `1 < 9`, `1 < 8`, `1 < 5`, `1 < 4`, `1 < 3`. Chèn `1` vào giữa `3` và `2`. Mảng con: `[9, 8, 5, 4, 3, 1]`.
6. Phần tử đang xét: `2`.
* `2 < 9`, `2 < 8`, `2 < 5`, `2 < 4`, `2 < 3`. `2 > 1`. Chèn `2` vào giữa `3` và `1`. Mảng con: `[9, 8, 5, 4, 3, 2, 1]`.
7. Phần tử đang xét: `6`.
* `6 < 9`, `6 < 8`. `6 > 5`. Chèn `6` vào giữa `8` và `5`. Mảng con: `[9, 8, 6, 5, 4, 3, 2, 1]`.

Kết quả cuối cùng là mảng được sắp xếp giảm dần: `[9, 8, 6, 5, 4, 3, 2, 1]`.

Trắc nghiệm nổi bật:

100+ câu trắc nghiệm Quản trị chất lượng dịch vụ có lời giải chi tiết - Phần 1

50 câu hỏi 60 phút

100+ câu trắc nghiệm Quản trị chất lượng dịch vụ có lời giải chi tiết - Phần 2

45 câu hỏi 60 phút

100+ câu trắc nghiệm tổng hợp Tái lập doanh nghiệp có đáp án - Phần 1

50 câu hỏi 60 phút

100+ câu trắc nghiệm tổng hợp Tái lập doanh nghiệp có đáp án - Phần 2

22 câu hỏi 60 phút

300+ câu trắc nghiệm Văn hóa doanh nghiệp kèm đáp án đúng theo chuẩn chương trình - Phần 1

50 câu hỏi 60 phút

300+ câu trắc nghiệm Văn hóa doanh nghiệp kèm đáp án đúng theo chuẩn chương trình - Phần 2

50 câu hỏi 60 phút

300+ câu trắc nghiệm Văn hóa doanh nghiệp kèm đáp án đúng theo chuẩn chương trình - Phần 3

50 câu hỏi 60 phút

300+ câu trắc nghiệm Văn hóa doanh nghiệp kèm đáp án đúng theo chuẩn chương trình - Phần 4

50 câu hỏi 60 phút

300+ câu trắc nghiệm Văn hóa doanh nghiệp kèm đáp án đúng theo chuẩn chương trình - Phần 5

50 câu hỏi 60 phút

300+ câu trắc nghiệm Văn hóa doanh nghiệp kèm đáp án đúng theo chuẩn chương trình - Phần 6

50 câu hỏi 60 phút

Danh sách câu hỏi:

Câu 1:

Hãy cho biết độ phức tạp của thuật toán Insertion sort (chèn trực tiếp) theo định nghĩa Big-O (O lớn).

b. Viết hàm sắp xếp mảng 1 chiều gồm N phần tử giảm dần với thuật toán Insertion sort.

c. Hãy cho biết dãy số sẽ thay đổi qua từng bước như thế nào khi áp dụng thuật toán ở câu 1b, biết rằng dãy số cho như sau: 3, 8, 4, 5, 9, 1, 2, 6.

Lời giải:
Thuật toán Sắp xếp chèn (Insertion Sort) có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất và trung bình, do trong mỗi lần chèn một phần tử, ta có thể phải duyệt qua tất cả các phần tử đã được sắp xếp trước đó để tìm vị trí thích hợp. Trong trường hợp tốt nhất (mảng đã sắp xếp), độ phức tạp là O(n). Để sắp xếp mảng giảm dần, ta cần thay đổi điều kiện so sánh trong vòng lặp `while` từ `key < arr[j]` sang `key > arr[j]` (trong trường hợp tăng dần) để đảm bảo các phần tử lớn hơn được dịch sang phải, tạo không gian cho phần tử hiện tại được chèn vào đúng vị trí để có thứ tự giảm dần. Minh họa từng bước với dãy `3, 8, 4, 5, 9, 1, 2, 6` cho việc sắp xếp giảm dần như sau:

1. Khởi tạo: Mảng con đã sắp xếp `[3]`. Phần tử đang xét: `8`.
* `8 > 3`. Chèn `8` vào sau `3`. Mảng con: `[8, 3]`.
2. Phần tử đang xét: `4`.
* `4 < 8`. `4 > 3`. Chèn `4` vào giữa `8` và `3`. Mảng con: `[8, 4, 3]`.
3. Phần tử đang xét: `5`.
* `5 < 8`. `5 > 4`. Chèn `5` vào giữa `8` và `4`. Mảng con: `[8, 5, 4, 3]`.
4. Phần tử đang xét: `9`.
* `9 > 8`. Chèn `9` vào đầu. Mảng con: `[9, 8, 5, 4, 3]`.
5. Phần tử đang xét: `1`.
* `1 < 9`, `1 < 8`, `1 < 5`, `1 < 4`, `1 < 3`. Chèn `1` vào giữa `3` và `2`. Mảng con: `[9, 8, 5, 4, 3, 1]`.
6. Phần tử đang xét: `2`.
* `2 < 9`, `2 < 8`, `2 < 5`, `2 < 4`, `2 < 3`. `2 > 1`. Chèn `2` vào giữa `3` và `1`. Mảng con: `[9, 8, 5, 4, 3, 2, 1]`.
7. Phần tử đang xét: `6`.
* `6 < 9`, `6 < 8`. `6 > 5`. Chèn `6` vào giữa `8` và `5`. Mảng con: `[9, 8, 6, 5, 4, 3, 2, 1]`.

Kết quả cuối cùng là mảng được sắp xếp giảm dần: `[9, 8, 6, 5, 4, 3, 2, 1]`.

Câu 2:

Cho dãy ký tự như sau: R, E, T, A, V, X, L, G, S, I

Hãy thực hiện các yêu cầu sau:

a. Vẽ cây nhị phân tìm kiếm bằng cách thêm lần lượt từng ký tự vào cây theo thứ tự từ trái qua phải của dãy ký tự trên, biết rằng giá trị của từng ký tự tương ứng theo thứ tự xuất
hiện của ký tự trong từ điển.

b. Cho biết kết qủa duyệt cây theo RNL, NRL.

c. Huỷ lần lượt từng nút L, T, E, R trên cây, mỗi lần huỷ 1 nút vẽ lại cây nối tiếp theo như thứ tự huỷ.
 

Lời giải:
Câu hỏi này yêu cầu thực hiện các thao tác trên cây nhị phân tìm kiếm (Binary Search Tree - BST), bao gồm xây dựng cây từ một dãy ký tự, duyệt cây theo các thứ tự khác nhau (RNL, NRL), và thực hiện các thao tác xóa nút trên cây. Để trả lời đầy đủ câu hỏi này, người học cần nắm vững các khái niệm sau:

1. Cây nhị phân tìm kiếm (BST): Định nghĩa, quy tắc xây dựng (mỗi nút con trái nhỏ hơn nút cha, mỗi nút con phải lớn hơn nút cha). Giá trị của ký tự được xác định theo thứ tự xuất hiện trong từ điển. Giả sử bảng chữ cái tiếng Anh là cơ sở để xác định giá trị.
* R -> 18
* E -> 5
* T -> 20
* A -> 1
* V -> 22
* X -> 24
* L -> 12
* G -> 7
* S -> 19
* I -> 9

2. Xây dựng BST: Thêm lần lượt các phần tử vào cây theo thứ tự cho trước.
* Thêm R (18): R là nút gốc.
* Thêm E (5): 5 < 18, E là con trái của R.
* Thêm T (20): 20 > 18, T là con phải của R.
* Thêm A (1): 1 < 18 (R), 1 < 5 (E), A là con trái của E.
* Thêm V (22): 22 > 18 (R), 22 > 20 (T), V là con phải của T.
* Thêm X (24): 24 > 18 (R), 24 > 20 (T), 24 > 22 (V), X là con phải của V.
* Thêm L (12): 12 < 18 (R), 12 > 5 (E), 12 < 20 (T), L là con trái của T.
* Thêm G (7): 7 < 18 (R), 7 > 5 (E), 7 < 20 (T), 7 < 12 (L), G là con trái của L.
* Thêm S (19): 19 > 18 (R), 19 > 20 (T), 19 < 22 (V), S là con trái của V.
* Thêm I (9): 9 < 18 (R), 9 > 5 (E), 9 < 20 (T), 9 > 12 (L), 9 > 7 (G), I là con phải của G.

Cây sau khi thêm là:
R(18)
/ \
E(5) T(20)
/ / \
A(1) L(12) V(22)
/ / \
G(7) S(19) X(24)
/ \
I(9)

3. Duyệt cây:
* RNL (Root-Node-Left): Thứ tự duyệt thường gặp là NLR (Node-Left-Right), LNR (Left-Node-Right), LRN (Left-Right-Node), RLN (Right-Left-Node), RNL (Right-Node-Left), RNL (Right-Node-Left), RNL (Right-Node-Left), RNL (Right-Node-Left). Tuy nhiên, RNL không phải là một thứ tự duyệt cây nhị phân chuẩn và có thể là một cách diễn đạt sai hoặc ít dùng. Nếu hiểu RNL là duyệt gốc trước, sau đó duyệt cây con bên phải rồi mới đến cây con bên trái, thì thứ tự sẽ là: R, T, V, X, S, E, A, L, G, I. Nếu RNL được hiểu theo cách khác, cần làm rõ.
* NRL (Node-Right-Left): Tương tự, NRL cũng không phải là một thứ tự duyệt cây nhị phân chuẩn. Nếu hiểu NRL là duyệt gốc trước, sau đó duyệt cây con bên phải rồi mới đến cây con bên trái, thì thứ tự sẽ là: R, T, V, X, S, E, A, L, G, I. Tuy nhiên, nếu quy ước duyệt theo chiều sâu (depth-first) với thứ tự gốc, phải, trái thì đó là RNR N, sau đó mới đến L N. RNL và NRL có thể là cách viết tắt của các thuật toán duyệt cây. Giả sử RNL có nghĩa là duyệt gốc, rồi đến cây con bên phải, rồi đến cây con bên trái. NRL có nghĩa là duyệt gốc, rồi đến cây con bên trái, rồi đến cây con bên phải. Nếu RNL là Root-Right-Left và NRL là Node-Right-Left. Giả sử đề bài muốn hỏi theo thứ tự duyệt cây "Right-Node-Left" và "Node-Right-Left". Tuy nhiên, các thứ tự duyệt cây chuẩn là NLR, LNR, LRN, RNL, RLN, NRN, NLR, LRN. Nếu RNL là Right-Node-Left và NRL là Node-Right-Left thì sẽ có sự khác biệt. Với RNL (Right-Node-Left): R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), A(1), E(5). Với NRL (Node-Right-Left) ta có thể hiểu là duyệt nút gốc, rồi duyệt cây con bên phải, rồi duyệt cây con bên trái. R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
Nếu RNL là duyệt gốc, cây con phải, cây con trái và NRL là duyệt gốc, cây con trái, cây con phải.
RNL: R, T, V, X, S, E, A, L, G, I
NRL: R, E, A, L, G, I, T, V, X, S.
Tuy nhiên, đề bài chỉ ghi RNL, NRL. RNL có thể là Right-Node-Left (Duyệt nút gốc, rồi cây con phải, rồi cây con trái). NRL không có chuẩn như vậy. Giả sử đề bài nhầm và muốn hỏi các thứ tự duyệt phổ biến như NLR, LNR. Tuy nhiên, ta phải tuân thủ đề bài. Nếu coi RNL và NRL là hai thứ tự duyệt cây cụ thể, thì ta sẽ thực hiện theo đúng quy tắc đó.
RNL (Root-Node-Left) có thể hiểu là: Gốc -> Cây con phải -> Cây con trái. Duyệt R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
NRL (Node-Right-Left) có thể hiểu là: Gốc -> Cây con phải -> Cây con trái. Đây là cùng một thứ tự như RNL. Điều này rất có thể là lỗi đề bài.
Giả sử RNL là Right-Node-Left (Cây con phải, Gốc, Cây con trái): S, X, V, T, I, G, L, A, E, R. NRL (Node-Right-Left) không có chuẩn.
Nếu RNL là Root-Right-Left và NRL là Node-Right-Left thì RNL sẽ là: R, T, V, X, S, L, G, I, E, A. NRL có thể hiểu là duyệt nút gốc, sau đó duyệt cây con bên phải, rồi cây con bên trái. R, T, V, X, S, L, G, I, E, A.
Nếu ta coi RNL là thứ tự duyệt: Root, Right, Left. Và NRL là thứ tự duyệt: Node, Right, Left.
RNL: R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
NRL: R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
Hai thứ tự này giống nhau.
Nếu đề bài muốn hỏi NLR, LNR thì sẽ khác:
NLR: R, E, A, T, L, G, I, V, S, X.
LNR: A, E, R, G, I, L, T, S, V, X.

Giả định RNL là duyệt Root-Then-Right-Then-Left và NRL là duyệt Node-Then-Right-Then-Left.
RNL: R -> T -> V -> X -> S -> L -> G -> I -> E -> A.
NRL: R -> T -> V -> X -> S -> L -> G -> I -> E -> A.
Nếu ta hiểu RNL là Right-Node-Left và NRL là Node-Right-Left, thì hai thứ tự duyệt này sẽ giống nhau.

4. Xóa nút trên cây: Các trường hợp xóa nút:
* Nút không có con.
* Nút có một con.
* Nút có hai con (thay thế bằng nút nhỏ nhất của cây con phải hoặc nút lớn nhất của cây con trái).

* Xóa L (12): L có một con là G.
Cây sau khi xóa L:
R(18)
/ \
E(5) T(20)
/ / \
A(1) G(7) V(22)
/ / \
I(9) S(19) X(24)

* Xóa T (20): T có hai con là G và V. Ta sẽ thay T bằng nút nhỏ nhất của cây con phải của T, đó là S (19).
Cây sau khi xóa T:
R(18)
/ \
E(5) S(19)
/ / \
A(1) G(7) V(22)
/ / \
I(9) X(24)

* Xóa E (5): E có một con là A.
Cây sau khi xóa E:
R(18)
/ \
A(1) S(19)
/ \
G(7) V(22)
/ / \
I(9) X(24)

* Xóa R (18): R là nút gốc, có hai con là A và S. Ta thay R bằng nút nhỏ nhất của cây con phải của R, đó là G (7).
Cây sau khi xóa R:
G(7)
/ \
A(1) S(19)
/ \
I(9) V(22)
/ \
X(24)

Vì câu hỏi không cung cấp đáp án để chọn (answer_iscorrect), nên ta sẽ tập trung vào việc giải thích chi tiết quy trình.

Câu 3:

Cho biết cây B-Tree bậc 3 là một cây thỏa mãn các tính chất sau:

  • Tất cả node lá nằm trên cùng một mức
  • Tất cả các node, trừ node gốc và node lá, có *tối thiểu* 2 node con.
  • Tất cả các node có *tối đa* 3 con
  • Tất cả các node, trừ node gốc, có từ 1 cho đến 2 khóa (keys)
  • Một node không phải lá và có n khóa thì phải có n+1 node con.

Hãy thực hiện các yêu cầu sau:

3.1 Cho dãy số: 12, 17, 20, 23, 15, 11, 24, 13, 19, 22, 18, 21, 16. Hỏi khi lần lượt thêm các số trong dãy theo thứ tự từ trái qua phải vào một cây B-Tree bậc 3 rỗng thì:

a. Các khóa nào khi thêm vào cây sẽ làm phát sinh thao tác tách (split) node? 

b. Vẽ cây B-Tree trước và sau khi thêm các khóa ở câu a.

3.2 Cho cây B-Tree bậc 3 như hình sau:

Hãy lần lượt tiến hành xóa các khóa sau khỏi cây: 13, 24, 19 và vẽ cây B-Tree trước và sau khi xóa mỗi khóa trên.

Lưu ý khi xoá:

- Khi khóa cần xóa (gọi là x) không nằm ở node lá, chọn khóa thế mạng là khóa có giá trị lớn nhất mà nhỏ hơn x.

- Thao tác nhường khoá (underflow) sẽ được thực hiện khi hai node liền kề có tổng số khóa >= 2. Khi có một node không còn đáp ứng đủ số lượng khóa tối thiểu, ưu tiên thực hiện underflow thay cho catenation (hợp) vì thao tác này không làm thay đổi số khóa của node cha.

- Khi có 02 lựa chọn node liền kể để thực hiện catenation, ưu tiên chọn catenation giữa node bị thiếu khóa với node liền trước.

Lời giải:
Câu hỏi này yêu cầu thực hiện các thao tác thêm và xóa trên cây B-Tree bậc 3.

Phần 3.1: Thêm các khóa vào cây B-Tree bậc 3 rỗng.

Một cây B-Tree bậc 3 có tối đa 3 con, nghĩa là mỗi nút có thể chứa tối đa 2 khóa.

Ta sẽ lần lượt thêm các số: 12, 17, 20, 23, 15, 11, 24, 13, 19, 22, 18, 21, 16.

1. Thêm 12: Cây: [12]
2. Thêm 17: Cây: [12, 17]
3. Thêm 20: Nút [12, 17] đầy, thêm 20 thành [12, 17, 20]. Tách nút: 17 lên làm gốc. Cây: [17] với con trái [12] và con phải [20]. *(Khóa gây tách: 20)*
4. Thêm 23: Thêm vào nút [20]. Cây: [17], [12], [20, 23]
5. Thêm 15: Thêm vào nút [12]. Cây: [17], [12, 15], [20, 23]
6. Thêm 11: Thêm vào nút [12, 15] thành [11, 12, 15]. Tách nút: 12 lên làm cha. Cây: [12, 17], [11], [15], [20, 23]. *(Khóa gây tách: 11)*
7. Thêm 24: Thêm vào nút [20, 23] thành [20, 23, 24]. Tách nút: 23 lên làm cha. Cây: [12, 17, 23], [11], [15], [20], [24]. *(Khóa gây tách: 24)*. Nút gốc [12, 17, 23] đầy, tách nút: 17 lên làm gốc mới. Cây: [17], [12], [23], [11], [15], [20], [24]. *(Khóa gây tách: 23)*
8. Thêm 13: Thêm vào nút [15]. Cây: [17], [12], [23], [11], [13, 15], [20], [24].
9. Thêm 19: Thêm vào nút [20]. Cây: [17], [12], [23], [11], [13, 15], [19, 20], [24].
10. Thêm 22: Thêm vào nút [23]. Cây: [17], [12], [22, 23], [11], [13, 15], [19, 20], [24].
11. Thêm 18: Thêm vào nút [19, 20] thành [18, 19, 20]. Tách nút: 19 lên làm cha. Cây: [17, 19], [12], [22, 23], [11], [13, 15], [18], [20], [24]. *(Khóa gây tách: 18)*
12. Thêm 21: Thêm vào nút [20]. Cây: [17, 19], [12], [22, 23], [11], [13, 15], [18], [20, 21], [24].
13. Thêm 16: Thêm vào nút [13, 15] thành [13, 15, 16]. Tách nút: 15 lên làm cha. Cây: [15, 17, 19], [12], [22, 23], [11], [13], [16], [18], [20, 21], [24]. *(Khóa gây tách: 16)*. Nút gốc [15, 17, 19] đầy, tách nút: 17 lên làm gốc mới. Cây: [17], [15], [19], [12], [22, 23], [11], [13], [16], [18], [20, 21], [24]. *(Khóa gây tách: 16)*.

a. Các khóa làm phát sinh thao tác tách node: 20, 11, 24, 23, 18, 16.
b. Cần vẽ lại cây tại mỗi bước có tách node.

Phần 3.2: Xóa các khóa khỏi cây B-Tree bậc 3 cho trước.

Cây B-Tree ban đầu:
* Gốc: [17, 25]
* Cây con trái của 17: [10, 14]
* Cây con giữa 17 và 25: [19, 22]
* Cây con phải của 25: [28, 30]
* Các nút lá con: [6, 8], [11, 12] (dưới [10, 14]); [18], [20, 21] (dưới [19, 22]); [27], [29] (dưới [28, 30]).

a. Xóa 13:
* Khóa 13 không có trong cây. Cây không thay đổi.
* Cây trước khi xóa: Như cây ban đầu.
* Cây sau khi xóa: Như cây ban đầu.

b. Xóa 24:
* Khóa 24 không có trong cây. Cây không thay đổi.
* Cây trước khi xóa: Như cây ban đầu.
* Cây sau khi xóa: Như cây ban đầu.

c. Xóa 19:
* 19 nằm ở gốc [17, 25].
* Tìm khóa thế mạng lớn nhất nhỏ hơn 19: là 18 (từ nút lá [18]).
* Thay 19 bằng 18 ở gốc. Gốc: [17, 18, 25].
* Xóa 18 khỏi nút lá [18]. Nút này còn trống.
* Xử lý underflow: Nút [18] trống. Node cha là [17, 18, 25]. Nút trống là con thứ 3.
* Xét anh em bên trái: nút [20, 21] (con thứ 4 của 25).
* Nhường khóa: Nút cha [17, 18, 25] nhường 18 xuống. Gốc thành [17, 25]. Khoá 18 đi xuống.
* Nút trống [18] nhận 18, trở thành [18].
* Nhường từ anh em: Nút [20, 21] nhường 20 lên. Nút [20, 21] còn [21].
* Cha [17, 25] nhận 20 lên. Cha thành [17, 20, 25].
* Cây sau khi xóa 19:
* Gốc: [17, 20, 25]
* Cây con 17: [10, 14]
* Cây con 20: [19, 22]
* Cây con 20: [18]
* Cây con 25: [21]
* Cây con 25: [28, 30]
* Các lá dưới [10, 14]: [6, 8], [11, 12]
* Các lá dưới [19, 22]: [18] (nơi 18 bị xóa, giờ là nút lá)
* Các lá dưới [28, 30]: [27], [29].

Lưu ý quan trọng: Với các thao tác vẽ cây, cần thể hiện rõ ràng cấu trúc của cây sau mỗi bước có thay đổi.

Câu 4:

Để việc tìm kiếm thông tin mặt hàng được nhanh chóng, người ta dùng một bảng băm theo phương pháp thăm dò, làm việc trên mã quản lý của mặt hàng. Mã quản lý này là một con số nguyên. Bảng băm có:

- Hàm băm: h(key) = (key % M)

- Hàm băm lại (hàm thăm dò): prob(key, i) = (h(key) + i*i + i) % M

Trong đó:

- key là giá trị khóa.

- i là một số nguyên cho biết lần băm lại (thăm dò) thứ i.

- M là kích thước bảng băm.

Giả sử M = 7, cho trường hợp T của bảng băm đã chứa dữ liệu như bên dưới. Biết “-” là ký hiệu vị trí trống trong bảng băm.

a. Trình bày từng bước việc tìm mã quản lý 23 trong bảng băm T.

b. Trình bày từng bước việc thêm các mã quản lý sau vào bảng băm T theo đúng thứ tự liệt kê là 11, 20, 27.

Lời giải:
Câu hỏi này kiểm tra kiến thức về cấu trúc dữ liệu bảng băm (hash table) với phương pháp giải quyết xung đột bằng thăm dò bậc hai (quadratic probing). Cụ thể, câu hỏi yêu cầu thực hiện hai tác vụ chính: tìm kiếm một mã quản lý đã có trong bảng băm và thêm mới một số mã quản lý vào bảng băm.

Phần a: Tìm kiếm mã quản lý 23

Để tìm mã quản lý 23, chúng ta sẽ sử dụng hàm băm và hàm thăm dò đã cho. Kích thước bảng băm là M = 7.

1. Tính toán vị trí ban đầu bằng hàm băm chính:
h(key) = key % M
h(23) = 23 % 7 = 2
Vị trí đầu tiên cần kiểm tra là chỉ số 2.

2. Kiểm tra vị trí 2 trong bảng băm T:
Quan sát hình ảnh bảng băm, ta thấy tại chỉ số 2 có giá trị là 16. Vì 16 != 23, nên mã 23 chưa được tìm thấy tại đây.

3. Tiến hành thăm dò lần thứ nhất (i=1) nếu vị trí ban đầu không khớp:
Hàm thăm dò: prob(key, i) = (h(key) + i*i + i) % M
prob(23, 1) = (h(23) + 1*1 + 1) % 7
prob(23, 1) = (2 + 1 + 1) % 7 = 4 % 7 = 4
Vị trí tiếp theo cần kiểm tra là chỉ số 4.

4. Kiểm tra vị trí 4 trong bảng băm T:
Tại chỉ số 4 có giá trị là 23. Mã quản lý 23 đã được tìm thấy.

Kết luận phần a: Mã quản lý 23 được tìm thấy tại chỉ số 4 sau 1 lần thăm dò.

Phần b: Thêm các mã quản lý 11, 20, 27

Chúng ta sẽ thêm lần lượt từng mã vào bảng băm T có kích thước M=7 và trạng thái ban đầu được cho.

1. Thêm mã 11:
- Tính vị trí ban đầu: h(11) = 11 % 7 = 4.
- Kiểm tra vị trí 4: Vị trí 4 đang chứa giá trị 23. Xung đột xảy ra.
- Thăm dò lần 1 (i=1): prob(11, 1) = (h(11) + 1*1 + 1) % 7 = (4 + 1 + 1) % 7 = 6 % 7 = 6.
- Kiểm tra vị trí 6: Vị trí 6 trống ('-').
- Thêm 11 vào vị trí 6.
Bảng băm sau khi thêm 11: [2, 9, 16, -, 23, -, 11]

2. Thêm mã 20:
- Tính vị trí ban đầu: h(20) = 20 % 7 = 6.
- Kiểm tra vị trí 6: Vị trí 6 đang chứa giá trị 11. Xung đột xảy ra.
- Thăm dò lần 1 (i=1): prob(20, 1) = (h(20) + 1*1 + 1) % 7 = (6 + 1 + 1) % 7 = 8 % 7 = 1.
- Kiểm tra vị trí 1: Vị trí 1 trống ('-').
- Thêm 20 vào vị trí 1.
Bảng băm sau khi thêm 20: [2, 20, 16, -, 23, -, 11]

3. Thêm mã 27:
- Tính vị trí ban đầu: h(27) = 27 % 7 = 6.
- Kiểm tra vị trí 6: Vị trí 6 đang chứa giá trị 11. Xung đột xảy ra.
- Thăm dò lần 1 (i=1): prob(27, 1) = (h(27) + 1*1 + 1) % 7 = (6 + 1 + 1) % 7 = 8 % 7 = 1.
- Kiểm tra vị trí 1: Vị trí 1 đang chứa giá trị 20. Xung đột xảy ra.
- Thăm dò lần 2 (i=2): prob(27, 2) = (h(27) + 2*2 + 2) % 7 = (6 + 4 + 2) % 7 = 12 % 7 = 5.
- Kiểm tra vị trí 5: Vị trí 5 trống ('-').
- Thêm 27 vào vị trí 5.
Bảng băm sau khi thêm 27: [2, 20, 16, -, 23, 27, 11]

Kết luận phần b: Các mã 11, 20, 27 được thêm vào các vị trí tương ứng là 6, 1, 5.

Câu 5:

Trong các ứng dụng thực tế, chẳng hạn trong mạng lưới giao thông đường bộ, đường thủy hoặc đường hàng không, người ta không chỉ quan tâm đến việc tìm đường đi giữa hai địa điểm mà còn phải lựa chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn không gian, thời gian hay chi phí). Vấn đề này có thể được mô hình hóa thành một bài toán trên đồ thị, trong đó mỗi địa điểm được biểu diễn bởi một đỉnh, cạnh nối hai đỉnh biểu diễn cho “đường đi trực tiếp” giữa hai địa điểm (tức không đi qua địa điểm trung gian) và trọng số của cạnh là khoảng cách giữa hai địa điểm.

Bài toán có thể phát biểu dưới dạng tổng quát như sau: Cho một đơn đồ thị có hướng và có trọng số dương G=(V,E), trong đó V là tập đỉnh, E là tập cạnh (cung) và các cạnh đều có trọng số, hãy tìm một đường đi (không có đỉnh lặp lại) ngắn nhất từ đỉnh xuất phát S thuộc V đến đỉnh đích F thuộc V. Giả sử thông tin đầu vào của bài toán (Input) được nhập vào chương trình như sau:

Input Giải thích

7

A B 1

B E 3

E D 3

C B 4

A D 7

E C 2

C D 1 A E

- Dòng đầu tiên chứa một số nguyên dương e cho biết số cạnh của đồ thị

- Với e dòng tiếp theo, mỗi dòng chứa hai chuỗi u, i và một số nguyên dương x, thể hiện thông tin có một cạnh nối từ đỉnh u sang đỉnh i trong đồ thị với độ dài (trọng số) là x

- Dòng cuối cùng chứa hai chuỗi s và f, đây là đỉnh bắt đầu và đỉnh kết thúc của đường đi cần tìm Lưu ý: không biết trước số đỉnh và danh sách các đỉnh.

Hãy thực hiện các yêu cầu sau:

a. Xây dựng các cấu trúc dữ liệu phù hợp nhất có thể để biểu diễn đồ thị trên máy tính theo input đã cho.

Cấu trúc được xem là tốt nếu đạt được các tiêu chuẩn sau: Tiết kiệm tài nguyên; Hỗ trợ một số thao tác cơ bản như “Kiểm tra hai đỉnh có kề nhau không”, “Tìm danh sách
các đỉnh kề với một đỉnh cho trước” với ràng buộc là không phải duyệt qua danh sách tất cả các cạnh của đồ thị.

b. Viết hàm nhập theo Input ở đầu bài và lưu trữ thông tin của đồ thị vào cấu trúc dữ liệu đã đề xuất ở câu a.

** KHÔNG YÊU CẦU tìm cách giải cho bài toán này. Sinh viên ĐƯỢC PHÉP sử dụng Standard Template Library-STL với những cấu trúc dữ liệu (vector, stack, queue, list, map, set, pair, …) cũng như giải thuật được xây dựng sẵn.

Lời giải:
Câu hỏi này yêu cầu hai phần chính:

a. Xây dựng cấu trúc dữ liệu biểu diễn đồ thị: Đề bài mô tả một bài toán tìm đường đi ngắn nhất trên đồ thị có hướng, có trọng số dương. Input bao gồm số cạnh, thông tin các cạnh (đỉnh đầu, đỉnh cuối, trọng số) và cặp đỉnh xuất phát - đích. Yêu cầu là xây dựng cấu trúc dữ liệu tiết kiệm tài nguyên và hỗ trợ hiệu quả các thao tác: kiểm tra hai đỉnh có kề nhau không, tìm danh sách đỉnh kề của một đỉnh mà không cần duyệt toàn bộ cạnh.

Để đáp ứng các tiêu chí này, ma trận kề (adjacency matrix) là một lựa chọn không tối ưu vì nó tiêu tốn O(V^2) bộ nhớ, không hiệu quả với đồ thị thưa, và việc tìm đỉnh kề yêu cầu duyệt toàn bộ hàng/cột (O(V)). Danh sách cạnh (edge list) trực tiếp lưu trữ input, nhưng việc tìm đỉnh kề hoặc kiểm tra kề nhau sẽ tốn O(E).

Cấu trúc dữ liệu phù hợp nhất cho yêu cầu này là danh sách kề (adjacency list). Với đồ thị có hướng, mỗi đỉnh sẽ có một danh sách (thường là `std::vector` hoặc `std::list` trong C++ STL) chứa các cặp (đỉnh kề, trọng số).

* Tiết kiệm tài nguyên: Dung lượng bộ nhớ là O(V + E), phù hợp với cả đồ thị thưa và dày.
* Kiểm tra hai đỉnh có kề nhau không (u, v): Ta truy cập danh sách kề của u, sau đó tìm kiếm v trong danh sách đó. Nếu đỉnh kề được lưu trong `std::vector`, tìm kiếm có thể mất O(deg(u)) hoặc O(log deg(u)) nếu sắp xếp. Tuy nhiên, nếu dùng `std::map` hoặc `std::unordered_map` để lưu danh sách kề (ánh xạ đỉnh kề tới trọng số), thao tác này sẽ nhanh hơn, trung bình O(1) với `unordered_map` hoặc O(log deg(u)) với `map`.
* Tìm danh sách các đỉnh kề với một đỉnh cho trước (u): Ta chỉ cần truy cập danh sách kề của đỉnh u. Thời gian là O(deg(u)), không phụ thuộc vào tổng số cạnh E.

Do đó, sử dụng một `std::map>>` hoặc `std::unordered_map>>` (hoặc tương tự với `int` thay vì `string` nếu đỉnh được đánh số) là giải pháp tối ưu.

b. Viết hàm nhập Input và lưu trữ: Hàm này cần đọc số lượng cạnh, sau đó lặp lại số lần đó để đọc thông tin từng cạnh (u, v, w) và lưu vào cấu trúc dữ liệu đã chọn. Cuối cùng, đọc cặp đỉnh xuất phát (s) và đích (f).

Lưu ý: Câu hỏi không yêu cầu giải thuật tìm đường đi ngắn nhất, chỉ tập trung vào việc biểu diễn đồ thị và nhập liệu. Do đó, không có đáp án đúng để chọn theo format `answer_iscorrect` vì đây là yêu cầu thực hiện, không phải trắc nghiệm.