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

Đáp án đúng: "A recursive method is a method that invokes itself directly or indirectly. For a recursive method to terminate there must be one or more base cases.". Câu này nêu đủ hai nửa của khái niệm: định nghĩa đệ quy là hàm tự gọi chính nó, trực tiếp hoặc qua hàm trung gian, và điều kiện dừng là phải có trường hợp cơ sở trả về kết quả mà không gọi lại chính mình, nếu không chuỗi lời gọi dài mãi và tràn ngăn xếp. Phương án "There is no difference between a recursive method and a non-recursive method." sai vì hàm đệ quy sinh nhiều khung lời gọi lồng nhau trên ngăn xếp, trong khi hàm thường chỉ một khung. Phương án "For a recursive method to terminate there must be one or more steps." nói một điều rỗng, hàm nào cũng gồm các bước, cái quyết định dừng là nhánh không gọi lại. Phương án "For a recursive method to terminate there must be one or more limit conditions." chỉ chạm nửa sau và dùng chữ chung chung: một điều kiện chặn mà bên trong vẫn gọi lại chính mình thì chương trình vẫn không dừng, điều cần là nhánh cơ sở có đường ra.

Đáp án đúng: "BAABBBBA". Trên cây Huffman, nhánh trái của gốc mang nhãn 0 và dẫn thẳng tới lá A, nhánh phải mang nhãn 1 và dẫn tới một nút trong; từ nút trong đó, nhãn 0 cho lá B và nhãn 1 cho lá C. Vậy A = 0, B = 10, C = 11, không mã nào là tiền tố của mã khác nên giải mã là duy nhất. Đọc 1000101010100 từ trái sang và đi trên cây: 10 cho B, 0 cho A, 0 cho A, rồi bốn cặp 10 liên tiếp cho B, B, B, B, cuối cùng bit 0 cho A. Ghép lại được BAABBBBA, dùng đúng hết 13 bit. Phương án "CAABBBBA" mở đầu bằng C ứng với 11, trong khi hai bit đầu là 10. Phương án "BAABBABA" và phương án "BABABBBA" đều xen thêm A vào giữa các cặp 10, nên tiêu thụ thừa bit 0 và tổng số bit không còn khớp với chuỗi đã cho.

Đáp án đúng: "True". Mã Huffman là mã có độ dài thay đổi: mỗi ký tự ứng với một chuỗi bit dài ngắn khác nhau, do đó dòng bit nén không có mốc phân cách ký tự nào ngoài chính cấu trúc cây mã. Bên giải nén phải lần theo đúng cây mà bên nén đã dùng để biết bit nào kết thúc một ký tự; dùng cây khác thì cùng một dòng bit sẽ được cắt thành các ký tự khác, cho ra tệp không trùng bản gốc. Vì vậy trên thực tế người ta gửi kèm bảng tần số hoặc bảng mã ngay trong phần đầu tệp nén, hoặc hai bên thống nhất trước một bảng mã cố định. "False" sai vì nếu không cần chung bảng mã thì việc giải mã sẽ phụ thuộc vào bảng mã tuỳ ý của bên nhận, và tính giải mã được một cách duy nhất của mã tiền tố mất ý nghĩa.

Đáp án đúng: "38". Cây khung nhỏ nhất của 6 đỉnh cần đúng 5 cạnh. Xét theo trọng số tăng: lấy A–B bằng 3, lấy C–D bằng 4, lấy A–C bằng 6 để nối hai khối lại, bỏ A–D bằng 8 vì hai đầu đã cùng khối, lấy C–E bằng 10 để thêm E, rồi lấy E–F bằng 15 là lối nhẹ nhất tới F so với D–F bằng 17, cuối cùng bỏ B–E bằng 19. Tổng bằng 3 cộng 4 cộng 6 cộng 10 cộng 15. Số "40" là tổng khi dùng D–F bằng 17 thay cho E–F bằng 15, vẫn là một cây khung nhưng đắt hơn đúng 2. Số "18" thấp hơn cả tổng năm cạnh nhẹ nhất của đồ thị là 3, 4, 6, 8, 10 bằng 31, nên không cây khung nào đạt được mức ấy. Số "24" cũng dưới 31, nó chỉ bằng tổng vài cạnh nhẹ chứ chưa đủ 5 cạnh. Số "26" vẫn dưới 31, mà năm cạnh nhẹ nhất đã là 31 và chúng còn chưa nối được hết 6 đỉnh.

Đáp án đúng: "15, 7, 20, 3, 12, 17, 0". Chèn lần lượt 15, 7, 3, 0, 12, 20, 17: 15 là gốc; 7 nhỏ hơn 15 nên là con trái; 3 nhỏ hơn 15 rồi nhỏ hơn 7 nên là con trái của 7; 0 đi tiếp xuống làm con trái của 3; 12 nhỏ hơn 15 nhưng lớn hơn 7 nên là con phải của 7; 20 lớn hơn 15 nên là con phải của gốc; 17 lớn hơn 15 nhưng nhỏ hơn 20 nên là con trái của 20. Đọc theo mức: 15, rồi 7 và 20, rồi 3, 12 và 17, rồi 0 ở mức bốn. "15, 7, 20, 3, 12, 0, 17" kéo 0 lên trước 17, nhưng 0 ở mức bốn còn 17 vẫn ở mức ba. "15, 7, 20, 3, 17, 12, 0" đọc 17 trước 12 trong cùng mức ba, trái với chiều từ trái sang phải vì 12 thuộc nhánh trái của gốc. "15, 7, 20, 3, 17, 0, 12" vừa đảo 12 với 17 vừa đưa 0 lên mức ba.

Đáp án đúng: "-1". Chèn lần lượt 5, 3, 6, 2, 4, 1: 5 làm gốc, 3 sang trái, 6 sang phải, 2 là con trái của 3, 4 là con phải của 3. Khi chèn 1 xuống làm con trái của 2, nhánh trái của gốc cao ba tầng còn nhánh phải chỉ một tầng, nên hệ số cân bằng của 5 thành -2 và cây mất cân bằng kiểu trái-trái; phép quay phải tại 5 đưa 3 lên làm gốc, con trái là 2 (vẫn giữ con trái 1) và con phải là 5 (với con trái 4, con phải 6). Sau quay, nút 2 có cây con trái là nút 1 cao một tầng và cây con phải rỗng cao không tầng, nên hệ số bằng 0 trừ 1, tức -1. "1" là dấu ngược lại, chỉ đúng nếu 1 là con phải của 2, nhưng 1 nhỏ hơn 2 nên phải nằm bên trái. "0" đòi hai cây con của 2 cao bằng nhau, tức 2 phải có cả hai con hoặc không có con nào. "2" không thể xuất hiện khi cây vẫn là AVL, vì hệ số cân bằng ở mọi nút chỉ nhận -1, 0 hoặc 1.

Đáp án đúng: "30, 10, 40, 5, 25, 35, 20". Cây có gốc 30, bên trái là 15 với hai con 5 và 25 trong đó 5 có con phải 10 và 25 có con trái 20, bên phải là 40 với con trái 35. Xoá bằng cách sao chép là kéo giá trị của nút liền trước, tức nút phải nhất của cây con trái, lên chỗ nút bị xoá rồi cắt nút ấy: cây con trái của 15 là 5, đi phải hết cỡ được 10, nên 10 lên thay 15 và nút 10 bị cắt khỏi 5. Cây mới có 30 với hai con 10 và 40; 10 có hai con 5 và 25; 25 có con trái 20; 40 có con trái 35. Duyệt bề rộng cho 30, rồi 10 và 40, rồi 5, 25, 35, rồi 20. Vì vậy "30, 5, 40, 10, 35, 25, 20" sai vì đó là kết quả của phép xoá bằng cách nối, treo cây con phải 25 vào nút 10 rồi đưa 5 lên; "30, 25, 40, 5, 20, 10, 35" sai vì nó dùng nút kế tiếp 25 thay cho nút liền trước 10, lại in 10 trước 35 dù 35 ở tầng trên; "30, 5, 40, 25, 35, 10, 20" sai vì nó dựng lại cả cấu trúc cây con trái, còn xoá bằng sao chép chỉ dời một giá trị và cắt đúng một nút.

Đáp án đúng: "22". Tính xuôi từ hai mốc f(0) = 2 và f(1) = 2 theo công thức f(n) = f(n-1) + 2f(n-2): f(2) = f(1) + 2f(0) = 2 + 4 = 6; f(3) = f(2) + 2f(1) = 6 + 4 = 10; f(4) = f(3) + 2f(2) = 10 + 12 = 22. Mẹo kiểm nhanh: hệ số 2 luôn nhân vào số hạng cách hai bậc, nên bước cuối phải là 10 cộng hai lần 6. Con số "24" đòi f(3) bằng 12, nhưng f(3) = 6 + 2 nhân 2 = 10. Con số "23" đòi f(3) bằng 11, không khớp bước nào vì mọi giá trị trong chuỗi 2, 2, 6, 10, 22 đều là số chẵn. Con số "21" đòi f(3) bằng 9, tức bớt một đơn vị ở phép tính 6 + 4.

Đáp án đúng: "2, 1, 4, 3, 7, 8, 9". Cây có gốc 5, con trái 2 với hai con 1 và 4, con trái của 4 là 3; con phải của 5 là 7, con phải của 7 là 8, con phải của 8 là 9. Xoá gốc theo kiểu hợp nhất: nhánh trái leo lên làm gốc mới, còn nhánh phải được treo vào nút phải nhất của nhánh trái. Nút phải nhất của nhánh trái là 4, vì từ 2 đi sang con phải 4 rồi 4 không còn con phải; nên cây gốc 7 trở thành con phải của 4. Cây mới: gốc 2 với hai con 1 và 4; 4 có con trái 3 và con phải 7; 7 có con phải 8; 8 có con phải 9. Các lớp là 2; rồi 1, 4; rồi 3, 7; rồi 8; rồi 9. Phương án "4, 2, 7, 1, 3, 8, 9" lấy nút phải nhất 4 lên làm gốc, đó là kiểu xoá sao chép. Phương án "2, 1, 4, 7, 8, 3, 9" đẩy 7 và 8 lên trước 3, nhưng 3 và 7 cùng là con của 4 nên cùng lớp và 3 là con trái nên đứng trước. Phương án "4, 2, 7, 1, 8, 3, 9" vừa đổi gốc thành 4 vừa xếp lớp sai.

Đáp án đúng: "Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like, into an index i = h(x) in the table T, where T[i] is used for storing an item having key x or its address.". Định nghĩa này nói đủ hai điều làm nên một hàm băm: khoá có thể thuộc kiểu bất kỳ, và giá trị trả về là một chỉ số i hợp lệ của bảng T, nơi lưu phần tử hoặc địa chỉ của nó; nếu không ràng buộc đích là chỉ số của bảng thì không có chỗ để đặt dữ liệu. "Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like, into non-negative integer." chưa đủ vì nó dừng ở số nguyên không âm, không nói gì tới việc ép về vùng chỉ số của bảng, mà chính bước lấy dư theo kích thước bảng mới làm nên hàm băm. "Hash function h(x) is a function which transforms a particular key x (string, or number) into an index i = h(x) in the table T, where T[i] is used for storing an item having key x or its address." bị hẹp vì chỉ nhận khoá là chuỗi hoặc số, loại bỏ khoá dạng bản ghi vốn rất thường gặp. "Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like, into a positive integer." sai vì nó loại trừ giá trị 0, trong khi ô đầu tiên của bảng mang chỉ số 0 và là đích hoàn toàn hợp lệ.

Đáp án đúng: "3". Lời gọi đầu có low bằng 2, high bằng 5 nên k bằng 3 và phần tử ở chỉ số 3 là 8; vì 7 nhỏ hơn 8 nên gọi tiếp với đoạn từ 2 tới 2. Lời gọi thứ hai có k bằng 2 và phần tử ở chỉ số 2 là 6; vì 7 lớn hơn 6 nên gọi tiếp với low bằng 3, high bằng 2. Lời gọi thứ ba thấy low lớn hơn high nên trả về -1 ngay, không gọi thêm. Vậy có ba lần vào hàm, kể cả lời gọi ban đầu. Số "2" bỏ quên chính lời gọi phát hiện đoạn rỗng, nhưng lần vào hàm ấy có thật và nó mới là chỗ kết luận không tìm thấy 7. Số "4" đòi thêm một tầng nữa sau khi đoạn đã rỗng, mà hàm trả về -1 chứ không gọi tiếp. Số "5" ứng với việc dò trên cả 8 phần tử của mảng, trong khi lời gọi ban đầu đã giới hạn vùng tìm từ chỉ số 2 tới 5, chỉ gồm bốn phần tử.

Đáp án đúng: "A, B, D, C, B, A". Đồ thị có hai cạnh song song A–B cùng các cạnh đơn B–C, B–D, C–D, mọi đỉnh bậc chẵn. Chạy thuật toán từ A: đẩy B và bỏ một cạnh A–B; tại B các đỉnh kề là A, C, D nên theo thứ tự chữ cái chọn A, đẩy A và bỏ cạnh A–B còn lại; A lúc này cô lập nên lấy ra, ghi A vào mảng kết quả; đỉnh ngăn xếp lại là B, chọn C, bỏ B–C; tại C chọn D, bỏ C–D; tại D chọn B, bỏ D–B; giờ mọi đỉnh đã cô lập nên lần lượt lấy ra B, D, C, B, A. Mảng kết quả theo đúng thứ tự lấy ra là A, B, D, C, B, A. "A, B, C, D, B, A" là chu trình thu được nếu tại B ta chọn C thay vì A, trái với quy tắc chọn đỉnh kề đầu theo thứ tự chữ cái. "A, B, C, B, A" chỉ đi bốn cạnh và bỏ sót hai cạnh nối với D. "A, B, A, B, D, C, A" kết thúc bằng cạnh C–A, mà ô A–C trong ma trận kề bằng 0 nên cạnh đó không tồn tại. "A, B, C, D, A" cũng cần cạnh D–A không có trong đồ thị.

Đáp án đúng: "for relatively permanent collections of data". Mảng chiếm một vùng nhớ liên tục có kích thước cố định, nhờ đó truy cập phần tử theo chỉ số chỉ mất O(1), nhưng phải trả giá khi tập dữ liệu biến động: thêm phần tử lúc đã đầy buộc cấp vùng mới lớn hơn rồi sao lại toàn bộ, còn chèn hay xoá ở giữa buộc dồn các phần tử phía sau, cả hai đều O(n). Vì vậy mảng phát huy đúng thế mạnh với tập dữ liệu khá ổn định, biết trước cỡ và chủ yếu để đọc theo chỉ số. "for the size of the structure and the data in the structure are constantly changing" lại mô tả đúng thứ mà mảng làm kém nhất: kích thước đổi liên tục đòi cấp lại bộ nhớ và sao chép nhiều lần, dữ liệu xê dịch liên tục đòi dồn mảng; nhu cầu đó phù hợp với danh sách liên kết, nơi thêm bớt một nút chỉ là sửa vài liên kết.

Đáp án đúng: "pop". Ngăn xếp có đúng hai phép cơ bản mang tên truyền thống: push đẩy phần tử vào đỉnh, pop lấy phần tử ở đỉnh ra và trả nó về cho người gọi; chính cặp tên đó làm người đọc nhận ra ngay kiểu dữ liệu vào sau ra trước. Vì vậy "peek" sai vì nó chỉ đọc giá trị ở đỉnh mà không tháo phần tử nào, số phần tử sau lệnh vẫn như trước; "delete" sai vì đó là tên chung của phép xoá, không nói gì tới việc trả phần tử về và cũng không gắn với đỉnh ngăn xếp; "remove" sai vì nó là tên quen thuộc của các lớp danh sách và tập hợp, nơi ta xoá theo chỉ số hoặc theo giá trị bất kỳ, chứ không phải tên truyền thống của phép lấy khỏi đỉnh ngăn xếp.

Đáp án đúng: "4X4U3X2U5X2U". Nén theo độ dài loạt chỉ việc gom các ký tự giống nhau nằm liền kề rồi ghi số lượng trước ký tự. Thông điệp XXXXUUUUXXXUUXXXXXUU gồm bốn X, bốn U, ba X, hai U, năm X rồi hai U, tổng 4 + 4 + 3 + 2 + 5 + 2 = 20 ký tự, đúng độ dài chuỗi gốc, nên kết quả là 4X4U3X2U5X2U. Dãy "4X4U3X2U5X" bỏ hẳn loạt hai U ở cuối, giải nén lại chỉ ra 18 ký tự. Dãy "4X4U3X2U5X2UU" thêm một U lẻ sau loạt cuối, giải nén thành 21 ký tự nên không khôi phục được thông điệp gốc. Dãy "X4U4X3U2X5UU2" đặt số sau ký tự và vẫn lệch ở đuôi; khuôn mã của phép nén này là số đi trước ký tự, đọc ngược lại sẽ hiểu sai từng loạt.

Đáp án đúng: "17 11 6 4 3 29 5 8 2". Danh sách đôi là 17, 11, 6, 4, 3, 29, 8, 2 và p trỏ vào nút 29. Mã tạo p1 giữ giá trị x = 5, lấy p2 = p.next là nút 8, rồi nối p.next = p1 cùng p1.prev = p để 5 đứng ngay sau 29, tiếp đó p1.next = p2 cùng p2.prev = p1 để 5 nối tiếp sang 8 ở cả hai chiều. Nút 5 do đó nằm giữa 29 và 8. Phương án "17 11 6 4 3 5 29 8 2" là chèn trước nút 29, muốn vậy phải nối qua p.prev chứ không qua p.next. Phương án "17 11 6 4 3 29 8 2 5" là chèn vào cuối, cần dùng tail và gán tail = p1. Phương án "17 5 11 6 4 3 29 8 2" chèn ngay sau head, không liên quan tới p. Phương án "5 17 11 6 4 3 29 8 2" chèn vào đầu, đòi gán lại head mà mã không làm.

Đáp án đúng: "The complete graph is always connected.". Theo định nghĩa đã cho, đồ thị đầy đủ có mọi đỉnh kề mọi đỉnh khác, nên với hai đỉnh bất kỳ đã có ngay một cạnh nối trực tiếp, mà một cạnh cũng là một đường đi; vậy điều kiện liên thông thoả hiển nhiên. "The connected graph is always complete." sai vì liên thông chỉ đòi tồn tại đường đi, không đòi cạnh trực tiếp: một đường thẳng A–B–C liên thông nhưng A và C không kề nhau nên không đầy đủ. "The complete graph is always connected and vise versa." sai đúng ở nửa đảo, vì chiều liên thông suy ra đầy đủ bị phản ví dụ A–B–C bác bỏ. "None of others" sai vì đã có một phát biểu đúng, chính là chiều đầy đủ suy ra liên thông. Nói gọn: đầy đủ là điều kiện mạnh hơn liên thông, bao hàm một chiều chứ không tương đương.

Đáp án đúng: "A, B, C, E, D, F". Từ A nhãn 0, các cung ra cho B nhãn 7, C nhãn 9, E nhãn 14. Chọn B vì 7 nhỏ nhất; qua B thì đường tới C dài 17 nên C giữ 9, còn D nhận 22. Chọn C vì 9 nhỏ nhất; cung C–E trọng số 2 hạ nhãn của E còn 11, cung C–D trọng số 6 hạ nhãn của D còn 15. Chọn E vì 11 nhỏ nhất; cung E–F trọng số 11 cho F nhãn 22. Giờ D với 15 nhỏ hơn F với 22 nên D vào tập S trước, rồi cung D–F trọng số 6 hạ nhãn của F xuống 21, cuối cùng F mới được chọn. Dãy "A, B, C, E, F" dừng ở F ngay sau E, nhưng lúc ấy nhãn của F là 22 còn nhãn của D là 15 nên D phải được chốt trước. Dãy "A, C, E, F" bỏ cả B lẫn D, mà nhãn 7 của B là nhỏ nhất ở bước thứ hai nên B không thể bị bỏ qua. Dãy "A, C, D, F" cũng bỏ B, lại cho D vào ngay sau C, trong khi sau C thì E với nhãn 11 còn nhỏ hơn D với nhãn 15.

Đáp án đúng: "6, 7, 5, 3, 8, 4, 2, 1". Cây có gốc 1 với con trái 3 và con phải 2; nút 3 có con trái 6 và con phải 5; nút 5 có con trái 7; nút 2 có con phải 4; nút 4 có con trái 8. Duyệt sau đi trái, phải rồi gốc nên lá ra trước và gốc ra sau cùng: nhánh trái cho 6, rồi 7 trước cha 5, rồi 3; nhánh phải cho 8 trước cha 4, rồi 2; cuối cùng là 1. "6, 3, 7, 5, 1, 2, 8, 4" là dãy duyệt giữa, dấu hiệu là gốc 1 nằm giữa hai nhánh thay vì ở cuối. "1, 3, 6, 7, 5, 2, 4, 8" mở đầu bằng gốc nên thuộc dáng duyệt trước, mà duyệt trước của cây này là 1, 3, 6, 5, 7, 2, 4, 8 nên dãy đó còn in 7 trước cha 5. "1, 3, 6, 5, 7, 2, 8, 4" cũng bắt đầu bằng gốc, và nó in 8 trước cha 4 nên không khớp phép duyệt nào.