25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật

 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
 }
 while (top >= 0) {
 output[len++] = pop() | 0x30;
 }
 // Kết quả: Điền các giá trị của output
}
Bài 3:
int N = 6;
int A[] = { 44,55,66,22,33,11 };
struct Node {
 int info;
 Node* next;
};
int* output = new int[N];
int len = 0;
void visit(Node* node) { output[len++] = node->info; }
Node* head = NULL;
Node* tail = NULL;
int main() {
// Kẻ bảng mô tả trạng thái của A[i] và danh sách liên kết
 Node* node;
 for (int i = 0; i < N; i++) {
 node = new Node(); node->info = A[i];
 if (A[i] % 2 == 0) { // số chẵn
 node->next = NULL;
 if (tail == NULL) {
 head = tail = node;
 }
 else {
 tail->next = node;
 tail = node;
 }
 }
 else { // số lẻ
 node->next = head;
 if (head == NULL) tail = node;
 head = node;
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
 }
 }
 node = head;
 while (node != NULL) { visit(node); node = node->next; }
 // Điền các giá trị của output
}
Bài 4:
int N = 6;
int A[] = { 44,55,22,11,66,33 };
int count = 0;
int* output = new int[N];
void add(int v) {
 int k = count++;
 output[k] = v;
 while (k != 0) {
 int i = (k - 1) / 2;
 if (output[i] >= v) break;
 output[k] = output[i];
 output[i] = v;
 k = i;
 }
}
int main() {
 // Kẻ bảng mô tả trạng thái của A[i] và output
 for (int i = 0; i < N; i++) {
 add(A[i]);
 }
 // Kết quả: Điền các giá trị của output
}
 ----------HẾT----------
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
 ĐÁP ÁN
Phần: Trắc nghiệm
 1. D 2. B 3. C 4. A 5. D 6. D 7. A 8. D
 9. C 10. D 11. D 12. A 13. D 14. C 15. C
Phần: Đọc hiểu
Câu 1:
bubble_sort:
input: 44,55,11,77,88,22,33,66
output: 11,44,55,22,77,88,33,66
Câu 2:
dec2bin:
input: 140
output: 1,0,0,0,1,1,0,0
Câu 3:
linked_list:
input: 44,55,66,22,33,11
output: 11,33,55,44,66,22
Câu 4:
priority_queue_max:
input: 44,55,22,11,66,33
output: 66,55,33,11,44,22
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
 ĐỀ SỐ 5
 ĐẠI HỌC BÁCH KHOA ĐỀ THI CUỐI HỌC KỲ 2
 TRƯỜNG ĐIỆN – ĐIỆN TỬ MÔN: CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
 Mã đề: 760 Thời gian: 60 phút (không kể thời gian giao đề
Phần: Trắc nghiệm
Câu 1. Biến middle được tính bao nhiêu lần khi gọi Search()?
int A[] = { 11, 22, 33, 44, 55, 66, 77, 88, 99 };
int x = 66;
int Search() {
 int first = 0, last = 8;
 while (last >= first) {
 int middle = (first + last) / 2;
 int comp = A[middle] - x;
 if (comp == 0) return middle;
 if (comp < 0) {
 first = middle + 1;
 } else {
 last = middle - 1;
 }
 }
 return -1;
}
A. 3
B. 4
C. 1
D. 2
Câu 2. Cho mảng sau:
int A[] = { 11, 66, 22, 33, 44, 55 };
Cho biết trạng thái của mảng A sau khi thực hiện vun đống cây ban đầu?
A. 66, 44, 55, 33, 11, 22
B. 66, 33, 55, 11, 44, 22
C. 55, 66, 22, 11, 33, 44
D. 66, 11, 55, 22, 33, 44
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
Câu 3. Đồ thị được lưu trữ trong ma trận lân cận kề dưới đây:
 A B C D E F
 A 0 1 1 0 0 0
 B 1 0 0 0 1 0
 C 0 0 0 0 0 1
 D 0 0 1 0 1 0
 E 0 1 0 1 0 0
 F 1 0 0 1 0 0
Cho biết thứ tự các nút khi duyệt theo chiều sâu bắt đầu từ nút B?
A. BACFDE
B. AEDEFB
C. BCAFDE
D. BDAFCE
Câu 4. Cho biết tác dụng của hàm Search?
int Search(int x, int A[], int N) {
 for (int i = 0; i < N; i++) {
 if (x == A[i]) return i;
 }
 return -1;
}
A. Tìm tất cả các vị trí có giá trị khác x trong A
B. Tìm tất cả các vị trí có giá trị bằng x trong A
C. Tìm vị trí cuối cùng của x trong A
D. Tìm vị trí đầu tiên của x trong A
Câu 5. Cho mảng sau:
int A[] = { 55, 11, 66, 22, 99, 88, 33, 44, 77 };
Cho biết trạng thái của mảng A sau khi thực hiện phân đoạn (Partion) lần đầu với phần tử 
chốt là A[0] ?
A. 44, 33, 22, 11, 55, 88, 99, 66, 77
B. 66, 99, 88, 77, 55, 44, 33, 22, 11
C. 33, 11, 44, 22, 55, 88, 99, 66, 77
D. 33, 11, 44, 22, 55, 99, 88, 66, 77
Câu 6. Cho mảng sau:
int A[] = { 55, 11, 66, 44, 99, 88, 33, 22, 77 };
Cho biết trạng thái của mảng A sau khi thực hiện 2 vòng lặp đầu tiên của thuật toán sắp xếp 
lựa chọn (Selection Sort)?
A. 11,22,33,44,99,88,66,55,77
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
B. 11,55,22,66,44,99,88,33,77
C. 11,22,66,44,99,88,33,55,77
D. 11,55,66,44,99,88,33,22,77
Câu 7. Cây nhị phân được lưu trữ bằng mảng A sau:
int A[] = { 55, 66, 11, 33, 44, 22 };
Cho biết thứ tự các giá trị được thăm khi duyệt cây theo thứ tự giữa (inOrder)?
A. 33, 44, 66, 22, 11, 55
B. 55, 66, 33, 44, 11, 22
C. 66, 55, 22, 33, 44, 11
D. 33, 66, 44, 55, 22, 11
Câu 8. Cho biết độ phức tạp của đoạn code sau:
for (int i = 1; i < N; i *= 2) { }
A. O(log N)
B. O(Nlog N)
C. O(N)
D. O(N2)
Câu 9. Cho thuật toán sau:
int Fn(int t) {
 return t < 3 ? 1 : Fn(t - 1) + Fn(t - 2);
}
Tính Fn(8) ?
A. 34
B. 21
C. 55
D. 13
Câu 10. Đồ thị được lưu trữ trong ma trận lân cận kề dưới đây:
 A B C D E F
 A 0 2 0 3 3 0
 B 2 0 4 2 2 0
 C 0 4 0 0 1 4
 D 3 2 0 0 0 3
 E 3 2 1 0 0 0
 F 0 0 4 3 0 0
Cho biết thứ tự các cặp đỉnh của cây khung nhỏ nhất được xây dựng bằng thuật toán 
Kruskal?
A. CE, AB, BD, BE, AD
B. CE, AB, BD, BE, BC
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
C. CE, AB, BD, BE, DF
D. CE, AB, BD, BE, AE
Câu 11. Đưa lần lượt các phần tử của mảng A vào cây AVL:
int [] = {55,66,11,44,77,99,88,22,33};
Cho biết thứ tự các giá trị được thăm khi duyệt cây theo thứ tự trước (preOrder))?
A. 33, 22, 44, 11, 88, 99, 77, 66, 55
B. 11, 33, 44, 22, 66, 88, 99, 77, 55
C. 55, 22, 11, 44, 33, 77, 66, 99, 88
D. 55, 11, 44, 22, 33, 66, 77, 99, 88
Câu 12. Dùng cấu trúc dữ liệu nào là tối ưu để kiểm tra các cặp đóng mở ngoặc trong biểu 
thức?
A. Hàng đợi
B. Đồ thị
C. Ngăn xếp
D. Cây
Câu 13. Dùng cấu trúc dữ liệu nào là tối ưu để lưu trữ cơ cấu tổ chức các đơn vị trong 
ĐHBK Hà Nội?
A. Cây
B. Ngăn xếp
C. Đồ thị
D. Hàng đợi
Câu 14. Đưa lần lượt các phần tử của mảng A vào cây nhị phân tìm kiếm (BST):
int [] = {55,66,11,44,77,99,88,22,33};
Cho biết thứ tự các giá trị được thăm khi duyệt cây theo thứ tự sau (postOrder)?
A. 55,22,11,44,33,77,66,99,88
B. 55,11,44,22,33,66,77,99,88
C. 33,22,44,11,88,99,77,66,55
D. 11,33,44,22,66,88,99,77,55
Câu 15. Đồ thị được lưu trữ trong ma trận lân cận kề dưới đây:
 A B C D E F
 A 0 0 0 0 0 1
 B 0 0 1 0 0 0
 C 0 0 0 0 1 0
 D 1 1 0 0 0 0
 E 1 0 0 1 0 0
 F 0 1 0 1 0 0
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
Cho biết thứ tự các nút khi duyệt theo chiều rộng bắt đầu từ nút E ?
A. EDAFCB
B. EAFBCD
C. BEDAFC
D. EADFBC
Phần: Đọc hiểu
Bài 1:
int N = 8;
int A[] = { 44,33,88,55,66,22,11,77 };
int step = 1;
int* output = A;
int main() {
 // Kẻ bảng mô tả trạng thái của i và A
 for (int i = 0; i < step; i++) {
 for (int k = N - 1; k > i; k--) {
 bool c = false;
 if (A[k] < A[k - 1]) {
 c = true;
 swap(A[k], A[k - 1]);
 }
 }
 if (c == false) break;
 }
 // Kết quả: Điền các giá trị của output
}
Bài 2:
int N = 8;
int x = 150;
char* output = new char[N];
int len = 0;
// stack
int S[10];
int top = -1;
void push(int i) { S[++top] = i; }
int pop() { return S[top--]; }
int main() {
 // Kẻ bảng mô tả trạng thái của x và S
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
for (int i = 0; i < N; i++) {
 push(x % 2);
 x /= 2;
 }
 while (top >= 0) {
 output[len++] = pop() | 0x30;
 }
 // Kết quả: Điền các giá trị của output
}
Bài 3:
int N = 6;
int A[] = { 44,66,11,22,33,55 };
struct Node {
 int info;
 Node* next;
};
int* output = new int[N];
int len = 0;
void visit(Node* node) { output[len++] = node->info; }
Node* head = NULL;
Node* tail = NULL;
int main() {
 // Kẻ bảng mô tả trạng thái của A[i] và danh sách liên kết
 Node* node;
 for (int i = 0; i < N; 1++) {
node = new Node(); node->info = A[i];
 if (A[i] % 2 == 0) { // số chẵn
 node->next = NULL;
 if (tail == NULL) {
 head = tail = node;
 }
 else {
 tail->next = node;
 tail = node;
 }
 }
 else { // số lẻ
 DeThiHay.net 25 Đề thi và Đáp án môn Cấu trúc dữ liệu và Giải thuật - DeThiHay.net
 node->next = head;
 if (head == NULL) tail = node;
 head = node;
 }
 }
 node = head;
 while (node != NULL) { visit(node); node = node->next; }
 // Điền các giá trị của output
}
Bài 4:
int N = 6;
int A[] = { 44,55,11,22,66,33 };
int count = 0;
int* output = new int[N];
void add(int v) {
 int k = count++;
 output[k] = v;
 while (k != 0) {
 int i = (k - 1) / 2;
 if (output[i] >= v) break;
 output[k] = output[i];
 output[i] = v;
 k = i;
 }
}
int main() {
 // Kẻ bảng mô tả trạng thái của A[i] và output
 for (int i = 0; i < N; i++) {
 add(A[i]);
 }
 // Kết quả: Điền các giá trị của output
}
 ----------HẾT----------
 DeThiHay.net