Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án)

Nội dung text: Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án)

1. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn ĐỀ SỐ 2 TRƯỜNG ĐH SƯ PHẠM TP.HCM ĐỀ THI KẾT THÚC HỌC PHẦN KHOA CÔNG NGHỆ THÔNG TIN Môn: Phân tích & thiết kế giải thuật Thời gian: 90 phút (không kể thời gian phát đề) Câu 1 (4đ): Cho hàm sau int maxPairwiseProduct (const vector & arr) { int maxProduct = 0; int n = arr.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { maxProduct = max(maxProduct, arr[i] * arr[j]); } } return maxProduct; } a. Tính độ phức tạp T (n) của hàm maxPairwiseProduct (1.0) b. Xác định BigO (chỉ rõ C và n0) của hàm maxPairwiseProduct (1.0) c. Cải tiến hàm maxPairwiseProduct sao cho có độ phức tạp nhỏ hơn độ phức tạp của hàm gốc (1.0) d. Tính độ phức tạp T(n) và O(n) (chỉ rõ C và n0) của hàm đã cải tiến. (1.0) Câu 2 (6đ): Cho mảng A gồm n (n > 1) số nguyên. Tìm mảng con B gồm các phần tử liền kề trong A sao cho tổng các phần tử của B là nhỏ nhất. Chọn một trong hai tiếp cận quy hoạch động hoặc quay lui để giải vấn đề trên. Với tiếp cận đã chọn, thực hiện a. Trình bày giải thuật chi tiết (bao gồm các biến, công thức hồi quy nếu cần) (2.0) b. Viết toàn bộ chương trình bao gồm các hàm - Hàm tìm B (2.5) - Hàm main của chương trình thực hiện yêu cầu của đề bài, trong đó bao gồm các chức năng nhập và xuất kết quả ra màn hình. (1,5) ----------HẾT---------- DeThi.edu.vn
2. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn ĐÁP ÁN Câu 1 (4 điểm) a. Tính độ phức tạp (푛) Hàm sử dụng hai vòng lặp lồng nhau: • Vòng lặp ngoài chạy từ 푖 = 0 đển 푛 ―1. • Vòng lặp trong chạy từ 푗 = 푖 +1 đến 푛 ―1. Số lần thực hiện phép tính maxProduct là: 푛(푛 1) 1 1 2 (푛) = (푛 ―1) + (푛 ―2) + + 1 + 0 = 2 = 2푛 ― 2푛 b. Xác định BigO (chỉ rõ và 푛0 ) 1 1 Từ 2 , ta thấy bậc cao nhất là 2. (푛) = 2푛 ― 2푛 푛 • Chọn = 1. 2 • Ta cần tìm 푛0 sao cho (푛) ≤ ⋅ 푛 với mọi 푛 ≥ 푛0. 1 1 1 1 • 2 2 2 (luôn đúng với mọi ). 2푛 ― 2푛 ≤ 푛 ⇔ ― 2푛 ― 2푛 ≤ 0 푛 ≥ 1 2 • Vậy: (푛 ) với = 1,푛0 = 1. c. Cải tiến hàm maxPairwiseProduct int maxPairwiseProductOptimized(const vector & arr) { int n = arr.size(); if (n < 2) return 0; int max1 = -1, max2 = -1; for (int x : arr) { if (x > max1) { max2 = max1; max1 = x; } else if (x > max2) { max2 = x; } } return max1 * max2; } d. Độ phức tạp hàm cải tiến - T(n): Hàm chỉ sử dụng một vòng lặp duy nhất chạy qua n phần tử. Vậy (푛) = 푛. • Bigo: (푛). • Chọn = 1,푛0 = 1. • Ta có 푛 ≤ 1 ⋅ 푛 với mọi 푛 ≥ 1. Câu 2 (6 điểm) DeThi.edu.vn
3. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn a. Giải thuật chi tiết Sử dụng tư tưởng: Tổng nhỏ nhất kết thúc tại chỉ số 푖 sẽ bằng chính nó hoặc bằng chính nó cộng với tổng nhỏ nhất kết thúc tại 푖 ―1. Biến: - min_ending_here: Tổng mảng con nhỏ nhất kết thúc tại vị trí hiện tại. - min_so_far: Tổng mảng con nhỏ nhất tìm thấy xuyên suốt mảng. - start, end, s: Các biến đánh dấu vị trí để trích xuất mảng con B . - Công thức hồi quy: (푖) = min( [푖], [푖] + (푖 ―1)) b. Chương trình hoàn chỉnh #include #include #include using namespace std; // Hàm tìm mảng con B có tổng nhỏ nhất vector findMinSubarray(const vector & A) { int n = A.size(); long long min_so_far = LLONG_MAX; long long min_ending_here = 0; int start = 0, end = 0, s = 0; for (int i = 0; i < n; i++) { min_ending_here += A[i]; if (min_so_far > min_ending_here) { min_so_far = min_ending_here; start = s; end = i; } if (min_ending_here > 0) { min_ending_here = 0; s = i + 1; } } // Trích xuất mảng con B từ vị trí start đến end DeThi.edu.vn
4. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn vector B; for (int i = start; i <= end; i++) { B.push_back(A[i]); } return B; } int main() { int n; cout 1): "; cin >> n; if (n <= 1) { cout << "n phai lon hon 1!" << endl; return 0; } vector A(n); cout << "Nhap cac phan tu cua mang A: "; for (int i = 0; i < n; i++) { cin >> A[i]; } vector B = findMinSubarray(A); cout << "Mang con B co tong nho nhat la: "; long long sumB = 0; for (int x : B) { cout << x << " "; sumB += x; } cout << "\nTong cua mang con B: " << sumB << endl; return 0; } DeThi.edu.vn
5. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn ĐỀ SỐ 3 TRƯỜNG ĐẠI HỌC SÀI GÒN ĐỀ THI KẾT THÚC HỌC PHẦN Môn: Phân tích & thiết kế giải thuật ĐỀ 1 Thời gian: 90 phút (không kể thời gian giao đề) Câu 1. (2,0 điểm) a. Cho hàm số T (n) = 4n + 3 + 2nlog2 n, đổi số n nguyên dương, chứng minh rằng T (n) = O(nlog2 n). b. Giả sử f(n), g(n) và r(n) là các hàm đổi số n nguyên không âm, chứng minh rằng nếu f(n) = O(g(n)) và g(n) = O(r(n)) thì f(n) = O(r(n)). Câu 2. (2,0 điểm) Cho A[1..n] là một mảng n số thực, tính độ phức tạp của giải thuật Riddle (A[1..n]) 1. if n = 1 return A[1] 2. else temp ← Riddle (A[1..n - 1]) 3. if temp ≤ A[n] return temp 4. else return A[n] Câu 3. (4,0 điểm) Cho số s và một dãy các số a1, a2, ,an được lưu trữ bởi một mảng một chiều. a. Áp dụng chiến lược thiết kế trực tiếp (brute force), viết một giải thuật để kiểm tra có tồn tại hay không hai số ai và aj (i ≠ j) trong dãy sao cho tổng của chúng bằng s. b. Áp dụng chiến lược biến đổi để trị, viết một giải thuật hiệu quả hơn giải thuật đã viết trong câu a, để kiểm tra có tồn tại hay không hai số ai và aj (i ≠ j) trong dãy sao cho tổng chúng bằng s. c. Tính độ phức tạp của các giải thuật đã viết ở câu a và b. Câu 4. (2, 0 điểm) Cho S = {1, 2 , , n} gồm n số nguyên dương. a. Viết một giải thuật quay lui tìm tất cả các chỉnh hợp chập k của n phần tử của S sao cho mỗi chỉnh hợp là một dãy các số tăng dần. b. Tính độ phức tạp về thời gian của giải thuật đã viết trong câu a. ----------HẾT---------- DeThi.edu.vn
6. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn ĐÁP ÁN Câu 1. (2,0 điểm) a. Vậy (푛) = (푛log2 푛). b. Giả sử: 1. (푛) = ( (푛)): Tồn tại 1,푛1 sao cho (푛) ≤ 1. (푛) với mọi 푛 ≥ 푛1. 2. (푛) = ( (푛)): Tồn tại 2,푛2 sao cho (푛) ≤ 2. (푛) với mọi 푛 ≥ 푛2. Kết hợp hai bất đẳng thức: (푛) ≤ 1. (푛) ≤ 1.( 2. (푛)) = ( 1. 2). (푛) với mọi 푛 ≥ max (푛1,푛2). Đặt = 1. 2 và 푛0 = max(푛1,푛2). Theo định nghĩa, ta có (푛) = ( (푛)). Câu 2. (2,0 điểm) Hệ thức truy hồi: (푛) = (푛 ―1) + 1. Giải hệ thức: (푛) = (푛 ― 1).1 = 푛 ―1. Kết luận: Độ phức tạp thời gian là (푛). Câu 3. (4,0 điểm) a. Giải thuật Vét cạn (Brute Force) Algorithm BruteForceSum(A, n, s): Input: Mảng A gồm n phần tử, số nguyên s. Output: True nếu tồn tại cặp số, ngược lại False. For i từ 1 đến n - 1 do: For j từ i + 1 đến n do: If (A[i] + A[j] == s) then: Return True Return False b. Giải thuật Biến đổi để trị (Transform and Conquer) Algorithm OptimizedSum(A, n, s): Input: Mảng A gồm n phần tử, số nguyên s. Output: True nếu tồn tại cặp số, ngược lại False. 1. Sắp xếp mảng A theo thứ tự tăng dần (ví dụ dùng Merge Sort hoặc Quick Sort). 2. left = 1 3. right = n 4. While (left < right) do: current_sum = A[left] + A[right] If (current_sum == s) then: Return True Else if (current_sum < s) then: left = left + 1 // Cần tổng lớn hơn nên tăng con trỏ trái Else: right = right - 1 // Cần tổng nhỏ hơn nên giảm con trỏ phải DeThi.edu.vn
7. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn Return False c. Độ phức tạp 푛(푛 1) - Giải thuật a: Sử dụng hai vòng lặp lổng nhau duyệt qua cặp. Độ phức tạp là 2 . 2 (푛 ) - Giải thuật b: * Sắp xếp: (푛log 푛) (sử dụng QuickSort hoạ̌c MergeSort). + Duyệt hai con trỏ: (푛). + Tổng độ phức tạp: (푛log 푛). Câu 4. (2, 0 điểm) a. Giải thuật quay lui: Procedure Trial(i) For 푗 = [푖 ―1] + 1 To 푛 ― + 푖 Do [푖] = 푗 If 푖 = Then Output( ) Else Trial ( 푖 +1 ) 푛 b. Độ phức tạp thời gian: . 푛 (hoặc . ). DeThi.edu.vn
8. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn ĐỀ SỐ 4 BỘ XÂY DỰNG ĐỀ KIỂM TRA HỌC PHẦN HỌC KỲ II TRƯỜNG ĐHXD MIỀN TÂY Môn: Phân tích & thiết kế giải thuật Thời gian: 60 phút (không kể thời gian giao đề) Câu 1: Thế nào là bài toán tìm kiếm - Viết thuật toán tìm kiếm tuần tự - Sơ đồ thuật toán tìm kiếm tuần tự - Đánh giá độ phức tạp thuật toán tuần tự Câu 2: Thực hiện các bước với thuật toán Insertion Sort để sắp xếp mảng. Có 10 bước, mỗi bước thực hiện đúng được 0,4 điểm. Câu 3: Ý tưởng thuật toán Bubble Sort - Viết thuật toán Bubble Sort - Đánh giá độ phức tạp của thuật toán Bubble Sort Câu 4: Trình bày giải pháp dựa trên thuật toán vét cạn để giải quyết bài toán “Cái ba lô” ----------HẾT---------- DeThi.edu.vn
9. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn ĐÁP ÁN Câu 1: Bài toán tìm kiếm là một loại bài toán tìm ra một đối tượng hoặc một tập hợp các đối tượng từ một không gian tìm kiếm, thoả mãn một số điều kiện cụ thể. *Phân Loại Bài Toán Tìm Kiếm - Tìm kiếm tuần tự (Sequential Search hoặc Linear Search): Duyệt qua từng phần tử trong tập hợp từ đầu đến cuối để tìm kiếm phần tử cần tìm. - Tìm kiếm nhị phân (Binary Search): Sử dụng trên các tập hợp đã được sắp xếp, bằng cách liên tục chia đôi tập hợp để giảm phạm vi tìm kiếm. - Tìm kiếm theo băm (Hash Search): Sử dụng các bảng băm để tìm kiếm phần tử một cách nhanh chóng thông qua các hàm băm. - Tìm kiếm bằng cây (Tree Search): Sử dụng các cấu trúc cây như cây nhị phân tìm kiếm (Binary Search Tree) để tổ chức và tìm kiếm dữ liệu. Các bài toán tìm kiếm rất phổ biến và xuất hiện trong nhiều ứng dụng thực tế, từ cơ sở dữ liệu, hệ thống tệp tin, cho đến các thuật toán tối ưu hóa và trí tuệ nhân tạo. - Thuật toán tìm kiếm tuần tự: (Có nhiều cách viết tùy tư duy của mỗi sinh viên) #include using namespace std; // Hàm tìm kiếm tuần tự int linearSearch(int arr[], int size, int target) { for (int i = 0; i < size; i++) { if (arr[i] == target) { return i; // Trả về chỉ số của phần tử nếu tìm thấy } } return -1; // Trả về -1 nếu không tìm thấy } int main() { int arr[] = {4, 2, 5, 1, 3, 9, 7}; int size = sizeof(arr) / sizeof(arr[0]); int target = 5; int result = linearSearch(arr, size, target); if (result != -1) { cout << "Phan tu " << target << " duoc tim thay tai chi so " << result << endl; } else { cout << "Phan tu " << target << " khong co trong mang" << endl; } DeThi.edu.vn
10. Tổng hợp 14 Đề thi môn Phân tích và thiết kế giải thuật (Kèm đáp án) - DeThi.edu.vn return 0; } - Sơ đồ thuật toán: - Độ phức tạp của thuật toán: O(n), với n là số lượng phần tử trong mảng. Câu 2: Các bước thực hiện của thuật toán Insertion Sort áp dụng cho mảng sau: [4, 7, 2, 10, 15, 14, 8, 10, 8, 5] Bước 01: [4, 7, 2, 10, 15, 14, 8, 10, 8, 5] Bước 02: [4, 7, 2, 10, 15, 14, 8, 10, 8, 5] Bước 03: [2, 4, 7, 10, 15, 14, 8, 10, 8, 5] Bước 04: [2, 4, 7, 10, 15, 14, 8, 10, 8, 5] Bước 05: [2, 4, 7, 10, 15, 14, 8, 10, 8, 5] Bước 06: [2, 4, 7, 10, 14, 15, 8, 10, 8, 5] Bước 07: [2, 4, 7, 8, 10, 14, 15, 10, 8, 5] Bước 08: [2, 4, 7, 8, 10, 10, 14, 15, 8, 5] Bước 09: [2, 4, 7, 8, 8, 10, 10, 14, 15, 5] Bước 10: [2, 4, 5, 7, 8, 8, 10, 10, 14, 15] Kết quả: [2, 4, 5, 7, 8, 8, 10, 10, 14, 15] DeThi.edu.vn