Đáp án đúng: "3B4Y3B2Y5B2Y". Mã hoá theo độ dài loạt chỉ việc đếm từng loạt ký tự giống nhau liền nhau rồi ghi số đếm kèm ký tự: BBB cho 3B, YYYY cho 4Y, BBB cho 3B, YY cho 2Y, BBBBB cho 5B và YY cuối cho 2Y. Kiểm lại bằng tổng các số đếm, 3 cộng 4 cộng 3 cộng 2 cộng 5 cộng 2 bằng 19, đúng bằng độ dài xâu gốc. "B4Y4B3Y2B5YY2" đặt ký tự trước số đếm và làm lệch cả các số đếm, giải mã lại không ra xâu ban đầu. "3B4Y3B2Y5B" bỏ hẳn loạt YY cuối nên chỉ dựng lại được 17 ký tự. "3B4Y3B2Y5B2YY" thêm một chữ Y lẻ sau 2Y, giải mã sẽ cho 20 ký tự và phá quy ước mỗi loạt gồm một số đếm kèm đúng một ký tự.
Đáp án đúng: "(1)". Đó là bảng có 63 ở ô 3, 74 ở ô 4, 94 ở ô 5 và 203 ở ô 7. Hàm băm lấy số dư cho 10 nên 63 vào ô 3, 74 vào ô 4; 94 cũng cho dư 4 nên va chạm, bước dò bậc hai thử ô 4 cộng 1 bằng ô 5 và ô ấy còn trống nên 94 nằm ở đó; 203 cho dư 3, ô 3 đã có 63, bước dò thứ nhất tới ô 4 cũng đã có 74, bước thứ hai cộng 4 tới ô 7 và ô này trống nên 203 nằm ở ô 7. Bảng "(2)" đặt 94 vào ô 6, muốn vậy phải cộng 2 vào ô gốc 4, mà dãy dò bậc hai từ ô 4 chỉ đi qua ô 5 rồi ô 8. Bảng "(3)" đặt 94 đúng ở ô 5 nhưng đẩy 203 vào ô 6, tức cộng 3 vào ô gốc 3, trong khi các bước dò chỉ cộng 1 rồi cộng 4. Bảng "(4)" đặt 94 ở ô 7 và 203 ở ô 0, cả hai ô đều không nằm trên dãy dò bậc hai xuất phát từ ô gốc 4 và ô gốc 3.
Đáp án đúng: "(4)", tức bảng có 221 ở ô 1, 33 ở ô 3, 204 ở ô 4, 95 ở ô 5, 53 ở ô 6 và 243 ở ô 7. Chạy tay với h(x) = x%10 và dò tuyến tính: 95 vào ô 5, 33 vào ô 3, 221 vào ô 1, 204 vào ô 4; 53 băm về ô 3 đang có 33 nên dò sang ô 4 và ô 5 cũng kín, dừng ở ô 6; 243 cũng băm về ô 3, dò qua các ô 4, 5, 6 đều kín và nằm xuống ô 7. "(1)" sai vì nó đặt 243 ở ô 8 và 53 ở ô 9, bỏ trống ô 6 và ô 7 dù dò tuyến tính luôn nhận ô rỗng gần nhất về bên phải. "(2)" sai vì xếp 53 ở ô 8 và 243 ở ô 9, cũng nhảy qua hai ô rỗng liền kề. "(3)" sai vì nó đảo hai khoá cuối, cho 243 vào ô 6 và 53 vào ô 7, kết quả đó chỉ đúng nếu 243 được chèn trước 53 trái với thứ tự đề cho.
ABucket is a linked list which holds items in the hash table.
BA bucket is a block of space which is large enough to store all colliding items.
CColliding elements in the same position in the hash table are placed on a bucket associated with that position.
DAll of the statements are incorrect.
Lời giải
Đáp án đúng: "Colliding elements in the same position in the hash table are placed on a bucket associated with that position.". Địa chỉ theo bucket gắn mỗi ô của bảng băm với một vùng chứa riêng, nên mọi khoá băm về cùng một chỉ số đều được xếp vào bucket của chính ô đó; tra cứu vì vậy chỉ cần tính hàm băm một lần rồi quét trong bucket tương ứng. Phương án "Bucket is a linked list which holds items in the hash table." mô tả phương pháp chuỗi móc nối, nơi vật chứa là danh sách liên kết co giãn tuỳ ý; bucket theo nghĩa địa chỉ bucket lại là một khối không gian có kích thước định trước. Phương án "A bucket is a block of space which is large enough to store all colliding items." nói đúng rằng bucket là một khối không gian nhưng khẳng định nó luôn đủ chứa mọi khoá va chạm; thực tế kích thước bucket cố định nên vẫn có thể tràn và phải xử lý tràn bằng cơ chế riêng. Phương án "All of the statements are incorrect." sai vì phát biểu gắn bucket với từng vị trí băm đã nêu đúng cơ chế.
Đáp án đúng: "3". Bậc các đỉnh: A và E đều bậc 4, còn B, C, D, F, G đều bậc 2, nên dãy xét giảm dần theo bậc là A, E rồi nhóm bậc 2 lấy theo thứ tự chữ cái B, C, D, F, G. Tô A màu 1; E không kề A nên cũng nhận màu 1; B kề A và E nên lấy màu 2; C kề A và E nên cũng màu 2; D kề A màu 1 còn F chưa tô nên D lấy màu 2; đến lượt F, nó kề E màu 1 và kề D màu 2 nên màu nhỏ nhất còn dùng được là 3. Con số "1" không được vì F kề E đang mang màu 1. Con số "2" chỉ xảy ra nếu F được xét trước D, nhưng trong nhóm cùng bậc 2 thì D đứng trước F theo thứ tự chữ cái nên D đã chiếm màu 2 ở đầu kia của cạnh D–F. Con số "4" vượt nhu cầu vì màu 3 vẫn trống với F. Con số "5" càng xa, cả đồ thị chỉ cần ba màu là A và E màu 1, nhóm bậc 2 màu 2 và riêng F màu 3.
Đáp án đúng: "40". Đồ thị có sáu đỉnh nên cây khung nhỏ nhất phải gồm đúng năm cạnh phủ hết A, B, C, D, E, F. Chạy Kruskal theo trọng số tăng: lấy A-B 3, lấy B-C 4, bỏ A-C 6 vì nó tạo chu trình A-B-C, lấy A-D 8, lấy C-E 10, rồi lấy E-F 15 để kéo F vào; tổng 3 + 4 + 8 + 10 + 15 = 40. Vì vậy "42" sai vì nó nối F bằng D-F 17 thay cho E-F 15, cho 3 + 4 + 8 + 10 + 17; "25" sai vì 3 + 4 + 8 + 10 mới có bốn cạnh và chỉ phủ A, B, C, D, E, bỏ rơi hẳn F; "31" sai vì nó thấp hơn mức sàn: phủ năm đỉnh đầu rẻ nhất đã tốn 25 và cạnh rẻ nhất chạm F là 15, nên không cây khung nào xuống dưới 40; "48" sai vì chỉ đạt được khi đếm thừa cạnh, chẳng hạn giữ cả A-C 6 gây chu trình rồi dùng D-F 17 thành 3 + 4 + 6 + 8 + 10 + 17, tức sáu cạnh cho sáu đỉnh.
Đáp án đúng: "B, A, C, F, D, E, B". Đồ thị có các cạnh A-B, A-C, A-D, A-F, B-C, B-D, B-E, C-D, C-E, C-F, D-E, D-F; thuật toán luôn chọn đỉnh kề chưa dùng đứng đầu theo chữ cái và quay lui khi bế tắc. Từ B chọn A, từ A chọn C, từ C chọn D. Tại D chọn E, nhưng E chỉ kề B, C, D đều đã nằm trong H mà H chưa đủ sáu đỉnh, nên E bị loại và quay lui; thử F cũng bế tắc vì F chỉ kề A, C, D. Quay lui thêm một bước, tại C thử E thì được B, A, C, E, D, F nhưng F không kề B nên không đóng được chu trình. Quay lui nữa, tại C chọn F, rồi F chọn D, rồi D chọn E; lúc này H đủ sáu đỉnh và E kề B nên chu trình đóng thành B, A, C, F, D, E, B. "B, A, F, D, E, C, B" và "B, A, F, C, D, E, B" đều chọn F tại A, trong khi C đứng trước F theo chữ cái và nhánh qua C chưa cạn. "B, C, E, D, F, A, B" bỏ A ngay bước đầu dù A là đỉnh kề đầu tiên của B. "B, D, A, F, C, E, B" bỏ qua cả A và C tại B.
{ch = top element of the stack S
if ch is isolated then remove it from the stack and put it to E
Đề bài
else
select the first vertex Y (by alphabet order), which is adjacent
to ch,push Y to S and remove the edge (ch,Y) from the graph
Đề bài
}
the last array E obtained is an Euler cycle of the graph
Suppose a multigraph G is given below (view picture). Which of the followings is the Euler cycle from the vertex C, created by above algorithm?
AC, B, A, D, C
BC, A, B, C, A, D, C
CC, D, A, C, B, A, C
DC, B, A, C, A, D, C
EC, B, A, D, C, A, C
Lời giải
Đáp án đúng: "C, D, A, C, B, A, C". Đồ thị có các cạnh A–B, A–D, B–C, C–D và hai cạnh song song A–C, mọi đỉnh đều bậc chẵn. Chạy thuật toán từ C: đỉnh kề C đứng đầu theo thứ tự chữ cái là A nên đẩy A và bỏ một cạnh A–C; từ A chọn B, bỏ A–B; từ B chỉ còn C, bỏ B–C; từ C chọn A, bỏ cạnh A–C còn lại; từ A chọn D, bỏ A–D; từ D chọn C, bỏ C–D. Ngăn xếp từ đáy lên là C, A, B, C, A, D, C và mọi đỉnh đã cô lập, nên lần lượt lấy ra ghi vào mảng kết quả theo chiều ngược lại, cho C, D, A, C, B, A, C. "C, A, B, C, A, D, C" là ngăn xếp đọc từ đáy lên, tức cùng chu trình nhưng đi theo chiều ngược, không phải mảng mà thuật toán xuất ra. "C, B, A, C, A, D, C" rời C bằng cạnh C–B, trái với quy tắc chọn đỉnh kề đầu theo thứ tự chữ cái. "C, B, A, D, C, A, C" cũng mở đầu bằng C–B nên vướng đúng chỗ đó dù vẫn đi đủ sáu cạnh. "C, B, A, D, C" chỉ dùng bốn cạnh, bỏ sót hai cạnh nên không phải chu trình Euler.
Đáp án đúng: "A, B, C, E, F". Khởi đầu A có nhãn 0, các cung ra cho B nhãn 7, C nhãn 9, E nhãn 14. Nhỏ nhất là 7 nên B vào tập S; từ B đường tới C dài 17 nên C giữ 9, còn D nhận 22. Nhỏ nhất kế tiếp là 9 nên C vào S; cung C–E trọng số 2 hạ nhãn của E xuống 11, cung C–D trọng số 11 hạ nhãn của D xuống 20. Nhỏ nhất bây giờ là 11 nên E vào S, cung E–F trọng số 9 cho F nhãn 20, nên F được lấy vào S ở bước kế tiếp và câu hỏi kết thúc đúng ở đó. Dãy "A, B, D, F" cho D vào S ngay sau B, nhưng nhãn của D không khi nào nhỏ hơn nhãn của C rồi của E, nên C với E phải vào S trước D và dãy chọn không thể bỏ qua chúng. Dãy "A, E, F" dùng cung A–E trọng số 14 để kết luận, bỏ qua đường qua C chỉ dài 11 và bỏ qua việc B, C được chốt trước vì nhãn nhỏ hơn. Dãy "A, C, E, F" thiếu B, nhưng nhãn 7 của B nhỏ hơn nhãn 9 của C nên B phải vào S ngay ở bước thứ hai.
Đáp án đúng: "C, B, D, F, A, E, G". Duyệt theo bề rộng từ C: thăm C, đưa các đỉnh kề của C theo thứ tự chữ cái vào hàng đợi là B, D, F. Lấy B thì thêm A và E (C, D đã biết); lấy D thì không có đỉnh mới vì B, C, F đã vào; lấy F thì thêm G. Các đỉnh còn lại trong hàng đợi A, E, G không mở ra đỉnh mới, vậy thứ tự thăm là C, B, D, F, A, E, G. Đỉnh H không có cạnh nào nên không bao giờ tới được từ C, phép duyệt một nguồn chỉ phủ thành phần liên thông chứa nguồn. "C, B, D, F, A, E, G, H" sai vì nó gắn thêm H vào dù không có đường nào từ C tới H. "C, B, D, A, E, F, G, H" sai vì vừa thêm H, vừa đẩy F xuống sau A và E dù F kề thẳng C nên thuộc mức một. "C, B, D, A, E, F, H, G" sai vì mắc cả hai lỗi trên và còn đảo thứ tự hai đỉnh cuối.
Đáp án đúng: "N". Muốn một đồ thị gắn cả n đỉnh vào một khối thì cần ít nhất n − 1 cạnh, và khi đúng n − 1 cạnh thì nó là cây, mà cây không có chu trình vì giữa hai đỉnh chỉ tồn tại duy nhất một đường đi. Thêm đúng một cạnh nữa, tổng n cạnh, là đủ để đóng một chu trình: chẳng hạn lấy một cây rồi nối hai lá lại với nhau. Vậy n là con số nhỏ nhất. Phương án "n-1" là số cạnh của cây khung, tức mức vừa đủ để nối hết đỉnh mà vẫn chưa có chu trình nào. Phương án "n+1" đủ tạo chu trình nhưng dư một cạnh so với mức cần, nó ứng với đồ thị đã có hai chu trình độc lập hoặc một cạnh thừa. Phương án "2n" dư nhiều hơn nữa, gấp đôi số đỉnh, trong khi n cạnh đã đóng được chu trình nên câu hỏi về mức tối thiểu không thể nhận con số ấy.
Đáp án đúng: "6, 2, 8, 1, 4, 7, 5". Cây có gốc 6, nhánh trái 3 với hai con 1 và 4, dưới 1 là con phải 2, dưới 4 là con phải 5, nhánh phải 8 với con trái 7. Xoá 3 bằng cách sao chép thì lấy nút cực phải của nhánh trái của 3: đi từ 1 sang 2, mà 2 không có con phải nên 2 là tiền nhiệm trung tố; gán 2 vào chỗ của 3 rồi tháo nút 2 cũ, vì 2 là lá nên con phải của 1 thành rỗng. Cây mới có gốc 6, nhánh trái 2 với hai con 1 và 4, dưới 4 vẫn là 5, nhánh phải vẫn là 8 với con trái 7. Duyệt theo chiều rộng cho 6, rồi 2 và 8, rồi 1, 4, 7, rồi 5. Dãy "6, 1, 8, 2, 7, 4, 5" là kết quả xoá bằng cách nối, khi 1 lên thế chỗ 3 và nhánh của 4 treo xuống dưới 2. Dãy "6, 2, 7, 1, 4, 8, 5" đưa 7 lên mức hai, nhưng 7 là con trái của 8 nên 8 vẫn giữ vai con phải của gốc. Dãy "6, 1, 7, 2, 8, 5, 4" vừa nhầm nút thay thế vừa xếp 5 trước 4, dù 4 là cha của 5 nên nằm cạn hơn một mức.
Đáp án đúng: "5, 1, 7, 2, 6, 8, 4". Cây ban đầu có gốc 5, bên trái là 3 với hai con 1 và 4 trong đó 1 chỉ có con phải 2, bên phải là 7 với hai con 6 và 8. Xoá bằng cách nối là tìm nút phải nhất của cây con trái của nút bị xoá, treo cây con phải của nút bị xoá vào đó, rồi đưa cây con trái lên thay chỗ: cây con trái của 3 là 1, đi phải hết cỡ được 2, nên nút 4 trở thành con phải của 2, rồi 1 lên làm con trái của 5. Cây mới có 5 với hai con 1 và 7; 1 có con phải 2; 2 có con phải 4; 7 có hai con 6 và 8. Duyệt bề rộng cho 5, rồi 1 và 7, rồi 2, 6, 8, rồi 4. Vì vậy "5, 1, 7, 6, 8, 2, 4" sai vì 2 là con của 1 nên phải ra khỏi hàng đợi trước các con của 7; "5, 2, 7, 1, 4, 6, 8" sai vì đó là kết quả của phép xoá bằng cách sao chép, nó kéo giá trị 2 lên chỗ nút 3 rồi cắt nút 2; "5, 2, 7, 1, 6, 8, 4" sai vì nó vừa đưa 2 lên làm con trái của 5 vừa treo 4 xuống dưới nút 1, không khớp bước nào của phép nối.
Đáp án đúng: "4, 2, 7, 5, 1, 3, 8, 6". Duyệt giữa luôn theo trình tự con trái, gốc, con 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). Nhánh trái: in 4 trước, rồi 2, rồi vào 5 phải xuống 7 trước nên in 7 rồi 5, được 4, 2, 7, 5. Thăm gốc 1. Nhánh phải: 3 không có con trái nên in 3 ngay, rồi vào 6 phải xuống 8 trước nên in 8 rồi 6, được 3, 8, 6. "4, 2, 7, 5, 1, 8, 6, 3" đẩy 3 xuống sau cả 8 và 6, đó là cách duyệt sau xử lý nhánh phải, còn duyệt giữa phải thăm 3 trước con phải của nó. "4, 7, 5, 2, 8, 6, 3, 1" là kết quả duyệt sau, nhận ra vì gốc 1 đứng cuối. "4, 2, 5, 7, 1, 8, 6, 3" in 5 trước con trái 7 của nó, tức làm theo thứ tự gốc rồi con trái.
Đáp án đúng: "1, 3, 4, 7, 5, 2, 6, 8". Cây có gốc 1 với con trái 3 và con phải 2; nút 3 có con trái 4 và con phải 5; nút 4 có con trái 7; nút 2 chỉ có con phải 6; nút 6 có con trái 8. Duyệt trước in gốc rồi vét hết nhánh trái mới sang nhánh phải: 1, 3, 4, 7, rồi 5 là con phải của 3; sang nhánh phải của gốc được 2, 6, rồi 8 là con trái của 6. "7, 4, 3, 5, 1, 2, 8, 6" là dãy duyệt giữa, nhận ra vì gốc 1 nằm giữa hai nhánh. "7, 4, 5, 3, 8, 6, 2, 1" là dãy duyệt sau, gốc 1 đứng cuối cùng. "1, 3, 4, 7, 5, 2, 8, 6" chỉ khác đáp án ở hai số cuối: nó in 8 trước 6, nhưng 8 là con trái của 6 nên trong duyệt trước cha 6 phải ra trước.
". Tiền thứ tự nghĩa là thăm gốc trước rồi mới xuống nhánh trái, sau đó nhánh phải, nên lệnh thăm phải đứng trước cả hai lời gọi đệ quy; thêm vào đó điều kiện p khác null chính là chỗ dừng, nó chặn lời gọi đi vào cây rỗng. Cách viết "
" đảo điều kiện thành p bằng null, tức chỉ làm việc khi con trỏ rỗng, nên nó thăm một nút không tồn tại và không bao giờ đi xuống cây thật. Cách viết "
" đúng trật tự thăm nhưng bỏ hẳn chỗ dừng, mỗi lá vẫn gọi tiếp vào hai con rỗng nên đệ quy lún vô hạn và chương trình đổ vì truy cập trên con trỏ rỗng.
Đáp án đúng: "4, 2, 7, 1, 3, 6, 8". Xoá bằng sao chép nghĩa là chép 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, rồi xoá chính nút nguồn đó. Cây con trái của 5 là 2 với con phải 4, mà 4 không có con phải nên 4 là khoá liền trước; chép 4 lên gốc rồi bỏ nút 4, con trái 3 của nó nối lên làm con phải của 2. Cây còn lại có gốc 4, con trái 2 với hai con 1 và 3, con phải 7 với hai con 6 và 8, nên duyệt theo bề rộng cho 4, rồi 2 và 7, rồi 1, 3, 6, 8. "2, 1, 4, 3, 7, 6, 8" sai vì đó là kết quả của xoá bằng hợp nhất, khi 2 lên gốc và cây con phải 7 được treo dưới nút phải nhất là 4. "2, 1, 4, 3, 7, 8, 6" sai vì ngoài việc dùng cách hợp nhất nó còn in 8 trước 6 ở mức cuối. "2, 1, 4, 3, 6, 7, 8" sai vì nó đưa 6 lên cùng mức với cha của nó là 7, mà duyệt theo mức không bao giờ in con trước cha.
Đáp án đúng: "40, 15, 50, 35, 45, 30". Cây có gốc 40, con trái 25 với con trái 15 và con phải 35, con trái của 35 là 30, còn 50 có con trái 45. Xoá 25 theo kiểu hợp nhất nghĩa là cho nhánh trái của nó leo lên thay chỗ, rồi treo nhánh phải của nó vào nút phải nhất của nhánh trái. Nhánh trái của 25 chỉ có một nút 15, nên 15 lên làm con trái của 40 và cây gốc 35 trở thành con phải của 15. Cây mới: 40 có hai con 15 và 50; 15 có con phải 35; 50 có con trái 45; 35 có con trái 30. Duyệt theo lớp cho 40; rồi 15, 50; rồi 35, 45; rồi 30. Phương án "40, 35, 15, 50, 45, 30" đưa 35 lên thay 25, đó là lấy nút phải nhất của nhánh trái làm nút thay thế, tức kiểu xoá sao chép. Phương án "15, 40, 35, 50, 45, 30" đặt 15 trước 40 nên không còn là duyệt theo lớp tính từ gốc. Phương án "40, 30, 15, 50, 35, 45" cho 30 làm con của 40, nhưng 30 vẫn nằm sâu dưới 35 sau khi hợp nhất.
Đáp án đúng: "The tree is both full and complete.". Cây có gốc 40 với hai con 25 và 50; 25 có hai con 15 và 35; 15 có hai con 10 và 20; 50 có hai con 45 và 55; các nút 35, 10, 20, 45, 55 là lá. Kiểm tính đầy: mọi nút trong là 40, 25, 15, 50 đều có đúng hai con và mọi nút khác không có con nào, nên cây đầy. Kiểm tính đủ: mức một có 40, mức hai có 25 và 50, mức ba có 15, 35, 45, 55 tức đã kín, mức cuối chỉ có 10 và 20 là hai con của 15 mà 15 là nút ngoài cùng bên trái của mức ba, nên các lá cuối nằm sát bên trái và cây đủ. Phương án "The tree is full but not complete." bỏ qua chi tiết 10 và 20 treo đúng ở nhánh trái nhất, nơi tính đủ yêu cầu. Phương án "The tree is complete but not full." sai vì không tìm được nút trong nào chỉ có một con. Phương án "The tree is neither complete nor full." trái cả hai phép kiểm vừa chạy.
Node search(int x){ Node p = root;while(p!=null && p.info != x){if(x<p.info) p = p.left;
else p=p.right;}return(p);}
The complexity of this algorithm is:
AO(n^2)
BO(n).
CO(log n).
DO(nlog n)
Lời giải
Đáp án đúng: "O(log n).". Thân vòng while chỉ làm một việc là so x với p.info rồi chuyển p sang p.left hoặc p.right, tức mỗi lượt đi xuống đúng một tầng và cắt bỏ trọn một cây con, nên số lượt lặp nhiều nhất bằng chiều cao cây. Với cây tìm kiếm nhị phân có chiều cao tối ưu trên n nút thì chiều cao xấp xỉ log2 của n, nên chi phí tìm là O(log n), và đó cũng chính là lý do người ta phải cân bằng cây. Vì vậy "O(n^2)" sai vì không có vòng lặp lồng nhau nào, thân vòng chỉ gồm một phép so sánh và một phép gán; "O(nlog n)" sai vì đó là cấp của các thuật toán sắp xếp dựa trên so sánh phải chạm mọi phần tử, còn ở đây ta chỉ đi một đường từ gốc xuống; riêng "O(n)." chỉ đúng khi cây suy biến thành dạng xương sống, mỗi nút một con và chiều cao bằng số nút, tức trường hợp xấu nhất mà câu hỏi không nêu, nên nó không phải cấp đặc trưng được gán cho phép tìm trên cây tìm kiếm.
