Chủ đề 6. Kĩ thuật lập trình – Bài 20: Thực hành bài toán tìm kiếm – sách bài tập trang 67 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.
Chủ đề 6. Kĩ thuật lập trình – Bài 20: Thực hành bài toán tìm kiếm
Câu 20.1
Trong các câu lệnh sau, câu lệnh nào được dùng để mở và ghi dữ liệu vào têp “data.inp”?
A. F = openRead(“data.inp”).
B. F = openWrite(“data.inp”).
C. F = open(“data.inp”, “w”).
D. F = open(“data.inp”,”r”).
Trả lời:
Đáp án C. Câu lệnh mở tệp để ghi dữ liệu trong Python là “open” với tham số “w”.
Câu 20.2
Các dữ liệu trong tệp sẽ bị ghi đè trong trường hợp nào sau đây?
A. Tập được mở với tham số w”.
B. Tập được mở với tham số “a”.
C. Kết thúc chương trình mà không có lệnh đóng tập.
D. Cứ có lệnh mở tệp là các dữ liệu trong tệp có thể bị ghi đè.
Trả lời:
Đáp án A. Muốn dữ liệu trong tệp không bị ghi đè, chúng ta phải mở tệp với tham số “a”.
Câu 20.3
Kiểu dữ liệu nào sau đây có thể áp dụng thuật toán tìm kiếm nhị phân?
A. Dữ liệu đã được sắp xếp.
B. Dữ liệu chưa được sắp xếp.
Trả lời:
Đáp án A. Để có thể áp dụng thuật toán tìm kiếm nhị phân, yêu cầu dữ liệu đầu vào phải được sắp xếp trước, nếu dữ liệu đầu vào chưa được sắp xếp, chúng ta chỉ có thể áp dụng thuật toán tìm kiếm tuần tự .
Câu 20.4
Mô tả nào sau đây là đúng nhất cho thuật toán tìm kiếm tuần tự ?
A. Sắp xếp các phần tử trong mảng theo thứ tự, sau đó lần lượt kiểm tra từng phần tử.
B. Sắp xếp các phần tử trong mảng theo thứ tự, chia mảng dữ liệu thành hai nửa. Kiểm tra phần tử ở giữa để xem cần tiếp tục tìm kiếm ở nửa bên trái hay nửa bên phải. Lặp lại các bước trên cho đến khi tìm được phần tử cần tim.
C. Không cần sắp xếp mảng dữ liệu, lần lượt kiểm tra từng phần tử trong mảng dữ liệu.
D. Không cần sắp xếp mảng dữ liệu. Chia mảng dữ liệu thành hai nửa. Kiểm tra phần tử ở giữa để xem cần tìm kiếm ở nửa bên trái hay nửa bên phải. Lặp lại các bước trên cho đến khi tìm được phần tử cần tìm.
Trả lời:
Đáp án C. Với thuật toán tìm kiếm tuần tự, chúng ta lần lượt kiểm tra từng phần tử trong mảng dữ liệu mà không cần mảng dữ liệu đã sắp xếp.
Câu 20.5
Giả sử cần sử dụng thuật toán tìm kiếm tuần tự để tìm ra số “10” trong dãy số sau:
A= [1, 3, 9, 8, 10, 19, 27, 11, 17].
Hỏi có bao nhiêu phép so sánh cần được thực hiện?
A. 4.
B. 5.
C. 6.
D. 7.
Trả lời:
Đáp án B. Thuật toán tìm kiếm tuần tự sẽ kiểm tra lần lượt các số 1, 3, 9, 8, 10. Đến đây chúng ta đã tìm ra số cần tìm và có thể kết thúc chương trình.
Câu 20.6
Giả sử cần sử dụng thuật toán tìm kiếm nhị phân để tìm ra số “10” trong dãy số sau:
A= [1, 3, 10, 12, 14, 15, 16].
Hỏi có bao nhiêu phép so sánh cần được thực hiện?
A. 2.
B. 3.
C. 4.
D. Thuật toán không tìm thấy số cần tìm.
Trả lời:
Đáp án B. Thuật toán tìm kiếm nhị phân được thực hiện như sau:
- Bước 1: Kiểm tra số chính giữa là số “12”, lớn hơn 10 nên số cần tìm nằm ở nửa trái của dãy. Dãy cần tìm kiếm tiếp là [1, 3, 10].
- Bước 2: Kiểm tra số chính giữa của dãy thu gọn là số “3”, nhỏ hơn 10 nên số cần tìm nằm ở nửa phải của dãy. Dãy cần tìm kiếm tiếp là [10].
- Bước 3: Kiểm tra số chính giữa của dãy thu gọn là số “10″, bằng 10. Kết luận tìm ra số cần tìm và kết thúc chương trình.
Như vậy, có 3 phép so sánh cần thực hiện.
Câu 20.7
Trong các đặc điểm sau đây, đâu là ưu điểm của thuật toán tìm kiếm tuần tự ?
A. Không cần sắp xếp trước dữ liệu đầu vào.
B. Có thể hoạt động hiệu quả trên mảng dữ liệu đã sắp xếp có kích thước lớn.
C. Chỉ có thể hoạt động tốt trên mảng dữ liệu đã sắp xếp.
D. Tốc độ tìm kiếm chậm trên mảng dữ liệu có kích thước lớn.
Trả lời:
Đáp án A. Thuật toán tìm kiếm tuần tự không cần sắp xếp trước dữ liệu đầu vào. Tuy nhiên, nhược điểm của thuật toán tìm kiếm tuần tự là tốc độ tìm kiếm chậm trên tập dữ liệu có kích thước lớn. Với tập dữ liệu có kích thước lớn đã được sắp xếp, thuật toán tìm kiếm nhị phân sẽ có tốc độ tìm kiếm nhanh hơn.
Câu 20.8
Viết chương trình tìm số lớn nhất trong dãy số sau:
A= [1, 3, 9, 8, 10, 19, 27, 11, 17].
Trả lời:
Chúng ta có thể áp dụng ý tưởng của thuật toán tìm kiếm tuần tự để tìm ra số lớn nhất trong dãy số. Chúng ta lần lượt duyệt từng phần tử trong dãy số và so sánh phần tử này với phần tử lớn nhất hiện tại (phần tử lớn nhất trong các phần tử đã duyệt). Chương trình tìm kiếm phần tử lớn nhất có thể được viết như sau:
A = [1, 3, 9, 8, 10, 19, 27, 11, 17]
max = A[0]
max_index = 0
for i in range(0,len (A)):
if max < A[i]:
max_index = i
max = A[i]
print("Phần tử lớn nhất trong dãy và số thứ tự trong dãy là: ", max, max_index)Câu 20.9*
Cho dãy số với các phần tử đã được sắp xếp theo thứ tự tăng dần, trong đó một số phần tử có thể xuất hiện nhiều lần như sau:
A= [1, 1, 3, 3, 3, 10, 10, 12, 14, 14, 14, 15, 16].
Hãy chỉnh sửa thuật toán tìm kiếm nhị phân để tìm kiếm một số và đưa ra vị trí mà số đó xuất hiện lần đầu tiên.
Ví dụ: Nếu số cần tìm là số 3 thì kết luận số 3 có trong dãy, vị trí xuất hiện lần đầu tiên có chỉ số là 2 (phần tử đầu tiên trong dãy có chỉ số là 0). Nếu số cần tìm là số 5 thì kết luận không tồn tại số 5 trong dãy.
Trả lời:
Để giải bài toán này, trước hết chúng ta sử dụng thuật toán tìm kiếm nhị phân để tìm ra vị trí mà phần tử cần tìm xuất hiện trong dãy (vị trí này có thể là vị trí đầu tiên, thứ hai hoặc vị trí cuối cùng mà phần tử cần tim xuất hiện). Sau đó, chúng ta so sánh phần tử vừa tìm được với các phần tử ngay trước nó để tìm ra vị trí đầu tiên phần tử cần tim xuất hiện.
def BinarySearch(A, K):
left = 0
right = len(A) - 1
while left <= right:
mid = (left + right) // 2
if A[mid] == K:
for i in range(mid, -1, -1):
mid = i + 1
if (A[i] != K):
break
return mid
elif A[mid] < K:
left = mid + 1
else:
right = mid - 1
return -1
A = [1, 1, 3, 3, 3, 10, 10, 12, 14, 14, 14, 15, 16]
K = 14
result = BinarySearch(A, K)
if result >= 0:
print("Lần đầu tiên số cần tìm xuất hiện tại vị trí", result)
else:
print("Không tìm thấy")Xem các bài giải khác: Giải Sách Bài Tập Lớp 11 Khoa Học Máy Tính Kết Nối Tri Thức Với Cuộc Sống
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
