Shell Sort có ý tưởng gần giống với giải thuật sắp xếp nào dưới đây?

Câu 1
Shell Sort có ý tưởng gần giống với giải thuật sắp xếp nào dưới đây? a. Insertion Sort b. Quick Sort c. Bubble Sort d. Interchange Sort
Đáp án: a. Insertion Sort Câu 2
Bảng băm kích thước là 9, h(k) = k % 9.
Thêm lần lượt các giá trị: 5, 28, 19, 15, 20, 33, 12, 17, 10. Dùng Separate Chaining.
Kích thước tối đa và tối thiểu của các danh sách trong bảng băm là: a. 3, 3 b. 3, 0 c. 4, 3 d. 4, 0 Đáp án: b. 3, 0 Câu 3
Khi thực hiện Quick Sort, cách chọn phần tử chốt (pivot) hiệu quả nhất là:
a. Chọn giá trị một phần tử bất kì
b. Chọn giá trị trung vị của 3 phần tử đầu, giữa và cuối
c. Chọn giá trị phần tử cuối cùng
d. Chọn giá trị phần tử ở chính giữa
e. Chọn giá trị phần tử đầu tiên
Đáp án: b. Chọn trung vị của 3 phần tử Câu 4
Cho dãy số: 15 3 5 17 2 8 9 20
Sau lượt Bubble Sort đầu tiên ta có: 2 15 3 5 17 8 9 20
Kết quả sau lượt thứ hai là: a. 2 3 15 5 8 17 9 20 b. 2 3 15 17 5 8 9 20 c. 2 15 3 5 17 8 9 20 d. 2 15 3 5 17 8 9 20 Đáp án: a và b
(Lý do: tùy phiên bản Bubble Sort.) Câu 5
Thuật toán tìm kiếm hiệu quả nhất trên dãy đã sắp xếp: a. Depth-First Search b. Binary Search c. Breadth-First Search d. Linear Search
Đáp án: b. Binary Search Câu 6
Quá trình sắp xếp trong hình thuộc thuật toán: a. Bubble Sort b. Selection Sort c. Merge Sort d. Quick Sort
Đáp án: c. Merge Sort Câu 7
Thuật toán Interpolation Search được cải tiến dựa trên: a. Linear Search b. Jump Search c. Binary Search d. KMP
Đáp án: c. Binary Search Câu 8
Interpolation Search hoạt động hiệu quả hơn Binary Search khi:
a. Giá trị các phần tử được sắp xếp theo thứ tự
b. Giá trị các phần tử phân phối đều nhưng không sắp xếp
c. Luôn hiệu quả hơn Binary Search trong mọi trường hợp
d. Giá trị các phần tử phân phối đều và được sắp xếp theo thứ tự Đáp án: d Câu 9
Shaker Sort (Cocktail Sort) có ý tưởng gần giống: a. Interchange Sort b. Quick Sort c. Bubble Sort d. Merge Sort
Đáp án: c. Bubble Sort Câu 10 Quick Sort. Cho dãy: 15 3 5 17 2 8 9 20 Pivot = 17
Kết quả phân đoạn đầu tiên là: a. {2 3 5 8 9 15 17} và {20} b. {15 3 5 17} và {2 8 9 20} c. {2 3 5 8} và {9 15 17 20} d. {15 3 5 9 2 8} và {17 20} Đáp án: c và d Câu 11
Độ phức tạp thời gian trong trường hợp xấu nhất của Linear Search: a. O(n) b. O(n²) c. O(1) d. O(log n) Đáp án: a. O(n) Câu 12
Độ phức tạp thời gian tốt nhất của Binary Search: a. O(log n) b. O(n) c. O(n²) d. O(1) Đáp án: d. O(1) Câu 13
Bảng băm kích thước 7, Linear Probing.
Thêm: 15, 11, 25, 16, 9, 8, 12.
Vị trí lưu phần tử 12 là: a. 6 b. 1 c. 5 d. 0 Đáp án: d. 0 Câu 14
Công thức tính vị trí trong Interpolation Search: a. mid = (right - left) / 2
b. mid = left + (right - left) / 2 c. mid = (left + right) / 2
d. mid = left + (X - a[left]) * (right - left) / (a[right] - a[left]) Đáp án: d Câu 15
Quá trình sắp xếp như mô tả: 51 11 56 83 20 26 33 11 51 56 83 20 26 33 11 20 56 83 51 26 33 11 20 26 83 51 56 33 11 20 26 33 51 56 83 11 20 26 33 51 56 83 Thuật toán nào? a. Quick Sort b. Selection Sort c. Insertion Sort d. Merge Sort
Đáp án: b. Selection Sort Câu 16
Trong các thuật toán dưới đây, thuật toán nào có độ phức tạp thời gian trong trường hợp tốt nhất là O(n)? a. Merge Sort b. Insertion Sort c. Quick Sort d. Bubble Sort
Đáp án: b. Insertion Sort Câu 17
Số phép so sánh cần thực hiện khi sắp xếp dãy a = {1, 5, 3, 8, 2} bằng Counting Sort? a. 9 b. 0 c. 5 d. 7 Đáp án: b. 0
(Counting Sort không thực hiện so sánh giữa các phần tử.) Câu 18
Thuật toán sắp xếp nào tạo ra quá trình sắp xếp sau: 83 5 8 12 65 72 71 5 83 8 12 65 72 71 5 8 83 12 65 72 71 5 8 12 83 65 72 71 5 8 12 65 83 72 71 5 8 12 65 72 83 71 5 8 12 65 71 72 83 a. Insertion Sort b. Merge Sort c. Selection Sort d. Quick Sort
Đáp án: a. Insertion Sort Câu 19
Thuật toán Quick Sort dựa trên kỹ thuật nào? a. Quay lui (Backtracking)
b. Chia để trị (Divide and Conquer) c. Tham lam (Greedy) d. Vét cạn (Brute-force)
Đáp án: b. Chia để trị (Divide and Conquer) Câu 20
Số phép so sánh tối đa khi thực hiện Linear Search trên dãy có kích thước 32 là bao nhiêu? Đáp án: 32 Câu 21
Sắp xếp dãy a = {5, 1, 4, 2, 8, 0, 2} bằng Shaker Sort.
Kết quả sau lượt sắp xếp đầu tiên: a. 0 1 4 2 5 2 8 b. 1 5 4 2 2 0 8 c. 1 5 4 2 8 0 2 d. 1 4 2 5 0 2 8
Đáp án: a. 0 1 4 2 5 2 8 Câu 22
Dãy ban đầu: {35, 33, 42, 10, 14, 19, 27, 44}
gap = 4 → các đoạn con được sắp xếp. Sau đó giảm gap = 2.
Kết quả sắp xếp với gap = 2 là: a. 19 10 33 44 14 27 35 42 b. 14 10 27 19 35 33 42 44 c. 14 27 35 42 19 10 33 44 d. 14 19 27 10 35 33 42 44
Đáp án: b. 14 10 27 19 35 33 42 44 Câu 23
Số phép so sánh tối đa khi thực hiện Binary Search trên dãy có kích thước 32 là: Đáp án: 5 (Vì log₂(32) = 5.) Câu 24 Cho dãy: 15 3 5 17 2 8 9 20 Interchange Sort.
Sau lượt 1: 2 15 5 17 3 8 9 20
Hỏi kết quả sau lượt thứ hai: a. 2 3 15 17 5 8 9 20 b. 2 3 15 5 17 8 9 20 c. 2 3 5 17 3 8 9 20 15 d. 2 3 5 17 15 8 9 20
Đáp án: a. 2 3 15 17 5 8 9 20 Câu 25
Thuật toán nào dùng để tìm kiếm mẫu trong chuỗi (Pattern Searching)? a. Knuth–Morris–Pratt b. Naïve algorithm c. Boyer–Moore d. Brute Force e. Rabin–Karp
f. Tất cả đáp án đều đúng
Đáp án: f. Tất cả đáp án đều đúng Câu 26
Thuật toán Binary Search chỉ hoạt động trên mảng: a. Số nguyên b. Ngẫu nhiên
c. Được sắp xếp theo thứ tự d. Số thực
Đáp án: c. Được sắp xếp theo thứ tự Câu 27
Thuật toán sắp xếp nào không cần thực hiện phép so sánh?
a. Radix Sort, Bucket Sort, Quick Sort
b. Bubble Sort, Counting Sort, Quick Sort
c. Selection Sort, Radix Sort, Bucket Sort
d. Counting Sort, Radix Sort, Bucket Sort
Đáp án: d. Counting Sort, Radix Sort, Bucket Sort Câu 28
Thuật toán tìm kiếm nào có thể không cần so sánh giá trị phần tử? a. Linear Search b. Binary Search
c. Tất cả thuật toán tìm kiếm đều phải so sánh d. Hashing Đáp án: d. Hashing Câu 29
Thuật toán Jump Search dựa trên ý tưởng giống thuật toán: a. Linear Search b. Hashing c. Binary Search d. KMP
Đáp án: c. Binary Search Câu 30
Trong Jump Search, sau khi tìm được vị trí k*m là nơi phần tử lớn hơn khóa, bước tiếp theo là:
a. Tìm kiếm nhị phân từ vị trí (km) về đầu dãy
b. Tìm kiếm tuần tự từ vị trí km về cuối dãy
c. Tìm kiếm tuần tự từ vị trí (k-1)m đến (km)
d. Tìm kiếm nhị phân từ vị trí (k*m) về cuối dãy
Đáp án: c. Tìm kiếm tuần tự từ (k-1)m đến (km)