30 Test Quizz PTTKTT - Có Key PDF

CÂU HỎI TRẮC NGHIỆM ÔN TẬP MÔN PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN Khoa CNTT – Đai học SPKTHY Câu 1 Phát biểu nào sau đây đúng về tính chất của thuật toán? A Tính đúng đắn, tính dừng, tính rõ ràng (xác định) B Tính hạn chế, tính dừng, tí...

CÂU HỎI TRẮC NGHIỆM ÔN TẬP MÔN PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN Khoa CNTT – Đai học SPKTHY Câu 1 Phát biểu nào sau đây đúng về tính chất của thuật toán? A Tính đúng đắn, tính dừng, tính rõ ràng (xác định) B Tính hạn chế, tính dừng, tính rõ ràng (xác định) C Tính đúng đắn, tính phức tạp, tính rõ ràng (xác định) D Tính đúng đắn, tính dừng, tính phức tạp Đáp án A Câu 2 Tính độ phức tạp của giải thuật sau test()? int test(int n) { int count = 0; for (int i = 0; i < n; i++) for (int j = i; j > 0; j--) count = count + 1; return count; } A Θ(n) B Θ(n2) C Θ(n2log(n)) D Θ(nlog(n)) Đáp án B Câu 3 Hàm nào sau đây không thuộc O(n2)? A 1510.n +2020 B 2020.n1.98 + 2002 C n3/log(n) D 1510.nlog(n) Đáp án C Câu 4 Cho đoạn code sau: int j, n; j = 1; while (j B < c, a, b> C < b, c, a, a> D < b, c, b, a> Đáp án D Câu 9 Tìm trình tự nhân và số cách tính tối ưu cho tích của ba ma trận M1M2M3 với các kích thước d = (2, 5, 4, 3) A (M1)(M2 M3), số phép tính 90 B (M1)(M2 M3), số phép tính 64 C (M1M2) (M3), số phép tính 64 D (M1M2) (M3), số phép tính 90 Đáp án C Câu 10 Gọi A1, A2, A3 và A4 là bốn ma trận có kích thước lần lượt là 10 x 5, 5 x 20, 20 x 10 và 10 x 5. Số phép nhân vô hướng tối thiểu cần thiết để tìm tích A1A2A3A4 bằng phương pháp nhân ma trận cơ bản là A 1500 B 2000 C 500 D 100 Đáp án A Câu 11 Điều gì xảy ra khi phương pháp tiếp cận từ trên xuống của quy hoạch động được áp dụng cho bất kỳ bài toán nào?  A Nó làm tăng cả hai, độ phức tạp về thời gian và độ phức tạp về không gian B Nó làm tăng độ phức tạp về không gian và giảm độ phức tạp về thời gian. C Nó làm tăng độ phức tạp về thời gian và giảm độ phức tạp về không gian D Nó làm giảm cả hai, độ phức tạp về thời gian và độ phức tạp về không gian Đáp án B Câu 12 Khẳng định nào sau đây là phù hợp nhất của Chiến lược thiết kế Tham Lam? A Giải thuật thiết kế kiểu từ trên xuống (top-down) B Đưa ra quyết định tốt nhất trong hiện tại, và trong tương lai sẽ không xem xét lại quyết định trong quá khứ C Giải thuật thiết kế kiểu từ dưới lên (bottom - up) D Phân chia bài toán ban đầu thành các bài toán con để giải Đáp án B Câu 13 Trong bài toán sắp xếp balo 0/1. Bước nào được thực hiện đầu tiên? A Sắp xếp các đồ vật theo chiều giảm tỉ lệ Giá trị/ Khối lượng. B Sắp xếp các đồ vật theo chiều giảm tỉ lệ Khối lượng/ Giá trị. C Sắp xếp các đồ vật theo chiều giảm tỉ lệ Giá trị + Khối lượng D Sắp xếp các đồ vật theo chiều giảm tỉ lệ Khối lượng Đáp án A Câu 14 Bốn ma trận M1, M2, M3 và M4 có kích thước lần lượt là pxq, qxr, rxs và sxt có thể được nhân bằng một số cách với tổng số phép nhân vô hướng khác nhau. Ví dụ: khi nhân với ((M1 X M2) X (M3 X M4)), tổng số phép nhân là pqr + rst + prt. Khi nhân với (((M1 X M2) X M3) X M4), tổng số phép nhân vô hướng là pqr + prs + pst. Nếu p = 10, q = 100, r = 20, s = 5 và t = 80 thì số phép nhân vô hướng ít nhất cần thiết là: A 248000 B 44000 C 19000 D 25000 Đáp án C Câu 15 Cho các thuật toán và độ phức tạp sau. A. O(log n) 1. Buble sort B. O(n^2) 2. Selection sort C. O(nlog n) 3. Binary search D. O(n^2) 4. Merge sort Lựa chọn sự ghép nối đúng: A B C D a. 3 1 4 2 b. 3 1 2 4 c. 1 3 4 2 d. 1 4 3 2 A a  B b C c D d Đáp án B Câu 16 Cho dãy số A[0..9] gồm 10 số sau: 1 10 16 21 29 30 49 77 80 101 Áp dụng thuật toán tìm kiếm nhị phân để tìm phần tử có giá trị x=32 xem có trong dãy đã cho hay không? Hỏi sau lần gọi đệ quy thứ nhất thuật toán tìm x=32 ở đoạn nào: A Tìm x ở đoạn A[0..4] B Tìm x ở đoạn A[4..9] C Tìm x ở đoạn A[0..3] D Tìm x ở đoạn A[5..9] Đáp án D Câu 17 Kỹ thuật chia để trị chia thành a không gian để trị có kích thước là n/b và phát sinh các phép toán theo hàm f(n) , thì ta có công thức truy hồi tổng quan như sau A T(n)=2T(n/2)+f(n) B T(n)=aT(n/b) + f(n). C T(n)=bT(n/a) + f(n). D T(n)=aT(n/a) + f(n). Đáp án B Câu 18 Cho đoạn mã sau để tìm dãy con chung dài nhất của 2 dãy Xi và Yi (0