Tất cả câu hỏi

Đá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: "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: "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: "(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: "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: "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: "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: "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: "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: "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: "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: "(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: "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: "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: "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: "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: "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.