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: "2^k – 1". Với quy ước gốc ở chiều cao 1, tầng thứ i nhiều nhất có 2 mũ (i-1) nút vì mỗi nút sinh tối đa hai con, nên cây k tầng chứa nhiều nhất 2^0 + 2^1 + ... + 2^(k-1) nút, và đó là tổng cấp số nhân bằng 2^k - 1. Thử lại: k bằng 1 cho 1 nút, đúng là một gốc; k bằng 3 cho 7 nút, đúng là cây đầy ba tầng 1 + 2 + 4. Vì vậy "2^(k+1) - 1" sai vì nó là số nút của cây k+1 tầng, tức cộng thêm một tầng không tồn tại, với k bằng 1 nó cho 3; "2^(k-1) + 1" sai vì 2 mũ (k-1) chỉ là sức chứa của riêng tầng cuối, cộng 1 không thay được tổng các tầng trên, với k bằng 3 nó cho 5 thay vì 7; "2^k + 1" sai vì nó vượt sức chứa thật đúng 2 nút, với k bằng 1 nó cho 3 trong khi cây cao một tầng chỉ có thể có một nút.

Đáp án đúng: "3, 5, 17, 11, 10, 8, 13, 4, 8, 6". Insertion sort chỉ sắp dần đoạn đầu, phần sau chưa bị chạm tới. Bước i = 1 chèn 5 vào đoạn chỉ gồm 17, được 5, 17, 3, 11, 10, 8, 13, 4, 8, 6. Bước i = 2 chèn 3 vào đoạn 5, 17, đẩy cả hai sang phải, được 3, 5, 17, 11, 10, 8, 13, 4, 8, 6; ba ô đầu đã sắp, bảy ô sau giữ nguyên thứ tự ban đầu. Dãy "3, 5, 11, 10, 8, 13, 4, 8, 6, 17" đẩy 17 xuống cuối mảng, dấu vết của một lượt bubble sort, còn phép chèn không bao giờ đưa phần tử ra khỏi đoạn đã sắp. Dãy "3, 4, 17, 11, 10, 8, 13, 5, 8, 6" hoán vị 4 với 5, tức chọn phần tử nhỏ nhất toàn mảng rồi đổi chỗ, đó là lối của selection sort. Dãy "3, 4, 5, 11, 10, 8, 13, 17, 8, 6" đã sắp xong ba giá trị nhỏ nhất của cả mảng, vượt xa hai bước đầu.

Đáp án đúng: "AAB". LZW giữ một chuỗi w và đọc thêm từng ký tự k: nếu wk đã có trong từ điển thì mở rộng w thành wk, nếu chưa có thì phát mã của w, thêm wk vào từ điển rồi đặt w = k. Với thông điệp AAABCADAB và từ điển khởi đầu (1) A, (2) B, (3) C, (4) D: w = A, đọc A thứ hai thì AA chưa có nên phát mã 1 và thêm AA thành mục (5), w = A; đọc A thứ ba thì AA đã có nên w = AA; đọc B thì AAB chưa có nên phát mã 5 và thêm AAB thành mục (6). Vậy mã (6) đại diện cho chuỗi AAB. Phương án "AA" là mục (5), sinh ra ngay ở bước đầu. Phương án "CA" chỉ vào từ điển muộn hơn, sau khi BC đã được thêm. Phương án "AB" vào từ điển ở bước cuối cùng, sau BC, CA, AD và DA. Phương án "ABC" chưa bao giờ là w cộng một ký tự trong lượt mã hoá này nên không được thêm vào từ điển.

Đáp án đúng: "7 10 6 4 2 13 8 5 3". Vòng lặp while(f.next != tail) f = f.next chạy từ head và dừng ở nút đứng liền trước nút cuối, tức nút 8. Sau đó q.next = tail và f.next = q khâu nút mới mang 5 vào giữa 8 và nút cuối 3, nên 5 nằm ở vị trí kế cuối. "7 10 6 4 2 13 8 3 5" sai vì chèn sau nút cuối phải viết tail.next = q rồi dời tail, còn ở đây q.next vẫn trỏ về nút cuối. "5 7 10 6 4 2 13 8 3" sai vì đoạn mã không ghi lại head nên đầu danh sách giữ nguyên là 7. "7 5 10 6 4 2 13 8 3" sai vì vị trí đó ứng với việc dùng ngay f = head mà bỏ qua vòng lặp đi tìm nút trước nút cuối. "7 10 6 4 2 13 5 8 3" sai vì nó chèn trước nút 8, muốn vậy vòng lặp phải dừng ở nút 13 chứ không phải nút 8.

Đáp án đúng: "fun(-1023);". Hàm có ba nhánh: n âm thì in dấu trừ rồi gọi lại với -n, n nhỏ hơn 10 thì in n và dừng, còn lại gọi fun(n/10) rồi in chữ số hàng đơn vị. Vậy số lời gọi đệ quy bằng số chữ số trừ một, cộng thêm một lần nữa nếu đối số âm. Với "fun(-1023);" chuỗi gọi là fun(-1023), fun(1023), fun(102), fun(10), fun(1), tức bốn lời gọi đệ quy, nhiều nhất trong các mức được nêu. Lời gọi "fun(1023);" cũng có bốn chữ số nhưng không cần bước đổi dấu nên chỉ ba lời gọi đệ quy. Lời gọi "fun(100);" có ba chữ số và dương, cho hai lời gọi là fun(10) rồi fun(1). Lời gọi "fun(0);" rơi ngay vào nhánh n nhỏ hơn 10, in 0 rồi kết thúc mà không gọi lại lần nào.

Đáp án đúng: "35, 22, 45, 12, 27, 40, 24, 32". Cây ban đầu: gốc 35, con trái 22 với hai con 12 và 32, nút 32 có con trái 27, nút 45 có con trái 40. Chèn 24: nhỏ hơn 35 nên sang trái, lớn hơn 22 nên sang phải tới 32, nhỏ hơn 32 nên tới 27, nhỏ hơn 27 nên thành con trái của 27. Khi đó nút 32 có nhánh trái cao hai mức và nhánh phải rỗng nên chênh 2; đó là nút mất cân bằng thấp nhất, dạng trái–trái, chữa bằng một phép quay phải tại 32: nút 27 lên thay chỗ, 24 vẫn là con trái của 27 và 32 thành con phải. Cây thành gốc 35 với 22 và 45, dưới 22 là 12 và 27, dưới 27 là 24 và 32, dưới 45 là 40. "35, 22, 45, 12, 32, 40, 27, 24" là trạng thái khi không quay, lúc đó cây vi phạm điều kiện AVL tại 32. "35, 22, 45, 12, 32, 40, 24, 27" cũng giữ 32 ở mức ba, chỉ đổi thứ tự hai nút mức bốn. "35, 22, 45, 12, 40, 27, 24, 32" đọc 40 trước 27 trong cùng mức ba, trái với chiều từ trái sang phải của duyệt theo mức.

Đáp án đúng: "7, 4, 8, 3, 6, 9, 5, 10". Chèn 7, 8, 9, 10, 4, 3, 6, 5 vào cây tìm kiếm nhị phân: 7 làm gốc; 8 lớn hơn 7 nên là con phải; 9 lớn hơn cả 7 và 8 nên là con phải của 8; 10 đi tiếp xuống con phải của 9; 4 nhỏ hơn 7 nên là con trái của gốc; 3 nhỏ hơn 4 nên là con trái của 4; 6 lớn hơn 4 nên là con phải của 4; 5 nhỏ hơn 7, lớn hơn 4, nhỏ hơn 6 nên là con trái của 6. Duyệt theo chiều rộng đọc từng mức từ trái sang phải: 7; rồi 4 và 8; rồi 3, 6 và 9; rồi 5 và 10. "7, 4, 8, 6, 3, 9, 5, 10" đổi chỗ 3 với 6, nhưng trong cùng một mức phải đọc từ trái sang phải mà 3 là con trái của 4. "7, 6, 8, 3, 4, 9, 5, 10" đặt 6 ngay dưới gốc, trong khi 6 chèn sau nên phải nằm dưới 4. "7, 8, 9, 10, 4, 3, 6, 5" chỉ là thứ tự chèn ban đầu, không phải thứ tự theo mức của cây.

Đáp án đúng: "It is necessary to build a tree with optimized height to stimulate searching operation.". Trên cây tìm kiếm nhị phân, mỗi phép so sánh đưa ta xuống đúng một tầng, nên chi phí tìm tỉ lệ với chiều cao chứ không với số nút; giữ chiều cao nhỏ nhất có thể, khoảng log2 của n với n nút, chính là điều kiện để phép tìm nhanh. Vì vậy "In a binary search tree, all the nodes that are left descendants of node A have key values greater than A; all the nodes that are A's right descendants have key values less than (or equal to) A." sai vì nó đảo ngược bất biến của cây tìm kiếm: con cháu bên trái phải NHỎ hơn nút, con cháu bên phải mới lớn hơn hoặc bằng. "The main purpose of balancing a tree is to keep the tree in good shape." sai vì dáng cây đẹp chỉ là hệ quả quan sát được, mục đích thật của cân bằng là chặn chiều cao để tìm, chèn, xoá giữ được O(log n). "For better searching performance, a tree should be in back-bone shape." sai vì dạng xương sống là cây suy biến, mỗi nút một con, chiều cao bằng số nút, khiến phép tìm tụt về quét tuyến tính.

Đáp án đúng: "25, 15, 35, 30, 50, 45". Cây có gốc 40, nhánh trái 25 với hai con 15 và 35, dưới 35 là con trái 30, nhánh phải 50 với con trái 45. Xoá 40 bằng cách nối: nhánh trái lên thế chỗ gốc nên 25 thành gốc mới, còn cả nhánh phải được treo vào nút cực phải của nhánh trái, đi từ 25 sang 35 mà 35 không có con phải nên 35 nhận 50 làm con phải. Cây mới có 25 ở mức một; 15 và 35 ở mức hai; 30 là con trái của 35 và 50 là con phải của 35 ở mức ba; 45 ở mức bốn. Duyệt theo chiều rộng cho 25, 15, 35, 30, 50, 45. Dãy "25, 15, 50, 35, 30, 45" đưa 50 lên làm con phải của gốc mới, nhưng phép nối treo cả nhánh phải xuống dưới nút cực phải 35 chứ không nâng nó lên mức hai. Dãy "25, 15, 35, 50, 30, 45" xếp 50 trước 30 ở cùng mức, trong khi duyệt chiều rộng đọc từ trái sang phải nên con trái 30 phải đứng trước con phải 50. Dãy "25, 15, 35, 30, 45, 50" đặt 45 trước 50, nhưng 45 là con trái của 50 nên nằm sâu hơn một mức.

Đáp án đúng: "6, 2, 8, 1, 4, 7, 9". Cây có gốc 6, con trái 3 với hai con 1 và 4, con phải của 1 là 2; con phải của 6 là 8 với hai con 7 và 9. Xoá 3 theo kiểu sao chép: tìm nút phải nhất của nhánh trái của 3, đi từ 1 sang con phải 2 rồi 2 không còn con phải nên nút cần là 2; chép giá trị 2 vào chỗ của 3 rồi tháo nút 2 khỏi vị trí cũ, khiến 1 không còn con phải. Cây mới: gốc 6 với hai con 2 và 8; 2 có hai con 1 và 4; 8 có hai con 7 và 9. Các lớp là 6; rồi 2, 8; rồi 1, 4, 7, 9. Phương án "6, 2, 1, 4, 8, 7, 9" xếp 1 và 4 trước 8, tức trộn lớp hai với lớp ba. Phương án "6, 1, 8, 2, 7, 9, 4" cho 1 lên thay 3 rồi đẩy 2 và 4 xuống sâu hơn, nhưng nút thay thế phải là nút phải nhất 2 chứ không phải gốc nhánh trái 1. Phương án "6, 1, 8, 2, 4, 7, 9" cũng chọn 1 làm nút thay thế nên lớp hai đã sai.

Đáp án đúng: "***** *** * That's all!", tức năm dấu sao ở dòng đầu, rồi ba, rồi một, cuối cùng mới tới dòng chữ. Đọc theo đúng thụt lề: khi n còn dương, hàm chạy vòng for in ra n dấu sao rồi xuống dòng, sau đó mới gọi fun(n-2); nghĩa là in trước, đệ quy sau. Vậy fun(5) in năm dấu sao, fun(3) in ba, fun(1) in một, rồi fun(-1) rơi vào nhánh n nhỏ hơn hoặc bằng 0 và in dòng chữ đúng một lần ở cuối. Dãy "That's all! ***** *** *" đặt dòng chữ lên đầu, thứ tự đó chỉ xảy ra khi lời gọi đệ quy đứng trước vòng for. Dãy "**** ** * That's all!" ứng với fun(4): trừ dần 2 từ 4 thì sau hai dòng đã về 0 nên không thể có dòng một dấu sao. Dãy "* *** ***** That's all!" đi theo chiều tăng, chiều này chỉ xuất hiện nếu vòng for được đặt sau lời gọi fun(n-2) để in lúc các lời gọi lần lượt quay về.

Đáp án đúng: "base cases". Một phương pháp đệ quy chỉ dừng được khi có ít nhất một tình huống nó trả lời trực tiếp mà không gọi lại chính nó, và mọi lời gọi phải tiến dần về tình huống ấy; cụm "base cases" chỉ đúng những tình huống nền đó. Từ "steps" chỉ nói tới các bước, mà bước lại chính là phần gọi lại, càng nhiều bước càng lún sâu chứ không giúp dừng. Từ "limit conditions" nghe như điều kiện chặn giá trị, nhưng một điều kiện giới hạn mà vẫn gọi tiếp thì đệ quy vẫn chạy mãi; điều cần là nhánh trả kết quả ngay. Từ "conditions" quá rộng: mọi câu lệnh rẽ nhánh trong hàm đều là một điều kiện, kể cả điều kiện dẫn vào nhánh đệ quy, nên nó không nêu được cái đặc trưng của chỗ dừng.

Đáp án đúng: "Linked list". Cấu trúc tuyến tính là cấu trúc mà mỗi phần tử có nhiều nhất một phần tử liền trước và một phần tử liền sau, nên toàn bộ dữ liệu xếp thành đúng một dãy và đi hết được bằng một lần đi thẳng; danh sách liên kết đúng như vậy vì mỗi nút chỉ giữ một liên kết tới nút kế tiếp. "Graphs" cho một đỉnh nối tới nhiều đỉnh khác và còn có thể chứa chu trình, không xếp được thành một dãy liền trước liền sau. "Trees" là cấu trúc phân cấp: một nút cha có thể có nhiều con nên từ một phần tử có nhiều hướng đi tiếp. "B-trees" càng không tuyến tính, vì mỗi nút chứa nhiều khoá và có thể có nhiều hơn hai con, cấu trúc này được dùng để hạ chiều cao cây khi dữ liệu nằm trên đĩa.

Đáp án đúng: "(2)", tức bảng có 105 ở ô 4, 25 ở ô 5, 96 ở ô 6 và 35 ở ô 9. Hàm băm chia lấy dư cho 10 nên 25 vào ô 5 và 96 vào ô 6, hai ô này còn trống. Khoá 35 cũng băm về ô 5 đã có 25 nên phải dò bậc hai: i = 1 cho (5+1)%10 = 6 vẫn bị 96 chiếm, i = 2 cho (5+4)%10 = 9 còn trống nên 35 nằm ở ô 9. Khoá 105 lại băm về ô 5: i = 1 ra ô 6 đã đầy, i = 2 ra ô 9 nay đã có 35, i = 3 cho (5+9)%10 = 4 còn trống nên 105 nằm ở ô 4. "(3)" đặt 35 ở ô 7 và 105 ở ô 8, đó là kết quả của dò tuyến tính cộng thêm 1 mỗi bước. "(4)" đặt 35 ở ô 7, chỉ đúng nếu bước dò thứ hai cộng 2 thay vì cộng bình phương của 2. "(1)" đặt 35 ở ô 0, tức (5+25)%10 với i = 5, nghĩa là đã bỏ qua ô 9 vốn còn trống ngay ở bước i = 2.

Đáp án đúng: "for the size of the structure and the data in the structure are constantly changing". Danh sách liên kết cấp phát từng nút rời rồi nối chúng bằng con trỏ, nên thêm hay bớt một phần tử chỉ là sửa vài liên kết: không phải dồn khối phần tử như mảng, cũng không phải cấp một vùng nhớ lớn hơn rồi sao chép toàn bộ khi hết chỗ, và kích thước cấu trúc lớn lên hay co lại đúng theo số nút đang dùng. Vì vậy "for relatively permanent collections of data" sai vì với tập dữ liệu gần như không đổi thì mảng tốt hơn hẳn: truy cập phần tử thứ i trong thời gian hằng nhờ tính địa chỉ, dữ liệu nằm liền nhau nên tận dụng được bộ đệm, và không tốn thêm ô nhớ cho con trỏ của từng nút; đó là trường hợp tiêu biểu để chọn mảng chứ không phải danh sách liên kết.

Đáp án đúng: "True". Từ nút đầu đã đi tới được mọi nút nhờ dãy con trỏ next, nên không phép toán nào trở thành bất khả nếu thiếu con trỏ tail; điều thay đổi chỉ là chi phí. Có tail thì thêm vào cuối hay cài hàng đợi trên danh sách liên kết chỉ mất thời gian hằng số; không có tail thì mỗi lần thêm vào cuối phải đi hết n nút để tìm nút cuối, tức O(n). Đổi lại, giữ tail buộc phải cập nhật nó ở mọi phép thêm và xoá, nhất là khi danh sách trở nên rỗng. Phương án "False" hàm ý tail mang thêm năng lực biểu diễn hoặc mở ra phép toán mới, nhưng mọi việc tail giúp đều làm được bằng cách đi lần từ nút đầu, chỉ chậm hơn.

Đáp án đúng: "A, B, C, E, D, F, A". Đồ 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, và không có A–E, B–F, E–F. Chạy quay lui từ A, mỗi bước lấy láng giềng đầu theo chữ cái: A chọn B, B chọn C, C chọn D, D chọn E; tới E thì B, C, D đều đã trong H mà H mới có 5 đỉnh, nên E bị loại và ghi là lựa chọn tồi; D chuyển sang F, nhưng F chỉ kề A, C, D nên không mở thêm được và H vẫn thiếu E, F cũng bị loại; D hết lựa chọn nên bị loại khỏi H; C chuyển sang E, E chọn D, D chọn F, lần này H đã đủ sáu đỉnh và F kề A nên đóng chu trình về A. Phương án "A, F, D, E, C, B, A" và phương án "A, F, C, E, D, B, A" đều hợp lệ về cạnh nhưng khởi đầu bằng F, trong khi từ A thuật toán luôn thử B trước. Phương án "A, F, D, B, E, C, A" cũng mắc lỗi khởi đầu ấy. Phương án "A, B, D, E, C, F, A" chọn D ngay sau B, trong khi láng giềng chưa dùng của B theo chữ cái là C đứng trước D.

Đáp án đúng: "(3)", tức bảng có 41 ở ô 1, 32 ở ô 2, 191 ở ô 3, 14 ở ô 4, 25 ở ô 5 và 21 ở ô 6. Với h(x) = x%10 và dò tuyến tính: 25 vào ô 5, 41 vào ô 1, 14 vào ô 4, 32 vào ô 2; 191 băm về ô 1 đang có 41, dò sang ô 2 có 32, rồi dừng ở ô 3 còn rỗng; 21 cũng băm về ô 1, dò lần lượt ô 2, 3, 4, 5 đều kín và nằm xuống ô 6. "(1)" sai vì nó đưa 191 tới ô 7 và 21 tới ô 6, bỏ trống ô 3 dù ô này còn rỗng đúng lúc chèn 191. "(2)" sai vì xếp 21 vào ô 3 và 191 vào ô 6, kết quả đó chỉ ra nếu đảo thứ tự chèn hai khoá cuối so với đề. "(4)" sai vì đặt 21 ở ô 8 và 191 ở ô 9, một bước nhảy không thuộc dò tuyến tính và để trống cả ba ô 3, 6, 7 ở phía trước.

Đáp án đúng: "(1)". Đó là mảng có y ở ô 0, o ở ô 1, u ở ô 2, ba ô còn lại trống. Mảng vòng sáu ô: nạp H vào ô 0, o vào ô 1, w vào ô 2; ba dấu sao lấy ra cả ba nên hàng đợi rỗng, nhưng con trỏ cuối vẫn đứng sau ô 2 vì phép lấy ra chỉ nhích con trỏ đầu. Nạp tiếp a vào ô 3, r vào ô 4, e vào ô 5, rồi y quay vòng về ô 0, o vào ô 1, u vào ô 2. Ba dấu sao cuối lấy ra a, r, e, nên chỉ còn y, o, u ở ô 0, ô 1, ô 2. Mảng "(2)" đặt y, o, u ở ô 1 tới ô 3, muốn vậy a phải vào ô 4, nghĩa là ba ký tự đầu đã chiếm ô 1 tới ô 3 thay vì ô 0 tới ô 2. Mảng "(3)" đặt y ở ô 4, o ở ô 5, u ở ô 0, tức a vào ô 1 nên cả khối lệch một ô. Mảng "(4)" đặt y ở ô 5, o ở ô 0, u ở ô 1, tức a vào ô 2 nên khối lệch hai ô so với ô 3 mà con trỏ cuối đang chỉ tới.

Đáp án đúng: "doringi". Ở đoạn mã này dấu sao vừa lấy phần tử ra khỏi ngăn xếp vừa in ngay phần tử đó, nên chuỗi in ra là dãy phần tử bị lấy ra. Chạy tay: Good vào rồi hai dấu sao in d và o; Mor vào rồi dấu sao in r; n, i vào rồi hai dấu sao in i và n; n, g vào rồi dấu sao in g; S, i vào rồi dấu sao in i. Ghép lại được d, o, r, i, n, g, i. "donrioo" đặt n trước r, nhưng r đã bị lấy ra bởi dấu sao đứng ngay sau khúc Mor, lúc đó n còn chưa được đẩy vào. "donrioG" mắc cùng chỗ đảo đó và còn kết bằng G, trong khi G nằm tận đáy ngăn xếp và không dấu sao nào lấy tới nó. "donriMG" in thêm cả M và G, hai ký tự vẫn còn nằm trong ngăn xếp khi xâu đã đọc hết, mà đoạn mã này không có vòng in phần còn lại. "GooMorni" là thứ tự các ký tự được đẩy vào chứ không phải thứ tự bị lấy ra.