WorksheetsÔn tập bài Thuật Toán - Tin học 7
Total questions: 54
Worksheet time: 30mins
Thuật toán tìm kiếm tuần tự là:
Tìm kiếm tuần tự từng phần tử trong danh sách.
Tìm kiếm theo thứ tự giảm dần.
Chia danh sách thành hai phần để tìm kiếm.
Sử dụng công thức để tính vị trí.
Thuật toán tìm kiếm tuần tự bắt đầu kiểm tra:
Từ phần tử đầu tiên của danh sách.
Từ phần tử giữa danh sách.
Từ phần tử cuối danh sách.
Ngẫu nhiên trong danh sách.
Kết quả của thuật toán khi tìm thấy phần tử cần tìm là:
Trả về vị trí của phần tử đó trong danh sách.
Xoá phần tử trong danh sách.
In ra toàn bộ danh sách.
Dừng chương trình ngay lập tức.
Tại sao thuật toán tìm kiếm tuần tự thường chậm khi danh sách lớn?
Vì phải kiểm tra từng phần tử một.
Vì chỉ kiểm tra phần tử ở giữa.
Vì dùng quá nhiều phép toán cộng.
Vì không kiểm tra được phần tử đầu.
Khi nào thuật toán tìm kiếm tuần tự kết thúc mà không tìm thấy kết quả?
Khi đã kiểm tra hết danh sách mà không khớp.
Khi tìm được phần tử đầu tiên.
Khi danh sách bị lỗi.
Khi kiểm tra một nửa danh sách.
Trong dãy [4, 8, 15, 16, 23, 42], nếu tìm số 15 bằng tìm kiếm tuần tự, cần kiểm tra:
3 phần tử
4 phần tử
5 phần tử
6 phần tử
Áp dụng thuật toán tìm kiếm tuần tự, cho danh sách [10, 25, 30, 45], tìm giá trị 30. Thuật toán trả về:
Vị trí 3
Vị trí 2
Vị trí 4
Không tìm thấy
Với danh sách [2, 5, 7, 9, 11], nếu cần tìm số 8 bằng thuật toán tìm kiếm tuần tự thì kết quả là:
Không tìm thấy
Vị trí 3
Vị trí 4
Vị trí 5
Viết thuật toán tìm kiếm tuần tự giả định như sau: nhập dãy gồm n số nguyên và một số x cần tìm. Câu lệnh điều kiện đúng khi nào?
Khi phần tử thứ i bằng x.
Khi phần tử thứ i lớn hơn x.
Khi x chia hết cho phần tử i.
Khi phần tử thứ i nhỏ hơn x.
Trong một chương trình, học sinh viết thuật toán tìm kiếm tuần tự nhưng chương trình luôn trả về “không tìm thấy”, dù phần tử cần tìm có trong danh sách. Lỗi có thể là:
Không kiểm tra đủ tất cả các phần tử trong danh sách.
Danh sách có chứa số âm.
Dùng sai hàm hiển thị kết quả.
Sử dụng sai kiểu dữ liệu mảng.
Thuật toán tìm kiếm tuần tự được sử dụng trong kiểu dữ liệu nào?
Danh sách chưa sắp xếp.
Danh sách đã sắp xếp tăng dần.
Danh sách số nguyên tố.
Danh sách chứa chữ cái.
Biến đếm trong thuật toán tìm kiếm tuần tự thường dùng để:
Xác định vị trí phần tử đang xét.
Lưu giá trị lớn nhất.
Đếm số lần nhập dữ liệu.
Tạo vòng lặp vô hạn.
Kết thúc thuật toán tìm kiếm tuần tự khi:
Tìm thấy phần tử hoặc kiểm tra hết danh sách.
Chạy đúng 3 lần lặp.
Phần tử lớn hơn tất cả các phần tử trong danh sách.
Gặp số âm.
Trong trường hợp danh sách không có phần tử cần tìm, thuật toán sẽ:
Kiểm tra hết danh sách và thông báo không tìm thấy.
Tự động dừng giữa chừng.
Xoá phần tử đầu tiên.
Thay thế toàn bộ danh sách.
Số lượng phép so sánh trong thuật toán tìm kiếm tuần tự tỉ lệ với:
Độ dài danh sách.
Loại phần tử tìm kiếm.
Kích thước bộ nhớ.
Loại biến sử dụng.
Nếu phần tử cần tìm nằm ở cuối danh sách, thuật toán:
Mất nhiều thời gian hơn vì phải duyệt tất cả phần tử trước đó.
Tìm thấy ngay ở vòng lặp đầu tiên.
Không thể tìm được.
Phát sinh lỗi chương trình.
Áp dụng thuật toán tìm kiếm tuần tự cho danh sách [3, 6, 9, 12], tìm giá trị 6. Kết quả là:
Vị trí 2
Vị trí 3
Vị trí 1
Không tìm thấy
n tìm kiếm tuần tự cho danh sách [3, 6, 9, 12], tìm giá trị 6. Kết quả là:
Vị trí 2
Vị trí 3
Vị trí 1
Không tìm thấy
Với danh sách [7, 14, 21, 28], tìm giá trị 35 bằng thuật toán tìm kiếm tuần tự sẽ:
Trả về không tìm thấy
Trả về vị trí 4
Dừng ở vị trí 2
Báo lỗi do vượt giới hạn
Khi viết thuật toán tìm kiếm tuần tự, học sinh quên cập nhật chỉ số vòng lặp. Hậu quả là:
Vòng lặp không kết thúc gây treo chương trình.
Tìm thấy phần tử ngay lập tức.
Danh sách bị đảo ngược.
Tạo ra danh sách mới.
Cải tiến nào dưới đây giúp tối ưu hóa thuật toán tìm kiếm tuần tự?
Dừng thuật toán ngay khi tìm thấy phần tử.
Tăng độ dài danh sách mỗi lần lặp.
Sắp xếp lại danh sách sau mỗi lần kiểm tra.
Kiểm tra từ phần tử cuối về đầu.
Tìm kiếm tuần tự còn có tên gọi khác là:
Tìm kiếm tuyến tính.
Tìm kiếm lặp.
Tìm kiếm ngẫu nhiên.
Tìm kiếm phân đôi.
Biến dùng để lưu giá trị cần tìm thường được đặt tên là:
x
n
i
list
Trong ngôn ngữ lập trình, tìm kiếm tuần tự thường dùng với cấu trúc:
Vòng lặp (for hoặc while)
Câu lệnh rẽ nhánh if-else
Biến hằng
Hàm đệ quy
Đặc điểm nổi bật của thuật toán tìm kiếm tuần tự là:
Đơn giản, dễ thực hiện.
Chạy nhanh nhất.
Phức tạp nhưng hiệu quả.
Chỉ dùng cho danh sách lớn.
Vì sao thuật toán tìm kiếm tuần tự không cần sắp xếp danh sách?
Vì thuật toán kiểm tra từng phần tử theo thứ tự.
Vì thuật toán chỉ cần phần tử đầu.
Vì sử dụng thuật toán đệ quy.
Vì danh sách được nhập ngẫu nhiên.
Trong chương trình tìm kiếm tuần tự, nếu không có điều kiện dừng đúng lúc thì:
Thuật toán có thể chạy vô hạn.
Phần tử bị xoá.
Kết quả sai số.
Không cần kiểm tra phần tử cuối.
Với danh sách ['a', 'b', 'c', 'd'], tìm phần tử 'c' bằng tìm kiếm tuần tự sẽ trả về:
úc thì:
Thuật toán có thể chạy vô hạn.
Phần tử bị xoá.
Kết quả sai số.
Không cần kiểm tra phần tử cuối.
Với danh sách ['a', 'b', 'c', 'd'], tìm phần tử 'c' bằng tìm kiếm tuần tự sẽ trả về:
Vị trí 3
Vị trí 2
Vị trí 4
Không tìm thấy
Danh sách [2, 4, 6, 8, 10], tìm số 8 bằng tìm kiếm tuần tự. Lệnh kiểm tra đúng là:
Nếu list[i] == 8
Nếu list[i] > 8
Nếu 8 chia hết cho list[i]
Nếu list[i] nhỏ hơn 8
Em cần tìm tất cả vị trí của số 5 trong danh sách [1, 5, 3, 5, 7, 5]. Cải tiến nào sau đây đúng?
Không dừng lại sau lần tìm thấy đầu tiên, tiếp tục duyệt đến hết danh sách.
Dừng ngay sau khi tìm được một phần tử.
Xoá phần tử 5 đầu tiên.
Đổi số 5 thành số 0 trong danh sách.
Giả sử thuật toán tìm kiếm tuần tự đang hoạt động trong danh sách 1000 phần tử, phần tử cần tìm nằm ở cuối. Phép toán nào sau đây có thể tối ưu hoá chương trình?
Kiểm tra phần tử ở đầu và cuối cùng lúc.
Kiểm tra 3 phần tử mỗi vòng lặp.
Chuyển sang tìm kiếm nhị phân.
Sắp xếp danh sách trước khi tìm.
Thuật toán tìm kiếm tuần tự có thể áp dụng cho:
Mọi loại danh sách, kể cả chưa sắp xếp.
Chỉ danh sách số nguyên dương.
Chỉ danh sách có thứ tự tăng dần.
Danh sách có độ dài chẵn.
Kết quả trả về của thuật toán thường là:
Vị trí phần tử hoặc thông báo không tìm thấy.
Tổng giá trị các phần tử.
Danh sách đảo ngược.
Danh sách đã sắp xếp.
Trong ngôn ngữ lập trình, danh sách thường được lưu trữ dưới dạng:
Mảng (array)
Chuỗi (string)
Biểu thức (expression)
Câu lệnh điều kiện
So với tìm kiếm nhị phân, tìm kiếm tuần tự:
Chậm hơn khi danh sách lớn.
Luôn nhanh hơn.
Không cần kiểm tra giá trị.
Yêu cầu danh sách phải sắp xếp.
Chậm hơn khi danh sách lớn.
Chậm hơn khi danh sách lớn.
Luôn nhanh hơn.
Không cần kiểm tra giá trị.
Yêu cầu danh sách phải sắp xếp.
Khi phần tử cần tìm xuất hiện nhiều lần trong danh sách, thuật toán tìm kiếm tuần tự:
Chỉ trả về lần xuất hiện đầu tiên (nếu không có cải tiến).
Tự động xoá phần tử trùng.
Nhân đôi kết quả.
Chỉ trả về phần tử cuối.
Lợi ích của tìm kiếm tuần tự đối với người mới học lập trình là:
Cấu trúc đơn giản, dễ hiểu.
Tự động tối ưu chương trình.
Giúp xử lý dữ liệu lớn nhanh hơn.
Không cần kiểm tra điều kiện.
Cho danh sách ["Nam", "Linh", "Hà", "Bình"], áp dụng tìm kiếm tuần tự để tìm "Hà". Kết quả là:
Vị trí 3
Vị trí 2
Vị trí 4
Không tìm thấy
Trong Python, câu lệnh nào phù hợp để tìm kiếm tuần tự?
for i in range(len(list)): if list[i] == x: return i
if x > list: return x
while x in list: print(x)
return list.index(x)
Để đếm số lần xuất hiện của phần tử X trong danh sách bằng tìm kiếm tuần tự, cần:
Duyệt toàn bộ danh sách và tăng biến đếm khi gặp X.
Dừng lại sau khi gặp X một lần.
Sắp xếp lại danh sách rồi tìm.
Sử dụng thuật toán chia để trị.
Một học sinh viết thuật toán tìm kiếm tuần tự nhưng kết quả luôn là "tìm thấy" dù X không có trong danh sách. Nguyên nhân có thể là:
Không kiểm tra điều kiện so sánh đúng cách.
Nhập sai định dạng dữ liệu.
Danh sách bị rỗng.
Thiếu vòng lặp.
Mục đích chính của thuật toán tìm kiếm tuần tự là:
Tìm một giá trị cụ thể trong danh sách.
Tính tổng các phần tử trong danh sách.
Xoá phần tử nhỏ nhất.
Sắp xếp lại danh sách.
Một đặc điểm của thuật toán tìm kiếm tuần tự là:
Không yêu cầu danh sách được sắp xếp trước.
Luôn cần danh sách tăng dần.
Tự động đảo danh sách.
Chạy song song hai chiều.
Thuật toán tìm kiếm tuần tự là:
Không yêu cầu danh sách được sắp xếp trước.
Luôn cần danh sách tăng dần.
Tự động đảo danh sách.
Chạy song song hai chiều.
Biểu diễn thuật toán tìm kiếm tuần tự phổ biến nhất là:
Dạng sơ đồ khối hoặc mã giả.
Dạng đồ thị cây.
Dạng chuỗi ký tự.
Dạng bảng số liệu.
Lý do nên dùng thuật toán tìm kiếm tuần tự cho danh sách nhỏ là:
Đơn giản, dễ triển khai và hiệu quả với dữ liệu ít.
Luôn cho kết quả nhanh nhất.
Dễ áp dụng cho dữ liệu lớn.
Có thể kiểm tra nhiều danh sách cùng lúc.
Khi tìm kiếm tuần tự phần tử đầu tiên trong danh sách, thuật toán sẽ:
Dừng ngay sau vòng lặp đầu tiên.
Tiếp tục đến hết danh sách.
Bỏ qua phần tử đầu.
Không hoạt động đúng.
Điều kiện kết thúc thuật toán tìm kiếm tuần tự là:
Khi tìm thấy phần tử hoặc duyệt hết danh sách.
Khi tìm thấy phần tử giữa danh sách.
Khi tìm được phần tử nhỏ nhất.
Khi hết thời gian chạy chương trình.
Dùng thuật toán tìm kiếm tuần tự để kiểm tra xem số 0 có trong danh sách [-1, -2, 0, 5] không. Kết quả là:
Có, tại vị trí thứ 3
Không có
Có, tại vị trí 2
Có, tại vị trí 4
Với danh sách ['x', 'y', 'z'], viết thuật toán tìm kiếm tuần tự tìm phần tử 'a', chương trình trả về:
Không tìm thấy
Vị trí 2
Vị trí 1
Lỗi do không có vòng lặp
Một học sinh viết thuật toán tìm kiếm tuần tự không đưa ra được vị trí đúng của phần tử cần tìm, lỗi có thể nằm ở đâu?
Không cập nhật chỉ số hoặc sai điều kiện so sánh.
Sử dụng danh sách sai thứ tự.
Chạy lặp lại danh sách nhiều lần.
Không đặt tên biến đúng quy tắc.
