Trắc nghiệm Kết nối Tin học 9 bài 15: Bài toán tin học

1. Khi phân tích thuật toán, thuật ngữ Big O notation được sử dụng để làm gì?

A. Đo lường chính xác thời gian chạy của thuật toán trên mọi máy tính.

B. Mô tả giới hạn trên của độ phức tạp thời gian hoặc không gian của thuật toán.

C. So sánh số lượng phép toán giữa hai thuật toán khác nhau.

D. Xác định thuật toán nào có nhiều lỗi nhất.

2. Ngôn ngữ lập trình nào thường được sử dụng để mô tả thuật toán một cách dễ hiểu cho con người trước khi chuyển sang mã máy?

A. Assembly Language.

B. Machine Code.

C. Pseudocode (Mã giả).

D. Binary Code.

3. Khi thiết kế thuật toán cho bài toán tính tổng các số tự nhiên từ 1 đến N, phương pháp nào sau đây hiệu quả nhất?

A. Sử dụng vòng lặp for để cộng từng số từ 1 đến N.

B. Sử dụng công thức toán học S = N * (N + 1) / 2.

C. Sử dụng đệ quy để cộng các số.

D. Sử dụng hàm tính tổng có sẵn trong thư viện.

4. Đặc điểm nào sau đây KHÔNG phải là đặc điểm cơ bản của một thuật toán?

A. Tính hữu hạn (Termination).

B. Tính không rõ ràng (Vagueness).

C. Tính đúng đắn (Correctness).

D. Tính hiệu quả (Efficiency).

5. Phát biểu nào sau đây mô tả đúng về điều kiện dừng (stopping condition) trong một thuật toán lặp?

A. Là điều kiện để bắt đầu vòng lặp.

B. Là điều kiện để thoát khỏi vòng lặp và tiếp tục các lệnh sau đó.

C. Là điều kiện để thực hiện lệnh đầu tiên trong vòng lặp.

D. Là điều kiện để thực hiện lệnh cuối cùng trong vòng lặp.

6. Khi phân tích một thuật toán, ký hiệu O(n log n) thường biểu thị điều gì?

A. Thuật toán có số bước cố định bất kể kích thước đầu vào.

B. Số bước của thuật toán tăng theo tỉ lệ thuận với kích thước đầu vào.

C. Số bước của thuật toán tăng theo cấp số nhân với kích thước đầu vào.

D. Số bước của thuật toán tăng theo logarit của kích thước đầu vào, nhân với kích thước đầu vào.

7. Phát biểu nào sau đây mô tả đúng về độ phức tạp không gian (space complexity) của một thuật toán?

A. Là thời gian mà thuật toán cần để chạy.

B. Là ước lượng lượng bộ nhớ mà thuật toán sử dụng theo hàm của kích thước đầu vào.

C. Là số lượng các biến được khai báo trong thuật toán.

D. Là dung lượng của file mã nguồn thuật toán.

8. Một thuật toán sắp xếp các phần tử theo thứ tự tăng dần, ví dụ: [5, 2, 8, 1, 9]. Sau bước đầu tiên của thuật toán sắp xếp nổi bọt (Bubble Sort), mảng có thể trông như thế nào?

A. [2, 5, 1, 8, 9]

B. [2, 5, 8, 1, 9]

C. [5, 2, 1, 8, 9]

D. [1, 2, 5, 8, 9]

9. Khi thiết kế thuật toán, việc lựa chọn cấu trúc dữ liệu phù hợp có ảnh hưởng như thế nào đến hiệu quả của thuật toán?

A. Không ảnh hưởng, chỉ có thuật toán mới quan trọng.

B. Có thể ảnh hưởng đáng kể đến tốc độ thực thi và lượng bộ nhớ sử dụng.

C. Chỉ ảnh hưởng đến cách hiển thị kết quả, không ảnh hưởng đến tốc độ.

D. Chỉ ảnh hưởng đến số lượng dòng code, không ảnh hưởng đến hiệu quả thực tế.

10. Một thuật toán đệ quy (recursive algorithm) là thuật toán mà trong quá trình thực hiện:

A. Nó gọi lại chính nó để giải quyết các bài toán con.

B. Nó chỉ thực hiện một lần duy nhất và dừng lại.

C. Nó sử dụng một vòng lặp vô hạn.

D. Nó thực hiện các phép tính toán học cơ bản.

11. Trong bài toán tìm kiếm, nếu chúng ta cần tìm một phần tử trong một danh sách đã được sắp xếp, thuật toán nào thường hiệu quả hơn?

A. Tìm kiếm tuần tự (Linear Search).

B. Tìm kiếm nhị phân (Binary Search).

C. Tìm kiếm ngẫu nhiên (Random Search).

D. Tìm kiếm theo cấu trúc cây (Tree Search).

12. Trong lập trình, thuật toán được hiểu là gì?

A. Một chuỗi các lệnh máy tính được viết bằng ngôn ngữ lập trình.

B. Một quy trình gồm hữu hạn các bước, được mô tả rõ ràng, dùng để giải quyết một lớp bài toán.

C. Một đoạn mã nguồn được biên dịch và thực thi trực tiếp trên phần cứng.

D. Một tập hợp các câu lệnh lặp lại để xử lý dữ liệu.

13. Yếu tố nào sau đây là quan trọng nhất để đánh giá một thuật toán có hiệu quả hay không?

A. Số lượng dòng lệnh trong mã nguồn.

B. Thời gian thực thi và bộ nhớ sử dụng.

C. Số lượng biến được khai báo.

D. Độ phức tạp của cấu trúc dữ liệu được sử dụng.

14. Phát biểu nào sau đây mô tả đúng về tính hữu hạn của thuật toán?

A. Thuật toán phải chạy vô thời hạn để xử lý hết dữ liệu.

B. Thuật toán phải kết thúc sau một số hữu hạn các bước thực hiện.

C. Thuật toán chỉ cần thực hiện tối đa 100 bước.

D. Thuật toán có thể lặp lại vô hạn các bước tùy theo điều kiện.

15. Phát biểu nào sau đây mô tả đúng về độ phức tạp thời gian (time complexity) của một thuật toán?

A. Là số lượng biến mà thuật toán sử dụng.

B. Là ước lượng số lượng thao tác mà thuật toán thực hiện theo hàm của kích thước đầu vào.

C. Là thời gian thực tế mà thuật toán chạy trên một máy tính cụ thể.

D. Là số lượng dòng code trong thuật toán.

16. Đâu là một ví dụ về bài toán tin học có thể được giải quyết bằng thuật toán?

A. Cảm nhận vẻ đẹp của một bức tranh.

B. Tìm đường đi ngắn nhất giữa hai địa điểm trên bản đồ.

C. Hiểu sâu sắc một tác phẩm văn học.

D. Trải nghiệm một cảm xúc phức tạp.

17. Khi mô tả thuật toán bằng ngôn ngữ tự nhiên, điều gì cần lưu ý để đảm bảo tính rõ ràng?

A. Sử dụng nhiều từ ngữ hoa mỹ và ẩn dụ.

B. Mỗi bước của thuật toán phải được diễn đạt một cách chính xác, không mơ hồ.

C. Chỉ sử dụng các thuật ngữ chuyên ngành phức tạp.

D. Không cần quan tâm đến thứ tự thực hiện các bước.

18. Thuật toán nào sau đây thường được dùng để tìm kiếm trong một danh sách chưa sắp xếp?

A. Tìm kiếm nhị phân (Binary Search).

B. Tìm kiếm tuần tự (Linear Search).

C. Tìm kiếm cây nhị phân cân bằng (Balanced Binary Search Tree).

D. Sắp xếp nổi bọt (Bubble Sort).

19. Khi một thuật toán sử dụng cách tiếp cận chia để trị (Divide and Conquer), quá trình hoạt động của nó thường bao gồm các bước nào?

A. Chia bài toán lớn thành các bài toán con nhỏ hơn, giải các bài toán con đó và kết hợp các lời giải.

B. Thực hiện một chuỗi các bước lặp đi lặp lại cho đến khi đạt được kết quả.

C. Duyệt qua tất cả các khả năng để tìm ra lời giải tốt nhất.

D. Thực hiện các phép tính trực tiếp trên dữ liệu đầu vào mà không chia nhỏ.

20. Trong bài toán sắp xếp, thuật toán QuickSort thường được đánh giá cao về hiệu quả vì lý do gì?

A. Nó luôn thực hiện số lượng phép so sánh cố định, không phụ thuộc vào dữ liệu đầu vào.

B. Nó sử dụng phương pháp chia để trị và thường có độ phức tạp trung bình là O(n log n).

C. Nó chỉ yêu cầu một lượng bộ nhớ rất nhỏ, không phụ thuộc vào kích thước dữ liệu.

D. Nó đơn giản và dễ hiểu hơn mọi thuật toán sắp xếp khác.

21. Trong các cấu trúc dữ liệu, mảng (array) được coi là phù hợp nhất cho việc gì?

A. Lưu trữ dữ liệu có kích thước thay đổi liên tục.

B. Truy cập trực tiếp vào một phần tử dựa trên chỉ số (index) của nó.

C. Lưu trữ dữ liệu không có thứ tự cố định.

D. Thực hiện các phép toán phức tạp trên các phần tử không liền kề.

22. Trong lập trình, vòng lặp (loop) là một cấu trúc điều khiển cho phép:

A. Thực hiện một khối lệnh chỉ một lần duy nhất.

B. Thực hiện một khối lệnh nhiều lần dựa trên một điều kiện hoặc số lần xác định.

C. Ngừng thực thi chương trình ngay lập tức.

D. Nhảy đến một phần khác của chương trình mà không cần điều kiện.

23. Phát biểu nào sau đây là đúng về tính đúng đắn của thuật toán?

A. Thuật toán phải luôn cho kết quả đúng với mọi bộ dữ liệu đầu vào có thể.

B. Thuật toán chỉ cần cho kết quả đúng với một số trường hợp đặc biệt.

C. Tính đúng đắn chỉ quan trọng khi thuật toán chạy nhanh.

D. Thuật toán có thể sai một vài lần nếu nó nhanh.

24. Để tránh tràn bộ nhớ (stack overflow) khi sử dụng thuật toán đệ quy, điều quan trọng nhất cần đảm bảo là:

A. Các lời gọi đệ quy phải có điều kiện dừng rõ ràng.

B. Thuật toán phải sử dụng nhiều biến cục bộ.

C. Mỗi lời gọi đệ quy phải thực hiện ít nhất 100 bước.

D. Không cần quan tâm đến điều kiện dừng, hệ thống sẽ tự xử lý.

25. Nếu một thuật toán có độ phức tạp là O(n^2), điều này có nghĩa là gì khi kích thước đầu vào tăng gấp đôi?

A. Thời gian thực thi sẽ tăng gấp đôi.

B. Thời gian thực thi sẽ tăng gấp bốn lần.

C. Thời gian thực thi sẽ giảm đi một nửa.

D. Thời gian thực thi sẽ không thay đổi.