All Question of Merge Sort - Tài liệu tham khảo | Đại học Hoa Sen
All Question of Merge Sort - Tài liệu tham khảo | Đại học Hoa Sen và thông tin bổ ích giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học.
Preview text:
Câu 1: Thuật toán sắp xếp nào sau đây có thời gian thực hiện ít phụ thuộc nhất vào thứ tự ban đầu của đầu vào? 1. Insertion sort 2. Quick sort 3. Merge sort 4. Selection sort
Câu 2: Thuật toán sắp xếp ____ có độ phức tạp trong trường hợp xấu nhất, thấp nhất ? 1. Selection sort 2. Bubble sort 3. Merge Sort 4. Quick Sort 5. Không ai trong số trên
Câu 3: Điều nào sao đây là độ phức tạp về thời gian trong trường hợp xấu nhất của thuật
toán sắp xếp hợp nhất ? 1. O(nlgn ) 2. O(n^1.5lgn) 3. O(n^2) 4. O(n)
Câu 4: Thuật toán sắp xếp hợp nhất hai chiều được sử dụng để sắp xếp các phần tử sau theo thứ tự tăng dần ?
200, 470, 150, 80, 90, 40, 400, 300, 120, 70.
Thứ tự của các phần tử này sau lần chuyển thứ hai của thuật toán sắp xếp hợp nhất là gì ?
1. 40, 80, 90, 150, 200, 300, 400, 470, 70, 120
2. 80, 150, 200, 470, 40, 90, 300, 400, 70, 120
3. 40, 70, 80, 90, 120, 150, 200, 300, 400, 470
4. 200, 470, 80, 150, 40, 90, 300, 400, 70, 120
Câu 5: Giả sử P, Q, R, S, T là các dãy sắp xếp có độ dài lần lượt là 20, 24, 30, 35, 50.
Chúng phải được hợp nhất thành một chuỗi duy nhất bằng cách hợp nhất hai chuỗi cùng
một lúc. Số phép so sánh cần thiết trong trường hợp xấu nhất theo thuật toán tối ưu để
thực hiện việc này là___? Đáp án: 358
Câu 6: Giả sử rằng thuật toán sáp nhập trong trường hợp xấu nhất mất 30s cho đầu vào
có kích thước 64. Điều nào sau đây gần đúng nhất với kích thước đầu vào tối đa của một
vấn đề có thể được giải trong 6 phút ? 1. 256 2. 512 3. 1024 4. 2048
Câu 7: Thuật toán sắp xếp ổn định có nghĩa là gì ?
1. Thuật toán sắp xếp ổn định nếu nó không giữ nguyên thứ tự các khóa trùng lặp
2. Thuật toán sắp xếp ổn định nếu có giữu nguyên thứ tự các khóa trùng lặp
3. Một thuật toán sắp xếp ổn định nếu có giữu nguyên thứ tự của tất cả các khóa
4. Thuật toán sắp xếp ổn định nếu nó giữ nguyên thứ tự các khóa không trùng lặp
Câu 8: Thời gian chạy trong trường hợp xấu nhất của sắp xếp chèn, sắp xếp hợp nhất và
sắp xếp nhanh tương ứng là ?
1. O(nlogn), O(nlogn) và O(n^2) 2. O(n^2), O(n^2) và O(nlogn)
3. O(n^2), O(nlogn) và O(nlogn)
4. O(n^2), O(nlogn) và O(n^2)
Câu 9: Nếu người ta sử dụng thuật toán sắp xếp hợp nhất hai chiều thẳng để sắp xếp các
phần tử sau theo thứ tự tăng dần 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 thì thứ tự của các phần
tử này sau lần vượt qua thứ hai của thuật toán là ?
1. 8, 9, 15, 20, 47, 4, 12, 17, 30, 40
2. 8, 15, 20, 47, 4, 9, 30, 40, 12, 17
3. 15, 20, 47, 4, 8, 9, 12, 30, 40, 17
4. 4, 8, 9, 15, 20, 47, 12, 17, 30, 40
Câu 10: Trong trường hợp trường hợp tốt nhất, hiệu suất thời gian của Merge Sort là bao nhiêu? a) O(n) b) O(n log n) c) O(n^2) d) O(1)
Câu 11: Merge Sort có thể được áp dụng trên danh sách liên kết không? a) Có b) Không
Câu 12: Thuật toán Merge Sort có ổn định hay không? a) Có b) Không
Câu 13: Merge Sort cần bao nhiêu bộ nhớ bổ sung để thực hiện quá trình gộp? a) O(1) b) O(n) c) O(n/2) d) O(log n)
Câu 14: Merge Sort có thể được sử dụng để sắp xếp các phần tử không so sánh được, như
các tập tin dữ liệu, không? a) Có b) Không
Câu 15: Merge Sort thuộc loại thuật toán sắp xếp nội tại hay ngoại tại?
a) Sắp xếp nội tại b) Sắp xếp ngoại tại
Câu 16: Thuật toán Merge Sort có hiệu suất thời gian cố định không phụ thuộc vào dữ liệu đầu vào? a) Có b) Không
Câu 17: Trong Merge Sort, thứ tự của hai phần tử có giá trị bằng nhau được duyệt qua
trong quá trình gộp làm thế nào? a) Đảo ngược b) Bất kỳ thứ tự nào c) Giữ nguyên
d) Sắp xếp theo thứ tự tùy ý
Câu 18: Merge Sort có thể được sử dụng để sắp xếp các phần tử số thực không? a) Có b) Không
Câu 19: Trong trường hợp xấu nhất, Merge Sort cần bao nhiêu phép so sánh để sắp xếp một mảng kích thước n? a) O(1) b) O(n) c) O(n log n) d) O(n^2)
Câu 20: Merge Sort có thể được sử dụng để sắp xếp một danh sách một chiều không liên tục không? a) Có b) Không
Câu 21: Ý tưởng phương pháp sắp xếp Trộn (Merge sort) là:
A) Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần
tử nào nhỏ hơn được đứng vị trí trên.
B) Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
C) Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước khoá
gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).
D) Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với
phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai,ba...
Câu 22: Trong các giải thuật sắp xếp, giải thuật nào áp dụng phương pháp "Chia để trị"? A) Quick sort, Heap sort B) Quick sort, Bubble sort C) Qucick sort, Insert sort
D) Quick sort, Merge sort
Câu 23: Cho dãy số : 3 1 6 0 5 4 8 2 9 7 và các bước sắp xếp sau:
Bước 1: 1 3 6 0 5 4 8 2 9 7
Bước 2: 1 3 6 0 5 4 8 2 9 7
Bước 3: 1 3 6 0 5 4 8 2 9 7
Bước 4: 0 1 3 5 6 4 8 2 9 7
Bước 5: 0 1 3 5 6 4 8 2 9 7
Bước 6: 0 1 3 5 6 2 4 8 9 7
Bước 7: 0 1 3 5 6 2 4 8 7 9
Bước 8: 0 1 3 5 6 2 4 7 8 9
Bước 9: 0 1 2 3 4 5 6 7 8 9
Các bước trên dựa theo giải thuật sắp xếp nào? A) Quick sort B) Select sort C) Merge sort D) Insert sort