Tất cả câu hỏi

Đá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.

Đá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 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: "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: "{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: "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: "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: "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: "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: "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: "1, 2, 4, 5, 7, 3, 6, 8". Duyệt trước thăm gốc rồi đi hết nhánh trái mới sang nhánh phải. Cây gốc 1 có con trái 2 (con trái 4, con phải 5, mà 5 chỉ có con trái 7) và con phải 3 (chỉ có con phải 6, mà 6 chỉ có con trái 8). Chạy dãy: thăm 1; sang nhánh trái thăm 2, rồi 4 là lá, rồi 5 và con trái của 5 là 7, được 2, 4, 5, 7; sang nhánh phải thăm 3, 3 không có con trái nên xuống 6, rồi con trái của 6 là 8, được 3, 6, 8. "1, 2, 4, 7, 5, 3, 6, 8" đặt 7 trước 5 dù 7 là con của 5, mà duyệt trước luôn thăm cha trước con. "1, 2, 4, 5, 7, 3, 8, 6" mắc đúng lỗi đó ở nhánh phải, đưa 8 lên trước cha của nó là 6. "4, 2, 7, 5, 1, 8, 6, 3" mở đầu bằng lá 4, điều không thể có ở duyệt trước vì phần tử đầu tiên bắt buộc là gốc; dãy đó đi theo lối thăm con trái trước gốc.

Đáp án đúng: "*** ** * That's all!", tức ba dấu sao ở dòng đầu, rồi hai, rồi một, cuối cùng mới tới dòng chữ. Hàm in trước rồi mới gọi đệ quy: với n bằng 3, vòng for in ba dấu sao rồi xuống dòng, sau đó gọi fun(2) in hai dấu sao, rồi fun(1) in một dấu sao, rồi fun(0) rơi vào nhánh đầu và in dòng chữ rồi dừng. Vì vậy số dấu sao giảm dần và dòng chữ luôn nằm cuối. Dãy "That's all! *** ** *" đặt dòng chữ lên đầu, điều đó chỉ xảy ra nếu lệnh in dòng chữ đứng trước phần đệ quy, trong khi nó nằm ở nhánh n bằng 0 và chỉ chạy sau ba lần gọi. Dãy "That's all! * ** ***" vừa đưa dòng chữ lên đầu vừa cho số dấu sao tăng dần, sai cả hai chỗ. Dãy "* ** *** That's all!" đúng chỗ dòng chữ nhưng số dấu sao tăng dần, chiều này chỉ xảy ra nếu hàm gọi đệ quy trước rồi mới chạy vòng for.

Đáp án đúng: "Both best and worst cases are O(nlogn)". Sắp xếp vun đống luôn gồm hai phần cố định: dựng đống từ n phần tử rồi lặp n lần việc lấy phần tử lớn nhất ở gốc, đưa về cuối và vun lại. Mỗi lần vun lại đi dọc một đường từ gốc xuống lá nên tốn cỡ log n, lặp n lần cho n log n, và không có dạng dữ liệu nào cắt bớt được các lần vun ấy, kể cả mảng đã sắp xếp sẵn. Mức "The best case is O(n), and the worst case is O(nlogn)" cho trường hợp tốt nhất là tuyến tính, nhưng dù mảng đã có thứ tự thì thuật toán vẫn phải vun lại sau từng lần lấy gốc nên không xuống được mức n. Mức "The best case is O(n), and the worst case is O(n^2)" vừa nêu trường hợp tốt nhất tuyến tính vừa cho trường hợp xấu nhất bình phương, đó là dáng của sắp xếp chèn có kiểm tra mảng đã xong. Mức "Best case is O(nlogn) , the worst case is O(n^2)" cho trường hợp xấu nhất bình phương, đó là dáng của sắp xếp nhanh khi chốt chọn lệch, còn vun đống không phụ thuộc việc chọn chốt.

Đáp án đúng: "AABBBCAB". Đọc cây mã trước: nhánh 1 từ gốc tới ngay lá A nên A = 1; nhánh 0 dẫn vào một nút trong, từ đó 0 tới B và 1 tới C, nên B = 00 và C = 01. Vì đây là mã tiền tố, cứ đọc bit từ trái và dừng ngay khi tới lá: 1 cho A, 1 cho A, 00 cho B, 00 cho B, 00 cho B, 01 cho C, 1 cho A, 00 cho B, vừa hết 13 bit của 1100000001100 và cho AABBBCAB. "CAABBBBA" sai vì nó mở đầu bằng C = 01 trong khi bit đầu của chuỗi là 1, mã tiền tố không cho phép đọc lệch như vậy. "AABBBBBA" sai vì nó đọc cặp bit thứ chín và mười, vốn là 01, thành thêm một B, tức bỏ qua nhánh 1 dẫn tới lá C. "AABBABAB" sai vì chuỗi bit của nó chỉ dài 12 bit và chèn một A vào giữa dải bit 0 liền nhau, không khớp với dữ liệu cần giải mã.

Đáp án đúng: "In all cases the selection sort is O(n^2).". Sắp xếp chọn luôn chạy hai vòng lặp lồng cố định: lượt thứ i quét toàn bộ phần chưa sắp để tìm phần tử nhỏ nhất, nên số phép so sánh là n−1 cộng n−2 cộng tiếp tới 1, bằng n(n−1)/2 bất kể dữ liệu ra sao. Nó không có cơ chế nào phát hiện mảng đã sắp để dừng sớm, vì phải quét hết mới biết đâu là nhỏ nhất; số phép đổi chỗ thì ít, chỉ cỡ n, nhưng phép so sánh mới chi phối chi phí. Phương án "In the worst case the selection sort is O(n^2), in the best case it is O(n)." mô tả sắp xếp nổi bọt có cờ kiểm tra hoán vị, loại dừng ngay khi một lượt không đổi gì, hoặc sắp xếp chèn trên mảng đã sắp. Phương án "In the worst case the selection sort is O(n^2), in the best case it is O(nlog n)." gán cho trường hợp tốt mức chi phí của sắp xếp trộn hay sắp xếp nhanh, hai thuật toán chia để trị. Phương án "In the average case the selection sort is O(n^2), in the best case it is O(nlog n)." đúng ở phần trung bình nhưng vẫn gán sai cho trường hợp tốt, vốn cũng là n(n−1)/2 phép so sánh.

Đáp án đúng: "(1)", tức bảng có 21 ở ô 1, 203 ở ô 3, 64 ở ô 4, 95 ở ô 5, 44 ở ô 6 và 144 ở ô 7. Hàm băm lấy số dư cho 10 nên 95 vào ô 5, 64 vào ô 4, 21 vào ô 1, 203 vào ô 3, các ô này đều trống nên nhận ngay. Khoá 44 băm về ô 4 đã có 64, dò tuyến tính sang ô 5 cũng đầy vì có 95, sang ô 6 trống nên dừng ở đó. Khoá 144 cũng băm về ô 4, dò qua ô 5, ô 6 rồi đậu ở ô 7. Bảng "(2)" đổi chỗ 44 với 144, nhưng 44 được chèn trước nên chính nó mới chiếm ô trống gần nhất là ô 6. Bảng "(3)" để trống ô 6 và ô 7 rồi đặt 44 ở ô 8, trái với dò tuyến tính vì phép dò này luôn nhận ô trống đầu tiên về phía sau. Bảng "(4)" vừa bỏ qua hai ô trống đó vừa đảo thứ tự hai khoá, sai cả bước dò lẫn trình tự chèn.

Đáp án đúng: "In this method, the table can never overflow if free memory is available, because the linked list is extendible.". Trong phương pháp nối kết, mỗi ô của bảng giữ đầu một danh sách liên kết, nên số khoá dồn vào một ô không bị chặn bởi kích thước bảng: chèn thêm chỉ là cấp một nút mới và móc vào dây, vì vậy bảng không bao giờ tràn khi còn bộ nhớ trống, khác hẳn địa chỉ mở nơi bảng đầy là hết chỗ chèn. Vì vậy "In chaining, some positions of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys" sai ở chữ some: mọi ô của bảng đều là đầu một dây, dây có thể rỗng chứ không phải chỉ một số ô mới có dây. "In chaining, the linked-list is used instead of array for a hash table" sai vì bảng vẫn phải là mảng để nhảy trực tiếp tới ô h(x) trong thời gian hằng, danh sách liên kết chỉ nối thêm vào từng ô; thay mảng bằng danh sách là mất luôn khả năng truy cập theo chỉ số. "None of others" sai vì đã có một phát biểu đúng nằm trong các lựa chọn.

Đáp án đúng: "It inserts new node with value x before the node p.". Đoạn mã lấy f = p.prev, nghĩa là nút đứng ngay trước p, việc chỉ danh sách liên kết đôi làm được trong một bước. Sau đó nút mới q mang giá trị x được nối hai chiều vào khoảng giữa f và p: q.prev = f cùng q.next = p cho q biết hai láng giềng, f.next = q cùng p.prev = q cho f và p biết q. Không liên kết nào của p.next bị đổi và không nút nào bị tách ra, nên hiệu quả đúng là chèn x vào trước p với chi phí O(1). "It inserts new node with value x after the node p." phải lấy mốc là p.next chứ không phải p.prev. "It replaces the node p with new node with value x." sai vì p vẫn nằm trong chuỗi, chỉ có liên kết lùi của nó chuyển sang q. "It creates new node with value x at the end of the list." sai vì vị trí chèn do p quyết định; nó chỉ trùng cuối danh sách trong trường hợp riêng p là nút cuối, mà ngay cả khi ấy x vẫn đứng trước p.

Đáp án đúng: "7 11 6 4 3 10 9 8 2". Đoạn mã tạo nút p1 chứa 9 rồi lấy p2 là nút đứng sau p, tức nút 8. Bốn phép gán p.next=p1, p1.prev=p, p1.next=p2 và p2.prev=p1 khâu đủ hai chiều, đặt nút 9 vào ngay sau nút 10 và trước nút 8. "7 11 6 4 3 10 8 2 9" là thêm vào cuối danh sách, phải đi qua tail chứ không phải qua p. "7 11 6 4 3 9 10 8 2" là chèn trước p, muốn vậy phải dùng p.prev để nối với nút 3 chứ không phải p.next. "7 9 11 6 4 3 10 8 2" là chèn sau nút đầu, cần một tham chiếu tới head. "9 7 11 6 4 3 10 8 2" là chèn vào đầu danh sách và bắt buộc phải gán lại head, mà đoạn mã không chạm tới head.

Đáp án đúng: "False". Trong danh sách liên kết vòng, nút cuối trỏ về nút đầu nên từ một tham chiếu duy nhất ta đi được tới mọi nút. Cách cài phổ biến là chỉ giữ một tham chiếu tới nút cuối: nút đầu lấy ngay bằng liên kết next của nó, nhờ đó cả việc thêm vào đầu lẫn thêm vào cuối đều tốn thời gian hằng số mà không cần biến thứ hai. Vì vậy mệnh đề đòi luôn phải khai cả hai đầu là không đúng. Trả lời "True" chỉ hợp khi người ta tự chọn lưu cả hai tham chiếu cho tiện, chẳng hạn để đọc thẳng phần tử đầu mà không qua một bước liên kết; đó là tuỳ chọn cài đặt chứ không phải điều kiện bắt buộc của cấu trúc vòng.