Free Printable CHƯƠNG 1. GIỚI THIỆU - 1.1. Khái niệm thuật toán

1.

Điền vào chỗ trống: Thuật toán là tập các chỉ dẫn (__________) có thứ tự, không nhập nhằng để giải bài toán.

a)

Instructions

b)

Variables

c)

Loops

d)

Functions

2.

Tại mỗi bước của thuật toán phải rõ ràng, không được nhập nhằng.

a)

Đúng

b)

Sai

3.

Thuật toán có thể biểu diễn bằng nhiều cách khác nhau.

a)

Đúng

b)

Sai

4.

Điền vào chỗ trống: Thuật toán đầu tiên là thuật toán ________ dùng để tìm ước số chung lớn nhất.

a)

Euclid

b)

Newton

c)

Dijkstra

d)

Fibonacci

5.

Điền vào chỗ trống: Trong thuật toán Euclid, nếu n = 0, ước số chung lớn là ________.

a)

m

b)

0

c)

1

d)

n

6.

Điền vào chỗ trống: Trong thuật toán Euclid, bước 2 là: r = m chia dư cho ________.

a)

n

b)

m

c)

r

d)

k

7.

Điền vào chỗ trống: Trong thuật toán Euclid, bước 3 là: m ← n và n ← ________, chuyển đến bước 1.

a)

r

b)

m+n

c)

m-n

d)

m*n

8.

Dựa vào sơ đồ khối mô tả thuật toán Euclid tìm ước số chung lớn nhất, ký hiệu hình elip dùng để biểu diễn điều gì?

a)

Kiểm tra điều kiện

b)

Điểm bắt đầu hoặc kết thúc thuật toán

c)

Mô tả dữ liệu đầu vào/đầu ra

d)

Thực hiện 1 thao tác, 1 bước của thuật toán

9.

Điền vào chỗ trống: Trong thuật toán Euclid, khi n = 0 thì giá trị trả về là _____

a)

m

b)

n

c)

0

d)

1

10.

Theo thuật toán Euclid, bước nào sau đây được lặp lại cho đến khi n = 0?

a)

A. return m

b)

B. r ← m mod n; m ← n; n ← r

c)

C. Đầu vào: 2 số nguyên m, n

d)

D. Kiểm tra điều kiện n = 0

11.

Bước đầu tiên của thuật toán tìm ước số chung lớn nhất của hai số m, n là gì?

a)

Đặt t = min{m, n}.

b)

Đặt t = max{m, n}.

c)

Đặt t = m + n.

d)

Đặt t = m - n.

12.

Trong thuật toán tìm ước số chung lớn nhất, điều kiện nào khiến thuật toán chuyển sang bước giảm t đi 1?

a)

Khi m chia cho t hoặc n chia cho t có dư khác 0.

b)

Khi m và n đều là số nguyên tố.

c)

Khi t lớn hơn m hoặc n.

d)

Khi m hoặc n bằng 0.

13.

Thuật toán tìm ước số chung lớn nhất của hai số m, n sẽ trả về giá trị nào nếu m chia hết cho t và n chia hết cho t?

a)

Trả về giá trị t.

b)

Trả về giá trị m.

c)

Trả về giá trị n.

d)

Trả về giá trị 1.

14.

Sơ đồ khối trong Hình 1-2 mô tả thuật toán nào?

a)

Thuật toán tìm ước số chung lớn nhất của hai số.

b)

Thuật toán sắp xếp nổi bọt.

c)

Thuật toán tìm kiếm nhị phân.

d)

Thuật toán tính tổng dãy số.

15.

Bước 1 của thuật toán tìm ước số chung lớn nhất bằng phân tích thừa số nguyên tố là gì?

a)

Phân tích m thành tích các thừa số nguyên tố.

b)

Lấy tổng của m và n.

c)

Chia m cho n.

d)

Tìm số nguyên tố lớn nhất nhỏ hơn m.

16.

Theo ví dụ minh họa, ước số chung lớn nhất của 60 và 24 là bao nhiêu?

a)

6

b)

8

c)

12

d)

24

17.

Thuật toán thứ 3 tìm ước số chung lớn nhất của hai số m, n sử dụng phương pháp nào?

a)

Phân tích hai số thành các thừa số nguyên tố và tìm tích các thừa số chung.

b)

Chia hai số cho nhau liên tiếp cho đến khi được số dư bằng 0.

c)

Cộng hai số lại rồi chia cho 2.

d)

Lấy số lớn trừ số nhỏ cho đến khi hai số bằng nhau.

18.

Ý nghĩa của biến 'us' trong thuật toán gcd3(m, n) là gì?

a)

Biến lưu kết quả ước số chung lớn nhất.

b)

Biến đếm số lần lặp của thuật toán.

c)

Biến lưu giá trị trung gian trong quá trình tính toán.

d)

Biến kiểm tra điều kiện dừng của thuật toán.

19.

Hình 1-3 mô tả thuật toán nào?

a)

Thuật toán tìm bội chung nhỏ nhất

b)

Thuật toán tìm ước số chung lớn nhất

c)

Thuật toán sắp xếp dãy số

d)

Thuật toán tính tổng hai số

20.

Trong sơ đồ khối, bước đầu tiên là gì?

a)

Phân tích m thành tích các thừa số nguyên tố

b)

Đầu vào: 2 số nguyên m, n

c)

return us

d)

us ← 1; i ← 1; j ← 1

21.

Điền vào chỗ trống: Trong sơ đồ khối, nếu p_i = q_j thì _________.

a)

us ← us * p_i; i ← i + 1; j ← j + 1

b)

us ← us + p_i; i ← i + 1; j ← j + 1

c)

us ← us * p_i; i ← i - 1; j ← j + 1

d)

us ← us * p_i; i ← i + 1; j ← j - 1

22.

Mục đích của thuật toán trong Hình 1-3 là:

a)

Tìm kiếm phần tử lớn nhất trong một dãy số.

b)

Sắp xếp các phần tử theo thứ tự tăng dần.

c)

Tính tổng các phần tử trong mảng.

d)

Tìm kiếm phần tử nhỏ nhất trong một dãy số.

23.

Dựa vào Hình 1-4, bước đầu tiên trong quy trình phân tích và thiết kế thuật toán là gì?

a)

Đọc hiểu bài toán.

b)

Viết mã giả cho thuật toán.

c)

Kiểm thử thuật toán.

d)

Tối ưu hóa thuật toán.

24.

Theo Hình 1-4, sau khi thiết kế thuật toán, bước tiếp theo là gì?

a)

Chứng minh tính đúng đắn.

b)

Viết mã giả cho thuật toán.

c)

Kiểm tra dữ liệu đầu vào.

d)

Tối ưu hóa thuật toán.

25.

Việc đọc hiểu bài toán trước khi thiết kế thuật toán giúp đảm bảo điều gì?

a)

Giúp xác định đúng yêu cầu và hướng giải quyết phù hợp

b)

Giúp tiết kiệm thời gian lập trình mà không cần hiểu bài toán

c)

Giúp thuật toán chạy nhanh hơn mà không cần kiểm tra đầu vào

d)

Giúp bỏ qua các bước kiểm thử thuật toán

26.

Khi nào nên chọn thuật toán xấp xỉ thay vì thuật toán chính xác?

a)

Khi bài toán quá phức tạp hoặc không thể giải được bằng thuật toán chính xác.

b)

Khi luôn có thể tìm được lời giải tối ưu một cách dễ dàng.

c)

Khi thuật toán chính xác nhanh hơn thuật toán xấp xỉ.

d)

Khi không cần quan tâm đến thời gian tính toán.

27.

Hình 1-4 mô tả quy trình phân tích và thiết kế thuật toán gồm bao nhiêu bước?

a)

3 bước

b)

4 bước

c)

5 bước

d)

6 bước

28.

Kĩ thuật thiết kế thuật toán là phương pháp chung để giải bài toán được áp dụng cho nhiều bài toán. Đúng hay Sai?

a)

Đúng

b)

Sai

29.

Sau khi thiết kế xong thuật toán, cần phải mô tả lại thuật toán này bằng ngôn ngữ gì?

a)

Ngôn ngữ tự nhiên hoặc ngôn ngữ lập trình giả mã.

b)

Ngôn ngữ máy tính nhị phân.

c)

Ngôn ngữ lập trình bậc thấp.

d)

Ngôn ngữ hình ảnh hoặc biểu đồ.

30.

Một kĩ thuật chung để chứng minh tính đúng đắn của thuật toán là sử dụng phương pháp nào?

a)

Phương pháp quy nạp toán học.

b)

Phương pháp thử và sai.

c)

Phương pháp loại trừ.

d)

Phương pháp trực giác.

31.

Hai tiêu chí để đánh giá hiệu quả của thuật toán là gì?

a)

Độ lớn đầu ra (tiêu chí về không gian) và thời gian.

b)

Số lượng biến sử dụng và độ phức tạp của thuật toán.

c)

Số lượng vòng lặp và số lượng hàm gọi.

d)

Tốc độ xử lý và số lượng dòng lệnh.

32.

Hiệu quả thời gian (còn gọi là độ phức tạp về thời gian) là ______ thực hiện của thuật toán từ khi nhận dữ liệu đầu vào cho đến khi có dữ liệu đầu ra.

a)

thời gian

b)

bộ nhớ

c)

dữ liệu

d)

kết quả

33.

Điền vào chỗ trống: Hiệu quả không gian (còn gọi là độ phức tạp về không gian) là ______ đơn vị bộ nhớ sử dụng cho thuật toán kể cả dữ liệu vào/ra.

a)

số lượng

b)

chất lượng

c)

tốc độ

d)

kích thước

34.

Kích thước đầu vào của một thuật toán là một hàm số 1 tham số n chỉ kích thước ______.

a)

đầu vào

b)

kết quả

c)

bộ nhớ

d)

thời gian

35.

Điền vào chỗ trống: Trong bài toán kiểm tra số nguyên dương n có phải là nguyên tố hay không, kích thước đầu vào chính là số ______ cần kiểm tra.

a)

n

b)

0

c)

1

d)

2

36.

Đơn vị đo thời gian chạy của một chương trình thực hiện theo thuật toán có thể là gì?

a)

giây, phần nghìn giây

b)

mét, kilômét

c)

lít, mililít

d)

kg, gam

37.

Phép toán cơ bản trong phân tích thuật toán là gì?

a)

Những phép toán góp phần lớn trong tổng thời gian chạy của thuật toán.

b)

Những phép toán chỉ xuất hiện một lần trong thuật toán.

c)

Những phép toán không ảnh hưởng đến thời gian chạy của thuật toán.

d)

Những phép toán chỉ dùng để kiểm tra điều kiện.

38.

Cho thuật toán SequentialSearch(A[0..n-1], K) dưới đây: ALGORITHM SequentialSearch(A[0..n - 1], K) i ← 0 while (i < n) and (A[i] ≠ K) do i ← i + 1 if (i < n) then return i

a)

Tìm kiếm một phần tử K trong mảng A.

b)

Sắp xếp mảng A theo thứ tự tăng dần.

c)

Tính tổng các phần tử trong mảng A.

d)

Tìm phần tử lớn nhất trong mảng A.

39.

Một hàm t(n) được gọi là thuộc lớp hàm O(g(n)), kí hiệu t(n) ∈ O(g(n)), nếu t(n) bị chặn trên bởi hằng số nhân với g(n) tức là tồn tại số c và n₀ sao cho: t(n) ≤ c.g(n) ∀ n ≥ n₀. Hàm t(n) được thể hiện qua Hình 2-1. Chọn đáp án đúng để điền vào chỗ trống: t(n) ≤ ___.

a)

c.g(n)

b)

g(n)/c

c)

c + g(n)

d)

g(n) - c

40.

Cho ví dụ: Chứng minh hàm t(n) = 100n + 5 ∈ O(n²). Số c và n₀ tương ứng trong trường hợp này là bao nhiêu?

a)

c = 101, n₀ = 5

b)

c = 5, n₀ = 100

c)

c = 100, n₀ = 1

d)

c = 105, n₀ = 2

41.

Điền vào chỗ trống: t(n) = 1/2 n(n-1) ∈ O(___).

a)

n²

b)

n

c)

log n

d)

$2^n$

42.

Kí hiệu O có tính chất quan trọng sau: t₁(n) ∈ O(g₁(n)) và t₂(n) ∈ O(g₂(n)), khi đó t₁(n) + t₂(n) ∈ O(___).

a)

max{g₁(n), g₂(n)}

b)

g₁(n) + g₂(n)

c)

min{g₁(n), g₂(n)}

d)

g₁(n) * g₂(n)

43.

Điền vào chỗ trống: $\sum_{i=1}^u c a_i = c \sum_{i=1}^u a_i = \underline{?}$

a)

c $\sum_{i=1}^u a_i$

b)

$\sum_{i=1}^u (c + a_i)$

c)

c + $\sum_{i=1}^u a_i$

d)

$\sum_{i=1}^u c \cdot a_i$

44.

Điền vào chỗ trống: $\sum_{i=1}^u (a_i \pm b_i) = \sum_{i=1}^u a_i \pm \sum_{i=1}^u b_i = \underline{?}$

a)

$\sum_{i=1}^u a_i \pm \sum_{i=1}^u b_i$

b)

$\sum_{i=1}^u (a_i b_i)$

c)

$\sum_{i=1}^u a_i b_i$

d)

$\sum_{i=1}^u (a_i + b_1)$

45.

Điền vào chỗ trống: $\sum_{i=l}^u 1 = u - l + 1 = \underline{?}$

a)

u - l + 1

b)

u + l + 1

c)

u - l - 1

d)

u + l - 1

46.

Điền vào chỗ trống: $\sum_{i=1}^n i = 1 + 2 + ... + n = \frac{n(n+1)}{2} = \underline{?}$

a)

$\frac{n(n+1)}{2}$

b)

$\frac{n(n-1)}{2}$

c)

$n^2$

d)

2n

47.

Điền vào chỗ trống: $\sum_{i=1}^n i^2 = 1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6} = \underline{?}$

a)

$\frac{n(n+1)(2n+1)}{6}$

b)

$\frac{n(n+1)}{2}$

c)

$\frac{n(n+1)(n+2)}{6}$

d)

$\frac{n^2(n+1)^2}{4}$

48.

Điền vào chỗ trống: $\sum_{i=0}^n a^i = a^0 + a^1 + ... + a^n = \frac{a^{n+1}-1}{a-1}, a \neq 1; \sum_{i=0}^n 2^i = 2^{n+1} - 1 = \underline{?}$

a)

$2^{n+1} - 1$

b)

$2^n - 1$

c)

$2^{n+1} + 1$

d)

$2^n + 1$

49.

Điền vào chỗ trống: $\sum_{i=0}^n i 2^i = 1 \times 2^0 + 2 \times 2^1 + ... + n \times 2^n = (n-1) \times 2^{n+1} + 2 = \underline{?}$

a)

$(n-1) \times 2^{n+1} + 2$

b)

$n \times 2^{n+1} - 1$

c)

$(n+1) \times 2^n + 2$

d)

$n^2 \times 2^n$

50.

Điền vào chỗ trống: $\sum_{i=1}^n \frac{1}{i} = 1 + \frac{1}{2} + ... + \frac{1}{n} \approx \ln n + \gamma, \text{ với } \gamma \approx 0.5772 = \underline{?}$

a)

\ln n + \gamma, với \gamma \approx 0.5772

b)

\ln n - \gamma, với \gamma \approx 1.4142

c)

n^2 + $\gamma$ , với $\gamma \approx 3.1416$

d)

\ln n + \gamma, với \gamma \approx 2.7183

51.

Điền vào chỗ trống: $\sum_{i=1}^n \log i \approx$ _________.

a)

$n \log n$

b)

$n^2$

c)

$\log n!$

d)

n

52.

Điền vào chỗ trống: $\sum_{i=1}^n i^k = 1^k + 2^k + ... + n^k \approx \frac{1}{k+1} n^{k+1}$ . Giá trị còn thiếu trong công thức là _________.

a)

$\frac{1}{k+1} n^{k+1}$

b)

$\frac{1}{k} n^{k}$

c)

$k n^{k+1}$

d)

$n^{k+1}$

53.

Thuật toán MaxElement nhận đầu vào là gì?

a)

Một số nguyên

b)

Một mảng số nguyên

c)

Một danh sách ký tự

d)

Một chuỗi

54.

Đầu ra của thuật toán UniqueElements là gì?

a)

Giá trị lớn nhất trong mảng

b)

Trả về 'true' nếu tất cả các phần tử là phân biệt, ngược lại 'false'

c)

Tổng các phần tử trong mảng

d)

Số lượng phần tử trùng nhau

55.

Độ phức tạp của thuật toán MaxElement là bao nhiêu?

a)

O(n)

b)

O(log n)

c)

$O(n^2)$

d)

O(1)

56.

Định nghĩa phép nhân hai ma trận vuông A và B cấp n x n là gì?

a)

$C_{ij} = \text{sum}_{k=0}^{n-1} A_{ik} * B_{kj}$

b)

$C_{ij} = \text{sum}_{k=0}^{n-1} A_{ik} + B_{kj}$

c)

C_{ij} = $\text{sum}_{k=0}^{n-1} A_{ik} - B_{kj}$

d)

$C_{ij} = \text{sum}_{k=0}^{n-1} A_{ik} / B_{kj}$

57.

Độ phức tạp của thuật toán nhân hai ma trận vuông cấp n x n là gì?

a)

$O(n^2)$

b)

$O(n^3)$

c)

O(n)

d)

$O(2^n)$

58.

Thuật toán Binary(n) dùng để làm gì?

a)

Tính tổng các chữ số của n

b)

Tính độ dài chuỗi nhị phân biểu diễn số nguyên n

c)

Tính tổng các ước của n

d)

Tính số lượng số nguyên tố nhỏ hơn n

59.

Độ phức tạp của thuật toán Binary(n) là gì?

a)

O(log n)

b)

O(n)

c)

$O(n^2)$

d)

O(1)

60.

Điền vào chỗ trống: Độ phức tạp của thuật toán chia đôi liên tục là ________.

a)

O(log n)

b)

O(n)

c)

$O(n^2)$

d)

O(1)

61.

Điền vào chỗ trống: Công thức đệ quy tính giai thừa F(n) là ________.

a)

F(n) = F(n-1) * n

b)

F(n) = F(n+1) * n

c)

F(n) = n + F(n-1)

d)

F(n) = n * F(n+1)

62.

Phép toán cơ bản trong thuật toán tính giai thừa F(n) là gì?

a)

Phép cộng

b)

Phép chia

c)

Phép nhân

d)

Phép trừ

63.

Điền vào chỗ trống: Đầu vào của thuật toán tính giai thừa F(n) là ________.

a)

Số nguyên dương n

b)

Số thực n

c)

Số nguyên âm n

d)

Số nguyên tố n

64.

Bài toán chuyển tháp Hà Nội yêu cầu chuyển n tháp từ vị trí A đến vị trí B, mỗi lần chỉ được đặt tháp nhỏ lên tháp lớn và trong quá trình chuyển lấy vị trí C làm trung gian.

a)

Đúng

b)

Sai

65.

Điền vào chỗ trống: Độ phức tạp của thuật toán chuyển tháp Hà Nội là O(___).

a)

$2^n$

b)

$n^2$

c)

n!

d)

n log n

66.

Công thức đệ quy để tính số phép di chuyển t(n) trong bài toán tháp Hà Nội là gì?

a)

t(n) = t(n-1) + 1 + t(n-1)

b)

t(n) = t(n-1) + n

c)

t(n) = 2*t(n-1) - 1

d)

t(n) = t(n-1) * 2

67.

Thuật toán BinRec(n) được sử dụng để làm gì?

a)

Chia nhỏ một số thành các lũy thừa của 2

b)

Sắp xếp một mảng theo thứ tự tăng dần

c)

Tìm kiếm nhị phân trong một mảng đã sắp xếp

d)

Tính tổng các số nguyên tố nhỏ hơn n

68.

Điền vào chỗ trống: Công thức đệ quy để đếm số bit nhị phân là t(n) = t(___) + 1 với t(1) = 0.

a)

n/2

b)

n-1

c)

2n

d)

n+1

69.

Cho các bài toán sau, chỉ ra: (i) kích thước dữ liệu đầu vào, (ii) phép toán cơ bản, (iii) phép toán cơ bản có thay đổi hay không nếu thay đổi dữ liệu đầu vào nhưng giữ nguyên kích thước. 1. Tính tổng n số nguyên.

a)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép cộng; (iii) Không thay đổi.

b)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép nhân; (iii) Có thay đổi.

c)

(i) Kích thước dữ liệu đầu vào: 1; (ii) Phép toán cơ bản: phép cộng; (iii) Có thay đổi.

d)

(i) Kích thước dữ liệu đầu vào: $n^2$ ; (ii) Phép toán cơ bản: $phép trừ$ ; (iii) Không thay đổi.

70.

Cho các bài toán sau, chỉ ra: (i) kích thước dữ liệu đầu vào, (ii) phép toán cơ bản, (iii) phép toán cơ bản có thay đổi hay không nếu thay đổi dữ liệu đầu vào nhưng giữ nguyên kích thước. 2. Tính n!.

a)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép nhân; (iii) Không thay đổi.

b)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép cộng; (iii) Có thay đổi.

c)

(i) Kích thước dữ liệu đầu vào: $n^2$ ; (ii) Phép toán cơ bản: $phép chia$ ; (iii) Không thay đổi.

d)

(i) Kích thước dữ liệu đầu vào: log n; (ii) Phép toán cơ bản: phép trừ; (iii) Có thay đổi.

71.

Cho các bài toán sau, chỉ ra: (i) kích thước dữ liệu đầu vào, (ii) phép toán cơ bản, (iii) phép toán cơ bản có thay đổi hay không nếu thay đổi dữ liệu đầu vào nhưng giữ nguyên kích thước. 3. Tìm số lớn nhất trong dãy số.

a)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép so sánh; (iii) Không thay đổi.

b)

(i) Kích thước dữ liệu đầu vào: 1; (ii) Phép toán cơ bản: phép cộng; (iii) Có thay đổi.

c)

(i) Kích thước dữ liệu đầu vào: $n^2$ ; (ii) Phép toán cơ bản: $phép nhân$ ; (iii) Không thay đổi.

d)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép chia; (iii) Có thay đổi.

72.

Cho các bài toán sau, chỉ ra: (i) kích thước dữ liệu đầu vào, (ii) phép toán cơ bản, (iii) phép toán cơ bản có thay đổi hay không nếu thay đổi dữ liệu đầu vào nhưng giữ nguyên kích thước. 4. Thuật toán Euclid tìm ước số chung lớn nhất của a, b.

a)

(i) Kích thước dữ liệu đầu vào: số chữ số của a và b; (ii) Phép toán cơ bản: phép chia lấy dư; (iii) Có thể thay đổi tùy thuộc vào giá trị của a và b.

b)

(i) Kích thước dữ liệu đầu vào: giá trị tuyệt đối của a và b; (ii) Phép toán cơ bản: phép cộng; (iii) Không thay đổi khi thay đổi dữ liệu đầu vào.

c)

(i) Kích thước dữ liệu đầu vào: tổng của a và b; (ii) Phép toán cơ bản: phép trừ; (iii) Luôn thay đổi khi thay đổi dữ liệu đầu vào.

d)

(i) Kích thước dữ liệu đầu vào: số lượng ước của a và b; (ii) Phép toán cơ bản: phép nhân; (iii) Không thay đổi khi thay đổi dữ liệu đầu vào.

73.

Cho các bài toán sau, chỉ ra: (i) kích thước dữ liệu đầu vào, (ii) phép toán cơ bản, (iii) phép toán cơ bản có thay đổi hay không nếu thay đổi dữ liệu đầu vào nhưng giữ nguyên kích thước. Nhân hai số nguyên có n chữ số.

a)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép nhân; (iii) Không thay đổi.

b)

(i) Kích thước dữ liệu đầu vào: 2n; (ii) Phép toán cơ bản: phép cộng; (iii) Có thay đổi.

c)

(i) Kích thước dữ liệu đầu vào: $n^2$ ; (ii) Phép toán cơ bản: $phép chia$ ; (iii) Không thay đổi.

d)

(i) Kích thước dữ liệu đầu vào: n; (ii) Phép toán cơ bản: phép trừ; (iii) Có thay đổi.

74.

Xét bài toán cộng hai ma trận cấp m × n. đánh giá độ phức tạp của thuật toán trên.

a)

Phép toán cơ bản là phép cộng. Độ phức tạp của thuật toán là O(mn).

b)

Phép toán cơ bản là phép nhân. Độ phức tạp của thuật toán là O(m+n).

c)

Phép toán cơ bản là phép trừ. Độ phức tạp của thuật toán là O(m^2n^2).

d)

Phép toán cơ bản là phép chia. Độ phức tạp của thuật toán là O(n).

75.

Bài 4. Các hàm sau thuộc lớp hàm nào?

a)

Hàm bậc nhất

b)

Hàm bậc hai

c)

Hàm hằng

d)

Hàm lũy thừa

76.

Hàm số √10n^2 + 7n + 3 thuộc lớp hàm nào?

a)

$O(n^2)$

b)

O(n)

c)

O(1)

d)

$O(n^3)$

77.

Hàm 2n.log(n + 2)^2 + (n + 2)^2log(n / 2) thuộc lớp hàm nào?

a)

$O(n^2 log n)$

b)

O(n log n)

c)

$O(n^3)$

d)

$O(n^2)$

78.

Hàm $2^n + 1$ + $3^n$ - 1 thuộc lớp hàm nào?

a)

Lớp hàm lũy thừa

b)

Lớp hàm đa thức

c)

Lớp hàm logarit

d)

Lớp hàm hằng số

79.

Hàm ⌊log2 n⌋ thuộc lớp hàm nào?

a)

Lớp hàm logarit

b)

Lớp hàm đa thức

c)

Lớp hàm hằng số

d)

Lớp hàm mũ

80.

Chọn khẳng định đúng về đa thức bậc k, p(n) = $a_k n^k + a_{k-1} n^{k-1} + ... + a_0$ , với a_k > 0:

a)

p(n) thuộc lớp $O(n^k)$

b)

p(n) thuộc lớp $O(n^{k-1})$

c)

p(n) thuộc lớp $O(n^{k+1})$

d)

p(n) thuộc lớp O(1)

81.

Bài 6. Tính các tổng sau đây: a. 1 + 3 + 5 + ... + 99

a)

2500

b)

2000

c)

2550

d)

2400

82.

Bài 6. Tính các tổng sau đây: b. 2 + 4 + 6 + ... + 100

a)

2550

b)

2450

c)

2600

d)

2750

83.

Bài 6. Tính các tổng sau đây:
c. $\Sigma_{i=3}^{n+1} 1$

a)

n - 2

b)

n + 1

c)

n - 1

d)

n

84.

Bài 6. Tính các tổng sau đây: d. $\Sigma_{i=3}^{n+1} i$

a)

(n+1)(n+2)/2 - 3

b)

(n+1)(n+2)/2 - 2

c)

(n+1)(n+2)/2 - 1

d)

(n+1)(n+2)/2

85.

Bài 6. Tính các tổng sau đây: e. $\Sigma_{i=0}^{n-1} i(i+1)$

a)

n(n-1)(n+1)/3

b)

n(n+1)(n+2)/6

c)

n(n-1)(n+2)/2

d)

n(n-1)(n+1)/2

86.

Bài 6. Tính các tổng sau đây: f. $\Sigma_{i=1}^{n} 3^{i+1}$

a)

$3^2 + 3^3 + ... + 3^{n+1} = (3^{n+2} - 9)/2$

b)

$3^2 + 3^3 + ... + 3^{n+1}$ = $(3^{n+1} - 3)/2$

c)

$3^2 + 3^3 + ... + 3^{n+1}$ = $(3^{n+2} - 3)/2$

d)

$3^2 + 3^3 + ... + 3^{n+1}$ = $(3^{n+1} - 9)/2$

87.

Bài 6. Tính các tổng sau đây: g. $\Sigma_{i=1}^{n} \Sigma_{j=1}^{i} i \times j$

a)

n(n+1)(n+2)/6

b)

n(n+1)(2n+1)/6

c)

$n(n+1)^2/4$

d)

$\frac{n^2(n+1)}{2}$

88.

Bài 6. Tính các tổng sau đây: h. $\Sigma_{i=3}^{n+1} \frac{1}{i(i+1)}$

a)

1/12 - 1/(n+1)(n+2)

b)

1/6 - 1/(n+2)

c)

1/3 - 1/(n+1)

d)

1/9 - 1/(n+1)(n+2)

89.

Thuật toán Mystery(n) tính giá trị nào sau đây? ALGORITHM Mystery(n) //Đầu vào: một số nguyên không âm n S ← 0 for i ← 1 to n do S ← S + i × i return S

a)

Tổng các bình phương của các số từ 1 đến n

b)

Tổng các số từ 1 đến n

c)

Tích các số từ 1 đến n

d)

Tổng các lập phương của các số từ 1 đến n

90.

Trong thuật toán Mystery(n), phép toán cơ bản là gì?

a)

Phép nhân i × i

b)

Phép gán S ← 0

c)

Phép so sánh i ≤ n

d)

Phép cộng S + i

91.

Đầu vào của thuật toán Secret(A[0..n-1]) là gì?

a)

Một mảng A[0..n-1] gồm n số thực

b)

Một số nguyên n

c)

Một số thực duy nhất

d)

Hai số nguyên bất kỳ

92.

Đầu ra của thuật toán Secret(A[0..n-1]) là gì?

a)

Hiệu giữa giá trị lớn nhất và nhỏ nhất của mảng A

b)

Tổng các phần tử trong mảng A

c)

Giá trị lớn nhất trong mảng A

d)

Số lượng phần tử trong mảng A

93.

Bài 8. Xét thuật toán sau: ALGORITHM Secret(A[0..n-1]) //Đầu vào: một mảng A[0..n-1] có n số thực minval ← A[0] maxval ← A[0] for i ← 1 to n-1 do if (A[i] < minval) then minval ← A[i] if (A[i] > maxval) then maxval ← A[i] return maxval - minval Số lần thực hiện phép toán cơ bản trong thuật toán là bao nhiêu?

a)

2(n-1)

b)

n

c)

n-1

d)

n+1

94.

Độ phức tạp của thuật toán trên là:

a)

$O(n^2)$

b)

O(n)

c)

O(log n)

d)

O(n!)

95.

Có thuật toán nào khác cũng tính giá trị S = max(A) - min(A) nhanh hơn thuật toán Secret(A[0..n-1]) không?

a)

Không, thuật toán Secret đã tối ưu về số lần so sánh.

b)

Có, có thể dùng thuật toán khác nhanh hơn.

c)

Có, nhưng chỉ khi mảng đã được sắp xếp.

d)

Không, chỉ có thể tối ưu về bộ nhớ chứ không về thời gian.

96.

Đầu vào của thuật toán Enigma(A[0..n-1, 0..n-1]) là gì?

a)

Một ma trận A[0..n-1, 0..n-1] các số thực

b)

Một dãy số nguyên

c)

Một chuỗi ký tự

d)

Một danh sách các số nguyên

97.

Đầu ra của thuật toán Enigma(A[0..n-1, 0..n-1]) là gì?

a)

Trả về true nếu ma trận A đối xứng qua đường chéo chính, ngược lại trả về false.

b)

Trả về tổng các phần tử trên đường chéo chính của ma trận.

c)

Trả về false nếu tất cả các phần tử của ma trận đều bằng nhau.

d)

Trả về số lượng phần tử khác nhau trong ma trận.

98.

Bài 9. Xét thuật toán sau: ALGORITHM Enigma(A[0..n-1, 0..n-1]) //Đầu vào: một ma trận A[0..n-1, 0..n-1] các số thực for i ← 0 to n-2 do for j ← i+1 to n-1 do if (A[i, j] ≠ A[j, i]) then return false return true Số lần thực hiện phép toán cơ bản của thuật toán Enigma là bao nhiêu?

a)

n(n-1)/2

b)

$n^2$

c)

n(n+1)/2

d)

n

99.

Độ phức tạp của thuật toán trên là:

a)

$O(n^2)$

b)

O(n)

c)

O(log n)

d)

O(n!)

CHƯƠNG 1. GIỚI THIỆU - 1.1. Khái niệm thuật toán

Total questions: 99

Worksheet time: 50mins

Similar Resources on Wayground