Cấu trúc dữ liệu và giải thuật - IT05 (15)

Trong giải thuật đệ quy thì lời giải trực tiếp mà không phải nhờ đến một bài toán con nào đó là thành phần nào?

Cho biết kết xuất của đoạn chương trình sau:

long F(int n)

{

if ((2*n+1) ==1)

return 1;

else

return (2*n+1)+F(n-1);

}

void main()

{

long x=F(3);

printf("%ld", x);

}

Để tính biểu thức s = ½ + ¼ + … + 1/(2n) với n>=1 ta chọn hàm

Để tính biểu thức s = ½ + 2/3 + ¾ + … + n/(n+1) ta chọn hàm

Để xác định giải thuật đệ quy cần xác định gì?

Thuật toán được biểu diễn bằng cách nào

Độ phức tạp thuật toán được đánh giá có loại nào?

Cho biết kết quả của đoạn chương trình sau:

long f5(int n)

{

if (2*n==2)

return 2;

else

return 2*n + f5(n-1);

}

int main()

{

long x = f5(3);

printf("%ld", x);

getch();

}

Để tính biểu thức s = xn với n>=0 ta chọn hàm

Cho đoạn mã sau, cho biết đoạn mã biểu diễn thuật toán gì?

Bước 1: S = 1, i = 1;

Bước 2: Nếu i<n thì s = s*i, qua bước 3;

Ngược lại qua bước 4;

Bước 3: i = i + 1;

Quay lại bước 2;

Bước 4: Xuất S ra màn hình

Cho biết kết quả sau khi thực hiện đoạn chương trình sau:

int main()

{

int a[20], n,i,k;

k = a[n-1];

for(i=n-2; i>=0; i--)

if (a[i] < k)

k = a[i];

}

Đây là định nghĩa của độ phức nào? “Được tính là tổng số chi phí về mặt không gian (bộ nhớ) cần thiết sử dụng cho thuật toán”

Đâu là công thức tổng quát để tính giai thừa dựa vào giải thuật đệ quy

Cho biết kết quả của đoạn chương trình sau:

long f3(int n)

{

if (n==1)

return 1;

else

return n*n + f3(n-1);

}

int main()

{

long x = f3(3);

printf("%ld", x);

getch();

}

Cho mảng a có N (N>=2) phần từ, x là một biến, xét đoạn mã sau cho biết đoạn mã biểu diễn thuật toán gì?

Bước 1: Khởi gán i = 0, s = 0, qua bước 2;

Bước 2: Nếu a[i] == x thì

s++; qua bước 3

Bước 3: i = i + 1;

Nếu i == n: hết mảng. Dừng, in s ra màn hình

Ngược lại: Lặp lại bước 2