Đề 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

Đề 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 tổng hợp câu hỏi trắc nghiệm chứa đựng nhiều dạng bài tập, bài thi, cũng như các câu hỏi trắc nghiệm và bài kiểm tra, trong bộ Trắc Nghiệm Tin Học 11 – Kết Nối Tri Thức. Nội dung trắc nghiệm nhấn mạnh phần kiến thức nền tảng và chuyên môn sâu của học phần này. Mọi bộ đề trắc nghiệm đều cung cấp câu hỏi, đáp án cùng hướng dẫn giải cặn kẽ. Mời bạn thử sức làm bài nhằm ôn luyện và làm vững chắc kiến thức cũng như đánh giá năng lực bản thân!

Đề 01

Đề 02

Đề 03

Đề 04

Đề 05

Đề 06

Đề 07

Đề 08

Đề 09

Đề 10

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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

1 / 30

Category: 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

Tags: Bộ đề 01

Câu 1: Mục đích chính của các thuật toán sắp xếp là gì?

Xóa bỏ các phần tử trùng lặp khỏi danh sách.

Sắp xếp các phần tử trong danh sách theo một thứ tự xác định.

Tìm kiếm một phần tử cụ thể trong danh sách.

Thêm các phần tử mới vào danh sách.

Sắp xếp là quá trình tổ chức lại các phần tử trong một danh sách theo một thứ tự nhất định (tăng dần hoặc giảm dần) để dễ dàng xử lý hoặc tìm kiếm sau này.

2 / 30

Category: 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

Tags: Bộ đề 01

Câu 2: Xét thuật toán sắp xếp nổi bọt (Bubble Sort). Trong mỗi lần duyệt (pass) qua danh sách, thuật toán thực hiện công việc gì?

Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đặt vào đúng vị trí.

Chèn một phần tử vào vị trí thích hợp trong phần đã sắp xếp.

So sánh và hoán đổi các cặp phần tử kề nhau để đưa phần tử lớn nhất (hoặc nhỏ nhất) về cuối phần chưa sắp xếp.

Chia danh sách thành hai nửa và sắp xếp từng nửa.

Thuật toán sắp xếp nổi bọt so sánh các cặp phần tử kề nhau và hoán đổi chúng nếu sai thứ tự. Sau mỗi lần duyệt, phần tử lớn nhất (hoặc nhỏ nhất tùy thứ tự sắp xếp) chưa được sắp xếp sẽ 'nổi' lên vị trí cuối cùng của phần chưa sắp xếp.

3 / 30

Category: 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

Tags: Bộ đề 01

Câu 3: Cho dãy số [5, 1, 4, 2, 8]. Áp dụng thuật toán sắp xếp nổi bọt (tăng dần). Dãy số sẽ trông như thế nào sau *lần duyệt đầu tiên* (first pass)?

[1, 4, 2, 5, 8]

[1, 2, 4, 5, 8]

[5, 1, 4, 2, 8]

[1, 5, 4, 2, 8]

Pass 1: (5,1)->[1,5,4,2,8]; (5,4)->[1,4,5,2,8]; (5,2)->[1,4,2,5,8]; (5,8)->[1,4,2,5,8]. Kết quả sau pass 1 là [1, 4, 2, 5, 8].

4 / 30

Category: 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

Tags: Bộ đề 01

Câu 4: Xét thuật toán sắp xếp chọn (Selection Sort). Trong mỗi lần duyệt (pass) qua phần chưa sắp xếp, thuật toán thực hiện công việc gì?

So sánh và hoán đổi các cặp phần tử kề nhau.

Chèn phần tử đầu tiên của phần chưa sắp xếp vào vị trí thích hợp trong phần đã sắp xếp.

Chia danh sách thành hai nửa.

Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và hoán đổi nó với phần tử đầu tiên của phần chưa sắp xếp.

Thuật toán sắp xếp chọn tìm phần tử nhỏ nhất (hoặc lớn nhất tùy thứ tự) trong phần chưa sắp xếp và hoán đổi nó với phần tử đầu tiên của phần chưa sắp xếp.

5 / 30

Category: 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

Tags: Bộ đề 01

Câu 5: Cho dãy số [5, 1, 4, 2, 8]. Áp dụng thuật toán sắp xếp chọn (tăng dần). Dãy số sẽ trông như thế nào sau *lần duyệt đầu tiên* (first pass)?

[1, 2, 4, 5, 8]

[1, 4, 2, 5, 8]

[1, 5, 4, 2, 8]

[5, 1, 4, 2, 8]

Pass 1: Tìm phần tử nhỏ nhất trong [5, 1, 4, 2, 8] là 1. Hoán đổi 1 với phần tử đầu tiên 5. Dãy trở thành [1, 5, 4, 2, 8].

6 / 30

Category: 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

Tags: Bộ đề 01

Câu 6: So sánh thuật toán sắp xếp nổi bọt và sắp xếp chọn trên một danh sách có n phần tử. Nhận định nào sau đây đúng về số lượng phép hoán đổi (swap) trong trường hợp xấu nhất?

Sắp xếp nổi bọt luôn thực hiện ít phép hoán đổi hơn.

Sắp xếp chọn thường thực hiện ít phép hoán đổi hơn đáng kể so với sắp xếp nổi bọt.

Số lượng phép hoán đổi của hai thuật toán là như nhau.

Sắp xếp chọn thực hiện nhiều phép hoán đổi hơn đáng kể so với sắp xếp nổi bọt.

Sắp xếp chọn thực hiện chính xác n-1 phép hoán đổi (trong mỗi pass tìm min/max, nó hoán đổi). Sắp xếp nổi bọt trong trường hợp xấu nhất (dãy ngược thứ tự) có thể thực hiện đến O(n^2) phép hoán đổi.

7 / 30

Category: 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

Tags: Bộ đề 01

Câu 7: Thuật toán sắp xếp chèn (Insertion Sort) hoạt động dựa trên ý tưởng chính nào?

Xây dựng danh sách đã sắp xếp bằng cách chèn từng phần tử vào vị trí đúng trong phần đã sắp xếp.

Tìm phần tử nhỏ nhất và hoán đổi nó với phần tử đầu tiên.

So sánh các cặp phần tử kề nhau và hoán đổi nếu cần.

Chia danh sách thành các danh sách con nhỏ hơn.

Sắp xếp chèn xây dựng danh sách đã sắp xếp từng bước một bằng cách lấy từng phần tử từ phần chưa sắp xếp và chèn nó vào vị trí đúng trong phần đã sắp xếp.

8 / 30

Category: 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

Tags: Bộ đề 01

Câu 8: Cho dãy số [5, 1, 4, 2, 8]. Áp dụng thuật toán sắp xếp chèn (tăng dần). Dãy số sẽ trông như thế nào sau khi xử lý xong phần tử thứ 3 (giá trị 4)? (Coi phần tử đầu tiên [5] đã là phần đã sắp xếp ban đầu).

[1, 5, 4, 2, 8]

[1, 4, 5, 2, 8]

[1, 2, 4, 5, 8]

[5, 1, 4, 2, 8]

Ban đầu: [5 | 1, 4, 2, 8].
Bước xử lý 1 (phần tử 1): Chèn 1 vào trước 5. Dãy: [1, 5 | 4, 2, 8].
Bước xử lý 2 (phần tử 4): Chèn 4 vào phần đã sắp xếp [1, 5]. 4 nằm giữa 1 và 5. Dãy: [1, 4, 5 | 2, 8].

9 / 30

Category: 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

Tags: Bộ đề 01

Câu 9: Thuật toán sắp xếp nào sau đây được xem là hiệu quả nhất trong ba thuật toán đơn giản (Nổi bọt, Chọn, Chèn) khi danh sách đầu vào *gần như đã được sắp xếp*?

Sắp xếp nổi bọt.

Sắp xếp chọn.

Sắp xếp chèn.

Cả ba đều có hiệu suất như nhau trong trường hợp này.

Sắp xếp chèn có thể đạt hiệu suất O(n) trong trường hợp tốt nhất (danh sách đã sắp xếp hoặc gần sắp xếp) vì nó chỉ cần thực hiện ít phép dịch chuyển để chèn các phần tử.

10 / 30

Category: 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

Tags: Bộ đề 01

Câu 10: Độ phức tạp thời gian (Time Complexity) của các thuật toán sắp xếp đơn giản (Nổi bọt, Chọn, Chèn) trong trường hợp xấu nhất thường là bao nhiêu với n là số lượng phần tử?

O(n)

O(n log n)

O(log n)

O(n^2)

Cả ba thuật toán sắp xếp nổi bọt, sắp xếp chọn và sắp xếp chèn đều có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất (ví dụ: danh sách ngược thứ tự).

11 / 30

Category: 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

Tags: Bộ đề 01

Câu 11: Thuật toán sắp xếp nào có đặc điểm là số lượng phép hoán đổi (swap) luôn không vượt quá số lượng phần tử (n-1), bất kể dữ liệu đầu vào như thế nào?

Sắp xếp nổi bọt.

Sắp xếp chọn.

Sắp xếp chèn.

Cả ba thuật toán.

Sắp xếp chọn thực hiện chính xác n-1 phép hoán đổi trong n-1 lần duyệt, mỗi lần hoán đổi phần tử nhỏ nhất/lớn nhất về đúng vị trí.

12 / 30

Category: 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

Tags: Bộ đề 01

Câu 12: Khi nào thì nên cân nhắc sử dụng một trong các thuật toán sắp xếp đơn giản (Nổi bọt, Chọn, Chèn) thay vì các thuật toán phức tạp hơn như Merge Sort hay Quick Sort?

Khi kích thước danh sách cần sắp xếp rất nhỏ.

Khi hiệu suất là yếu tố quan trọng nhất.

Khi danh sách chứa rất nhiều phần tử trùng lặp.

Khi danh sách đã được sắp xếp ngược thứ tự.

Các thuật toán đơn giản dễ hiểu và dễ cài đặt. Chúng thường đủ nhanh cho các danh sách có kích thước nhỏ (n nhỏ) mặc dù có độ phức tạp O(n^2). Với n lớn, O(n log n) thuật toán sẽ vượt trội.

13 / 30

Category: 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

Tags: Bộ đề 01

Câu 13: Một thuật toán sắp xếp được mô tả như sau: 'Lặp lại việc duyệt qua danh sách, so sánh từng cặp phần tử kề nhau và hoán đổi nếu chúng sai thứ tự. Quá trình này lặp lại cho đến khi không còn cặp nào cần hoán đổi.' Mô tả này ứng với thuật toán sắp xếp nào?

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

Sắp xếp chọn (Selection Sort).

Sắp xếp chèn (Insertion Sort).

Sắp xếp nhanh (Quick Sort).

Đây chính xác là mô tả của thuật toán sắp xếp nổi bọt, với việc so sánh và hoán đổi các cặp kề nhau.

14 / 30

Category: 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

Tags: Bộ đề 01

Câu 14: Cho dãy số [3, 1, 4, 1, 5, 9, 2, 6]. Áp dụng sắp xếp chọn (tăng dần). Phần tử nào sẽ nằm ở vị trí đầu tiên sau khi hoàn thành *pass thứ 2*?

Dãy: [3, 1, 4, 1, 5, 9, 2, 6]
Pass 1: Tìm min trong [3, 1, 4, 1, 5, 9, 2, 6] là 1 (ở vị trí index 1 hoặc 3). Giả sử chọn index 1. Hoán đổi 3 và 1. Dãy: [1, 3, 4, 1, 5, 9, 2, 6]. Phần đã sắp xếp: [1].
Pass 2: Tìm min trong phần chưa sắp xếp [3, 4, 1, 5, 9, 2, 6] là 1 (ở vị trí index 3 trong dãy gốc, index 2 trong phần chưa sắp xếp). Hoán đổi 3 và 1. Dãy: [1, 1, 4, 3, 5, 9, 2, 6]. Phần đã sắp xếp: [1, 1].
Phần tử ở vị trí đầu tiên sau pass 2 là 1.

15 / 30

Category: 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

Tags: Bộ đề 01

Câu 15: Xét thuật toán sắp xếp chèn. Sau k bước lặp chính (xử lý xong k phần tử đầu tiên của phần chưa sắp xếp), phần k+1 phần tử đầu tiên của danh sách ban đầu sẽ có đặc điểm gì?

Phần k+1 phần tử đầu tiên là tập hợp k+1 phần tử nhỏ nhất của toàn bộ danh sách, đã được sắp xếp.

Phần k+1 phần tử đầu tiên là tập hợp k+1 phần tử đầu tiên của danh sách ban đầu, nhưng chưa chắc đã sắp xếp.

Phần k+1 phần tử đầu tiên là tập hợp k+1 phần tử lớn nhất của toàn bộ danh sách, đã được sắp xếp.

Phần k+1 phần tử đầu tiên là tập hợp k+1 phần tử đầu tiên của danh sách ban đầu, và chúng đã được sắp xếp.

Sắp xếp chèn xây dựng phần đã sắp xếp từ bên trái sang. Sau khi xử lý xong k phần tử từ phần chưa sắp xếp (tức là đến phần tử thứ k+1 của dãy gốc), k+1 phần tử đầu tiên của dãy sẽ là tập hợp k+1 phần tử đầu tiên của dãy gốc, nhưng đã được sắp xếp.

16 / 30

Category: 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

Tags: Bộ đề 01

Câu 16: Trong thuật toán sắp xếp nổi bọt, làm thế nào để biết khi nào toàn bộ danh sách đã được sắp xếp và có thể dừng thuật toán sớm?

Khi số lần duyệt đạt đến n-1.

Khi trong một lần duyệt, không có cặp phần tử nào bị hoán đổi.

Khi phần tử cuối cùng của danh sách đã đúng vị trí.

Khi phần tử đầu tiên của danh sách đã đúng vị trí.

Nếu trong một lần duyệt (pass) qua toàn bộ phần chưa sắp xếp, không có bất kỳ phép hoán đổi nào xảy ra, điều đó chứng tỏ tất cả các cặp kề nhau đều đã đúng thứ tự, tức là toàn bộ danh sách đã được sắp xếp.

17 / 30

Category: 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

Tags: Bộ đề 01

Câu 17: Giả sử bạn cần sắp xếp một danh sách liên kết (linked list). Thuật toán sắp xếp đơn giản nào sau đây có thể gặp khó khăn hoặc kém hiệu quả hơn đáng kể so với mảng (array) do cấu trúc dữ liệu?

Sắp xếp chèn (Insertion Sort).

Sắp xếp chọn (Selection Sort).

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

Cả ba đều gặp khó khăn như nhau.

Sắp xếp chọn và nổi bọt cần truy cập ngẫu nhiên các phần tử (để tìm min/max hoặc so sánh kề nhau). Sắp xếp chèn cũng cần dịch chuyển các phần tử. Tuy nhiên, việc dịch chuyển trong danh sách liên kết (Insertion Sort) chỉ cần thay đổi con trỏ, trong khi hoán đổi phần tử ở xa nhau (Selection Sort, Bubble Sort) trong danh sách liên kết sẽ phức tạp và tốn kém hơn nhiều so với mảng.

18 / 30

Category: 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

Tags: Bộ đề 01

Câu 18: Cho dãy số [7, 3, 5, 8, 2]. Áp dụng sắp xếp chèn (tăng dần). Dãy số sẽ trông như thế nào sau khi xử lý xong phần tử có giá trị 8?

[2, 3, 5, 7, 8]

[3, 5, 7, 2, 8]

[3, 5, 2, 7, 8]

[3, 5, 7, 8, 2]

Ban đầu: [7 | 3, 5, 8, 2]
Bước xử lý 1 (3): chèn 3 vào trước 7 -> [3, 7 | 5, 8, 2]
Bước xử lý 2 (5): chèn 5 vào [3, 7] -> [3, 5, 7 | 8, 2]
Bước xử lý 3 (8): chèn 8 vào [3, 5, 7]. 8 lớn hơn tất cả, nên giữ nguyên vị trí. Dãy: [3, 5, 7, 8 | 2].

19 / 30

Category: 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

Tags: Bộ đề 01

Câu 19: Nhận định nào sau đây là SAI khi nói về thuật toán sắp xếp chọn (Selection Sort)?

Số lượng phép hoán đổi luôn là n-1.

Trong mỗi lần duyệt, thuật toán tìm phần tử nhỏ nhất trong phần chưa sắp xếp.

Hiệu suất của thuật toán thay đổi đáng kể tùy thuộc vào việc danh sách đầu vào đã sắp xếp hay chưa.

Độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2).

Sắp xếp chọn thực hiện cùng số lượng phép so sánh (O(n^2)) bất kể dữ liệu đầu vào như thế nào (trường hợp tốt nhất, xấu nhất hay trung bình). Số phép hoán đổi thì luôn là n-1.

20 / 30

Category: 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

Tags: Bộ đề 01

Câu 20: Trong bối cảnh lập trình, việc cài đặt thuật toán sắp xếp chèn (Insertion Sort) thường sử dụng cấu trúc lặp lồng nhau. Vòng lặp ngoài thường dùng để làm gì?

Duyệt qua các phần tử từ phần chưa sắp xếp để chọn ra phần tử cần chèn.

Tìm vị trí thích hợp để chèn phần tử vào phần đã sắp xếp.

Thực hiện việc dịch chuyển các phần tử trong phần đã sắp xếp.

Đếm số lần hoán đổi đã thực hiện.

Vòng lặp ngoài trong sắp xếp chèn duyệt qua các phần tử từ phần chưa sắp xếp (bắt đầu từ phần tử thứ 2). Mỗi lần lặp của vòng ngoài sẽ lấy một phần tử và chèn nó vào phần đã sắp xếp.

21 / 30

Category: 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

Tags: Bộ đề 01

Câu 21: Thuật toán sắp xếp nào sau đây có thể dừng sớm nếu danh sách đầu vào đã được sắp xếp hoàn toàn ngay từ đầu?

Sắp xếp nổi bọt (với cờ kiểm tra hoán đổi).

Sắp xếp chọn.

Cả sắp xếp chọn và sắp xếp chèn.

Không có thuật toán đơn giản nào có thể dừng sớm.

Sắp xếp nổi bọt có thể được cải tiến để dừng sớm nếu không có hoán đổi nào trong một lượt duyệt. Sắp xếp chèn cũng có thể dừng sớm vòng lặp bên trong khi tìm được vị trí chèn (nếu phần tử lớn hơn vị trí hiện tại). Sắp xếp chọn thì luôn thực hiện đủ số lượt duyệt và hoán đổi (nếu cần) bất kể dữ liệu đã sắp xếp hay chưa.

22 / 30

Category: 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

Tags: Bộ đề 01

Câu 22: Cho dãy số [6, 5, 4, 3, 2, 1]. Đây là trường hợp xấu nhất cho thuật toán sắp xếp nào trong ba thuật toán đơn giản xét về số lượng phép so sánh hoặc hoán đổi?

Sắp xếp chọn.

Sắp xếp chèn.

Sắp xếp nổi bọt.

Đây là trường hợp xấu nhất (hoặc gần xấu nhất) cho cả ba thuật toán.

Dãy ngược thứ tự là trường hợp xấu nhất cho cả ba thuật toán đơn giản (Bubble, Selection, Insertion) khi nói về số phép so sánh (O(n^2)). Đối với số phép hoán đổi, nó cũng là trường hợp xấu nhất cho Bubble Sort và Insertion Sort (vì cần dịch chuyển/hoán đổi nhiều), còn Selection Sort thì số hoán đổi luôn cố định là n-1.

23 / 30

Category: 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

Tags: Bộ đề 01

Câu 23: Khi sắp xếp một danh sách các đối tượng phức tạp (ví dụ: đối tượng SinhVien với nhiều thuộc tính), yếu tố nào sau đây của thuật toán sắp xếp đơn giản trở nên quan trọng cần cân nhắc?

Số lượng phép so sánh.

Số lượng phép hoán đổi.

Độ phức tạp không gian bộ nhớ.

Khả năng dừng sớm.

Với các đối tượng phức tạp, phép hoán đổi (di chuyển toàn bộ dữ liệu của đối tượng) thường tốn kém hơn nhiều so với phép so sánh (chỉ so sánh một thuộc tính). Do đó, thuật toán nào giảm thiểu số phép hoán đổi (như Selection Sort) sẽ có lợi hơn trong trường hợp này.

24 / 30

Category: 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

Tags: Bộ đề 01

Câu 24: Thuật toán sắp xếp nào sau đây được mô tả là 'ổn định' (stable), nghĩa là nó giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau?

Sắp xếp chọn.

Chỉ sắp xếp nổi bọt.

Sắp xếp nổi bọt và sắp xếp chèn.

Không có thuật toán đơn giản nào ổn định.

Sắp xếp nổi bọt và Sắp xếp chèn là các thuật toán ổn định. Sắp xếp chọn không ổn định vì việc hoán đổi phần tử nhỏ nhất/lớn nhất với phần tử đầu tiên của phần chưa sắp xếp có thể làm thay đổi thứ tự tương đối của các phần tử bằng nhau.

25 / 30

Category: 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

Tags: Bộ đề 01

Câu 25: Áp dụng sắp xếp nổi bọt (tăng dần) cho dãy [4, 2, 1, 3]. Số lượng phép hoán đổi (swap) tối thiểu cần thực hiện để dãy được sắp xếp là bao nhiêu?

Dãy: [4, 2, 1, 3]
Pass 1: (4,2)->[2,4,1,3]; (4,1)->[2,1,4,3]; (4,3)->[2,1,3,4]. Swaps: 3.
Pass 2: (2,1)->[1,2,3,4]; (2,3)->[1,2,3,4]; (3,4)->[1,2,3,4]. Swaps: 1.
Pass 3: (2,3)->[1,2,3,4]; (3,4)->[1,2,3,4]. Swaps: 0. Dừng.
Tổng số hoán đổi: 3 + 1 = 4. (Lưu ý: đây là số hoán đổi thực tế, không phải số lần lặp).

26 / 30

Category: 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

Tags: Bộ đề 01

Câu 26: Áp dụng sắp xếp chọn (tăng dần) cho dãy [4, 2, 1, 3]. Số lượng phép hoán đổi (swap) cần thực hiện là bao nhiêu?

Dãy: [4, 2, 1, 3] (n=4)
Pass 1 (index 0): Min trong [4,2,1,3] là 1 (index 2). Hoán đổi 4 và 1. Dãy: [1, 2, 4, 3]. Hoán đổi: 1.
Pass 2 (index 1): Min trong [2,4,3] là 2 (index 1). Hoán đổi 2 và 2 (không đổi). Dãy: [1, 2, 4, 3]. Hoán đổi: 0.
Pass 3 (index 2): Min trong [4,3] là 3 (index 3). Hoán đổi 4 và 3. Dãy: [1, 2, 3, 4]. Hoán đổi: 1.
Tổng số hoán đổi: 1 + 0 + 1 = 2. (Hoặc đơn giản là n-1 = 4-1 = 3 hoán đổi vị trí, nhưng số lần thực hiện lệnh swap có thể khác tùy cài đặt. Tuy nhiên, câu hỏi thường ngụ ý số lần cặp phần tử thay đổi vị trí). Nếu tính số lần thực hiện lệnh swap khi phần tử không ở đúng vị trí thì là 2 lần.

27 / 30

Category: 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

Tags: Bộ đề 01

Câu 27: Áp dụng sắp xếp chèn (tăng dần) cho dãy [4, 2, 1, 3]. Dãy số sẽ trông như thế nào sau khi xử lý xong phần tử có giá trị 1?

[2, 4, 1, 3]

[4, 2, 1, 3]

[1, 2, 4, 3]

[1, 2, 3, 4]

Ban đầu: [4 | 2, 1, 3]
Bước xử lý 1 (2): chèn 2 vào [4] -> [2, 4 | 1, 3]
Bước xử lý 2 (1): chèn 1 vào [2, 4]. 1 nhỏ hơn 2, dịch 2 và 4 sang phải, chèn 1 vào đầu. Dãy: [1, 2, 4 | 3].

28 / 30

Category: 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

Tags: Bộ đề 01

Câu 28: Nhận định nào sau đây là đúng nhất về ưu điểm của thuật toán sắp xếp nổi bọt (Bubble Sort)?

Luôn có hiệu suất tốt nhất trong trường hợp trung bình.

Số lượng phép hoán đổi luôn tối thiểu.

Hiệu quả với danh sách có kích thước lớn.

Đơn giản và dễ cài đặt.

Ưu điểm chính của Bubble Sort là tính đơn giản và dễ hiểu, dễ cài đặt. Hiệu suất không phải là ưu điểm của nó với dữ liệu lớn.

29 / 30

Category: 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

Tags: Bộ đề 01

Câu 29: Khi cần sắp xếp một danh sách rất lớn và hiệu suất là yếu tố quan trọng hàng đầu, các thuật toán đơn giản O(n^2) thường không được ưu tiên. Thay vào đó, người ta thường sử dụng các thuật toán có độ phức tạp thời gian nào?

O(n^3)

O(n log n)

O(log n)

O(n)

Đối với danh sách lớn, các thuật toán có độ phức tạp thời gian O(n log n) như Merge Sort, Quick Sort, Heap Sort thường được sử dụng vì chúng hiệu quả hơn đáng kể so với O(n^2).

30 / 30

Category: 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

Tags: Bộ đề 01

Câu 30: Giả sử bạn cần sắp xếp một tệp dữ liệu rất lớn không thể chứa hết trong bộ nhớ RAM (external sorting). Thuật toán sắp xếp đơn giản nào sau đây sẽ gặp khó khăn lớn nhất khi triển khai trong tình huống này?

Sắp xếp nổi bọt.

Sắp xếp chọn.

Sắp xếp chèn.

Cả ba thuật toán đơn giản đều không hiệu quả cho external sorting.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Các thuật toán đơn giản O(n^2) thường yêu cầu truy cập ngẫu nhiên và hoán đổi/dịch chuyển nhiều phần tử, làm cho chúng không phù hợp với dữ liệu ngoại vi (trên đĩa) do chi phí truy cập đĩa rất cao. Các thuật toán như Merge Sort (dựa trên chia và trộn) thường phù hợp hơn cho external sorting.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 02

1 / 30

Category: 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

Tags: Bộ đề 02

Câu 1: Bài toán sắp xếp là gì?

Tìm kiếm một phần tử trong danh sách.

Sắp xếp các phần tử trong danh sách theo một thứ tự nhất định.

Xóa một phần tử khỏi danh sách.

Thêm một phần tử vào danh sách.

Bài toán sắp xếp là bài toán tổ chức lại các phần tử trong một danh sách theo một thứ tự nhất định (tăng dần hoặc giảm dần).

2 / 30

Category: 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

Tags: Bộ đề 02

Câu 2: Thuật toán Sắp xếp chọn (Selection Sort) hoạt động theo nguyên tắc nào?

So sánh các phần tử kề nhau và đổi chỗ nếu sai thứ tự.

Chèn từng phần tử vào đúng vị trí trong phần đã sắp xếp.

Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp.

Chia danh sách thành hai nửa và sắp xếp từng nửa.

Sắp xếp chọn hoạt động bằng cách lặp lại việc tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa được sắp xếp của danh sách và đưa nó về đúng vị trí của nó ở đầu phần đã sắp xếp.

3 / 30

Category: 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

Tags: Bộ đề 02

Câu 3: Cho dãy số A = [5, 2, 8, 1, 9]. Áp dụng thuật toán Sắp xếp chọn theo thứ tự tăng dần. Dãy A sẽ như thế nào sau *lần duyệt (pass) đầu tiên*?

[2, 5, 8, 1, 9]

[1, 2, 8, 5, 9]

[5, 2, 8, 1, 9]

[1, 2, 8, 5, 9]

Lần duyệt đầu tiên của Sắp xếp chọn tìm phần tử nhỏ nhất trong toàn bộ dãy ([5, 2, 8, 1, 9]) là 1, và đổi chỗ nó với phần tử đầu tiên (5). Kết quả là [1, 2, 8, 5, 9].

4 / 30

Category: 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

Tags: Bộ đề 02

Câu 4: Thuật toán Sắp xếp nổi bọt (Bubble Sort) hoạt động theo nguyên tắc nào?

So sánh các phần tử kề nhau và đổi chỗ nếu sai thứ tự, lặp lại cho đến khi danh sách được sắp xếp.

Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp.

Chèn từng phần tử vào đúng vị trí trong phần đã sắp xếp.

Chia danh sách thành hai nửa và sắp xếp từng nửa.

Sắp xếp nổi bọt lặp lại việc so sánh các cặp phần tử kề nhau và đổi chỗ chúng nếu chúng không đúng thứ tự, dần dần 'nổi' các phần tử lớn (hoặc nhỏ) về cuối (hoặc đầu) danh sách.

5 / 30

Category: 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

Tags: Bộ đề 02

Câu 5: Cho dãy số B = [6, 1, 4, 3, 2]. Áp dụng thuật toán Sắp xếp nổi bọt theo thứ tự tăng dần. Dãy B sẽ như thế nào sau *lần duyệt (pass) đầu tiên*?

[1, 2, 3, 4, 6]

[1, 4, 3, 2, 6]

[6, 1, 4, 3, 2]

Lần duyệt đầu tiên của Bubble Sort: (6,1)->(1,6), (6,4)->(4,6), (6,3)->(3,6), (6,2)->(2,6). Kết quả là [1, 4, 3, 2, 6].

6 / 30

Category: 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

Tags: Bộ đề 02

Câu 6: Thuật toán Sắp xếp chèn (Insertion Sort) hoạt động theo nguyên tắc nào?

So sánh các phần tử kề nhau và đổi chỗ nếu sai thứ tự.

Chèn từng phần tử vào đúng vị trí trong phần đã sắp xếp được xây dựng từ trái sang phải.

Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp.

Chia danh sách thành hai nửa và sắp xếp từng nửa.

Sắp xếp chèn xây dựng danh sách đã sắp xếp từng bước một bằng cách lấy các phần tử từ danh sách chưa sắp xếp và chèn chúng vào đúng vị trí trong phần danh sách đã sắp xếp.

7 / 30

Category: 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

Tags: Bộ đề 02

Câu 7: Cho dãy số C = [7, 3, 5, 1, 4]. Áp dụng thuật toán Sắp xếp chèn theo thứ tự tăng dần. Dãy C sẽ như thế nào sau khi xử lý xong phần tử có giá trị bằng 5 (tức là sau khi chèn 3 và 5 vào phần đã sắp xếp)?

[3, 5, 7, 1, 4]

[3, 7, 5, 1, 4]

[1, 3, 5, 7, 4]

[7, 3, 5, 1, 4]

Ban đầu: [7, 3, 5, 1, 4]. Chèn 3: [3, 7, 5, 1, 4]. Chèn 5: [3, 5, 7, 1, 4]. Phần đã sắp xếp là [3, 5, 7].

8 / 30

Category: 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

Tags: Bộ đề 02

Câu 8: Đối với dãy có n phần tử, thuật toán Sắp xếp chọn (Selection Sort) cần bao nhiêu lượt so sánh trong trường hợp xấu nhất (worst case)?

O(n)

O(n log n)

O(n^2)

O(log n)

Selection Sort luôn thực hiện (n-1) + (n-2) + ... + 1 = n*(n-1)/2 phép so sánh, bất kể dữ liệu đầu vào. Độ phức tạp là O(n^2).

9 / 30

Category: 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

Tags: Bộ đề 02

Câu 9: Thuật toán Sắp xếp nổi bọt (Bubble Sort) có thể dừng sớm nếu trong một lượt duyệt (pass) không có bất kỳ cặp phần tử nào được đổi chỗ. Điều này xảy ra khi nào?

Khi danh sách rỗng.

Khi chỉ còn một phần tử trong danh sách.

Khi tất cả các phần tử đều có giá trị giống nhau.

Khi danh sách đã được sắp xếp hoàn toàn.

Nếu trong một lượt duyệt của Bubble Sort, không có cặp nào cần đổi chỗ, điều đó có nghĩa là toàn bộ danh sách đã được sắp xếp.

10 / 30

Category: 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

Tags: Bộ đề 02

Câu 10: Trong trường hợp tốt nhất (best case), thuật toán Sắp xếp chèn (Insertion Sort) có độ phức tạp thời gian là bao nhiêu và xảy ra khi nào?

O(n^2) khi danh sách đã sắp xếp.

O(n) khi danh sách đã sắp xếp.

O(n log n) khi danh sách ngược thứ tự.

O(1) khi danh sách chỉ có 2 phần tử.

Best case của Insertion Sort là khi danh sách đã được sắp xếp. Mỗi phần tử mới chỉ cần 1 phép so sánh để xác nhận nó ở đúng vị trí. Tổng cộng O(n) phép so sánh.

11 / 30

Category: 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

Tags: Bộ đề 02

Câu 11: Thuật toán sắp xếp nào trong các thuật toán đơn giản (Selection, Bubble, Insertion) có số lần đổi chỗ (swap) luôn cố định là n-1 đối với dãy có n phần tử?

Sắp xếp chọn (Selection Sort)

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

Sắp xếp chèn (Insertion Sort)

Cả ba thuật toán đều có số lần đổi chỗ thay đổi tùy theo dữ liệu đầu vào.

Selection Sort ở mỗi bước tìm phần tử min/max và đổi chỗ nó về đúng vị trí. Có n-1 bước như vậy, mỗi bước thực hiện tối đa 1 swap. Tổng cộng là n-1 swap (nếu phần tử đã ở đúng vị trí thì swap với chính nó, vẫn tính là 1 swap logic).

12 / 30

Category: 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

Tags: Bộ đề 02

Câu 12: Khi nào thì nên cân nhắc sử dụng thuật toán Sắp xếp chèn (Insertion Sort) thay vì Sắp xếp chọn hoặc Sắp xếp nổi bọt?

Khi danh sách có kích thước rất lớn.

Khi cần đảm bảo số lần so sánh là cố định.

Khi danh sách hoàn toàn ngược thứ tự.

Khi danh sách có kích thước nhỏ hoặc đã gần như được sắp xếp.

Insertion Sort hiệu quả đặc biệt với các danh sách có kích thước nhỏ hoặc danh sách đã gần như được sắp xếp, vì nó có best case là O(n).

13 / 30

Category: 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

Tags: Bộ đề 02

Câu 13: Cho dãy số D = [4, 1, 3, 2]. Áp dụng thuật toán Sắp xếp chèn theo thứ tự tăng dần. Dãy D sẽ như thế nào sau khi hoàn thành *bước chèn phần tử thứ 3* (giá trị 3)?

[1, 4, 3, 2]

[1, 3, 4, 2]

[1, 2, 3, 4]

[4, 1, 3, 2]

Ban đầu: [4, 1, 3, 2]. Phần đã sắp xếp ban đầu là [4]. Chèn 1: [1, 4, 3, 2]. Phần đã sắp xếp là [1, 4]. Chèn 3: So sánh 3 với 4 (đổi chỗ), so sánh 3 với 1 (không đổi chỗ). Kết quả sau khi chèn 3 là [1, 3, 4, 2].

14 / 30

Category: 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

Tags: Bộ đề 02

Câu 14: Độ phức tạp thời gian của các thuật toán sắp xếp đơn giản (Selection, Bubble, Insertion) trong trường hợp xấu nhất đều là O(n^2). Điều này có ý nghĩa gì khi xử lý các danh sách có kích thước rất lớn?

Các thuật toán này rất hiệu quả với danh sách lớn.

Thời gian thực thi tăng tuyến tính với kích thước danh sách.

Thời gian thực thi tăng rất nhanh khi kích thước danh sách lớn, khiến chúng không hiệu quả.

Số lần đổi chỗ không đáng kể với danh sách lớn.

Độ phức tạp O(n^2) nghĩa là thời gian thực thi tăng theo bình phương số lượng phần tử. Đối với danh sách rất lớn, thời gian này sẽ tăng lên rất nhanh, khiến các thuật toán này trở nên không hiệu quả.

15 / 30

Category: 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

Tags: Bộ đề 02

Câu 15: Giả sử bạn đang triển khai một ứng dụng cần sắp xếp dữ liệu 'trực tuyến' (online), nghĩa là các phần tử mới được thêm vào danh sách cần sắp xếp liên tục. Thuật toán đơn giản nào phù hợp nhất cho việc này?

Sắp xếp chọn (Selection Sort)

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

Sắp xếp chèn (Insertion Sort)

Cả ba thuật toán đều không phù hợp.

Insertion Sort có thể dễ dàng thích nghi với việc thêm phần tử mới vào danh sách đã sắp xếp từng phần, bằng cách đơn giản chèn phần tử mới vào đúng vị trí của nó trong phần đã sắp xếp.

16 / 30

Category: 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

Tags: Bộ đề 02

Câu 16: Đặc điểm nào sau đây KHÔNG phải là ưu điểm của các thuật toán sắp xếp đơn giản (Selection, Bubble, Insertion)?

Dễ hiểu và dễ cài đặt.

Yêu cầu ít bộ nhớ phụ (O(1) không gian).

Phù hợp với danh sách nhỏ hoặc gần sắp xếp (đối với Insertion Sort).

Tốc độ xử lý nhanh đối với danh sách có kích thước lớn.

Các thuật toán đơn giản thường dễ hiểu và dễ cài đặt. Chúng cũng yêu cầu ít bộ nhớ bổ sung (in-place). Tuy nhiên, chúng kém hiệu quả hơn các thuật toán phức tạp hơn (như Quick Sort, Merge Sort) đối với dữ liệu lớn.

17 / 30

Category: 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

Tags: Bộ đề 02

Câu 17: Cho dãy số E = [9, 8, 7, 6, 5]. Áp dụng thuật toán Sắp xếp nổi bọt theo thứ tự tăng dần. Có bao nhiêu lần đổi chỗ (swap) được thực hiện trong *lần duyệt (pass) đầu tiên*?

Lần duyệt đầu tiên của Bubble Sort: (9,8)->(8,9) 1 swap; (9,7)->(7,9) 1 swap; (9,6)->(6,9) 1 swap; (9,5)->(5,9) 1 swap. Tổng cộng 4 lần đổi chỗ.

18 / 30

Category: 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

Tags: Bộ đề 02

Câu 18: Trong Sắp xếp chèn (Insertion Sort), phần nào của danh sách được coi là 'đã sắp xếp' sau mỗi bước lặp chính?

Phần tử cuối cùng của danh sách.

Phần đầu của danh sách, bao gồm các phần tử đã được chèn vào đúng vị trí.

Toàn bộ danh sách.

Phần tử nhỏ nhất tìm được trong mỗi bước.

Insertion Sort xây dựng phần đã sắp xếp từ đầu danh sách. Sau mỗi bước, một phần tử từ phần chưa sắp xếp được chèn vào đúng vị trí trong phần đã sắp xếp, mở rộng phần này thêm một phần tử.

19 / 30

Category: 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

Tags: Bộ đề 02

Câu 19: Cho dãy số F = [10, 20, 30, 40, 50]. Áp dụng thuật toán Sắp xếp nổi bọt theo thứ tự tăng dần. Có bao nhiêu lần đổi chỗ (swap) được thực hiện trong *toàn bộ quá trình* sắp xếp?

N-1

N*(N-1)/2

Thay đổi tùy theo cách triển khai

Dãy đã được sắp xếp. Bubble Sort sẽ thực hiện các phép so sánh nhưng không có cặp nào cần đổi chỗ. Thuật toán có thể dừng sau lần duyệt đầu tiên mà không cần đổi chỗ nào (nếu có cờ hiệu). Tổng số đổi chỗ là 0.

20 / 30

Category: 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

Tags: Bộ đề 02

Câu 20: Thuật toán sắp xếp nào trong các thuật toán đơn giản có số lần so sánh là cố định O(n^2) bất kể dữ liệu đầu vào là gì?

Sắp xếp chọn (Selection Sort)

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

Sắp xếp chèn (Insertion Sort)

Cả ba thuật toán.

Selection Sort luôn thực hiện số lượng phép so sánh cố định (n*(n-1)/2) để tìm phần tử nhỏ nhất/lớn nhất trong phần còn lại của danh sách, không phụ thuộc vào trạng thái sắp xếp ban đầu.

21 / 30

Category: 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

Tags: Bộ đề 02

Câu 21: Cho dãy số G = [3, 1, 4, 1, 5, 9, 2, 6]. Áp dụng Sắp xếp chọn theo thứ tự tăng dần. Dãy G sẽ như thế nào sau khi hoàn thành *hai lần duyệt (pass)* đầu tiên?

[1, 3, 4, 1, 5, 9, 2, 6]

[1, 1, 3, 4, 5, 9, 2, 6]

[1, 1, 4, 3, 5, 9, 2, 6]

Ban đầu: [3, 1, 4, 1, 5, 9, 2, 6]. Pass 1: Tìm min (1) ở vị trí 2, đổi chỗ với phần tử đầu (3). Dãy: [1, 3, 4, 1, 5, 9, 2, 6]. Pass 2: Xét phần chưa sắp xếp [3, 4, 1, 5, 9, 2, 6]. Tìm min (1) ở vị trí 4 (ban đầu), đổi chỗ với phần tử đầu của phần chưa sắp xếp (3). Dãy: [1, 1, 4, 3, 5, 9, 2, 6].

22 / 30

Category: 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

Tags: Bộ đề 02

Câu 22: Thuật toán nào trong các thuật toán đơn giản được mô tả bằng các bước sau: 'Lặp từ phần tử thứ hai đến hết danh sách. Với mỗi phần tử, so sánh nó với các phần tử trong phần đã sắp xếp ở phía trước và chèn nó vào đúng vị trí bằng cách dịch chuyển các phần tử lớn hơn sang phải.'

Sắp xếp chọn (Selection Sort)

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

Sắp xếp chèn (Insertion Sort)

Không phải thuật toán nào trong số này.

Đây là mô tả chính xác của thuật toán Sắp xếp chèn (Insertion Sort).

23 / 30

Category: 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

Tags: Bộ đề 02

Câu 23: Cho dãy số H = [2, 1, 4, 3]. Áp dụng Sắp xếp nổi bọt theo thứ tự tăng dần. Dãy H sẽ như thế nào sau khi hoàn thành *lần duyệt (pass) thứ hai*?

[1, 2, 3, 4]

[1, 2, 4, 3]

[2, 1, 4, 3]

[1, 3, 2, 4]

Ban đầu: [2, 1, 4, 3]. Pass 1: (2,1)->(1,2), (2,4)->(2,4), (4,3)->(3,4). Dãy: [1, 2, 3, 4]. Pass 2: Dãy đã sắp xếp. Không có đổi chỗ nào. Dãy vẫn là [1, 2, 3, 4].

24 / 30

Category: 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

Tags: Bộ đề 02

Câu 24: Thuật toán sắp xếp nào được gọi là 'stable' (ổn định) nếu nó duy trì thứ tự tương đối của các phần tử có giá trị bằng nhau?

Sắp xếp chọn (Selection Sort)

Sắp xếp nhanh (Quick Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp trộn (Merge Sort)

Tính ổn định của thuật toán sắp xếp là khả năng duy trì thứ tự ban đầu của các phần tử có giá trị bằng nhau. Sắp xếp chèn (Insertion Sort) và Sắp xếp nổi bọt (Bubble Sort) có thể triển khai để ổn định, trong khi Sắp xếp chọn (Selection Sort) điển hình là không ổn định.

25 / 30

Category: 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

Tags: Bộ đề 02

Câu 25: Một giáo viên yêu cầu học sinh sắp xếp một chồng bài kiểm tra theo điểm từ thấp đến cao. Chồng bài kiểm tra chỉ có 15 bài. Thuật toán đơn giản nào có thể là lựa chọn hợp lý nhất về mặt hiệu quả và dễ hiểu?

Sắp xếp hợp nhất (Merge Sort)

Sắp xếp nhanh (Quick Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp đếm (Counting Sort)

Với kích thước danh sách rất nhỏ (15 bài), sự khác biệt về độ phức tạp O(N^2) giữa các thuật toán đơn giản là không đáng kể. Insertion Sort thường hiệu quả trong thực tế với dữ liệu nhỏ và rất dễ hiểu, giống cách người ta thường sắp xếp bài hoặc quân bài.

26 / 30

Category: 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

Tags: Bộ đề 02

Câu 26: Thuật toán sắp xếp đơn giản nào có số lần đổi chỗ (swap) có thể lên tới O(n^2) trong trường hợp xấu nhất (ví dụ: dãy ngược thứ tự)?

Sắp xếp chọn (Selection Sort)

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

Sắp xếp chèn (Insertion Sort)

Tất cả các thuật toán trên.

Bubble Sort trong trường hợp xấu nhất (dãy ngược thứ tự) phải thực hiện O(n^2) phép so sánh và O(n^2) phép đổi chỗ để đưa các phần tử về đúng vị trí.

27 / 30

Category: 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

Tags: Bộ đề 02

Câu 27: Cho dãy số I = [8, 4, 6, 2]. Áp dụng Sắp xếp chèn theo thứ tự tăng dần. Dãy I sẽ như thế nào sau khi hoàn thành *bước chèn phần tử thứ 4* (giá trị 2)?

[4, 6, 8, 2]

[2, 8, 4, 6]

[4, 2, 6, 8]

[2, 4, 6, 8]

Ban đầu: [8, 4, 6, 2]. Phần đã sắp xếp ban đầu: [8]. Chèn 4: [4, 8, 6, 2]. Phần đã sắp xếp: [4, 8]. Chèn 6: [4, 6, 8, 2]. Phần đã sắp xếp: [4, 6, 8]. Chèn 2: So sánh 2 với 8 (đổi), 2 với 6 (đổi), 2 với 4 (đổi). Kết quả: [2, 4, 6, 8].

28 / 30

Category: 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

Tags: Bộ đề 02

Câu 28: Tại sao Sắp xếp chọn (Selection Sort) lại có số lần đổi chỗ ít hơn đáng kể so với Sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất?

Vì nó sử dụng kỹ thuật chia để trị.

Vì nó chỉ thực hiện 1 lần đổi chỗ cho mỗi lần duyệt để đưa phần tử nhỏ nhất/lớn nhất về đúng vị trí.

Vì nó chỉ so sánh các phần tử kề nhau.

Vì nó chèn từng phần tử vào đúng vị trí.

Selection Sort chỉ thực hiện 1 lần đổi chỗ cho mỗi lần duyệt (pass) để đưa phần tử đúng vị trí, tổng cộng n-1 đổi chỗ. Bubble Sort có thể đổi chỗ nhiều lần trong mỗi pass nếu các phần tử cần 'nổi' lên xa vị trí cuối cùng của pass đó.

29 / 30

Category: 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

Tags: Bộ đề 02

Câu 29: Xem xét ba thuật toán Sắp xếp chọn, Sắp xếp nổi bọt và Sắp xếp chèn. Thuật toán nào có thể dừng sớm nhất nếu danh sách đầu vào đã được sắp xếp?

Sắp xếp chọn (Selection Sort)

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

Sắp xếp chèn (Insertion Sort)

Sắp xếp nổi bọt (với cờ hiệu) và Sắp xếp chèn.

Bubble Sort (với cờ hiệu kiểm tra swap) và Insertion Sort (best case O(n)) có thể nhận biết danh sách đã sắp xếp và dừng sớm. Selection Sort luôn chạy hết số lần duyệt cố định bất kể dữ liệu.

30 / 30

Category: 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

Tags: Bộ đề 02

Câu 30: Một nhà phát triển cần chọn một thuật toán sắp xếp đơn giản cho một hệ thống nhúng với bộ nhớ rất hạn chế. Yếu tố 'in-place' (sắp xếp tại chỗ, không dùng bộ nhớ phụ đáng kể) là rất quan trọng. Thuật toán nào trong số các thuật toán đơn giản đáp ứng yêu cầu này?

Sắp xếp chọn (Selection Sort) và Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp chèn (Insertion Sort) và Sắp xếp hợp nhất (Merge Sort)

Chỉ có Sắp xếp chọn (Selection Sort)

Cả Sắp xếp chọn, Sắp xếp nổi bọt và Sắp xếp chèn.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Cả ba thuật toán Sắp xếp chọn, Sắp xếp nổi bọt và Sắp xếp chèn đều là các thuật toán sắp xếp tại chỗ (in-place), nghĩa là chúng chỉ cần một lượng bộ nhớ phụ cố định (O(1)) để thực hiện việc sắp xếp, không phụ thuộc vào kích thước danh sách.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 03

1 / 30

Category: 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

Tags: Bộ đề 03

Câu 1: Bài toán sắp xếp (Sorting Problem) trong Tin học có mục tiêu chính là gì?

Sắp xếp các phần tử của một dãy dữ liệu theo một thứ tự nhất định (tăng dần hoặc giảm dần).

Tìm kiếm một phần tử cụ thể trong một dãy dữ liệu.

Thêm hoặc bớt các phần tử vào một dãy dữ liệu.

Kết hợp hai hoặc nhiều dãy dữ liệu thành một.

Câu hỏi kiểm tra kiến thức cơ bản về mục tiêu của bài toán sắp xếp. Đây là câu hỏi ở mức độ Nhận biết.

2 / 30

Category: 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

Tags: Bộ đề 03

Câu 2: Thuật toán Sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên nguyên tắc cơ bản nào?

Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đưa nó về đúng vị trí.

Chia dãy thành hai nửa, sắp xếp từng nửa rồi trộn lại.

So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng không đúng thứ tự.

Lấy từng phần tử từ dãy ban đầu và chèn vào đúng vị trí trong phần đã sắp xếp.

Câu hỏi kiểm tra sự hiểu biết về nguyên tắc hoạt động của Bubble Sort. Đây là câu hỏi ở mức độ Hiểu.

3 / 30

Category: 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

Tags: Bộ đề 03

Câu 3: Cho dãy số A = [5, 1, 4, 2, 8]. Sau khi thực hiện **một lượt (pass)** đầu tiên của thuật toán Sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần, dãy A sẽ trở thành như thế nào?

[1, 2, 4, 5, 8]

[1, 5, 4, 2, 8]

[5, 1, 4, 2, 8]

[1, 4, 2, 5, 8]

Câu hỏi yêu cầu Áp dụng thuật toán Bubble Sort để theo dõi trạng thái của dãy sau lượt duyệt đầu tiên. Lượt 1: (5,1)->(1,5), (5,4)->(4,5), (5,2)->(2,5), (5,8). Dãy cuối lượt 1 là [1, 4, 2, 5, 8].

4 / 30

Category: 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

Tags: Bộ đề 03

Câu 4: Thuật toán Sắp xếp chọn (Selection Sort) hoạt động dựa trên nguyên tắc cơ bản nào?

Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và hoán đổi nó với phần tử ở vị trí đầu tiên của phần chưa sắp xếp.

So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng không đúng thứ tự.

Lấy từng phần tử từ dãy ban đầu và chèn vào đúng vị trí trong phần đã sắp xếp.

Chia dãy thành hai nửa, sắp xếp từng nửa rồi trộn lại.

Câu hỏi kiểm tra sự hiểu biết về nguyên tắc hoạt động của Selection Sort. Đây là câu hỏi ở mức độ Hiểu.

5 / 30

Category: 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

Tags: Bộ đề 03

Câu 5: Cho dãy số B = [6, 2, 8, 3, 1]. Sau khi thực hiện **hai lượt (pass)** đầu tiên của thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, dãy B sẽ trở thành như thế nào?

[1, 2, 3, 6, 8]

[1, 2, 8, 3, 6]

[1, 6, 8, 3, 2]

[6, 2, 8, 3, 1]

Câu hỏi yêu cầu Áp dụng thuật toán Selection Sort để theo dõi trạng thái của dãy sau 2 lượt duyệt. Lượt 1: Tìm min (1), đổi chỗ với B[0]. Dãy: [1, 2, 8, 3, 6]. Lượt 2: Tìm min trong phần còn lại [2, 8, 3, 6] là 2, đổi chỗ với B[1]. Dãy: [1, 2, 8, 3, 6].

6 / 30

Category: 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

Tags: Bộ đề 03

Câu 6: Thuật toán Sắp xếp chèn (Insertion Sort) hoạt động dựa trên nguyên tắc cơ bản nào?

Chia dãy thành hai nửa, sắp xếp từng nửa rồi trộn lại.

Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đưa nó về đúng vị trí.

So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng không đúng thứ tự.

Xây dựng dãy đã sắp xếp bằng cách lần lượt chèn từng phần tử của dãy ban đầu vào đúng vị trí của nó trong phần đã sắp xếp.

Câu hỏi kiểm tra sự hiểu biết về nguyên tắc hoạt động của Insertion Sort. Đây là câu hỏi ở mức độ Hiểu.

7 / 30

Category: 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

Tags: Bộ đề 03

Câu 7: Cho dãy số C = [7, 3, 5, 8, 4]. Sau khi thực hiện **bước chèn phần tử thứ 3** (với phần tử thứ nhất và thứ hai đã được xem như phần đã sắp xếp ban đầu) của thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần, dãy C sẽ trở thành như thế nào?

[3, 5, 4, 7, 8]

[3, 7, 5, 8, 4]

[3, 5, 7, 8, 4]

[7, 3, 5, 8, 4]

Câu hỏi yêu cầu Áp dụng thuật toán Insertion Sort để theo dõi trạng thái của dãy sau khi chèn phần tử thứ 3. Ban đầu, phần đã sắp xếp là [7]. Chèn 3: [3, 7]. Chèn 5: [3, 5, 7]. Dãy sau khi chèn phần tử thứ 3 (giá trị 5) là [3, 5, 7, 8, 4].

8 / 30

Category: 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

Tags: Bộ đề 03

Câu 8: Xét độ phức tạp thời gian trong trường hợp xấu nhất (Worst Case) của các thuật toán sắp xếp đơn giản (Bubble Sort, Selection Sort, Insertion Sort) với N phần tử. Độ phức tạp này thường được biểu diễn bằng ký hiệu Big O là gì?

O(N^2)

O(N log N)

O(N)

O(log N)

Câu hỏi kiểm tra kiến thức về độ phức tạp thời gian của các thuật toán sắp xếp đơn giản trong trường hợp xấu nhất. Cả ba thuật toán này đều có độ phức tạp là O(N^2). Đây là câu hỏi ở mức độ Nhận biết/Hiểu.

9 / 30

Category: 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

Tags: Bộ đề 03

Câu 9: Tại sao các thuật toán sắp xếp đơn giản (như Bubble Sort, Selection Sort, Insertion Sort) lại không hiệu quả cho các tập dữ liệu rất lớn?

Chúng yêu cầu quá nhiều bộ nhớ phụ.

Số lượng phép so sánh và hoán đổi tăng rất nhanh (theo bình phương) khi số lượng phần tử lớn.

Chúng chỉ hoạt động trên các kiểu dữ liệu số.

Chúng cần dữ liệu phải được sắp xếp trước khi bắt đầu.

Câu hỏi yêu cầu Phân tích lý do về hiệu quả của thuật toán dựa trên độ phức tạp. Độ phức tạp O(N^2) có nghĩa là thời gian thực hiện tăng theo bình phương số lượng phần tử, trở nên rất lớn khi N lớn. Đây là câu hỏi ở mức độ Phân tích.

10 / 30

Category: 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

Tags: Bộ đề 03

Câu 10: Trong trường hợp tốt nhất (Best Case) của thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần (khi dãy đã được sắp xếp tăng dần), số lượng phép so sánh gần đúng là bao nhiêu với N phần tử?

O(N^2)

O(N log N)

O(N)

O(1)

Câu hỏi yêu cầu Phân tích hiệu suất của Insertion Sort trong trường hợp tốt nhất. Khi dãy đã sắp xếp, mỗi phần tử mới được chèn chỉ cần so sánh với phần tử cuối cùng của dãy đã sắp xếp (1 phép so sánh) trước khi được đặt vào vị trí ngay sau đó. Tổng cộng khoảng N-1 phép so sánh. Đây là câu hỏi ở mức độ Phân tích.

11 / 30

Category: 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

Tags: Bộ đề 03

Câu 11: So sánh giữa Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp chọn (Selection Sort) trên một dãy có N phần tử. Thuật toán nào có xu hướng thực hiện ít phép hoán đổi (swap) hơn trong trường hợp trung bình và xấu nhất?

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

Sắp xếp chọn (Selection Sort)

Cả hai đều thực hiện số lượng hoán đổi tương đương.

Không thể so sánh được.

Câu hỏi yêu cầu Phân tích và So sánh hiệu suất (số lượng hoán đổi) của hai thuật toán. Bubble Sort có thể thực hiện nhiều hoán đổi trong mỗi lượt. Selection Sort chỉ thực hiện tối đa 1 hoán đổi trong mỗi lượt (đưa phần tử min/max về đúng vị trí). Do đó, Selection Sort thực hiện ít hoán đổi hơn. Đây là câu hỏi ở mức độ Phân tích.

12 / 30

Category: 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

Tags: Bộ đề 03

Câu 12: Thuật toán sắp xếp đơn giản nào có thể hiệu quả nhất (về số phép so sánh) trong trường hợp dãy đầu vào đã được sắp xếp gần hoàn toàn?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Cả ba đều có hiệu quả như nhau trong trường hợp này.

Câu hỏi yêu cầu Vận dụng kiến thức về trường hợp tốt nhất của các thuật toán. Insertion Sort có trường hợp tốt nhất là O(N) khi dãy đã sắp xếp hoặc gần sắp xếp, vì mỗi phần tử mới chỉ cần dịch chuyển một khoảng nhỏ hoặc không cần dịch chuyển. Đây là câu hỏi ở mức độ Vận dụng.

13 / 30

Category: 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

Tags: Bộ đề 03

Câu 13: Xét dãy số D = [4, 1, 3, 2]. Theo dõi thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Sau khi phần tử có giá trị 2 được chèn vào đúng vị trí, dãy D sẽ như thế nào?

[1, 2, 3, 4]

[1, 3, 2, 4]

[4, 1, 3, 2]

[1, 4, 3, 2]

Câu hỏi yêu cầu Áp dụng thuật toán Insertion Sort và theo dõi trạng thái. Ban đầu: [4]. Chèn 1: [1, 4]. Chèn 3: [1, 3, 4]. Chèn 2: So sánh 2 với 4 (dịch 4), so sánh 2 với 3 (dịch 3), so sánh 2 với 1 (không dịch). Chèn 2 vào giữa 1 và 3. Dãy: [1, 2, 3, 4].

14 / 30

Category: 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

Tags: Bộ đề 03

Câu 14: Cho dãy số E = [9, 7, 5, 3, 1]. Khi áp dụng thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, sau lượt thứ nhất, phần tử nào chắc chắn đã ở đúng vị trí cuối cùng của nó trong dãy đã sắp xếp?

Phần tử nhỏ nhất của dãy ban đầu.

Phần tử ở vị trí cuối cùng của dãy ban đầu.

Phần tử ở vị trí đầu tiên của dãy ban đầu.

Không có phần tử nào chắc chắn ở đúng vị trí cuối cùng của nó sau lượt thứ nhất, trừ khi đó là phần tử nhỏ nhất và nó ở vị trí 0 ngay từ đầu.

Câu hỏi yêu cầu Phân tích kết quả của Selection Sort sau một lượt. Lượt 1 của Selection Sort (sắp xếp tăng dần) tìm phần tử nhỏ nhất trong toàn bộ dãy và đổi chỗ nó với phần tử ở vị trí đầu tiên. Sau lượt 1, phần tử nhỏ nhất (1) sẽ ở vị trí 0. Lượt 2 tìm phần tử nhỏ nhất trong phần còn lại và đổi chỗ với vị trí 1, v.v. Phần tử lớn nhất (9) sẽ chỉ được đưa về vị trí cuối cùng sau lượt cuối cùng (lượt N-1). Đây là câu hỏi ở mức độ Phân tích.

15 / 30

Category: 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

Tags: Bộ đề 03

Câu 15: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Bubble, Selection, Insertion) thường được coi là dễ cài đặt nhất cho người mới bắt đầu học?

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

Sắp xếp chèn (Insertion Sort)

Sắp xếp chọn (Selection Sort)

Độ khó cài đặt là như nhau.

Câu hỏi kiểm tra kiến thức về tính thực tiễn/cài đặt của thuật toán. Bubble Sort và Selection Sort thường được coi là đơn giản nhất về mặt ý tưởng và cài đặt cơ bản. Insertion Sort có thể hơi phức tạp hơn một chút do việc dịch chuyển phần tử. Đây là câu hỏi ở mức độ Hiểu.

16 / 30

Category: 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

Tags: Bộ đề 03

Câu 16: Xét thuật toán Sắp xếp nổi bọt (Bubble Sort) trên dãy A = [1, 2, 3, 4, 5] (đã sắp xếp tăng dần). Hỏi cần bao nhiêu phép so sánh và bao nhiêu phép hoán đổi để thuật toán kết thúc nếu nó có cơ chế kiểm tra xem có hoán đổi nào xảy ra trong một lượt không?

(N-1)*N/2 phép so sánh, 0 hoán đổi.

N-1 phép so sánh, 0 hoán đổi.

(N-1)*N/2 phép so sánh, (N-1)*N/2 hoán đổi.

N-1 phép so sánh, N-1 hoán đổi.

Câu hỏi yêu cầu Phân tích hiệu suất Best Case của Bubble Sort có tối ưu. Nếu dãy đã sắp xếp, lượt đầu tiên không có hoán đổi nào xảy ra. Thuật toán có thể dừng lại sau lượt đầu tiên. Số phép so sánh trong lượt đầu tiên là N-1. Số hoán đổi là 0. Đây là câu hỏi ở mức độ Phân tích/Vận dụng.

17 / 30

Category: 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

Tags: Bộ đề 03

Câu 17: Cho dãy số F = [10, 20, 30, 40, 50]. Khi áp dụng thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, số lượng phép hoán đổi sẽ là bao nhiêu?

N/2

N-1

N*(N-1)/2

Câu hỏi yêu cầu Áp dụng và Phân tích số hoán đổi của Selection Sort trong trường hợp Best Case (đã sắp xếp). Selection Sort luôn tìm min/max và đổi chỗ với vị trí đầu tiên của phần chưa sắp xếp. Nếu dãy đã sắp xếp, phần tử min/max đã ở đúng vị trí. Tuy nhiên, thuật toán vẫn thực hiện phép hoán đổi (đổi chỗ phần tử với chính nó, hoặc một phép hoán đổi 'giả' nếu cài đặt không tối ưu). Với N phần tử, có N-1 lượt, mỗi lượt có 1 hoán đổi (có thể là với chính nó). Số hoán đổi là N-1.

18 / 30

Category: 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

Tags: Bộ đề 03

Câu 18: Một dãy số được sắp xếp bằng một trong ba thuật toán đơn giản. Sau một số bước, dãy có dạng [1, 3, 5, 8, 2, 4, 6]. Dựa vào cấu trúc 'phần đã sắp xếp' và 'phần chưa sắp xếp', có thể suy đoán dãy này đang được sắp xếp bằng thuật toán nào?

Sắp xếp chèn (Insertion Sort)

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

Sắp xếp chọn (Selection Sort)

Không thể xác định chỉ với thông tin này.

Câu hỏi yêu cầu Phân tích cấu trúc của dãy để nhận diện thuật toán. Dãy có một phần đầu [1, 3, 5, 8] đã sắp xếp và phần còn lại [2, 4, 6] chưa sắp xếp, nhưng các phần tử trong phần chưa sắp xếp vẫn giữ nguyên thứ tự tương đối so với ban đầu. Đây là đặc điểm của Insertion Sort: xây dựng phần đã sắp xếp từ trái sang. Bubble Sort sẽ đẩy phần tử lớn nhất về cuối. Selection Sort sẽ đặt phần tử nhỏ nhất vào vị trí đầu tiên của phần chưa sắp xếp. Dãy [1, 3, 5, 8, 2, 4, 6] không phù hợp với trạng thái trung gian điển hình của Bubble hoặc Selection Sort (ví dụ: sau k lượt Bubble, k phần tử cuối cùng đã đúng vị trí; sau k lượt Selection, k phần tử đầu tiên đã đúng vị trí). Đây là câu hỏi ở mức độ Phân tích.

19 / 30

Category: 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

Tags: Bộ đề 03

Câu 19: Cho dãy số G = [7, 1, 5, 12, 3, 8]. Theo dõi thuật toán Sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần. Sau khi phần tử có giá trị 12 được 'nổi bọt' đến đúng vị trí cuối cùng của nó, dãy G sẽ như thế nào?

[1, 3, 5, 7, 8, 12]

[1, 5, 3, 7, 8, 12]

[1, 5, 7, 8, 3, 12]

[1, 5, 7, 3, 8, 12]

Câu hỏi yêu cầu Áp dụng và theo dõi Bubble Sort. Phần tử lớn nhất (12) sẽ 'nổi bọt' đến vị trí cuối cùng sau lượt duyệt đầu tiên. Lượt 1: (7,1)->(1,7), (7,5)->(5,7), (7,12), (12,3)->(3,12), (12,8)->(8,12). Dãy sau lượt 1: [1, 5, 7, 3, 8, 12].

20 / 30

Category: 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

Tags: Bộ đề 03

Câu 20: Khi nào thì thuật toán Sắp xếp chọn (Selection Sort) và Sắp xếp nổi bọt (Bubble Sort) có cùng độ phức tạp thời gian trong trường hợp tốt nhất (Best Case)?

Khi dãy đã được sắp xếp tăng dần.

Khi dãy được sắp xếp ngược lại (giảm dần).

Khi tất cả các phần tử trong dãy đều bằng nhau.

Không bao giờ có cùng độ phức tạp thời gian trong trường hợp tốt nhất.

Câu hỏi yêu cầu Phân tích hiệu suất Best Case. Best Case của Bubble Sort (có tối ưu) là O(N). Best Case của Selection Sort luôn là O(N^2) vì nó luôn thực hiện N-1 lượt tìm kiếm min/max, mỗi lượt duyệt phần còn lại. Do đó, chúng không có cùng độ phức tạp trong trường hợp tốt nhất. Đây là câu hỏi ở mức độ Phân tích/Vận dụng.

21 / 30

Category: 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

Tags: Bộ đề 03

Câu 21: Thuật toán sắp xếp nào trong ba thuật toán đơn giản có tính chất là sau mỗi lượt (pass), một phần tử *chắc chắn* đã được đưa về đúng vị trí cuối cùng của nó trong dãy đã sắp xếp?

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

Sắp xếp chèn (Insertion Sort)

Sắp xếp chọn (Selection Sort)

Cả ba thuật toán đều có tính chất này.

Câu hỏi kiểm tra sự hiểu biết sâu hơn về cơ chế của thuật toán. Selection Sort tìm phần tử min/max trong phần chưa sắp xếp và đưa nó về vị trí đầu tiên của phần chưa sắp xếp (tức là vị trí cuối cùng của phần đã sắp xếp). Bubble Sort đưa phần tử lớn nhất (hoặc nhỏ nhất) về cuối/đầu dãy sau mỗi lượt. Insertion Sort chèn một phần tử vào phần đã sắp xếp, không đảm bảo phần tử đó là 'cuối cùng' của dãy sắp xếp. Cả Selection Sort và Bubble Sort (theo cách truyền thống) có tính chất này. Tuy nhiên, Selection Sort *trực tiếp* đưa phần tử min/max về đúng vị trí cuối cùng của nó trong dãy cuối cùng sau mỗi lượt. Bubble Sort đẩy phần tử lớn nhất về cuối sau mỗi lượt, và phần tử đó cũng ở đúng vị trí cuối cùng của nó. Cả 1 và 3 đều đúng theo nghĩa này. Tuy nhiên, Selection Sort thường được mô tả với tính chất này rõ ràng hơn.

22 / 30

Category: 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

Tags: Bộ đề 03

Câu 22: Cho dãy số H = [8, 4, 6, 2]. Theo dõi thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần. Sau khi kết thúc lượt thứ 2, dãy H sẽ như thế nào?

[2, 4, 6, 8]

[2, 8, 6, 4]

[2, 4, 8, 6]

[8, 4, 6, 2]

Câu hỏi yêu cầu Áp dụng thuật toán Selection Sort và theo dõi trạng thái sau 2 lượt. Ban đầu: [8, 4, 6, 2]. Lượt 1: Tìm min (2), đổi chỗ với H[0]. Dãy: [2, 4, 6, 8]. Lượt 2: Tìm min trong phần còn lại [4, 6, 8] là 4, đổi chỗ với H[1]. Dãy: [2, 4, 6, 8].

23 / 30

Category: 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

Tags: Bộ đề 03

Câu 23: So sánh Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp chèn (Insertion Sort) về số lượng phép hoán đổi. Thuật toán nào có thể thực hiện ít phép hoán đổi hơn trong trường hợp trung bình?

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

Sắp xếp chèn (Insertion Sort)

Cả hai đều thực hiện số lượng hoán đổi tương đương.

Không thể so sánh được.

Câu hỏi yêu cầu Phân tích và So sánh số hoán đổi. Bubble Sort thực hiện hoán đổi liên tục để đưa phần tử lớn hơn về phía cuối. Insertion Sort thực hiện dịch chuyển các phần tử sang phải để tạo chỗ trống và chỉ thực hiện 1 hoán đổi (hoặc gán) để chèn phần tử vào vị trí đúng. Trong trường hợp trung bình, Insertion Sort thường th??c hiện ít hoán đổi/di chuyển dữ liệu hơn Bubble Sort. Đây là câu hỏi ở mức độ Phân tích/Vận dụng.

24 / 30

Category: 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

Tags: Bộ đề 03

Câu 24: Một lập trình viên cần chọn một thuật toán sắp xếp đơn giản để sắp xếp một danh sách rất nhỏ (ví dụ, dưới 20 phần tử) trong một ứng dụng nhúng có bộ nhớ hạn chế. Thuật toán nào trong ba thuật toán đơn giản có thể là lựa chọn hợp lý nhất, xét về sự đơn giản và hiệu quả trên dữ liệu nhỏ?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Cả ba đều phù hợp như nhau.

Câu hỏi yêu cầu Vận dụng kiến thức để giải quyết vấn đề thực tế. Trên dữ liệu nhỏ, sự khác biệt về độ phức tạp O(N^2) không quá lớn. Các thuật toán đơn giản đều không yêu cầu bộ nhớ phụ đáng kể (in-place). Insertion Sort thường hiệu quả hơn trên dữ liệu gần sắp xếp và có thể có ít hoán đổi hơn. Bubble Sort và Selection Sort đơn giản. Tuy nhiên, Insertion Sort có thể là lựa chọn tốt vì hiệu quả tốt trên dữ liệu gần sắp xếp và chi phí thấp trên dữ liệu nhỏ. Cả ba đều là lựa chọn hợp lý, nhưng Insertion Sort thường được ưu tiên hơn một chút cho dữ liệu nhỏ hoặc gần sắp xếp. Selection Sort ít hoán đổi nhất. Bubble Sort đơn giản nhất. Câu hỏi này hơi mở, nhưng Insertion Sort thường được nhấn mạnh là hiệu quả cho dữ liệu nhỏ. Tuy nhiên, Selection Sort với số hoán đổi ít nhất cũng là một điểm mạnh trong môi trường bộ nhớ hạn chế (giảm thao tác ghi).

25 / 30

Category: 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

Tags: Bộ đề 03

Câu 25: Cho dãy số I = [5, 3, 1]. Theo dõi thuật toán Sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần. Cần bao nhiêu phép so sánh để dãy được sắp xếp hoàn toàn?

Câu hỏi yêu cầu Áp dụng và tính số phép so sánh của Bubble Sort (không có tối ưu dừng sớm). N=3. Lượt 1: so sánh (5,3), (5,1). 2 so sánh. Dãy: [3, 1, 5]. Lượt 2: so sánh (3,1). 1 so sánh. Dãy: [1, 3, 5]. Lượt 3: 0 so sánh (phần chưa sắp xếp còn 1 phần tử). Tổng cộng 2 + 1 = 3 so sánh. Hoặc công thức (N-1)*N/2 = (3-1)*3/2 = 3.

26 / 30

Category: 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

Tags: Bộ đề 03

Câu 26: Cho dãy số J = [5, 3, 1]. Theo dõi thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần. Cần bao nhiêu phép hoán đổi để dãy được sắp xếp hoàn toàn?

Câu hỏi yêu cầu Áp dụng và tính số hoán đổi của Selection Sort. N=3. Ban đầu: [5, 3, 1]. Lượt 1: Tìm min (1), đổi chỗ với J[0]. Dãy: [1, 3, 5]. 1 hoán đổi (5 và 1). Lượt 2: Tìm min trong [3, 5] là 3, đổi chỗ với J[1]. Dãy: [1, 3, 5]. 1 hoán đổi (3 và 3). Tổng cộng 2 hoán đổi. Hoặc N-1 hoán đổi.

27 / 30

Category: 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

Tags: Bộ đề 03

Câu 27: Cho dãy số K = [5, 3, 1]. Theo dõi thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Cần bao nhiêu phép so sánh để dãy được sắp xếp hoàn toàn?

Câu hỏi yêu cầu Áp dụng và tính số phép so sánh của Insertion Sort. N=3. Ban đầu: [5]. Chèn 3: so sánh 3 với 5 (1 so sánh), dịch 5, chèn 3. Dãy: [3, 5]. Chèn 1: so sánh 1 với 5 (1 so sánh), dịch 5, so sánh 1 với 3 (1 so sánh), dịch 3, chèn 1. Dãy: [1, 3, 5]. Tổng cộng 1 + (1+1) = 3 phép so sánh.

28 / 30

Category: 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

Tags: Bộ đề 03

Câu 28: Thuật toán sắp xếp nào có thể được mô tả là 'chia dãy thành hai phần: một phần đã sắp xếp và một phần chưa sắp xếp, và lần lượt đưa phần tử từ phần chưa sắp xếp sang phần đã sắp xếp sao cho nó vẫn giữ được tính thứ tự'?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Cả ba thuật toán.

Câu hỏi kiểm tra khả năng nhận diện thuật toán qua mô tả nguyên tắc hoạt động. Mô tả này khớp với cách hoạt động của Insertion Sort. Đây là câu hỏi ở mức độ Hiểu/Phân tích.

29 / 30

Category: 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

Tags: Bộ đề 03

Câu 29: Xét một dãy số có N phần tử. Trong trường hợp xấu nhất, thuật toán Sắp xếp chọn (Selection Sort) sẽ thực hiện khoảng bao nhiêu phép so sánh?

N log N

N-1

N*(N-1)/2

Câu hỏi yêu cầu Phân tích hiệu suất Worst Case của Selection Sort. Selection Sort luôn thực hiện N-1 lượt. Lượt i (từ 0 đến N-2) tìm min trong N-i phần tử còn lại, cần (N-i-1) phép so sánh. Tổng số so sánh = (N-1) + (N-2) + ... + 1 + 0 = N*(N-1)/2. Đây là câu hỏi ở mức độ Phân tích.

30 / 30

Category: 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

Tags: Bộ đề 03

Câu 30: Đặc điểm nào sau đây là điểm chung của cả ba thuật toán sắp xếp đơn giản (Bubble Sort, Selection Sort, Insertion Sort) khi nói về yêu cầu bộ nhớ?

Chúng đều là các thuật toán 'tại chỗ' (in-place) và chỉ cần một lượng bộ nhớ phụ cố định.

Chúng đều yêu cầu một mảng phụ có kích thước bằng mảng ban đầu.

Yêu cầu bộ nhớ của chúng phụ thuộc tuyến tính vào số lượng phần tử (O(N)).

Chúng yêu cầu bộ nhớ phụ theo cấp logarit (O(log N)).

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Câu hỏi kiểm tra kiến thức về yêu cầu bộ nhớ của các thuật toán. Cả ba thuật toán đơn giản này đều là thuật toán sắp xếp 'tại chỗ' (in-place), nghĩa là chúng chỉ cần một lượng bộ nhớ phụ cố định (thường là một vài biến tạm) không phụ thuộc vào kích thước của mảng. Đây là câu hỏi ở mức độ Hiểu.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 04

1 / 30

Category: 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

Tags: Bộ đề 04

Câu 1: Khi bạn sử dụng công cụ tìm kiếm trên một website thương mại điện tử để tìm một sản phẩm cụ thể (ví dụ: 'điện thoại Samsung Galaxy S23'), 'miền dữ liệu' của bài toán tìm kiếm này là gì?

Chỉ các từ khóa bạn gõ vào ô tìm kiếm.

Toàn bộ danh mục sản phẩm và thông tin liên quan có trên website.

Các kết quả tìm kiếm được hiển thị trên màn hình.

Tất cả các website bán hàng trên internet.

Miền dữ liệu trong bài toán tìm kiếm là tập hợp tất cả các đối tượng hoặc thông tin mà thuật toán có thể duyệt qua để tìm kiếm. Trong trường hợp này, đó là toàn bộ danh mục sản phẩm (bao gồm thông tin, hình ảnh, mô tả) có trên website đó.

2 / 30

Category: 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

Tags: Bộ đề 04

Câu 2: Thuật toán tìm kiếm tuần tự (Sequential Search) hoạt động dựa trên nguyên tắc cơ bản nào?

Chia đôi danh sách và tìm kiếm trong một nửa.

Sắp xếp danh sách trước khi tìm kiếm.

Duyệt qua từng phần tử của danh sách theo thứ tự.

So sánh phần tử cần tìm với phần tử ở giữa danh sách.

Tìm kiếm tuần tự là thuật toán đơn giản nhất, nó kiểm tra từng phần tử trong danh sách theo một thứ tự nhất định (thường là từ đầu đến cuối) cho đến khi tìm thấy phần tử cần hoặc duyệt hết danh sách.

3 / 30

Category: 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

Tags: Bộ đề 04

Câu 3: Cho dãy số A = [4, 12, 7, 25, 18, 31, 9]. Nếu bạn tìm kiếm giá trị K = 18 bằng thuật toán tìm kiếm tuần tự, bạn sẽ cần duyệt qua bao nhiêu phần tử trước khi tìm thấy K?

Thuật toán tìm kiếm tuần tự duyệt từ đầu dãy. Để tìm 18, ta kiểm tra: 4 (không), 12 (không), 7 (không), 25 (không), 18 (có). Đã duyệt qua 5 phần tử.

4 / 30

Category: 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

Tags: Bộ đề 04

Câu 4: Trong trường hợp nào, thuật toán tìm kiếm tuần tự đạt hiệu suất tốt nhất (số bước duyệt ít nhất)?

Phần tử cần tìm là phần tử đầu tiên của dãy.

Phần tử cần tìm là phần tử cuối cùng của dãy.

Phần tử cần tìm không tồn tại trong dãy.

Dãy dữ liệu có kích thước nhỏ.

Trường hợp tốt nhất xảy ra khi phần tử cần tìm là phần tử đầu tiên của dãy, vì thuật toán chỉ cần một bước so sánh duy nhất.

5 / 30

Category: 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

Tags: Bộ đề 04

Câu 5: Thuật toán tìm kiếm nhị phân (Binary Search) chỉ có thể áp dụng trực tiếp một cách hiệu quả khi dữ liệu đầu vào có đặc điểm gì?

Dữ liệu có kích thước nhỏ.

Dữ liệu chứa các số nguyên dương.

Dữ liệu đã được sắp xếp theo một thứ tự.

Dữ liệu không chứa các phần tử trùng lặp.

Điều kiện tiên quyết quan trọng nhất để áp dụng tìm kiếm nhị phân là danh sách 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).

6 / 30

Category: 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

Tags: Bộ đề 04

Câu 6: Cho dãy số đã sắp xếp tăng dần A = [10, 20, 30, 40, 50, 60, 70, 80, 90]. Bạn cần tìm giá trị K = 70 bằng thuật toán tìm kiếm nhị phân. Giá trị của phần tử được kiểm tra ở bước **thứ hai** là bao nhiêu?

Dãy có 9 phần tử (chỉ số 0-8). Bước 1: low=0, high=8, mid=(0+8)//2=4. Kiểm tra A[4]=50. K=70 > 50. Tìm kiếm trong nửa phải (chỉ số 5-8). Bước 2: low=5, high=8, mid=(5+8)//2=6. Kiểm tra A[6]=70. Tìm thấy. Giá trị kiểm tra ở bước thứ hai là 70.

7 / 30

Category: 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

Tags: Bộ đề 04

Câu 7: Với một dãy số đã sắp xếp có N phần tử, số bước duyệt tối đa (trong trường hợp xấu nhất) của thuật toán tìm kiếm nhị phân xấp xỉ là bao nhiêu?

log₂(N)

N/2

N * log₂(N)

Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân là O(log N). Trong trường hợp xấu nhất, số bước duyệt tỉ lệ thuận với logarit cơ số 2 của số lượng phần tử.

8 / 30

Category: 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

Tags: Bộ đề 04

Câu 8: Bạn có một tệp văn bản chứa hàng triệu dòng dữ liệu, mỗi dòng là một giao dịch bán hàng. Các giao dịch này được lưu trữ theo thứ tự thời gian (không sắp xếp theo bất kỳ trường nào khác). Bạn cần tìm tất cả các giao dịch của một khách hàng cụ thể dựa trên ID khách hàng. Thuật toán tìm kiếm nào phù hợp nhất để thực hiện công việc này?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân (vì dữ liệu lớn).

Cần phải sắp xếp lại dữ liệu theo ID khách hàng rồi mới tìm.

Cả hai thuật toán đều không phù hợp.

Danh sách dữ liệu không được sắp xếp theo ID khách hàng. Do đó, tìm kiếm nhị phân không thể áp dụng trực tiếp. Tìm kiếm tuần tự là lựa chọn duy nhất có thể duyệt qua từng giao dịch để kiểm tra ID.

9 / 30

Category: 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

Tags: Bộ đề 04

Câu 9: So sánh tốc độ giữa tìm kiếm tuần tự và tìm kiếm nhị phân trên một dãy dữ liệu rất lớn (ví dụ 1 tỷ phần tử) đã được sắp xếp. Nhận định nào sau đây là đúng nhất?

Tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân vì nó đơn giản hơn.

Tìm kiếm nhị phân nhanh hơn đáng kể so với tìm kiếm tuần tự.

Tốc độ của cả hai thuật toán là tương đương.

Tốc độ phụ thuộc vào phần tử cần tìm, đôi khi tuần tự nhanh hơn.

Với dữ liệu lớn đã sắp xếp, tìm kiếm nhị phân (O(log N)) nhanh hơn đáng kể so với tìm kiếm tuần tự (O(N)). Ví dụ, với 1 tỷ phần tử, log₂(10⁹) khoảng 30 bước, trong khi tuần tự có thể cần tới 1 tỷ bước trong trường hợp xấu nhất.

10 / 30

Category: 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

Tags: Bộ đề 04

Câu 10: Khi sử dụng thuật toán tìm kiếm tuần tự để tìm một phần tử K trong dãy A mà K không có trong A, thuật toán sẽ dừng lại khi nào?

Ngay lập tức khi nhận ra K không tồn tại.

Sau khi duyệt đến cuối dãy mà không tìm thấy K.

Khi số bước duyệt vượt quá số lượng phần tử của dãy.

Khi tìm thấy một phần tử khác có giá trị gần K nhất.

Nếu phần tử cần tìm không có trong dãy, thuật toán tìm kiếm tuần tự sẽ phải duyệt qua tất cả các phần tử từ đầu đến cuối dãy và chỉ dừng lại khi đã kiểm tra hết mà không tìm thấy.

11 / 30

Category: 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

Tags: Bộ đề 04

Câu 11: Khi sử dụng thuật toán tìm kiếm nhị phân để tìm một phần tử K trong dãy A (đã sắp xếp) mà K không có trong A, thuật toán sẽ dừng lại khi nào?

Khi phạm vi tìm kiếm (khoảng giữa low và high) trở thành rỗng.

Sau khi duyệt hết toàn bộ dãy.

Khi số bước duyệt vượt quá log₂(N).

Khi tìm thấy một phần tử khác có giá trị gần K nhất.

Trong tìm kiếm nhị phân, phạm vi tìm kiếm được thu hẹp sau mỗi bước. Nếu phần tử không tồn tại, quá trình thu hẹp sẽ dẫn đến việc chỉ số 'low' vượt qua chỉ số 'high' (hoặc ngược lại, tùy cách cài đặt), khi đó phạm vi tìm kiếm trở thành rỗng và thuật toán dừng lại.

12 / 30

Category: 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

Tags: Bộ đề 04

Câu 12: Giả sử bạn có một danh sách rất lớn (hàng trăm nghìn mục) các hồ sơ bệnh nhân, được lưu trữ theo thứ tự alphabet của tên. Bạn cần thường xuyên tìm kiếm hồ sơ của một bệnh nhân cụ thể. Thuật toán tìm kiếm nào là lựa chọn tối ưu nhất cho tác vụ này?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai đều có hiệu quả tương đương.

Cần sử dụng một cấu trúc dữ liệu khác không phải danh sách.

Danh sách đã được sắp xếp theo tên, và kích thước rất lớn. Tìm kiếm nhị phân tận dụng được tính sắp xếp để tìm kiếm nhanh hơn đáng kể so với tìm kiếm tuần tự trên dữ liệu lớn.

13 / 30

Category: 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

Tags: Bộ đề 04

Câu 13: Bạn có một bộ sưu tập các bức ảnh kỹ thuật số được lưu trữ trong một thư mục trên máy tính. Các tệp ảnh không được sắp xếp theo bất kỳ thứ tự nào cụ thể (ví dụ: theo tên, ngày chụp). Bạn muốn tìm một bức ảnh cụ thể dựa trên tên tệp mà bạn nhớ mang máng. Hệ thống tệp của máy tính nhiều khả năng sẽ sử dụng nguyên tắc tìm kiếm nào để duyệt qua các tệp trong thư mục?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Tìm kiếm theo chỉ mục băm (Hashing).

Một thuật toán sắp xếp trước khi tìm kiếm.

Dữ liệu (các tệp trong thư mục) không được sắp xếp theo tên tệp trong cấu trúc lưu trữ vật lý. Để tìm một tệp cụ thể, hệ thống cần duyệt qua danh sách các tệp có trong thư mục theo một thứ tự nào đó (không nhất thiết phải là thứ tự sắp xếp logic mà người dùng thấy), về cơ bản là tìm kiếm tuần tự trên danh sách đó.

14 / 30

Category: 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

Tags: Bộ đề 04

Câu 14: Khi một dãy dữ liệu đã sắp xếp chứa nhiều phần tử có giá trị giống nhau, nếu tìm kiếm nhị phân tìm thấy phần tử cần tìm K tại một vị trí, vị trí đó có đảm bảo là vị trí xuất hiện **đầu tiên** của K trong dãy không?

Luôn luôn là vị trí đầu tiên.

Luôn luôn là vị trí cuối cùng.

Có thể là bất kỳ vị trí nào của K trong dãy.

Thuật toán tìm kiếm nhị phân không hoạt động với dữ liệu trùng lặp.

Thuật toán tìm kiếm nhị phân tìm một vị trí bất kỳ trong dãy con hiện tại nơi giá trị bằng K được tìm thấy. Nếu có nhiều phần tử K liền kề nhau, thuật toán có thể trả về vị trí của bất kỳ phần tử K nào trong dãy con đang xét, không nhất thiết là vị trí đầu tiên của K trong toàn bộ dãy ban đầu.

15 / 30

Category: 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

Tags: Bộ đề 04

Câu 15: Giả sử bạn cần thực hiện 1000 lần tìm kiếm trên một danh sách dữ liệu lớn (1 triệu phần tử) chưa được sắp xếp. Chi phí để sắp xếp danh sách này là đáng kể (ví dụ: tương đương 100.000 bước duyệt tuần tự). Chiến lược nào sau đây có khả năng mang lại tổng thời gian thực hiện (sắp xếp + tìm kiếm) hiệu quả nhất?

Sử dụng tìm kiếm tuần tự cho cả 1000 lần tìm kiếm.

Sắp xếp danh sách một lần rồi sử dụng tìm kiếm nhị phân cho 1000 lần tìm kiếm.

Sử dụng tìm kiếm nhị phân trực tiếp trên danh sách chưa sắp xếp.

Chia danh sách thành các phần nhỏ hơn và tìm kiếm tuần tự trên từng phần.

Chi phí sắp xếp một lần (100.000 bước) sau đó thực hiện 1000 lần tìm kiếm nhị phân (mỗi lần khoảng log₂(10⁶) ≈ 20 bước, tổng 1000 * 20 = 20.000 bước) là 100.000 + 20.000 = 120.000 bước. So với 1000 lần tìm kiếm tuần tự (mỗi lần trung bình 1.000.000/2 = 500.000 bước, tổng 1000 * 500.000 = 500.000.000 bước), chiến lược sắp xếp rồi tìm kiếm nhị phân hiệu quả hơn rất nhiều.

16 / 30

Category: 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

Tags: Bộ đề 04

Câu 16: Trong thuật toán tìm kiếm nhị phân, nếu giá trị cần tìm K lớn hơn giá trị của phần tử ở giữa dãy con hiện tại, thuật toán sẽ tiếp tục tìm kiếm ở phần nào của dãy con đó?

Nửa bên phải của phần tử giữa (bao gồm cả phần tử ngay sau phần tử giữa).

Nửa bên trái của phần tử giữa (bao gồm cả phần tử ngay trước phần tử giữa).

Toàn bộ dãy con hiện tại.

Chỉ phần tử ở giữa đó.

Trong dãy đã sắp xếp tăng dần, nếu K lớn hơn phần tử ở giữa, K chỉ có thể nằm ở nửa bên phải của phần tử giữa. Do đó, thuật toán loại bỏ nửa bên trái và tiếp tục tìm kiếm trong nửa bên phải.

17 / 30

Category: 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

Tags: Bộ đề 04

Câu 17: Cho dãy A = [1, 5, 8, 12, 16, 19, 23]. Tìm giá trị K = 15 bằng thuật toán tìm kiếm nhị phân. Các phần tử nào sẽ được kiểm tra theo thứ tự cho đến khi thuật toán dừng lại?

12, 16, 19

16, 12, 19

12, 19, 16

Dãy có 7 phần tử (chỉ số 0-6). B1: low=0, high=6, mid=(0+6)//2=3. Check A[3]=12. K=15 > 12. Tìm trong nửa phải (chỉ số 4-6). B2: low=4, high=6, mid=(4+6)//2=5. Check A[5]=19. K=15 < 19. Tìm trong nửa trái (chỉ số 4-4). B3: low=4, high=4, mid=(4+4)//2=4. Check A[4]=16. K=15 < 16. high=mid-1=3. low=4, high=3. low > high. Dừng. Các phần tử đã kiểm tra là 12, 19, 16.

18 / 30

Category: 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

Tags: Bộ đề 04

Câu 18: Điều gì xảy ra trong thuật toán tìm kiếm nhị phân khi giá trị cần tìm K bằng giá trị của phần tử ở giữa dãy con hiện tại?

Thuật toán tiếp tục tìm kiếm ở cả hai nửa của dãy con.

Thuật toán dừng lại và báo cáo không tìm thấy.

Thuật toán tiếp tục tìm kiếm ở nửa bên phải.

Thuật toán dừng lại và báo cáo tìm thấy phần tử tại vị trí đó.

Đây là trường hợp tìm thấy phần tử. Thuật toán sẽ trả về chỉ số của phần tử đó và kết thúc.

19 / 30

Category: 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

Tags: Bộ đề 04

Câu 19: Khi tìm kiếm thông tin trên Internet bằng các công cụ tìm kiếm (ví dụ: Google, Bing), 'miền dữ liệu' được tìm kiếm là gì?

Tập hợp các trang web và nội dung đã được các công cụ tìm kiếm lập chỉ mục.

Chỉ các trang web có chứa chính xác các từ khóa bạn tìm.

Toàn bộ thông tin có trên tất cả các máy tính kết nối Internet.

Các kết quả được hiển thị trên trang kết quả tìm kiếm.

Các công cụ tìm kiếm lập chỉ mục (index) một lượng khổng lồ các trang web và nội dung công khai trên Internet. Miền dữ liệu tìm kiếm chính là tập hợp các thông tin đã được lập chỉ mục này, không phải toàn bộ Internet tức thời hay chỉ một phần nhỏ.

20 / 30

Category: 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

Tags: Bộ đề 04

Câu 20: Thuật toán tìm kiếm nào sau đây có thể được áp dụng hiệu quả nhất để tìm kiếm một từ khóa trong một văn bản dài (ví dụ: một cuốn sách điện tử) mà không cần bất kỳ quá trình tiền xử lý (như sắp xếp) nào trên văn bản đó?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai đều không phù hợp.

Một thuật toán sắp xếp kết hợp tìm kiếm.

Văn bản không được sắp xếp theo từ khóa. Tìm kiếm tuần tự là thuật toán đơn giản và phù hợp để duyệt qua từng từ hoặc từng ký tự trong văn bản để tìm kiếm từ khóa.

21 / 30

Category: 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

Tags: Bộ đề 04

Câu 21: Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp xấu nhất là O(N), trong đó N là số lượng phần tử. Điều này có nghĩa là gì?

Số bước thực hiện tăng theo logarit của N.

Số bước thực hiện không phụ thuộc vào N.

Số bước thực hiện tăng tỉ lệ thuận với N.

Số bước thực hiện giảm khi N tăng.

Độ phức tạp O(N) (tuyến tính) nghĩa là số bước thực hiện (thời gian) tăng tỉ lệ thuận với kích thước của dữ liệu đầu vào (N). Trong trường hợp xấu nhất của tìm kiếm tuần tự (phần tử ở cuối hoặc không có), thuật toán phải duyệt qua tất cả N phần tử.

22 / 30

Category: 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

Tags: Bộ đề 04

Câu 22: So với tìm kiếm tuần tự, ưu điểm chính của tìm kiếm nhị phân khi áp dụng trên dữ liệu phù hợp là gì?

Đơn giản hơn trong cài đặt.

Có thể áp dụng cho mọi loại dữ liệu (đã sắp xếp hoặc chưa sắp xếp).

Đảm bảo tìm thấy tất cả các vị trí của phần tử trùng lặp.

Tốc độ tìm kiếm nhanh hơn đáng kể với dữ liệu lớn đã được sắp xếp.

Ưu điểm lớn nhất của tìm kiếm nhị phân là tốc độ tìm kiếm nhanh hơn đáng kể (độ phức tạp logarit so với tuyến tính) trên các tập dữ liệu lớn đã được sắp xếp.

23 / 30

Category: 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

Tags: Bộ đề 04

Câu 23: Cho dãy số A = [5, 12, 8, 20, 15]. Bạn muốn tìm tất cả các phần tử lớn hơn 10 bằng tìm kiếm tuần tự. Các phần tử nào sẽ được tìm thấy?

5, 12, 20, 15

12, 20, 15

12, 20

Chỉ 20

Duyệt tuần tự: 5 (không), 12 (lớn hơn 10), 8 (không), 20 (lớn hơn 10), 15 (lớn hơn 10). Các phần tử lớn hơn 10 là 12, 20, 15.

24 / 30

Category: 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

Tags: Bộ đề 04

Câu 24: Một hệ thống quản lý kho hàng lưu trữ thông tin về hàng triệu sản phẩm theo mã sản phẩm (một chuỗi ký tự duy nhất cho mỗi sản phẩm). Mã sản phẩm được gán ngẫu nhiên và không theo bất kỳ thứ tự nào. Khi nhân viên muốn tìm kiếm thông tin chi tiết của một sản phẩm dựa vào mã, hệ thống nên sử dụng thuật toán tìm kiếm nào trên danh sách mã sản phẩm?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cần sắp xếp lại danh sách mã sản phẩm trước.

Một thuật toán sắp xếp nhanh.

Mã sản phẩm không được sắp xếp. Tìm kiếm nhị phân không thể áp dụng. Tìm kiếm tuần tự là lựa chọn khả thi để duyệt qua danh sách mã sản phẩm.

25 / 30

Category: 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

Tags: Bộ đề 04

Câu 25: Khái niệm 'miền dữ liệu' trong bài toán tìm kiếm giúp chúng ta xác định điều gì?

Tốc độ thực hiện của thuật toán tìm kiếm.

Số lượng phần tử cần tìm.

Tập hợp tất cả các đối tượng hoặc thông tin có thể được tìm kiếm.

Vị trí của phần tử cần tìm trong dữ liệu đầu vào.

Miền dữ liệu xác định phạm vi toàn bộ các đối tượng hoặc thông tin mà thuật toán tìm kiếm có thể xem xét. Nó định nghĩa không gian mà trong đó kết quả tìm kiếm (nếu có) sẽ tồn tại.

26 / 30

Category: 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

Tags: Bộ đề 04

Câu 26: Tìm kiếm nhị phân hoạt động bằng cách liên tục loại bỏ một nửa phạm vi tìm kiếm. Điều này đạt được nhờ vào việc so sánh phần tử cần tìm K với phần tử nào trong dãy con hiện tại?

Phần tử nằm chính giữa dãy con hiện tại.

Phần tử đầu tiên của dãy con hiện tại.

Phần tử cuối cùng của dãy con hiện tại.

Một phần tử ngẫu nhiên trong dãy con hiện tại.

Nguyên tắc của tìm kiếm nhị phân là so sánh K với phần tử nằm chính giữa dãy con hiện tại. Kết quả so sánh (K nhỏ hơn, lớn hơn, hoặc bằng) cho phép loại bỏ một nửa dãy con.

27 / 30

Category: 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

Tags: Bộ đề 04

Câu 27: Cho dãy số đã sắp xếp tăng dần A = [2, 5, 8, 12, 16]. Tìm giá trị K = 6 bằng thuật toán tìm kiếm nhị phân. Các giá trị của các biến 'low' và 'high' sẽ thay đổi như thế nào cho đến khi thuật toán dừng lại?

(0,4) -> (2,4) -> (3,4)

(0,4) -> (0,1) -> (0,0)

(0,4) -> (0,1) -> (1,1) -> (2,1)

(0,4) -> (2,4) -> (3,4) -> (4,4)

Dãy có 5 phần tử (chỉ số 0-4). B1: low=0, high=4, mid=2. Check A[2]=8. K=6 < 8. high=mid-1=1. B2: low=0, high=1, mid=0. Check A[0]=2. K=6 > 2. low=mid+1=1. B3: low=1, high=1, mid=1. Check A[1]=5. K=6 > 5. low=mid+1=2. B4: low=2, high=1. low > high. Dừng. low và high thay đổi từ (0,4) -> (0,1) -> (1,1) -> (2,1).

28 / 30

Category: 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

Tags: Bộ đề 04

Câu 28: Nhận định nào sau đây là **sai** khi so sánh tìm kiếm tuần tự và tìm kiếm nhị phân?

Tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp.

Tìm kiếm nhị phân thường nhanh hơn tìm kiếm tuần tự trên dữ liệu lớn đã sắp xếp.

Tìm kiếm tuần tự có thể áp dụng cho dữ liệu chưa được sắp xếp.

Tìm kiếm tuần tự chỉ hiệu quả khi dữ liệu có kích thước rất lớn.

Tìm kiếm tuần tự có thể áp dụng cho cả dữ liệu đã sắp xếp và chưa sắp xếp. Đây là một ưu điểm về tính linh hoạt của nó, mặc dù không hiệu quả bằng nhị phân trên dữ liệu lớn đã sắp xếp.

29 / 30

Category: 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

Tags: Bộ đề 04

Câu 29: Trong một danh sách gồm 1024 phần tử đã sắp xếp, trong trường hợp xấu nhất, thuật toán tìm kiếm nhị phân cần tối đa bao nhiêu bước so sánh để xác định một phần tử có tồn tại trong danh sách hay không?

1024

512

Số bước tối đa của tìm kiếm nhị phân trên N phần tử là log₂(N) + 1 (hoặc xấp xỉ log₂(N)). Với N = 1024 = 2¹⁰, số bước là log₂(1024) = 10.

30 / 30

Category: 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

Tags: Bộ đề 04

Câu 30: Bạn đang viết chương trình tìm kiếm một từ trong một từ điển điện tử có hàng trăm nghìn từ đã được sắp xếp theo thứ tự alphabet. Kiểu dữ liệu và yêu cầu tìm kiếm này phù hợp nhất với thuật toán nào?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai đều có hiệu quả tương đương.

Một thuật toán sắp xếp.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Dữ liệu (các từ trong từ điển) đã được sắp xếp theo thứ tự alphabet và có kích thước lớn. Đây là trường hợp lý tưởng để áp dụng tìm kiếm nhị phân, mang lại tốc độ truy vấn rất nhanh.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 05

1 / 30

Category: 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

Tags: Bộ đề 05

Câu 1: Thuật toán sắp xếp nào sau đây hoạt động bằng cách lặp đi lặp lại việc so sánh các cặp phần tử liền kề và đổi chỗ nếu chúng không đúng thứ tự?

Thuật toán sắp xếp chọn (Selection Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp chèn (Insertion Sort)

Thuật toán sắp xếp nhanh (Quick Sort)

2 / 30

Category: 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

Tags: Bộ đề 05

Câu 2: Khi sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp dãy số [5, 2, 8, 1, 9] theo thứ tự tăng dần, dãy số sẽ trông như thế nào sau khi hoàn thành **lượt duyệt đầu tiên** (tìm phần tử nhỏ nhất và đưa về đầu)?

[2, 5, 8, 1, 9]

[1, 2, 5, 8, 9]

[1, 2, 8, 5, 9]

[5, 2, 8, 1, 9]

3 / 30

Category: 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

Tags: Bộ đề 05

Câu 3: Thuật toán sắp xếp chèn (Insertion Sort) hoạt động dựa trên nguyên tắc chính nào?

Chia dãy thành hai nửa và sắp xếp riêng lẻ

Tìm phần tử nhỏ nhất và đặt vào đúng vị trí

So sánh các cặp phần tử liền kề và đổi chỗ

Xây dựng dãy đã sắp xếp từng bước bằng cách chèn phần tử vào đúng vị trí trong phần đã sắp xếp

4 / 30

Category: 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

Tags: Bộ đề 05

Câu 4: Cho dãy số [7, 4, 1, 9, 3]. Khi áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần, dãy số sẽ như thế nào sau khi kết thúc **lượt duyệt thứ hai**?

[4, 1, 7, 3, 9]

[1, 4, 3, 7, 9]

[1, 4, 7, 3, 9]

[7, 4, 1, 9, 3]

5 / 30

Category: 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

Tags: Bộ đề 05

Câu 5: Thuật toán sắp xếp nào sau đây có hiệu suất tốt nhất (trung bình) khi áp dụng cho một dãy số **gần như đã được sắp xếp**?

Thuật toán sắp xếp chọn (Selection Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp chèn (Insertion Sort)

Tất cả đều như nhau với dãy gần sắp xếp

6 / 30

Category: 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

Tags: Bộ đề 05

Câu 6: Độ phức tạp thời gian trong trường hợp xấu nhất của các thuật toán sắp xếp đơn giản như Sắp xếp nổi bọt, Sắp xếp chọn, Sắp xếp chèn là bao nhiêu?

O(log n)

O(n^2)

O(n log n)

O(n)

7 / 30

Category: 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

Tags: Bộ đề 05

Câu 7: Khi sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp một dãy gồm N phần tử, số lần **đổi chỗ** (swap) tối đa có thể xảy ra là bao nhiêu?

N * (N-1) / 2

N * (N-1)

N^2

N - 1

8 / 30

Category: 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

Tags: Bộ đề 05

Câu 8: Dãy số [3, 1, 4, 1, 5, 9, 2, 6]. Áp dụng thuật toán sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Dãy số sẽ như thế nào sau khi phần tử có giá trị 5 được chèn vào đúng vị trí của nó?

[1, 3, 4, 1, 5, 9, 2, 6]

[1, 1, 3, 4, 5, 9, 2, 6]

[1, 3, 4, 5, 1, 9, 2, 6]

[3, 1, 4, 1, 5, 9, 2, 6]

9 / 30

Category: 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

Tags: Bộ đề 05

Câu 9: Đặc điểm nào sau đây là **không đúng** về thuật toán sắp xếp nổi bọt (Bubble Sort)?

So sánh và đổi chỗ các phần tử liền kề.

Trong mỗi lượt, phần tử lớn nhất (hoặc nhỏ nhất) chưa được sắp xếp sẽ 'nổi' lên cuối dãy chưa sắp xếp.

Hiệu quả nhất khi dãy số đã được sắp xếp ngược.

Có thể dừng sớm nếu không có cặp phần tử nào được đổi chỗ trong một lượt duyệt.

10 / 30

Category: 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

Tags: Bộ đề 05

Câu 10: Giả sử bạn có một danh sách rất lớn các bản ghi cần sắp xếp, và bộ nhớ là một hạn chế nghiêm trọng. Thuật toán sắp xếp nào trong các thuật toán đơn giản sau đây thường được ưu tiên vì nó thực hiện sắp xếp **tại chỗ** (in-place) và không yêu cầu thêm không gian bộ nhớ đáng kể?

Merge Sort

Quick Sort

Heap Sort

Cả Sắp xếp nổi bọt, Sắp xếp chọn và Sắp xếp chèn đều là thuật toán tại chỗ.

11 / 30

Category: 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

Tags: Bộ đề 05

Câu 11: Cho dãy số [10, 5, 3, 8, 1]. Khi sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần, phần tử nào sẽ nằm ở vị trí đầu tiên sau khi hoàn thành **lượt duyệt thứ hai**?

12 / 30

Category: 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

Tags: Bộ đề 05

Câu 12: Trong thuật toán sắp xếp chèn (Insertion Sort), sau khi phần tử th?? `i` được chèn vào đúng vị trí trong dãy con đã sắp xếp `A[0...i-1]`, dãy con `A[0...i]` sẽ có đặc điểm gì?

Tất cả các phần tử nhỏ hơn `A[i]` đều nằm ở bên trái nó.

Dãy con `A[0...i]` đã được sắp xếp hoàn chỉnh.

Phần tử `A[i]` chắc chắn là phần tử lớn nhất trong dãy con `A[0...i]`.

Số lần đổi chỗ luôn bằng `i`.

13 / 30

Category: 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

Tags: Bộ đề 05

Câu 13: Xét thuật toán sắp xếp nổi bọt (Bubble Sort) trên dãy [6, 5, 4, 3, 2, 1]. Trong **lượt duyệt đầu tiên**, có bao nhiêu cặp phần tử liền kề được so sánh và đổi chỗ?

14 / 30

Category: 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

Tags: Bộ đề 05

Câu 14: Tại sao thuật toán sắp xếp chọn (Selection Sort) lại có số lần đổi chỗ (swap) ít hơn đáng kể so với Sắp xếp nổi bọt (Bubble Sort) hoặc Sắp xếp chèn (Insertion Sort) trong trường hợp xấu nhất?

Nó chỉ thực hiện một lần đổi chỗ cho mỗi lượt duyệt chính (đưa phần tử nhỏ nhất về đúng vị trí).

Nó không bao giờ thực hiện đổi chỗ.

Nó chỉ so sánh các phần tử ở xa nhau.

Nó sử dụng thêm bộ nhớ để lưu trữ vị trí cần đổi chỗ.

15 / 30

Category: 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

Tags: Bộ đề 05

Câu 15: Trong trường hợp tốt nhất (dãy đã được sắp xếp tăng dần), thuật toán sắp xếp nào trong các thuật toán đơn giản sau đây có thể kết thúc với số bước ít nhất (hoặc độ phức tạp thời gian tốt nhất)?

Thuật toán sắp xếp chọn (Selection Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp chèn (Insertion Sort)

Cả Sắp xếp nổi bọt (với cờ hiệu) và Sắp xếp chèn

16 / 30

Category: 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

Tags: Bộ đề 05

Câu 16: Một lập trình viên cần sắp xếp một danh sách nhỏ (dưới 20 phần tử). Anh ta nên chọn thuật toán sắp xếp đơn giản nào để tối ưu hóa tốc độ lập trình và dễ hiểu, thay vì hiệu quả chạy chương trình trên dữ liệu lớn?

Quick Sort

Merge Sort

Heap Sort

Bất kỳ thuật toán đơn giản nào như Bubble, Selection, hoặc Insertion Sort đều phù hợp.

17 / 30

Category: 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

Tags: Bộ đề 05

Câu 17: Xét dãy số [4, 2, 7, 1, 5]. Sử dụng Sắp xếp nổi bọt (Bubble Sort) tăng dần. Dãy số sau khi kết thúc **lượt duyệt thứ nhất** (bubble up phần tử lớn nhất) là:

[2, 4, 1, 5, 7]

[4, 2, 7, 1, 5]

[1, 2, 4, 5, 7]

[4, 2, 1, 5, 7]

18 / 30

Category: 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

Tags: Bộ đề 05

Câu 18: Thuật toán sắp xếp nào có cách tiếp cận tương tự như cách con người sắp xếp một bộ bài (cầm từng lá bài lên và chèn vào đúng vị trí trong phần bài đã xếp)?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp nhanh (Quick Sort)

19 / 30

Category: 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

Tags: Bộ đề 05

Câu 19: Dãy số [8, 3, 6, 1, 4]. Sử dụng Sắp xếp chọn (Selection Sort) tăng dần. Dãy số sau khi kết thúc **lượt duyệt thứ ba** (đã sắp xếp 3 phần tử đầu tiên) là:

[1, 3, 4, 6, 8]

[1, 3, 4, 8, 6]

[1, 3, 6, 8, 4]

[1, 4, 6, 8, 3]

20 / 30

Category: 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

Tags: Bộ đề 05

Câu 20: Thuật toán sắp xếp đơn giản nào sau đây có số lần **so sánh** là cố định, không phụ thuộc vào trạng thái ban đầu của dãy (dù đã sắp xếp hay chưa)?

Thuật toán sắp xếp chọn (Selection Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp chèn (Insertion Sort)

Cả Sắp xếp nổi bọt và Sắp xếp chèn

21 / 30

Category: 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

Tags: Bộ đề 05

Câu 21: Khi nào thì nên cân nhắc sử dụng các thuật toán sắp xếp đơn giản như Sắp xếp nổi bọt, Sắp xếp chọn hoặc Sắp xếp chèn thay vì các thuật toán phức tạp hơn như Quick Sort hay Merge Sort?

Khi cần sắp xếp một lượng dữ liệu rất lớn.

Khi yêu cầu hiệu suất chạy chương trình cực kỳ cao trên mọi loại dữ liệu.

Khi kích thước dữ liệu nhỏ hoặc cần triển khai thuật toán một cách nhanh chóng và đơn giản.

Khi dữ liệu luôn ở trạng thái sắp xếp ngược hoàn toàn.

22 / 30

Category: 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

Tags: Bộ đề 05

Câu 22: Dãy số [5, 2, 4, 6, 1, 3]. Sử dụng Sắp xếp chèn (Insertion Sort) tăng dần. Dãy số sau khi hoàn thành việc chèn phần tử có giá trị 6 (phần tử thứ 4 ban đầu) là:

[1, 2, 4, 5, 6, 3]

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 1, 6, 3]

[2, 4, 5, 6, 1, 3] (Phần tử 6 đã ở đúng vị trí so với dãy con [2, 4, 5])

23 / 30

Category: 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

Tags: Bộ đề 05

Câu 23: Phát biểu nào sau đây mô tả đúng về việc 'sắp xếp tại chỗ' (in-place sorting)?

Thuật toán chỉ sử dụng một lượng không gian bộ nhớ phụ trợ cố định, không phụ thuộc vào kích thước của dữ liệu đầu vào (hoặc chỉ một lượng rất nhỏ so với dữ liệu).

Thuật toán yêu cầu tạo một bản sao hoàn chỉnh của dữ liệu gốc.

Thứ tự tương đối của các phần tử có giá trị bằng nhau được giữ nguyên sau khi sắp xếp.

Thuật toán chỉ hoạt động trên dữ liệu đã được lưu trữ trên đĩa cứng.

24 / 30

Category: 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

Tags: Bộ đề 05

Câu 24: Đối với một dãy số có N phần tử, trong trường hợp xấu nhất, thuật toán sắp xếp nổi bọt (Bubble Sort) sẽ thực hiện khoảng bao nhiêu phép so sánh?

N * log(N)

N * (N-1) / 2

N - 1

25 / 30

Category: 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

Tags: Bộ đề 05

Câu 25: Dãy số [9, 7, 5, 3, 1]. Sử dụng Sắp xếp chèn (Insertion Sort) tăng dần. Dãy số sẽ như thế nào sau khi hoàn thành việc chèn phần tử có giá trị 3 (phần tử thứ 4 ban đầu)?

[3, 5, 7, 9, 1]

[9, 7, 5, 3, 1]

[1, 3, 5, 7, 9]

[7, 5, 3, 9, 1]

26 / 30

Category: 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

Tags: Bộ đề 05

Câu 26: Sự khác biệt cơ bản trong cách tìm phần tử để đưa về đúng vị trí giữa Sắp xếp chọn (Selection Sort) và Sắp xếp chèn (Insertion Sort) là gì?

Selection Sort tìm phần tử lớn nhất, còn Insertion Sort tìm phần tử nhỏ nhất.

Selection Sort tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ về đầu phần chưa sắp xếp; Insertion Sort lấy phần tử đầu tiên của phần chưa sắp xếp và chèn vào đúng vị trí trong phần đã sắp xếp.

Selection Sort chỉ hoạt động với số nguyên, còn Insertion Sort hoạt động với mọi loại dữ liệu.

Selection Sort sử dụng đệ quy, còn Insertion Sort sử dụng vòng lặp.

27 / 30

Category: 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

Tags: Bộ đề 05

Câu 27: Một thuật toán sắp xếp được gọi là 'ổn định' (stable) nếu nó giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau. Trong các thuật toán đơn giản, thuật toán nào sau đây là **không** ổn định?

Thuật toán sắp xếp chọn (Selection Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp chèn (Insertion Sort)

Cả ba thuật toán đều ổn định.

28 / 30

Category: 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

Tags: Bộ đề 05

Câu 28: Xét dãy số [2, 8, 3, 5]. Sử dụng Sắp xếp nổi bọt (Bubble Sort) tăng dần. Sau lượt duyệt thứ nhất, dãy số là [2, 3, 5, 8]. Có thể kết luận gì về trạng thái sắp xếp của dãy tại thời điểm này?

Dãy đã được sắp xếp hoàn chỉnh.

Phần tử đầu tiên đã ở đúng vị trí cuối cùng của nó.

Tất cả các phần tử đã di chuyển đến vị trí cuối cùng của chúng.

Phần tử cuối cùng (8) đã ở đúng vị trí cuối cùng của nó.

29 / 30

Category: 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

Tags: Bộ đề 05

Câu 29: Khi sắp xếp một danh sách gồm các đối tượng phức tạp (ví dụ: danh sách sinh viên, mỗi sinh viên có nhiều thuộc tính), việc sử dụng thuật toán sắp xếp chọn (Selection Sort) có thể có một ưu điểm nhỏ so với Sắp xếp nổi bọt hoặc Sắp xếp chèn trong một số trường hợp thực tế. Ưu điểm đó là gì?

Số lần so sánh ít hơn.

Độ phức tạp thời gian tốt hơn.

Số lần đổi chỗ (swap) ít hơn, điều này có thể quan trọng nếu việc đổi chỗ các đối tượng lớn tốn kém.

Luôn ổn định (stable).

30 / 30

Category: 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

Tags: Bộ đề 05

Câu 30: Cho dãy số [1, 2, 3, 4, 5]. Khi áp dụng thuật toán sắp xếp chèn (Insertion Sort) tăng dần, số lần đổi chỗ (swap) xảy ra là bao nhiêu?

N * (N-1) / 2

Không thể xác định được.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 06

1 / 30

Category: 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

Tags: Bộ đề 06

Câu 1: Trong bài toán tìm kiếm, khái niệm 'miền dữ liệu' (hay không gian tìm kiếm) được hiểu là gì?

Tập hợp các thuật toán có thể sử dụng để giải quyết bài toán.

Kết quả mong muốn mà thuật toán tìm kiếm trả về.

Tập hợp tất cả các đối tượng hoặc thông tin có thể chứa đối tượng cần tìm.

Số lượng bước thực hiện của thuật toán tìm kiếm.

2 / 30

Category: 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

Tags: Bộ đề 06

Câu 2: Một người muốn tìm số điện thoại của một cửa hàng trong danh bạ điện thoại được sắp xếp theo tên. Thuật toán tìm kiếm nào sau đây *không* phù hợp nhất cho tình huống này nếu danh bạ rất lớn?

Tìm kiếm tuần tự (Sequential Search)

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

Cả hai thuật toán đều phù hợp như nhau.

Tùy thuộc vào số lượng chữ cái trong tên cửa hàng.

3 / 30

Category: 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

Tags: Bộ đề 06

Câu 3: Cho dãy số A = [15, 8, 22, 5, 12, 35, 18] và cần tìm giá trị K = 12 bằng thuật toán tìm kiếm tuần tự. Thuật toán sẽ thực hiện bao nhiêu phép so sánh tối đa với các phần tử trong dãy để tìm thấy K?

4 / 30

Category: 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

Tags: Bộ đề 06

Câu 4: Thuật toán tìm kiếm nhị phân yêu cầu dữ liệu đầu vào phải có đặc điểm gì để hoạt động hiệu quả?

Chỉ chứa các số nguyên dương.

Đã được sắp xếp theo một thứ tự nhất định (tăng dần hoặc giảm dần).

Có số lượng phần tử là lũy thừa của 2.

Các phần tử có giá trị duy nhất, không trùng lặp.

5 / 30

Category: 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

Tags: Bộ đề 06

Câu 5: Cho dãy số đã sắp xếp tăng dần: A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Sử dụng tìm kiếm nhị phân để tìm giá trị K = 23. Chỉ số của phần tử được so sánh trong lần lặp *thứ hai* của thuật toán là bao nhiêu? (Giả sử chỉ số bắt đầu từ 0).

6 / 30

Category: 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

Tags: Bộ đề 06

Câu 6: Xét trường hợp tốt nhất (best-case scenario) cho thuật toán tìm kiếm tuần tự trên một danh sách gồm N phần tử. Số phép so sánh cần thực hiện là bao nhiêu?

N/2

log₂N

7 / 30

Category: 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

Tags: Bộ đề 06

Câu 7: Xét trường hợp xấu nhất (worst-case scenario) cho thuật toán tìm kiếm nhị phân trên một danh sách gồm N phần tử đã được sắp xếp. Độ phức tạp thời gian (số phép so sánh) thường được biểu diễn bằng ký hiệu Big O là gì?

O(1)

O(N)

O(log N)

O(N²)

8 / 30

Category: 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

Tags: Bộ đề 06

Câu 8: Ưu điểm chính của thuật toán tìm kiếm nhị phân so với tìm kiếm tuần tự khi áp dụng cho danh sách *lớn và đã được sắp xếp* là gì?

Không cần biết trước kích thước của danh sách.

Tốc độ tìm kiếm nhanh hơn đáng kể.

Đơn giản hơn trong cài đặt.

Có thể tìm kiếm trên dữ liệu chưa sắp xếp.

9 / 30

Category: 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

Tags: Bộ đề 06

Câu 9: Khi nào thì thuật toán tìm kiếm tuần tự có thể là lựa chọn tốt hơn hoặc duy nhất có thể áp dụng so với tìm kiếm nhị phân?

Khi cần tìm nhiều phần tử cùng lúc.

Khi danh sách dữ liệu rất lớn.

Khi cần tìm phần tử ở cuối danh sách.

Khi danh sách dữ liệu chưa được sắp xếp.

10 / 30

Category: 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

Tags: Bộ đề 06

Câu 10: Cho dãy số A = [10, 20, 30, 40, 50] và cần tìm K = 25 bằng tìm kiếm nhị phân. Sau khi thuật toán kết thúc, điều gì sẽ xảy ra?

Thuật toán sẽ báo lỗi vì K không phải là bội số của 10.

Thuật toán sẽ trả về chỉ số của phần tử gần nhất với 25 (ví dụ 20 hoặc 30).

Thuật toán sẽ kết thúc và báo rằng không tìm thấy phần tử K trong dãy.

Thuật toán sẽ tiếp tục lặp vô hạn.

11 / 30

Category: 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

Tags: Bộ đề 06

Câu 11: Giả sử bạn có một danh sách 1024 phần tử đã được sắp xếp. Trong trường hợp xấu nhất, tìm kiếm nhị phân cần tối đa bao nhiêu lần so sánh để xác định một phần tử có tồn tại trong danh sách hay không?

512

1024

12 / 30

Category: 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

Tags: Bộ đề 06

Câu 12: Trong thuật toán tìm kiếm nhị phân, nếu phần tử tại vị trí giữa lớn hơn giá trị cần tìm, thì phạm vi tìm kiếm tiếp theo sẽ được giới hạn ở đâu?

Nửa bên trái của danh sách (bao gồm cả phần tử giữa nếu bằng giá trị cần tìm).

Nửa bên phải của danh sách (không bao gồm phần tử giữa).

Toàn bộ danh sách lại từ đầu.

Chỉ phần tử tại vị trí giữa.

13 / 30

Category: 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

Tags: Bộ đề 06

Câu 13: Bài toán 'Tìm tất cả các bài viết về biến đổi khí hậu trên một trang web tin tức' có thể được coi là một bài toán tìm kiếm. Miền dữ liệu trong trường hợp này là gì?

Chỉ các bài viết có tiêu đề chứa cụm từ 'biến đổi khí hậu'.

Số lượng bài viết về biến đổi khí hậu.

Các trang web khác nói về biến đổi khí hậu.

Tất cả các bài viết có trên trang web tin tức đó.

14 / 30

Category: 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

Tags: Bộ đề 06

Câu 14: Thuật toán tìm kiếm tuần tự hoạt động dựa trên nguyên tắc cơ bản nào?

Chia danh sách thành hai nửa.

So sánh phần tử cần tìm với phần tử ở giữa danh sách.

Duyệt qua từng phần tử trong danh sách từ đầu đến cuối cho đến khi tìm thấy hoặc hết danh sách.

Sử dụng chỉ mục để truy cập trực tiếp phần tử.

15 / 30

Category: 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

Tags: Bộ đề 06

Câu 15: So sánh độ phức tạp thời gian trung bình của tìm kiếm tuần tự và tìm kiếm nhị phân trên một danh sách N phần tử (tìm kiếm thành công).

Tìm kiếm tuần tự là O(N), tìm kiếm nhị phân là O(log N).

Tìm kiếm tuần tự là O(log N), tìm kiếm nhị phân là O(N).

Cả hai đều là O(N).

Cả hai đều là O(log N).

16 / 30

Category: 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

Tags: Bộ đề 06

Câu 16: Giả sử bạn có một danh sách 100 phần tử chưa được sắp xếp. Bạn muốn tìm một giá trị cụ thể. Thuật toán nào sau đây là lựa chọn phù hợp *ngay lập tức* mà không cần thao tác tiền xử lý?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai đều cần sắp xếp trước.

Không có thuật toán nào phù hợp.

17 / 30

Category: 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

Tags: Bộ đề 06

Câu 17: Trong tìm kiếm nhị phân trên dãy A = [5, 10, 15, 20, 25, 30, 35], tìm K = 30. Lần so sánh đầu tiên sẽ kiểm tra phần tử nào? (Giả sử chỉ số từ 0)

5 (chỉ số 0)

15 (chỉ số 2)

20 (chỉ số 3)

35 (chỉ số 6)

18 / 30

Category: 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

Tags: Bộ đề 06

Câu 18: Tiếp theo Câu 17, sau lần so sánh đầu tiên, phạm vi tìm kiếm tiếp theo cho K = 30 sẽ là các chỉ số nào?

[0, 2]

[0, 3]

[4, 6]

[3, 6]

19 / 30

Category: 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

Tags: Bộ đề 06

Câu 19: Mục tiêu cuối cùng của bài toán tìm kiếm là gì?

Sắp xếp dữ liệu.

Xác định xem một đối tượng cụ thể có tồn tại trong miền dữ liệu hay không và, nếu có, trả về thông tin về nó (ví dụ: vị trí).

Đếm số lượng đối tượng trong miền dữ liệu.

Thay đổi giá trị của các đối tượng trong miền dữ liệu.

20 / 30

Category: 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

Tags: Bộ đề 06

Câu 20: Tại sao việc sắp xếp dữ liệu lại là bước tiền xử lý quan trọng đối với thuật toán tìm kiếm nhị phân?

Để có thể loại bỏ một nửa miền tìm kiếm sau mỗi lần so sánh với phần tử giữa.

Để đảm bảo các phần tử có giá trị duy nhất.

Để giảm số lượng phần tử trong danh sách.

Để dễ dàng cài đặt thuật toán hơn.

21 / 30

Category: 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

Tags: Bộ đề 06

Câu 21: Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp xấu nhất trên danh sách N phần tử là O(N). Điều này có nghĩa là gì?

Thời gian thực hiện tăng gấp đôi khi số lượng phần tử tăng gấp đôi.

Thời gian thực hiện không phụ thuộc vào số lượng phần tử.

Thời gian thực hiện tăng tỷ lệ thuận với số lượng phần tử N.

Thời gian thực hiện tăng rất nhanh khi số lượng phần tử tăng.

22 / 30

Category: 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

Tags: Bộ đề 06

Câu 22: Một thư viện lưu trữ thông tin sách trong một cơ sở dữ liệu. Thủ thư muốn tìm một cuốn sách dựa trên mã số ISBN (một chuỗi ký tự duy nhất cho mỗi sách). Mã số ISBN không được sắp xếp. Thuật toán tìm kiếm nào phù hợp nhất?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cần sắp xếp theo ISBN rồi dùng tìm kiếm nhị phân.

Chỉ có thể tìm bằng cách duyệt thủ công.

23 / 30

Category: 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

Tags: Bộ đề 06

Câu 23: Cho dãy số A = [1, 3, 6, 10, 15, 21, 28]. Sử dụng tìm kiếm nhị phân để tìm K = 21. Chỉ số của phần tử được so sánh trong lần lặp *cuối cùng* (khi tìm thấy) là bao nhiêu? (Giả sử chỉ số từ 0)

24 / 30

Category: 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

Tags: Bộ đề 06

Câu 24: Sự khác biệt cơ bản nhất trong cách tiếp cận giữa tìm kiếm tuần tự và tìm kiếm nhị phân là gì?

Một thuật toán sử dụng vòng lặp, thuật toán kia sử dụng đệ quy.

Một thuật toán kiểm tra từng phần tử một cách tuyến tính, thuật toán kia loại bỏ một phần đáng kể miền tìm kiếm sau mỗi bước so sánh.

Một thuật toán chỉ dùng cho số, thuật toán kia dùng cho mọi loại dữ liệu.

Một thuật toán nhanh, thuật toán kia chậm.

25 / 30

Category: 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

Tags: Bộ đề 06

Câu 25: Khi nào thì tìm kiếm tuần tự đạt hiệu quả tốt nhất (ít bước nhất) trong trường hợp tìm thấy phần tử?

Khi phần tử cần tìm nằm ở vị trí đầu tiên của danh sách.

Khi phần tử cần tìm nằm ở vị trí cuối cùng của danh sách.

Khi danh sách chỉ có một phần tử.

Khi danh sách rất dài.

26 / 30

Category: 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

Tags: Bộ đề 06

Câu 26: Một tệp văn bản chứa 1000 dòng. Mỗi dòng chứa một từ duy nhất. Bạn muốn tìm xem một từ cụ thể có xuất hiện trong tệp hay không. Nếu tệp chưa được sắp xếp, thuật toán tìm kiếm tuần tự sẽ phải đọc và so sánh tối đa bao nhiêu dòng trong trường hợp xấu nhất?

500

999

1000

27 / 30

Category: 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

Tags: Bộ đề 06

Câu 27: Nếu tệp văn bản trong Câu 26 được sắp xếp theo thứ tự bảng chữ cái, và bạn sử dụng tìm kiếm nhị phân, số dòng tối đa cần đọc và so sánh trong trường hợp xấu nhất sẽ giảm đáng kể. Con số đó xấp xỉ bao nhiêu?

Khoảng 10 (log₂1000 ≈ 9.96)

Khoảng 500

Khoảng 100

Vẫn là 1000 vì phải đọc cả tệp.

28 / 30

Category: 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

Tags: Bộ đề 06

Câu 28: Trong thuật toán tìm kiếm nhị phân, biến 'mid' (chỉ số giữa) thường được tính như thế nào từ 'low' (chỉ số đầu) và 'high' (chỉ số cuối) của phạm vi tìm kiếm hiện tại?

mid = high - low

mid = low * high / 2

mid = (low + high) / 2 (lấy phần nguyên nếu cần)

mid = low + high

29 / 30

Category: 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

Tags: Bộ đề 06

Câu 29: Bài toán 'Tìm quyển sách có tiêu đề 'Đắc Nhân Tâm' trong kho sách của cửa hàng A' có thể được mô tả như thế nào về mặt bài toán tìm kiếm?

Tìm một phần tử trong một danh sách ngẫu nhiên.

Tìm một đối tượng cụ thể ('quyển sách Đắc Nhân Tâm') trong một miền dữ liệu ('kho sách của cửa hàng A').

Sắp xếp các quyển sách theo tiêu đề.

Đếm số lượng sách trong kho.

30 / 30

Category: 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

Tags: Bộ đề 06

Câu 30: Khi nào thì việc áp dụng thuật toán tìm kiếm nhị phân *không* mang lại lợi ích đáng kể về tốc độ so với tìm kiếm tuần tự?

Khi danh sách dữ liệu rất lớn.

Khi phần tử cần tìm nằm ở cuối danh sách.

Khi cần tìm kiếm nhiều lần trên cùng một danh sách đã sắp xếp.

Khi danh sách dữ liệu rất nhỏ (ví dụ dưới 10 phần tử).

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 07

1 / 30

Category: 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

Tags: Bộ đề 07

Câu 1: Mục đích chính của các thuật toán sắp xếp là gì?

Giảm dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu.

Sắp xếp các phần tử theo một thứ tự nhất định (tăng dần hoặc giảm dần).

Tìm kiếm một phần tử cụ thể trong danh sách nhanh hơn.

Mã hóa dữ liệu để bảo mật thông tin.

2 / 30

Category: 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

Tags: Bộ đề 07

Câu 2: Cho dãy số A = [6, 3, 8, 1, 5]. Áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp dãy A theo thứ tự tăng dần. Dãy A sẽ như thế nào sau LƯỢT duyệt (pass) đầu tiên?

[1, 3, 5, 6, 8]

[3, 8, 6, 5, 1]

[3, 6, 1, 5, 8]

[6, 3, 8, 1, 5]

3 / 30

Category: 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

Tags: Bộ đề 07

Câu 3: Thuật toán sắp xếp nào sau đây hoạt động dựa trên nguyên tắc liên tục tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa được sắp xếp và đưa nó về đúng vị trí ở đầu phần đã sắp xếp?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp nhanh (Quick Sort)

4 / 30

Category: 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

Tags: Bộ đề 07

Câu 4: Cho dãy số B = [7, 4, 9, 2, 5]. Áp dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp dãy B theo thứ tự tăng dần. Dãy B sẽ như thế nào sau khi 2 phần tử ĐẦU TIÊN đã nằm đúng vị trí sau các bước chọn và hoán đổi?

[2, 4, 5, 7, 9]

[2, 7, 9, 4, 5]

[4, 2, 9, 7, 5]

[2, 4, 9, 7, 5]

5 / 30

Category: 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

Tags: Bộ đề 07

Câu 5: Thuật toán sắp xếp nào sau đây hoạt động bằng cách xây dựng mảng đã sắp xếp từng bước một, lấy các phần tử từ mảng ban đầu và chèn chúng vào đúng vị trí trong phần mảng con đã được sắp xếp?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp trộn (Merge Sort)

6 / 30

Category: 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

Tags: Bộ đề 07

Câu 6: Cho dãy số C = [5, 2, 4, 6, 1, 3]. Áp dụng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp dãy C theo thứ tự tăng dần. Dãy C sẽ như thế nào sau khi phần tử '4' được chèn vào đúng vị trí trong phần mảng con đã sắp xếp?

[2, 4, 5, 6, 1, 3]

[2, 5, 4, 6, 1, 3]

[5, 2, 4, 6, 1, 3]

[2, 4, 5, 1, 6, 3]

7 / 30

Category: 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

Tags: Bộ đề 07

Câu 7: Đối với một dãy số có N phần tử đã được sắp xếp theo đúng thứ tự cần sắp (tăng dần), thuật toán sắp xếp nổi bọt (Bubble Sort) sẽ thực hiện số lần so sánh và hoán đổi là bao nhiêu trong trường hợp TỐT NHẤT?

Khoảng N*N/2 so sánh và N*N/2 hoán đổi.

Khoảng N*N/4 so sánh và N*N/4 hoán đổi.

N-1 so sánh và N-1 hoán đổi.

N-1 so sánh và 0 hoán đổi.

8 / 30

Category: 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

Tags: Bộ đề 07

Câu 8: Đối với một dãy số có N phần tử, thuật toán sắp xếp chọn (Selection Sort) sẽ thực hiện số lần hoán đổi (swap) là bao nhiêu trong trường hợp XẤU NHẤT?

0 lần.

N-1 lần.

Khoảng N*N lần.

Số lần hoán đổi phụ thuộc vào thứ tự ban đầu của dãy.

9 / 30

Category: 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

Tags: Bộ đề 07

Câu 9: Thuật toán sắp xếp chèn (Insertion Sort) đặc biệt hiệu quả (thực hiện ít phép so sánh và hoán đổi) trong trường hợp nào?

Dãy số đã gần như được sắp xếp.

Dãy số có thứ tự ngược hoàn toàn.

Dãy số chứa rất nhiều phần tử trùng lặp.

Dãy số có kích thước rất lớn (hàng triệu phần tử).

10 / 30

Category: 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

Tags: Bộ đề 07

Câu 10: So sánh thuật toán sắp xếp nổi bọt (Bubble Sort) và sắp xếp chọn (Selection Sort) cho một dãy có N phần tử. Nhận định nào sau đây là ĐÚNG về số lần hoán đổi (swap) trong trường hợp xấu nhất?

Bubble Sort luôn thực hiện ít hoán đổi hơn Selection Sort.

Selection Sort luôn thực hiện ít hoán đổi hơn Bubble Sort.

Số lần hoán đổi của cả hai thuật toán là tương đương trong trường hợp xấu nhất.

Selection Sort không thực hiện hoán đổi, chỉ di chuyển phần tử.

11 / 30

Category: 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

Tags: Bộ đề 07

Câu 11: Cho dãy số D = [10, 20, 30, 40, 50]. Nếu áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp dãy D theo thứ tự tăng dần, điều gì sẽ xảy ra trong lượt duyệt đầu tiên?

Phần tử 50 sẽ được chuyển về vị trí đầu tiên.

Sẽ có nhiều cặp phần tử được hoán đổi vị trí.

Không có bất kỳ cặp phần tử kề nhau nào bị hoán đổi.

Thuật toán sẽ dừng lại ngay lập tức vì dãy đã sắp xếp.

12 / 30

Category: 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

Tags: Bộ đề 07

Câu 12: Khi nào thì thuật toán sắp xếp chèn (Insertion Sort) có hiệu suất kém nhất?

Dãy số có kích thước nhỏ.

Dãy số chứa nhiều phần tử trùng lặp.

Dãy số đã được sắp xếp tăng dần.

Dãy số được sắp xếp theo thứ tự ngược với thứ tự cần sắp.

13 / 30

Category: 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

Tags: Bộ đề 07

Câu 13: Trong thuật toán sắp xếp chọn (Selection Sort), số lần so sánh phần tử là bao nhiêu đối với một dãy có N phần tử?

Khoảng N so sánh.

Khoảng log(N) so sánh.

Khoảng N*(N-1)/2 so sánh.

Số lần so sánh phụ thuộc vào thứ tự ban đầu của dãy.

14 / 30

Category: 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

Tags: Bộ đề 07

Câu 14: Một lập trình viên cần sắp xếp một danh sách liên kết (linked list) thay vì mảng (array). Trong ba thuật toán sắp xếp đơn giản đã học (Bubble, Selection, Insertion), thuật toán nào có thể gặp khó khăn hoặc kém hiệu quả hơn khi làm việc với danh sách liên kết so với mảng?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Cả ba thuật toán đều gặp khó khăn như nhau.

15 / 30

Category: 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

Tags: Bộ đề 07

Câu 15: Thuật toán sắp xếp nào sau đây được coi là 'ổn định' (stable)? (Thuật toán ổn định là thuật toán giữ nguyên thứ tự tương đối của các phần tử bằng nhau.)

Sắp xếp chọn (Selection Sort)

Sắp xếp nhanh (Quick Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp vun đống (Heap Sort)

16 / 30

Category: 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

Tags: Bộ đề 07

Câu 16: Cho dãy số E = [4, 1, 3, 2]. Áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp dãy E tăng dần. Dãy E sẽ như thế nào sau lượt duyệt thứ hai?

[1, 2, 3, 4]

[1, 3, 2, 4]

[4, 1, 3, 2]

[1, 4, 3, 2]

17 / 30

Category: 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

Tags: Bộ đề 07

Câu 17: Cho dãy số F = [8, 5, 2, 6]. Áp dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp dãy F tăng dần. Dãy F sẽ như thế nào sau khi phần tử thứ hai (tính từ đầu) đã được đặt đúng vị trí?

[2, 5, 6, 8]

[2, 8, 5, 6]

[5, 2, 8, 6]

[2, 5, 8, 6]

18 / 30

Category: 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

Tags: Bộ đề 07

Câu 18: Cho dãy số G = [7, 1, 5, 12, 3]. Áp dụng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp dãy G tăng dần. Dãy G sẽ như thế nào sau khi phần tử '12' được xử lý và chèn vào đúng vị trí?

[1, 5, 7, 12, 3]

[1, 5, 7, 3, 12]

[1, 7, 5, 12, 3]

[7, 1, 5, 12, 3]

19 / 30

Category: 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

Tags: Bộ đề 07

Câu 19: Tại sao thuật toán sắp xếp nổi bọt (Bubble Sort) thường không được sử dụng cho các tập dữ liệu lớn trong thực tế?

Nó đòi hỏi quá nhiều bộ nhớ.

Nó có hiệu suất kém (chậm) đối với dữ liệu lớn.

Nó không thể sắp xếp được các loại dữ liệu khác ngoài số nguyên.

Nó cần dữ liệu phải được sắp xếp một phần trước khi bắt đầu.

20 / 30

Category: 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

Tags: Bộ đề 07

Câu 20: Trong các thuật toán sắp xếp đơn giản (Bubble, Selection, Insertion), thuật toán nào có số lần hoán đổi (swap) ít nhất trong trường hợp xấu nhất?

Sắp xếp chọn (Selection Sort)

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

Sắp xếp chèn (Insertion Sort)

Cả ba thuật toán có số hoán đổi tương đương.

21 / 30

Category: 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

Tags: Bộ đề 07

Câu 21: Thuật toán sắp xếp chèn (Insertion Sort) có thể được mô phỏng giống với cách con người sắp xếp một bộ bài trên tay như thế nào?

Chia bộ bài thành hai nửa và sắp xếp từng nửa.

Liên tục tìm lá bài nhỏ nhất và đưa nó về đầu bộ bài.

Giữ một phần bài đã sắp xếp và chèn từng lá bài mới vào đúng vị trí.

So sánh từng cặp lá bài kề nhau và đổi chỗ nếu sai thứ tự.

22 / 30

Category: 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

Tags: Bộ đề 07

Câu 22: Khi phân tích hiệu quả của thuật toán sắp xếp, chúng ta thường quan tâm đến hai yếu tố chính là số phép so sánh và số phép hoán đổi (hoặc di chuyển). Tại sao số phép hoán đổi lại quan trọng?

Phép hoán đổi thường tốn kém tài nguyên hơn phép so sánh.

Số phép hoán đổi luôn bằng số phép so sánh.

Chỉ có số phép so sánh mới quan trọng.

Số phép hoán đổi quyết định tính ổn định của thuật toán.

23 / 30

Category: 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

Tags: Bộ đề 07

Câu 23: Thuật toán sắp xếp nổi bọt (Bubble Sort) có một kỹ thuật tối ưu đơn giản là dừng thuật toán sớm nếu trong một lượt duyệt không có hoán đổi nào xảy ra. Kỹ thuật này giúp cải thiện hiệu suất đáng kể trong trường hợp nào?

Dãy số có thứ tự ngược hoàn toàn.

Dãy số đã được sắp xếp hoặc gần như sắp xếp.

Dãy số có kích thước rất lớn.

Dãy số chứa nhiều phần tử trùng lặp.

24 / 30

Category: 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

Tags: Bộ đề 07

Câu 24: Cho dãy số H = [5, 3, 1, 4, 2]. Áp dụng thuật toán sắp xếp chèn (Insertion Sort) tăng dần. Dãy H sẽ như thế nào sau khi phần tử '1' được chèn vào đúng vị trí?

[1, 5, 3, 4, 2]

[3, 1, 5, 4, 2]

[1, 3, 4, 5, 2]

[1, 3, 5, 4, 2]

25 / 30

Category: 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

Tags: Bộ đề 07

Câu 25: Trong thuật toán sắp xếp chọn (Selection Sort), phần tử nào được đảm bảo sẽ nằm đúng vị trí cuối cùng của nó sau lượt duyệt (pass) đầu tiên?

Phần tử nhỏ nhất trong dãy ban đầu.

Phần tử lớn nhất trong dãy ban đầu.

Phần tử ở vị trí cuối cùng của dãy ban đầu.

Không có phần tử nào được đảm bảo ở vị trí cuối cùng chỉ sau lượt duyệt đầu tiên.

26 / 30

Category: 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

Tags: Bộ đề 07

Câu 26: Bạn cần sắp xếp một danh sách rất nhỏ (khoảng dưới 20 phần tử). Trong các thuật toán sắp xếp đơn giản, thuật toán nào thường được ưu tiên vì sự đơn giản trong cài đặt và hiệu suất chấp nhận được với dữ liệu nhỏ?

Sắp xếp nhanh (Quick Sort)

Sắp xếp trộn (Merge Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp vun đống (Heap Sort)

27 / 30

Category: 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

Tags: Bộ đề 07

Câu 27: Khi so sánh hiệu suất của các thuật toán sắp xếp đơn giản, yếu tố nào thường được coi là ít quan trọng hơn trong phân tích độ phức tạp O(N^2)?

Các hằng số và số hạng bậc thấp trong công thức tính số bước.

Số lượng phần tử (N) của dãy.

Số phép so sánh.

Số phép hoán đổi.

28 / 30

Category: 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

Tags: Bộ đề 07

Câu 28: Thuật toán sắp xếp nào sau đây KHÔNG đảm bảo rằng phần tử lớn nhất trong phần chưa sắp xếp sẽ được đưa về cuối phần chưa sắp xếp sau mỗi lượt duyệt hoàn chỉnh?

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

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

Cả ba thuật toán đều đảm bảo điều đó.

29 / 30

Category: 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

Tags: Bộ đề 07

Câu 29: Một giáo viên yêu cầu học sinh viết chương trình sắp xếp một danh sách điểm của lớp (khoảng 40 học sinh). Thuật toán sắp xếp đơn giản nào là lựa chọn hợp lý nhất để giới thiệu cho học sinh vì sự dễ hiểu và cài đặt?

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

Sắp xếp nhanh (Quick Sort)

Sắp xếp trộn (Merge Sort)

Sắp xếp vun đống (Heap Sort)

30 / 30

Category: 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

Tags: Bộ đề 07

Câu 30: Cho dãy số I = [15, 10, 20, 5]. Áp dụng thuật toán sắp xếp chọn (Selection Sort) tăng dần. Dãy I sẽ như thế nào sau lượt duyệt thứ hai (chọn và hoán đổi để đặt phần tử thứ hai đúng vị trí)?

[5, 10, 15, 20]

[5, 10, 20, 15]

[10, 5, 20, 15]

[5, 15, 20, 10]

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 08

1 / 30

Category: 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

Tags: Bộ đề 08

Câu 1: Điểm khác biệt cơ bản nhất về yêu cầu dữ liệu đầu vào giữa thuật toán tìm kiếm tuần tự (Sequential Search) và thuật toán tìm kiếm nhị phân (Binary Search) là gì?

Tìm kiếm tuần tự yêu cầu dữ liệu là số nguyên, còn tìm kiếm nhị phân thì không.

Tìm kiếm tuần tự chỉ áp dụng cho danh sách ngắn, tìm kiếm nhị phân cho danh sách dài.

Tìm kiếm tuần tự có thể áp dụng cho dữ liệu bất kỳ (đã hoặc chưa sắp xếp), còn tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp.

Tìm kiếm tuần tự yêu cầu dữ liệu duy nhất, còn tìm kiếm nhị phân cho phép dữ liệu trùng lặp.

2 / 30

Category: 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

Tags: Bộ đề 08

Câu 2: Bạn cần tìm kiếm một từ khóa trong một tài liệu văn bản rất dài (hàng triệu ký tự) mà không biết tài liệu đó có được sắp xếp theo thứ tự nào hay không. Thuật toán tìm kiếm nào là lựa chọn phù hợp nhất trong trường hợp này?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai thuật toán đều không phù hợp.

Một thuật toán sắp xếp trước rồi mới tìm kiếm nhị phân.

3 / 30

Category: 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

Tags: Bộ đề 08

Câu 3: Cho dãy số A = [15, 8, 22, 5, 30, 12]. Khi tìm kiếm giá trị K = 30 bằng thuật toán tìm kiếm tuần tự, thuật toán sẽ thực hiện bao nhiêu phép so sánh (so sánh giá trị phần tử với K) cho đến khi tìm thấy?

4 / 30

Category: 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

Tags: Bộ đề 08

Câu 4: Tại sao thuật toán tìm kiếm nhị phân lại hiệu quả hơn đáng kể so với tìm kiếm tuần tự khi áp dụng cho các danh sách dữ liệu lớn đã được sắp xếp?

Vì tìm kiếm nhị phân sử dụng nhiều bộ nhớ hơn.

Vì mỗi bước lặp, tìm kiếm nhị phân loại bỏ được một nửa số phần tử còn lại trong phạm vi tìm kiếm.

Vì tìm kiếm nhị phân chỉ hoạt động trên dữ liệu số.

Vì tìm kiếm nhị phân luôn tìm thấy phần tử ở vị trí đầu tiên.

5 / 30

Category: 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

Tags: Bộ đề 08

Câu 5: Điều kiện tiên quyết bắt buộc để có thể áp dụng thuật toán tìm kiếm nhị phân là gì?

Danh sách phải có ít nhất 100 phần tử.

Các phần tử trong danh sách phải là số nguyên dương.

Danh sách dữ liệu phải được sắp xếp (tăng dần hoặc giảm dần).

Phần tử cần tìm phải nằm ở nửa đầu của danh sách.

6 / 30

Category: 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

Tags: Bộ đề 08

Câu 6: Cho dãy số đã sắp xếp A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Khi tìm kiếm giá trị K = 23 bằng thuật toán tìm kiếm nhị phân, phần tử nào sẽ được so sánh ở bước lặp thứ hai (sau bước so sánh phần tử giữa ban đầu)?

7 / 30

Category: 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

Tags: Bộ đề 08

Câu 7: Trong trường hợp xấu nhất khi sử dụng thuật toán tìm kiếm tuần tự trên một danh sách gồm N phần tử, số lượng phép so sánh cần thiết để xác định một phần tử *không* có trong danh sách là bao nhiêu?

N/2

log₂N

8 / 30

Category: 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

Tags: Bộ đề 08

Câu 8: Trong trường hợp tốt nhất khi sử dụng thuật toán tìm kiếm nhị phân trên một danh sách đã sắp xếp gồm N phần tử, số lượng phép so sánh cần thiết để tìm thấy một phần tử là bao nhiêu?

log₂N

N/2

9 / 30

Category: 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

Tags: Bộ đề 08

Câu 9: Bạn đang sử dụng một ứng dụng từ điển trên điện thoại. Khi bạn gõ một từ để tra cứu, ứng dụng hiển thị kết quả gần như ngay lập tức từ một cơ sở dữ liệu từ vựng rất lớn đã được sắp xếp theo thứ tự chữ cái. Nguyên tắc tìm kiếm nào có khả năng cao nhất được ứng dụng này sử dụng?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Một thuật toán sắp xếp.

Chỉ đơn giản là duyệt toàn bộ danh sách.

10 / 30

Category: 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

Tags: Bộ đề 08

Câu 10: Nếu một danh sách dữ liệu đã được sắp xếp theo thứ tự giảm dần, để áp dụng thuật toán tìm kiếm nhị phân, bạn cần điều chỉnh logic như thế nào?

Thay đổi hướng so sánh: nếu phần tử giữa nhỏ hơn giá trị cần tìm thì tìm ở nửa bên trái, nếu lớn hơn thì tìm ở nửa bên phải.

Thuật toán tìm kiếm nhị phân không thể áp dụng cho danh sách giảm dần.

Chỉ cần đảo ngược thứ tự danh sách thành tăng dần trước khi tìm kiếm.

Không cần thay đổi gì, thuật toán vẫn hoạt động bình thường.

11 / 30

Category: 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

Tags: Bộ đề 08

Câu 11: Cho dãy số A = [10, 4, 8, 15, 6]. Khi tìm kiếm giá trị K = 8 bằng thuật toán tìm kiếm tuần tự, chỉ số (index) của phần tử được tìm thấy là bao nhiêu (giả sử chỉ số bắt đầu từ 0)?

12 / 30

Category: 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

Tags: Bộ đề 08

Câu 12: Cho dãy số đã sắp xếp A = [5, 10, 15, 20, 25, 30]. Khi tìm kiếm giá trị K = 20 bằng thuật toán tìm kiếm nhị phân, chỉ số (index) của phần tử được tìm thấy là bao nhiêu (giả sử chỉ số bắt đầu từ 0)?

13 / 30

Category: 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

Tags: Bộ đề 08

Câu 13: Trong bài toán "Tìm kiếm thông tin về thời tiết hiện tại của thành phố Hà Nội trên một trang web dự báo thời tiết", đâu là "miền dữ liệu" của bài toán này?

Chỉ thông tin thời tiết của thành phố Hà Nội.

Toàn bộ dữ liệu thời tiết mà trang web đó cung cấp (của tất cả các địa điểm và thời gian).

Tên của thành phố Hà Nội.

Kết quả dự báo thời tiết của Hà Nội.

14 / 30

Category: 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

Tags: Bộ đề 08

Câu 14: So sánh số bước (phép so sánh) trong trường hợp xấu nhất khi tìm kiếm trên một danh sách 1000 phần tử đã sắp xếp bằng tìm kiếm tuần tự và tìm kiếm nhị phân. Nhận xét nào sau đây là đúng?

Tìm kiếm tuần tự và tìm kiếm nhị phân có số bước tương đương nhau.

Tìm kiếm tuần tự cần ít bước hơn nhiều so với tìm kiếm nhị phân.

Tìm kiếm nhị phân cần ít bước hơn nhiều so với tìm kiếm tuần tự (khoảng log₂1000 so với 1000).

Tìm kiếm nhị phân cần nhiều bước hơn nhưng các bước đơn giản hơn.

15 / 30

Category: 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

Tags: Bộ đề 08

Câu 15: Cho dãy số đã sắp xếp A = [10, 20, 30, 40, 50]. Tìm kiếm giá trị K = 35 bằng thuật toán tìm kiếm nhị phân. Sau khi thuật toán kết thúc mà không tìm thấy giá trị 35, điều gì cho thấy giá trị đó không có trong danh sách?

Khoảng tìm kiếm (giới hạn dưới và giới hạn trên) trở nên rỗng hoặc giới hạn dưới vượt quá giới hạn trên.

Thuật toán dừng lại ở phần tử đầu tiên.

Thuật toán dừng lại ở phần tử cuối cùng.

Số lần so sánh đạt đến một giới hạn cố định.

16 / 30

Category: 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

Tags: Bộ đề 08

Câu 16: Điều gì xảy ra nếu bạn áp dụng thuật toán tìm kiếm nhị phân trên một danh sách dữ liệu *chưa* được sắp xếp?

Thuật toán sẽ hoạt động bình thường nhưng chậm hơn.

Thuật toán sẽ luôn tìm thấy phần tử cần tìm nếu nó tồn tại.

Thuật toán sẽ báo lỗi ngay lập tức.

Thuật toán có thể không tìm thấy phần tử cần tìm ngay cả khi nó tồn tại trong danh sách.

17 / 30

Category: 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

Tags: Bộ đề 08

Câu 17: Khái niệm "chia đôi" trong thuật toán tìm kiếm nhị phân đề cập đến việc gì?

Chia giá trị cần tìm thành hai phần.

Chia số lượng phép so sánh làm đôi.

Chia khoảng tìm kiếm hiện tại (phần danh sách đang xét) thành hai nửa dựa trên phần tử giữa.

Chia danh sách ban đầu thành hai danh sách con.

18 / 30

Category: 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

Tags: Bộ đề 08

Câu 18: Trong trường hợp nào thuật toán tìm kiếm tuần tự có thể là lựa chọn tốt hơn hoặc duy nhất khả thi so với tìm kiếm nhị phân?

Khi danh sách dữ liệu chưa được sắp xếp hoặc có kích thước rất nhỏ.

Khi cần tìm kiếm nhiều lần trên cùng một danh sách.

Khi danh sách dữ liệu rất lớn và đã được sắp xếp.

Khi phần tử cần tìm chắc chắn nằm ở cuối danh sách.

19 / 30

Category: 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

Tags: Bộ đề 08

Câu 19: Cho dãy số A = [50, 30, 70, 10, 90]. Khi tìm kiếm giá trị K = 40 bằng thuật toán tìm kiếm tuần tự, thuật toán sẽ thực hiện bao nhiêu phép so sánh cho đến khi xác định giá trị 40 không có trong dãy?

20 / 30

Category: 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

Tags: Bộ đề 08

Câu 20: Mục đích chính của bài toán tìm kiếm là gì?

Sắp xếp lại dữ liệu theo một thứ tự nhất định.

Kiểm tra xem một phần tử cụ thể có tồn tại trong một tập hợp dữ liệu hay không và (nếu có) xác định vị trí của nó.

Thêm các phần tử mới vào tập hợp dữ liệu.

Xóa các phần tử không mong muốn khỏi tập hợp dữ liệu.

21 / 30

Category: 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

Tags: Bộ đề 08

Câu 21: Một lập trình viên sử dụng thuật toán tìm kiếm tuần tự để tìm kiếm một bản ghi khách hàng trong một cơ sở dữ liệu chứa hàng triệu bản ghi đã được sắp xếp theo tên. Đánh giá về lựa chọn thuật toán này?

Đây là lựa chọn tối ưu vì tìm kiếm tuần tự đơn giản để cài đặt.

Lựa chọn này phù hợp vì dữ liệu đã được sắp xếp.

Lựa chọn này không hiệu quả vì tìm kiếm tuần tự không thể xử lý dữ liệu lớn.

Lựa chọn này không hiệu quả vì với dữ liệu lớn đã sắp xếp, tìm kiếm nhị phân sẽ nhanh hơn rất nhiều.

22 / 30

Category: 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

Tags: Bộ đề 08

Câu 22: Cho dãy số đã sắp xếp A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Tìm kiếm giá trị K = 56 bằng thuật toán tìm kiếm nhị phân. Phần tử nào được so sánh ở bước lặp thứ ba?

23 / 30

Category: 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

Tags: Bộ đề 08

Câu 23: Bạn có một danh sách điểm thi của học sinh trong lớp, danh sách này được nhập theo thứ tự ngẫu nhiên (không sắp xếp). Bạn muốn kiểm tra xem có học sinh nào đạt điểm 10 hay không. Thuật toán tìm kiếm nào là phù hợp nhất trong tình huống này nếu bạn không muốn mất thời gian sắp xếp danh sách?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai đều không phù hợp.

Chỉ có thể dùng cách kiểm tra thủ công.

24 / 30

Category: 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

Tags: Bộ đề 08

Câu 24: Một công ty quản lý danh sách sản phẩm của mình trong một cơ sở dữ liệu, được sắp xếp theo mã sản phẩm. Khi khách hàng nhập mã sản phẩm để xem thông tin chi tiết, hệ thống cần tìm kiếm mã sản phẩm đó một cách nhanh chóng. Thuật toán tìm kiếm nào nên được ưu tiên sử dụng?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai đều có tốc độ như nhau trong trường hợp này.

Một thuật toán sắp xếp.

25 / 30

Category: 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

Tags: Bộ đề 08

Câu 25: Sự khác biệt cốt lõi trong cách thu hẹp phạm vi tìm kiếm giữa tìm kiếm tuần tự và tìm kiếm nhị phân là gì?

Tìm kiếm tuần tự loại bỏ từng phần tử một từ đầu, còn tìm kiếm nhị phân loại bỏ từng phần tử một từ cuối.

Tìm kiếm tuần tự loại bỏ một nửa danh sách ở mỗi bước, còn tìm kiếm nhị phân loại bỏ từng phần tử một.

Tìm kiếm tuần tự chỉ làm việc với các số, còn tìm kiếm nhị phân làm việc với mọi loại dữ liệu.

Tìm kiếm tuần tự loại bỏ từng phần tử một từ đầu danh sách, còn tìm kiếm nhị phân loại bỏ một nửa khoảng tìm kiếm hiện tại dựa vào so sánh với phần tử giữa.

26 / 30

Category: 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

Tags: Bộ đề 08

Câu 26: Khi bạn sử dụng chức năng "Tìm kiếm bạn bè" trên một mạng xã hội, hệ thống sẽ xử lý yêu cầu tìm kiếm của bạn trên một cơ sở dữ liệu người dùng khổng lồ. Để trả về kết quả nhanh chóng, nguyên tắc tìm kiếm nào, hoặc kết hợp các nguyên tắc nào, có khả năng cao nhất được sử dụng?

Chỉ tìm kiếm tuần tự trên toàn bộ cơ sở dữ liệu.

Chỉ tìm kiếm nhị phân trên toàn bộ cơ sở dữ liệu (không khả thi nếu dữ liệu không được sắp xếp hoàn hảo theo tiêu chí tìm kiếm).

Kết hợp các kỹ thuật chỉ mục (indexing) và các thuật toán tìm kiếm hiệu quả (có thể dựa trên nguyên tắc phân chia như nhị phân hoặc các cấu trúc dữ liệu chuyên biệt).

Chỉ đơn giản là duyệt qua từng hồ sơ người dùng một cách tuần tự.

27 / 30

Category: 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

Tags: Bộ đề 08

Câu 27: Nếu thuật toán tìm kiếm tuần tự mất khoảng T giây để tìm kiếm trong trường hợp xấu nhất trên một danh sách N phần tử, thì ước tính thời gian cần thiết trong trường hợp xấu nhất cho một danh sách có 2N phần tử là bao nhiêu?

T/2 giây

T giây

T * log₂N giây

Khoảng 2T giây

28 / 30

Category: 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

Tags: Bộ đề 08

Câu 28: Nếu thuật toán tìm kiếm nhị phân mất khoảng T giây để tìm kiếm trong trường hợp xấu nhất trên một danh sách N phần tử đã sắp xếp, thì ước tính thời gian cần thiết trong trường hợp xấu nhất cho một danh sách có N² phần tử đã sắp xếp là bao nhiêu?

T * N giây

Khoảng 2T giây (vì log₂(N²) = 2log₂N)

T² giây

T + N giây

29 / 30

Category: 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

Tags: Bộ đề 08

Câu 29: Trong thuật toán tìm kiếm nhị phân, việc so sánh giá trị cần tìm với phần tử nằm ở vị trí giữa của khoảng tìm kiếm hiện tại có ý nghĩa gì?

Để xác định xem phần tử giữa có phải là phần tử cần tìm hay không.

Để xác định xem phần tử cần tìm nằm ở nửa bên trái hay nửa bên phải của khoảng tìm kiếm hiện tại (hoặc chính là phần tử giữa).

Cả đáp án 1 và 2 đều đúng.

Để xác định xem danh sách có được sắp xếp đúng thứ tự hay không.

30 / 30

Category: 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

Tags: Bộ đề 08

Câu 30: Một danh sách dữ liệu ban đầu đã được sắp xếp, nhưng sau đó một vài phần tử mới được thêm vào ở các vị trí ngẫu nhiên, làm cho danh sách không còn hoàn toàn được sắp xếp nữa. Bạn cần tìm kiếm một phần tử trong danh sách này. Thuật toán nào đảm bảo tìm thấy phần tử nếu nó tồn tại, mà không cần thực hiện lại quá trình sắp xếp toàn bộ danh sách?

Tìm kiếm tuần tự.

Tìm kiếm nhị phân.

Cả hai đều không thể đảm bảo tìm thấy.

Chỉ có thể sử dụng thuật toán sắp xếp trước.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 09

1 / 30

Category: 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

Tags: Bộ đề 09

Câu 1: Mục đích chính của các thuật toán sắp xếp là gì?

Tìm kiếm một phần tử cụ thể trong danh sách.

Lọc bỏ các phần tử trùng lặp khỏi danh sách.

Sắp xếp các phần tử trong danh sách theo một thứ tự nhất định (tăng dần hoặc giảm dần).

Thêm hoặc xóa phần tử khỏi danh sách.

2 / 30

Category: 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

Tags: Bộ đề 09

Câu 2: Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên nguyên tắc nào?

So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng không đúng thứ tự.

Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đưa về đúng vị trí.

Xây dựng mảng con đã sắp xếp bằng cách chèn từng phần tử vào đúng vị trí.

Chia mảng thành hai nửa rồi sắp xếp từng nửa một cách đệ quy.

3 / 30

Category: 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

Tags: Bộ đề 09

Câu 3: Cho mảng A = [6, 3, 8, 2, 5]. Sau khi thực hiện **một lượt (pass)** đầu tiên của thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần, mảng A sẽ có trạng thái như thế nào?

[2, 3, 5, 6, 8]

[3, 6, 2, 5, 8]

[6, 3, 8, 2, 5]

[3, 6, 2, 5, 8]

4 / 30

Category: 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

Tags: Bộ đề 09

Câu 4: Cho mảng A = [6, 3, 8, 2, 5]. Thuật toán sắp xếp chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa về đầu. Sau khi thực hiện **lần đặt phần tử đầu tiên** vào đúng vị trí, mảng A sẽ có trạng thái như thế nào?

[2, 3, 8, 6, 5]

[6, 3, 8, 2, 5]

[2, 3, 5, 6, 8]

[3, 6, 8, 2, 5]

5 / 30

Category: 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

Tags: Bộ đề 09

Câu 5: Cho mảng A = [6, 3, 8, 2, 5]. Thuật toán sắp xếp chèn (Insertion Sort) hoạt động bằng cách chèn từng phần tử vào phần đã sắp xếp. Sau khi xử lý và chèn xong **phần tử thứ hai** (giá trị 3), mảng A sẽ có trạng thái như thế nào?

[3, 6, 8, 2, 5]

[6, 3, 8, 2, 5]

[2, 3, 6, 8, 5]

6 / 30

Category: 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

Tags: Bộ đề 09

Câu 6: Thuật toán sắp xếp nào trong các thuật toán đơn giản (Nổi bọt, Chọn, Chèn) có hiệu suất tốt nhất trong trường hợp mảng đầu vào **đã được sắp xếp hoàn toàn**?

Sắp xếp nổi bọt (Bubble Sort) không có tối ưu.

Sắp xếp chọn (Selection Sort).

Sắp xếp chèn (Insertion Sort).

Cả ba thuật toán đều có hiệu suất như nhau trong trường hợp này.

7 / 30

Category: 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

Tags: Bộ đề 09

Câu 7: Độ phức tạp thời gian trong trường hợp xấu nhất (worst-case time complexity) của các thuật toán sắp xếp đơn giản như Nổi bọt, Chọn, Chèn là gì (với n là số phần tử)?

O(n^2)

O(n log n)

O(n)

O(log n)

8 / 30

Category: 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

Tags: Bộ đề 09

Câu 8: Khi sắp xếp một mảng gồm 1000 phần tử bằng thuật toán sắp xếp chọn (Selection Sort), số lượt (pass) chính mà thuật toán cần thực hiện để đưa các phần tử về đúng vị trí cuối cùng là bao nhiêu?

1000

Khoảng log₂(1000)

999

Không xác định được vì phụ thuộc vào trạng thái ban đầu của mảng.

9 / 30

Category: 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

Tags: Bộ đề 09

Câu 9: Thuật toán sắp xếp nào trong các thuật toán đơn giản **không** thực hiện hoán đổi vị trí các phần tử liền kề một cách trực tiếp như Bubble Sort?

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

Sắp xếp chọn (Selection Sort).

Sắp xếp chèn (Insertion Sort).

Cả ba thuật toán đều thực hiện hoán đổi liền kề.

10 / 30

Category: 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

Tags: Bộ đề 09

Câu 10: Giả sử bạn cần sắp xếp một danh sách rất nhỏ (khoảng dưới 20 phần tử) và sự đơn giản trong cài đặt là ưu tiên hàng đầu. Thuật toán sắp xếp đơn giản nào thường được coi là dễ hiểu và cài đặt nhất?

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

Sắp xếp chọn (Selection Sort).

Sắp xếp chèn (Insertion Sort).

Không có thuật toán đơn giản nào nổi bật về sự dễ cài đặt.

11 / 30

Category: 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

Tags: Bộ đề 09

Câu 11: Cho mảng A = [1, 2, 3, 4, 5]. Khi áp dụng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp tăng dần, số lần hoán đổi (swap) hoặc dịch chuyển (shift) phần tử sẽ là bao nhiêu?

Nhiều nhất.

Bằng số phần tử.

Ít nhất nhưng không phải 0.

0 (hoặc rất ít dịch chuyển nếu mảng đã sắp xếp).

12 / 30

Category: 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

Tags: Bộ đề 09

Câu 12: Trong trường hợp xấu nhất (ví dụ: mảng được sắp xếp ngược), thuật toán sắp xếp nào trong các thuật toán đơn giản (Nổi bọt, Chọn, Chèn) thực hiện số lần hoán đổi **ít nhất**?

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

Sắp xếp chọn (Selection Sort).

Sắp xếp chèn (Insertion Sort).

Số lần hoán đổi là như nhau đối với cả ba thuật toán trong trường hợp xấu nhất.

13 / 30

Category: 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

Tags: Bộ đề 09

Câu 13: Cho mảng A = [7, 1, 5, 12, 3]. Sau khi kết thúc **toàn bộ quá trình** sắp xếp bằng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần, mảng A sẽ có trạng thái như thế nào?

[1, 3, 5, 7, 12]

[1, 5, 7, 3, 12]

[1, 7, 5, 12, 3]

[3, 1, 5, 7, 12]

14 / 30

Category: 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

Tags: Bộ đề 09

Câu 14: Cho mảng A = [7, 1, 5, 12, 3]. Sau khi kết thúc **toàn bộ quá trình** sắp xếp bằng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần, mảng A sẽ có trạng thái như thế nào?

[7, 1, 5, 12, 3]

[1, 7, 5, 3, 12]

[1, 3, 5, 7, 12]

[1, 5, 7, 3, 12]

15 / 30

Category: 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

Tags: Bộ đề 09

Câu 15: Cho mảng A = [7, 1, 5, 12, 3]. Sau khi kết thúc **toàn bộ quá trình** sắp xếp bằng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp tăng dần, mảng A sẽ có trạng thái như thế nào?

[7, 1, 5, 12, 3]

[1, 3, 5, 7, 12]

[1, 5, 7, 3, 12]

[1, 7, 5, 12, 3]

16 / 30

Category: 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

Tags: Bộ đề 09

Câu 16: Một mảng được sắp xếp bằng một thuật toán đơn giản và sau vài bước, mảng có dạng: [2, 5, 8, 1, 4]. Phần tử 2, 5, 8 đã ở đúng vị trí tương đối so với nhau. Thuật toán nào có khả năng đã được sử dụng?

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

Sắp xếp chọn (Selection Sort).

Sắp xếp chèn (Insertion Sort).

Không thể xác định chỉ với thông tin này.

17 / 30

Category: 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

Tags: Bộ đề 09

Câu 17: Một mảng được sắp xếp bằng một thuật toán đơn giản và sau vài bước, mảng có dạng: [1, 3, 8, 6, 5]. Phần tử nhỏ nhất (1) đã được đưa về đầu. Thuật toán nào có khả năng đã được sử dụng?

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

Sắp xếp chọn (Selection Sort).

Sắp xếp chèn (Insertion Sort).

Cả ba thuật toán đều có thể tạo ra trạng thái này.

18 / 30

Category: 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

Tags: Bộ đề 09

Câu 18: Đặc điểm nào sau đây là **đúng** khi so sánh giữa Sắp xếp chọn (Selection Sort) và Sắp xếp nổi bọt (Bubble Sort) trên một mảng ngẫu nhiên có kích thước lớn?

Selection Sort thường thực hiện ít hoán đổi hơn Bubble Sort.

Bubble Sort luôn nhanh hơn Selection Sort.

Selection Sort có độ phức tạp thời gian tốt hơn Bubble Sort trong trường hợp xấu nhất.

Cả hai thuật toán đều có cùng số lần so sánh trong mọi trường hợp.

19 / 30

Category: 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

Tags: Bộ đề 09

Câu 19: Thuật toán sắp xếp chèn (Insertion Sort) được cho là hiệu quả hơn Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp chọn (Selection Sort) trong trường hợp nào?

Mảng có kích thước rất lớn.

Mảng chứa nhiều phần tử trùng lặp.

Mảng gần như đã được sắp xếp.

Mảng được sắp xếp theo thứ tự ngược hoàn toàn.

20 / 30

Category: 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

Tags: Bộ đề 09

Câu 20: Khi sử dụng thuật toán sắp xếp nổi bọt (Bubble Sort), sau mỗi lượt (pass), điều gì xảy ra với phần tử lớn nhất trong phần chưa sắp xếp?

Nó "nổi" lên và được đặt ở vị trí cuối cùng của phần chưa sắp xếp (đầu phần đã sắp xếp).

Nó được hoán đổi với phần tử đầu tiên của mảng.

Nó được chèn vào đúng vị trí trong phần đã sắp xếp.

Vị trí của nó không thay đổi trong lượt đó.

21 / 30

Category: 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

Tags: Bộ đề 09

Câu 21: Thuật toán sắp xếp chọn (Selection Sort) luôn đảm bảo rằng sau k lượt (pass) đầu tiên, điều gì là đúng về k phần tử đầu tiên của mảng?

Chúng là k phần tử nhỏ nhất của mảng ban đầu và đã được sắp xếp đúng thứ tự tương đối so với nhau.

Chúng là k phần tử đầu tiên của mảng ban đầu.

Chúng là k phần tử lớn nhất của mảng ban đầu.

Chúng là k phần tử nhỏ nhất của mảng ban đầu và đã được sắp xếp đúng thứ tự cuối cùng.

22 / 30

Category: 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

Tags: Bộ đề 09

Câu 22: Thuật toán sắp xếp chèn (Insertion Sort) duy trì một mảng con đã sắp xếp. Mảng con này ban đầu bao gồm bao nhiêu phần tử?

1 (phần tử đầu tiên của mảng)

Tất cả các phần tử của mảng.

23 / 30

Category: 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

Tags: Bộ đề 09

Câu 23: Trong thuật toán sắp xếp chèn (Insertion Sort), khi chèn một phần tử vào mảng con đã sắp xếp, các phần tử lớn hơn nó trong mảng con sẽ được thực hiện hành động gì?

Dịch chuyển sang phải một vị trí.

Dịch chuyển sang trái một vị trí.

Hoán đổi vị trí với phần tử đang chèn.

Giữ nguyên vị trí.

24 / 30

Category: 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

Tags: Bộ đề 09

Câu 24: So sánh số lần so sánh giữa Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp chèn (Insertion Sort) trong trường hợp xấu nhất (mảng ngược).

Bubble Sort luôn thực hiện ít so sánh hơn Insertion Sort.

Insertion Sort luôn thực hiện ít so sánh hơn Bubble Sort.

Số lần so sánh có cùng bậc O(n^2), nhưng giá trị cụ thể có thể khác nhau.

Cả hai đều thực hiện n lần so sánh.

25 / 30

Category: 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

Tags: Bộ đề 09

Câu 25: Khi nào thì việc sử dụng một trong các thuật toán sắp xếp đơn giản (Nổi bọt, Chọn, Chèn) là **không** hiệu quả cho một tập dữ liệu lớn (ví dụ: hàng triệu phần tử)?

Khi dữ liệu đã được sắp xếp.

Khi dữ liệu gần được sắp xếp.

Khi yêu cầu độ chính xác cao.

Khi cần tốc độ xử lý nhanh.

26 / 30

Category: 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

Tags: Bộ đề 09

Câu 26: Cho mảng A = [4, 1, 3, 2]. Sau khi kết thúc **lượt thứ hai** của thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần (bắt đầu từ đầu mảng), mảng A sẽ có trạng thái như thế nào?

[1, 3, 2, 4]

[1, 2, 3, 4]

[4, 1, 3, 2]

[1, 3, 4, 2]

27 / 30

Category: 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

Tags: Bộ đề 09

Câu 27: Cho mảng A = [4, 1, 3, 2]. Sau khi kết thúc **lần đặt phần tử thứ hai** vào đúng vị trí bằng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần, mảng A sẽ có trạng thái như thế nào?

[1, 4, 3, 2]

[1, 2, 3, 4]

[4, 1, 3, 2]

[1, 2, 3, 4]

28 / 30

Category: 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

Tags: Bộ đề 09

Câu 28: Cho mảng A = [4, 1, 3, 2]. Sau khi xử lý và chèn xong **phần tử thứ ba** (giá trị 3) bằng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp tăng dần, mảng A sẽ có trạng thái như thế nào?

[1, 3, 4, 2]

[1, 2, 3, 4]

[4, 1, 3, 2]

[1, 4, 3, 2]

29 / 30

Category: 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

Tags: Bộ đề 09

Câu 29: Khi phân tích hiệu quả của thuật toán sắp xếp, khái niệm "độ phức tạp thời gian" (time complexity) O(n^2) biểu thị điều gì?

Thời gian thực hiện tăng tuyến tính theo số lượng phần tử (n).

Thời gian thực hiện tăng xấp xỉ bình phương số lượng phần tử (n).

Thời gian thực hiện tăng theo logarit của số lượng phần tử (n).

Thời gian thực hiện là hằng số, không phụ thuộc vào số lượng phần tử (n).

30 / 30

Category: 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

Tags: Bộ đề 09

Câu 30: Giả sử bạn có một danh sách dữ liệu cần được sắp xếp rất thường xuyên, và tốc độ là yếu tố quan trọng nhất. Dựa trên hiểu biết về độ phức tạp thời gian, bạn nên chọn thuật toán sắp xếp đơn giản (O(n^2)) hay tìm hiểu các thuật toán phức tạp hơn (ví dụ: O(n log n))?

Nên tìm hiểu các thuật toán phức tạp hơn (O(n log n)) vì chúng hiệu quả hơn đáng kể với dữ liệu lớn.

Nên sử dụng các thuật toán đơn giản (O(n^2)) vì chúng dễ cài đặt hơn.

Độ phức tạp thời gian không quan trọng bằng số lần hoán đổi.

Nên chọn thuật toán dựa trên bộ nhớ sử dụng, không phải thời gian.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

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 - Đề 10

1 / 30

Category: 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

Tags: Bộ đề 10

Câu 1: Mục đích chính của các thuật toán sắp xếp là gì?

Giảm dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu.

Mã hóa dữ liệu để bảo mật thông tin.

Tăng tốc độ truyền dữ liệu qua mạng.

Sắp xếp các phần tử trong danh sách theo một thứ tự nhất định (tăng dần hoặc giảm dần).

2 / 30

Category: 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

Tags: Bộ đề 10

Câu 2: Thuật toán sắp xếp chọn (Selection Sort) hoạt động dựa trên nguyên tắc nào?

So sánh và hoán đổi các phần tử kề nhau cho đến khi danh sách được sắp xếp.

Chèn từng phần tử vào vị trí thích hợp trong phần danh sách đã được sắp xếp.

Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần danh sách chưa được sắp xếp và đưa nó về đúng vị trí.

Chia danh sách thành hai nửa, sắp xếp từng nửa rồi trộn lại.

3 / 30

Category: 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

Tags: Bộ đề 10

Câu 3: Cho mảng A = [5, 2, 8, 1, 9]. Sau khi thực hiện xong *lượt 1* của thuật toán sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, mảng A sẽ có trạng thái như thế nào?

[2, 5, 8, 1, 9]

[1, 2, 8, 5, 9]

[5, 2, 8, 1, 9]

[1, 5, 8, 2, 9]

4 / 30

Category: 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

Tags: Bộ đề 10

Câu 4: Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên nguyên tắc nào?

So sánh và hoán đổi các cặp phần tử kề nhau nếu chúng không đúng thứ tự.

Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa về đầu.

Chèn phần tử hiện tại vào đúng vị trí trong phần đã sắp xếp.

Chia danh sách và sắp xếp độc lập các phần nhỏ hơn.

5 / 30

Category: 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

Tags: Bộ đề 10

Câu 5: Cho mảng B = [7, 3, 9, 4]. Sau khi thực hiện xong *lượt 1* của thuật toán sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần, mảng B sẽ có trạng thái như thế nào?

[3, 7, 9, 4]

[7, 3, 4, 9]

[3, 7, 4, 9]

[3, 4, 7, 9]

6 / 30

Category: 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

Tags: Bộ đề 10

Câu 6: Thuật toán sắp xếp chèn (Insertion Sort) hoạt động dựa trên nguyên tắc nào?

Lặp lại việc tìm phần tử nhỏ nhất và đặt nó vào vị trí đầu tiên của phần chưa sắp xếp.

Xây dựng dần một danh sách con đã sắp xếp bằng cách chèn từng phần tử từ phần chưa sắp xếp vào đúng vị trí của nó.

So sánh và hoán đổi các cặp phần tử kề nhau cho đến khi không còn cặp nào sai thứ tự.

Sử dụng một trục (pivot) để phân chia danh sách thành hai phần và sắp xếp đệ quy.

7 / 30

Category: 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

Tags: Bộ đề 10

Câu 7: Cho mảng C = [6, 1, 4, 8]. Sau khi thực hiện xong *bước chèn phần tử thứ 2* (giá trị 1) vào phần đã sắp xếp của thuật toán sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần, mảng C sẽ có trạng thái như thế nào?

[1, 6, 4, 8]

[6, 1, 4, 8]

[1, 4, 6, 8]

[6, 4, 1, 8]

8 / 30

Category: 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

Tags: Bộ đề 10

Câu 8: Giả sử bạn có một danh sách gồm N phần tử. Trong trường hợp xấu nhất, thuật toán sắp xếp chọn (Selection Sort) cần khoảng bao nhiêu phép so sánh để sắp xếp danh sách đó?

N log N

N/2

N^2/2

9 / 30

Category: 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

Tags: Bộ đề 10

Câu 9: Đối với một mảng gồm N phần tử, thuật toán sắp xếp nổi bọt (Bubble Sort) có số lần hoán đổi (swap) trong trường hợp tốt nhất (mảng đã sắp xếp) là bao nhiêu?

N^2

N log N

10 / 30

Category: 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

Tags: Bộ đề 10

Câu 10: Khi nào thì thuật toán sắp xếp chèn (Insertion Sort) thể hiện hiệu suất tốt nhất?

Khi danh sách hoàn toàn chưa được sắp xếp.

Khi danh sách có kích thước rất lớn.

Khi danh sách gần như đã được sắp xếp.

Khi danh sách chỉ chứa các phần tử duy nhất.

11 / 30

Category: 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

Tags: Bộ đề 10

Câu 11: Hãy xác định thuật toán sắp xếp nào trong các thuật toán đơn giản (Chọn, Nổi bọt, Chèn) thường ít hiệu quả nhất trên các danh sách lớn và hoàn toàn ngẫu nhiên?

Sắp xếp Chèn

Sắp xếp Nổi bọt

Sắp xếp Chọn

Cả ba đều có hiệu suất tương đương trong trường hợp này.

12 / 30

Category: 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

Tags: Bộ đề 10

Câu 12: Cho mảng D = [10, 5, 20, 15]. Bạn thực hiện sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần. Sau khi phần tử 20 đã 'nổi' đến vị trí cuối cùng đúng của nó, mảng sẽ có trạng thái như thế nào?

[5, 10, 15, 20]

[10, 5, 15, 20]

[5, 10, 20, 15]

[10, 5, 20, 15] hoặc [5, 10, 20, 15] tùy số lần duyệt

13 / 30

Category: 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

Tags: Bộ đề 10

Câu 13: Thuật toán sắp xếp nào trong số Sắp xếp Chọn, Sắp xếp Nổi bọt, Sắp xếp Chèn đảm bảo rằng sau *k* lượt thực hiện đầu tiên, *k* phần tử nhỏ nhất (hoặc lớn nhất) của mảng sẽ nằm ở *k* vị trí đầu tiên đúng của chúng (khi sắp xếp tăng dần)?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Cả ba thuật toán đều không có đặc điểm này.

14 / 30

Category: 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

Tags: Bộ đề 10

Câu 14: Cho mảng E = [4, 1, 3, 2]. Bạn sử dụng thuật toán sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Sau khi chèn xong phần tử có giá trị 3 (phần tử thứ 3 ban đầu), mảng sẽ có trạng thái như thế nào?

[1, 4, 3, 2]

[1, 3, 4, 2]

[4, 1, 3, 2]

[1, 2, 3, 4]

15 / 30

Category: 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

Tags: Bộ đề 10

Câu 15: So sánh Sắp xếp Nổi bọt và Sắp xếp Chèn. Trong trường hợp nào Sắp xếp Chèn thường hiệu quả hơn Sắp xếp Nổi bọt?

Khi mảng chứa rất nhiều phần tử trùng lặp.

Khi cần sắp xếp theo thứ tự giảm dần.

Khi mảng hoàn toàn không được sắp xếp.

Khi mảng đã gần được sắp xếp.

16 / 30

Category: 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

Tags: Bộ đề 10

Câu 16: Thuật toán sắp xếp nào trong ba thuật toán đơn giản được giới thiệu (Chọn, Nổi bọt, Chèn) có đặc điểm là số lần hoán đổi (swap) không bao giờ vượt quá số lần hoán đổi của thuật toán sắp xếp chọn?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Không có thuật toán nào có đặc điểm này.

17 / 30

Category: 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

Tags: Bộ đề 10

Câu 17: Cho mảng F = [8, 3, 6, 2, 7]. Bạn áp dụng thuật toán sắp xếp chọn (Selection Sort) theo thứ tự tăng dần. Trạng thái của mảng sau khi kết thúc lượt thứ 2 là gì?

[2, 3, 6, 7, 8]

[2, 8, 6, 3, 7]

[2, 3, 6, 8, 7]

[2, 3, 8, 6, 7]

18 / 30

Category: 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

Tags: Bộ đề 10

Câu 18: Khi sử dụng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp một mảng theo thứ tự tăng dần, phần tử đang được chèn sẽ được so sánh với các phần tử nào trong mảng?

Chỉ phần tử đầu tiên của mảng.

Chỉ phần tử cuối cùng của mảng.

Tất cả các phần tử trong mảng.

Các phần tử trong phần mảng đã được sắp xếp (từ phải sang trái).

19 / 30

Category: 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

Tags: Bộ đề 10

Câu 19: Thuật toán sắp xếp nào trong ba thuật toán đơn giản có thể dừng sớm nếu mảng đã được sắp xếp hoàn toàn trước khi tất cả các lượt được hoàn thành?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Cả ba thuật toán đều không thể dừng sớm.

20 / 30

Category: 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

Tags: Bộ đề 10

Câu 20: Cho mảng G = [1, 2, 3, 4, 5]. Khi áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần, số lần hoán đổi (swap) sẽ là bao nhiêu?

Không xác định được.

21 / 30

Category: 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

Tags: Bộ đề 10

Câu 21: Tại sao thuật toán sắp xếp chọn (Selection Sort) lại có số lần hoán đổi ít hơn so với sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất?

Vì nó sử dụng ít phép so sánh hơn.

Vì nó chỉ hoán đổi các phần tử kề nhau.

Vì nó chỉ thực hiện một hoán đổi duy nhất sau mỗi lượt tìm kiếm phần tử nhỏ nhất (hoặc lớn nhất).

Vì nó có thể dừng sớm khi mảng đã sắp xếp.

22 / 30

Category: 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

Tags: Bộ đề 10

Câu 22: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Chọn, Nổi bọt, Chèn) thường được coi là trực quan và dễ hiểu nhất đối với người mới bắt đầu học?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Cả ba đều có độ phức tạp như nhau.

23 / 30

Category: 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

Tags: Bộ đề 10

Câu 23: Cho mảng H = [9, 7, 5, 3, 1]. Bạn áp dụng thuật toán sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Sau khi kết thúc lượt chèn phần tử cuối cùng (giá trị 1), mảng sẽ có trạng thái như thế nào?

[1, 3, 5, 7, 9]

[9, 7, 5, 3, 1]

[1, 9, 7, 5, 3]

[3, 5, 7, 9, 1]

24 / 30

Category: 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

Tags: Bộ đề 10

Câu 24: Khi phân tích hiệu quả của thuật toán sắp xếp, yếu tố nào sau đây *không* phải là yếu tố chính thường được xem xét?

Số lần so sánh giữa các phần tử.

Số lần hoán đổi (swap) các phần tử.

Lượng bộ nhớ phụ trợ cần thiết.

Màu sắc của các phần tử trong mảng.

25 / 30

Category: 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

Tags: Bộ đề 10

Câu 25: Giả sử bạn cần sắp xếp một danh sách rất nhỏ (ví dụ, dưới 10 phần tử). Sự khác biệt về hiệu năng giữa Sắp xếp Chọn, Sắp xếp Nổi bọt và Sắp xếp Chèn có đáng kể không?

Không đáng kể, vì N quá nhỏ nên sự khác biệt về độ phức tạp O(N^2) không thể hiện rõ.

Rất đáng kể, thuật toán nhanh nhất sẽ vượt trội hơn nhiều.

Chỉ đáng kể nếu danh sách đã được sắp xếp ngược.

Chỉ đáng kể nếu danh sách chứa các số âm.

26 / 30

Category: 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

Tags: Bộ đề 10

Câu 26: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Chọn, Nổi bọt, Chèn) có thể được mô tả như việc 'sắp xếp tay' một bộ bài, nơi bạn cầm từng lá bài mới lên và chèn nó vào đúng vị trí trong các lá bài đã được sắp xếp trong tay?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Cả ba đều không phù hợp với mô tả này.

27 / 30

Category: 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

Tags: Bộ đề 10

Câu 27: Cho mảng I = [12, 11, 13, 5, 6]. Áp dụng sắp xếp nổi bọt (Bubble Sort) tăng dần. Sau khi kết thúc lượt duyệt thứ 3 (lượt cuối cùng của các cặp kề nhau trong 4 phần tử đầu tiên), mảng sẽ có trạng thái như thế nào?

[5, 6, 11, 12, 13]

[11, 12, 13, 5, 6]

[11, 12, 5, 6, 13]

[5, 11, 12, 6, 13]

28 / 30

Category: 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

Tags: Bộ đề 10

Câu 28: Thuật toán sắp xếp nào trong ba thuật toán đơn giản có độ phức tạp thời gian là O(N^2) trong trường hợp xấu nhất, nhưng có thể cải thiện đáng kể (xuống O(N)) trong trường hợp tốt nhất?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Cả ba đều luôn là O(N^2).

29 / 30

Category: 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

Tags: Bộ đề 10

Câu 29: Một giáo viên yêu cầu học sinh tự sắp xếp danh sách tên theo thứ tự bảng chữ cái. Học sinh A tìm tên đầu tiên trong toàn bộ danh sách, ghi ra giấy, gạch tên đó khỏi danh sách ban đầu, rồi lặp lại quy trình với danh sách còn lại. Học sinh A đang mô phỏng thuật toán sắp xếp nào?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Một thuật toán khác không được học.

30 / 30

Category: 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

Tags: Bộ đề 10

Câu 30: Trong các thuật toán sắp xếp đơn giản (Chọn, Nổi bọt, Chèn), thuật toán nào thường được sử dụng làm bước con trong các thuật toán sắp xếp phức tạp hơn (như Quicksort hoặc Mergesort) để xử lý các mảng con nhỏ?

Sắp xếp Chọn

Sắp xếp Nổi bọt

Sắp xếp Chèn

Không có thuật toán nào trong số này.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Đề trắc nghiệm liên quan:

Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 10: Lưu Trữ Dữ Liệu Và Khai Thác Thông Tin Phục Vụ Quản Lí
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 18: Thực Hành Xác Định Cấu Trúc Bảng Và Các Trường Khóa
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 29: Thực Hành Thiết Kế Chương Trình Theo Mô Đun
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 8: Thực Hành Nâng Cao Sử Dụng Thư Điện Tử Và Mạng Xã Hội
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 24: Đánh Giá Độ Phức Tạp Thời Gian Thuật Toán

Đề 01

Đề 02

Đề 03

Đề 04

Đề 05

Đề 06

Đề 07

Đề 08

Đề 09

Đề 10

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Đề trắc nghiệm liên quan:

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha