Câu hỏi: CSD201 Cấu trúc dữ liệu và giải thuật – Bộ ôn tập thi lại số 3

Đáp án đúng: "40, 25, 50, 15, 33, 45, 30, 35". Cây ban đầu có gốc 40, con trái 25 với hai con 15 và 35, con trái của 35 là 30, còn 50 có con trái 45. Chèn 33: nhỏ hơn 40 nên sang 25, lớn hơn 25 nên sang 35, nhỏ hơn 35 nên sang 30, lớn hơn 30 nên thành con phải của 30. Lúc này nút 35 có nhánh trái cao 2 và nhánh phải cao 0, lệch 2 nên mất cân bằng; đường chèn đi trái rồi phải nên phải quay kép: quay trái quanh 30 rồi quay phải quanh 35, đưa 33 lên làm gốc nhánh với hai con 30 và 35. Cây thành 40 có hai con 25 và 50; 25 có hai con 15 và 33; 50 có con trái 45. Duyệt theo lớp cho 40; rồi 25, 50; rồi 15, 33, 45; rồi 30, 35. Phương án "40, 25, 50, 15, 30, 45, 33, 35" ứng với quay đơn để 30 lên thay 35. Phương án "40, 25, 50, 15, 35, 45, 30, 33" ứng với không quay gì, giữ 35 tại chỗ và treo 33 dưới 30. Phương án "40, 25, 50, 15, 30, 45, 35, 33" vừa giữ 30 ở lớp hai lại xếp 35 trước 33 ở lớp ba, trong khi sau quay kép lớp ba chỉ còn 30 và 35.

Đáp án đúng: "27". Cây khung nhỏ nhất của sáu đỉnh gồm đúng năm cạnh; chạy Kruskal theo trọng số tăng dần: B–C = 2 nhận, A–C = 4 nhận, A–D = 5 nhận, C–D = 6 bỏ vì tạo chu trình A–C–D, D–F = 7 nhận, B–E = 9 nhận và lúc này đủ sáu đỉnh. Tổng 2 + 4 + 5 + 7 + 9 = 27. "28" sai vì nó dùng C–E = 10 để kéo E vào cây thay cho B–E = 9, mà B đã nằm trong cây nên cạnh 9 rẻ hơn và vẫn hợp lệ. "26" sai vì nó cộng cả C–D = 6, cạnh này nối hai đỉnh đã cùng một thành phần nên tạo chu trình. "24" sai vì nó lấy năm cạnh rẻ nhất 2, 4, 5, 6, 7 mà không kiểm tra gì: vừa có chu trình qua C–D, vừa bỏ rơi đỉnh E. "18" sai vì 2 + 4 + 5 + 7 chỉ là bốn cạnh, không thể phủ sáu đỉnh khi cây khung luôn cần năm cạnh.

Đáp án đúng: "D, B, C, F, A, E, G, H". Duyệt theo chiều rộng xuất phát ở D: thăm D rồi xếp các láng giềng của nó vào hàng đợi theo thứ tự chữ cái, mà D kề B, C, F nên tầng kế tiếp đúng là B, C, F. Lấy B ra thấy láng giềng chưa thăm là A rồi E; lấy C ra không thêm được gì vì B, D, F đã thăm; lấy F ra bổ sung G. Vậy thứ tự thăm là D, B, C, F, A, E, G, và còn H là đỉnh cô lập nên phép duyệt phải khởi động lại ở H để không bỏ đỉnh nào, cho dãy đủ tám đỉnh. Dãy "D, B, C, F, A, E, G" đi đúng tới G nhưng bỏ hẳn H, trong khi duyệt một đồ thị phải phủ mọi đỉnh, kể cả đỉnh không có cạnh nào. Dãy "D, C, F, B, E, A, G, H" đặt C trước B ngay tầng đầu, trái với yêu cầu thăm theo thứ tự chữ cái khi các đỉnh ngang khả năng chọn. Dãy "D, C, B, F, A, G, E, H" xếp G trước E, nhưng E đã vào hàng đợi từ lúc xử lý B còn G chỉ vào khi tới F, nên E phải ra trước G.

Đáp án đúng: "O(nlog n)". Quicksort phân hoạch mảng quanh một chốt rồi gọi đệ quy hai phần; khi chốt chia tương đối đều, cây đệ quy sâu khoảng log n mức và mỗi mức tốn khoảng n phép so sánh cho các bước phân hoạch, nên tổng chi phí là n log n, và đó cũng là độ phức tạp trung bình thường được dùng để gọi tên thuật toán. "O(log n)" là chi phí của một lần tìm nhị phân hay một lần đi từ gốc xuống lá, nhỏ hơn cả việc đọc hết mảng nên không thể là chi phí sắp xếp. "O(n)" là chi phí của đúng một lượt phân hoạch, mới là một mức trong cây đệ quy. "O(n^2)" đúng ở trường hợp xấu nhất, khi chốt luôn rơi vào phần tử nhỏ nhất hoặc lớn nhất, chẳng hạn mảng đã sắp sẵn mà chốt lấy ở đầu, làm đệ quy sâu tới n mức; đó là cận xấu nhất chứ không phải độ phức tạp vẫn được nêu cho quicksort.

Đáp án đúng: "ouToDay". Hàng đợi vào trước ra trước, nên mỗi dấu sao loại bỏ ký tự cũ nhất còn trong hàng, và vòng cuối in ra theo đúng thứ tự nạp vào. Chạy tay theo đúng thứ tự ký tự của từ: nạp H, o, w, A, r, e; ba dấu sao bỏ H, o, w, còn A, r, e; nạp Y, o, u; hai dấu sao bỏ A, r, còn e, Y, o, u; nạp T, o; hai dấu sao bỏ e và Y, còn o, u, T, o; nạp D, a, y. Hàng còn o, u, T, o, D, a, y và in ra đúng dãy đó. "uToDay" thiếu chữ o đứng đầu, tức tính thừa một lần loại bỏ so với bảy dấu sao có trong từ. "ouToDa" thiếu y ở cuối, dù y được nạp sau dấu sao cuối cùng nên không ai lấy nó ra. "yaDoTu" là dãy đảo ngược, đó là cách lấy ra của ngăn xếp chứ không phải của hàng đợi.

Đáp án đúng: "4". Bubble sort chỉ đổi chỗ hai phần tử kề nhau khi chúng đứng sai thứ tự, nên tổng số lần đổi chỗ bằng đúng số cặp nghịch thế của mảng ban đầu. Trong 2, 5, 1, 3, 4 các cặp đứng sai thứ tự là 2 với 1, 5 với 1, 5 với 3 và 5 với 4, đúng bốn cặp. Chạy tay cho cùng con số: lượt một đổi 5 với 1, 5 với 3, 5 với 4 đưa 5 về cuối và mảng thành 2, 1, 3, 4, 5; lượt hai đổi 2 với 1 cho 1, 2, 3, 4, 5; lượt ba không còn lần đổi nào nên cờ swapped tắt, tổng 3 cộng 1 bằng 4. Vì vậy "5" sai vì nó đòi một cặp nghịch thế thứ năm, mà mọi cặp còn lại như 2 với 3, 2 với 4, 1 với 3, 3 với 4 đều đã đúng thứ tự; "6" sai vì sáu cặp là hơn nửa trong mười cặp của mảng năm phần tử, chỉ xảy ra với mảng gần như đảo ngược; "7" sai vì nó đếm lẫn cả những lần so sánh không kèm đổi chỗ, riêng lượt một đã có bốn lần so sánh mà chỉ ba lần đổi.

Đáp án đúng: "1 4 4". Hàm gọi đệ quy trước rồi mới in, nên các số dư bật ra theo chiều ngược: t(100, 8) gọi t(12, 8), t(12, 8) gọi t(1, 8), t(1, 8) gọi t(0, 8) và lời gọi này dừng ngay vì điều kiện n lớn hơn 0 không còn đúng. Khi quay về, t(1, 8) in 1%8 = 1, t(12, 8) in 12%8 = 4, t(100, 8) in 100%8 = 4, cho 1 4 4; đó đúng là biểu diễn cơ số 8 của 100 vì 1 nhân 64 cộng 4 nhân 8 cộng 4 bằng 100. Dãy "1 2 0" không ứng với số dư nào trong chuỗi, vì ba số dư thu được chỉ là 1, 4 và 4. Dãy "1 6 6" đọc thành 166 trong cơ số 8, tức giá trị 118, không phải 100. Phương án "None of the others." bị loại vì dãy 1 4 4 đã khớp đúng cả giá trị lẫn thứ tự in.

Đáp án đúng: "Node f = tail.prev; f.next = null; tail = f;". Trong danh sách liên kết đôi, tail.prev cho ngay nút kế cuối mà không cần đi từ head, nên phép gán f = tail.prev là O(1); f.next = null cắt liên kết xuôi tới nút cuối cũ và tail = f dời đuôi về f, nhờ đó nút cuối cũ không còn ai tham chiếu và cả hai mốc head, tail đều nhất quán. Phương án "Node f = tail.prev; f.next = null;" cắt đúng nhưng bỏ quên tail, nên tail vẫn trỏ vào nút vừa bị loại: đi xuôi từ head thì không thấy nút cuối mà biến tail lại khẳng định nó còn đó. Phương án "Node f = tail.prev; f.next = tail; tail = f;" gán lại chính liên kết cũ rồi mới dời tail, kết quả là nút cuối vẫn nằm trong danh sách trong khi tail chỉ vào nút kế cuối, không nút nào bị xoá. Phương án "Node f = tail.prev; f.next = tail.next; tail = f.next;" lấy tail.next vốn bằng null nên f.next = null là đúng, nhưng ngay sau đó tail = f.next lại đặt tail bằng null, làm mất hẳn đuôi danh sách dù các nút phía trước vẫn còn.

Đáp án đúng: "7, 4, 5, 3, 8, 6, 2, 1". Post-order đi cây con trái, rồi cây con phải, cuối cùng mới tới gốc. Nhánh trái của gốc 1 là nút 3: xuống 4 thì phải xử lý con trái 7 trước nên ra 7, rồi 4, rồi lá 5, rồi 3, cho 7, 4, 5, 3. Nhánh phải là nút 2: 2 không có con trái, con phải 6 lại có con trái 8, nên ra 8, rồi 6, rồi 2. Gốc 1 in sau cùng. "7, 4, 3, 5, 1, 2, 8, 6" sai vì đó là dãy in-order, trong đó gốc 1 nằm giữa hai nhánh thay vì ở cuối. "1, 3, 4, 7, 5, 2, 6, 8" sai vì đó là dãy pre-order, mở đầu bằng gốc 1 trong khi post-order luôn mở đầu bằng một lá. "1, 3, 4, 7, 5, 2, 8, 6" sai vì nó cũng bắt đầu từ gốc như pre-order, lại còn in 8 trước cha 6 nên không khớp với phép duyệt nào.

Đáp án đúng: "A binary tree T is a set of nodes such that either • T is empty, or • T is partitioned into 3 disjoint subsets: - A single node r, the root, and - Two binary trees, called left subtree and right subtree of r.". Định nghĩa đệ quy của cây nhị phân phải nhận trường hợp rỗng, bởi nhánh trái lẫn nhánh phải của một nút lá đều là cây rỗng; thiếu mệnh đề rỗng thì phép phân rã không có điểm dừng. Cách viết "A binary tree T is a set of one or more nodes such that T is partitioned into 3 disjoint subsets: • A single node r, the root • Two sets that are binary trees, called left subtree and right subtree of r." khởi đầu bằng tập hợp có một nút trở lên, tức không nhận cây rỗng, nên khi phân rã tới một lá thì hai cây con của lá ấy chẳng thuộc lớp vừa định nghĩa và dây đệ quy treo lại. Cách viết "A binary tree T is a set of nodes such that either • T is empty, or • T is partitioned into 3 disjoint subsets: - A single node r, the root, and - Two non-empty binary trees, called left subtree and right subtree of r." có mệnh đề rỗng nhưng lại đòi hai cây con khác rỗng, kéo theo mọi nút đã có con thì phải có đủ hai con khác rỗng, nên cây một nút hay cây lệch hẳn về một bên đều bị loại oan dù chúng vẫn là cây nhị phân.