Data chương 1

Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2 mà T1(n)=O(f(n)), T2(n)=O(g(n) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là ?

• T(n)= O(min(f(n),g(n)))

• T(n)= O(f(n).g(n))

• T(n)=O(max(f(n),g(n)))

• T(n)=O(1).

Ta thường sử dụng ký hiệu nào để đánh giá độ phức tạp của giải thuật?

• Ô lớn (O)

• T lớn (T)

• Log

Phương pháp nào dùng để biểu diễn giải thuật?

• Biểu diễn bằng tay

• Biểu diễn bằng sơ đồ khối

• Biểu diễn bằng máy

Đối với các chương trình không gọi chương trình con, thì dùng quy tắc cộng, quy tắc nhân và quy tắc chung để phân tích, tính độ phức tạp ?

• Sai

• Đúng

Tính thời gian thực hiện của đoạn chương trình Tính tổng của các số:

Sum:=0;

for(int i=1; i<=n; i++){

    cin>>x;

    Sum=Sum+x;

}  

• O(n-1)

• O(1)

• O(n)

Đối với các chương trình gọi chương trình con, thì tính độ phức tạp theo nguyên tắc ?

• Từ trong ra

• Từ dưới lên

• Từ ngoài vào

• Từ trên xuống

Trong đánh giá độ phức tạp giải thuật, đơn vị đo thời gian thực hiện chương trình là?

• Tính theo đơn vị thời gian

• Tình theo số tài nguyên máy tính được sử dụng trong quá trình thực hiện

• Tính theo dung lượng bộ nhớ

• Tính theo số các lệnh (phép tính cơ sở) được thực hiện trong một máy tính lý tưởng.

Phân tích, đánh giá giải thuật là cần thiết để ?

• Lựa chọn giải thuật tốt hoặc để cải tiến giải thuật.

• Tìm nghiệm của bài toán.

• In ra kết quả của bài toán.

• Lựa chọn phương pháp biểu diễn thuật toán

Thời gian thực hiện đoạn chương trình sau là... ?

for (int i=1; i<=n;i++)

    x=x+1;

• O(n.1) = O(n)

• O(max(n-1)) = O(n-1)

• O(n.n) = O(n^2)

Lệnh gán x=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu cin>>x; tốn một hằng thời gian hay O(1).Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là ?

• O(max(1,1))=O(1)

• O(min(1,n))=O(logn)

• O(min(1,1))=O(n*n)

• O(max(1,n))=O(n)