Câu 1
Độ phức tạp thời gian của thuật toán được xác định bởi yếu tố nào?
Đáp án và lời giải
Đáp án: A
Trắc nghiệm Tin học 11 Cánh diều Bài 5 (có đáp án): Đánh giá 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 tuyến tính được ký hiệu là gì?
Đáp án và lời giải
Đáp án: C
Câu 3
Phép toán nào được coi là phép toán sơ cấp?
Đáp án và lời giải
Đáp án: A
Câu 4
Thuật toán nào sau đây có độ phức tạp thời gian hằng số?
Đáp án và lời giải
Đáp án: B
Câu 5
Khi ước lượng độ phức tạp thời gian của thuật toán, quy tắc nào được áp dụng?
Đáp án và lời giải
Đáp án: B
Câu 6
Trong trường hợp nào thuật toán có thể có độ phức tạp thời gian tuyến tính?
Đáp án và lời giải
Đáp án: C
Câu 7
Phép toán nào không được coi là sơ cấp?
Đáp án và lời giải
Đáp án: B
Câu 8
Cách nào được coi là ước lượng làm giả thêm?
Đáp án và lời giải
Đáp án: D
Câu 9
Khi nào độ phức tạp thời gian của thuật toán là O(n^2)?
Đáp án và lời giải
Đáp án: B
Câu 10
Đặc điểm nào sau đây không thuộc về độ phức tạp thời gian hằng số?
Đáp án và lời giải
Đáp án: D
Câu 11
Thuật toán nào sau đây có độ phức tạp thời gian hằng số?
- a)Tính tổng dãy số bằng cách cộng dồn từng số.
- b)Tính tổng dãy số bằng công thức tính tổng cấp số cộng
- c)Tìm kiếm một phần tử trong danh sách đã sắp xếp bằng cách sử dụng thuật toán tìm kiếm nhị phân.
- d)Sắp xếp một dãy số bằng thuật toán sắp xếp nổi bọt (bubble sort).
Đáp án và lời giải
Đáp án: a) Sai; b) Đúng; c) Sai; d) Sai
Câu 12
Cách nào dưới đây có độ phức tạp thời gian tuyến tính?
- a)Tìm số lớn nhất trong dãy số bằng cách so sánh từng cặp.
- b)Tính giai thừa của một số nguyên n bằng đệ quy.
- c)Sắp xếp một dãy số bằng thuật toán Quick Sort.
- d)Tìm kiếm một số trong dãy số không sắp xếp bằng cách lặp qua từng phần tử.
Đáp án và lời giải
Đáp án: a) Đúng; b) Sai; c) Sai; d) Đúng
Câu 13
Tại sao cần phải ước lượng độ phức tạp thời gian của một thuật toán?
Đáp án và lời giải
Đáp án: Để so sánh hiệu quả của các thuật toán khác nhau. Giải thích: Độ phức tạp thời gian giúp lập trình viên xác định được thời gian thực hiện và tài nguyên mà thuật toán cần, từ đó lựa chọn thuật toán phù hợp nhất cho bài toán cụ thể. Điều này đặc biệt quan trọng khi xử lý lượng dữ liệu lớn hoặc khi thời gian thực hiện là yếu tố quyết định trong ứng dụng.
Câu 14
Thế nào là độ phức tạp thời gian hằng số?
Đáp án và lời giải
Đáp án: Độ phức tạp thời gian hằng số là khi số phép toán cần thực hiện không phụ thuộc vào kích thước dữ liệu đầu vào. Giải thích: Thuật toán có độ phức tạp thời gian hằng số thực hiện một số lượng phép toán cố định, không tăng theo kích thước n. Ví dụ, nếu một thuật toán chỉ cần thực hiện ba phép toán để cho ra kết quả, thì nó có độ phức tạp thời gian hằng số T(n) = 3, tức là O(1).
Câu 15
Độ phức tạp thời gian tuyến tính có ý nghĩa gì trong việc đánh giá thuật toán?
Đáp án và lời giải
Đáp án: Độ phức tạp thời gian tuyến tính có nghĩa là số phép toán thực hiện tỷ lệ thuận với kích thước đầu vào. Giải thích: Khi một thuật toán có độ phức tạp thời gian tuyến tính, điều này cho thấy rằng thời gian thực hiện sẽ tăng lên theo từng đơn vị kích thước dữ liệu. Ví dụ, nếu một thuật toán phải kiểm tra từng phần tử trong danh sách để tìm một giá trị cụ thể, thì số phép toán sẽ tương ứng với số lượng phần tử trong danh sách. Nếu danh sách có n phần tử, thì số phép toán sẽ là n, ký hiệu là T(n) = n, tức là O(n).