Fcs37. Hãy xác định độ phức tạp của thuật toán Quick Sort trong trường hợp xấu nhất.

Trả lời:

Độ phức tạp của thuật toán Quick Sort trong trường hợp xấu nhất là O(n$^{2}$)

Fcs38. Mã lệnh Python sau đây thể hiện hàm sắp xếp nhanh sử dụng phân đoạn Lomuto, được trích dẫn từ Hình 3 trong sách giáo khoa Tin học 11 – Khoa học máy tính,

Có thể thấy rằng trong phần cài đặt của hàm quickSort, ta lại gọi chính nó hai lần. Kỹ thuật này được gọi là đệ quy. Em hãy giải thích tại sao hàm quickSort không chạy vô hạn với một bộ tham số hợp lệ, dù nó sẽ liên tục gọi lại chính nó.

Trả lời:

Em tránh được việc đệ quy vô hạn vì phần cài đặt luôn đảm bảo điều kiện dừng là lo≥hi. Điều kiện này chắc chắn sẽ xảy ra vì kích thước của đoạn [lo, hi] sẽ luôn bị thu hẹp qua tùng lớp phân đoạn.

Fcs39. Sửa lại cách cài đặt thuật toán Quick Sort để sắp xếp một danh sách tuple (ưu tiên khoá bên trái trước, nếu khoá bên trái bằng nhau thì so sánh khoá bên phải).

Trả lời:

F340. Một công ty có n nhân viên. Đã tới cuối tháng, người chủ nhận thấy tháng này có khá nhiều nhân viên vắng làm. Ông đã kiểm tra danh sách chấm công và biết được số ngày mỗi nhân viên đã đi làm trong tháng. Sau đó là danh sách xin nghỉ phép gồm m dòng.

Hãy lập trình để xác định xem có bao nhiêu nhân viên vắng không phép và liệt kê ra các nhân viên đó theo thứ tự số buổi vắng không phép giảm dần.

Dữ liệu: Nhập từ thiết bị vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên dương n,m.

• Dòng thứ hai chứa n số nguyên b[i] là số ngày đi làm của nhân viên có số hiệu là i (Các nhân viên được đánh số 1, 2, 3,..., n).

• m dòng cuối cùng, mỗi dòng chứa thông tin dưới dạng “a d” tức là người a xin nghỉ phép vào ngày d 1≤a≤n,1≤d≤30 (giả sử tháng đang hỏi có 30 ngày). Dữ liệu vào đảm bảo trong cùng một cùng, mỗi nhân viên chỉ xin phép tối đa một lần.

Kết quả: Hiển thị ở thiết bị ra chuẩn:

• Dòng đầu tiên chứa số lượng nhân viên đã vắng không phép

• Dòng thứ hai chứa các chỉ số của các nhân viên vắng (được sắp xếp theo số lượng buổi vắng không phép giảm dần)

Ví dụ:

Trả lời: