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

Đáp án đúng: "5". Cây nhị phân đầy đòi mọi nút không phải lá đều có đúng hai con, còn chiều cao 3 với gốc ở mức 1 nghĩa là bắt buộc có nút ở mức 3. Muốn ít nút nhất thì gốc sinh hai con ở mức 2, một trong hai con đó để làm lá còn con kia sinh hai lá ở mức 3, tổng cộng 1 + 2 + 2 = 5 nút và vẫn không nút nào có đúng một con. "4" sai vì trong cây đầy các con luôn sinh theo cặp nên tổng số nút luôn là số lẻ; 4 nút đồng nghĩa có một nút chỉ một con. "6" sai cũng vì tính chẵn lẻ đó, 6 nút không dựng được cây đầy nào. "7" sai vì 7 là số nút nhiều nhất khi cả hai nút ở mức 2 đều sinh hai lá, tức giá trị cực đại chứ không phải cực tiểu mà câu hỏi cần.

Đáp án đúng: "O(log n)". Vòng lặp chỉ đi theo một đường từ gốc xuống, mỗi lần so sánh thì hoặc rẽ trái hoặc rẽ phải, nên số lần lặp nhiều nhất bằng chiều cao cây. Cây AVL giữ hiệu chiều cao hai nhánh của mọi nút trong khoảng từ -1 tới 1, nhờ đó chiều cao bị chặn bởi một hằng số nhân logarit của số nút, và phép tìm tốn thời gian tỉ lệ với log n. Mức "O(n)" đúng cho cây nhị phân tìm kiếm không cân bằng, trường hợp suy biến thành một dây nút giống danh sách liên kết, chính là điều mà ràng buộc AVL ngăn lại. Mức "O(nlog n)" là chi phí của các phép sắp xếp so sánh trên cả n phần tử, ở đây chỉ có một đường đi xuống nên không có thừa số n. Mức "O(n^2)" cần hai vòng lặp lồng nhau trên dữ liệu, mà đoạn mã chỉ có một vòng và trong vòng không có phép lặp nào khác.

Đáp án đúng: "gnoG". Vòng lặp đọc xâu chỉ đẩy ký tự thường vào ngăn xếp, còn mỗi dấu sao lấy một phần tử ra mà không in; phần in nằm ở vòng lặp sau, lấy từ đỉnh xuống đáy. Chạy tay: Good vào thành G, o, o, d, hai dấu sao lấy d và o nên còn G, o; Morn vào thành G, o, M, o, r, n, hai dấu sao lấy n và r nên còn G, o, M, o; i vào rồi ba dấu sao lấy i, o, M nên còn G, o; n và g vào thành G, o, n, g. Vòng in lấy từ đỉnh được g, n, o, G. "gnoM" giữ M trên đỉnh, nghĩa là chỉ dùng hai trong ba dấu sao đứng sau chữ i. "gnro" giữ lại r, nhưng r đã bị lấy ra bởi dấu sao ngay sau khúc Morn. "Gong" là đọc ngăn xếp từ đáy lên đỉnh, tức in theo kiểu vào trước ra trước của hàng đợi thay vì vào sau ra trước của ngăn xếp.

Đáp án đúng: "donrnio". Khác biến thể in ở cuối, ở đây mỗi dấu sao lấy ký tự ở đỉnh ngăn xếp và in ngay, còn sau khi đọc hết từ thì không có vòng xả, nên ký tự còn lại trong ngăn xếp không bao giờ xuất hiện. Chạy tay theo đúng thứ tự ký tự của từ: nạp G, o, o, d, hai dấu sao in d rồi o; nạp M, o, r, n, hai dấu sao in n rồi r; nạp i, n, ba dấu sao in n, i rồi o (chữ o đẩy vào ngay sau M); cuối cùng nạp g nhưng không còn dấu sao nên g cùng G, o, M nằm lại trong ngăn xếp. Màn hình nhận d, o, n, r, n, i, o, đúng bảy ký tự cho bảy dấu sao. "donrnoo" in o trước r trong nhóm M, o, r, n, trái nguyên tắc vào sau ra trước vì r được đẩy vào sau o. "donrniM" và "donrniG" lầm ở dấu sao thứ bảy: lúc đó đỉnh ngăn xếp là chữ o đẩy vào sau M, còn M nằm dưới nó và G nằm dưới cùng.

Đáp án đúng: "The tree is complete but not full.". 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; 35 chỉ có con trái 30; 50 có hai con 45 và 55. Cây full đòi mọi nút có đúng 0 hoặc 2 con, mà 35 có một con duy nhất nên điều kiện này đứt ngay. Cây complete đòi mọi tầng đầy trừ tầng cuối và tầng cuối lấp liên tục từ trái sang: tầng gốc có 40, tầng sau có 25 và 50, tầng tiếp có đủ bốn nút 15, 35, 45, 55, tầng cuối có 10, 20, 30 nằm liền nhau ở ba vị trí trái nhất mà không có chỗ trống chen vào trước chúng, nên complete thoả. Vì vậy "The tree is full but not complete." sai vì nó đảo ngược đúng hai tính chất vừa kiểm; "The tree is both full and complete." sai vì con trái đơn độc của 35 phá điều kiện full; "The tree is neither complete nor full." sai vì tầng cuối không hề có lỗ hổng nào trước nút 30.

Đáp án đúng: "30, 5, 40, 10, 35, 25, 20". Cây có gốc 30, nhánh trái 15 với hai con 5 và 25, dưới 5 là con phải 10, dưới 25 là con trái 20, nhánh phải 40 với con trái 35. Xoá 15 bằng cách nối thì nhánh trái của nó lên thế chỗ và nhánh phải được treo vào nút cực phải của nhánh trái: đi từ 5 sang 10, mà 10 không có con phải nên 10 nhận nút 25 làm con phải; sau đó 5 thành con trái của 30. Cây mới có 30 ở mức một; 5 và 40 ở mức hai; 10 là con phải của 5 và 35 là con trái của 40 ở mức ba; 25 ở mức bốn; 20 ở mức năm. Duyệt theo chiều rộng cho 30, 5, 40, 10, 35, 25, 20. Dãy "30, 5, 40, 10, 25, 35, 20" treo 25 ngay dưới 5, nhưng chỗ trống hợp lệ là dưới nút cực phải 10, nếu không 5 sẽ có hai con phải. Dãy "30, 25, 40, 5, 20, 10, 35" đưa 25 lên thay 15, đó là lối sao chép với nút kế vị chứ không phải phép nối. Dãy "30, 5, 40, 25, 35, 10, 20" đặt 25 ở mức ba và đẩy 10 xuống mức bốn, đảo ngược quan hệ cha con vì 10 là con của 5 còn 25 phải nằm dưới 10.

Đáp án đúng: "simple graph". Đồ thị đơn là đồ thị không có khuyên, tức cạnh nối một đỉnh với chính nó, và không có cạnh song song, tức hai cạnh cùng nối một cặp đỉnh; đó đúng hai điều kiện mà câu hỏi nêu. Nhờ vậy quan hệ kề biểu diễn được bằng ma trận 0 và 1, mỗi cặp đỉnh ứng với nhiều nhất một cạnh. Phương án "multigraph" chính là loại cho phép cạnh song song, nên vi phạm điều kiện cấm cạnh song song. Phương án "pseudograph" nới thêm một bước nữa, cho phép cả khuyên lẫn cạnh song song, tức vi phạm cả hai điều kiện. Phương án "connected graph" nói về tính liên thông, rằng giữa hai đỉnh bất kỳ đều có đường đi; một đồ thị liên thông vẫn có thể chứa khuyên hoặc cạnh song song, và ngược lại một đồ thị đơn có thể gồm nhiều thành phần rời nhau, nên hai khái niệm này độc lập với nhau.

Đáp án đúng: "Undo sequence in a text editor.". Chuỗi hoàn tác cần lấy ra đúng thao tác vừa làm gần nhất, tức vào sau ra trước, nên cấu trúc tự nhiên là ngăn xếp; nếu dùng hàng đợi thì lệnh hoàn tác đầu tiên lại gỡ thao tác cũ nhất, sai hẳn ngữ nghĩa. "Store a waiting list of printing jobs." là ứng dụng kinh điển của hàng đợi, bản in nào gửi trước thì in trước. "Multi-programming." cũng dùng hàng đợi, hệ điều hành xếp các tiến trình chờ bộ xử lý theo thứ tự đến để cấp lượt công bằng. "Auxiliary data structure for algorithms." đúng vì nhiều thuật toán lấy hàng đợi làm cấu trúc phụ, rõ nhất là duyệt theo bề rộng trên cây và đồ thị, nơi thứ tự vào ra quyết định việc thăm hết mức này mới sang mức sau.

Đáp án đúng: "4B4U3B2U5B2U". Mã hoá theo loạt đọc chuỗi thành từng đoạn 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 bốn B, bốn U, ba B, hai U, năm B, hai U, cộng lại đúng 20 ký tự ban đầu. Chuỗi "4B4U3B2U5B" dừng ở loạt năm B và bỏ mất hai U 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 "4B4U3B2U5B2UU" ghi loạt cuối thành 2UU, vừa nêu số lần vừa viết thừa một chữ U, giải mã lại sẽ cho ba U. Chuỗi "B4U4B3U2B5UU2" đặt số sau ký tự một cách không nhất quán và kết thúc bằng UU2, nên đọc theo khuôn số đứng trước ký tự thì nó không khôi phục được thông điệp gốc.

Đáp án đúng: "ABBCD". Cây cho mã A bằng 1, B bằng 00, C bằng 010 và D bằng 011, vì từ gốc nhánh 1 tới ngay lá A, nhánh 0 rồi 0 tới lá B, còn nhánh 0 rồi 1 dẫn tới nút trong cuối với 0 cho C và 1 cho D. Giải mã 10000010011 bằng cách đi từ gốc và cắt mỗi khi tới lá: 1 cho A, 00 cho B, 00 cho B, 010 cho C, 011 cho D, vừa hết chuỗi mười một bit. "ABBDC" đọc 011 trước 010, nhưng sau hai chữ B phần còn lại là 010011 mà ba bit đầu của nó là 010 nên C phải ra trước. "ABCBD" đòi mã C ngay sau chữ B đầu, trong khi lúc đó ba bit tiếp theo là 000, chỉ khớp với một chữ B nữa. "ABCDB" cũng cần C quá sớm và còn kết thúc bằng mã của B, trong khi ba bit cuối của chuỗi là 011, đúng bằng mã của D.