ÔN TẬP CHỦ ĐỀ 5: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH (PHẦN 1 - 20 CÂU)

Câu 1: Hãy mô tả thuật toán tìm kiếm tuần tự.

Trả lời:

Bước 1: Xét vị trí đầu tiên của danh sách.

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

Bước 3: Kiểm tra đã hết danh sách chưa. Nếu đã hết 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: Thông báo “Tìm thấy” và chỉ ra vị trí phần tử tìm được. Kết thúc.

Bước 5: Thông báo “Không tìm thấy”. Kết thúc.

Câu 2: Thuật toán tìm kiếm nhị phân là gì.

Trả lời:

- Thuật toán tìm kiếm nhị phân là thuật toán thực hiện tìm trên danh sách đã được sắp xếp theo thứ tự từ nhỏ đến lớn. Bắt đầu từ vị trí ở giữa danh sách.

- Tại mỗi bước lặp, so sánh giá trị cần tìm với giá trị của vị trí giữa danh sách, nếu bằng thì dừng lại, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách.

- Chừng nào chưa tìm thấy và vùng tìm kiếm còn phần tử thì còn tiếp tục.

Câu 3: Thuật toán sắp xếp nổi bọt là gì?

Trả lời:

Thuật toán sắp xếp nổi bọt là thuật toán sắp xếp được thực hiện bằng cách hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.

Câu 4: Thuật toán tìm kiếm tuần tự yêu cầu danh sách cần tìm phải được sắp xếp không?

Trả lời:

Thuật toán tìm kiếm tuần tự không yêu cầu danh sách cần tìm phải được sắp xếp. Thuật toán sẽ tìm kiếm lần lượt từ đầu danh sách đến khi tìm được hoặc là đến cuối danh sách nên không cần danh sách phải sắp xếp theo trình tự.

Câu 5: Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp nào?
Trả lời:

Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp danh sách đã được sắp xếp và yêu cầu đi tìm một phần tử bất kì.

Câu 6: Em hãy chọn thuật toán sắp xếp hợp lý cho từng trường hợp sau:

a) Hoán đổi vị trí hai phần tử liên tiếp khi chúng không đúng thứ tự là thuật toán nào?

b) Tìm phần tử nhỏ nhất trong dãy và đổi chỗ phần tử này với phần tử đầu tiên của dãy chưa được sắp xếp là thuật toán nào?

Trả lời:

a) Thuật toán sắp xếp nổi bọt.

b) Thuật toán sắp xếp chọn.

Câu 7: Em hãy điền các từ/cụm từ:

[đã hết, “Không tìm thấy”, bằng, vị trí đầu tiên, “Tìm thấy”]

vào chỗ chấm (...) 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ự.

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

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

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

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

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

a) vị trí đầu tiên

b) “Tìm thấy”

c) đã hết

d) bằng

e) “Không tìm thấy”

Câu 8: Hãy ghép mỗi nội dung ở cột A với những nội dung phù hợp ở cột B để xác định đầu vào và đầu ra của thuật toán tìm kiếm nhị phân.

Trả lời:

1-c 1-d 2-a 2-b

Câu 9: Nếu sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số 8, 22, 7, 19, 5 theo thứ tự tăng dần thì số lần thực hiện thao tác hoán đổi giá trị trong vòng lặp thứ nhất là bao nhiêu?

Trả lời:

Đáp án là 2.

Vòng lặp 1:

| 8 | 22 | 7 | 19 | 5 | → lần 1: | 7 | 22 | 8 | 19 | 5 | → lần 2: | 5 | 22 | 7 | 19 | 8 |

Câu 10: Cho danh sách các số [1, 4, 6, 7, 8, 10].

Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu bước để tìm thấy số 7.

Trả lời:

Thuật toán tìm kiếm tuần tự cần thực hiện 4 bước để tìm thấy số 7:

Bước 1: Thấy số 1.

Bước 2: Thấy số 4.

Bước 3: Thấy số 6.

Bước 4: Thấy số 7.

Câu 11: Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy “Mai" trong danh sách ["Hoa”, ”Lan”, "Ly”, ”Mai”, ”Phong”, ”Vi]?

Trả lời:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 3.

So sánh “Ly” và “Mai”. Vì “L” đứng trước “M” trong bảng chữ cái nên bỏ đi nửa đầu danh sách.

Bước 2: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí số 5.

So sánh “Phong” và “Mai”. Vì “P” đứng sau “M” trong bảng chữ cái nên bỏ đi nửa sau danh sách.

Bước 3: Xét vị trí ở giữa của dãy giữa sau danh sách, đó là vị trí số 4.

So sánh “Mai” và “Mai”. Vì hai giá trị bằng nhau nên thuật toán kết thúc

Sau 3 bước đã tìm thấy “Mai” trong danh sách.

Câu 12: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

Trả lời:

Câu 13: Thực hiện thuật toán tìm kiếm tuần tự để tìm số 10 trong danh sách các số [2, 6, 8, 4, 10, 12]. Đầu ra của thuật toán là ?

Trả lời:

Thực hiện thuật toán tìm kiếm tuần tự để tìm số 10:

Bước 1: Tìm thấy số 2 ở vị trí đầu tiên.

Bước 2: Tìm thấy số 6 ở vị trí thứ hai.

Bước 3: Tìm thấy số 8 ở vị trí thứ ba.

Bước 4: Tìm thấy số 4 ở vị trí thứ tư.

Bước 5: Tìm thấy số 10 ở vị trí thứ năm.

Bước 6: Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ năm của danh sách.

Câu 14: Cho danh sách sau:

Em hãy viết các bước thực hiện thuật toán tìm kiếm nhị phân để tìm khách hàng tên “Hoà” trong danh sách trên.

Trả lời:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 5

So sánh “Hoà” và “Mai”. Vì “H” đứng trước “M” trong bảng chữ cái nên bỏ đi nửa sau danh sách.

Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3

So sánh “Hòa” và “Hòa”, vì hai giá trị bằng nhau nên thuật toán kết thúc.

Sau 2 bước đã tìm thấy tên khách hàng tên “Hoà” nên thuật toán kết thúc.

Câu 15: Em hãy nêu sự khác nhau giữa thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chọn?
Trả lời:

Sự khác nhau giữa thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chọn là:

- Cách thức hoạt động :

+ Thuật toán sắp xếp nổi bọt di chuyển lần lượt qua danh sách, so sánh cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự. Quá trình này lặp lại cho đến khi không còn phần tử nào cần phải hoán đổi.

+ Thuật toán sắp xếp chọn lựa chọn phần tử nhỏ nhất từ danh sách và đặt nó ở vị trí đầu tiên. Sau đó, nó chọn phần tử nhỏ nhất thứ hai và đặt nó ở vị trí thứ hai, và tiếp tục như vậy cho đến khi danh sách được sắp xếp hoàn toàn.

- Hiệu suất: Thuật toán sắp xếp nổi bọt thường sẽ hiệu quả hơn thuật toán sắp xếp chọn đối với danh sách nhỏ hoặc đã gần sắp xếp. Tuy nhiên thì cả 2 đều không thể hoạt động tốt với danh sách lớn vì phải thực hiện nhiều lần lặp.

Câu 16: Em hãy lập danh sách những cuốn sách mà em có. Sau đó sử dụng thuật toán tìm kiếm tuần tự để tìm một cuốn sách trong danh sách đó.

Trả lời:

- Danh sách tên các sách: Toán, Ngữ Văn, Tiếng Anh, Lịch Sử, Địa Lý, Sinh Học, Vật Lý.

- Sử dụng thuật toán tuần tự tìm sách Địa Lý.

Câu 17: Cho bảng điểm môn Tin học của học sinh tổ một như sau:

a) Em hãy sắp xếp lại danh sách theo thứ tự tăng dần của Điểm.

b) Em hãy liệt kê các bước lặp thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học. Hãy cho biết tên học sinh đó

Trả lời:

a) Dựa vào kiến thức đã học và thuật toán tìm kiếm nhị phân

b) Các bước thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học

Vùng tìm kiếm là dãy số: 7,5 8,0 8,5 9,0 9,5 10

Bước 1. Chọn phần tử ở giữa, đó là 8,5.

So sánh ta có 9,5 > 8,5, do đó vùng tìm kiếm thu hẹp chỉ còn nửa sau của danh sách.

Bước 2. Chọn phần tử ở giữa, đó là 9,5.

So sánh ta có 9,5 = 9,5, tìm thấy giá trị cần tìm nên thuật toán dừng lại.

Câu 18: Hãy mô tả thuật toán sắp xếp nổi bọt.

Trả lời:

1. Với vị trí đầu tiên, thực hiện một vòng lặp như sau:

1.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên.

1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.

1.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên.

2. Với vòng lặp thứ hai, em thực hiện một vòng lặp tương tự như trên.

2.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai.

2.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.

2.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai.

3. Tương tự như trên với các vị trí thứ 3, thứ tư,… đến vị trí trước vị trí cuối cùng.

4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Câu 19: Thực hành: Em hãy tìm kiếm thông tin trên internet để lập bảng danh sách khoảng 10 mặt hàng của mỗi mặt hàng. Sau đó thực hiện thuật toán tìm kiếm tuần tự để tìm kiếm một mặt hàng mà em thích nhất và cho biết đơn giá của mặt hàng đó.

Trả lời:

Bước 1. Tìm kiếm thông tin trên internet, lập bảng danh sách khoản 10 mặt hàng và đơn giá mỗi mặt hàng.

Bước 2. Chỉ ra tên một mặt hàng mà em thích nhất.

Bước 3. Lập bảng liệt kê các bước thực hiện thuật toán tìm kiếm tuần tự để tìm tên mặt hàng mà em thích nhất trong danh sách ở bước 1.

Câu 20: Điểm môn Tin học của tổ một lớp 7A được ghi trong bảng sau:

Em hãy sắp xếp lại danh sách theo thứ tự tăng dần của điểm bằng cách dùng thuật toán sắp xếp nổi bọt và sắp xếp chọn.

Trả lời:

Kết quả các vòng thực hiện sắp xếp nổi bọt để sắp xếp điểm theo thứ tự tăng dần:

Kết quả các vòng lặp thực hiện sắp xếp chọn để sắp xếp điểm theo thứ tự tăng dần:

Danh sách sẽ được sắp xếp lại như bảng sau: