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

Đáp án đúng: "6, 2, 7, 5, 1, 3, 8, 4". Duyệt trung tố đi nhánh trái, rồi gốc, rồi nhánh phải. Cây có gốc 1, nhánh trái 2 với hai con 6 và 5, dưới 5 là con trái 7, nhánh phải 3 chỉ có con phải 4, dưới 4 là con trái 8. Trong nhánh trái: 6 là lá nên ra trước, rồi gốc nhánh 2, rồi vào 5 mà 5 có con trái 7 nên 7 ra trước 5, được 6, 2, 7, 5. Gốc 1 nằm giữa dãy. Nhánh phải: 3 không có con trái nên ra ngay, rồi vào 4 và con trái 8 ra trước 4, được 3, 8, 4. Dãy "6, 7, 5, 2, 8, 4, 3, 1" là kết quả duyệt hậu tố, nhận ra vì gốc 1 đứng cuối dãy. Dãy "6, 2, 7, 5, 1, 8, 4, 3" đúng tới gốc 1 nhưng thăm 8 và 4 trước 3, trong khi 3 không có con trái nên phải được in ngay lúc bước vào nhánh phải. Dãy "1, 2, 6, 7, 5, 3, 4, 8" bắt đầu bằng gốc, dấu hiệu của duyệt tiền tố; trung tố chỉ thăm gốc sau khi in xong toàn bộ nhánh trái.

Đáp án đúng: "A, B, D, E, C". Các cung là A→B = 2, A→D = 20, A→E = 5, A→C = 10, B→D = 1, D→C = 4, E→D = 10, E→C = 1. Chọn A với khoảng cách 0, cập nhật B = 2, E = 5, C = 10, D = 20. Nhỏ nhất là B = 2 nên B vào S; qua B→D = 1 thì D hạ xuống 2 + 1 = 3. Nhỏ nhất kế tiếp là D = 3 nên D vào S; qua D→C = 4 thì C hạ xuống 3 + 4 = 7. Tiếp đến E = 5 vào S; qua E→C = 1 thì C hạ tiếp xuống 5 + 1 = 6. Cuối cùng C = 6 được chọn, nên thứ tự là A, B, D, E, C. Phương án "A, B, C" coi C = 10 là chốt ngay sau khi A và B vào S, bỏ qua D = 3 và E = 5 đều nhỏ hơn. Phương án "A, B, D, C" bỏ E = 5 dù 5 nhỏ hơn giá trị 7 của C lúc đó, mà chính E mới hạ C xuống 6. Phương án "A, B, E, C" bỏ D = 3, trong khi cung B→D = 1 vừa hạ D xuống 3 nên D phải vào S ngay sau B.

Đáp án đúng: "O(n)". Danh sách liên kết đôi không lưu sẵn số phần tử, nên muốn đếm thì phải bắt đầu từ head và đi theo liên kết next cho tới khi hết, mỗi nút được ghé đúng một lần và tăng biến đếm một lần; với n nút thì chi phí tỉ lệ thuận với n. Hai chiều liên kết giúp đi lùi và xoá nút nhanh, nhưng không cho nhảy nhiều nút một bước nên không rút ngắn phép đếm. "O(n^2)" sai vì không có vòng lặp lồng nào, mỗi nút chỉ ghé một lần. "O(nlogn)" sai vì đó là mức chi phí của các thuật toán chia để trị như sắp xếp trộn, còn đếm chỉ là một lượt đi thẳng. "O(1)" sai trong phạm vi câu hỏi: nó chỉ đúng nếu danh sách giữ thêm một biến size được cập nhật mỗi lần thêm hoặc bớt, khi đó không còn là đếm mà là đọc giá trị đã lưu.

Đáp án đúng: "gioG". Ở đoạn mã này dấu sao chỉ lấy bỏ phần tử trên đỉnh mà không in; chỉ sau khi đọc hết chuỗi mới lấy ra lần lượt và in, nên kết quả là phần còn lại đọc ngược. Nạp G, o, o, d, M; hai dấu sao bỏ M rồi d. Nạp o, r, n; bốn dấu sao bỏ n, r, o rồi o. Nạp i, n; một dấu sao bỏ n. Nạp g và hết chuỗi, ngăn xếp còn G, o, i, g nên in ngược từ đỉnh xuống. Chuỗi "gioM" kết thúc bằng M, mà M đã bị dấu sao thứ nhất lấy bỏ nên không còn trong ngăn xếp. Chuỗi "giod" kết thúc bằng d, cũng là ký tự đã bị dấu sao thứ hai lấy bỏ. Chuỗi "Goig" liệt kê theo đúng chiều nạp vào, trong khi vòng lặp cuối lấy từ đỉnh nên phần tử nạp sau cùng là g phải ra trước và G ra sau chót.

Đáp án đúng: "b, c, e". Các cạnh là a–b, b–c, b–d, c–d, c–e, e–f, e–g, e–h, f–g và g–h. Đỉnh khớp là đỉnh mà bỏ nó cùng mọi cạnh của nó thì đồ thị rời thêm: bỏ b thì a mất đường duy nhất nên tách ra; bỏ c thì cụm a, b, d mất liên lạc với cụm e, f, g, h vì c–e là mối nối duy nhất; bỏ e thì f, g, h tuy còn nối nhau qua f–g và g–h nhưng không còn đường nào về phía c. "c, e, a" kể thêm a, mà a chỉ có một cạnh nên bỏ a đi phần còn lại vẫn liên thông; đỉnh bậc một không bao giờ là đỉnh khớp. "e, d, a" kể d, nhưng d nằm trên chu trình b–c–d nên bỏ d thì b và c vẫn nối nhau trực tiếp. "b, c, d" đúng hai đỉnh đầu nhưng thay e bằng d, trong khi bỏ d không làm rời đồ thị còn bỏ e thì cắt cụm f, g, h khỏi phần còn lại.

Đáp án đúng: "Binary search trees". Cây tìm kiếm nhị phân có bất biến: mọi khoá trong cây con trái nhỏ hơn khoá ở gốc, mọi khoá trong cây con phải lớn hơn. Duyệt giữa đi con trái, thăm gốc, rồi con phải, nên nó in hết phần nhỏ hơn trước, rồi khoá hiện tại, rồi phần lớn hơn; lập luận đó đúng ở mọi nút nên dãy thu được tăng dần. "Binary trees" chỉ ràng buộc mỗi nút có nhiều nhất hai con, không ràng buộc gì về giá trị, nên duyệt giữa cho một dãy tuỳ hình dạng cây. "Heaps" chỉ bảo đảm quan hệ cha con theo một chiều, chẳng hạn cha không lớn hơn hai con, nhưng không nói gì về quan hệ giữa hai cây con, nên duyệt giữa của đống không cho dãy có thứ tự; muốn dãy tăng dần từ đống phải lấy phần tử gốc ra nhiều lần liên tiếp. "None of others" sai vì trường hợp cây tìm kiếm nhị phân đúng như đã chỉ ra.

Đáp án đúng: "BA". LZW giữ một chuỗi đang khớp và chỉ thêm mục mới vào từ điển đúng lúc chuỗi đang khớp cộng ký tự vừa đọc không còn trong từ điển, mục mới chính là chuỗi dài hơn ấy. Lần theo AABAACAABD với từ điển đầu gồm (1) là A, (2) là B, (3) là C, (4) là D: chuỗi khớp A gặp A nên AA chưa có, phát (1) và thêm AA thành (5); chuỗi khớp A gặp B nên AB chưa có, phát (1) và thêm AB thành (6); chuỗi khớp B gặp A nên BA chưa có, phát (2) và thêm BA thành (7). Vậy mã (7) chỉ chuỗi BA. Vì vậy "AB" sai vì đó là mục (6), được thêm ở bước ngay trước; "AC" sai vì khi đọc tới C thì chuỗi đang khớp đã là AA nên mục thêm lúc đó là AAC mang mã (8), cặp AC không bao giờ vào từ điển; "ABA" sai vì mục ba ký tự chỉ sinh ra sau khi khớp được một mục hai ký tự, mà AB không bao giờ được khớp lại trong phần còn lại của thông điệp; "BAA" sai vì cũng vậy, BA chỉ xuất hiện một lần duy nhất nên không bao giờ được khớp để mở rộng.

Đáp án đúng: "by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated". Nhờ các phần tử nằm liên tiếp và mỗi phần tử chiếm đúng cùng số byte, địa chỉ của phần tử thứ i tính được bằng địa chỉ đầu cộng i nhân kích thước một phần tử, nên truy cập theo chỉ số mất thời gian hằng số và chương trình chỉ cần lưu một địa chỉ gốc. Phương án "the architecture of computer memory does not allow arrays to store other than serially" quy việc đó cho phần cứng, nhưng bộ nhớ hoàn toàn cho phép lưu rời rạc: danh sách liên kết và cây để các nút rải rác khắp vùng nhớ rồi nối nhau bằng con trỏ. Lưu liên tiếp là một lựa chọn thiết kế để đổi lấy phép tính địa chỉ, chứ không phải điều kiện bắt buộc của kiến trúc.

Đáp án đúng: "2, 1, 4, 3, 7, 6, 8". Cây có gốc 5, con trái 2 với hai con 1 và 4, con trái của 4 là 3; con phải của 5 là 7 với hai con 6 và 8. Xoá 5 theo kiểu hợp nhất: nhánh trái leo lên làm gốc, nhánh phải treo vào nút phải nhất của nhánh trái. Nút phải nhất của nhánh trái là 4, vì từ 2 sang con phải 4 rồi 4 không có con phải; nên cây gốc 7 trở 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 7; 7 có hai con 6 và 8. Các lớp là 2; rồi 1, 4; rồi 3, 7; rồi 6, 8. Phương án "2, 1, 4, 3, 6, 7, 8" xếp 6 cùng lớp với 3 và trước 7, nhưng sau hợp nhất 6 là con của 7 nên nằm ở lớp sâu hơn. Phương án "2, 1, 4, 3, 7, 8, 6" đảo hai con của 7, trong khi duyệt theo lớp đọc con trái 6 trước con phải 8. Phương án "4, 2, 7, 1, 3, 6, 8" lấy nút phải nhất 4 lên làm gốc, đó là kiểu xoá sao chép chứ không phải hợp nhất.

Đáp án đúng: "Recursion". Đệ quy đúng là việc một thuật toán hay một hàm tự gọi chính nó, trực tiếp khi thân hàm gọi thẳng tên mình, hoặc gián tiếp khi nó gọi hàm khác rồi hàm đó gọi lại nó; lời giải thu nhỏ dần bài toán cho tới trường hợp cơ sở, và các lời gọi chồng lên nhau trên ngăn xếp thực thi. "Sub algorithm" sai vì thuật toán con chỉ là đoạn được thuật toán khác gọi tới, nó không bắt buộc và thường không gọi lại chính mình. "Traversal algorithm" sai vì duyệt là tên theo mục đích, tức thăm lần lượt các phần tử của một cấu trúc; nó có thể cài bằng đệ quy nhưng cũng cài được bằng vòng lặp với ngăn xếp hay hàng đợi. "Polish notation" sai vì đó là cách viết biểu thức với toán tử đặt trước toán hạng, một ký pháp chứ không phải một kiểu lời gọi.