Câu hỏi: CSD201 Cấu trúc dữ liệu và giải thuật – Bộ ôn tập cuối kỳ số 3

Đáp án đúng: "2". Đồ thị có các cạnh A–B, A–C, A–D, A–G, B–C, B–E, C–E, E–F, E–G và D–F. Tô tuần tự theo thứ tự chữ cái, mỗi đỉnh nhận màu nhỏ nhất chưa bị đỉnh kề đã tô dùng: A được 1; B kề A nên được 2; C kề A màu 1 và B màu 2 nên được 3; D kề A màu 1 nên được 2; E kề B màu 2 và C màu 3, không kề đỉnh nào màu 1 nên được 1; F kề E màu 1 và D màu 2 nên được 3; cuối cùng G kề A màu 1 và E màu 1, màu nhỏ nhất còn dùng được là 2. "1" không dùng được vì cả A và E, 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 luôn lấy màu nhỏ nhất. "4" đòi G bị chặn cả ba màu đầu, nhưng G chỉ có hai đỉnh kề nên nhiều nhất chặn được hai màu. "5" càng xa hơn, vì cả đồ thị này tô xong chỉ dùng tới ba màu.

Đáp án đúng: "It is difficult to expand hash tables because they are based on arrays.". Bảng băm dựng trên mảng có kích thước M cố định, mà vị trí của mỗi khoá lại do hàm băm phụ thuộc chính M quyết định. Khi bảng gần đầy, không thể cấp thêm ô ở cuối rồi dùng tiếp, mà phải cấp mảng mới với M mới và băm lại toàn bộ khoá cũ: một lượt O(n) và phải giữ hai vùng nhớ cùng lúc. Đó là cái giá thật của việc đổi lấy truy cập trung bình O(1). "In most cases the collision is unsolvable." sai vì va chạm luôn giải được, bằng dò tuyến tính, dò bậc hai, băm kép hay móc nối; va chạm chỉ làm chậm thao tác chứ không chặn nó. "It is hard to retrieve an item from the hash table." nói ngược thế mạnh của băm: băm khoá ra ô rồi so vài khoá trên đường dò là xong, trung bình O(1). "It is imposible to delete an item from a hash tables." cũng sai: với móc nối thì tháo nút ra khỏi chuỗi, với địa chỉ mở thì đánh dấu ô đã xoá để các lượt dò sau không bị cắt mạch giữa chuỗi.

Đáp án đúng: "(3)". Đó là bảng có 110 ở ô 0, 12 ở ô 2, 103 ở ô 3, 32 ở ô 4, 75 ở ô 5, 132 ở ô 6 và các ô 1, 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: 75 vào ô 5, 12 vào ô 2, 110 vào ô 0, 103 vào ô 3; 32 băm về ô 2 đã có 12 nên dò ô 3 có 103 rồi dừng ở ô 4; 132 cũng băm về ô 2 nên dò 3, 4, 5 đều đầy và dừng ở ô 6. Vì vậy "(1)" sai vì nó đặt 132 ở ô 4 và 32 ở ô 6, chỉ xảy ra nếu 132 được chèn trước 32, trái thứ tự đề cho; "(2)" sai vì nó để trống ô 4 rồi nhét 132 vào ô 6 và 32 vào ô 7, trong khi dò tuyến tính phải nhận ô trống đầu tiên gặp được; "(4)" sai vì nó đặt 132 ở ô 8 và 32 ở ô 9, tức bước dò không phải 1 và lại bỏ qua các ô trống 4, 6 nằm ngay trên đường dò.

Đáp án đúng: "(2)", tức bảng có 64 ở ô 4, 75 ở ô 5, 95 ở ô 6 và 204 ở ô 8, các ô khác trống. Hàm băm lấy số dư cho 10: khoá 64 về ô 4 đang trống nên nhận ngay; khoá 75 về ô 5 cũng trống nên nhận ngay; khoá 95 cũng băm về ô 5 nhưng ô đã đầy, bước dò bậc hai thứ nhất cộng 1 cho ô 6 và ô này trống nên 95 đậu ở ô 6; khoá 204 băm về ô 4 đã đầy, bước dò thứ nhất cộng 1 cho ô 5 cũng đầy, bước dò thứ hai cộng 4 cho ô 8 và ô này trống nên 204 đậu ở ô 8. Bảng "(1)" đặt 204 ở ô 7, chỉ đúng nếu dò từng ô một như dò tuyến tính thay vì cộng bình phương của số bước. Bảng "(3)" đặt 95 ở ô 7, nhưng bước dò đầu tiên của 95 chỉ cộng 1 vào ô 5 nên đích phải là ô 6 đang trống. Bảng "(4)" vừa đẩy 95 tới ô 7 vừa đặt 204 ở ô 9, mà ô 9 lệch 5 so với ô 4 và 5 không phải bình phương của bước dò nào.

Đáp án đúng: "84". Hàm băm gấp dịch chuyển cắt khoá thành các nhóm theo dấu phân cách, cộng các nhóm lại như những số nguyên rồi lấy dư theo kích thước bảng. Với K = 43-65-69-7 ta có bốn nhóm 43, 65, 69 và 7; cộng dần được 43 + 65 = 108, cộng 69 thành 177, cộng 7 thành 184; chia 184 cho TSize = 100 lấy dư được 84. Phương án "82" ứng với tổng 182, tức một nhóm bị cộng thiếu 2. Phương án "86" ứng với tổng 186, như khi nhóm cuối bị đọc thành 9 thay vì 7. Phương án "87" ứng với tổng 187, thường xuất hiện khi một nhóm bị đọc lệch chữ số. Điểm cần nhớ là gấp dịch chuyển cộng thẳng các nhóm theo đúng chiều đọc, khác với gấp biên là lật ngược một số nhóm trước khi cộng; nếu lật nhóm thì tổng và phần dư đều khác.

Đáp án đúng: "94". Boundary folding gấp khoá như gấp một dải giấy, nên các nhóm ở vị trí chẵn bị đảo chữ số trước khi cộng: nhóm 42 giữ nguyên, nhóm 58 đảo thành 85, nhóm 67 giữ nguyên, tổng 42 + 85 + 67 = 194 và h(K) = 194 % 100 = 94. "67" sai vì đó là kết quả của shift folding, phép chỉ cộng thẳng ba nhóm mà không đảo nhóm nào: 42 + 58 + 67 = 167 cho dư 67. "85" sai vì 85 chỉ là nhóm giữa sau khi đảo, tức mới làm nửa việc mà chưa cộng ba nhóm lại. "42" sai vì đó là nhóm đầu chép lại nguyên vẹn, bỏ hẳn cả bước đảo lẫn bước cộng. Điểm cần nhớ là boundary folding và shift folding khác nhau đúng ở chỗ có đảo nhóm xen kẽ hay không, nên cùng một khoá thường cho hai giá trị băm khác nhau.

Đáp án đúng: "3F4O3F2O5F2O". Mã hoá theo loạt đọc dãy ký tự giống nhau liền nhau rồi ghi số lần lặp đứng trước ký tự. Thông điệp tách thành ba F, bốn O, ba F, hai O, năm F, hai O, cộng lại đúng 19 ký tự. Chuỗi "3F4O3F2O5F" dừng ở loạt năm F và bỏ mất hai O cuối, nhưng loạt cuối cùng cũng phải được ghi, nếu không thì giải mã ra chuỗi ngắn hơn hai ký tự. Chuỗi "3F4O3F2O5F2OO" ghi loạt cuối thành 2OO, vừa nêu số lần vừa viết thừa một chữ O, giải mã lại sẽ cho ba O. Chuỗi "FFFOOOOFFFOOFFFFFOO" là chính thông điệp gốc chưa qua mã hoá, nó dài 19 ký tự còn bản mã chỉ 12, nên không có bước nén nào đã xảy ra.

Đáp án đúng: "101". Gộp hai tần số nhỏ nhất E 6 và D 16 thành nút 22, nút nặng hơn là D nằm bên trái nhận nhánh 0 nên E nhận nhánh 1. Hai nhỏ nhất kế tiếp là F 18 và nút 22, gộp thành 40 với nút 22 bên trái và F bên phải. Rồi C 28 với B 32 thành nút 60, B bên trái và C bên phải. Cuối cùng 40 với 60 thành gốc, nút 60 nặng hơn nên bên trái nhận nhánh 0, nút 40 nhận nhánh 1. Đường từ gốc tới E vì vậy là 1 rồi 0 rồi 1. "001" tương ứng với việc nhánh chứa D và E bị treo bên trái gốc, trái với quy ước nhánh nặng hơn đứng bên trái. "100" đúng là mã của D, tức nhầm nhánh ở bước tách D với E. "01" là mã của C, chỉ dài hai bit vì C treo ngay dưới gốc, trong khi E có tần số nhỏ nhất nên phải nằm sâu ba bậc.

Đáp án đúng: "AABBABAB". Theo cây, nhánh phải của gốc là lá A nên A = 1; 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 110000100100 lần lượt: 1 ra A, 1 ra A, 00 ra B, 00 ra B, 1 ra A, 00 ra B, 1 ra A, 00 ra B, hết đúng 12 bit. "CAABBBBA" mở đầu bằng C nên đòi hai bit đầu là 01, còn chuỗi bắt đầu bằng 11. "BABABBBA" cũng sai ngay đầu: B đòi 00 trong khi hai bit đầu là 11. "AABBBCAB" khớp bốn mã đầu rồi gán B cho bit thứ bảy, nhưng bit thứ bảy là 1 nên chỉ có thể là A; muốn đọc ra C thì cần cặp 01, mà sau bit thứ bảy lại là cặp 00.

Đáp án đúng: "(3) (5) (4) (1)". LZW luôn giữ một chuỗi đang khớp, chỉ phát mã khi thêm ký tự mới làm chuỗi đó không còn trong từ điển, và chuỗi dài hơn vừa thất bại chính là mục được thêm với mã kế tiếp. Trên CCCDABCAADA với từ điển đầu chỉ có (1) là A, (2) là B, (3) là C, (4) là D: chuỗi đang khớp là C, gặp C thứ hai thì CC chưa có nên phát (3) và thêm CC thành (5), chuỗi đang khớp lại là C; đọc C thứ ba thì CC đã có mã nên chuỗi đang khớp thành CC, gặp D thì CCD chưa có nên phát (5) và thêm CCD thành (6); chuỗi đang khớp là D, gặp A thì DA chưa có nên phát (4) và thêm DA thành (7); chuỗi đang khớp là A, gặp B thì AB chưa có nên phát (1). Vì vậy "(3) (1) (1) (2)" sai vì nó phát từng ký tự rời và không dùng mục CC vừa thêm; "(3) (5) (6) (4)" sai vì (6) là mã vừa được tạo ở chính bước phát (5), mà LZW không bao giờ phát ngay mã nó mới thêm; "(3) (5) (3) (2)" sai vì sau khi phát (5) thì phần còn lại bắt đầu từ D chứ không phải C; "(5) (1) (4) (2)" sai vì (5) chưa tồn tại lúc bắt đầu, từ điển ban đầu chỉ có bốn mục.