Radix Sort va Quick Sort - Tài liệu tham khảo | Đại học Hoa Sen
Radix Sort va Quick 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:
Trắc nghiệm: Radix Sort Câu1:
Sắp xếp danh sách sau bằng thuật toán sắp xếp Radix.
329, 457, 839, 436, 720, 355, 657
Đầu ra của thuật toán sau lần vượt qua thứ hai là gì?
1. 329, 355, 436, 457, 657, 720, 839
2. 355, 329, 457, 436, 720, 657, 839
3. 720, 329, 436, 839, 355, 457, 657
4. 720, 355, 436, 457, 657, 329, 839
Câu 2: Độ phức tạp về thời gian trong trường hợp tốt nhất của thuật toán sắp xếp cơ số là gì? 1. Ω(n log(n)). 2. Ω(n+k). 3. Ω(n). 4. Ω(nk).
Câu 3: Hãy xem xét một mảng các số nquyên dương trong khoảng từ 123456 đến
876543, thuật toán sắp xếp nào có thể được sử dụng để sắp xếp các số này theo thời gian tuyển tính?
1. Impossible to sort in linear time 2. Radix Sort 3. Insertion Sort 4. Bubble Sort
Câu 4: Số lượng so sánh tối đa cần thiết để sắp xếp 9 mục bằng cách sử dụng sắp
xếp cơ sở là (giả sử mỗi mục là số bát phân có 5 chữ số): 1. 45 2. 72 3. 360 4. 450
Câu 5: Thời điểm nào sau đây là thời điểm tốt nhất để sắp xếp n số nguyên trong khoảng 0 đến n^2-1 1. O(logn) 2. O(n) 3. O(n log n) 4. O(n^2)
Câu 6: Cho một mảng trong đó các số nằm trong khoảng từ 1 đến n^6, thuật
toán sắp xếp nào có thể được sử dụng để sắp xếp các số này theo thời gian tuyến tính?
1. Not possible to sort in linear time 2. Radix Sort 3. Counting Sort 4. Quick Sort
Câu 7: Nếu chúng ta sử dụng Radix Sort để sắp xếp n số nguyên trong dãy
(n^k/2,n^k], với một số k>0 độc lập với n thì thời gian thực hiện sẽ là bao nhiêu? 1. O(n) 2. O(kn) 3. O(nlogn) 4. O(n2)
Câu 8: Nếu có n số nguyên cần sắp xếp, mỗi số nguyên có d chữ số và mỗi chữ số
nằm trong tập {1, 2, ..., k}, sắp xếp cơ số có thể sắp xếp các số theo: 1. O (k (n + d)) 2. O (d (n + k)) 3. O ((n + k) lg d) 4. O ((n + d) lg k)
Câu 9: Nếu có n số nguyên cần sắp xếp, mỗi số nguyên có d chữ số và mỗi chữ số
thuộc tập {1, 2, ..., k}, sắp xếp cơ số có thể sắp xếp các số theo: 1. O(d n k) 2. O(d nk) 3. O((d +n) k) 4. O(d (n + k))
Câu10: Sẽ thực hiện bao nhiêu phép so sánh để sắp xếp mảng arr = {1, 5, 3, 8, 2}
bằng phương pháp sắp xếp cơ số MSD? 1. 5 2. 7 3. 9 4. 0
Câu 11: Độ phức tạp thời gian trung bình của việc sắp xếp cơ số MSD là bao
nhiêu (w= số bit cần thiết để lưu trữ mỗi khóa)? 1. O(n + w) 2. O(nw) 3. O(n ) 2 4. O(n log n)
Trắc nghiệm: Quick Sort
Câu 1: Độ phức tạp trung bình của thuật toán sắp xếp nhanh (Quick Sort) là: a.O(nlogn) b.O(n) c.O(logn) d.O(n^2)
Câu 2: Ý tưởng phương pháp sắp xếp nhanh (Quick Sort) là:
a. Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khóa (dãy con trước khóa
gồm các phần tử nhỏ hơn khóa và dãy còn lại gồm các phần tử lớn hơn khóa).
b. 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.
c. 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…
d. 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âu 3: Phương pháp sắp xếp nhanh (Quick Sort) chính là phương pháp: a. Phân đoạn b. Vun đống c. Chèn d. Trộn
Câu 4: 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. Quick sort, Insert sort d. Quick sort, Merge sort
Câu 5: Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F(a, t, s); Begin B:= true; if t while b do begin
i:=i+1; while a[i]<=key do i:=i+1;
j:=j -1; while a[j]>=key do j:=j-1;
if i<="" br="">begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; end else b:=false; end;
tg:=a[t]; a[t]:=a[j]; a[j]:=tg; call F(a, t , j-1); call F(a, j+1 , s); end; End; a. Quick sort b. Insert sort c. Merge sort d. Bubble sort
Câu 6: Cho dãy số {3 1 6 0 5 4 8 2 9 7}. Áp dụng phương pháp sắp xếp nhanh (Quick
sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số
thu được sau lần lặp thứ hai là:
a. {0 (1 2) 3 (5 4 8 6 9 7)} b. {(0 1 2 3) 4 (5 6 7 8 9)} c. {(0 1 2) 3 (5 4 8 6 9 7)} d. {(3 1 6 0) 5 (4 8 2 9 7)}
Câu 7: Cho dãy số {3 1 6 0 5 4 8 2 9 7}. Áp dụng phương pháp sắp xếp nhanh (Quick
sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số
thu được sau lần lặp thứ ba là:
a. {(0) 1 (2 3) 4 (5 6) 7 (8 9)}
b. {(3) 1 (6 0) 5 (4 8) 2 (9 7)} c. {0 1 (2) 3 (5 4 8 6 9 7)}
d. {0 1 (2) 3 (5 4) 8 (6 9 7)}
Câu 8: Cho dãy số {3 1 6 0 5 4 8 2 9 7}. Áp dụng phương pháp sắp xếp nhanh (Quick
sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số
thu được sau lần lặp thứ bốn là:
a. {(0) 1 (2 3) 4 (5 6) 7 (8 9)} b. {0 1 (2) 3 (5 4) 8 (6 9 7)}
c. {(3) 1 (6 0) 5 (4 8) 2 (9 7)} d. {0 1 2 3 (5 4 8 6 9 7)}
Câu 9: 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: (0 1 2) 3 (5 4 8 6 9 7)
Bước 2: 0 (1 2) 3 (5 4 8 6 9 7)
Bước 3: 0 1 (2) 3 (5 4 8 6 9 7)
Bước 4: 0 1 2 3 (5 4 8 6 9 7)
Bước 5: 0 1 2 3 (4) 5 (8 6 9 7)
Bước 6: 0 1 2 3 4 5 (8 6 9 7)
Bước 7: 0 1 2 3 4 5 (7 6) 8 (9)
Bước 8: 0 1 2 3 4 5 (6) 7 8 (9)
Bước 9: 0 1 2 3 4 5 6 7 8 (9)
Bước 10: 0 1 2 3 4 5 6 7 8 9 a. Merge sort b. Quick sort c. Select sort d. Insert sort
Câu 10: Cho dãy số sau: 40 25 75 15 65 55 90 30 95 85. Áp dụng phương pháp sắp
xếp nhanh (Quick_Sort), sau lượt 1 dãy sẽ được sắp xếp lại như thế nào?
a. 15 25 40 75 30 55 65 90 85 95
b. 15 40 30 25 55 65 75 85 90 95
c. 40 25 55 15 30 65 75 90 85 95
d. (15 25 30) 40 (65 55 90 75 95 85)