Bài 25 Thực hành xác định độ phức tạp thời gian thuật toán

Lớp 11Tin Học16 câu hỏiBài tập
Tải Word | Làm thử | Giao đề

Phần 1

Câu 1

(Câu 25.1 trang 77 SBT Tin học 11) Cho hàm thời gian T ( n ) = n + 2 l o g n . Độ phức tạp thời gian của hàm là gì?
A O ( n ) .
B O ( l o g n ) .
C O ( n 2 ) .
D O ( 1 ) .

Câu 2

(Câu 25.1 trang 77 SBT Tin học 11) Cho hàm thời gian T ( n ) = n 2 + 3 n l o g n + 2 n . Độ phức tạp thời gian của hàm là gì?
A O ( n 2 ) .
B O ( n ) .
C O ( l o g n ) .
D O ( 1 ) .

Câu 3

(Câu 25.1 trang 77 SBT Tin học 11) Cho hàm thời gian T ( n ) = 2 1 0 0 . Độ phức tạp thời gian của hàm là gì?
A O ( 1 ) .
B O ( n ) .
C O ( n 2 ) .
D O ( 2 n ) .

Câu 4

(Câu 25.1 trang 77 SBT Tin học 11) Cho hàm thời gian T ( n ) = 2 n + 1 . Độ phức tạp thời gian của hàm là gì?
A O ( 2 n ) .
B O ( n ) .
C O ( n 2 ) .
D O ( 1 ) .

Câu 5

(Câu 25.2 trang 77 SBT Tin học 11) Thuật toán sau thực hiện công việc gì? def findMax(A): maxVal = A[0]; for i in range(1, len(A)): if A[i] > maxVal: maxVal = A[i]; return maxVal.
ATìm phần tử lớn nhất của mảng A.
BTìm phần tử nhỏ nhất của mảng A.
CSắp xếp mảng A theo thứ tự tăng dần.
DĐếm số phần tử của mảng A.

Câu 6

(Câu 25.3 trang 78 SBT Tin học 11) Hàm revFunction(S) khởi tạo revs = "", i = len(S) - 1, sau đó lặp và ghép S[i] vào revs rồi giảm i. Hàm này thực hiện công việc gì?
ATrả về xâu đảo ngược của xâu đầu vào.
BĐếm số kí tự của xâu đầu vào.
CTìm kí tự lớn nhất trong xâu đầu vào.
DXoá toàn bộ kí tự trong xâu đầu vào.

Câu 7

(Câu 25.4 trang 78 SBT Tin học 11) Với thuật toán sắp xếp chèn trong PDF, thời gian chạy tối đa được đánh giá là T ( n ) = n 2 + 2 n − 2 . Độ phức tạp thời gian của thuật toán là gì?
A O ( n 2 ) .
B O ( n ) .
C O ( l o g n ) .
D O ( 1 ) .

Câu 8

(Câu 25.5 trang 78 SBT Tin học 11) Hàm exaFunction(n) có ba vòng lặp lồng nhau, trong đó i chạy từ 1 đến n, j chạy từ 1 đến i, k chạy từ j đến i + j. Độ phức tạp thời gian của hàm là gì?
A O ( n 3 ) .
B O ( n 2 ) .
C O ( n ) .
D O ( l o g n ) .

Phần 2

Câu 1

(Câu 25.2 trang 77 SBT Tin học 11) Phân tích hàm findMax(A) tìm phần tử lớn nhất của mảng A.
a)Hàm khởi tạo maxVal = A[0] để lưu giá trị lớn nhất tạm thời.
b)Vòng lặp duyệt các phần tử của A từ chỉ số 1 đến len(A) - 1.
c)Nếu A[i] > maxVal thì hàm cập nhật maxVal = A[i].
d)Thời gian chạy của hàm là O ( n 2 ) vì có hai vòng lặp lồng nhau.

Câu 2

(Câu 25.3 trang 78 SBT Tin học 11) Phân tích hàm đảo ngược xâu revFunction(S).
a)Hàm khởi tạo revs là xâu rỗng.
b)Biến i ban đầu được gán bằng len(S) - 1.
c)Vòng lặp while thực hiện n lần nếu xâu S có n kí tự.
d)Độ phức tạp thời gian của hàm là O ( 1 ) vì chỉ có một lệnh return.

Câu 3

(Câu 25.4 trang 78 SBT Tin học 11) Phân tích thuật toán sắp xếp chèn trong PDF.
a)Dòng n = len(A) cần một đơn vị thời gian.
b)Vòng lặp for chạy với i từ 1 đến n - 1 nên có n - 1 bước lặp.
c)Trong trường hợp xấu nhất, vòng lặp while có thể chạy tối đa i lần ở bước lặp thứ i.
d)Thời gian chạy tối đa của thuật toán là O ( n ) .

Câu 4

(Câu 25.4 trang 78 SBT Tin học 11) Xét công thức thời gian chạy tối đa của thuật toán sắp xếp chèn trong PDF.
a)Công thức được rút gọn thành T ( n ) = n 2 + 2 n − 2 .
b)Thành phần bậc cao nhất của T ( n ) là n 2 .
c)Khi đánh giá theo kí hiệu O-lớn, các hạng tử bậc thấp và hệ số hằng không làm thay đổi bậc độ phức tạp.
d)Vì T ( n ) = n 2 + 2 n − 2 nên độ phức tạp thời gian là O ( l o g n ) .

Câu 5

(Câu 25.5 trang 78 SBT Tin học 11) Phân tích hàm exaFunction(n) trong PDF.
a)Lệnh gán r = 0 cần một đơn vị thời gian.
b)Vòng lặp ngoài với biến i chạy từ 1 đến n nên có n bước lặp.
c)Với mỗi i, vòng lặp j chạy từ 1 đến i.
d)Hàm chỉ có một vòng lặp nên thời gian chạy là O ( n ) .

Câu 6

(Câu 25.5 trang 78 SBT Tin học 11) Xét độ phức tạp của hàm exaFunction(n).
a)Hàm có các vòng lặp lồng nhau.
b)Số lần thực hiện lệnh r = r + 1 phụ thuộc vào n.
c)Thành phần tăng nhanh nhất của thời gian chạy có bậc ba theo n.
d)Độ phức tạp thời gian của hàm là O ( 1 ) .

Câu 7

(Câu 25.6 trang 78 SBT Tin học 11) Nếu f ( n ) = O ( g ( n ) ) thì có suy ra được g ( n ) = O ( f ( n ) ) hay không?
a)Không thể suy ra trong mọi trường hợp.
b)Có thể lấy ví dụ f ( n ) = n , g ( n ) = n 2 thì f ( n ) = O ( g ( n ) ) .
c)Với f ( n ) = n , g ( n ) = n 2 , chiều ngược lại g ( n ) = O ( f ( n ) ) là không đúng.
d)Nếu f ( n ) = O ( g ( n ) ) thì chắc chắn g ( n ) = O ( f ( n ) ) .

Câu 8

(Câu 25.7 trang 78 SBT Tin học 11) Giả sử f ( n ) = a k n k + a k − 1 n k − 1 + . . . + a 1 n + a 0 , với a k ≠ 0 . Xét độ phức tạp của hàm đa thức này.
a)Hạng tử có bậc cao nhất là a k n k .
b)Khi n đủ lớn, hạng tử bậc cao nhất quyết định tốc độ tăng của đa thức.
c)Theo quy tắc lấy thành phần tăng nhanh nhất, f ( n ) = O ( n k ) .
d)Với mọi đa thức bậc k, ta luôn có f ( n ) = O ( 1 ) .
Tải Word | Làm thử | Giao đề bài này ngay