Trắc nghiệm Tin học 11 Kết nối tri thức Bài 19: Bài toán tìm kiếm - Đề 01 bao gồm nhiều câu hỏi hay, bám sát chương trình. Cùng làm bài tập trắc nghiệm ngay.
Câu 1: Trong bài toán tìm kiếm, phát biểu nào sau đây mô tả đúng nhất mục tiêu của thuật toán tìm kiếm?
- A. Sắp xếp dữ liệu đầu vào theo một thứ tự nhất định.
- B. Tính toán số lượng phần tử trong tập dữ liệu.
- C. Loại bỏ các phần tử trùng lặp khỏi tập dữ liệu.
- D. Xác định vị trí của một phần tử cụ thể (khóa tìm kiếm) trong một tập dữ liệu cho trước.
Câu 2: Xét một danh sách các số nguyên chưa được sắp xếp. Thuật toán tìm kiếm nào sau đây đảm bảo tìm thấy phần tử mục tiêu nếu nó tồn tại trong danh sách, nhưng có thể có hiệu suất kém nhất trong trường hợp xấu nhất?
- A. Tìm kiếm tuần tự (Sequential Search)
- B. Tìm kiếm nhị phân (Binary Search)
- C. Tìm kiếm nội suy (Interpolation Search)
- D. Tìm kiếm theo chiều rộng (Breadth-First Search)
Câu 3: Điều kiện tiên quyết bắt buộc nào sau đây cần được đáp ứng để có thể áp dụng hiệu quả thuật toán tìm kiếm nhị phân?
- A. Dữ liệu phải là số nguyên dương.
- B. Kích thước của tập dữ liệu phải nhỏ hơn một ngưỡng nhất định.
- C. Dữ liệu phải được sắp xếp theo một thứ tự nhất định (tăng dần hoặc giảm dần).
- D. Các phần tử trong dữ liệu phải là duy nhất (không có phần tử trùng lặp).
Câu 4: Trong thuật toán tìm kiếm nhị phân, nếu tại mỗi bước, phạm vi tìm kiếm giảm đi một nửa, thì số bước tìm kiếm tối đa trong trường hợp xấu nhất cho một danh sách có kích thước N sẽ tỉ lệ với:
- A. N
- B. log₂(N)
- C. N²
- D. √N
Câu 5: Cho danh sách số đã được sắp xếp: A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Sử dụng thuật toán tìm kiếm nhị phân để tìm kiếm số 23. Hỏi số lần so sánh cần thực hiện là bao nhiêu?
Câu 6: Xét bài toán tìm kiếm một cuốn sách trong thư viện. Nếu thư viện không có hệ thống sắp xếp sách theo bất kỳ trật tự nào, thì phương pháp tìm kiếm nào sau đây sẽ tương tự như thuật toán tìm kiếm tuần tự?
- A. Hỏi thủ thư để được chỉ dẫn đến khu vực có thể chứa cuốn sách.
- B. Duyệt qua từng kệ sách, từ đầu đến cuối, cho đến khi tìm thấy cuốn sách.
- C. Sử dụng bảng chỉ mục của thư viện để xác định vị trí cuốn sách.
- D. Tìm kiếm ngẫu nhiên ở các kệ sách khác nhau cho đến khi tìm thấy.
Câu 7: Trong trường hợp nào thì thuật toán tìm kiếm tuần tự có thể hiệu quả hơn thuật toán tìm kiếm nhị phân?
- A. Khi kích thước của tập dữ liệu rất lớn.
- B. Khi dữ liệu đã được sắp xếp.
- C. Khi cần tìm kiếm phần tử lớn nhất hoặc nhỏ nhất.
- D. Khi danh sách dữ liệu nhỏ và không được sắp xếp.
Câu 8: Một ứng dụng quản lý sinh viên cần thực hiện tìm kiếm thông tin sinh viên dựa trên mã số sinh viên. Biết rằng mã số sinh viên được gán ngẫu nhiên và không theo thứ tự nào. Thuật toán tìm kiếm nào phù hợp nhất để sử dụng trong trường hợp này?
- A. Tìm kiếm tuần tự
- B. Tìm kiếm nhị phân
- C. Tìm kiếm nội suy
- D. Cả tìm kiếm nhị phân và tìm kiếm nội suy đều phù hợp
Câu 9: Giả sử bạn có một cuốn từ điển được sắp xếp theo thứ tự bảng chữ cái. Khi bạn muốn tìm nghĩa của một từ, bạn thường mở từ điển ở khoảng giữa, sau đó tùy thuộc vào từ bạn tìm kiếm ở trước hay sau trang bạn mở, bạn sẽ tiếp tục tìm kiếm trong nửa trước hoặc nửa sau. Phương pháp tìm kiếm này tương tự với thuật toán nào trong tin học?
- B. Tìm kiếm nhị phân
- C. Tìm kiếm theo chiều sâu
- D. Tìm kiếm theo chiều rộng
Câu 10: Trong ngôn ngữ lập trình Python, phương thức `index()` của list thực hiện loại tìm kiếm nào để xác định vị trí của một phần tử?
- A. Tìm kiếm tuần tự
- B. Tìm kiếm nhị phân (nếu list đã sắp xếp)
- C. Tìm kiếm ngẫu nhiên
- D. Tìm kiếm tuyến tính có điều kiện
Câu 11: Cho danh sách A = [7, 2, 9, 5, 1, 8, 4, 3, 6]. Nếu sử dụng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp danh sách này theo thứ tự tăng dần, thì sau hai lượt duyệt đầu tiên, danh sách sẽ trở thành:
- A. [1, 2, 3, 4, 5, 6, 7, 8, 9]
- B. [2, 7, 5, 1, 8, 4, 3, 6, 9]
- C. [2, 5, 7, 1, 4, 3, 6, 8, 9]
- D. [7, 2, 9, 5, 1, 8, 4, 3, 6]
Câu 12: Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình và trường hợp xấu nhất đều là O(n log n), được coi là hiệu quả cho các tập dữ liệu lớn?
- A. Sắp xếp nổi bọt (Bubble Sort)
- B. Sắp xếp trộn (Merge Sort)
- C. Sắp xếp chèn (Insertion Sort)
- D. Sắp xếp chọn (Selection Sort)
Câu 13: Phát biểu nào sau đây mô tả đúng nhất về thuật toán sắp xếp chèn (Insertion Sort)?
- A. Chia danh sách thành các danh sách con, sắp xếp từng danh sách con rồi trộn lại.
- B. Liên tục đổi chỗ các cặp phần tử liền kề nếu chúng không đúng thứ tự.
- C. Xây dựng danh sách đã sắp xếp bằng cách chèn lần lượt từng phần tử từ danh sách chưa sắp xếp vào đúng vị trí.
- D. Chọn phần tử nhỏ nhất từ danh sách chưa sắp xếp và đưa về đầu danh sách.
Câu 14: Trong thuật toán sắp xếp chọn (Selection Sort), sau mỗi lượt duyệt, phần tử nào sau đây được đặt đúng vị trí cuối cùng trong danh sách đã sắp xếp?
- A. Phần tử đầu tiên của danh sách chưa sắp xếp.
- B. Phần tử ở giữa danh sách chưa sắp xếp.
- C. Phần tử lớn nhất trong danh sách chưa sắp xếp.
- D. Phần tử nhỏ nhất trong danh sách chưa sắp xếp.
Câu 15: Thuật toán sắp xếp nào sau đây thường được sử dụng hiệu quả cho các danh sách đã gần như được sắp xếp hoàn chỉnh?
- A. Sắp xếp trộn (Merge Sort)
- B. Sắp xếp nhanh (Quick Sort)
- C. Sắp xếp chèn (Insertion Sort)
- D. Sắp xếp vun đống (Heap Sort)
Câu 16: Xét danh sách B = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Nếu áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort), số lần đổi chỗ (hoán vị) phần tử cần thực hiện để sắp xếp danh sách này theo thứ tự tăng dần là bao nhiêu?
Câu 17: Trong lập trình, khi nào nên ưu tiên sử dụng thuật toán sắp xếp nhanh (Quick Sort) hơn thuật toán sắp xếp trộn (Merge Sort), mặc dù trong trường hợp xấu nhất, sắp xếp nhanh có thể chậm hơn?
- A. Khi cần đảm bảo độ ổn định của thuật toán sắp xếp.
- B. Khi hiệu suất trung bình là yếu tố quan trọng và không gian bộ nhớ hạn chế.
- C. Khi cần đảm bảo hiệu suất tốt nhất trong mọi trường hợp, kể cả trường hợp xấu nhất.
- D. Khi kích thước dữ liệu đầu vào rất nhỏ.
Câu 18: Thuật toán sắp xếp nào sau đây là một thuật toán "không tại chỗ" (not in-place), nghĩa là nó cần thêm không gian bộ nhớ đáng kể ngoài dữ liệu đầu vào để thực hiện sắp xếp?
- A. Sắp xếp trộn (Merge Sort)
- B. Sắp xếp chèn (Insertion Sort)
- C. Sắp xếp chọn (Selection Sort)
- D. Sắp xếp nổi bọt (Bubble Sort)
Câu 19: Cho danh sách C = ["z", "b", "a", "y", "c", "x"]. Nếu sử dụng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp danh sách này theo thứ tự bảng chữ cái, hãy mô tả trạng thái của danh sách sau ba lần chèn phần tử.
- A. ["a", "b", "c", "x", "y", "z"]
- B. ["a", "b", "z", "y", "c", "x"]
- C. ["b", "a", "z", "y", "c", "x"]
- D. ["z", "b", "a", "y", "c", "x"]
Câu 20: Trong các thuật toán sắp xếp đã học (nổi bọt, chèn, chọn, trộn, nhanh), thuật toán nào có số lượng phép so sánh và phép gán ít nhất trong trường hợp danh sách đã được sắp xếp rồi?
- A. Sắp xếp chọn (Selection Sort)
- B. Sắp xếp trộn (Merge Sort)
- C. Sắp xếp chèn (Insertion Sort)
- D. Sắp xếp nhanh (Quick Sort)
Câu 21: Để tìm kiếm thông tin về các chuyến bay thẳng từ Hà Nội đến Đà Nẵng trên một trang web đặt vé máy bay, miền dữ liệu của bài toán tìm kiếm này là gì?
- A. Tất cả thông tin trên Internet.
- B. Cơ sở dữ liệu về lịch trình và thông tin chuyến bay của các hãng hàng không.
- C. Danh sách các sân bay trên toàn thế giới.
- D. Thông tin cá nhân của tất cả người dùng Internet.
Câu 22: Giả sử bạn cần sắp xếp một mảng lớn chứa thông tin về sản phẩm (tên, giá, mô tả, hình ảnh). Tiêu chí sắp xếp chính là theo giá sản phẩm (tăng dần). Thuật toán sắp xếp nào sau đây có thể phù hợp nhất nếu bạn quan tâm đến hiệu suất và sử dụng bộ nhớ hiệu quả?
- A. Sắp xếp nổi bọt (Bubble Sort)
- B. Sắp xếp chèn (Insertion Sort)
- C. Sắp xếp chọn (Selection Sort)
- D. Sắp xếp nhanh (Quick Sort)
Câu 23: Trong một trò chơi điện tử, hệ thống cần tìm kiếm nhanh chóng thông tin của một người chơi dựa trên tên đăng nhập. Biết rằng số lượng người chơi rất lớn và tên đăng nhập là duy nhất. Cấu trúc dữ liệu nào sau đây sẽ hỗ trợ tìm kiếm hiệu quả nhất?
- A. Mảng (Array)
- B. Danh sách liên kết (Linked List)
- C. Bảng băm (Hash Table)
- D. Cây nhị phân tìm kiếm (Binary Search Tree)
Câu 24: Khi đánh giá hiệu quả của một thuật toán tìm kiếm hoặc sắp xếp, yếu tố nào sau đây thường được xem xét quan trọng nhất trong khoa học máy tính?
- A. Độ phức tạp thời gian và không gian (Time and Space Complexity)
- B. Sự dễ hiểu và dễ cài đặt của thuật toán (Simplicity and Ease of Implementation)
- C. Tính phổ biến và được sử dụng rộng rãi của thuật toán (Popularity and Wide Usage)
- D. Ngôn ngữ lập trình được sử dụng để cài đặt thuật toán (Programming Language)
Câu 25: Cho dãy số [5, 2, 8, 1, 9, 4, 7, 6, 3]. Nếu áp dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp dãy số này theo thứ tự tăng dần, sau lượt chọn phần tử nhỏ nhất đầu tiên, dãy số sẽ trở thành:
- A. [1, 2, 3, 4, 5, 6, 7, 8, 9]
- B. [1, 2, 8, 5, 9, 4, 7, 6, 3]
- C. [5, 2, 8, 1, 9, 4, 7, 6, 3]
- D. [9, 8, 7, 6, 5, 4, 3, 2, 1]
Câu 26: Trong thuật toán tìm kiếm nhị phân, điều gì xảy ra nếu phần tử cần tìm không tồn tại trong danh sách đã sắp xếp?
- A. Thuật toán sẽ trả về vị trí của phần tử gần nhất với giá trị cần tìm.
- B. Thuật toán sẽ lặp vô hạn.
- C. Thuật toán sẽ kết thúc và thông báo rằng không tìm thấy phần tử.
- D. Thuật toán sẽ trả về vị trí của phần tử đầu tiên trong danh sách.
Câu 27: Để sắp xếp một danh sách các đối tượng phức tạp (ví dụ: sinh viên với nhiều thuộc tính như tên, tuổi, điểm số) theo nhiều tiêu chí ưu tiên (ví dụ: ưu tiên theo điểm trung bình, sau đó theo tên), thuật toán sắp xếp nào sau đây vẫn có thể áp dụng được một cách linh hoạt?
- A. Sắp xếp nổi bọt (Bubble Sort)
- B. Sắp xếp chọn (Selection Sort)
- C. Sắp xếp chèn (Insertion Sort)
- D. Tất cả các thuật toán sắp xếp đã học đều có thể áp dụng được, chỉ cần điều chỉnh phép so sánh.
Câu 28: Trong thực tế, khi nào việc sử dụng thuật toán tìm kiếm tuần tự là lựa chọn hợp lý mặc dù nó có thể kém hiệu quả hơn tìm kiếm nhị phân về mặt lý thuyết?
- A. Khi danh sách dữ liệu đã được sắp xếp.
- B. Khi việc cài đặt đơn giản và nhanh chóng được ưu tiên hơn hiệu suất.
- C. Khi kích thước danh sách dữ liệu rất lớn.
- D. Khi cần tìm kiếm phần tử ở vị trí giữa danh sách.
Câu 29: Ưu điểm chính của thuật toán sắp xếp trộn (Merge Sort) so với sắp xếp nổi bọt (Bubble Sort) là gì?
- A. Độ phức tạp thời gian tốt hơn cho dữ liệu lớn.
- B. Dễ cài đặt và dễ hiểu hơn.
- C. Yêu cầu ít bộ nhớ hơn.
- D. Hiệu quả hơn cho dữ liệu đã gần như được sắp xếp.
Câu 30: Trong bài toán tìm kiếm và sắp xếp, "độ ổn định" (stability) của thuật toán sắp xếp có ý nghĩa gì?
- A. Khả năng thuật toán luôn cho ra kết quả đúng.
- B. Tốc độ thực hiện thuật toán không thay đổi theo thời gian.
- C. Thứ tự tương đối của các phần tử bằng nhau được giữ nguyên sau khi sắp xếp.
- D. Thuật toán có thể sắp xếp dữ liệu thuộc nhiều kiểu khác nhau.
