Bài kiểm tra số 2

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:

• Cấu trúc dữ liệu + Giải thuật = Chương trình

• Cấu trúc dữ liệu + Chương trình = Giải thuật

• Chương trình + Giải thuật = Cấu trúc dữ liệu

• Cấu trúc dữ liệu = Chương trình

Để đánh giá một cấu trúc dữ liệu ta thường dựa vào một số tiêu chí

• Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong),

• Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán,

• Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu.

• Cả a, b, c đều đúng

Để đánh giá giải thuật ta sử dụng khái niệm:

• Quy tắc cộng, quy tắc nhân và quy tắc chung

• Phương trình đệ quy, nghiệm của phương trình đệ quy

• Độ phức tạp và ký hiệu ô lớn

Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng:

• Qui tắc cộng

• Qui tắc trừ

• Qui tắc nhân

• Tất cả đều đúng

Trong qui tắc tổng quát, thời gian thực hiện của mỗi lệnh gán, scanf, printf là:

• C(0)

• C(1)

• O(0)

• O(1)

Theo qui tắc cộng, 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; và 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(max(f(n),g(n)))

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

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

Có thể tính độ phức tạp của một giải thuật theo nguyên tắc:

• Qui tắc cộng

• Qui tắc nhân

• Qui tắc tổng quát để phân tích một chương trình

• Tất cả đều đúng

Xác định thời gian thực hiện của chương trình là:

• A. Xác định các bước thực hiện của giải thuật

• B. Xác định sai sót trong kết quả của giải thuật

• C. Xác định độ phức tạp của giải thuật.

• D. Tất cả đều đúng

Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến

• Kết quả thu được sau khi thực hiện của chương trình

• Hiệu quả của thời gian thực hiện của chương trình

• Các bước tính toán trong quá trình thực hiện chương trình

• Tất cả đều đúng

Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến

Hàm thể hiện độ phức tạp có dạng thường gặp là:

• log₂n, n, nlog₂n

• n² , n³

• 2ⁿ, 3ⁿ , n! , nⁿ

• Tất cả đều đúng