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

Đáp án đúng: "4F4O3F2O5F2O". Mã hoá theo độ dài loạt đi từ đầu tới cuối, gom mỗi cụm ký tự giống nhau liền nhau thành một cặp gồm số lần lặp kèm ký tự. Tách chuỗi FFFFOOOOFFFOOFFFFFOO được sáu cụm FFFF, OOOO, FFF, OO, FFFFF, OO, cho ra 4F, 4O, 3F, 2O, 5F, 2O; cộng các số lại 4 + 4 + 3 + 2 + 5 + 2 = 20 đúng bằng độ dài chuỗi gốc, đó là cách tự kiểm nhanh nhất. Vì vậy "4F4O3F2O5F" sai vì nó dừng ở cụm thứ năm và bỏ hẳn hai ký tự O cuối, tổng chỉ còn 18 trong 20; "FFFFOOOOFFFOOFFFFFOO" sai vì đó là thông điệp thô chưa mã hoá, không có cặp số nào; "4F4O3F2O5F2OO" sai vì nó viết 2OO, tức vừa ghi số lần lặp vừa viết lặp ký tự, trong khi mỗi cụm chỉ gồm một số và đúng một ký tự, nên giải mã ngược lại sẽ thừa một chữ O.

Đáp án đúng: "BC". Thuật toán LZW nối thêm đúng một ký tự vào cụm đang khớp để tạo mục mới, nên từ điển dài ra từng ký tự một. Mã hoá AABCAAAABD với từ điển đầu là 1 cho A, 2 cho B, 3 cho C, 4 cho D: gặp AA chưa có nên phát mã của A và thêm AA làm mục 5; gặp AB chưa có nên phát mã của A và thêm AB làm mục 6; gặp BC chưa có nên phát mã của B và thêm BC làm mục 7; gặp CA chưa có nên phát mã của C và thêm CA làm mục 8; sau đó AA khớp mục 5, gặp AAA nên thêm AAA làm mục 9; rồi AB khớp mục 6, gặp ABD nên thêm ABD làm mục 10. Vậy mã 7 chỉ cụm BC. Cụm "CA" là mục 8, sinh ra ngay sau BC. Cụm "BCA" dài ba ký tự nên chỉ có thể xuất hiện sau khi BC đã nằm trong từ điển và được khớp lại một lần nữa, điều không xảy ra trong thông điệp này. Cụm "CAA" không bao giờ được thêm vào, mục đứng sau CA là AAA.

Đáp án đúng: "5, 2, 6, 1, 4, 7, 8". Cây có gốc 5, con trái 3 với hai con 1 và 4, con phải của 1 là 2; con phải của 5 là 6 với hai con 7 và 8. Xoá 3 theo kiểu sao chép: lấy nút phải nhất của nhánh trái của 3, đi từ 1 sang con phải 2 rồi 2 không còn con phải nên nút cần là 2; chép 2 vào chỗ của 3 rồi tháo nút 2 ở vị trí cũ, nên 1 mất con phải. Cây mới: gốc 5 với hai con 2 và 6; 2 có hai con 1 và 4; 6 có hai con 7 và 8. Các lớp là 5; rồi 2, 6; rồi 1, 4, 7, 8. Phương án "5, 2, 6, 1, 7, 8, 4" đẩy 4 xuống sau 7 và 8, nhưng 4 là con phải của 2 nên cùng lớp với 1, 7, 8 và đứng ngay sau 1. Phương án "5, 1, 6, 2, 7, 8, 4" lấy 1 lên thay 3, tức dùng gốc nhánh trái thay vì nút phải nhất của nhánh trái. Phương án "5, 1, 6, 7, 8, 2, 4" cũng đặt 1 vào chỗ của 3 rồi đẩy 2 và 4 xuống sâu hơn, sai ngay ở bước chọn nút thay thế.

Đáp án đúng: "doring". Ngăn xếp lấy ra ở đỉnh, nên mỗi dấu sao in chữ cái vừa đẩy vào gần nhất. Chạy tay: đẩy G, o, o, d rồi hai sao lấy d và o, in do; đẩy M, o, r rồi một sao lấy r, in r; đẩy n, i rồi hai sao lấy i và n, in in; đẩy n, g rồi một sao lấy g, in g. Sáu dấu sao cho đúng sáu chữ theo thứ tự d, o, r, i, n, g. "droino" sai vì nó muốn r ra thứ hai, nhưng ngay sau khi lấy d thì đỉnh ngăn xếp đang là o của cụm Good, mà r thậm chí chưa được đẩy vào. "droinG" sai vì chữ G nằm dưới cùng, muốn lấy được nó thì toàn bộ chữ phía trên phải bị lấy ra trước, trong khi dãy nhập chỉ có sáu dấu sao. "droion" sai vì nó đổi hai chữ cuối thành o rồi n, còn lần lấy thứ năm phải cho n của cụm ni và lần cuối cho g. "droinM" sai vì M bị o của cụm Mor và các chữ sau đè lên, nó chỉ ra được nếu còn thêm dấu sao sau khi đã lấy hết phần trên.

Đáp án đúng: "It deletes the node p.". Hai dòng đầu lấy p1 là nút liền trước p và p2 là nút liền sau p; hai dòng sau cho prev của p2 trỏ về p1 và next của p1 trỏ sang p2. Sau đó không còn liên kết nào từ danh sách dẫn vào p, trong khi p1 với p2 đã nối trực tiếp với nhau, nghĩa là p bị tháo khỏi danh sách; các trường trong p không bị xoá nhưng không ai đi tới nó được nữa. Việc "It deletes the node before p." sẽ cần nối p với nút trước p1, tức phải lấy thêm p1.prev. Việc "It deletes the node after p." sẽ cần nối p với nút sau p2, tức phải lấy thêm p2.next. Việc "It does not make any change on the list." không đúng vì đoạn mã có sửa thật hai liên kết của hai nút láng giềng, và chỉ một trong hai phép gán đó đã làm hình dạng danh sách khác trước.

Đáp án đúng: "{c, e}". Đồ thị gồm các cạnh a-b, b-c, b-d, c-d, c-e, e-f, f-g, g-h, e-h và e-g. Cạnh cầu là cạnh mà bỏ nó đi thì số thành phần liên thông tăng, nghĩa là cạnh không nằm trên chu trình nào. Cạnh c-e là mối nối duy nhất giữa cụm a, b, c, d và cụm e, f, g, h nên bỏ nó thì không còn đường nào đi từ d sang f. "{b, c}" nằm trên chu trình b-c-d-b, bỏ nó thì b vẫn tới c qua d. "{b,d}" cũng nằm trên chu trình đó, bỏ nó thì b vẫn tới d qua c. "{f, g}" nằm trên chu trình f-g-e-f, bỏ nó thì f vẫn tới g qua e. Đáng chú ý là cạnh a-b cũng là cầu vì a chỉ có đúng một cạnh, nhưng cạnh đó không nằm trong các lựa chọn.

Đáp án đúng: "HowAre". Ở biến thể này mỗi dấu sao lấy ký tự ở đầu hàng đợi và in ngay, còn các ký tự khác chỉ được nạp vào cuối hàng; sau khi đọc hết từ thì không có vòng xả nên phần còn lại trong hàng không bao giờ được in. Vì hàng đợi vào trước ra trước, thứ tự in trùng đúng thứ tự nạp. Chạy tay theo đúng thứ tự ký tự của từ: nạp H, o, w, A, r, e; hai dấu sao in H rồi o; nạp Y, o, u; hai dấu sao in w rồi A; nạp T, o; hai dấu sao in r rồi e; cuối cùng nạp D, a, y mà không còn dấu sao nào. Sáu dấu sao in ra đúng sáu ký tự được nạp sớm nhất: H, o, w, A, r, e. "HowAr" chỉ có năm ký tự, tức đếm thiếu một dấu sao. "owAreY" bỏ chữ H dù H vào hàng sớm nhất nên phải ra trước nhất. "erAwoH" 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: "The complexity of insertion sort is O(n^2), in the best case it is O(n).". Sắp xếp chèn lấy từng phần tử rồi dịch ngược về vị trí đúng trong phần đã sắp, và vòng lặp trong dừng ngay khi gặp phần tử nhỏ hơn hoặc bằng. Khi mảng đã sắp sẵn, mỗi phần tử chỉ so đúng một lần với phần tử liền trước rồi dừng, tổng n-1 phép so sánh và không có phép dịch nào, tức O(n); khi mảng sắp ngược, phần tử thứ i phải dịch qua i phần tử, tổng khoảng n(n-1)/2 phép, tức O(n^2). Vì vậy "In all cases the insertion sort is O(n^2)." sai vì nó bỏ qua trường hợp mảng đã sắp, nơi điều kiện dừng sớm cắt hẳn vòng trong; "The complexity of insertion sort is O(nlog n), in the best case it is O(n)." sai vì O(nlog n) là cấp của những thuật toán chia đôi dữ liệu như trộn hay vun đống, còn chèn thì dịch tuần tự nên trường hợp xấu là bình phương; "The complexity of insertion sort is O(n^2), in the best case it is O(nlog n)." sai vì trường hợp tốt nhất còn nhanh hơn thế, chỉ cần n-1 phép so sánh.

Đáp án đúng: "(2)", tức mảng vòng có o ở ô 0, r ở ô 1, l ở ô 2, d ở ô 3, còn ô 4 và ô 5 rỗng. Chạy theo chuỗi Hello rồi ba dấu sao, Wor rồi hai dấu sao, ld rồi một dấu sao: H, e, l, l, o chiếm ô 0 đến ô 4; ba dấu sao lấy ra H, e, l nên đầu hàng chuyển về ô 3; W vào ô 5, o quay vòng về ô 0, r vào ô 1; hai dấu sao lấy ra l ở ô 3 và o ở ô 4 nên đầu hàng về ô 5; l vào ô 2, d vào ô 3; dấu sao cuối lấy ra W ở ô 5. Còn lại bốn ký tự o, r, l, d ở các ô 0, 1, 2, 3 với đầu hàng tại ô 0. Bảng "(1)" đặt d ở ô 0 và o, r, l ở ô 3, ô 4, ô 5, tức lệch vòng, trong khi lần quay vòng duy nhất chỉ đưa chữ o của Wor về đúng ô 0. Bảng "(3)" dồn r, l, d xuống ô 0 đến ô 2 và để o ở ô 5, nghĩa là đầu hàng lùi thêm một ô so với thực tế. Bảng "(4)" chiếm ô 1 đến ô 4, ứng với việc nạp H từ ô 1 thay vì ô 0.

Đáp án đúng: "The collision is resolved by finding an available table entry other than the position to which the colliding key is originally hashed". Địa chỉ mở giữ mọi khoá ngay trong mảng bảng băm: khi ô mà hàm băm chỉ tới đã bị chiếm, thuật toán dò tiếp theo một quy tắc định trước, tuyến tính hoặc bậc hai hoặc băm kép, để tìm một ô trống KHÁC trong chính bảng, và lúc tra cứu cũng dò lại theo đúng dãy đó. Phương án "Each position of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys" mô tả phương pháp chuỗi móc nối, nơi khoá va chạm đi ra ngoài bảng vào một danh sách liên kết chứ không chiếm ô khác của bảng. Phương án "The collision is resolved by finding a free memory area to store any collision" nói tới việc xin vùng nhớ mới, gần với vùng tràn hoặc bucket phụ, trong khi địa chỉ mở không cấp phát thêm gì. Phương án "A free memory area is opened for storing keys" cũng hiểu chữ open theo nghĩa mở một vùng nhớ, nhưng chữ open ở đây nói rằng địa chỉ cuối của một khoá là mở, không bị ghim vào ô băm ban đầu.