F19. Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm tuần tự áp dụng cho dãy số {11, 70, 18, 39, 63, 52, 41, 5} để tìm:

1) x = 39.

2) x = 60.

Trả lời:

Dãy xuất phát:

 Dãy

 a1

a2 

a3 

a4 

a5 

a6 

a7 

a8 

 11

70 

18 

39 

63 

52 

41 

1) Số phải tìm là x (x=39). Các bước thực hiện tìm kiếm:

Bước

Thực hiện

1

So sánh số ở đầu dãy với x:

Vì a1 = 11 $\neq $x nên chuyển sang xét số tiếp theo a2 trong dãy

2

 So sánh số đang xét với x:

Vì a2 = 70 $\neq $x nên chuyển sang xét số tiếp theo a3 trong dãy.

3

 So sánh số đang xét với x:

Vì a3 = 18 $\neq $x nên chuyển sang xét số tiếp theo a4 trong dãy.

4

 So sánh số đang xét với x:

Vì a4 = 39 = x

Kết luận: Tìm thấy x ở vị trí thứ 4 trong dãy; kết thúc thuật toán.

2) Số phải tìm là x (x=60). Các bước thực hiện tìm kiếm:

Bước

Thực hiện

1

So sánh số ở đầu dãy với x:

Vì a1 = 11 $\neq $x nên chuyển sang xét số tiếp theo a2 trong dãy

2

  So sánh số đang xét với x:

Vì a2 = 70 $\neq $x nên chuyển sang xét số tiếp theo a3 trong dãy.

3

  So sánh số đang xét với x:

Vì a3 = 18 $\neq $x nên chuyển sang xét số tiếp theo a4 trong dãy.

 

 ...

8

  So sánh số đang xét với x:

Vì a8= 55 $\neq $x và không chuyển số tiếp theo được nữa vì hết dãy.

Kết quả "Không tìm thấy".

F20. Hãy trình bày diễn biến từng bước của thuật toán sắp xếp chọn dần áp dụng cho dãy số  {11, 70, 18, 39, 63, 52, 41, 5} để được dãy số giảm dần.

Trả lời:

Dãy (a)

 a1

a2 

 a3

a4 

a5 

a6 

a7 

a8 

Ban đầu, i = 1

 11

70 

18 

39 

63 

52 

41 

Sau bước 1, i = 2

 70

11 

18 

39 

63 

52 

41 

 Sau bước 2, i = 3

 70

63 

18 

39 

11 

52 

41 

 Sau bước 3, i = 4

 70

63 

52 

39 

11 

18 

41 

 Sau bước 4, i = 5

 70

63 

52 

41 

11 

18 

39 

 Sau bước 5, i = 6

 70

63 

52 

41 

 39

18 

11 

 Sau bước 6, i = 7

 70

63 

52 

41 

39 

18 

11 

 Sau bước 7

 70

63 

52 

41 

39 

18 

11 

 Dãy kết quả

 70

63 

52 

41 

39 

18 

11 

F21. Hãy trình bày diễn biến từng bước của thuật toán sắp xếp chọn dần áp dụng cho dãy số  {11, 70, 18, 39, 63, 52, 41, 5} để được dãy số tăng dần.

Trả lời:

Xuất phát, i=1

 11

70 

18 

39 

63 

52 

41 

Lượt thứ nhất

 11

18

39 

63 

52 

41 

70 

Lượt thứ hai

 11

18 

39 

52 

41 

63 

70 

 Lượt thứ ba

 11

18 

39 

41 

52 

63 

70 

 Lượt thứ tư

 11

18

39 

41 

52 

63 

70 

 Lượt thứ năm

 11

18 

39 

41 

52 

63 

70 

 Lượt thứ sáu

 11

18 

39 

41 

52 

63 

70 

 Lượt thứ bảy

 5

11 

18 

39 

41 

52 

63 

70 

 Lượt thứ tám

 5

11 

18 

39 

41 

52 

63 

70 

 Dãy kết quả

 5

11 

18 

39 

41 

52 

63 

70 

F22. Cho dãy số {5, 11, 18, 39, 41, 52, 63, 70}. Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm nhị phân để tìm kiếm x trong dãy.

1) x = 39

2) x = 60.

Trả lời:

1) Số phải tìm là x = 39:

 Dãy (a)

 a1

a2 

a3 

a4 

a5 

a6 

a7 

a8 

 Xuất phát

 5

11 

18 

39 

41 

52 

63 

70 

 Bước 1

 5

11 

18 

39 

 

 

 

 

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a8. Lấy a4 là số có vị trí giữa dãy. Vì x = a4 nên đã tìm thấy x = 39 tại vị trí thứ 4.

2) Số phải tìm là x = 60.

 Dãy (a)

 a1

a2 

a3 

a4 

a5 

a6 

a7 

a8 

 Xuất phát

 5

11 

18 

39 

41 

52 

63 

70 

 Bước 1

 

 

 

 

 41

52 

63 

70 

 

 

 

 

 

 

 

63 

70 

 

 

 

 

 

 

 

 63

 

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a8. Lấy a4 là số có vị trí giữa dãy.

Vì x > a4 nên nửa đầu dãy (có nền màu xám nhạt) chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con từ a5 đến a8.

Chia đôi lần 2: lấy a6 là số có vị trí giữa dãy còn lại.

Vì x>a6 nên nửa đầu dãy (có nền màu xám nhạt) chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con từ a7 đến a8.

Chia đôi lần 3: lấy a7 là số có vị trí giữa dãy còn lại.

Vì x<a7 nên nửa sau dãy (có nền màu xám nhạt) chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con một phần tử a7.

Chỉ còn một phần tử, không chia đôi nữa, so sánh thấy x khác a. Kết luận: Không tìm thấy.