Free Printable Độ phức tạp thời gian của thuật toán

Worksheets

Độ phức tạp thời gian của thuật toán

Total questions: 52

Worksheet time: 26mins

Name

Class

Date

Phương án nào bên dưới thể hiện độ phức tạp thời gian của thuật toán tìm kiếm tuần tự?

$O(1)$

$O(\log n)$

$O(n)$

$O(n^2)$

Phương án nào bên dưới thể hiện độ phức tạp thời gian của thuật toán sắp xếp nổi bọt BubbleSort?

$O(n^2)$

$O(n\log n)$

$O(n)$

$O(1)$

Phương án nào bên dưới thể hiện độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp xấu nhất?

$O(n\log n)$

$O(\log n)$

$O(n)$

$O(1)$

Phương án nào bên dưới thể hiện độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp tốt nhất?

$O(n\log n)$

$O(\log n)$

$O(n)$

$O(1)$

Ký hiệu $O(n)$ trong nhận định độ phức tạp thời gian biểu thị điều gì sau đây?

Chương trình có độ phức tạp tuyến tính

Chương trình có độ phức tạp bình phương

Chương trình có độ phức tạp mũ

Chương trình có độ phức tạp hằng số

Trong trường hợp nào dưới đây độ phức tạp thời gian của chương trình là $O(1)$ ?

Khi chương trình có vòng lặp lồng nhau

Khi chương trình chỉ có các phép toán đơn và không phụ thuộc vào $n$

Khi chương trình có độ phức tạp tuyến tính

Khi chương trình có độ phức tạp lũy thừa

Để tính độ phức tạp thời gian của chương trình với các phép toán lồng nhau, ta áp dụng quy tắc nào sau đây?

Quy tắc cộng

Quy tắc nhân

Quy tắc chia

Quy tắc cộng và chia

Phương án nào bên dưới cho biết độ phức tạp thời gian của đoạn chương trình sau: for i in range(1, n+1): if i%2==0: c=c+1

$O(1)$

$O(\log n)$

$O(n)$

$O(n^2)$

Phương án nào bên dưới cho biết độ phức tạp thời gian của đoạn chương trình sau: for i in range(1, n+1): if i%2==0: c1=c1+1 else: c2=c2+1

$O(1)$

$O(\log n)$

$O(n)$

$O(n^2)$

10.

Phương án nào bên dưới cho biết độ phức tạp thời gian của đoạn chương trình sau: for i in range(1, n+1): if i%2==0: for j in range(1,n+1): c=c+1

$O(1)$

$O(\log n)$

$O(n)$

$O(n^2)$

11.

Phương án nào bên dưới cho biết độ phức tạp thời gian của đoạn chương trình sau: a=0 b=0 c=0 for i in range(1,n+1): a=a+1 b=b+1 c=c+i*i

$O(1)$

$O(n)$

$O(n^2)$

$O(n^3)$

12.

Phương án nào dưới đây cho biết độ phức tạp thời gian của đoạn chương trình sau: i = n d = 0 while i > 0: i = i - 1 d = d + i

$O(1)$

$O(\log n)$

$O(n)$

$O(n^2)$

13.

Phương án nào dưới đây cho biết độ phức tạp thời gian của đoạn chương trình sau: i = 0 d = 0 while True: i = i + 1 if i % 3 == 0: d = d + i if i >= n: break

$O(1)$

$O(\log n)$

$O(n)$

$O(n^2)$

14.

Phương án nào dưới đây cho biết độ phức tạp thời gian của đoạn chương trình sau: d = 0 for i in range(1, n): for j in range(i + 1, n + 1): d = d + 1

$O(1)$

$O(n)$

$O(n^2)$

$O(n^3)$

15.

Phương án nào dưới đây cho biết độ phức tạp thời gian của đoạn chương trình sau: d = 0 for i in range(1, n - 1): for j in range(i + 1, n): for k in range(j + 1, n + 1): d = d + 1

$O(1)$

$O(n)$

$O(n^2)$

$O(n^3)$

16.

Phương án nào dưới đây cho biết độ phức tạp thời gian của đoạn chương trình sau: d = 0 while n > 0: n = n / 2 d = d + 1

$O(1)$

$O(\log n)$

$O(n)$

$O(n^2)$

17.

Phát biểu nào sau đây đúng về mảng một chiều?

Là dãy các phần tử có kiểu dữ liệu khác nhau.

Là dãy các phần tử có cùng kiểu.

Là dãy các cặp khóa–giá trị.

Là dãy các hàm.

18.

Phương án nào dưới đây là cách viết khai báo thư viện mảng trong Python?

import array

import arrays

from python import array

include array

19.

Cách nào dưới đây đúng để tạo mảng a lưu trữ các số nguyên?

a = array.array('i', [1, 2, 3])

a = array('i', [1, 2, 3])

a = [1, 2, 3]

a = (1, 2, 3)

20.

Để thêm phần tử x vào cuối mảng a, ta dùng lệnh nào dưới đây?

a.append(x)

a.push(x)

a.add(x)

a.insert(x)

21.

Để gọi đến phần tử đầu tiên trong mảng a, ta dùng lệnh nào dưới đây?

a[0]

a[1]

a.first()

a(0)

22.

Cho mảng a gồm các phần tử [3, 4, 5]. Khi đó len(a) bằng giá trị nào bên dưới?

23.

Để xóa phần tử cuối mảng a, ta dùng lệnh nào dưới đây?

a.pop()

a.removeLast()

a.delete()

a.cut()

24.

Để thêm phần tử x vào đầu mảng a, ta dùng lệnh nào dưới đây?

a.insert(0, x)

a.append(0, x)

a.prepend(x)

a.addFirst(x)

25.

Sau khi thực hiện đoạn chương trình dưới đây thì kết quả hiển thị trên màn hình là: myArray = array.array('i', [1, 2, 3]) myArray.append(4) print(myArray)

array('i', [1, 2, 3])

array('i', [1, 2, 3, 4])

array('i', [4, 1, 2, 3])

Error

26.

Lệnh nào dưới đây dùng để tìm vị trí xuất hiện đầu tiên của x trong mảng a?

index(x)

find(x)

locate(x)

search(x)

27.

Sau khi thực hiện đoạn chương trình dưới đây thì kết quả hiển thị trên màn hình là: myArray = array.array('i', [1, 2, 3, 4, 5]) print(myArray[1:4])

array('i', [1, 2, 3])

array('i', [2, 3, 4])

array('i', [2, 3, 5])

array('i', [1, 2, 3, 4])

28.

Để ghép các mảng thành một mảng, ta dùng dấu nào dưới đây?

29.

Thuật toán tìm kiếm nhị phân được sử dụng để tìm một phần tử trong một danh sách dữ liệu có đặc điểm nào trong các phương án dưới đây?

Chưa được sắp xếp.

Có ít phần tử.

Đã được sắp xếp với số lượng phần tử nhiều.

Chưa được sắp xếp với số lượng phần tử ít.

30.

Phát biểu nào bên dưới thể hiện điều kiện cần thiết phải đảm bảo về danh sách dữ liệu khi áp dụng thuật toán tìm kiếm nhị phân?

Có kích thước nhỏ.

Có kích thước lớn.

Được sắp xếp.

Không cần sắp xếp.

31.

Phương án nào bên dưới mô tả hoạt động của thuật toán tìm kiếm nhị phân?

Bắt đầu từ phần tử đầu tiên, lần lượt so sánh các phần tử trong danh sách với giá trị cần tìm cho đến khi tìm được phần tử có giá trị bằng với giá trị cần tìm.

Bắt đầu từ phần tử bất kì, lần lượt so sánh các phần tử trong danh sách với giá trị cần tìm cho đến khi tìm được phần tử có giá trị bằng với giá trị cần tìm.

Chia danh sách dữ liệu làm đôi và thu hẹp phạm vi tìm kiếm cho đến khi tìm được phần tử có giá trị bằng với giá trị cần tìm.

Chia danh sách dữ liệu làm ba và thu hẹp phạm vi tìm kiếm cho đến khi tìm được phần tử có giá trị bằng với giá trị cần tìm.

32.

Thuật toán tìm kiếm nhị phân có ưu điểm gì so với tìm kiếm tuần tự?

Đơn giản hơn trong lập trình.

Có thể áp dụng cho mọi danh sách.

Tốc độ nhanh hơn khi danh sách đã sắp xếp.

Không cần phải sắp xếp danh sách trước khi tìm.

33.

Trong thuật toán tìm kiếm nhị phân, điều kiện nào quyết định quá trình tìm kiếm tiếp theo?

Vị trí giữa của danh sách so sánh với giá trị cần tìm.

Giá trị đầu tiên của danh sách.

Giá trị cuối cùng của danh sách.

Tổng số phần tử trong danh sách.

34.

Với dữ liệu đầu vào là danh sách có 32 phần tử, thuật toán tìm kiếm nhị phân thực hiện tối đa bao nhiêu lần thao tác so sánh?

35.

Cho danh sách d=[12, 13, 35, 78, 56] và giá trị cần tìm là 78. Sử dụng thuật toán tìm kiếm nhị phân trên danh sách d thì cần bao nhiêu lần lặp cho đến khi giá trị cần tìm được tìm thấy?

36.

Thuật toán tìm kiếm nhị phân trên danh sách d=[3, 5, 7, 10, 23] thực hiện bao nhiêu phép so sánh để tìm được số 7?

0–1

3–4

2–3

5–6

37.

Giá trị phần tử ở giữa trong lần duyệt thứ nhất và thứ hai khi thực hiện thuật toán tìm kiếm nhị phân trên danh sách d=[23, 45, 67, 89, 90, 96] với giá trị cần tìm là 90 là gì?

67 và 89

67 và 96

67 và 90

Hai giá trị khác

38.

Phương án nào dưới đây nêu hoạt động của thuật toán tìm kiếm nhị phân?

Sắp xếp các phần tử trong danh sách, kiểm tra lần lượt từng phần tử của danh sách với giá trị cần tìm

Các phần tử trong danh sách không cần phải sắp xếp, so sánh giá trị cần tìm với phần tử ở giữa, thu hẹp phạm vi tìm kiếm và lặp lại

Sắp xếp các phần tử trong danh sách, so sánh giá trị cần tìm với phần tử ở giữa, thu hẹp phạm vi tìm kiếm và lặp lại

Các phần tử trong danh sách không cần phải sắp xếp, kiểm tra lần lượt từng phần tử của danh sách với giá trị cần tìm

39.

Thuật toán tìm tuần tự trên danh sách d=[1, 4, 8, 7, 10, 28] thực hiện bao nhiêu phép so sánh để tìm được số 7?

40.

Trường hợp nào dưới đây nên sử dụng thuật toán tìm kiếm tuần tự trên một danh sách dữ liệu?

Danh sách có ít phần tử

Danh sách không có thứ tự

Sử dụng trên mọi danh sách dữ liệu

Danh sách không có thứ tự và số lượng phần tử nhỏ hoặc trung bình

41.

Bất điều nào bên dưới là nhược điểm của thuật toán tìm kiếm tuần tự?

Tốn nhiều bộ nhớ

Độ phức tạp thời gian lớn hơn so với các thuật toán tìm kiếm khác

Thuật toán khó hiểu

Thuật toán khó cài đặt

42.

Trong tìm kiếm tuần tự, khi nào cần nhiều bước nhất để tìm ra kết quả?

Khi phần tử cần tìm ở giữa danh sách

Khi phần tử cần tìm là phần tử cuối cùng

Khi phần tử cần tìm không có trong danh sách

Khi phần tử cần tìm là phần tử đầu tiên

43.

Mục đích của vòng lặp bên trong trong thuật toán sắp xếp nổi bọt là gì?

Tìm phần tử lớn nhất và đưa nó về đúng vị trí

Tìm phần tử nhỏ nhất và đưa nó về đúng vị trí

So sánh và hoán đổi các phần tử liền kề nếu chúng không đúng thứ tự

Chia mảng thành các phần nhỏ hơn để sắp xếp

44.

Khi nào chúng ta sử dụng thuật toán sắp xếp nổi bọt?

Khi số lượng phần tử trong danh sách rất lớn

Khi cần sắp xếp một danh sách ngẫu nhiên có số lượng nhỏ hoặc trung bình

Khi không yêu cầu hiệu suất cao

Khi danh sách đã được sắp xếp hoàn toàn

45.

Xét đoạn mã Python kiểm tra số nguyên tố: def is_prime(n): if n < 2: return False for i in range(2, n): if n % i == 0: return False return True Chọn tất cả mệnh đề đúng về đoạn mã trên.

Hàm is_prime(n) trả về True nếu n là số nguyên tố

Hàm is_prime(n) trên đã tối ưu

Vòng lặp for dùng để kiểm tra xem n có ước nào khác 1 và chính nó hay không

Có thể cải tiến thuật toán bằng cách chỉ kiểm tra các giá trị i đến $\sqrt{n}$

46.

Xét đoạn mã Python tính UCLN: def gcd(a, b): while b != 0: a, b = b, a % b return a Chọn tất cả mệnh đề đúng về đoạn mã trên.

Đoạn mã trên cài đặt thuật toán Euclid

Biến a luôn chứa UCLN của hai số tại mọi thời điểm

Phép toán % là phép chia lấy dư

Thuật toán dừng khi b bằng 0

47.

Xét đoạn mã Python sau: import math print(math.comb(5, 2)) Chọn tất cả mệnh đề đúng về đoạn mã trên.

Đoạn mã trên tính tổ hợp $C(5,2)$

Kết quả in ra là 10

Tổ hợp có xét đến thứ tự các phần tử

Hàm comb thuộc thư viện math

48.

Xét đoạn mã Python sau cho tìm kiếm tuyến tính: a = [1, 3, 5, 7, 9] x = 7 found = False for i in range(len(a)): if a[i] == x: found = True break Chọn tất cả mệnh đề đúng về đoạn mã trên.

Chương trình trên cài đặt thuật toán tìm kiếm tuyến tính (Linear Search)

Chương trình so sánh x với từng phần tử của danh sách theo thứ tự chỉ số tăng dần

Chương trình yêu cầu danh sách a phải được sắp xếp trước

Khi x nằm ở vị trí đầu danh sách, vòng lặp chỉ thực hiện một lần

49.

Cho danh sách a ban đầu rỗng. Xem đoạn chương trình Python: a = [] a.append(10) a.append(20) Chọn tất cả các mệnh đề đúng về đoạn chương trình và phương thức append.

a là một danh sách (kiểu list) trong Python

Phương thức append thêm một phần tử vào cuối danh sách

Thao tác append có độ phức tạp thời gian trung bình là O(1)

Danh sách trong Python có kích thước cố định ngay từ khi khởi tạo

50.

Xem đoạn chương trình Python thực hiện tìm kiếm nhị phân trên danh sách a có n phần tử: # Nhập số phần tử n = int(input()) # Nhập danh sách đã sắp xếp a = list(map(int, input().split())) # Nhập giá trị cần tìm x = int(input()) left = 0 right = n - 1 found = False while left <= right: mid = (left + right) // 2 if a[mid] == x: found = True break elif a[mid] < x: left = mid + 1 else: right = mid - 1 if found: print("FOUND") else: print("NOT FOUND") Chọn tất cả các mệnh đề đúng về thuật toán trong chương trình.

Thuật toán chỉ hoạt động đúng khi danh sách a đã được sắp xếp

Mỗi lần lặp, thuật toán loại bỏ một nửa không gian tìm kiếm

Độ phức tạp thời gian của thuật toán là O(n)

Khi x không tồn tại trong danh sách, vòng lặp kết thúc khi left > right

51.

Xem đoạn chương trình Python sắp xếp nổi bọt (Bubble Sort) cho danh sách a có n phần tử: # Nhập số phần tử n = int(input()) # Nhập danh sách các phần tử a = list(map(int, input().split())) for i in range(n - 1): for j in range(n - i - 1): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] # In kết quả for x in a: print(x, end=" ") Chọn tất cả các mệnh đề đúng về thuật toán trong chương trình.

Thuật toán trong chương trình so sánh và hoán đổi các cặp phần tử kề nhau

Độ phức tạp thời gian trung bình của thuật toán là O(nlogn)

Sau mỗi lần lặp của vòng for bên ngoài, phần tử lớn nhất chưa được sắp xếp sẽ được đưa về cuối dãy

Thuật toán sắp xếp được cài đặt là thuật toán sắp xếp tại chỗ

52.

Cho một dãy số nguyên gồm n phần tử được lưu trong danh sách a. Xem đoạn chương trình Python sắp xếp tăng dần bằng thuật toán sắp xếp chèn (Insertion Sort): # Nhập số phần tử n = int(input()) # Nhập danh sách các phần tử a = list(map(int, input().split())) for i in range(1, n): key = a[i] j = i - 1 while j >= 0 and a[j] > key: a[j + 1] = a[j] j -= 1 a[j + 1] = key # In kết quả for x in a: print(x, end=" ") Chọn tất cả các mệnh đề đúng về thuật toán trong chương trình.

Sau mỗi lần lặp của vòng for bên ngoài, đoạn a[0..i] đã được sắp xếp tăng dần

Thuật toán chèn từng phần tử vào vị trí thích hợp trong đoạn đã sắp xếp

Độ phức tạp thời gian trung bình của thuật toán là O(nlogn)

Thuật toán trong chương trình là thuật toán sắp xếp tại chỗ, không sử dụng mảng phụ

Reset

Độ phức tạp thời gian của thuật toán

Total questions: 52

Worksheet time: 26mins

Similar Resources on Wayground