Câu hỏi: CSD201 Cấu trúc dữ liệu và giải thuật – Bộ ôn tập cuối kỳ số 4

Đáp án đúng: "4, 7, 5, 3, 8, 6, 2, 1". Cây có gốc 1 với con trái 3 và con phải 2; nút 3 có con trái 4 và con phải 5; nút 5 có con trái 7; nút 2 chỉ có con phải 6; nút 6 có con trái 8. Duyệt sau đi trái, rồi phải, rồi gốc nên lá ra trước và gốc ra sau cùng: trong nhánh trái, lá 4 ra trước, tiếp đến 7 rồi 5, rồi mới tới 3; trong nhánh phải, 8 ra trước 6, rồi 2; cuối cùng là gốc 1. "1, 3, 4, 5, 7, 2, 6, 8" chính là dãy duyệt trước của cây này, nhận ra ngay vì gốc 1 đứng đầu chứ không đứng cuối. "4, 3, 7, 5, 1, 2, 8, 6" là dãy duyệt giữa, dấu hiệu là gốc 1 nằm giữa hai nhánh. "1, 3, 4, 7, 5, 2, 6, 8" cũng mở đầu bằng gốc nên không thể là duyệt sau, và nó còn in 7 trước cha 5 nên không khớp cả duyệt trước.

Đáp án đúng: "3, 4, 6, 7, 9, 11, 8, 10". Chốt là x = a[low] = 7, rồi dò hai đầu: i tiến tới phần tử đầu tiên lớn hơn 7, j lùi tới phần tử đầu tiên không lớn hơn 7, hai bên gặp cặp sai chỗ thì đổi chỗ. Trên 7, 4, 10, 11, 9, 3, 8, 6: i dừng ở 10, j dừng ở 6 (phần tử cuối, vì 6 không lớn hơn 7), đổi chỗ được 7, 4, 6, 11, 9, 3, 8, 10; vòng hai i dừng ở 11, j dừng ở 3, đổi chỗ được 7, 4, 6, 3, 9, 11, 8, 10; vòng ba i dừng ở 9 còn j lùi về đúng ô của số 3 nên hai chỉ số đã vượt nhau và không đổi gì nữa. Cuối cùng đổi chốt 7 với a[j] = 3, cho 3, 4, 6, 7, 9, 11, 8, 10, trong đó mọi số bên trái 7 đều nhỏ hơn 7 và mọi số bên phải đều lớn hơn 7 — đúng mục tiêu của một lần phân hoạch. "3, 4, 7, 6, 9, 11, 8, 10" để 6 nằm bên phải chốt dù 6 nhỏ hơn 7. "3, 4, 6, 7, 9, 8, 10, 11" và "3, 4, 6, 7, 8, 9, 11, 10" đều đã sắp lại phần bên phải chốt, việc mà một lần phân hoạch chưa làm.

Đáp án đúng: "(2)". Đó là bảng có 21 ở ô 1, 32 ở ô 2, 41 ở ô 3, 14 ở ô 4, 25 ở ô 5, 191 ở ô 6 và các ô 0, 7, 8, 9 trống. Với h(x) bằng x chia 10 lấy dư và dò tuyến tính bước 1, theo đúng thứ tự chèn: 25 vào ô 5, 21 vào ô 1, 14 vào ô 4, 32 vào ô 2; 41 băm về ô 1 đang có 21 nên dò ô 2 có 32 rồi dừng ở ô 3 đang trống; 191 cũng băm về ô 1 nên dò 2, 3, 4, 5 đều đầy và dừng ở ô 6. Vì vậy "(1)" sai vì nó đặt 191 vào ô 3 và 41 vào ô 6, chỉ xảy ra nếu 191 được chèn trước 41, trái thứ tự đề cho; "(3)" sai vì nó chỉ giữ 21, 32, 14, 25 và làm mất hai khoá va chạm, trong khi dò tuyến tính luôn tìm được ô trống khi bảng chưa đầy; "(4)" sai vì nó đặt 41 ở ô 9 và 191 ở ô 8, bỏ qua các ô trống 3 và 6 nằm ngay trên đường dò bước 1.

Đáp án đúng: "D, B, D, C, B, A, D". Đa đồ thị có các cạnh A–B, A–D, B–C, hai cạnh song song B–D và cạnh C–D, mọi đỉnh bậc chẵn nên tồn tại chu trình Euler. Chạy thuật toán từ D: đẩy D, chọn đỉnh kề nhỏ nhất theo chữ cái là A rồi xoá cạnh D–A; từ A chỉ còn B nên đẩy B; từ B còn C và hai cạnh tới D nên chọn C; từ C còn D nên đẩy D; từ D còn hai cạnh tới B nên đẩy B; từ B còn một cạnh tới D nên đẩy D. Ngăn xếp từ đáy lên là D, A, B, C, D, B, D, và lúc này đỉnh trên cùng đã hết cạnh nên mảng kết quả nhận các đỉnh theo đúng thứ tự lấy ra: D, B, D, C, B, A, D. Dãy "D, A, B, C, D, B, D" chính là thứ tự các đỉnh được đẩy vào, còn mảng kết quả được ghi khi lấy ra nên đảo lại. Dãy "D, B, C, D, B, A, D" đòi lúc đứng ở B lần đầu phải đẩy sang D trong khi cạnh B–C vẫn còn, trái luật chọn đỉnh kề nhỏ nhất theo chữ cái. Dãy "D, C, B, D, B, A, D" cũng bỏ qua C ở lần đứng tại B đầu tiên. Dãy "D, A, B, C, D" chỉ dùng bốn cạnh, bỏ sót hai cạnh B–D nên không phải chu trình Euler.

Đáp án đúng: "46". Các cạnh là A–B = 3, A–C = 6, A–D = 8, B–C = 4, B–E = 18, C–D = 10, D–F = 16, E–F = 15. Chạy Kruskal theo trọng số tăng: lấy A–B = 3, lấy B–C = 4, bỏ A–C = 6 vì tạo chu trình A–B–C, lấy A–D = 8, bỏ C–D = 10 cũng vì chu trình, lấy E–F = 15, rồi lấy D–F = 16 để nối cụm E, F vào phần còn lại; tới đây đã đủ 5 cạnh cho 6 đỉnh nên dừng và B–E = 18 bị loại. Tổng là 3 + 4 + 8 + 15 + 16 = 46. Phương án "30" là tổng 3 + 4 + 8 + 15, mới chỉ nối A, B, C, D thành một khối và E với F thành khối riêng nên chưa phải cây khung. Phương án "29" là tổng 3 + 4 + 6 + 16, vừa chứa chu trình A–B–C lại bỏ sót đỉnh E. Phương án "48" là tổng 3 + 4 + 10 + 15 + 16, dùng C–D = 10 thay cho A–D = 8. Phương án "50" là tổng 3 + 6 + 8 + 18 + 15, chạm E bằng cạnh đắt B–E = 18 thay vì đi qua cặp E–F và D–F.

Đáp án đúng: "4, 6, 9, 2, 8, 1, 3, 7, 5, 10". Một lượt của vòng for chỉ so từng cặp kề nhau và đổi chỗ khi trái lớn hơn phải: 6 với 4 đổi thành 4, 6; 6 với 9 và 9 với 10 giữ nguyên; rồi 10 lớn hơn mọi số sau nó nên bị đẩy dần qua 2, 8, 1, 3, 7, 5 và nằm ở cuối, các số bị vượt lùi lên đúng một ô mà không đổi thứ tự tương đối. Vậy sau một lượt chỉ 6 và 4 hoán vị, còn 10 về cuối. "4, 6, 9, 8, 2, 1, 3, 7, 5, 10" sai vì nó đổi thêm 2 với 8, nhưng khi so cặp đó thì phần tử đang mang theo là 10 chứ không phải 8. "4, 6, 9, 1, 2, 8, 3, 7, 5, 10" sai vì nó đẩy 1 lên trước 2 và 8, một bước nhảy mà phép so cặp kề nhau không làm được trong một lượt. "4, 6, 9, 2, 8, 1, 3, 5, 7, 10" sai vì nó đổi thêm 7 với 5 ở gần cuối, trong khi cặp đang so lúc đó là 10 với 7 rồi 10 với 5.

Đáp án đúng: "5 7 11 61 42 3 12 8 2". Đoạn mã dựng nút mới mang 5, đặt prev của nó là null, next của nó trỏ vào head cũ là 7, rồi sửa prev của 7 trỏ về nút mới và cuối cùng dời head sang nút mới, nên 5 thành phần tử đầu danh sách còn dãy cũ giữ nguyên thứ tự phía sau. Biến p trỏ tới nút 12 không hề được dùng nên quanh 12 không có gì thay đổi. Dãy "7 11 61 42 3 12 8 2 5" đặt 5 ở cuối, muốn vậy phải sửa next của nút cuối chứ không phải cho next của nút mới trỏ vào head. Dãy "7 11 61 42 3 12 8 5 2" chèn 5 vào trước phần tử cuối, cần một vòng lặp đi tìm nút liền trước nút cuối mà đoạn mã này không có. Dãy "7 11 61 42 3 12 5 8 2" chèn 5 ngay sau 12, đó mới là chỗ dùng tới biến p. Dãy "7 5 11 61 42 3 12 8 2" đặt 5 vào sau nút đầu, tức phải gán next của head cũ, trong khi ở đây head bị thay bằng chính nút mới.

Đáp án đúng: "1, 3, 6, 5, 7, 2, 4, 8". Cây có gốc 1 với con trái 3 và con phải 2; nút 3 có con trái 6 và con phải 5; nút 5 có con trái 7; nút 2 chỉ có con phải 4; nút 4 có con trái 8. Duyệt trước in gốc rồi vét nhánh trái, xong mới sang nhánh phải: 1, tới 3, in 3 rồi con trái 6, rồi con phải 5 và con trái 7 của nó; hết nhánh trái mới sang 2, in 2 rồi con phải 4 và con trái 8 của 4. "1, 3, 6, 7, 5, 2, 4, 8" in 7 trước 5, nhưng 7 là con của 5 nên theo duyệt trước cha phải ra trước con. "1, 3, 6, 5, 7, 2, 8, 4" mắc lỗi đối xứng ở nhánh phải: 8 là con của 4 nên không được đứng trước 4. "6, 3, 7, 5, 1, 8, 4, 2" mở đầu bằng lá 6 và đẩy gốc vào giữa, đó là dáng của duyệt giữa, nhưng duyệt giữa của cây này là 6, 3, 7, 5, 1, 2, 8, 4 nên dãy đó không phải phép duyệt nào.

Đáp án đúng: "C, B, A, E, G, F, D, H". Duyệt theo chiều sâu đi hết một nhánh rồi mới quay lui, và khi có nhiều đỉnh kề chưa thăm thì lấy theo thứ tự chữ cái. Với các cạnh A–B, A–E, A–G, B–C, B–E, C–D, D–F, E–G, F–G: từ C chọn B (B đứng trước D); từ B chọn A; từ A chọn E; từ E chọn G; từ G chọn F; từ F chọn D; tại D mọi đỉnh kề đã thăm nên quay lui hết. Bảy đỉnh đã xong mà H chưa thăm, nên phép duyệt khởi động lại ở H và H đứng cuối dãy. "C, B, E, G, F, D, A, H" bỏ A tại B dù A đứng trước E theo chữ cái. "C, B, A, G, F, D, E, H" chọn G tại A dù E đứng trước G. "C, B, A, E, G, F, D" đúng mạch nhưng thiếu H; đỉnh cô lập vẫn phải được liệt kê để phủ hết đỉnh của đồ thị.

Đáp án đúng: "It inserts new node with value x at the head of the list.". Nút mới q được tạo với q.prev = null, tức không có ai đứng trước nó; q.next = head cho nó trỏ sang nút đầu cũ; head.prev = q nối chiều ngược để danh sách hai chiều vẫn nhất quán; cuối cùng head = q đưa chính q thành nút đầu mới. Vì vậy x nằm ở vị trí đầu tiên, trước giá trị đang ở đầu, và thứ tự các nút cũ không đổi. Phương án "It inserts new node with value x after the head of the list." đòi chèn vào giữa nút đầu và nút thứ hai, muốn vậy phải viết q.prev = head, q.next = head.next, cập nhật head.next.prev = q rồi head.next = q, và tuyệt đối không được gán lại head; đoạn mã đã cho vừa đặt q.prev = null vừa dịch head nên không thể là phép chèn sau nút đầu.

Đáp án đúng: "B, C, D, E, F". Các cung là B→C = 4, B→D = 22, B→E = 8, B→F = 12, C→D = 3, D→F = 6, E→D = 12, E→F = 2. Chọn B với khoảng cách 0, cập nhật C = 4, E = 8, F = 12, D = 22. Nhỏ nhất là C = 4 nên C vào S; qua C→D = 3 thì D hạ xuống 4 + 3 = 7. Nhỏ nhất kế tiếp là D = 7 nên D vào S; qua D→F = 6 được 13 nhưng 13 lớn hơn 12 nên F giữ nguyên 12. Tiếp đó E = 8 vào S; qua E→F = 2 thì F hạ xuống 8 + 2 = 10. Cuối cùng F = 10 được chọn, nên thứ tự là B, C, D, E, F. Phương án "B, C, F" dừng quá sớm, nó coi F = 12 là chốt mà không thấy D = 7 và E = 8 đều nhỏ hơn 12 nên phải vào S trước. Phương án "B, C, D, F" bỏ qua E = 8 dù 8 nhỏ hơn 10, mà chính E mới là đỉnh hạ F từ 12 xuống 10. Phương án "B, C, E, F" bỏ D = 7 trong khi 7 nhỏ hơn 8, và D được hạ giá nhờ C→D = 3 ngay sau khi C vào S.

Đáp án đúng: "GoodAfterN". Hàng đợi lấy ra theo đúng thứ tự đưa vào, nên mỗi dấu sao in ra chữ cái chưa in nào vào sớm nhất. Dãy nhập có mười dấu sao nên in ra mười chữ. Chữ cái vào lần lượt là G, o, o, d, A, f, t, e, r, N, o, o, n; mười lần dequeue lấy đúng mười chữ đầu của dãy đó, cho GoodAfterN, còn o, o, n vẫn nằm trong hàng đợi khi dãy nhập hết. "GoodAfter" sai vì nó chỉ có chín chữ, tức đếm thiếu một dấu sao trong cụm ba sao cuối. "oodAfteroo" sai vì nó bỏ chữ G đầu tiên, nhưng G vào trước nên phải là chữ ra trước nhất. "oAdoretfoo" sai vì thứ tự đó đảo lộn chữ vào trước ra sau, giống hành vi của ngăn xếp chứ không phải hàng đợi.

Đáp án đúng: "40, 20, 50, 15, 35, 45, 30". Xoá bằng sao chép thay giá trị nút bị xoá bằng nút cực phải của nhánh trái, tức nút liền trước nó theo thứ tự tăng. Nhánh trái của 25 gồm 15 với con phải 20, nút cực phải là 20, nên 25 nhận giá trị 20, nút 20 cũ bị tháo và con phải của 15 thành rỗng. Cây còn lại: gốc 40, bên trái là 20 với con trái 15, con phải 35, bên phải là 50 với con trái 45, còn 30 là con trái của 35. Đọc từng tầng từ trái sang phải cho 40, rồi 20, 50, rồi 15, 35, 45, rồi 30. Dãy "40, 15, 50, 35, 45, 30, 20" đưa 15 lên thay 25, đó là kéo con trái lên chứ không lấy nút cực phải của nhánh trái, lại đẩy 20 xuống tầng sâu nhất. Dãy "40, 35, 15, 50, 45, 30, 20" lấy 35 thay cho 25 và xếp 15 trước 50 dù 50 ở tầng cao hơn, trái với luật đọc hết tầng này mới sang tầng sau. Dãy "15, 20, 40, 35, 50, 45, 30" mở đầu bằng 15 nên không thể là duyệt theo chiều rộng, vì phép duyệt ấy luôn bắt đầu từ gốc 40.

Đáp án đúng: "(2) (5) (1) (2)". LZW đọc dần xâu BBBABDACADA và chỉ phát mã khi chuỗi đang gom không còn trong từ điển. Bắt đầu với B, thêm B thành BB chưa có nên phát mã của B là 2 và nạp BB vào ô 5; lại từ B, thêm B được BB đã có ở ô 5 nên gom tiếp, thêm A thành BBA chưa có nên phát 5 và nạp BBA vào ô 6; còn A, thêm B được AB chưa có nên phát mã của A là 1 và nạp AB vào ô 7; còn B, thêm D được BD chưa có nên phát mã của B là 2. Bốn mã đầu là 2, 5, 1, 2. "(2) (5) (6) (4)" dùng ngay ô 6 vừa nạp, nhưng ô 6 là BBA mà sau khúc BBA phần còn lại bắt đầu bằng AB nên không thể khớp. "(2) (5) (3) (2)" phát mã của C, trong khi ký tự đứng sau khúc BBA là A. "(2) (5) (2) (4)" bỏ mất chữ A ở vị trí thứ tư. "(5) (1) (4) (2)" phát mã của BB ngay bước đầu, lúc đó ô 5 còn chưa được nạp.

Đáp án đúng: "4, 3, 7, 5, 1, 2, 8, 6". Duyệt giữa luôn theo trình tự con trái, thăm gốc, con phải. Cây có gốc 1 với con trái 3 (con trái 4, con phải 5, mà 5 chỉ có con trái 7) và con phải 2 (không có con trái, con phải là 6, mà 6 chỉ có con trái 8). Nhánh trái: vào 4 in 4, thăm 3, sang 5 thì phải xuống con trái 7 trước nên in 7 rồi 5, được 4, 3, 7, 5. Thăm gốc 1. Nhánh phải: 2 không có con trái nên in 2 ngay, sang 6 thì xuống con trái 8 trước nên in 8 rồi 6, được 2, 8, 6. Ghép lại thành 4, 3, 7, 5, 1, 2, 8, 6. "1, 3, 4, 5, 7, 2, 6, 8" là kết quả duyệt trước, nhận ra ngay vì nó mở đầu bằng gốc 1. "4, 7, 5, 3, 8, 6, 2, 1" là kết quả duyệt sau, nhận ra vì gốc 1 đứng cuối. "1, 3, 4, 7, 5, 2, 6, 8" không ứng với phép duyệt nào: nó đặt 7 trước 5 trong khi 7 là con của 5.

Đáp án đúng: "7 11 6 4 33 5 12 8 3". Đoạn mã lấy f bằng p.prev, tức nút 33 đứng ngay trước nút 12, rồi đặt bốn liên kết q.prev bằng f, q.next bằng p, f.next bằng q và p.prev bằng q; bốn phép gán này khâu nút mới mang giá trị 5 vào đúng khe giữa 33 và 12, nên 5 hiện ra ngay trước 12 và không nút nào bị mất. Vì vậy "7 11 6 4 33 12 8 3 5" sai vì muốn nối vào cuối thì phải sửa tail.next và tail, mà đoạn mã không chạm tới tail; "7 11 6 4 33 12 5 8 3" sai vì nó đặt 5 sau 12, tức lấy mốc là p.next chứ không phải p.prev; "7 5 11 6 4 33 12 8 3" sai vì nó chèn sau head, nghĩa là f phải là head chứ không phải nút trước p; "5 7 11 6 4 33 12 8 3" sai vì chèn vào đầu còn cần gán lại head bằng q, điều đoạn mã không làm.

Đáp án đúng: "2 0 1". Hàm in trước rồi mới gọi đệ quy, nên các số dư hiện ra theo chiều đi xuống: fun(17) in 17%5 = 2 rồi gọi fun(17/3) = fun(5); fun(5) in 5%5 = 0 rồi gọi fun(5/3) = fun(1); fun(1) in 1%5 = 1 rồi gọi fun(0), và fun(0) dừng vì điều kiện n lớn hơn 0 không còn đúng. Chuỗi in ra vì vậy là 2 0 1. Dãy "2 1" bỏ mất bước fun(5), tức coi 17/3 bằng 1 thay vì 5. Dãy "2 2 1" lấy số dư theo cơ số 3 ở bước giữa vì 5%3 = 2, trong khi lệnh in dùng cơ số 5. Dãy "2 1 2" đảo thứ tự, nhưng lệnh in đứng trước lời gọi đệ quy nên số dư của n lớn nhất phải ra đầu tiên. Dãy "3 1 1" bắt đầu bằng 17/5 = 3 chứ không phải 17%5 = 2, tức lẫn giữa phép chia và phép lấy dư.

Đáp án đúng: "We can delete the node p by moving the data from the next node into the p node and then deleting the next node by statement p.next = p.next.next; This solution has O(1) runtime.". Trong danh sách liên kết đơn ta không lùi được, nhưng không nhất thiết phải giải phóng đúng ô nhớ của p: chép dữ liệu của nút kế tiếp vào p rồi tháo nút kế tiếp ra bằng p.next = p.next.next là đã cho đúng dãy giá trị cần có, và vì p không phải tail nên p.next luôn tồn tại; toàn bộ gói trong vài phép gán nên là O(1). Phương án "We can find the node f before the node p and then deleting the node p by statement f.next = p.next; This solution has O(1) runtime." sửa liên kết đúng nhưng ước lượng sai chi phí: tìm f phải đi từ head nên mất O(n). Phương án "Deleting the node p always takes O(n) time." bị chữ always phá bởi đúng mẹo chép dữ liệu nói trên. Phương án "Deleting the node p always takes O(1) time." sai theo chiều ngược lại: nếu p là nút cuối thì không có nút kế tiếp để chép, buộc phải đi tìm nút trước nó, nên không phải lúc nào cũng O(1).

Đáp án đúng: "It inserts new node with value x after the node p.". Đọc theo thứ tự lệnh: p2 giữ lại nút đứng sau p, rồi p.next = p1 và p1.prev = p nối nút mới vào ngay sau p, cuối cùng p1.next = p2 và p2.prev = p1 khâu nút mới với nút kế tiếp. Cả bốn liên kết của một danh sách liên kết đôi đều được vá nên nút mới nằm gọn giữa p và nút sau nó. "It inserts new node with value x before the node p." sai vì chèn trước p phải xuất phát từ p.prev, mà đoạn mã này không hề đọc p.prev. "It replaces the node p with new node with value x." sai vì p vẫn còn nguyên trong danh sách và còn là nút đi trước nút mới; thay thế thì phải cho nút trước p trỏ vượt qua p. "It creates new node with value x at the end of the list." sai vì kết quả đó chỉ xảy ra khi p tình cờ là nút cuối, còn đề đã nói p có nút kế tiếp.