Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án)

Nội dung text: Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án)

1. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn Câu 8. Đồ 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 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 Câu 9. 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 vị trí đầu tiên của x trong A B. Tìm tất cả các vị trí có giá trị bằng x trong A C. Tìm tất cả các vị trí có giá trị khác x trong A D. Tìm vị trí cuối cùng của x trong A 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 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 ? A. B A C F D E B. B D A F C E C. A E D E F B D. B C A F D E DeThi.edu.vn
2. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn Câu 11. 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. Ngăn xếp B. Đồ thị C. Cây D. Hàng đợi Câu 12. Đồ 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, DF B. CE, AB, BD, BE, BC C. CE, AB, BD, BE, AE D. CE, AB, BD, BE, AD Câu 13. 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. 13 B. 34 C. 55 D. 21 Câu 14. 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 15. 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? DeThi.edu.vn
3. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn A. Cây B. Ngăn xếp C. Đồ thị D. Hàng đợi Phần: Đọc Hiểu Bài 1. int N = 8; int A[] = { 44,77,66,11,88,55,33,22 }; 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 = 133; 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 for (int i = 0; i < N; i++) { DeThi.edu.vn
4. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn 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,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; DeThi.edu.vn
5. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn 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,66,22,33,11,55 }; 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---------- DeThi.edu.vn
6. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn ĐÁP ÁN Phần: Trắc nghiệm 1. D 2. D 3. D 4. C 5. A 6. A 7. C 8. D 9. A 10. A 11. A 12. A 13. D 14. A 15. A Phần: Đọc Hiểu Câu 1: input: 44,77,66,11,88,55,33,22 output: 11,44,77,66,22,88,55,33 Câu 2: dec2bin: input: 133 output: 1,0,0,0,0,1,0,1 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,66,22,33,11,55 output: 66,44,55,33,11,22 DeThi.edu.vn
7. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn ĐỀ SỐ 4 ĐẠ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ã đề: 477 Thời gian: 60 phút (không kể thời gian giao đề Phần: Trắc nghiệm Câu 1. Cây nhị phân được lưu trữ bằng mảng A sau: int [] = {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. 66, 55, 22, 33, 44, 11 B. 33, 44, 66, 22, 11, 55 C. 55, 66, 33, 44, 11, 22 D. 33, 66, 44, 55, 22, 11 Câu 2. 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. Ngăn xếp C. Cây D. Đồ thị 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 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 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. BEDAFC C. EADFBC D. EAFBCD 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; } DeThi.edu.vn
8. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn return -1; } A. Tìm vị trí đầu tiên của x trong A B. Tìm tất cả các vị trí có giá trị khác x trong A C. Tìm vị trí cuối cùng của x trong A D. Tìm tất cả các vị trí có giá trị bằng x trong A Câu 5. Đồ 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. AEDEFB B. BDAFCE C. BCAFDE D. BACFDE Câu 6. 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. 66,99,88,77,55,44,33,22,11 B. 44,33,22,11,55,88,99,66,77 C. 33,11,44,22,55,99,88,66,77 D. 33,11,44,22,55,88,99,66,77 Câu 7. Đưa lần lượt các phần tử của mảng A vào cây AVL : int A[]={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. 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 8. Cho biết độ phức tạp của đoạn code sau: for (int i = 1; i < N; i *= 2) { } A. O(Nlog N) DeThi.edu.vn
9. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn B. O(N2) C. O(N) D. (log ) Câu 9. Đồ 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 C. CE, AB, BD, BE, DF D. CE, AB, BD, BE, AE Câu 10. 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 B. 11,55,66,44,99,88,33,22,77 C. 11,55,22,66,44,99,88,33,77 D. 11,22,66,44,99,88,33,55,77 Câu 11. 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. 13 B. 34 C. 55 D. 21 Câu 12. 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; DeThi.edu.vn
10. Bộ 25 Đề thi Cấu trúc dữ liệu & giải thuật (Có đáp án) - DeThi.edu.vn 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 13. Cho mảng sau: int [] = {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,11,55,22,33,44 B. 55, 66, 22, 11, 33, 44 C. 66, 33, 55, 11, 44, 22 D. 66, 44, 55, 33, 11, 22 Câu 14. 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. Ngăn xếp B. Đồ thị C. Cây D. Hàng đợi Câu 15. Đư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,11,44,22,33,66,77,99,88 B. 11, 33, 44, 22, 66, 88, 99, 77, 55 DeThi.edu.vn