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: "1 3 5 7 9". Đọc theo thụt lề thì lệnh in nằm sau lời gọi fun(n-2), nên mỗi lời gọi phải đi hết chiều sâu rồi mới in lúc quay về. Chuỗi lời gọi là fun(9), fun(7), fun(5), fun(3), fun(1), fun(-1); lời gọi với -1 không thoả n > 0 nên trả về ngay mà không in gì. Khi các lời gọi lần lượt quay về, giá trị in ra theo chiều ngược của chuỗi, tức 1, rồi 3, 5, 7 và cuối cùng 9. "9 7 5 3 1" sai vì đó là kết quả nếu lệnh in đứng trước lời gọi đệ quy, kiểu in trước rồi mới đi xuống sâu. "9 7 5 3" sai vì vừa in theo chiều giảm, vừa bỏ mất 1 dù fun(1) vẫn thoả điều kiện n > 0. "7 5 3 1" sai vì nó thiếu 9: lời gọi ngoài cùng cũng in giá trị của nó, và vì in sau đệ quy nên 9 phải là số ra cuối cùng.

Đáp án đúng: "Values in a node is greater than every value in children of it". Tính chất của đống cực đại là tính chất cục bộ giữa cha với con: mỗi nút không nhỏ hơn mọi con trực tiếp của nó. Từ đó suy ra gốc giữ giá trị lớn nhất và mỗi nút không nhỏ hơn mọi giá trị nằm dưới nó, nhưng không có ràng buộc nào so hai nhánh với nhau nên hai cây con của một nút chứa giá trị lớn nhỏ tuỳ ý. Chính vì vậy đống không dùng để tìm một khoá bất kỳ, nó chỉ cho lấy nhanh phần tử lớn nhất. Mô tả "Values in a node is greater than every value in left sub tree and smaller than right sub tree" đặt nhánh trái nhỏ hơn và nhánh phải lớn hơn, đó là thứ tự của cây nhị phân tìm kiếm; trong đống cực đại thì nút còn phải lớn hơn cả nhánh phải nên mô tả ấy trái hẳn. Mô tả "Both of other conditions applies" đòi cả hai điều cùng đúng, nhưng điều kiện kiểu cây tìm kiếm không phải tính chất của đống nên không thể nhận chung.

Đáp án đúng: "O(nlog n)". Sắp xếp vun đống làm hai việc: dựng đống từ mảng, rồi lặp n lần lấy phần tử lớn nhất ở gốc đổi về cuối và vun lại phần còn lại. Mỗi lần vun lại chỉ đi từ gốc xuống theo một đường tới lá, dài nhất là log n bước, nên n lần lấy ra tốn n log n; phần dựng đống còn nhanh hơn thế. Đáng nhớ là cận này đúng cho cả trường hợp tốt nhất và xấu nhất, vì chiều cao đống không phụ thuộc dữ liệu. "O(log n)" là chi phí của đúng một lần vun lại, mới là một trong n bước. "O(n)" là chi phí đọc hết mảng một lần, cũng là chi phí dựng đống, chưa tính n lần lấy phần tử lớn nhất. "O(n^2)" là cận xấu của những thuật toán đổi chỗ các phần tử lân cận như sắp xếp chèn hay nổi bọt; vun đống không rơi xuống mức đó vì nó luôn tìm được phần tử lớn nhất trong log n bước.

Đáp án đúng: "In coalesced hashing, the linked list is created inside the hash table and a colliding key is put in the last available position of the table.". Nét riêng của móc nối hợp nhất là danh sách liên kết nằm ngay trong bảng băm: mỗi ô vừa giữ khoá vừa giữ chỉ số ô kế tiếp của chuỗi. Khoá bị va chạm được đặt vào ô trống cuối cùng của bảng, rồi ô va chạm móc liên kết tới ô đó; lấp từ cuối bảng trở về giúp các ô mà hàm băm hay trỏ tới còn trống cho khoá về sau, nhờ vậy các chuỗi ít dính vào nhau hơn. "In coalesced hashing, the linked list is created outside the hash table and a colliding keys are put in the list connected to the colliding position of the table." mô tả móc nối rời, nơi bảng chỉ giữ con trỏ còn các nút nằm ngoài bảng. "In coalesced hashing, the linked list is created inside the hash table and a colliding key is put in the first available position of the table." lấp ô trống đầu tiên, đó là lối của dò tuyến tính và nó tiêu mất đúng những ô mà khoá sau sẽ băm tới. "Because in coalesced hashing, the linked list is created inside the hash table, thus the searching must be carried out sequentially." sai ở chỗ tìm kiếm không quét tuần tự cả bảng: ta băm để biết ô đầu chuỗi rồi lần theo liên kết, nên chỉ xem các khoá trong cùng một chuỗi.

Đáp án đúng: "(1)". Đó là bảng có 110 ở ô 0, 111 ở ô 1, 32 ở ô 2, 101 ở ô 3, 74 ở ô 4, 131 ở ô 5 và các ô 6, 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: 74 vào ô 4, 111 vào ô 1, 110 vào ô 0, 32 vào ô 2; 101 băm về ô 1 đang có 111 nên dò ô 2 có 32 rồi dừng ở ô 3; 131 cũng băm về ô 1 nên dò 2, 3, 4 đều đầy và dừng ở ô 5. Vì vậy "(4)" sai vì nó đặt 131 ở ô 3 và 101 ở ô 5, chỉ xảy ra nếu 131 được chèn trước 101, trái thứ tự đề cho; "(2)" sai vì nó đẩy 131 xuống ô 8 và 101 xuống ô 9 trong khi ô 3 và ô 5 còn trống ngay trên đường dò; "(3)" sai vì nó đặt 101 ở ô 8 và 131 ở ô 9, cũng bỏ qua ô trống đầu tiên gặp được, dấu hiệu của bước dò khác 1 chứ không phải dò tuyến tính.

Đáp án đúng: "B, A, C, E, G, D, F, H". Các cạnh là A–B, A–E, A–G, B–C, B–E, C–D, D–F, E–G, F–G, còn H đứng riêng. Duyệt theo chiều rộng từ B: thăm B rồi xếp hàng các lân cận theo thứ tự chữ cái A, C, E. Lấy A ra, nó thêm G vào hàng; lấy C ra, nó thêm D; lấy E ra, mọi lân cận đã có trong hàng; lấy G ra, nó thêm F; rồi lấy D và F. Trật tự thăm là B, A, C, E, G, D, F, và vì H chưa thăm nên phép duyệt khởi động lại ở H. Dãy "B, A, E, G, F, D, C, H" là kết quả duyệt theo chiều sâu, nó lao một mạch A, E, G, F, D thay vì rải theo từng lớp. Dãy "B, A, C, E, G, D, F" đúng trật tự nhưng bỏ đỉnh cô lập H, trong khi duyệt cả đồ thị phải lặp lại ở mọi đỉnh chưa thăm. Dãy "B, A, C, E, G, F, D, H" đổi chỗ D với F, nhưng D được phát hiện từ C ở lớp thứ hai còn F chỉ xuất hiện khi lấy G ra, nên D vào hàng trước F.

Đáp án đúng: "In chaining, each position of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys". Phương pháp chuỗi móc nối coi bảng băm là mảng các đầu danh sách: mỗi ô, không trừ ô nào, gắn với một danh sách liên kết chứa những khoá băm về đúng chỉ số đó, nên va chạm chỉ làm một danh sách dài thêm chứ không đẩy khoá sang ô khác, và hệ số tải có thể vượt 1. Phương án "In chaining, only some positions of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys" giới hạn sai: cấu trúc phải đồng nhất ở mọi ô vì ta không biết trước khoá sẽ băm về đâu, ô chưa có khoá đơn giản là một danh sách rỗng. Phương án "In chaining, the linked-list is used instead of array for a hash table" đảo ngược vai trò: bảng vẫn là mảng để tới được ô theo chỉ số trong một bước, danh sách chỉ nằm phía sau mỗi ô. Phương án "None of others" sai vì phát biểu gắn mọi ô với một danh sách đã nêu đúng cơ chế.

Đáp án đúng: "singly linked list". Câu nói tới một cấu trúc mà mỗi phần tử gồm dữ liệu kèm đúng một liên kết tới phần tử kế tiếp, và chính một liên kết đó đủ xâu các phần tử thành chuỗi, đó là danh sách liên kết đơn. Cấu trúc "doubly linked list" có hai liên kết ở mỗi nút, một tới nút sau và một tới nút trước, nên không khớp với mô tả chỉ có liên kết tới phần tử kế tiếp. Cấu trúc "binary search tree" cũng có hai liên kết nhưng là tới con trái với con phải, lại kèm ràng buộc thứ tự giá trị, nên nó không phải một chuỗi tuyến tính. Cấu trúc "skip list" cho mỗi nút nhiều liên kết tiến ở nhiều mức để nhảy xa, chính phần nhiều mức ấy mới làm nên nó, vì vậy mô tả chỉ một liên kết duy nhất là chưa đủ.

Đáp án đúng: "7 11 6 4 3 5 12 8 2". Danh sách liên kết đôi cho phép đi lùi, nên f lấy ngay p.prev là nút 3 mà không cần dò từ đầu. Bốn phép gán q.prev=f, q.next=p, f.next=q và p.prev=q khâu nút 5 vào giữa nút 3 và nút 12 theo cả hai chiều. "7 11 6 4 3 12 8 2 5" là thêm vào cuối, phải đi qua tail. "7 11 6 4 3 12 5 8 2" là chèn sau p, lúc đó phải dùng p.next chứ không phải p.prev. "7 5 11 6 4 3 12 8 2" là chèn sau nút đầu, chỉ đúng nếu p là nút thứ hai của danh sách. "5 7 11 6 4 3 12 8 2" là chèn vào đầu, việc đó bắt buộc gán lại head mà đoạn mã không chạm tới head.

Đáp án đúng: "4B4Q3B2Q5B2Q". Mã hoá theo độ dài loạt thay mỗi đoạn ký tự giống nhau liền nhau bằng cặp số đếm rồi ký tự. Cắt BBBBQQQQBBBQQBBBBBQQ thành các loạt: bốn B, bốn Q, ba B, hai Q, năm B, hai Q; tổng 4+4+3+2+5+2 = 20, đúng độ dài thông điệp gốc. Ghép theo khuôn số trước chữ sau được 4B4Q3B2Q5B2Q. "4B4Q3B2Q5B" bỏ mất loạt hai Q cuối, giải mã lại chỉ còn 18 ký tự. "4B4Q3B2Q5B2QQ" thêm một chữ Q lẻ sau cặp 2Q, làm thông điệp giải ra dài 21 ký tự. "B4Q4B3Q2B5QQ2" viết ký tự trước số đếm, nên đọc theo khuôn đó thì loạt đầu thành một B rồi bốn Q, trong khi loạt đầu của thông điệp là bốn B, và phần QQ2 ở cuối còn không ghép được thành cặp nào.

Đáp án đúng: "GoodAf". Hàng đợi nhả theo nguyên tắc vào trước ra trước, và mỗi dấu sao nhả đúng một ký tự nên độ dài kết quả bằng số dấu sao: thông điệp có hai dấu sao sau GoodA, ba dấu sao sau fter và một dấu sao sau Noo, tổng 2 + 3 + 1 = 6, vậy kết quả phải dài 6 ký tự. Chạy tay: nạp G, o, o, d, A; hai dấu sao nhả G rồi o; nạp f, t, e, r; ba dấu sao nhả o, d, A; nạp N, o, o; dấu sao cuối nhả f; ký tự n còn lại chỉ được nạp vào. Ghép theo thứ tự nhả được G, o, o, d, A, f. Vì vậy "Adoretfo" sai vì nó dài 8 ký tự và lại nhả theo chiều ngược, lấy ký tự vào sau cùng trước, tức hành vi của ngăn xếp; "odAfter" sai vì nó dài 7 ký tự và bỏ hai ký tự đầu G, o mà hai dấu sao đầu tiên buộc phải nhả; "GoodA" sai vì chỉ có 5 ký tự, nó bỏ sót lần nhả của dấu sao thứ sáu, lúc đó đầu hàng đang là f.

Đáp án đúng: "9". Hàm in sang luồng chuẩn khi count lẻ và sang luồng lỗi khi count chẵn, rồi gọi tiếp với count-1 cho tới khi count bằng 0, nên một lời gọi printOut(X) chạy qua đủ các giá trị X, X-1, cho tới 0. Số dòng mang nhãn StdOut chính là số giá trị lẻ trong đoạn đó: với X bằng 9 các giá trị lẻ là 9, 7, 5, 3, 1, đúng 5 dòng, và chuỗi chỉ tốn 9 lời gọi đệ quy. Con số "10" cũng cho 5 dòng vì 10 chẵn nên in sang luồng lỗi, nhưng nó tốn thêm một lời gọi nên không phải lựa chọn ít bước nhất như câu hỏi đòi. Con số "8" chỉ có các giá trị lẻ 7, 5, 3, 1, tức 4 dòng, thiếu một dòng. Con số "11" cho các giá trị lẻ 11, 9, 7, 5, 3, 1, tức 6 dòng, nhiều hơn yêu cầu.

Đáp án đúng: "(4)", tức mảng vòng có r ở ô 1, l ở ô 2, d ở ô 3, còn các ô 0, 4, 5 trống. Mảng sáu ô, nạp từ ô 0 trở đi, mỗi dấu sao lấy ra ở đầu hàng. Chuỗi vào lần lượt là H, e, l, l, o, bốn dấu sao, W, o, r, l, hai dấu sao, d, một dấu sao. Chạy theo đó: H, e, l, l, o chiếm các ô 0 đến 4; bốn dấu sao lấy ra H, e, l, l nên đầu hàng lùi tới ô 4 chỉ còn o; W vào ô 5, rồi o, r, l quay vòng vào các ô 0, 1, 2; hai dấu sao kế tiếp lấy ra o ở ô 4 và W ở ô 5; d vào ô 3; dấu sao cuối lấy ra o ở ô 0. Còn lại r ở ô 1, l ở ô 2, d ở ô 3. Phương án "(1)" đặt r ở ô 4, l ở ô 5 và d ở ô 0, lệch đúng một vòng so với vị trí thật. Phương án "(2)" đặt r ở ô 5, l ở ô 0 và d ở ô 1, cũng đúng nội dung nhưng sai điểm bắt đầu. Phương án "(3)" dồn r, l, d về các ô 0, 1, 2, ứng với việc nén hàng đợi về đầu mảng thay vì để đầu hàng trôi theo vòng.

Đáp án đúng: "Saving data storage". Nén dữ liệu là biến một biểu diễn dài thành biểu diễn ngắn hơn bằng cách khai thác phần dư thừa, chẳng hạn mã Huffman cho ký tự hay gặp một chuỗi bit ngắn, hay RLE gộp các ký tự lặp lại; cái đạt được trực tiếp và luôn luôn đúng là số byte phải lưu giảm đi, nên đây là lý do sát nhất với câu hỏi. "Saving network band-width" đúng trong tình huống dữ liệu phải truyền qua mạng, khi ít byte hơn nghĩa là ít thời gian truyền hơn, nhưng đó là hệ quả của cùng một việc giảm kích thước và chỉ xuất hiện ở bài toán truyền tin, trong khi câu hỏi không giới hạn vào ngữ cảnh mạng. "Increasing system performance" không phải lý do vì nén và giải nén còn tốn thêm thời gian xử lý; nó chỉ có lợi gián tiếp khi hệ thống bị nghẽn ở đĩa hoặc đường truyền. "Just compress data for individual hobby" sai vì nó không nêu lợi ích kỹ thuật nào cả.

Đáp án đúng: "Mdnroon". Mỗi dấu sao lấy phần tử trên đỉnh ngăn xếp rồi in ngay, nên thứ tự in ngược thứ tự nạp. Nạp G, o, o, d, M; hai dấu sao in M rồi d, còn lại G, o, o. Nạp o, r, n; bốn dấu sao in n, r, o rồi o, còn lại G, o. Nạp i, n; một dấu sao in n, còn lại G, o, i. Nạp g rồi hết chuỗi, nên bảy dấu sao cho đúng bảy ký tự. Chuỗi "Mdnrono" đổi chỗ hai ký tự cuối, nhưng sau khi bốn dấu sao đã vét tới o thì lần nạp i, n đặt n lên đỉnh, nên dấu sao cuối phải in n chứ không phải o. Chuỗi "MdnrooG" kết thúc bằng G, mà G nạp đầu tiên nên nằm dưới cùng và không thể ra khi trên nó vẫn còn o với n. Chuỗi "Mdonroo" in o ở vị trí thứ ba, trong khi ngay sau hai lần in đầu thì đỉnh ngăn xếp là n của lần nạp o, r, n.

Đáp án đúng: "2". Các cạnh là A–B, A–C, A–D, A–G, B–E, C–E, D–F, E–F và E–G, nên A và E đều bậc 4, còn B, C, D, F, G đều bậc 2. Xếp theo bậc giảm dần được A, E rồi nhóm bậc hai theo chữ cái là B, C, D, F, G. Tô dần, mỗi đỉnh nhận màu nhỏ nhất chưa bị đỉnh kề đã tô dùng: A nhận 1; E không kề A nên cũng nhận 1; B kề A và E nên nhận 2; C kề A và E nên nhận 2; D kề A nên nhận 2; F kề E màu 1 và D màu 2 nên nhận 3; G kề A màu 1 và E màu 1 nên màu nhỏ nhất dùng được là 2. "1" không dùng được vì cả hai đỉnh kề của G đều đã mang màu 1. "3" bỏ qua màu 2 dù màu 2 vẫn hợp lệ cho G, trái với nguyên tắc lấy màu nhỏ nhất. "4" đòi ba màu đầu đều bị chặn, nhưng G chỉ có hai đỉnh kề nên nhiều nhất chặn được hai màu. "5" càng không thể, vì cả đồ thị tô xong chỉ dùng tới ba màu.

Đáp án đúng: "35, 22, 39, 12, 27, 37, 24, 32". Cây ban đầu có gốc 35, con trái 22 với hai con 12 và 32 (32 chỉ có con trái 27), con phải 39 chỉ có con trái 37. Chèn 24: nhỏ hơn 35 nên sang 22, lớn hơn 22 nên sang 32, nhỏ hơn 32 nên sang 27, nhỏ hơn 27 nên thành con trái của 27. Lúc này nút 32 có cây con trái cao hai tầng và cây con phải rỗng, hệ số cân bằng -2, mất cân bằng kiểu trái-trái vì khoá mới đi trái hai lần liên tiếp; quay phải tại 32 đưa 27 lên thay chỗ, với con trái 24 và con phải 32. Cây thành gốc 35, mức hai là 22 và 39, mức ba là 12, 27, 37, mức bốn là 24 và 32, nên duyệt theo chiều rộng cho 35, 22, 39, 12, 27, 37, 24, 32. "35, 22, 39, 12, 37, 27, 24, 32" đảo 27 với 37 ở mức ba, nhưng 27 thuộc nhánh trái nên phải đọc trước. "35, 22, 39, 12, 32, 37, 27, 24" và "35, 22, 39, 12, 32, 37, 24, 27" đều giữ 32 ở mức ba, tức không quay, và như vậy 32 vẫn mang hệ số cân bằng -2 nên cây không còn là AVL.

Đáp án đúng: "Tree". Cây được định nghĩa đúng bằng hai điều kiện ấy, liên thông và không chứa chu trình đơn; hệ quả là cây n đỉnh có đúng n-1 cạnh, giữa hai đỉnh bất kỳ có duy nhất một đường đi, và thêm bất kỳ cạnh mới nào cũng sinh ngay một chu trình. Vì vậy "Kn" sai vì đồ thị đầy đủ n đỉnh nối mọi cặp đỉnh, với n từ 3 trở lên nó chứa tam giác, tức có chu trình đơn; "Simple graph" sai vì đồ thị đơn chỉ nói không có khuyên và không có cạnh song song, nó vẫn được phép chứa chu trình và còn có thể không liên thông; "Pseudo graph" sai vì giả đồ thị cho phép khuyên, mà một khuyên tự nó đã là chu trình ngắn nhất, trái hẳn điều kiện không có chu trình đơn.

Đáp án đúng: "16, 7, 20, 3, 12, 17, 1". Chèn lần lượt vào cây tìm kiếm rỗng: 16 thành gốc; 7 nhỏ hơn 16 nên thành con trái của 16; 3 nhỏ hơn 16 rồi nhỏ hơn 7 nên thành con trái của 7; 1 nhỏ hơn 3 nên thành con trái của 3; 12 nhỏ hơn 16 nhưng lớn hơn 7 nên thành con phải của 7; 20 lớn hơn 16 nên thành con phải của 16; 17 lớn hơn 16 và nhỏ hơn 20 nên thành con trái của 20. Các mức vì vậy là 16; rồi 7 và 20; rồi 3, 12, 17; rồi 1. Duyệt theo chiều rộng cho 16, 7, 20, 3, 12, 17, 1. Dãy "16, 7, 20, 3, 12, 1, 17" đặt 1 trước 17, nhưng 17 là con của 20 nên nằm ở mức ba còn 1 là con của 3 ở mức bốn. Dãy "16, 7, 20, 3, 17, 1, 12" đẩy 12 xuống mức cuối, dù 12 là con phải của 7 nên cùng mức với 3 và 17. Dãy "16, 7, 20, 3, 17, 12, 1" cũng đưa 12 khỏi mức ba và còn xếp nó sau 17, trong khi mức ba đọc từ trái sang phải là 3, 12 rồi 17.