Cấu trúc dữ liệu & Giải thuật 1

Với a được khai báo là số nguyên và giá trị khởi tạo là 1. Cho biết kết quả của lệnh

printf ("%d", a==2?5:2);

• 2

• 5

• 1

• 0

Cho phát biểu sau: "Nếu T₁(n), T₂(n), ... ,T_k(n) lần lượt là thời gian thực hiện các đoạn trình liên tiếp nhau và có độ phức tạp tương ứng là O(g₁), O(g₂), ... ,O(g_k) thì độ phức tạp của toàn bộ chương trình sẽ là: T(n) = T₁(n) + T₂(n) + ... + T_k(n) = O(max{g_{1, ... ,}g_k})". Phát biểu trên là nội dung của quy tắc nào ?

• Quy tắc nhân

• Quy tắc tổng

• Quy tắc hằng

• Quy tắc biến

Đánh giá độ phức tạp của giải thuật sau:

int KiemTra(int n) {

iint i;

for (i = 2; i<n; i++)

if (n%i == 0) return 0;

return1;

}

• O(n³)

• O(n²)

• O(n)

• O(log₂n)

Lệnh "return (a>b) ? a:b; " tương dương với lệnh nào sau đây ?

• if (a>=b) return a, else return b;

• if (a=b) return a, else return b;

• if (a<b) return a, else return b;

• if (a>b) return a, else return b;

Độ phức tạp của giải thuật không đệ quy tính n! (n giai thừa) là bao nhiêu ?

• O(n)

• O(log₂n)

• O(n²)

• O(n³)

Đối với một giải thuật, ta thường sử dụng những quy tắc nào để đánh giá độ phức tạp của giải thuật ? Chọn phương án đúng nhất

• Không dùng quy tắc nào

• Quy tắc tổng, quy tắc nhân

• Quy tắc tổng

• Quy tắc nhân

Tìm mô tả đúng cho giải thuật sau:

int Tinh (int n) {

if (n==1) return 1;

return Tinh (n-1) + n;

}

• Hàm tính tổng các lập phương của n số tự nhiên đầu tiên

• Hàm tính tổng các bình phương của n số tự nhiên đầu tiên

• Hàm tính tổng n số tự nhiên đầu tiên

• Hàm tính tổng các căn bậc 2 của n số tự nhiên đầu tiên