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

Đáp án đúng: "None of the others". Đệ quy chỉ là cách viết gọn chứ không mở thêm năng lực tính toán: mọi lời gọi đệ quy đều thay được bằng một vòng lặp cộng với một ngăn xếp tường minh để lưu các trạng thái còn dở, vì đó đúng là việc mà ngăn xếp lời gọi của máy đang làm hộ. "Tower of Hanoi" có bản lặp quen thuộc: với n đĩa, chạy 2^n - 1 bước theo quy tắc luân phiên di chuyển đĩa nhỏ nhất rồi thực hiện nước đi hợp lệ duy nhất còn lại. "Fibonacci Series" thậm chí nên viết lặp, chỉ cần hai biến giữ hai số liền trước rồi cộng dồn, nhanh hơn hẳn bản đệ quy nhân đôi lời gọi. "Tree Traversal" cũng viết lặp được: dùng một ngăn xếp để đẩy các nút còn chờ xử lý, hoặc dùng hàng đợi nếu duyệt theo chiều rộng. Cả ba thuật toán vừa nêu đều không bắt buộc đệ quy, nên câu trả lời phủ định toàn bộ mới đúng.

Đáp án đúng: "False". Phát biểu trong đề nói cây cân bằng là cây mà gốc có số con cháu bên trái nhiều hơn hẳn bên phải hoặc ngược lại, nhưng đó đúng là mô tả của một cây LỆCH, trái hẳn khái niệm cân bằng. Cân bằng nghĩa là hai phía của mỗi nút xấp xỉ nhau: ở cây AVL, chiều cao cây con trái và cây con phải của mọi nút lệch nhau nhiều nhất 1, nhờ đó chiều cao giữ ở mức khoảng log2 của n và các phép tìm, chèn, xoá còn O(log n). Vì vậy "True" sai vì nếu chấp nhận định nghĩa ấy thì cây xâu, loại cây mà mỗi nút chỉ có một con và toàn bộ con cháu dồn về một phía, lại được coi là cân bằng nhất; trong khi nó có chiều cao đúng bằng số nút và làm phép tìm tụt xuống O(n), tức chính cái mà việc cân bằng được đặt ra để tránh.

Đáp án đúng: "the variable in E will appear as external nodes (leaves) and operations in internal nodes". Trong cây biểu thức, mỗi phép toán hai toán hạng cần đúng hai cây con làm toán hạng của nó, nên nút mang phép toán buộc phải có hai con và nằm bên trong cây; còn biến không nhận toán hạng nào nên không có con, tức là lá. Phương án "the operations in E will appear as external nodes (leaves) and variables in internal nodes" đảo vai: phép toán thành lá thì không còn chỗ gắn toán hạng, còn biến ở nút trong lại phải có hai con mà biến chẳng có toán hạng nào. Phương án "the variables and operations in E will appear only in internal nodes" để cây không có lá, điều bất khả vì mọi cây hữu hạn đều kết thúc ở những nút không con. Phương án "the variables and operations in E will appear only in external nodes (leaves)" để cây chỉ gồm lá, tức không nút nào có con, nên không biểu diễn được phép toán nối hai toán hạng.

Đáp án đúng: "7, 4, 8, 1, 6, 9, 3". Chèn lần lượt 7, 8, 4, 1, 3, 6, 9 vào cây tìm kiếm rỗng: 7 làm gốc; 8 lớn hơn 7 nên thành con phải; 4 nhỏ hơn 7 nên thành con trái; 1 nhỏ hơn 7 rồi nhỏ hơn 4 nên là con trái của 4; 3 nhỏ hơn 7, nhỏ hơn 4, lớn hơn 1 nên là con phải của 1; 6 nhỏ hơn 7 nhưng lớn hơn 4 nên là con phải của 4; 9 lớn hơn 7 và lớn hơn 8 nên là con phải của 8. Duyệt theo lớp cho 7; rồi 4, 8; rồi 1, 6, 9; rồi 3. Phương án "7, 4, 8, 1, 3, 6, 9" xếp 3 cùng lớp với 1 và 6, nhưng 3 nằm dưới 1 nên thuộc lớp thứ tư. Phương án "7, 4, 8, 1, 6, 3, 9" đặt 3 trước 9, trong khi 9 là con của 8 ở lớp ba còn 3 ở lớp bốn. Phương án "7, 4, 1, 3, 6, 8, 9" chính là kết quả duyệt tiền thứ tự, đi gốc rồi vét hết nhánh trái mới sang 8, chứ không phải duyệt theo lớp.

Đáp án đúng: "15, 5, 25, 10, 20, 40, 35". Xoá bằng hợp nhất nút 30: con trái 15 lên thay chỗ, còn cả cây con phải gốc 40 được treo làm con phải của nút phải nhất trong cây con trái. Đi phải từ 15 được 25, mà 25 chỉ có con trái 20 nên 25 chính là nút phải nhất, vậy 40 thành con phải của 25. Cây mới: gốc 15 với hai con 5 và 25; 5 giữ con phải 10; 25 giữ con trái 20 và nhận con phải 40; 40 vẫn có con trái 35. Duyệt theo bề rộng cho 15, rồi 5 và 25, rồi 10, 20, 40, cuối cùng 35. "25, 15, 40, 5, 20, 35, 10" sai vì đó là kết quả xoá bằng sao chép, khi khoá 25 được chép lên gốc và 20 nối lên thay nút 25. "25, 15, 40, 5, 35, 10, 20" sai vì vừa dùng cách sao chép vừa xếp lộn mức, đặt 35 trước 20 và đẩy 20 xuống cuối. "15, 5, 40, 10, 35, 25, 20" sai vì nó treo 40 vào đúng chỗ của 25 làm 25 tụt xuống sâu hơn, còn hợp nhất chỉ gắn cây con phải xuống dưới nút phải nhất.

Đáp án đúng: "5, 1, 7, 4, 6, 8, 3". Xoá bằng sao chép lấy nút cực phải của nhánh trái để thay giá trị nút bị xoá. Nhánh trái của 2 chỉ có nút 1 và nút này không có con phải, nên nút cực phải là 1: giá trị 2 bị thay bằng 1, nút 1 cũ bị tháo, con trái của chỗ ấy thành rỗng, còn 4 với con trái 3 vẫn treo bên phải. Cây thành gốc 5, bên trái là 1 với con phải 4, bên phải là 7 với hai con 6, 8, và 3 là con trái của 4. Đọc từng tầng từ trái sang phải cho 5, rồi 1, 7, rồi 4, 6, 8, rồi 3. Dãy "5, 1, 7, 4, 6, 3, 8" đặt 3 trước 8, nhưng 8 ở tầng thứ ba còn 3 ở tầng thứ tư nên 8 phải ra trước. Dãy "5, 1, 7, 4, 3, 6, 8" cũng đẩy 3 lên trước 6, 8 vì cùng lỗi đọc tầng ấy. Dãy "5, 4, 7, 1, 3, 6, 8" đưa 4 lên thay 2, tức lấy con phải của nút bị xoá chứ không lấy nút cực phải của nhánh trái, và như thế 1 với 3 lại thành hai con của 4.

Đáp án đúng: "35, 20, 45, 10, 25, 40, 22, 30". Cây ban đầu có gốc 35, con trái 20 với hai con 10 và 30, nút 30 có con trái 25, nút 45 có con trái 40. Chèn 22: nhỏ hơn 35 nên sang trái, lớn hơn 20 nên sang phải tới 30, nhỏ hơn 30 nên tới 25, nhỏ hơn 25 nên thành con trái của 25. Khi đó nút 30 có nhánh trái cao hai mức và nhánh phải rỗng nên chênh 2, đây là nút mất cân bằng thấp nhất và thuộc dạng trái–trái, chữa bằng một phép quay phải tại 30: nút 25 lên thay chỗ, giữ 22 làm con trái và nhận 30 làm con phải. Cây thành gốc 35 với 20 và 45, dưới 20 là 10 và 25, dưới 25 là 22 và 30, dưới 45 là 40. "35, 20, 45, 10, 30, 40, 25, 22" là trạng thái nếu không quay gì cả, khi đó cây không còn thoả điều kiện AVL. "35, 20, 45, 10, 25, 40, 30, 22" đặt 30 làm con trái và 22 làm con phải của 25, ngược thứ tự khoá. "35, 20, 45, 10, 40, 25, 22, 30" đọc 40 trước 25 trong cùng mức ba, trái với chiều từ trái sang phải của duyệt theo mức.

Đáp án đúng: "1, 2, 6, 7, 5, 3, 4, 8". Duyệt trước thăm gốc rồi mới xuống nhánh trái và nhánh phải. Cây gốc 1 có con trái 2 (con trái 6, con phải 5, mà 6 chỉ có con trái 7) và con phải 3 (chỉ có con phải 4, mà 4 chỉ có con trái 8). Chạy dãy: thăm 1; vào nhánh trái thăm 2, rồi 6, rồi con trái của 6 là 7, hết nhánh trái của 2 thì sang con phải 5, được 2, 6, 7, 5; vào nhánh phải thăm 3, 3 không có con trái nên xuống con phải 4, rồi con trái của 4 là 8, được 3, 4, 8. "1, 2, 6, 7, 5, 3, 8, 4" đặt 8 trước 4 dù 8 là con của 4, mà duyệt trước luôn thăm cha trước con. "7, 6, 2, 5, 1, 3, 8, 4" là kết quả duyệt giữa, nhận ra vì gốc 1 nằm giữa dãy. "7, 6, 5, 2, 8, 4, 3, 1" là kết quả duyệt sau, nhận ra vì gốc 1 đứng cuối cùng.

Đáp án đúng: "7, 4, 3, 5, 1, 2, 8, 6". Cây có gốc 1 với con trái 3 và con phải 2; 3 có hai con 4 và 5; 4 có con trái 7; 2 có con phải 6; 6 có con trái 8. Duyệt in-order đi cây con trái, rồi gốc, rồi cây con phải. Nhánh trái: vào 3 thì trước hết vào 4, trước 4 lại vào 7 nên in 7, rồi 4, rồi 3, rồi 5, được 7, 4, 3, 5. Kế đó in gốc 1. Nhánh phải: 2 không có con trái nên in 2, rồi xuống 6 mà trước 6 phải in con trái 8, được 2, 8, 6. Vì vậy "1, 3, 4, 7, 5, 2, 6, 8" sai vì đó chính là dãy pre-order của cây này, in gốc trước rồi mới tới hai nhánh; "7, 4, 5, 3, 8, 6, 2, 1" sai vì đó là dãy post-order, gốc 1 bị đẩy xuống cuối cùng; "1, 3, 4, 7, 5, 2, 8, 6" sai vì nó cũng mở đầu bằng gốc 1 như pre-order, mà in-order không bao giờ in gốc trước khi vét hết nhánh trái.

Đáp án đúng: "4, 7, 5, 2, 8, 6, 3, 1". Duyệt hậu tố đi nhánh trái, rồi nhánh phải, rồi gốc. Cây có gốc 1, nhánh trái 2 với hai con 4 và 5, dưới 5 là con trái 7, nhánh phải 3 chỉ có con phải 6, dưới 6 là con trái 8. Nhánh trái cho 4 trước, rồi trong nhánh của 5 ra 7 rồi 5, rồi tới 2, thành 4, 7, 5, 2. Nhánh phải cho 8 rồi 6 rồi 3. Gốc 1 ra sau cùng, nên dãy đầy đủ là 4, 7, 5, 2, 8, 6, 3, 1. Dãy "4, 2, 7, 5, 1, 3, 8, 6" chính là kết quả duyệt trung tố, nhận ra ngay vì gốc 1 nằm giữa dãy. Dãy "4, 2, 7, 5, 1, 8, 6, 3" cũng đọc theo lối trung tố ở nhánh trái và kết thúc bằng 3, nhưng hậu tố thì phần tử cuối luôn là gốc của cả cây. Dãy "4, 2, 1, 5, 7, 8, 6, 3" đặt gốc 1 ở vị trí thứ ba, trong khi hậu tố chỉ thăm gốc sau khi đã in xong cả hai nhánh.

Đáp án đúng: "6, 2, 7, 1, 4, 8, 3, 9". Chèn 6, 7, 8, 9, 2, 1, 4, 3: 6 làm gốc; 7 lớn hơn 6 nên thành con phải; 8 thành con phải của 7; 9 thành con phải của 8; 2 nhỏ hơn 6 nên thành con trái của 6; 1 nhỏ hơn 2 nên là con trái của 2; 4 lớn hơn 2 nên là con phải của 2; 3 nhỏ hơn 6, lớn hơn 2, nhỏ hơn 4 nên là con trái của 4. Các lớp lần lượt là 6; rồi 2, 7; rồi 1, 4, 8; rồi 3, 9. Phương án "6, 7, 8, 9, 2, 1, 4, 3" chỉ chép lại đúng thứ tự chèn, nó không phản ánh cấu trúc cây đã dựng. Phương án "6, 2, 1, 7, 4, 8, 3, 9" đưa 1 lên ngay sau 2, tức trộn lớp hai với lớp ba. Phương án "6, 4, 1, 7, 2, 8, 3, 9" cho 4 làm con trái của 6, nhưng 4 vào cây sau 2 và vì 4 lớn hơn 2 nên phải nằm dưới 2.

Đáp án đúng: "2, 1, 4, 3, 6, 8, 7". Xoá gốc 5 bằng hợp nhất: con trái 2 lên làm gốc, rồi cả cây con phải gốc 6 được treo làm con phải của nút phải nhất trong cây con trái. Đi phải từ 2 được 4, mà 4 chỉ có con trái 3 nên 4 là nút phải nhất, vậy 6 thành con phải của 4. Cây mới: gốc 2 với hai con 1 và 4; 4 có con trái 3 và con phải 6; 6 có con phải 8; 8 có con trái 7. Duyệt theo bề rộng đọc từng mức cho 2, rồi 1 và 4, rồi 3 và 6, rồi 8, cuối cùng 7. "2, 1, 4, 3, 6, 7, 8" sai vì 7 là con của 8 nên phải in sau 8, không thể đứng trước. "4, 2, 6, 1, 3, 8, 7" sai vì đó là kết quả xoá bằng sao chép, khi khoá 4 được chép lên gốc và con trái 3 của nó nối lên thay chỗ. "4, 2, 6, 1, 3, 7, 8" sai vì vừa dùng cách sao chép vừa in 7 trước cha 8.

Đáp án đúng: "4, 2, 7, 1, 3, 6, 8". Nút bị xoá là gốc 5; nhánh trái của nó gồm 2 với con trái 1, con phải 4, trong đó 4 còn con trái 3. Nút cực phải của nhánh trái là 4 vì 4 không có con phải, nên 4 được sao vào gốc, nút 4 cũ bị tháo và con trái 3 của nó lên làm con phải của 2. Cây thành gốc 4, bên trái là 2 với hai con 1, 3, bên phải là 7 với hai con 6, 8. Đọc theo tầng cho 4, rồi 2, 7, rồi 1, 3, 6, 8. Dãy "4, 2, 7, 1, 6, 8, 3" cùng cây ấy nhưng xếp 3 xuống cuối, trong khi 3 là con của 2 nên thuộc tầng thứ ba, phải đứng ngay sau 1. Dãy "2, 1, 4, 7, 3, 6, 8" đưa 2 lên làm gốc, đó là cách nối nhánh chứ không phải sao chép, vì sao chép giữ nguyên hình dạng cây và chỉ chuyển giá trị 4 lên gốc. Dãy "2, 1, 4, 3, 7, 6, 8" cũng lấy 2 làm gốc nên mắc cùng chỗ sai, lại liệt kê 3 ngay sau 1, 4 theo lối đi sâu từng nhánh chứ không theo tầng.

Đáp án đúng: "General graphs may contains cycles". Trong cây, từ gốc tới mỗi nút chỉ có một đường duy nhất nên phép duyệt không bao giờ gặp lại nút đã thăm và không cần ghi nhớ gì. Đồ thị tổng quát thì có chu trình và nhiều đường đi tới cùng một đỉnh, nếu không đánh dấu đỉnh đã thăm thì phép duyệt sẽ quay vòng mãi hoặc xử lý lặp cùng một đỉnh, nên mảng đánh dấu chính là thứ cắt chu trình. "Trees are disconnected" nói ngược: cây theo định nghĩa là liên thông và không có chu trình. "Trees always have a designated root" đúng với cây có gốc và giải thích vì sao ta biết bắt đầu từ đâu, nhưng có gốc vẫn không ngăn được việc thăm lại một đỉnh khi đồ thị có chu trình, nên đó không phải lý do tồn tại của mảng đánh dấu. "Tree cannot be traversed using DFS or BFS" sai hẳn, vì duyệt trước, duyệt giữa và duyệt sau đều là tìm theo chiều sâu, còn duyệt theo mức chính là tìm theo chiều rộng trên cây.

Đáp án đúng: "F, C, D, G, B, A, E, H". Duyệt theo chiều rộng dùng hàng đợi: thăm hết các đỉnh kề của đỉnh đang xét rồi mới đi xa hơn, các đỉnh ngang điều kiện lấy theo thứ tự chữ cái. Với các cạnh A–B, A–E, A–G, B–C, B–D, B–E, C–D, C–F, D–F, E–G, F–G: từ F nạp C, D, G nên dãy mở đầu F, C, D, G. Xét C, nó kề B, D, F, chỉ B là mới nên nạp B. Xét D, các đỉnh kề B, C, F đều đã có trong hàng. Xét G, nó kề A, E, F nên nạp A rồi E. Lấy ra lần lượt B, A, E. Bảy đỉnh đã xong, còn H cô lập nên phép duyệt khởi động lại ở H và H đứng cuối. "F, C, B, D, G, A, E, H" đưa B lên trước D và G, tức đi sâu từ C trước khi xét hết các đỉnh kề của F. "F, C, D, G, A, B, E, H" đặt A trước B, nhưng B được nạp từ C còn A nạp từ G, mà C ra khỏi hàng đợi trước G. "F, C, D, G, B, A, E" đúng mạch nhưng bỏ sót H.

Đáp án đúng: "A, C, D, E, B". Dijkstra mỗi bước kết nạp đỉnh có khoảng cách tạm nhỏ nhất rồi cập nhật theo các cung đi ra. Khởi đầu từ A, khoảng cách tạm là C bằng 3, E bằng 6, B bằng 11, D bằng 21. Nhỏ nhất là C nên kết nạp C, và cung C→D 2 hạ D từ 21 xuống 3 + 2 = 5. Giờ D bằng 5 nhỏ hơn E bằng 6 nên kết nạp D, cung D→B 5 hạ B xuống 5 + 5 = 10. Tiếp theo E bằng 6 là nhỏ nhất nên kết nạp E, cung E→B 2 hạ B xuống 6 + 2 = 8. Cuối cùng kết nạp B với nhãn 8. Vì vậy "A, C, E, B" sai vì nó bỏ D, nhưng sau khi qua C thì D chỉ còn 5, nhỏ hơn E bằng 6; "A, C, D, B" sai vì ngay sau D thì B đang là 10 còn E là 6, nên E phải vào trước; "A, C, B" sai vì lúc đó B vẫn mang nhãn 11 theo cung trực tiếp A→B, lớn hơn cả D bằng 5 và E bằng 6.

Đáp án đúng: "5". Các cung là A sang C nặng 3, A sang D nặng 21, A sang E nặng 6, A sang B nặng 11, C sang D nặng 2, D sang B nặng 5, E sang D nặng 11, E sang B nặng 2. Chạy Dijkstra từ A: cố định A với nhãn 0 rồi cập nhật C bằng 3, E bằng 6, B bằng 11, D bằng 21. Đỉnh tạm nhỏ nhất là C với 3, qua cung C sang D nhãn của D hạ xuống 3 + 2 = 5. Tiếp đó cố định D với 5 và hạ nhãn của B xuống 5 + 5 = 10. Rồi cố định E với 6 và hạ nhãn của B xuống 6 + 2 = 8. Khi B được cố định với 8, tức đường ngắn nhất từ A tới B đã xác định, nhãn của D đang là 5. Con số "21" là nhãn tạm ban đầu lấy từ cung trực tiếp A sang D, bị thay ngay khi C được cố định. Con số "17" ứng với đường qua E là 6 + 11, lớn hơn 5 nên chưa bao giờ được nhận. Phương án "infinity" chỉ đúng nếu D không tới được từ A, nhưng D đã có nhãn hữu hạn ngay từ lần cập nhật đầu tiên.

Đáp án đúng: "B, D, C, B, A, B". Đa đồ thị có hai cạnh song song B–A cùng các cạnh B–C, B–D và C–D; bậc của A, C, D là 2 và của B là 4, đều chẵn nên chu trình Euler tồn tại. Chạy thuật toán từ B: B chưa cô lập, láng giềng đầu theo chữ cái là A nên đẩy A và bỏ một cạnh B–A; tại A còn cạnh B–A thứ hai nên đẩy B và bỏ cạnh đó; tại B còn C và D, chọn C rồi bỏ B–C; tại C còn D nên đẩy D và bỏ C–D; tại D còn B nên đẩy B và bỏ D–B. Giờ B đã cô lập nên các đỉnh lần lượt bị lấy khỏi ngăn xếp và ghi vào E: B, D, C, B, A, B. Phương án "B, A, B, D, C, B" chính là đường đi lúc đẩy vào, chưa qua bước lấy ra, mà E được dựng từ chiều lấy ra nên là đảo của nó. Phương án "B, C, D, B, A, B" hợp lệ về cạnh nhưng ứng với việc chọn C trước A, trái thứ tự chữ cái. Phương án "B, A, C, D, B" dùng cạnh A–C không tồn tại. Phương án "B, C, D, A, B" dùng cạnh D–A không tồn tại và bỏ sót một cạnh B–A.

Đáp án đúng: "A, B, C, E, D, A". Chạy thuật toán từ A với luật luôn lấy đỉnh kề đầu tiên theo thứ tự chữ cái và chưa nằm trong H: từ A lấy B, từ B lấy C, từ C lấy D, từ D chỉ còn E nên lấy E. Tại E hai đỉnh kề là C và D đều đã trong H mà E lại không kề A, nên E bị gỡ và ghi là lựa chọn xấu; D cũng hết đỉnh để đi nên bị gỡ tiếp. Lùi về dãy A, B, C thì đỉnh kề kế tiếp của C sau D là E, đi E rồi từ E lấy D; lúc này H chứa cả năm đỉnh và D kề A nên chu trình đóng lại thành A, B, C, E, D, A. "A, B, C, D, E, A" sai vì E không kề A, hai cạnh duy nhất của E là E–C và E–D. "A, B, C, D, E, C, A" sai vì nó đi qua C hai lần, còn chu trình Hamilton phải thăm mỗi đỉnh đúng một lần. "A, C, D, E, B, A" sai vì bước đầu thuật toán buộc chọn B trước C theo thứ tự chữ cái, hơn nữa E không kề B. "A, D, E, C, B, A" tuy là một chu trình có thật trong đồ thị nhưng không phải thứ tự thuật toán sinh ra, vì từ A nó bỏ qua B để lấy D.

Đáp án đúng: "42". Cây khung nhỏ nhất của 6 đỉnh cần đúng 5 cạnh và không được tạo chu trình. Xét các cạnh theo trọng số tăng: lấy A–B bằng 3, lấy B–C bằng 4, bỏ A–C bằng 6 vì nó khép chu trình với hai cạnh vừa lấy, lấy E–F bằng 8, lấy B–E bằng 11 để nối khối chứa A, B, C với khối chứa E, F, bỏ C–E bằng 12 vì hai đầu đã cùng khối, cuối cùng phải với tới D nên chọn lối nhẹ hơn là D–F bằng 16 thay vì C–D bằng 17. Tổng bằng 3 cộng 4 cộng 8 cộng 11 cộng 16. Số "43" là tổng của cây khung dùng C–D bằng 17 để với tới D, đắt hơn đúng 1. Số "40" dưới mức nhỏ nhất ấy, nó ứng với việc lấy thêm A–C bằng 6 trong khi A–B cùng B–C đã nối ba đỉnh đó, cạnh thừa khép chu trình nên 5 cạnh không còn phủ hết 6 đỉnh. Số "37" cũng dưới mức nhỏ nhất vì bỏ hẳn cạnh nối hai khối, khi đó A, B, C đứng riêng còn D, E, F một khối. Số "45" là tổng của một cây khung dùng cả C–E bằng 12 lẫn A–C bằng 6, hai cạnh nặng hơn lựa chọn thay thế của chúng.