CTDL_3

Đố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?

• Quy tắc nhân.

• Quy tắc tỏng và quy tắc nhân.

• Quy tắc tỏng.

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

Cho biết dộ phức tạp của giải thuật sau:

sum=0;

for(i=0;i<n;i++){

sum=sum+i*i; }

• O(n²)

• O(n³)

• O(n)

• O(log₂n)

Cho biết độ phức tạp của giải thuật tính tổng các nghịch đảo của n số tự nhiên đầu tiên.

• O(n²)

• O(n3)

• O(log₂n)

• O(n)

Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh họa bằng đẳng thức nào dưới đây?

• Giải thuật=Chương trình.

• CTDL+Chương trình=Giải thuật.

• CTDL+Giải thuật=Chương trình.

• CTDL=Giải thuật+Chương trình.

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 câu lệnh: printf("%d",a==2? 5:2);

• 2

• 5

• 0

• 1

Để đánh giá một CTDL chúng ta thường dựa vào những tiêu chí nào?

• CTDL phải phản ánh đúng thực tế của bài toán.

• CTDL phải dễ dàng trong việc thao tác dữ liệu.

• CTDL phải tiết kiệm tài nguyên (bộ nhớ trong).

• Cả 3 tiêu chí trên.

Cho chương trình sau:

#include <stdio.h>

float Tinh(float n){ if(n==1) return 0.5;

return Tinh(n-1) + 1/(2*n);}

int main(){ printf("\nkq= %3.2f", Tinh(4); }

Cho biết kết quả hiển thị ra màn hình khi chạy chương trình trên.

• 1.041667

• 1.04

• 3.2

• 1.041

Cho biết phân cơ sở của giải thuật sau:

int Tinh(int n){ if(n==1) return 1;

return Tinh(n-1) + n;}

• if(n==1) return 1;

• int Tinh(int n){

• return

• 1

 $Cho\ S\left(n\right)=\frac{1}{2}+\frac{3}{4}+\frac{5}{6}+\cdot\cdot\cdot+\frac{\left(2n+1\right)}{\left(2n+2\right)}$  , n là số nguyên không âm. viết công thức truy hồi cho S(n)

•  $S(n)=\frac{\left(2n+1\right)}{\left(2n+2\right)}$  

•  $S(n)=S\left(n-1\right)+\frac{\left(2n+1\right)}{\left(2n+2\right)}$  

•  $S(n)=\frac{1}{2}$  

•  $S(n)=0$  

Khi viết giải thuật tính xⁿ với x là số thực, n là số nguyên, ta phải xét những trường hợp nào của n?

• n>0

• n=0

• Cả 3 phương án

• n<0