Free Printable Tuần 1: bài kiểm tra 15 phút

Worksheets

Tuần 1: bài kiểm tra 15 phút

Total questions: 89

Worksheet time: 48mins

Name

Class

Date

Với thuật toán tính tổng của các số chẵn trong dãy n số nguyên (n nguyên dương), cần:

Kiểm tra tính chất chia hết cho 2 của từng phần tử trong dãy

Lặp lại qua từng phần tử

Khởi tạo tổng bằng -1

Tăng tổng khi gặp số lẻ

Biểu diễn thuật toán bằng ngôn ngữ tự nhiên có thể áp dụng tốt khi:

Sử dụng cấu trúc vòng lặp phức tạp

Giao tiếp với người chưa học lập trình

Giới thiệu khái niệm thuật toán

Viết phần mềm lớn

Câu 3: Biểu diễn thuật toán giải phương trình bậc nhất ax + b = 0 (a,b là số thực) bằng sơ đồ khối, các bước nào là phù hợp?

A. Sử dụng hình tròn/elip để biểu thị vòng lặp

B. Dùng hình thoi để kiểm tra điều kiện a = 0

C. Gán giá trị cho x sau khi kiểm tra điều kiện

D. Tính nghiệm x = b/a mà không kiểm tra điều kiện

Trong lưu đồ khối biểu diễn thuật toán:

Hình bình hành dùng để biểu diễn thao tác nhập/xuất

Hình tròn để biểu diễn thao tác kết thúc của thuật toán

mũi tên biểu diễn hướng thực hiện thuật toán

không có ký hiệu điều kiện

Trong lưu đồ khối biểu diễn thuật toán tìm giá trị lớn nhất trong dãy n số nguyên (n nguyên dương), bằng mã giả cần:

Gán max = 0 là cách làm đúng cho mọi trường hợp

So sánh từng phần tử trong dãy với max

Lưu đồ khối không dùng được cho thuật toán này

Gán giá trị ban đầu cho biến tìm max

Khi biểu diễn thuật toán tính tổng các số từ 1 đến n (n là số nguyên dương) bằng giả mã, cần:

Kiểm tra n chẵn/lẻ trước khi tính tổng

Khởi tạo biến tính tổng bằng 0

Dùng vòng lặp for từ 1 đến n

Tăng biến tổng sau khi vòng lặp kết thúc

Đoạn chương trình viết bằng giả mã sau thực hiện công việc gì?:

(chọn 2 phương án đúng)

1. scanf(&a, &b);

2. while (b != 0){

3. r = a % b;

4. a = b;

5. b = r;

}

6. us = a;

Tìm ước chung lớn nhất của hai số a và b (thuật toán Euclid)

Tính tổng hai số a và b

Áp dụng thuật toán euclid để tính ước số chung lớn nhất

tìm bội chung nhỏ nhất của hai số a, b

Trong lưu đồ khối biểu diễn thuật toán tìm USCLN của 2 số nguyên a, b bằng phương pháp Euclid, cần:

Luôn dùng vòng lặp for

Chỉ xét số nguyên dương < 5

Sử dụng phép chia có dư

Dừng khi phần dư bằng 0

Ngôn ngữ tự nhiên có thể gây mơ hồ trong bước xử lý

Đúng

Sai

10.

Giả mã yêu cầu nhiều ký hiệu đặc biệt

Đúng

Sai

11.

Mỗi cách biểu diễn thuật toán đều phù hợp với các tình huống khác nhau

Đúng

Sai

12.

Khối hình chữ nhật trong sơ đồ khối biểu diễn thao tác xử lý

Đúng

Sai

13.

Sơ đồ khối giúp lập trình viên dễ gỡ rối hơn

Đúng

Sai

14.

Trong sơ đồ khối, không cần có điểm bắt đầu/kết thúc

Đúng

Sai

15.

Ngôn ngữ tự nhiên là cách biểu diễn tối ưu nhất

Đúng

Sai

16.

1) Việc dùng giả mã để biểu diễn thuật toán làm khó khăn cho người học lập trình

Đúng

Sai

17.

: Mọi biểu diễn thuật toán bằng giả mã có thể dịch sang một ngôn ngữ lập trình.

Đúng

Sai

18.

Trong biểu diễn thật toán bằng giả mã cấu trúc lặp được dùng là “for”

Đúng

Sai

19.

Biểu diễn thật toán bằng giả mã không hỗ trợ điều kiện rẽ nhánh

Đúng

Sai

20.

1) Ngôn ngữ tự nhiên là cách biểu diễn tối ưu nhất

Đúng

Sai

21.

2) Sơ đồ khối giúp lập trình viên dễ gỡ rối hơn

Đúng

Sai

22.

3) Trong sơ đồ khối không cần có điểm bắt đầu/kết thúc

Đúng

Sai

23.

4) Khối hình chữ nhật trong sơ đồ khối biểu diễn thao tác xử lý

Đúng

Sai

24.

1) Trong sơ đồ khối, thao tác xử lý đều dùng hình chữ nhật

Đúng

Sai

25.

2) Trong sơ đồ khối, hình tròn/elip dùng để biểu diễn thao tác kiểm tra điều kiện

Đúng

Sai

26.

3) Trong sơ đồ khối có thể có nhiều điểm bắt đầu

Đúng

Sai

27.

4) Sơ đồ khối không thể hiện được vòng lặp

Đúng

Sai

28.

Việc dùng giả mã để biểu diễn thuật toán làm khó khăn cho người học lập trình

Đúng

Sai

29.

Mọi biểu diễn thuật toán bằng giả mã đều có thể dịch sang một ngôn ngữ lập trình

Đúng

Sai

30.

Biểu diễn thuật toán bằng giả mã không hỗ trợ điều kiện rẽ nhánh

Đúng

Sai

31.

Các thuật toán tính tổng không dùng sơ đồ khối

Đúng

Sai

32.

Khối hình thoi trong sơ đồ khối có 3 nhánh đi ra

Đúng

Sai

33.

Sơ đồ khối yêu cầu tuân thủ quy ước về các hình khối sử dụng

Đúng

Sai

34.

Sơ đồ khối giúp trực quan hóa thuật toán

Đúng

Sai

35.

Sơ đồ khối không áp dụng được cho thuật toán đệ quy

Đúng

Sai

36.

Sơ đồ khối giúp giảm mã lỗi khi lập trình

Đúng

Sai

37.

Biểu diễn thuật toán bằng giả mã có thể viết bằng bất kỳ cú pháp nào không cần theo quy tắc

Đúng

Sai

38.

Biểu diễn thuật toán bằng giả mã dùng cú pháp của C hoặc Pascal

Đúng

Sai

39.

Câu 1: khi đánh giá độ phức tạp của một chương trình chính có gọi các chương trình con (không đệ quy) ta thực hiện theo thứ tự nào dưới đây ?( chọn 2 phương án đúng)

Ưu tiên phân tích chương trình chính rồi bỏ qua chương trình con

Phân tích độ phức tạp của từng chương trình con

Xác định số lần chương trình chính gọi mỗi chương trình con

Bỏ qua phần thân chương trình con vì không ảnh hưởng đến độ phức tạp

40.

Trong một đoạn chương trình có vòng lặp lồng nhau for (k=1; k<=n; k=k+2) for (j=1;j<=n; j=j+2) nếu mỗi thao tác trong thân vòng lặp có độ phức tạp O(1) thì độ phức tạp thời gian của đoạn chương trình là:(chọn 2 phương án đúng nhất)

$O((n^2)/4)$

O(logn)

O(n)

$O(n^2)$

41.

Cho đoạn mã chương trình sau: scan(&n); while (n > 1) { n=n-2 } Với đầu vào n là số lẻ, phát biểu nào là đúng: (chọn 2 phương án đúng )

A. Độ phức tạp là O(log n)

B. Vòng lặp không bao giờ dừng

C. Vòng lặp chạy nhưng dừng tại n = 1

D. Vòng lặp thực hiện (n - 1)/2 lần

42.

Câu 4: Cho thuật toán có một vòng lặp for chạy từ 1 đến n, trong thân vòng mỗi thao tác có độ phức tạp O(log n). Độ phức tạp tổng thể của thuật toán là:

vòng lặp thực hiện n lần, mỗi lần xử lý O( log n)

t $tổng\ độ\ phức\ tạp\ thời\ gian\ là\ O\left(n\log n\right)$

độ phức tạp thời gian là O(log n)

thuật toán có thể được tối ưu xuống O(n)

43.

Trong một đoạn chương trình có vòng lặp lồng nhau for (k=1; k<=n; k=k+2) for (j=1;j<=n; j++) nếu mỗi thao tác trong thân vòng lặp có độ phức tạp O(n) thì tổng độ phức tạp của đoạn chương trình sẽ là:

O(n*n*n)

O(n³)

O(n²)

O(nlogn)

44.

Trong một đoạn chương trình có vòng lặp lồng nhau for (k=1; k<=n; k++) for (j=1;j<=n; j++) mỗi thao tác trong thân vòng lặp có độ phức tạp O(1). Phát biểu nào sau đây là đúng:

A. Độ phức tạp tổng thể là O(n²)

B. Số lần thực hiện thao tác O(1) là n*n

C. Vòng lặp trong thực hiện n lần

D. Độ phức tạp là O(n)

45.

Câu 7: Trong đánh giá độ phức tạp của thuật toán, quy tắc nhân thường áp dụng cho:

(Chọn 2 phương án đúng)

vòng lặp lồng nhau.

các thao tác thực hiện nối tiếp

hàm gọi nhiều hàm con với chi phí tương tự

các thao tác chạy đồng thời (song song)

46.

Độ phức tạp thời gian của đoạn chương trình sau là? trong đó a, b là các số nguyên không âm và n = max(a,b);

A. Độ phức tạp phụ thuộc vào số lần chia, tối đa là O(log n)

B. Thuật toán thực hiện trong thời gian hằng số O(1) về số vòng lặp ít

C. Độ phức tạp là O(n) vì dùng phép chia dư trong vòng lặp

D. Độ phức tạp trung bình là O(log n) trong hầu hết các trường hợp

47.

Cho đoạn chương trình có một vòng lặp duy nhất chạy từ 1 đến n, trong thân vòng lặp có thao tác O(1). Phát biểu nào sau đây là đúng:

Độ phức tạp là O(n²)

Tổng số thao tác thực hiện là O(n)

Độ phức tạp là O(1)

Độ phức tạp thời gian là O(n)

48.

Chọn phát biểu đúng về khả năng hỗ trợ của đệ quy trong các ngôn ngữ lập trình?( chọn 2 phương án đúng)

C và Pascal đều hỗ trợ hàm đệ quy

Tất cả các ngôn ngữ lập trình đều hỗ trợ đệ quy

Đệ quy không thể dùng trong bài toán tính tổng

Đệ quy có thể thay thế vòng lặp trong một số trường hợp

49.

Câu 2: Chọn 2 phương án đúng nói về việc lập và sử dụng phương trình đệ quy Sinh viên chọn 2 phương án đúng nhất

A. T(n) = T(n-1) - C là công thức phổ biến

B. T(n) = T(n) + 1 là phương trình đúng

C. T(n)=T(n-1) + C có độ phức tạp O(n)

D. Để tính độ phức tạp thuật toán đệ quy, cần lập phương trình đệ quy

50.

Các phần bắt buộc để xây dựng một chương trình còn đệ quy là gì?

Câu lệnh gọi

Điều kiện dừng

Lời gọi đệ quy

Sử dụng vòng lặp

51.

Ví dụ nào sau đây là đệ quy đúng trong lập trình?

Một hàm gọi chính nó với tham số giảm dần

Một hàm gọi hàm khác

Một hàm dùng vòng lặp for

Một hàm gọi chính nó mà không thay đổi tham số

52.

Phương trình đệ quy nào dưới đây có thể được phân tích bằng định lý Master

T(n)=T(n-1) + n

$T(n)=4T(n/3) + n^2$

T(n)=3T(n/2) + n

T(n)=2T(n-1) + 1

53.

Sinh viên chọn 2 phương án đúng liên quan đến hàm đệ quy uscln(a,b)

Đệ quy không được sử dụng trong các phép chia

Hàm uscln(a, b) sẽ chạy vô hạn nếu b luôn khác 0

Phép gọi uscln(b, a % b) là phần đệ quy

Hàm uscln(a, b) có phần cơ sở là khi b == 0

54.

Chọn 2 phương án đúng liên quan đến ưu, nhược điểm của đệ quy:

Đệ quy chỉ dùng được khi dữ liệu là số nguyên

Một số bài toán đối hỏi bắt buộc phải dùng đệ quy

Đệ quy giúp biểu diễn bài toán ngắn gọn hơn

Đệ quy là cách viết khó hơn và ít ứng dụng hơn vòng lặp

55.

Chọn 2 phương án đúng nói về việc sử dụng đệ quy trong bài toán Fibonacci

A. Hàm tính Fibonacci có hai lời gọi đệ quy

B. Fibonacci không thể tính bằng vòng lặp

C. Dãy Fibonacci là ví dụ kinh điển của thuật toán đệ quy

D. Tính fibo(5) chỉ gọi một lần đệ quy

56.

Những điểm cần chú ý khi biểu diễn thuật toán bằng ngôn ngữ tự nhiên là:

Dùng từ thông dụng, dễ hiểu

Trình bày theo trình tự logic của quá trình xử lý

Nên dùng thuật ngữ lập trình chuyên nghiệp

Không cần viết rõ kết quả đầu ra

57.

Chọn 2 phương án đúng phát biểu đến khả năng hỗ trợ đệ quy trong các ngôn ngữ lập trình.

Sinh viên chọn 2 phương án đúng nhất

C và Pascal đều hỗ trợ hàm đệ quy

Tất cả các ngôn ngữ lập trình đều hỗ trợ hàm đệ quy

đệ quy không thể dùng trong các bài toán tính tồng

đệ quy có thể thay thế vòng lặp trong một số trường hợp

58.

Chọn 2 phương án đúng liên quan đến phần cơ sở trong đệ quy Sinh viên chọn 2 phương án đúng nhất

Nếu không có phần cơ sở, chương trình sẽ lặp vô hạn

Phần cơ sở có thể bỏ qua nếu bài toán nhỏ

Một chương trình đệ quy phải có phần cơ sở để kết thúc đệ quy

Hàm đệ quy không thể dùng trong pascal

59.

Trong lưu đồ khối biểu diễn thuật toán tìm USCLN của hai số nguyên a, b bằng phương pháp Euclid cần:

Luôn dùng vòng lặp for

Chỉ xét số nguyên dương <5

Dừng khi phần dư bằng 0

Sử dụng phép chia có dư

60.

Thuật toán giải phương trình ax+b=0 (với a,b là số thực) bằng giả mã, cần:

Xuất thông báo nếu b≠0

Kiểm tra hệ số a=0

Duyệt a, b bằng vòng lặp

Tính nghiệm x=-b/a

61.

Câu 6: Cho đoạn mã chương trình sau
Scan(&n);
While(n>1){
n=n-2;
};
Với đầu vào n là số chẵn, phát biểu nào sau đây đúng.

vòng lặp không thực hiện nếu n<1

Độ phức tạp là O(n)

Số lần lặp là n/2

Vòng lặp sẽ kết thúc khi n =2

62.

Sinh viên chọn 2 phương án đúng nhất:

Vòng lặp không thực hiện nếu n<1

Độ phức tạp là O(n)

Số lần lặp là n/2

Vòng lặp kết thúc khi n=2

63.

Chọn 2 phương án đúng liên quan đến hàm đệ quy uscln(a,b): Sinh viên chọn 2 phương án đúng nhất

Đệ quy không được sử dụng trong các phép chia

Hàm uscln(a,b) chạy vô hạn nếu b luôn khác 0

Phép gọi uscln(a, a%b) là phần đệ quy

Hàm uscln(a,b) có phần cơ sở khi b==0

64.

Câu 3: Với bài toán “Tháp Hà Nội”, để chuyển n đĩa từ cọc A sang cọc B (cọc trung gian C)

Lặp lại thao tác 64 lần

Chuyển n-1 đĩa từ C sang B

Chuyển 2 đĩa từ A sang B

Chuyển n-1 đĩa từ A sang C

65.

Khi sử dụng quy tắc tổng quát để phân tích độ phức tạp chương trình, nếu phần thân của chương trình có độ phức tạp O(n) và số vòng lặp là n, thì độ phức tạp toàn vòng lặp là:

$O(n^2)$

O(n)

O(n+n)

n×O(n)

66.

Giả sử chương trình có hai vòng lặp lồng nhau, mỗi vòng lặp chạy từ 1 đến n. Trong thân của vòng lặp, mỗi thao tác có độ phức tạp O(1). Phát biểu nào sau đây đúng.

Độ phức tạm là O(1)

Tổng số thao tác chương trình là O(n^2)

Độ phức tạm thời gian là O(n^2)

Độ phức tạp thời gian là O(n)

67.

Đoạn chương trình viết bằng giả mã sau thực hiện công việc gì?: Sinh viên chọn 2 phương án đúng nhất

1. scan(&a,&b) ;

2. while(b !=0){

3. r = a%b ;

4. a=b ;

5. b=r ;

}

6. us=a ;

Tìm bội chung nhỏ nhất (BCNN) của a và b

Tính tổng hai số nguyên a và b

Áp dụng thuật toán Euclid để tính USCLN

Tính ước số chung lớn nhất (USCLN) của hai số a và b

68.

Chọn hai phương án đúng về thuật toán đơn định (Sinh viên chọn 2 phương án đúng nhất)

Độ phức tạp thuật toán có dạng $O(n^k)$ với k là hằng số

Tất cả các thuật toán đơn định đều có độ phức tạp tuyến tính

Thuật toán đơn định luôn cho kết quả giống nhau với cùng đầu vào

Thuật toán đơn định có thể cho phép chọn nhiều hướng đi

69.

Câu 12: Chọn hai phương án đúng liên quan đến lớp bài toán NP.

A. Tìm phần tử lớn nhất trong mảng là bài toán lớp NP

B. Bài toán tìm tập con có tổng bằng 0 là bài toán lớp NP

C. Bài toán phân hoạch cũng thuộc lớp NP

D.Thuật toán kiểm chứng nghiệm bài toán NP luôn là đệ quy

70.

Chọn hai phương án đúng về quan hệ giữa các bài toán P và NP

Nếu một bài toán có độ phức tạp $O(2^n)$ thì chắc chắn thuộc lớp P

Nếu P = NP thì tất cả các bài toán NP đều giải được bằng thuật toán đơn định trong thời gian đa thức

Một số bài toán có thể kiểm tra nghiệm nhanh nhưng tìm nghiệm thì rất khó

Lớp NP chỉ chứa các bài toán dễ

71.

Bài toán nào sau đây thuộc lớp P?

Sắp xếp dãy số bằng thuật toán QuickSort

Tô màu đồ thị

Tìm chu trình Hamilton

Tìm kiếm tuyến tính

72.

Bài toán nào sau đây có thể kiểm chứng nghiệm trong thời gian đa thức?

Tìm kiếm tuyến tính

Tính tổng dãy số

Xác định số nguyên tố

Tập con có tổng bằng 0 (Subset Sum Problem)

73.

Thuật toán không đơn định có đặc điểm nào?(chọn 2 phương án đúng nhất)

Luôn đi theo một hướng duy nhất tại mỗi bước

Có thể "thử" các khả năng khác nhau cùng lúc

Kết quả luôn giống nhau với cùng đầu vào

có nhiều hướng đi tiếp tại mỗi bước

74.

Bài toán thuộc lớp P có tính chất nào?

Có thể kiểm chứng nghiệm trong thời gian đa thức

Có thể giải bằng thuật toán vét cạn trong thời gian mũ

Có thể giải bằng thuật toán đơn định trong thời gian đa thức

Chỉ có thể giải bằng thuật toán không đơn định

75.

Bài toán lớp P thỏa mãn điều kiện nào?

Là bài toán không thể giải trong thực tế

Có thể giải bằng thuật toán đơn định trong thời gian đa thức

Có thể kiểm chứng nghiệm trong thời gian đa thức

Luôn có độ phức tạp là O(n!)

76.

Bài toán nào sau đây có thể được giải bằng thuật toán không đơn định đa thức?

Xếp ba lô 0-1

Nhân ma trận

Tìm chu trình Euler

Tìm chu trình Hamilton

77.

Câu 31: Đâu là hai đặc điểm đúng của thuật toán đơn định?

Thuật toán luôn cho kết quả giống nhau với cùng một đầu vào.

Thuật toán có thể cho kết quả khác nhau với cùng một đầu vào.

Độ phức tạp đa thức có dạng O(n^k) với k là hằng số

Tất cả thuật toán đơn định đều có độ phức tạp tuyến tính

78.

Câu 32: Chọn hai phương án đúng liên quan đến lớp bài toán P (Sinh viên chọn 2 phương án đúng nhất)

A. Lớp P được coi là lớp bài toán khó

B. Lớp P gồm các bài toán giải trong thời gian đa thức bằng thuật toán đơn định

C. Sắp xếp và tìm kiếm tuyến tính là bài toán lớp P

D. Mọi bài toán lớp P đều không giải được trong thực tế

79.

Ví dụ nào thuộc lớp NP nhưng chưa biết có nằm trong P hay không?

Tìm kiếm nhị phân

Tìm phân tử lớn nhất

Phân hoạch tập số

Tô màu đồ thị

80.

Đặc điểm nhận biết bài toán thuộc lớp NP là:

Có thuật toán đơn định giải trong thời gian tuyến tính

Có thể tìm được lời giải bằng thuật toán logarit

Có thể kiểm tra nghiệm trong thời gian đa thức

Được giải quyết bởi các phương pháp xấp xỉ

81.

Ví dụ nào sau đây thuộc lớp P với độ phức tạp O(n^2)?

Tính lũy thừa nhị phân

Nhân ma trận

Kiểm tra tính liên thông đồ thị

Tìm chu trình Hamilton

82.

thuật toán đơn định có đặc điểm nào sau đây: 2 đáp đúng

có thể cho nhiều kết quả với cùng đầu vào

luôn kết thúc sau số bước xác định

có độ phức tạp không xác định

luôn chọn một hành động duy nhất tại mỗi bước

83.

Phương pháp nào thường dùng để giải bài toán NP trong thực tế?
(Chọn 2 phương án đúng)

tìm kiếm vét cạn

sắp xếp nhanh

Heuristic

Thuật toán xấp xỉ

84.

Trong một tình huống không đơn định, điều nào đúng?

Luôn có lời giải duy nhất

Có nhiều hướng đi tiếp tại mỗi bước

Có thể “thử” các khả năng khác nhau cùng lúc

Không bao giờ đưa ra kết quả sai

85.

Bài toán lớp P thỏa mãn điều kiện nào?

Luôn có độ phức tạp là O(n!)

Có thể kiểm chứng nghiệm trong thời gian đa thức

Có thể giải bằng thuật toán đơn định trong thời gian đa thức

Là bài toán không thể giải trong thực tế

86.

Phát biểu nào đúng về thuật toán đơn định?

Độ phức tạp đa thức có dạng O(n^k) với k là hằng số

Có thể lựa chọn nhiều hướng đi cùng lúc

Luôn cho kết quả giống nhau với cùng đầu vào

Tất cả đều có độ phức tạp tuyến tính

87.

Ví dụ điển hình về quy dẫn từ bài toán SAT là:

A. Từ HC sang TSP

B. Từ TSP sang HC

C. Từ P sang NP

D. Từ SAT sang 3-SAT

88.

Chứng minh bài toán PHẠT là NPC dựa trên bài toán nào?

A. CIRCUITSAT

B. Max-Cut

C. KNAPSACK

D. TSP

89.

Để quy dẫn từ bài tán SAT sang bài toán Max-Cut, cần:

Tìm đường đi Euler

Dùng mô hình Hamilton

Mã hóa ràng buộc logic bằng trong số cạnh

Biểu diễn biến logic thành đỉnh và cạnh của đồ thị

Reset

Tuần 1: bài kiểm tra 15 phút

Total questions: 89

Worksheet time: 48mins

Similar Resources on Wayground