Trắc Nghiệm Cấu Trúc Dữ Liệu Và Giải Thuật - Bài 06
1-
Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến:
A -
Kết quả thu được sau khi thực hiện của chương trình
B -
Hiệu quả của thời gian thực hiện của chương trình
C -
Các bước tính toán trong quá trình thực hiện chương trình
D -
Tất cả đều đúng
2-
Xác định thời gian thực hiện của chương trình là:
A -
Xác định cách 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
3-
Ta có thể tính độ phức tạp của một giải thuật bất kỳ theo nguyên tắc:
A -
Qui tắc cộng
B -
Qui tắc nhân
C -
Qui tắc tổng quát để phân tích một chương trình
D -
Tất cả đều đúng
4-
Trong 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à:
A -
T(n)=O(min(f(n),g(n)))
B -
T(n)=O(max(f(n),g(n)))
C -
T(n) = O(f(n).g(n))
D -
T=O(max(f(n),g(n)))
5-
Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu READ(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à:
A -
O(max(1,1))=O(1)
B -
O(max(0,0))=O(1)
C -
O(min(1,1))=O(1)
D -
O(min(0,0))=O(1)
6-
Trong qui tắc nhân, Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và 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 đoạn chương trình đó lồng nhau là:
A -
T(n)=O(min(f(n),g(n)))
B -
T(n)=O(max(f(n),g(n)))
C -
T(n) = O(f(n).g(n))
D -
T(n2) = O(f(n).g(n))
7-
Trong qui tắc tổng quát, thời gian thực hiện của mỗi lệnh gán, READ, WRITE là:
A -
C(0)
B -
C(1)
C -
O(0)
D -
O(1)
8-
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:
A -
Qui tắc cộng
B -
Qui tắc trừ
C -
Qui tắc nhân
D -
Tất cả đều đúng
9-
Qui tắc khi thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh là:
A -
Qui tắc cộng
B -
Qui tắc trừ
C -
Qui tắc nhân
D -
Qui tắc tổng quát
10-
Tính thời gian thực hiện T(n) của thủ tục sắp xếp "nổi bọt" :
