Bài kiểm tra giữa kì 2 Tin 7 23_24

Thuật toán tìm kiếm tuần tự thực hiện công việc gì?

• Lưu trữ dữ liệu

• Sắp xếp dữ liệu theo chiều tăng dần.

• Xử lí dữ liệu.

• Tìm kiếm dữ liệu cho trước trong một danh sách đã cho

Thuật toán tìm kiếm tuần tự thực hiện công việc như thế nào?

• Sắp xếp lại dữ liệu theo thứ tự của bảng chữ cái

• Xem xét mục dữ liệu đầu tiên, sau đó xem xét lần lượt từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.

• Chia nhỏ dữ liệu thành từng phần để tìm kiếm

• Bắt đầu tìm từ vị trí bất kì của danh sách

Chọn đáp án để điền vào chỗ chấm (….) được đánh số trong các câu sau để được mô tả chính xác về thuật toán tìm kiếm tuần tự.

Bước 1. Xét phần tử ………….(1)…………của danh sách.

Bước 2. Nếu giá trị của phần tử ở vị trí đang xét …….(2)…….. giá trị cần tìm thì chuyển sang bước 4, nếu không chuyển đến vị trí tiếp theo.

Bước 3. Kiểm tra đã hết danh sách chưa. Nếu ……..(3)………… danh sách thì chuyển sang bước 5, nếu chưa thì lặp lại từ bước 2.

Bước 4. Trả lời ……(4)………. và chỉ ra vị trí phần tử tìm được. Kết thúc.

Bước 5. Trả lời………(5)…………; Kết thúc.

• (1) vị trí đầu tiên) - (2) bằng - (3) đã hết -(4) “Tìm thấy” -(5) “Không tìm thấy”

• (1) vị trí đầu tiên) - (2) đã hết -(3) bằng -(4) “Tìm thấy” -(5) “Không tìm thấy”

• (1) vị trí đầu tiên) - (2) bằng - (3) đã hết -(4) “Không tìm thấy”-(5) “Tìm thấy”

• (1) vị trí đầu tiên) - (2) bằng -(3) “Tìm thấy” - (4) đã hết -(5) “Không tìm thấy”

Kết quả lần thứ  4 khi thực hiện thuật toán tìm kiếm tuần tự để tìm số 10 trong danh sách [2, 6, 8, 4, 10, 12]

• 6  

• 4 

• 8   

• 10

Chọn câu diễn đạt đúng hoạt động của thuật toán nhị phân:

• Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

• Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

• Tìm trên danh sách bất kì, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

• Tìm trên danh sách bất kì, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

Vị trí bắt đầu khi thực hiện thuật toán nhị phân là:

• Vị đầu đầu tiên

• Vị trí ở cuối

• Vị trí ở giữa

• Vị trí bất kì

Danh sách đầu vào của thuật tìm kiếm nhị phân để tìm số 10 là?

• [2,4,8,6,0,10]

• [2,4,0,6,8,10]

• [0,2,4,6,8,10]

• [0,2,4,8,6,10]

Chọn đáp án để điền vào chỗ chấm (….) được đánh số trong các câu sau để được mô tả chính xác về thuật toán tìm kiếm nhị phân.

Bước 1. Nếu vùng tìm kiếm không có phần tử nào thì kết luận ………(1)…….và thuật toán kết thúc.

Bước 2. Xác định vị trí giữa vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.

Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận…….(2)……và thuật toán kết thúc.

Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì cùng tìm kiếm mới được thu hẹp lại, chỉ còn ……..(3)……của dãy.

Ngược lại (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn …………(4)………… của dãy.

Bước 5. Lặp lại Bước 1 đến Bước 5 cho đến vùng tìm kiếm không khi còn phần tử nào (Bước 1) hoặc tìm thấy giá trị cần tìm Bước 3

• (1) giá trị cần tìm xuất hiện ở vịt trí giữa - (2) “Không tìm thấy” - (3) nửa trước

  (4) nửa sau

• (1) nửa sau - (2) “Không tìm thấy” - (3) giá trị cần tìm xuất hiện ở vịt trí giữa - (4) nửa trước

• (1) “Không tìm thấy” - (2) giá trị cần tìm xuất hiện ở vịt trí giữa - (3) nửa sau - (4) nửa trước

• (1) “Không tìm thấy” - (2) giá trị cần tìm xuất hiện ở vịt trí giữa - (3) nửa trước

  (4) nửa sau

Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp nào?

• Tìm một phần tử trong danh sách bất kì.

• Tìm một phần tử trong danh sách đã được sắp xếp.

Kết quả lần thứ  2 khi thực hiện thuật toán tìm kiếm nhị phân để tìm số 10 trong danh sách

[0, 2, 3, 5, 4, 6, 8, 10, 12]

• 6,8,10,12

• 10,12

• 2

• 0,2,3,5