Tính toán và kiểm định các thuật toán sắp xếp. Xét về các
Tính toán và kiểm định các thuật toán sắp xếp. Xét về các thuật toán sắp xếp thông dụng áp dụng lên một mảng ban đầu $a = [4, 2, 7, 1, 5]$:
| Đúng | Sai | |
|---|---|---|
| a) Khi tiến hành chạy lượt đầu tiên của Sắp xếp nổi bọt (Bubble Sort), phần tử lớn nhất mang giá trị 7 chắc chắn sẽ dạt xuống nằm ở cuối mảng. | ||
| b) Nếu sử dụng Sắp xếp chọn (Selection Sort), lượt chạy đầu tiên sẽ tự động đổi chỗ phần tử nhỏ nhất số 1 (chỉ số 3) với phần tử đang đứng đầu là số 4 (chỉ số 0). | ||
| c) Nếu xét về trường hợp tốt, Sắp xếp chèn (Insertion Sort) với một mảng đã được sắp xếp sẵn từ trước sẽ sở hữu độ phức tạp tối ưu $O(n)$. | ||
| d) Cả ba thuật toán sơ đẳng như Sắp xếp nổi bọt (Bubble Sort), Sắp xếp chọn (Selection Sort), và Sắp xếp chèn (Insertion Sort) đều có độ phức tạp về mặt thời gian tại trường hợp tệ nhất (Worst-case) là $O(n^2)$. |
Đáp án đúng là: Đ; Đ; Đ; Đ
Quảng cáo
Bubble Sort: So sánh cặp phần tử kề nhau và hoán đổi nếu chúng sai thứ tự. Sau mỗi lượt, phần tử lớn nhất của đoạn chưa sắp xếp sẽ "nổi" về cuối.
Selection Sort: Tìm phần tử nhỏ nhất trong dãy chưa sắp xếp và đổi chỗ nó với phần tử đầu tiên của dãy đó.
Insertion Sort: Duyệt từng phần tử và chèn nó vào vị trí thích hợp trong đoạn đã sắp xếp phía trước. Ở trường hợp mảng đã có thứ tự, nó chỉ thực hiện các phép so sánh mà không cần hoán đổi/dời chỗ.
Độ phức tạp: Cả 3 thuật toán đều sử dụng 2 vòng lặp lồng nhau trong trường hợp xấu nhất, dẫn đến số phép tính tỉ lệ với $n^2$.
Đáp án cần chọn là: Đ; Đ; Đ; Đ
Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí
>> 2K8 Chú ý! Lộ Trình Sun 2026 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi 26+ TN THPT, 90+ ĐGNL HN, 900+ ĐGNL HCM, 70+ ĐGTD - Click xem ngay) tại Tuyensinh247.com.Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, luyện thi theo 3 giai đoạn: Nền tảng lớp 12, Luyện thi chuyên sâu, Luyện đề đủ dạng đáp ứng mọi kì thi.
 |
 |
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
