Câu 1
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch(A, K) là:
Đáp án và lời giải
Đáp án: B
Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25 (có đáp án): Thực hành xác định độ phức tạp thời gian thuật toán
Xem trước: đọc nhanh mọi câu dạng chữ, chưa tính giờ, chưa hiện đáp án.
Luyện tập: chọn đáp án là biết đúng sai ngay, kèm lời giải.
Thi thử: nộp bài mới chấm điểm và hiện lời giải.
Luyện tập: chọn đáp án là biết đúng sai ngay, kèm lời giải.
Thi thử: nộp bài mới chấm điểm và hiện lời giải.
Câu 2
Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort(A) là:
Đáp án và lời giải
Đáp án: C
Câu 3
Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt BubbleSort(A) là:
Đáp án và lời giải
Đáp án: B
Câu 4
Đối với thuật toán LinearSearch(A, K), thời gian tính toán trong trường hợp tốt nhất là:
Đáp án và lời giải
Đáp án: C
Câu 5
Độ phức tạp thời gian của hàm Mystery(n) với các vòng lặp lồng nhau từ i đến j và j đến k là:
Đáp án và lời giải
Đáp án: C
Câu 6
Nếu thời gian thực hiện thuật toán sắp xếp chọn là 1 giây, giá trị lớn nhất của n sẽ là:
Đáp án và lời giải
Đáp án: D
Câu 7
Hàm func(A) với hai vòng lặp lồng nhau chạy từ 0 đến n-1, thực hiện một phép so sánh mỗi lần duyệt, có độ phức tạp là:
Đáp án và lời giải
Đáp án: C
Câu 8
Trong các thuật toán tìm kiếm tuần tự, thời gian thực hiện tối đa sẽ là bao nhiêu đối với mảng kích thước n?
Đáp án và lời giải
Đáp án: A
Câu 9
Khi SelectionSort(A) thực hiện một phép đổi chỗ tại dòng cuối, phép tính này sẽ tốn:
Đáp án và lời giải
Đáp án: C
Câu 10
Độ phức tạp thời gian của BubbleSort trong trường hợp tốt nhất khi mảng đã sắp xếp là:
Đáp án và lời giải
Đáp án: A
Câu 11
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch(A, K) là gì?
- a)O(1)
- b)O(logn)
- c)O(n)O(n)O(n)
- d)O(n2)O(n^2)O(n2)
Đáp án và lời giải
Đáp án: a) Sai; b) Sai; c) Đúng; d) Sai
Câu 12
Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort(A) là gì?
- a)O(1)O(1)O(1)
- b)O(n)O(n)O(n)
- c)O(nlogn)
- d)O(n2)O(n^2)O(n2)
Đáp án và lời giải
Đáp án: a) Sai; b) Sai; c) Sai; d) Đúng
Câu 13
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch là gì và tại sao?
Đáp án và lời giải
Đáp án: O(n) Giải thích: Thuật toán tìm kiếm tuần tự LinearSearch duyệt qua toàn bộ mảng để tìm kiếm phần tử cần tìm. Trong trường hợp xấu nhất (khi phần tử không tồn tại trong mảng), thuật toán phải thực hiện n phép so sánh, với n là kích thước của mảng. Vì vậy, độ phức tạp thời gian của thuật toán là O(n), nghĩa là tuyến tính theo kích thước của mảng.
Câu 14
Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort là gì và tại sao?
Đáp án và lời giải
Đáp án: O(n²) Giải thích: Thuật toán sắp xếp chọn SelectionSort hoạt động bằng cách tìm phần tử nhỏ nhất trong phần mảng chưa được sắp xếp và hoán đổi nó vào vị trí đúng trong mảng đã sắp xếp. Trong mỗi lần lặp, thuật toán cần duyệt qua phần còn lại của mảng để tìm phần tử nhỏ nhất, dẫn đến số phép tính tăng lên theo bình phương của n. Vì vậy, độ phức tạp thời gian của thuật toán là O(n²), đặc biệt khi kích thước mảng lớn.
Câu 15
Giả sử mỗi phép tính tốn một micro giây, giá trị lớn nhất của n mà thuật toán tìm kiếm tuần tự có thể thực hiện trong một giây là bao nhiêu?
Đáp án và lời giải
Đáp án: 1.000.000 Giải thích: Vì mỗi phép tính tốn một micro giây và có 1.000.000 micro giây trong một giây, thuật toán LinearSearch có thể thực hiện tối đa cho n = 1.000.000 phần tử trong một giây. Điều này dựa trên độ phức tạp O(n), nghĩa là thuật toán cần thực hiện n phép tính, tương đương với số phần tử trong mảng.