WorksheetsCâu hỏi về Thuật toán và Cấu trúc Dữ liệu
Total questions: 40
Worksheet time: 20mins
Đoạn mã sau sử dụng thuật toán sắp xếp nào?
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
Insertion Sort
Merge Sort
Bubble Sort
Selection Sort
Thuật toán nào sau đây có độ phức tạp trung bình tốt nhất cho dữ liệu ngẫu nhiên?
Merge Sort
Quick Sort
Heap Sort
Selection Sort
Với dữ liệu gần như đã được sắp xếp, thuật toán nào có hiệu năng cao nhất?
Quick Sort
Bubble Sort
Insertion Sort
Heap Sort
Với một hàng đợi ưu tiên dạng max-heap chứa các phần tử [50, 40, 30, 20, 10], sau khi thêm phần tử 60 vào, đỉnh heap sẽ là?
50
60
40
30
Dữ liệu đầu vào: [10, 20, 15, 30, 40]. Kết quả tạo heap là gì (dạng max-heap)?
[40, 30, 15, 10, 20]
[40, 20, 30, 10, 15]
[40, 30, 20, 10, 15]
[30, 20, 15, 10, 40]
Kỹ thuật xử lý xung đột trong bảng băm không bao gồm phương pháp nào sau đây?
Separate chaining
Linear probing
Binary search
Quadratic probing
Nếu bảng băm có kích thước 10, hàm băm là h(k) = k % 10. Khi chèn các khóa 7, 17, 27 thì số phần tử ở vị trí chỉ mục 7 là?
0
1
2
3
Sau khi chèn lần lượt các phần tử: 10, 20, 30 vào cây AVL, cây sẽ cân bằng lại bằng phép quay nào?
Không cần quay
Quay trái đơn
Quay phải đơn
Quay kép trái-phải
Chiều cao tối đa của một cây AVL với 10 nút là:
3
4
5
6
Với cây BST sau: 50 / \ 30 70 / \ / 20 40 60 Thứ tự duyệt hậu tự là?
20 40 30 60 70 50
30 20 40 70 60 50
20 40 30 60 70 50
20 30 40 60 70 50
Nếu xóa node 50, nút thay thế thích hợp trong cây BST là?
Node có giá trị nhỏ nhất bên phải
Node có giá trị lớn nhất bên trái
Node có giá trị nhỏ nhất trong cây
Node có giá trị lớn nhất trong cây
Một cây nhị phân đầy đủ (full binary tree) có 15 node. Có bao nhiêu node lá?
8
7
15
10
Với cây sau: A / \ B C / \ D E Thứ tự duyệt theo hậu tự là?
D E B C A
A B C D E
D E C B A
D E C A B
Một cây nhị phân đầy đủ (full binary tree) có đúng n nút lá thì tổng số nút trong cây là?
2n
2n - 1
n
n + 1
Khi nào thuật toán Merge Sort có thể kém hiệu quả hơn Quick Sort trên dữ liệu ngẫu nhiên?
Khi sử dụng thêm bộ nhớ tạm trong merge
Khi dữ liệu chứa các phần tử giống nhau
Khi độ sâu đệ quy quá lớn
Khi danh sách đã gần sắp xếp
Đoạn mã sau thực hiện thao tác gì? int mid = (l + r) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r);
Sắp xếp chèn
Sắp xếp chọn
Merge Sort
Quick Sort
Đoạn mã dưới đây mô tả loại sắp xếp nào? int i, j, min_idx; for (i = 0; i < n-1; i++) { min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(&arr[min_idx], &arr[i]); }
Selection Sort
Insertion Sort
Bubble Sort
Shell Sort
Trong Quick Sort, nếu bạn luôn chọn phần tử cuối cùng làm pivot và dãy đầu vào đã được sắp xếp tăng dần, độ phức tạp là:
O(n log n)
O(log n)
O(n)
O(n²)
Cho heap dạng max-heap: [90, 80, 70, 50, 60, 30, 40]. Sau khi xóa phần tử gốc, phần tử nào sẽ là gốc tiếp theo?
80
70
60
40
Trong hàng đợi ưu tiên sử dụng heap, thao tác chèn phần tử mới có độ phức tạp:
O(1)
O(log n)
O(n)
O(n log n)
Nếu một hàng đợi ưu tiên được cài đặt bằng cây nhị phân không cân bằng, độ phức tạp tồi nhất của thao tác extract_max() là:
O(1)
O(log n)
O(n)
O(n²)
Giả sử bạn sử dụng priority queue để mô phỏng hệ thống xử lý bệnh nhân khẩn cấp (người có mức ưu tiên cao hơn được xử lý trước). Cấu trúc nào phù hợp nhất?
Stack
Queue
Max-Heap
Hash Table
Với phương pháp linear probing trong bảng băm, điều gì xảy ra khi có quá nhiều phần tử?
Truy cập sẽ nhanh hơn
Tải trọng giảm
Hiện tượng clustering xảy ra
Sử dụng ít bộ nhớ hơn
Trong một bảng băm, tải trọng (load factor) là gì?
Tổng số phần tử chia cho kích thước bảng
Kích thước bảng chia cho tổng số phần tử
Kích thước bảng
Số phần tử có thể chứa tối đa
Nếu một bảng băm có tải trọng > 1, điều gì có thể xảy ra?
Tìm kiếm có thể chậm hơn
Không có ảnh hưởng
Giảm xung đột
Giảm tốc độ chèn
Cây AVL là gì?
Cây nhị phân mà tất cả các node có tối đa 2 con
Cây nhị phân tìm kiếm có thể không cân bằng
Cây nhị phân tìm kiếm với độ lệch chiều cao không quá 1 tại mọi node
Cây nhị phân có độ sâu bằng nhau ở tất cả các lá
Sau khi chèn 50, 40, 60, 30 vào cây AVL, phép quay nào sẽ xảy ra?
Không cần quay
Quay phải đơn
Quay trái đơn
Quay phải-trái kép
Đoạn mã dưới đây đại diện cho thao tác gì trong cây AVL? if (balance > 1 && key < node->left->key) return rightRotate(node);
Trường hợp Left Right
Trường hợp Right Left
Trường hợp Left Left
Trường hợp Right Right
Sau khi xóa một node trong cây AVL, có thể cần thực hiện:
Chỉ quay phải
Chỉ quay trái
Một hoặc nhiều phép quay để cân bằng lại
Không bao giờ cần quay
Cây AVL với 15 nút có chiều cao nhỏ nhất là:
3
4
5
6
Khi tìm kiếm trong BST, nếu cây bị mất cân bằng nghiêm trọng (toàn bộ node về một phía), độ phức tạp là:
O(log n)
O(1)
O(n)
O(n log n)
Đoạn mã dưới đây làm gì? if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { // xử lý node cần xóa }
Tìm kiếm node trong AVL
Tìm kiếm node trong heap
Xóa node trong BST
Xóa node trong cây đỏ-đen
Sau khi chèn 10, 5, 15, 3, 7, 12, 18 vào cây BST, kết quả duyệt theo thứ tự giữa (in-order) là:
3 5 7 10 12 15 18
10 5 3 7 15 12 18
3 7 5 10 12 15 18
3 5 10 7 12 15 18
BST có 7 node và chiều cao bằng 6. Câu nào sau đây đúng?
Cây là cân bằng
Cây có thể là AVL
Cây bị lệch hoàn toàn
Cây đầy đủ
Một cây nhị phân có 5 mức. Số node tối đa mà cây có thể có là:
16
31
32
63
Với cây nhị phân đầy đủ (full binary tree), nếu có 20 node lá thì số node không lá là:
10
15
19
20
Duyệt cây theo thứ tự level-order (từng mức từ trái sang phải) có thể được thực hiện bằng:
Stack
Queue
Recursion
DFS
Với cây sau, thứ tự duyệt tiền tự là?
A B D E C
D E B A C
A C B D E
D B E C A
Cây nhị phân có n node. Số cạnh trong cây là:
n - 1
n
n + 1
n / 2
Câu nào sau đây đúng với cây nhị phân hoàn chỉnh (complete binary tree)?
Tất cả node đều có 2 con
Node chỉ có bên trái hoặc bên phải
Tất cả các mức (trừ mức cuối) được lấp đầy, và node ở mức cuối cùng được xếp từ trái sang
Cây chỉ có node lá
