CTDL_Tuần 1

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

• Phương pháp truy hồi hoặc phương pháp đoán nghiệm.

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

• C(0)

• C(1)

• O(0)

• O(1)

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 lập trình, việc sử dụng cấu trúc dữ liệu giúp cho việc nào sau đây?

• Làm cho chương trình dễ đọc và dễ hiểu hơn

• Tối ưu hóa việc sử dụng bộ nhớ

• Tăng tốc độ xử lý của chương trình

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

Trong lập trình, thời gian thực hiện của một thuật toán thường được đo bằng đơn vị nào?

• Đơn vị thời gian

• Đơn vị bộ nhớ

• Đơn vị tốc độ xử lý

• Đơn vị thời gian O()

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à:

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

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

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

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