15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 8: Lập trình một số thuật toán sắp xếp có đáp án
15 câu hỏi
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Thuật toán sắp xếp nào được gọi là sắp xếp tại chỗ?
Sắp xếp nổi bọt
Sắp xếp chèn tuyến tính
Sắp xếp nhanh (Quick Sort)
Tất cả các thuật toán trên
Đáp án: D
Giải thích: Tất cả các thuật toán nêu trên đều có thể được thực hiện theo cách sắp xếp tại chỗ, tức là không sử dụng một mảng khác để lưu trữ kết quả, mà chỉ thay đổi vị trí của các phần tử trong mảng ban đầu.
Mục đích của thuật toán sắp xếp nổi bọt là gì?
Tìm kiếm phần tử lớn nhất trong dãy
Loại bỏ các nghịch thể trong dãy số
Đếm số phần tử trong dãy
Tăng kích thước mảng
Đáp án: B
Giải thích: Thuật toán sắp xếp nổi bọt (Bubble Sort) làm việc bằng cách so sánh và đổi chỗ các cặp phần tử liền kề để loại bỏ nghịch thể cho đến khi dãy được sắp xếp đúng thứ tự.
Trong thuật toán sắp xếp chèn tuyến tính, khi nào thì dãy con được coi là có thứ tự?
Khi dãy con có một phần tử
Khi dãy con có ít nhất hai phần tử
Khi dãy con đã được sắp xếp hoàn toàn
Khi dãy con không có phần tử nào
Đáp án: A
Giải thích: Dãy con có một phần tử luôn được coi là có thứ tự, vì không có phần tử nào khác để so sánh
Trong thuật toán sắp xếp nổi bọt, điều gì sẽ xảy ra nếu trong một vòng lặp không có bất kỳ lần đổi chỗ nào?
Thuật toán tiếp tục chạy mãi mãi
Thuật toán dừng lại vì dãy đã được sắp xếp
Thuật toán quay lại vòng lặp trước đó
Thuật toán chỉ sắp xếp một phần của dãy
Đáp án: B
Giải thích: Nếu không có bất kỳ lần đổi chỗ nào trong một vòng lặp, điều đó có nghĩa là dãy đã được sắp xếp và thuật toán sẽ dừng lại.
Thuật toán nào sau đây không phải là một thuật toán sắp xếp?
Sắp xếp nổi bọt
Sắp xếp chèn tuyến tính
Sắp xếp chọn (Selection Sort)
Tìm kiếm tuần tự (Linear Search
Đáp án: D
Giải thích: Tìm kiếm tuần tự là một phương pháp tìm kiếm phần tử trong mảng, không phải là một thuật toán sắp xếp.
Trong thuật toán sắp xếp chèn tuyến tính, phần tử nào sẽ được chèn vào dãy đã được sắp xếp?
Phần tử nhỏ nhất
Phần tử lớn nhất
Phần tử tại vị trí đầu tiên của dãy
Phần tử hiện tại mà đang được xem xét
Đáp án: D
Giải thích: Trong thuật toán sắp xếp chèn tuyến tính, phần tử đang được xem xét sẽ được chèn vào vị trí thích hợp trong dãy đã được sắp xếp.
Tính chất nào sau đây là đúng về thuật toán sắp xếp nổi bọt?
Nó có độ phức tạp thời gian O(n log n)
Nó không có khả năng sắp xếp tại chỗ
Nó có thể không hiệu quả với dãy số lớn
Nó không thể xử lý số âm
Đáp án: C
Giải thích: Thuật toán sắp xếp nổi bọt không hiệu quả với dãy số lớn do độ phức tạp thời gian của nó là O(n^2).
Khi sử dụng hàm sorted() trong Python, kết quả sẽ là gì?
Dãy số sẽ được sắp xếp tại chỗ
Hàm trả về một dãy mới đã được sắp xếp
Dãy số sẽ bị xóa
Hàm không làm gì cả
Đáp án: B
Giải thích: Hàm sorted() trong Python tạo ra và trả về một dãy mới với các phần tử đã được sắp xếp, trong khi dãy cũ vẫn không thay đổi.
Tại sao việc sắp xếp dữ liệu là quan trọng trong tin học?
Để làm cho dữ liệu đẹp hơn
Để dễ dàng tìm kiếm và truy xuất thông tin
Để giảm kích thước của dữ liệu
Để bảo vệ dữ liệu khỏi bị mất
Đáp án: B
Giải thích: Sắp xếp dữ liệu giúp cho việc tìm kiếm và truy xuất thông tin trở nên nhanh chóng và hiệu quả hơn.
Nghịch thể trong một dãy số được định nghĩa như thế nào?
Hai phần tử có cùng giá trị
Hai phần tử có thứ tự không đúng
Hai phần tử có giá trị khác nhau
Hai phần tử ở cùng một vị trí
Đáp án: B
Giải thích: Nghịch thể là hai phần tử mà thứ tự của chúng không đúng theo tiêu chí sắp xếp (ví dụ, nếu a > b nhưng a ở trước b trong dãy).
Khi nào thuật toán sắp xếp nổi bọt (Bubble Sort) được cho là đã hoàn thành?
a) Khi không còn cặp phần tử nào là nghịch thế.
b) Khi tất cả các phần tử trong dãy đều bằng nhau.
c) Khi không xảy ra bất kỳ thao tác đổi chỗ nào trong một vòng lặp.
d) Khi đã thực hiện đủ n vòng lặp.
a) Sai. Dù không còn nghịch thế, thuật toán có thể chưa hoàn thành nếu vẫn cần kiểm tra các vòng lặp tiếp theo.
b) Sai. Việc tất cả các phần tử bằng nhau không phải là điều kiện cần thiết để thuật toán hoàn thành.
c) Đúng. Nếu trong một vòng lặp không xảy ra bất kỳ thao tác đổi chỗ nào, có nghĩa là dãy đã được sắp xếp và thuật toán hoàn thành.
d) Sai. Việc thực hiện đủ n vòng lặp không đảm bảo rằng dãy đã được sắp xếp, có thể cần ít hơn n vòng lặp nếu dãy đã sắp xếp từ trước.
Thuật toán sắp xếp chèn (Insertion Sort) hoạt động như thế nào khi chèn một phần tử vào dãy đã sắp xếp?
a) Nó so sánh phần tử với các phần tử trong dãy và di chuyển chúng sang trái cho đến khi tìm thấy vị trí thích hợp.
b) Nó thêm phần tử vào cuối dãy và sắp xếp lại toàn bộ dãy.
c) Nó chỉ thay đổi vị trí của phần tử mà không cần so sánh với các phần tử khác.
d) Nó sử dụng một dãy tạm thời để lưu trữ các phần tử trong khi sắp xếp.
a) Đúng. Thuật toán sắp xếp chèn sẽ so sánh phần tử mới với các phần tử đã được sắp xếp, di chuyển các phần tử lớn hơn sang phải để tạo khoảng trống cho phần tử mới.
b) Sai. Thuật toán không sắp xếp lại toàn bộ dãy; nó chỉ chèn phần tử vào vị trí thích hợp trong dãy đã sắp.
c) Sai. Thuật toán luôn cần so sánh phần tử với các phần tử khác để xác định vị trí chèn.
d) Sai. Sắp xếp chèn không sử dụng dãy tạm thời mà thực hiện trên dãy ban đầu.
Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động như thế nào để sắp xếp một dãy số?
Đáp án:Thuật toán sắp xếp nổi bọt so sánh từng cặp phần tử liền kề trong dãy và đổi chỗ chúng nếu chúng ở sai thứ tự. Quá trình này được lặp lại cho đến khi không còn cặp phần tử nào cần đổi chỗ, nghĩa là dãy đã được sắp xếp.
Giải thích:Ý tưởng của thuật toán là "nổi bọt" các phần tử lớn hơn lên cuối dãy. Sau mỗi vòng lặp, phần tử lớn nhất trong dãy sẽ được chuyển tới vị trí cuối cùng, do đó không cần phải xem xét lại nó trong các vòng lặp tiếp theo. Điều này giúp giảm số lượng so sánh và đổi chỗ cần thiết, làm cho thuật toán có thể dừng lại sớm hơn khi dãy đã được sắp xếp.
Khi nào thì thuật toán sắp xếp tại chỗ được sử dụng và nó khác gì với thuật toán sắp xếp không tại chỗ?
Đáp án:Thuật toán sắp xếp tại chỗ được sử dụng khi không cần thêm một mảng khác để chứa kết quả sắp xếp, mà chỉ cần thực hiện các thao tác đổi chỗ giữa các phần tử trong dãy ban đầu. Ngược lại, thuật toán sắp xếp không tại chỗ sẽ sử dụng một mảng khác để lưu trữ kết quả.
Giải thích:Sắp xếp tại chỗ giúp tiết kiệm bộ nhớ, điều này rất quan trọng khi làm việc với các dãy dữ liệu lớn. Các thuật toán như Bubble Sort và Insertion Sort thường được thực hiện theo cách này, trong khi một số thuật toán như Merge Sort cần một mảng phụ để hoàn thành việc sắp xếp.
Tại sao sắp xếp là một thao tác quan trọng trong lập trình và xử lý dữ liệu?
Đáp án: Sắp xếp giúp tổ chức lại dữ liệu theo thứ tự cụ thể, từ đó hỗ trợ cho các thao tác tìm kiếm nhanh hơn và dễ dàng hơn trong việc phân tích dữ liệu.
Giải thích: Khi dữ liệu được sắp xếp, các thuật toán tìm kiếm như tìm kiếm nhị phân có thể được áp dụng, giúp giảm thời gian tìm kiếm từ O(n) xuống O(log n). Ngoài ra, sắp xếp cũng giúp cho việc trình bày dữ liệu dễ dàng hơn, như trong các bảng điểm hay danh sách sản phẩm, làm cho người dùng có thể nhanh chóng tìm kiếm và phân tích thông tin hơn.
