Trắc nghiệm kiểm tra Cấu trúc dữ liệu và giải thuật Tuần 2 - Cấu trúc dữ liệu và giải thuật (ET2100) | Trường Đại học Bách khoa Hà Nội

lOMoAR cPSD| 44729304
1. Đâu là khẳng định đúng về thuật toán •
Mỗi bài toán chỉ tồn tại duy nhất một thuật toán để giải chính xác •
Thuật toán có thể được mô tả theo nhiều cách khác nhau •
Kích thước đầu vào bài toán thay đổi có thể dẫn đến việc thay đổi thuậ t toán •
Thuật toán có thể được biểu diễn dưới dạng đệ quy hoặc vòng lặp Thuật toán được coi là
chính xác nếu không tìm được phản ví dụ
2. Cho hàm sau, đâu là khẳng định đúng int func(int n, int k) { int result = n;
for (int i = 1; i < k+n; i *= 2) result ++; return result; } •
Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(n) •
Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(n+k) •
Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(sqrt(n+k) )
Đ ộ ph ức t ạ p tính toán theo O-L ớ n trong TH t ồi nh ất là O(log(n+k) ) •
Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(logn)
3. Ưu điểm của cách đánh giá thuật toán trực tiếp là Có thể đánh giá thuật toán ngay từ mô tả •
Không phụ thuộc vào cấu hình phần cứng máy tính •
Có thể tái sử dụng đánh giá cũ khi so sánh thuật toán •
Đánh giá đơn giản và dễ dàng hơn mô hình gián tiếp
4. Đâu là khẳng định đúng về thời gian thực hiên của thuật toán theo O-lớn
• Nếu đầu vào bài toán cỡ n = 1000 và thời gian chấp nhận được thì ta có thể chọn các thuật toán
thuộc lớp hàm O(logn), O(n), O(n^2), O(n^3)
• Nếu đầu vào bài toán cỡ n = 10,000,000 và thời gian chấp nhận được thì ta có thể chọn các thuật
toán thuộc lớp hàm O(logn), O(n), O(n^2), O(n^3)
• Nếu đầu vào bài toán cỡ n = 100,000,000 và thời gian chấp nhận được thì ta có thể chọn các thuật
toán thuộc lớp hàm O(logn), O(n), O(nlogn), O(n^2)
• Nếu đầu vào bài toán cỡ n = 1,000,000,000 và thời gian chấp nhận được thì ta có thể chọn các thuật
toán thuộc lớp hàm O(logn), O(n), O(nlogn), O(n^2)
5. Thời gian thực hiện của thuật toán có đặc điểm là gì? Hãy chọn các đáp án đúng
• Phụ thuộc vào kích thước đầu vào
• Phụ thuộc vào giá trị đầu vào cụ thể của dữ liệu
• Thời gian thực hiện tồi nhất là thời gian được quan tâm nhất lOMoAR cPSD| 44729304
• Thời gian trung bình là trung bình cộng của thời gian tồi nhất và tốt nhất
6. A và B là 2 thuật toán có thời gian thực hiện trong trường hợp tồi nhất tương ứng là
T_a(n) = 100n^2 + n+6, và T_B(n) = n^3 +n. Những kết luận nào sau đây là đúng
• Thuật toán B luôn cho thời gian thực hiện tồi hơn A
• Thuật toán A thường nhanh hơn B trong trường hợp tổng quát
• Trong một số trường hợp, thuật toán A có thể chậm hơn thuật toán B
• Thuật toán A luôn nhanh hơn thuật toán B
7. Cho các hàm sau, xét theo thứ tự tốc độ tăng thì đâu là khẳng định đúng
2^n, 2^logn, nlogn, n√n, n^(3/5), n! √ là căn bậc 2 ^ là hàm mũ
Hàm có t ốc đ ộ tăng nhanh nh ấ t là n ó •
Hàm có tốc độ tăng nhanh nhất là 2^n •
Hàm có tốc độ tăng chậm nhất là nlogn
Hàm có t ốc đ ộ tăng ch ậ m nh ất l à n^(3/5)
8. Đánh giá độ phức tạp thuật toán theo O-lớn là
• Đánh giá hiệu quả của thuật toán trong trường hợp tồi nhất
• Đánh giá tốc độ tăng về thời gian thực hiện theo kích thước đầu vào
Đánh giá về bộ nhớ của
thuật toán cần theo kích thước đầu vào
Ch ỉ quan tâm đ ế n l ệ nh đ ượ c th ực hi ệ n nhi ều nh ất
• Quan tâm đến tất cả các lệnh trong mô tả thuật toán
9. Cho đoạn chương trình sau, đâu là khẳng định đúng int k = 0, i=1; while (i<=n) { i=i*2; k++; } printf("%d", k);
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(n)
Đ ộ ph ức t ạ p tính toán theo O-L ớ n trong TH t ồi nh ấ t là O(logn)
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(1)
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(n^2) lOMoAR cPSD| 44729304
10. Viết hàm tính tổng các phần tử chẵn trong dãy dùng đệ quy, Cần điền gì vào chỗ trống?
// Hàm đệ quy tính tổng các phần tử chẵn trong mảng int
sumEvenRecursive(int arr[], int n) { if (n == 1) { if (arr[0] % 2 == 0) { return arr[0]; } else { return A1; } }
else { if (arr[n-1]%2==0) { return A2; }
else { return sumEven Recursive(arr, n - 1); } } }
A1 đi ền 0, A2 đi ền arr[n - 1] + sumEvenRecursive(arr, n - 1)
• A1 điền -1, A2 điền sumEvenRecursive(arr, n - 1)
• A1 điền 0, A2 điền sumEvenRecursive(arr, n - 1)
• A1 điền 0, A2 điền sumEvenRecursive(arr, n)
11. Đâu là khẳng định đúng về các kỹ thuật đánh giá hiệu quả thuật toán
• Hai thuậc t toán thu ộc 2 l ớp hàm khác nhau (theo O-l ớ n) sẽ có t ốc đ ộ tăng khá nhau
• Hai thuật toán thuộc cùng 1 lớp hàm (theo O-lớn) sẽ có thời gian thực hiện như nhau
• Muốn so sánh cụ thể thời gian thực hiệ mô
n c ủa các thu ậ t toán ta c ần phân tích dùng hình RAM
• Nếu việc phân tích thuật toán theo mô hình RAM quá phức tạp, ta có thể cài đặt và đo thời gian
thuật toán gián tiếp để đánh giá thuật toán (cần chạy nhiều lần tính thời gian trung bình)
12. Tại sao cần xây dựng thuật toán hiệu quả lOMoAR cPSD| 44729304
• Vì máy tính không thể tăng tốc độ bộ xử lý lên mãi được
• Vì kích thước dữ liệu của bài toán mà máy tính cần xử lý ngày càng tăng
• Vì chúng ta muốn rút ngắn thời gian phải chờ đợi
• Vì chi phí xây dựng thuật toán hiệu quả sẽ rẻ hơn
• Vì chi phí để đầu tư nâng cao tốc độ máy tính thường đắt hơn nhiều so với chi phí đầu tư cải tiến thuật toán
13. Cho hàm có độ phức tạp sau f(n) = 50n - logn + 2000+ log99(100n+2) Đâu là khẳng định đúng? • f(n) = O(n^2) • f(n) = O(nlogn) • f(n) = O(logn) f(n) = O(n)
14. Cho đoạn chương trình sau, đâu là khẳng định đúng int i, j, k = 0; for (i = 0; i < n; i++) { for (j = i; j <= n; j = j * 2) { k++; } } printf("%d", k);
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(logn)
Đ ộ ph ức t ạp tính toán theo O-L
ớn trong TH t ồi nh ất là O(nlogn)
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(n)
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(n^2)
15. Cách đo hiệu quả thuật toán gián tiếp qua hiệu quả chương trình máy tính không đủ tin cậy khi so sánh thuật toán vì
• Thời gian chạy phụ thuộc nhiều vào cấu hình phần cứng
• Ngôn ngữ lập trình ảnh hưởng đến hiệu quả chương trình
• Kinh nghiệm của người lập trình sẽ ảnh hưởng tới hiệu quả chương trình
• Việc so sánh thuật toán sẽ mất nhiều thời gian
• Khó có thể tận dụng lại các kết quả đã có khi so sánh với 1 thuật toán mới
16. // hàm kiểm tra mảng đối xứng 1,2,3,2,1 - --> 1 và 1,2,2,3 --> 0
// A là tên mảng // n là số lượng
phần tử int testFunc(int* A, int n, int k) { if (n < 2) return 0; if (k == n / 2) return 1; else {
int s = testFunc(A, n, k + 1); if (s == 0) return 0; AAAAAAAAAAAAAAAAA; } }
Bạn cần điền gì vào vị trí AAAAAAAAAAAAAAAAA(1 Point) L lOMoAR cPSD| 44729304
• if((A+k) == *(A+n-k)) return 1; else return 0;
• if((A+k+1) == *(A+n-1-k)) return 1; else return 0; if((A+k) == (A+n-k)) return 1; else return 0;
if((A+k) == *(A+n-1-k)) return 1; else return 0;
17. Đặc điểm của mô hình RAM là
• Đếm số lần thực hiện các câu lệnh cơ bản
• Chỉ quan tâm chính đến thời gian thực hiện - thời gian CPU
• Chỉ có thể đánh giả thuật toán được mô tả bằng giả ngôn ngữ hoặ lập trình cụ thể c ngôn ngữ
• mất nhiều thời gian để đánh giá vì phải xét từng câu lệnh đơn lẻ
18. Cho đoạn chương trình sau, đâu là khẳng định đúng sqrt là hàm căn bậc hai int i = 1, s = 1; while (s <= n) { i++; S+= i; } printf("%d", i);
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(n)
Đ ộ ph ức t ạ p tính toán theo O-L ớ n trong TH t ồi nh ất là O(sqrt(n))
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(nlogn)
• Độ phức tạp tính toán theo O-Lớn trong TH tồi nhất là O(logn)
19. Cho thuật toán được định nghĩa dưới dạng đệ quy sau, đâu là các khẳng định đúng int Func(int N) { if(N= 0) return 1;
return Func(N-1) + 2*Func(N-2); }
• Giá trị của Func(5) là 21
• Giá trị của Func(5) là 11 ỗi Hàm l •
Giá trị của Func(4) là 11
• Giá trị của Func(4) là 5
20. Cho thuật toán được định nghĩa dưới dạng đệ quy sau, đâu là các khẳng định đúng int Func(int N)
{ if(N>0 && N%2==0) return 2*Func(N/2); else if(N>0 && N%2!=0) return Func(N/2) + 1; else return 0; }
• Giá trị của Func(5) là 3
Giá tr ị c ủa Func(5) là 4 • Hàm lỗi
• Giá trị của Func(6) là 4
Giá tr ị c ủa Func(6) là 6