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

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

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

Đá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: "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: "BABABCBC". Cây cho A = 1 vì nhánh phải của gốc là lá A, còn nhánh trái dẫn tới nút trong có lá B ở nhánh 0 và lá C ở nhánh 1, nên B = 00 và C = 01. Đọc 00100100010001 từ trái sang: 00 ra B, 1 ra A, 00 ra B, 1 ra A, 00 ra B, rồi 01 ra C, 00 ra B, 01 ra C, vừa hết 14 bit. "BABABBBA" khớp năm mã đầu rồi coi cặp bit thứ chín và thứ mười là 00, nhưng cặp đó là 0 và 1 nên phải đọc ra C. "BABABCAB" cũng đúng tới BABABC rồi đòi tiếp A và B, tức ba bit 1 và 00, trong khi bốn bit còn lại là 0001 nên chỉ có thể tách thành 00 và 01. "AABBABAB" mở đầu bằng hai chữ A nên đòi hai bit đầu là 11, còn chuỗi đã cho mở đầu bằng 00.