Mô tả “Ở mỗi bước thuật toán lấy một phần tử ở phần chưa được sắp xếp và đưa vào đúng vị trí của nó trong phần dãy số đã được duyệt” là đúng nhất với thuật toán sắp xếp nào sau đây?

A. Thuật toán sắp xếp chèn. B. Thuật toán sắp xếp chọn.

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

D. Các thuật toán ở phương án A, B, C đều không phù hợp.

Mô tả “Thuật toán lần lượt duyệt từng cặp phần tử trong danh sách, đổi chỗ các cặp phần tử chưa đúng thứ tự” là đúng nhất với thuật toán sắp xếp nào sau đây?

A. Thuật toán sắp xếp chèn.

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

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

D. Các thuật toán ở phương án A, B, C đều không phù hợp.

Trong một số ứng dụng, chúng ta phải sắp xếp dữ liệu ngay khi chúng được thêm vào một dãy số. Ví dụ, giả sử đã có một danh sách dữ liệu đã sắp xếp và thường xuyên phải bổ sung thêm các dữ liệu mới vào danh sách. Theo em, thuật toán sắp xếp nào là phù hợp nhất với ứng dụng ở trên?

A. Sắp xếp chọn.

B. Sắp xếp chèn.

C. Sắp xếp nổi bọt.

D. Các thuật toán ở phương án A, B, C đều không phù hợp.

Áp dụng thuật toán sắp xếp chọn cho dãy số sau:

A [4, 6, 1, 3, 10, 7]

Thứ tự các phần tử trong dãy như thế nào sau vòng lặp đầu tiên?

A. 3, 1, 4, 6, 10, 7.

C. 1, 3, 4, 6, 7, 10.

B. 1, 4, 6, 3, 10, 7.

D. 1, 6, 4, 3, 10, 7.

Cho trước hai dãy số A, B, trong đó dãy A đã được sắp xếp đúng. Viết chương trình mô tả hàm insert(A, B) đưa tất cả các phần tử của B vào A mà vẫn phải giữ đúng thứ tự sắp xếp đúng của A.

Ví dụ: A = [1, 4], B = [5, 2, 3] thì sau khi thực hiện hàm insert(A, B), được dãy A = [1, 2, 3, 4, 5].

Ý tưởng của thuật toán sắp xếp nổi bọt được mô tả bao gồm hai vòng lặp, Ý vòng lặp bên trong sẽ duyệt từng phần tử từ bên phải sang và đổi chỗ hai phần tử cạnh nhau nếu chúng sắp xếp không đúng. Sau mỗi vòng lặp bên trong thì phần tử nhỏ nhất sẽ được đưa lên vị trí đúng ở phía đầu dãy.

Ý tưởng này được mô tả bằng đoạn mã giả sau:

1 Lặp n - 1 lần

2 Cho chỉ số j chạy từ phải sang đến vị trí thứ 2 của dãy

3 Nếu A[j] < A[j-1] thì đổi chỗ 2 phần tử A[j], A[j-1]

Em hãy viết chương trình mô tả đoạn mã giả trên.

Trong trường hợp nào thuật toán sắp xếp chọn theo cách trên sẽ không cần thực hiện lệnh đổi chỗ hai phần tử tại dòng 8 của mô tả thuật toán trong sách giáo khoa?

Viết lại chương trình mô tả thuật toán sắp xếp chọn đã mô tả trong Câu 21.6 sử dụng hàm min() của Python.

Ý tưởng của thuật toán sắp xếp chọn đã được mô tả trong sách giáo khoa như sau:

1 def SelectionSort(A):

2 for i in range(n-1):

3 Chọn phần tử nhỏ nhất trong dây A[i], A[i+1],

A[n-1]

4 Đồi chỗ phần từ này với A[i]

Nếu thay dòng 3 bằng A + 1] A + 2]. ... An – 1] thì thuật toán còn đúng không?

Quan sát lại ý tưởng của thuật toán sắp xếp chèn

1 Cho chỉ số i chạy từ phần tử thứ hai đến cuối dày

2 Chèn phần tử A[i] vào vị trí đúng của dây đã sắp xếp A[e], A[1], ..., A[i-1]

Có thể viết riêng các lệnh của thao tác “chèn” trong dòng 2 ở trên thành một hàm độc lập được không? Nếu được thì viết lại thuật toán này theo cách mới,

Với thuật toán sắp xếp chèn, khi nào thuật toán thực hiện nhiều phép so sánh nhất?

Với thuật toán sắp xếp chèn, khi nào thuật toán thực hiện ít phép so sánh nhất?

Viết lại thuật toán chèn theo cách đã mô tả trong câu trên khác cách mô tả trong sách giáo khoa.

 1 Cho chỉ số i chạy từ phần từ thứ hai đến cuối dây

2 Chèn phần tử A[i] vào vị trí đúng của dây đã sắp xếp A[0], A[1], A[i-1]

Nếu công việc chèn tại dòng 2 ở trên được thực hiện như sau:

j = i

while j>e and A[j] < A[j-1]:

đổi chỗ Aljl, Aj-1]

j = j - 1

Thuật toán được mô tả theo cách trên có đúng không?

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.

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].

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.

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.

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.

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 tìm. 

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.

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.

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 đè.

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").

C. F = open("data.inp", "w").

B. F = openWrite("data.inp").

D. F = open("data.inp","r").

Em hãy giúp bạn Minh cách chơi tối ưu nhất cho trò chơi lật thẻ bài đã mô tả trong sách giáo khoa.

Viết chương trình cải tiến thuật toán tìm kiếm nhị phân trong sách giáo khoa (sách giáo khoa) để việc tìm kiếm nhanh hơn nếu K nằm ngoài vùng giá trị của dãy A.

Với thuật toán toán tìm kiếm nhị phân, khi nào thì việc tìm kiếm sẽ chậm nhất, cần nhiều phép so sánh nhất?

Với thuật toán tìm kiếm nhị phân, khi nào thì tìm kiếm nhanh nhất, cần ít phép so sánh nhất?

Viết thuật toán và chương trình tìm kiếm tuần tự mở rộng như sau:

Cho trước dãy A và giá trị K. Cần tìm tất cả các phần tử trong A có giá trị bằng K. Kết quả trả về là một list chỉ số của các phần tử bằng K. Ngược lại, nếu không tìm thấy thì trả về list rỗng.

Ví dụ A: = [1,0,3,2,5,1,8], K = 1 thì kết quả trả về là list [0, 5).

Giả sử dữ liệu tên và điểm thi môn Tin học của các bạn lớp em được cho dưới dạng sau, ví dụ:

[(“Hà”, 7.5), (“Bình”, 8), (“Quang”,9.2), (“An”, 10)]

Viết chương trình thực hiện các việc sau:

Nhập một điểm số từ bàn phím. Sau đó tìm kiếm xem trong lớp có bạn nào có điểm thi bằng điểm đã nhập không. Nếu có thì chỉ cần thông báo một bạn, ví dụ: Tìm thấy bạn An.

– Nếu không thấy thì thông báo: Không tìm thấy.

Cho ma trận số A bậc m x n. Viết chương trình thực hiện việc tìm kiếm tuần tự trên ma trận A. Giả sử K là giá trị cần tìm kiếm. Nếu tìm thấy sẽ trả về cặp chỉ số phần tử (i, j) có giá trị K, tức là A[i][j] = K, nếu không thấy sẽ trả về (-1,-1).

Cho ma trận số A bậc m x n. Viết chương trình thực hiện việc tìm kiếm tuần

tự trên ma trận A. Giả sử K là giá trị cần tìm kiếm. Nếu tìm thấy sẽ trả về cặp chỉ số phần tử (i, j) có giá trị K, tức là A[i][j] = K, nếu không thấy sẽ trả về (-1,-1).

Có ý kiến cho rằng: Thiết kế các thuật toán tìm kiếm phụ thuộc rất nhiều vào cấu trúc dữ liệu của miền cần tìm kiếm. Điều đó đúng hay sai?

Khi nào thì thuật toán tìm kiếm tuần tự trên một danh sách tốn nhiều thời gian nhất?

Viết chương trình khai báo một mảng hai chiều 8x8 biểu diễn trạng thái của

một bàn cờ vua. Giá trị một ô bàn cờ là 0 nếu không có quân cờ. Bên quân trắng sử dụng giá trị 1 đến 6 lần lượt cho các quân vua, hậu, xe, mã, tượng, tốt của bên trắng. Tương tự quân đen sử dụng giá trị -1 đến -6. Các cột bàn cờ được kí hiệu bằng các kí tự A, B, C, D, E, F, G, H trong khi đó các dòng được kí hiệu bằng số 1 đến 8 từ dưới lên.

Giả sử quân trắng chuẩn bị đi, hãy in ra vị trí các quân xe trắng cùng các ô nó có thể được đi ở nước tiếp theo.

Gợi ý: Đầu tiên cần tìm vị trí các quân xe trắng bằng cách dùng hai vòng lặp duyệt qua tất cả các hàng và cột của mảng hai chiều tìm các ô có giá trị là 3 (ứng với quân xe trắng). Vì con xe có thể đi dọc và ngang nên để tìm các ô nó có thể đi chỉ cần duyệt từ vị trí mỗi con xe theo 4 hướng trên, dưới, trái, phải cho đến khi gặp một quân cờ khác hoặc đến biên bàn cờ.

Viết chương trình yêu cầu người dùng nhập vào toạ độ ba đỉnh của một tam giác. Lưu các toạ độ đó trong một mảng hai chiều sau đó tính chu vi tam giác.

Em hãy lưu điểm tổng kết ba môn học Toán, Ngữ văn, Tiếng Anh của các học sinh vào một mảng hai chiều, mỗi dòng là điểm của một học sinh theo thứ tự Toán, Ngữ văn, Tiếng Anh. Sau đó tính điểm trung bình cả ba môn của mỗi học sinh và số thứ tự của học sinh có điểm cao nhất mỗi môn học. Trường hợp nhiều học sinh cùng đạt điểm cao nhất trong một môn học thì chỉ cần in ra số thứ tự của học sinh đầu tiên.

Viết chương trình hỏi số điện thoại người dùng, lưu các chữ số vào một

mảng. Sau đó thống kê các chữ số không xuất hiện trong số điện thoại đó. Định dạng số điện thoại nhập vào chỉ gồm các chữ số, không có các kí tự khác. Nếu tất cả các chữ số đều xuất hiện thì thông báo “Số điện thoại này gồm tất cả các chữ số từ 0 đến 9”.

Hãy dự đoán nội dung được in ra bởi chương trình sau:

1 danh_sach

= [0, 1, 2, 3, 4, 5, 6]

2_print(danh_sach[-1])

3_print(danh_sach[-5:-1])

Khi sử dụng lệnh append để bổ sung một phần tử vào list thì phần tử đó được chèn vào vị trí nào?

A. Đầu tiên.

C. Vị trí ứng với chỉ số 1.

B. Vị trí được chỉ định.

D. Cuối cùng.

Hàm nào sau đây dùng để đếm số phần tử của mảng một chiều trong Python?

A. count().

B. length().

C. len().

D. size().