Câu hỏi: CSI106 - Phần 11: Giải thuật

Đáp án đúng: "Sorting". Sắp xếp là quá trình xếp lại dữ liệu theo giá trị của chúng, theo chiều tăng hay giảm, và nó phổ biến vì nhiều việc khác như tìm nhị phân, phát hiện trùng lặp hay trình bày báo cáo đều dựa trên dữ liệu đã có thứ tự. Việc "Classifying" là gán dữ liệu vào các nhóm theo tiêu chí, kết quả là các lớp chứ không phải một dãy có thứ tự theo giá trị. Việc "Re-structuring" đổi cách tổ chức hay định dạng dữ liệu, không nói gì tới việc so sánh giá trị để xếp chỗ. Việc "Searching" là dò tìm một phần tử theo khoá rồi trả về vị trí của nó, và nó không hề làm thay đổi thứ tự của dữ liệu.

Đáp án đúng: "decision". Cấu trúc quyết định đánh giá một biểu thức điều kiện rồi dựa vào kết quả đúng hoặc sai mà chọn một trong hai nhánh lệnh để thi hành, nên nó đúng là cấu trúc dùng để kiểm tra một điều kiện. Cấu trúc "sequence" chỉ thi hành các lệnh lần lượt từ trên xuống, không có chỗ nào rẽ nhánh. Cấu trúc "repetition" có dùng điều kiện, nhưng điều kiện ở đó dùng để quyết định còn lặp lại khối lệnh nữa hay dừng, khác với việc chọn giữa hai nhánh, và bản chất được định nghĩa của nó là sự lặp lại. Từ "flow" chỉ nói chung về dòng điều khiển của chương trình và không phải một trong ba cấu trúc cơ bản.

Đáp án đúng: "Bubble Sort". Sắp xếp nổi bọt đi dọc dãy, so sánh từng cặp phần tử nằm kề nhau và đổi chỗ chúng nếu sai thứ tự; sau mỗi lượt quét, phần tử lớn nhất trong phần chưa sắp nổi về cuối, đúng như tên gọi. Thuật toán "Quick Sort" chia dãy quanh một phần tử chốt, các phần tử bị đổi chỗ thường nằm xa nhau ở hai phía chốt chứ không kề nhau. Thuật toán "Merge Sort" chia dãy thành nửa, sắp từng nửa rồi trộn hai dãy đã sắp, nó sao chép phần tử sang vùng kết quả thay vì đổi chỗ hai phần tử kề nhau. Thuật toán "Selection Sort" mỗi lượt tìm phần tử nhỏ nhất trong phần còn lại rồi đưa nó về đầu, chỉ một lần đổi chỗ giữa hai vị trí có thể rất xa nhau.

Đáp án đúng: "They all require the same amount of additional memory". Ba thuật toán được nêu đều sắp xếp ngay trên dãy gốc và chỉ cần thêm vài biến phụ để so sánh và đổi chỗ, nên bộ nhớ phụ của cả ba đều là một lượng hằng số không phụ thuộc số phần tử; vì thế không thuật toán nào trong số đó tiết kiệm bộ nhớ hơn hai thuật toán kia. Chọn "Bubble Sort" là sai vì nó chỉ cần một biến tạm để đổi chỗ, đúng bằng mức của hai thuật toán còn lại. Chọn "Selection Sort" cũng sai vì nó chỉ giữ thêm chỉ số của phần tử nhỏ nhất, vẫn là lượng hằng số. Chọn "Insertion Sort" sai tương tự, vì biến giữ phần tử đang được chèn cũng chỉ chiếm một ô nhớ.

Đáp án đúng: "Switch". Cấu trúc này là rẽ nhánh nhiều lựa chọn: máy xét giá trị biểu thức, nhảy vào nhánh khớp rồi chạy một lần và đi ra, không có cơ chế quay lại kiểm điều kiện để lặp. Mục "For" là vòng lặp dùng khi biết trước số lần, có biến đếm, điều kiện dừng và bước nhảy. Mục "While" là vòng lặp kiểm điều kiện trước mỗi lần chạy thân, nên thân có thể không chạy lần nào. Mục "Do-While" cũng là vòng lặp nhưng kiểm điều kiện sau khi chạy thân, bảo đảm thân chạy ít nhất một lần. Ba cấu trúc đó đều có thể quay lại điểm đầu nhiều lần, điểm mà cấu trúc rẽ nhánh nhiều lựa chọn không có.

Đáp án đúng: "Repeatedly comparing adjacent elements and swapping them if they are in the wrong order." Thuật toán này đi dọc danh sách, so sánh từng cặp phần tử đứng cạnh nhau và đổi chỗ chúng nếu thứ tự sai; sau mỗi lượt phần tử lớn nhất trong phần chưa sắp sẽ nổi về cuối, lặp đủ số lượt thì cả danh sách có thứ tự. Mục "Dividing the list into two parts and inserting elements from unsorted to sorted" là cơ chế của sắp xếp chèn, nó lấy một phần tử rồi tìm chỗ đặt vào phần đã sắp. Mục "Finding the smallest element and swapping it to the correct position" là cơ chế của sắp xếp chọn, mỗi lượt chỉ có một phép đổi chỗ sau khi đã tìm ra phần tử nhỏ nhất. Mục "Dividing the list in half and searching" không phải thuật toán sắp xếp, đó là tìm nhị phân, nó còn đòi danh sách phải sắp xếp sẵn.

Đáp án đúng: "Only for small lists, or lists that are not searched often, and are not ordered." Tìm tuần tự duyệt lần lượt từng phần tử cho tới khi gặp giá trị cần tìm hoặc hết danh sách, trung bình phải so sánh khoảng một nửa số phần tử, nên nó chỉ đáng dùng khi danh sách nhỏ, ít phải tìm, hoặc chưa được sắp xếp, vì lúc đó cách nhanh hơn không áp dụng được. Mục "For very large, sorted lists." là trường hợp nên dùng tìm nhị phân, thứ chỉ cần số phép so sánh theo logarit. Mục "When the list is organized hierarchically" ứng với dữ liệu dạng cây, ở đó người ta đi theo đường từ gốc xuống. Mục "When the exact position of the target is known" tự loại mình, biết sẵn vị trí thì truy cập trực tiếp vào chỗ đó, không phải tìm kiếm gì nữa.

Đáp án đúng: "Selection sort". Thuật toán này coi danh sách gồm hai phần, phần đầu đã có thứ tự và phần sau chưa; mỗi lượt nó quét phần chưa sắp để tìm phần tử nhỏ nhất rồi đổi chỗ phần tử đó với phần tử đứng đầu phần chưa sắp, nhờ vậy ranh giới giữa hai phần dịch sang một ô và mỗi lượt chỉ cần đúng một phép đổi chỗ. Mục "Bubble sort" không tìm phần tử nhỏ nhất, nó đổi chỗ liên tục các cặp kề nhau nên một lượt có thể sinh rất nhiều phép đổi. Mục "Insertion sort" cũng chia hai phần nhưng làm ngược chiều: lấy phần tử đầu của phần chưa sắp rồi chèn vào đúng vị trí trong phần đã sắp, phải dịch các phần tử lớn hơn sang chỗ khác. Mục "Binary sort" không phải tên của một thuật toán sắp xếp, cách chia đôi vốn thuộc về tìm kiếm.

Đáp án đúng: "When the data is unsorted". Tìm nhị phân sống nhờ một tiền đề: dữ liệu đã sắp thứ tự, nhờ đó một phép so sánh với phần tử giữa đủ để biết nên bỏ nửa trước hay nửa sau. Dữ liệu chưa sắp xếp thì phép loại nửa đó mất căn cứ, thuật toán có thể bỏ qua đúng phần tử cần tìm. "When the data is sorted" lại chính là điều kiện để thuật toán chạy được. "When the data is in an array" là hoàn cảnh thuận lợi nhất, vì mảng cho nhảy thẳng tới chỉ số giữa trong một bước. "When the data is in a linked list" làm thuật toán chậm đi do phải đi tuần tự mới tới được phần tử giữa, nhưng nếu danh sách đã sắp thứ tự thì kết quả vẫn đúng.

Đáp án đúng: "Using a for loop to iterate over a list". Cấu trúc lặp nghĩa là một nhóm lệnh được thực hiện lại nhiều lần dưới sự kiểm soát của một điều kiện hoặc một dãy giá trị; vòng for đi qua từng phần tử của danh sách đúng là hình ảnh đó. "Assigning a value to a variable" là một lệnh đơn chạy một lần, thuộc cấu trúc tuần tự. "Evaluating a condition once" là cấu trúc quyết định: xét điều kiện rồi rẽ nhánh, không có chuyện quay lại thực hiện tiếp. "Breaking out of a loop" là lệnh thoát khỏi vòng lặp, nó rút bớt số lần lặp đang có chứ bản thân không sinh ra sự lặp nào.

Đáp án đúng: "When stack overflow is a concern". Mỗi lời gọi đệ quy đều đẩy một khung vào ngăn xếp lời gọi để giữ tham số và chỗ quay về; độ sâu lớn làm ngăn xếp cạn và chương trình chết, trong khi bản lặp chỉ giữ trạng thái trong vài biến nên không tốn ngăn xếp. "When solving problems that require backtracking" là chỗ đệ quy có lợi, vì việc quay lui khớp tự nhiên với việc trả về khung gọi trước đó. "When the problem involves tree traversal" cũng vậy: cây vốn được định nghĩa đệ quy nên duyệt bằng đệ quy ngắn và rõ hơn. "When solving problems with divide-and-conquer techniques" chia bài toán thành bài toán con cùng dạng, đúng khuôn mẫu mà đệ quy diễn đạt gọn nhất.

Đáp án đúng: "Binary search divides the search space into halves, while sequential search checks elements one by one". Khác biệt gốc nằm ở cách thu hẹp vùng tìm: mỗi bước của tìm nhị phân loại bỏ một nửa số phần tử còn lại nên số phép so sánh tỉ lệ với logarit kích thước dữ liệu, còn tìm tuần tự xét lần lượt từng phần tử nên chi phí tỉ lệ với số phần tử. Khẳng định "Sequential search requires the data to be sorted in ascending order" nói ngược vấn đề, bởi chính tìm nhị phân mới đòi dữ liệu đã sắp thứ tự, còn tìm tuần tự chạy trên dữ liệu bất kỳ. Khẳng định "Sequential search exhibits greater efficiency and speed compared to binary search" sai vì dữ liệu càng lớn thì lợi thế càng nghiêng về phía chia nửa. Còn "sequential search is specifically designed to work only with arrays" cũng sai: tìm tuần tự dùng được cho cả danh sách liên kết, trong khi tìm nhị phân mới là thuật toán cần truy cập ngẫu nhiên.

Đáp án đúng: "for". Lệnh for là cấu trúc lặp với số lần xác định: nó lần lượt lấy từng phần tử hoặc từng chỉ số của mảng rồi chạy lại thân lệnh cho tới khi đi hết mảng. "if else" chỉ xét một điều kiện rồi chọn một trong hai nhánh và chạy đúng một lần, nên không đi qua được toàn bộ mảng. "switch case" cũng là cấu trúc rẽ nhánh, chỉ chọn nhánh khớp với giá trị của biểu thức rồi kết thúc. "return" kết thúc hàm hiện tại và trả giá trị về nơi gọi, thậm chí làm vòng lặp dừng sớm, chứ không tạo ra sự lặp.

Đáp án đúng: "When the target is found or the end of the list is reached". Tìm kiếm tuần tự so khoá cần tìm với từng phần tử theo thứ tự xuất hiện, nên chỉ có hai lý do để dừng: hoặc đã gặp phần tử trùng khoá, hoặc đã đi hết danh sách mà không gặp và khi đó kết luận khoá không tồn tại. "When the middle of the list is reached" sai vì mốc giữa danh sách là cách làm của tìm kiếm nhị phân, thuật toán chia đôi vùng tìm và chỉ áp dụng được trên danh sách đã sắp. "When largest element of the list is found" sai vì phần tử lớn nhất không có vai trò gì ở đây; danh sách tìm tuần tự có thể chưa sắp nên gặp phần tử lớn nhất cũng không cho biết phần còn lại không chứa khoá. "None of the other answers" sai vì đã có một mô tả đúng điều kiện dừng nên không thể chọn cách phủ định tất cả.

Đáp án đúng: "[-35, -15, -10, 1, 5, 7, 12, 50]". Tìm kiếm nhị phân chỉ chạy đúng khi danh sách đã được sắp thứ tự, vì mỗi bước nó so khoá với phần tử giữa rồi bỏ hẳn một nửa; danh sách được chọn tăng dần đều từ giá trị nhỏ nhất đến giá trị lớn nhất nên điều kiện được thoả. "[-60, 37, 42, -63, 59, 53, -78, 57]" không sắp thứ tự: ngay sau giá trị 42 đã tụt xuống số âm, nên việc loại nửa danh sách sẽ loại mất cả khoá cần tìm. "[3, 1, 2]" cũng không sắp, phần tử đầu lớn hơn hai phần tử đứng sau. "[1, 2, 3, 4, 5, 6, 7, 9, 0]" tăng dần cho tới 9 rồi đột ngột quay về 0 ở cuối; chỉ một chỗ sai thứ tự là đủ làm thuật toán kết luận sai, chẳng hạn khi tìm giá trị 0 nó sẽ bỏ ngay nửa sau.

Đáp án đúng: "An algorithm that calls itself". Thuật toán đệ quy là thuật toán được định nghĩa bằng chính nó: trong lời giải có lời gọi lại chính thuật toán trên dữ liệu nhỏ hơn, cộng thêm một trường hợp cơ sở để dãy lời gọi dừng lại. Tính giai thừa hay duyệt cây là ví dụ quen thuộc. "An algorithm that runs only once" sai vì chạy đúng một lần là mô tả chung của hầu hết lời gọi hàm thông thường, không liên quan tới cách định nghĩa đệ quy. "An algorithm that sorts data" sai vì sắp xếp là một bài toán cụ thể; có thuật toán sắp xếp viết theo lối đệ quy nhưng cũng có thuật toán sắp xếp viết theo lối lặp. "An algorithm that stores data" sai vì lưu dữ liệu là việc của cấu trúc dữ liệu, không phải đặc điểm của một thuật toán.

Đáp án đúng: "Sequence, decision, and repetition". Lập trình có cấu trúc chứng minh rằng mọi thuật toán đều viết được bằng ba khối điều khiển: thực hiện tuần tự, rẽ nhánh theo điều kiện và lặp lại; chỉ cần ba khối này ghép lồng vào nhau là đủ, nhờ đó chương trình không cần lệnh nhảy tuỳ ý và luôn có một đường vào, một đường ra. Phương án "Variables, loops, and conditions" trộn lẫn hai thứ khác loại: biến là nơi chứa dữ liệu, không phải khối điều khiển, nên danh sách này không phải ba cấu trúc chuẩn. Phương án "Functions, arrays, and pointers" liệt kê các tiện ích của ngôn ngữ và cấu trúc dữ liệu, không phải cách điều khiển dòng thi hành. Phương án "Compilation, execution, and debugging" nói về các bước làm việc với chương trình, nằm ngoài bản thân cấu trúc chương trình.

Đáp án đúng: "To locate a specific element within a data set.". Thuật toán tìm kiếm nhận vào một danh sách và một khoá cần tìm, rồi trả lời khoá đó có nằm trong danh sách hay không và nếu có thì ở vị trí nào; bản chất của nó là định vị, chứ không làm thay đổi dữ liệu. Phương án "To call Google's API efficiently." nhầm khái niệm thuật toán với một ứng dụng cụ thể của việc tìm kiếm trên web, và việc gọi giao diện lập trình của một dịch vụ không phải nội dung môn học này bàn tới. Phương án "To perform calculations on a set of data." mô tả thuật toán tính toán hay tổng hợp số liệu, một nhóm việc khác. Phương án "To create new data elements based on existing ones." nói về sinh thêm dữ liệu, trong khi tìm kiếm chỉ đọc danh sách và không thêm phần tử nào.

Đáp án đúng: "Recursive algorithms use more memory due to stack calls.". Mỗi lần gọi đệ quy, máy phải đẩy một bản ghi kích hoạt chứa tham số, biến cục bộ và địa chỉ trở về lên ngăn xếp; độ sâu đệ quy càng lớn thì ngăn xếp càng phình, và nếu quá sâu thì chương trình tràn ngăn xếp, trong khi vòng lặp chỉ dùng một khung duy nhất. Phương án "Recursive algorithms are harder to implement." không đúng nói chung: với bài toán có cấu trúc tự lặp như duyệt cây hay tháp Hà Nội thì bản đệ quy ngắn và sáng hơn bản vòng lặp. Phương án "Recursive algorithms always have higher time complexity." sai ở chữ luôn luôn, vì cùng một thuật toán viết đệ quy hay vòng lặp đều cho cùng độ phức tạp. Phương án "Recursive algorithms cannot solve sorting problems." trái thực tế, bởi sắp xếp trộn và sắp xếp nhanh đều là thuật toán đệ quy.

Đáp án đúng: "It is efficient when searching small or unsorted datasets". Tìm kiếm tuần tự quét lần lượt từng phần tử nên không đòi hỏi dữ liệu phải sắp xếp trước và cũng không cần chuẩn bị gì; với danh sách ngắn hoặc danh sách chưa có thứ tự, chi phí sắp xếp để dùng cách nhanh hơn còn đắt hơn chính việc quét, nên cách này lại là lựa chọn hợp lý. Phương án "It is the fastest search method for large datasets" sai vì số phép so sánh tăng tỉ lệ với số phần tử, chậm hơn hẳn tìm kiếm nhị phân với dữ liệu lớn đã sắp xếp. Phương án "It can only be used on sorted lists" nói ngược đúng ưu thế của nó: không cần sắp xếp mới là điều kiện tự do của tìm kiếm tuần tự. Phương án "It requires dividing the dataset into halves at every step" mô tả tìm kiếm nhị phân, một cách làm khác hẳn.