BThe best case is O(n), and the worst case is O(n^2)
CThe best case is O(n), and the average case is O(nlogn)
DThe best case is O(n), and the average case is O(n^2)
Lời giải
Đáp án đúng: "Both best and worst cases are O(n^2)". Sắp xếp chọn luôn phải quét hết phần chưa sắp để biết phần tử nhỏ nhất nằm đâu, nên lượt thứ i tốn n−i phép so sánh và tổng luôn là n(n−1)/2, không phụ thuộc dữ liệu đầu vào. Mảng đã sắp sẵn cũng không giúp gì vì thuật toán không có cờ nào để dừng sớm; cái duy nhất giảm được là số phép đổi chỗ. Phương án "The best case is O(n), and the worst case is O(n^2)" là đặc trưng của sắp xếp nổi bọt có kiểm tra lượt không hoán vị, hoặc của sắp xếp chèn. Phương án "The best case is O(n), and the average case is O(nlogn)" trộn hai thuật toán khác: mức n log n thuộc sắp xếp trộn hoặc sắp xếp nhanh. Phương án "The best case is O(n), and the average case is O(n^2)" đúng phần trung bình nhưng vẫn cho trường hợp tốt là O(n), trong khi trường hợp tốt vẫn tốn n(n−1)/2 phép so sánh.
Đáp án đúng: "1, 3, 4, 5, 7, 2, 6, 8". Pre-order thăm gốc trước, rồi cây con trái, rồi cây con phải. Bắt đầu ở gốc 1; sang nhánh trái là 3, in 3, rồi con trái 4 vốn là lá nên in 4, rồi con phải 5 và tiếp con trái 7 của nó, cho 1, 3, 4, 5, 7. Sang nhánh phải là 2, in 2; 2 không có con trái nên xuống con phải 6, rồi con trái 8 của 6, cho 2, 6, 8. "1, 3, 4, 7, 5, 2, 6, 8" sai vì nó treo 7 dưới 4, còn trong hình 7 là con trái của 5 nên phải in sau 5. "1, 3, 4, 5, 7, 2, 8, 6" sai vì nó in 8 trước cha 6, mà pre-order luôn in cha trước con. "4, 3, 7, 5, 1, 8, 6, 2" sai vì đó là dãy in-order, nhận ra ngay vì gốc 1 nằm giữa dãy thay vì ở đầu.
int fun(int n){if(n <0)return(fun(-n));
else if(n<5)return(2);
else
return(n*fun(n/2));}
Which call will result in the most recursive calls?
Afun(-1012);
Bfun(100);
Cfun(0);
Dfun(1012);
Lời giải
Đáp án đúng: "fun(-1012);". Hàm dừng khi n không âm và nhỏ hơn 5; n âm thì tốn thêm một lời gọi để đổi dấu, n từ 5 trở lên thì gọi tiếp với n/2. Với "fun(-1012);" chuỗi gọi là fun(-1012), fun(1012), fun(506), fun(253), fun(126), fun(63), fun(31), fun(15), fun(7), fun(3), tức chín lời gọi đệ quy gồm tám lần chia đôi cộng một lần đổi dấu. Lời gọi "fun(1012);" đi đúng tám lần chia đôi ấy nhưng không cần bước đổi dấu nên ít hơn một lời gọi. Lời gọi "fun(100);" chia đôi theo chuỗi 100, 50, 25, 12, 6, 3 nên chỉ có năm lời gọi đệ quy. Lời gọi "fun(0);" có n bằng 0, vừa không âm vừa nhỏ hơn 5 nên rơi thẳng vào chỗ dừng và không sinh lời gọi nào.
Đáp án đúng: "CAABBBAC". Cây chỉ có ba lá nên mã là A bằng 1, B bằng 00 và C bằng 01: từ gốc nhánh 1 tới ngay lá A, còn nhánh 0 dẫn tới nút trong thứ hai với nhánh 0 cho B và nhánh 1 cho C. Giải mã bằng cách đi từ gốc và cắt mỗi khi tới lá: 01 cho C, 1 cho A, 1 cho A, 00 cho B, 00 cho B, 00 cho B, 1 cho A, 01 cho C, dùng vừa đúng 13 bit của chuỗi. "BABABCBC" mở đầu bằng B, tức đọc hai bit đầu là 00, nhưng hai bit đầu của chuỗi là 01. "CAABABAB" khớp bốn ký tự đầu rồi đòi một chữ A, trong khi sau khúc CAAB phần còn lại là 0000101 và hai bit tiếp là 00 nên phải là B. "CAABBCAB" khớp năm ký tự đầu rồi đòi C tức 01, nhưng sau khúc CAABB phần dư là 00101 nên hai bit tiếp vẫn là 00 của thêm một chữ B.
int x =13;
Node f = p.prev;//prev is a link to predecessor node
Node q = new Node(x);
q.prev = f; q.next = p;
f.next = q; p.prev = q;
A7 1 6 4 31 17 8 2 13
B7 1 6 4 31 13 17 8 2
C7 1 6 4 31 17 13 8 2
D7 13 1 6 4 31 17 8 2
E13 7 1 6 4 31 17 8 2
Lời giải
Đáp án đúng: "7 1 6 4 31 13 17 8 2". p trỏ vào nút 17, nên f = p.prev là nút 31 đứng ngay trước. Nút mới q mang 13 được khâu vào giữa 31 và 17 theo cả hai chiều: q.prev = f cùng q.next = p nối q sang hai bên, f.next = q cùng p.prev = q để 31 và 17 nhận lại q. Danh sách thành 7 1 6 4 31 13 17 8 2, dài thêm đúng một nút và không nút nào bị mất. "7 1 6 4 31 17 13 8 2" đặt 13 ngay sau 17, kết quả của việc lấy mốc là p.next chứ không phải p.prev. "7 1 6 4 31 17 8 2 13" là chèn vào cuối danh sách, chẳng dùng tới p. "7 13 1 6 4 31 17 8 2" và "13 7 1 6 4 31 17 8 2" chèn ở gần đầu danh sách, trong khi bốn lệnh gán chỉ chạm tới hai nút kề p là 31 và 17.
AIn a singly-linked list there is no efficient way to insert a node before a given node in the middle of the list (the action is considered efficient if it's complexity is O(1)).
BIn a singly-linked list we can insert a node after a given node with time complexity O(1)
CIn a singly-linked list we can insert a node after a given node with time complexity O(n)
DIn a singly-linked list we can insert a node before a given node in the middle of the list with time complexity O(1)
Lời giải
Đáp án đúng gồm hai ý: "In a singly-linked list there is no efficient way to insert a node before a given node in the middle of the list (the action is considered efficient if it's complexity is O(1))." và "In a singly-linked list we can insert a node after a given node with time complexity O(1)". Trong danh sách liên kết đơn mỗi nút chỉ có liên kết next: với nút p cho sẵn, chèn sau p chỉ cần q.next bằng p.next rồi p.next bằng q, hai phép gán không phụ thuộc số nút nên là O(1); còn chèn trước p thì cần nút tiền nhiệm, mà không có liên kết lùi nên buộc dò lại từ head, chi phí O(n), tức không có cách làm hiệu quả theo đúng nghĩa O(1) mà đề nêu. Vì vậy "In a singly-linked list we can insert a node after a given node with time complexity O(n)" không phải ý cần chọn vì nó mô tả chi phí của việc phải dò tìm nút, trong khi p đã được cho sẵn nên không có bước dò nào, hai phép gán là xong; "In a singly-linked list we can insert a node before a given node in the middle of the list with time complexity O(1)" sai vì nó mâu thuẫn trực tiếp với việc thiếu liên kết lùi, muốn O(1) thì cấu trúc phải là danh sách liên kết đôi.
Đáp án đúng: "Node q = p.next; p.next = q.next;". Muốn bỏ nút ngay sau p thì chỉ cần nối p vượt qua nó: giữ nút cần bỏ vào q rồi cho p.next nhận q.next, nhờ vậy q không còn ai trỏ tới mà phần đuôi vẫn liền mạch, chi phí hằng số. Bản "Node q = p.next; q.next = p.next.next;" chỉ sửa con trỏ bên trong q, p vẫn trỏ vào q nên không nút nào rời danh sách, hơn nữa nó làm q bỏ qua chính nút kế của q. Bản "p = p.next; p.next = null;" chỉ dời biến cục bộ p rồi cắt đuôi, kết quả là mọi nút sau q bị mất mà q thì vẫn còn trong danh sách. Bản "p.next= null;" cắt luôn cả phần sau p, tức xoá hàng loạt chứ không xoá đúng một nút.
Đáp án đúng: "40". Các cạnh là A–B = 3, A–D = 8, B–C = 4, B–E = 18, C–D = 6, C–E = 12, D–F = 16, E–F = 15. Chạy Kruskal theo trọng số tăng: lấy A–B = 3, lấy B–C = 4, lấy C–D = 6, bỏ A–D = 8 vì đã có đường A–B–C–D nên thành chu trình, lấy C–E = 12 để chạm E, lấy E–F = 15 để chạm F; tới đây đủ 5 cạnh cho 6 đỉnh nên dừng, D–F = 16 và B–E = 18 đều bị loại. Tổng là 3 + 4 + 6 + 12 + 15 = 40. Phương án "41" là tổng 3 + 4 + 6 + 12 + 16, dùng D–F = 16 thay cho E–F = 15. Phương án "43" là tổng 3 + 4 + 8 + 12 + 16, dùng cả A–D = 8 và D–F = 16. Phương án "48" là tổng 3 + 4 + 8 + 18 + 15, chạm E bằng cạnh đắt B–E = 18. Phương án "25" thấp dưới mức khả thi: riêng việc chạm F đã tốn ít nhất 15 và bốn cạnh nhẹ nhất còn lại cộng vào đã quá 25.
Đáp án đúng: "25, 15, 40, 5, 20, 35, 10". Xoá bằng sao chép lấy khoá liền trước nút bị xoá theo thứ tự giữa, tức nút phải nhất của cây con trái: từ 15 đi phải được 25, mà 25 không có con phải nên 25 là khoá cần chép lên chỗ của 30; xoá nút 25 thì con trái 20 của nó nối lên làm con phải của 15. Cây mới có gốc 25, con trái 15 với con trái 5 và con phải 20, con phải 40 với con trái 35, còn 5 vẫn giữ con phải 10. Duyệt theo bề rộng cho 25, rồi 15 và 40, rồi 5, 20, 35, cuối cùng 10. "15, 5, 25, 10, 20, 40, 35" sai vì đó là kết quả xoá bằng hợp nhất, khi 15 lên gốc và cây con phải 40 được treo dưới 25. "15, 5, 25, 20, 10, 40, 35" sai vì ngoài cách hợp nhất nó còn đảo thứ tự trong mức, đặt 20 trước 10 dù 10 là con của 5 nên đứng trước. "15, 5, 40, 10, 35, 25, 20" sai vì nó đưa 40 vào đúng chỗ của 25 và đẩy 25 xuống sâu, không khớp cách xoá nào.
Đáp án đúng: "Traverse". Phép duyệt là việc đi qua từng phần tử của danh sách đúng một lần để đọc hoặc xử lý, và dấu hiệu nhận ra nó là mỗi phần tử được thăm đúng một lần, không bỏ sót, không lặp lại. Thao tác "Inserting" thêm một phần tử mới vào danh sách, nó chỉ chạm tới chỗ chèn chứ không đi qua mọi phần tử, lại làm đổi số phần tử. Thao tác "Merging" trộn hai danh sách thành một, nó làm việc với hai nguồn dữ liệu và cho ra một danh sách khác, không phải phép đi qua một danh sách. Thao tác "Sorting" xếp lại các phần tử theo thứ tự khoá, nó đổi vị trí phần tử và nói chung phải so sánh nhiều lượt, tức thăm nhiều phần tử nhiều lần chứ không đúng một lần.
BThe best case is O(n), and the worst case is O(nlogn)
CThe best case is O(nlogn), and the worst case is O(n^2)
DThe best case is O(n), and the worst case is O(n^2)
Lời giải
Đáp án đúng: "The best case is O(n), and the worst case is O(n^2)". Sắp xếp chèn lấy từng phần tử rồi đẩy nó lùi về chỗ đúng trong phần đã sắp. Nếu mảng đã sắp sẵn, mỗi phần tử chỉ cần một phép so sánh với phần tử liền trước là dừng, tổng cộng n trừ 1 phép so sánh nên chi phí tuyến tính. Nếu mảng sắp ngược, phần tử ở vị trí thứ i phải lùi qua cả i phần tử trước nó, tổng là 1 cộng 2 cộng tới n trừ 1, xấp xỉ n bình phương chia 2 nên là bậc hai. "Both best and worst cases are O(n^2)" bỏ mất tính thích nghi với dữ liệu gần sắp, vốn là lý do người ta dùng sắp xếp chèn cho mảng nhỏ hoặc gần như đã sắp. "The best case is O(n), and the worst case is O(nlogn)" gán cho nó cận xấu nhất của sắp xếp trộn hay vun đống, trong khi chèn không chia đôi dữ liệu nên không đạt được n log n. "The best case is O(nlogn), and the worst case is O(n^2)" đặt cận tốt nhất quá cao, vì với mảng đã sắp số phép so sánh chỉ là n trừ 1.
int x =19;
Node p1, p2;
p1 = new Node(x);
p2 = p.next;
p.next = p1; p1.prev = p;
p1.next = p2; p2.prev = p1;
A27 11 6 4 3 10 8 2 19
B27 11 6 4 3 19 10 8 2
C27 11 6 4 3 10 19 8 2
D27 19 11 6 4 3 10 8 2
E19 27 11 6 4 3 10 8 2
Lời giải
Đáp án đúng: "27 11 6 4 3 10 19 8 2". Lần này mốc là p.next: p trỏ vào nút 10, p1 là nút mới mang 19, còn p2 = p.next là nút 8. Bốn lệnh gán khâu p1 vào giữa 10 và 8: p.next = p1 cùng p1.prev = p nối về phía trước, p1.next = p2 cùng p2.prev = p1 nối về phía sau, nên danh sách thành 27 11 6 4 3 10 19 8 2. "27 11 6 4 3 19 10 8 2" đặt 19 trước 10, đó là kết quả nếu dùng p.prev làm mốc như biến thể chèn vào trước. "27 11 6 4 3 10 8 2 19" là thêm vào cuối danh sách, không dùng tới p. "27 19 11 6 4 3 10 8 2" và "19 27 11 6 4 3 10 8 2" chèn ở đầu danh sách, trong khi đoạn mã chỉ sửa liên kết của hai nút 10 và 8.
Đáp án đúng: "4, 2, 6, 1, 3, 8, 7". Cây có gốc 5, bên trái là 2 với hai con 1 và 4 trong đó 4 chỉ có con trái 3, bên phải là 6 chỉ có con phải 8 và 8 chỉ có con trái 7. Xoá gốc bằng cách sao chép kéo giá trị nút liền trước, tức nút phải nhất của cây con trái, lên chỗ gốc rồi cắt nút ấy: từ 2 đi phải hết cỡ được 4, nên 4 lên làm gốc; nút 4 chỉ có con trái 3 nên khi cắt nó, 3 lên thay chỗ và thành con phải của 2. Cây mới có gốc 4 với hai con 2 và 6; 2 có hai con 1 và 3; 6 có con phải 8; 8 có con trái 7. Duyệt bề rộng cho 4, rồi 2 và 6, rồi 1, 3, 8, rồi 7. Vì vậy "4, 2, 6, 1, 3, 7, 8" sai vì 8 ở tầng ngay dưới 6 còn 7 là con của 8 ở tầng sâu hơn, duyệt bề rộng phải vét xong tầng trên; "2, 1, 4, 3, 6, 8, 7" sai vì đó là kết quả của phép xoá bằng cách nối, treo cây con phải 6 vào nút 4 rồi đưa 2 lên làm gốc; "2, 1, 4, 3, 6, 7, 8" sai vì nó vừa đưa 2 lên gốc theo kiểu nối lại vừa in 7 trước 8, phá luôn thứ tự tầng.
void fun(int n){if(n <=0)
System.out.println("Hello");
else
{for(int i =0; i < n; i++)
System.out.print("$");
System.out.println();fun(n -2);}}
What is the output when the statement fun(5); is run?
AHello
$$$$$
$$$
$
B$$$$$
$$$
$
Hello
C$$$$
$$
$
Hello
D$
$$$
$$$$$
Hello
Lời giải
Đáp án đúng: "$$$$$ $$$ $ Hello", tức bốn dòng lần lượt là năm ký tự đô la, ba ký tự, một ký tự rồi chữ Hello. Lời gọi fun(5) thấy n lớn hơn 0 nên vòng for chạy với i từ 0 tới 4, in đúng 5 ký tự rồi xuống dòng, sau đó gọi fun(3) in 3 ký tự, fun(1) in 1 ký tự, cuối cùng fun(-1) có n nhỏ hơn hoặc bằng 0 nên in Hello và dừng; vì lệnh in nằm trước lời gọi đệ quy nên dòng dài nhất ra trước và Hello ra sau cùng. Dãy "Hello $$$$$ $$$ $" đặt Hello lên đầu, nhưng Hello chỉ được in ở lời gọi sâu nhất nên nó phải đứng cuối. Dãy "$$$$ $$ $ Hello" đếm sai số ký tự: điều kiện i nhỏ hơn n cho đúng n ký tự mỗi dòng, tức 5, 3, 1 chứ không phải 4, 2, 1. Dãy "$ $$$ $$$$$ Hello" xếp từ ngắn tới dài, trái với việc n giảm hai đơn vị sau mỗi dòng đã in.
Đáp án đúng: "(4)", tức bảng có 36 ở ô 0, 106 ở ô 5, 26 ở ô 6 và 97 ở ô 7, các ô còn lại rỗng. Với h(x) = x%10 và dò bậc hai (h(x) + i^2)%10: 26 băm về ô 6 đang trống nên vào ô 6; 97 băm về ô 7 và vào ô 7; 36 cũng băm về 6 nhưng ô 6 đã có 26, thử i = 1 được ô 7 đang có 97, thử i = 2 được (6 + 4)%10 = 0 nên 36 vào ô 0; 106 lại băm về 6, i = 1 cho ô 7 và i = 2 cho ô 0 đều kẹt, i = 3 cho (6 + 9)%10 = 5 nên 106 vào ô 5. Phương án "(1)" ghi 26 ở cả ô 6 và ô 8 rồi đặt 106 ở ô 9, tức đã đọc 36 thành 26 và dò tuyến tính thay vì bậc hai. Phương án "(2)" đặt 106 ở ô 4, chỉ đúng nếu bước i = 3 cộng 8 thay vì cộng 9. Phương án "(3)" đặt 36 ở ô 1, chỉ đúng nếu bước i = 2 cộng 5 thay vì cộng 4.
Đáp án đúng: "push". Ngăn xếp là cấu trúc vào sau ra trước và chỉ cho tác động ở một đầu gọi là đỉnh, nên hai phép cơ bản của nó mang tên riêng: push đẩy một phần tử lên đỉnh và pop lấy phần tử ở đỉnh ra. Cặp tên này gắn với ngữ nghĩa đỉnh, nhờ vậy đọc mã là biết ngay cấu trúc đang dùng. "append" sai vì nó là từ của danh sách và chuỗi, nghĩa là nối thêm vào cuối, một vị trí mà ngăn xếp không nói tới. "insert" sai vì nó hàm ý chèn vào một vị trí bất kỳ, điều ngăn xếp cấm vì mọi thao tác chỉ xảy ra ở đỉnh. "add" sai vì đó là tên chung của các tập hợp, không cho biết phần tử mới đi vào đâu và lấy ra theo luật nào.
{if(p==null)return(null);if(p.info==x)return(p);if(x<p.info)return(search(p.left,x));
else
return(search(p.right,x));}". Phép tìm đệ quy trên cây nhị phân tìm kiếm cần hai chỗ dừng: tham chiếu rỗng thì trả về null vì đã đi quá lá, và nút đang xét mang đúng x thì trả về chính nó; còn lại dùng thứ tự của cây, x nhỏ hơn giá trị nút thì chỉ có thể nằm bên nhánh trái, ngược lại nằm bên nhánh phải. Cách viết "Node search(Node p, int x){if(p.info==x)return(p);if(x<p.info)return(search(p.left,x));
else
return(search(p.right,x));}" thiếu chỗ dừng cho tham chiếu rỗng, nó đọc p.info ngay nên khi x không có trong cây, lời gọi xuống tới con rỗng của một lá sẽ truy cập trường của null và chương trình đổ. Cách viết "Node search(Node p, int x){if(p==null)return(null);if(p.info==x)return(p);if(x<p.info)return(search(p.right,x));
else
return(search(p.left,x));
}" có đủ hai chỗ dừng nhưng rẽ ngược: x nhỏ hơn giá trị nút lại đi sang nhánh phải, nơi chỉ chứa khoá lớn hơn, nên phép tìm bỏ qua đúng nửa cây có thể chứa x và trả về null dù x nằm trong cây.
Đáp án đúng: "6, 1, 8, 2, 7, 9, 4". Cây có gốc 6 với con trái 3 và con phải 8; nút 3 có con trái 1 và con phải 4; nút 1 có con phải 2; nút 8 có hai con 7 và 9. Xoá bằng cách trộn bỏ hẳn nút 3, đưa nhánh trái của nó lên thay chỗ và treo nhánh phải vào nút phải nhất của nhánh trái: nút phải nhất của nhánh 1 là 2, nên 4 thành con phải của 2 và 1 lên làm con trái của 6. Đọc theo mức: 6; rồi 1 và 8; rồi 2, 7 và 9; rồi 4 ở mức bốn. "6, 1, 8, 2, 4, 7, 9" để 4 ở mức ba cùng với 2, nhưng 4 bị treo dưới 2 nên thuộc mức bốn. "6, 2, 8, 1, 4, 7, 9" là kết quả của cách xoá bằng cách thế, tức đưa 2 là nút lớn nhất của nhánh trái lên đúng vị trí nút 3 và giữ nguyên hai nhánh. "6, 2, 1, 4, 8, 7, 9" vừa đưa 2 lên chỗ của 3 vừa đọc hết nhánh trái trước khi chạm 8, tức đi theo chiều sâu chứ không theo mức.
AIn a linked list, the tail node is introduced for performance purpose only.
BIn a linked list, there must be the tail node.
CThe tail node is necessary for inserting a node after the last node
DThe tail node is necessary for inserting a node before the last node
Lời giải
Đáp án đúng: "In a linked list, the tail node is introduced for performance purpose only.". Một danh sách liên kết chỉ cần biến head là đủ để biểu diễn trọn vẹn dữ liệu: muốn tới nút cuối thì dò từ head cho tới khi gặp nút có next là null. Giữ thêm biến tail không thêm thông tin nào mà chỉ rút ngắn thao tác ở cuối danh sách từ O(n) xuống O(1), nên nó thuần là chuyện hiệu năng. "In a linked list, there must be the tail node." sai vì rất nhiều hiện thực chỉ có head vẫn chạy đúng mọi phép thêm, xoá, tìm. "The tail node is necessary for inserting a node after the last node" sai vì không có tail ta vẫn chèn được vào sau nút cuối, chỉ phải dò một lượt để tìm nút cuối. "The tail node is necessary for inserting a node before the last node" càng sai: trên danh sách liên kết đơn, chèn trước nút cuối cần nút đứng trước nút cuối, mà tail không cho biết nút ấy nên vẫn phải dò từ head.
int fun(int n){if(n==1|| n==2)return(1);
else
return(fun(n-1)+3*fun(n-2));}
What is the value of fun(3)?
A5
B12
C3
D4
E11
Lời giải
Đáp án đúng: "4". Hàm dừng khi n bằng 1 hoặc 2 với giá trị trả về 1, còn lại trả fun(n-1) cộng 3 lần fun(n-2), chú ý hệ số 3 chỉ nhân vào hạng tử fun(n-2). Với n bằng 3: fun(3) = fun(2) + 3 × fun(1) = 1 + 3 × 1 = 4; toàn bộ dấu vết chỉ gồm ba lời gọi fun(3), fun(2) và fun(1), hai lời gọi sau là trường hợp cơ sở nên không mở thêm nhánh nào. Vì vậy "3" sai vì nó chỉ lấy 3 × fun(1) và bỏ mất hạng tử fun(2) bằng 1; "5" sai vì nó ứng với việc coi trường hợp cơ sở trả về chính n, tức fun(2) bằng 2 cho 2 + 3 = 5, trong khi mã trả về 1 cho cả n bằng 1 và n bằng 2; "12" sai vì nó bằng 3 lần kết quả đúng, tức nhân hệ số 3 vào cả tổng thay vì chỉ vào fun(n-2); "11" sai vì nó không phải giá trị của fun ở bất kỳ đối số nào, dãy giá trị đầu là 1, 1, 4, 7.
