Data chương 2 p2

Tại mỗi bước sắp xếp của phương pháp sắp xếp nổi bọt, dãy số được duyệt bắt đầu từ đâu?

• Từ giữa dãy sang 2 bên

• Từ đầu dãy đến cuối dãy

• Từ cuối dãy lên đầu dãy

Trường hợp tốt nhất của thuật toán trộn tự nhiên là trường hợp nào?

• Dãy đầu vào có thứ tự thuận

• Dãy đầu vào có thứ tự ngược

• Khi dãy có số phần tử là số chẵn

N(N-1)/2 là số phép so sánh mà thuật toán sắp xếp chọn (Selection Sort) sử dụng trong trường hợp nào?

• Xấu nhất

• Tốt nhất

• Tất cả các trường hợp

Phương pháp trộn tự nhiên và trộn trực tiếp khác nhau ở quá trình nào?

• Quá trình trộn 2 dãy con lại thành 1 dãy có thứ tự

• Quá trình tách dãy thành các dãy con

Cho các bước sắp xếp như sau:

Bước 1 : // Chuẩn bị

k = 1; // k là chiều dài của dãy con trong bước hiện hành

Bước 2:Tách dãy a1, a2, ., an thành 2 dãy b, c theo nguyên tắc luân phiên từng nhóm k phần tử:

b = a1, ..., ak, a2k+1, ..., a3k, .

c = ak+1, ..., a2k, a3k+1, ..., a4k, .

Bước 3: Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a.

Bước 4: k = k*2; Nếu k < n thì trở lại bước 2. Ngược lại: Dừng

Dãy trên đã được sắp xếp bằng phương pháp gì?

• Nổi bọt

• Trộn trực tiếp

• Chọn trực tiếp

• Sắp xếp nhanh

 

Trường hợp tốt nhất của phương pháp sắp xếp Quick Sort là… ?

• Sắp xếp dãy theo thứ tự giảm

• Sắp xếp dãy theo thứ tự tăng

• Mỗi lần phân hoạch dãy được chia thành 2 nửa đều nhau

• Mỗi lần phân hoạch chia dãy thành 1 nửa gồm 1 phần tử gồm các phần tử còn lại của dãy

 

Lệnh nào sau đây sẽ được đưa vào dòng lệnh thứ {8} của thủ tục sau?

• t=A[j];

• A[j-1]=t;

• t=A[j-1];

• A[j]=t

 

Phần tử chốt được chọn tốt nhất trong phương pháp Quick Sort là phần tử như thế nào ?

• Lớn nhất của dãy

• Nhỏ nhất của dãy

• Phần tử trung vị (median) của dãy

• Tùy theo ý muốn

Quick Sort sắp xếp dãy a  theo thứ tự không giảm, phần tử chốt là x, duyệt từ bên trái (đầu) dãy theo chỉ số i đến dừng tại ai, duyệt từ bên phải (cuối) dãy theo chỉ số j đến dừng tại aj. Đổi chỗ ai và aj sau đó…?

• Duyệt tiếp từ 2 bên cho đến khi i≤j

• Duyệt tiếp từ 2 bên cho đến khi i≥j

• Duyệt tiếp từ 2 bên cho đến khi 1 trong 2 bên gặp chốt

• Dừng lại. Kết thúc 1 bước phân hoạch

Trường hợp xấu nhất của phương pháp sắp xếp Quick Sort là… ?

• Mỗi lần phân hoạch dãy được chia thành 2 nửa đều nhau

• Mỗi lần phân hoạch dãy được chia thành 2 nửa đều nhau

• Sắp xếp dãy theo thứ tự giảm

• Phần tử được chọn làm chốt là phần tử lớn nhất (nhỏ nhất) của dãy