wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

PTTT 1

Total questions: 99

Worksheet time: 53mins

Name
Class
Date
1.

Giải bài toán trên máy tính là

a)

thực hiện một dãy hữu hạn những thao tác để tìm được dữ liệu ra

b)

thực hiện một dãy hữu hạn những thao tác có cơ sở khoa học thích hợp để tìm được dữ liệu ra

c)

xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có cơ sở khoa học thích hợp để tìm được dữ liệu ra

d)

xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có cơ sở khoa học thích hợp để tìm được dữ liệu ra theo yêu cầu của bài toán

2.

Thuật toán là

a)

một dãy hữu hạn các bước, mô tả chính xác các phép toán hoặc hành động để giải quyết một vấn đề

b)

một dãy hữu hạn các bước, mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề

c)

một dãy các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề

d)

một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề

3.

Tính hiệu quả của thuật toán được đánh giá dựa trên các tiêu chuẩn:

a)

Dung lượng bộ nhớ cần có và thời gian cần thiết để chạy chương trình

b)

Dung lượng bộ nhớ cần có

c)

Thời gian cần thiết để chạy chương trình

d)

Dung lượng bộ nhớ của máy tính và thời gian chạy chương trình

4.

Giải thuật là

a)

cách giải quyết bài toán cho kết quả gần đúng (chấp nhận được) đỡ phức tạp và có hiệu quả hơn

b)

cách giải quyết bài toán cho kết quả đúng

c)

cách giải quyết bài toán đảm bảo các đặc trưng của thuật toán

d)

cách giải quyết bài toán cho kết quả có hiệu quả hơn

5.

Trong biểu diễn một bài toán trên máy tính, Output là:

a)

Các dữ liệu vào của bài toán

b)

Các dữ liệu ra của bài toán

c)

Các dữ liệu ra thỏa mãn yêu cầu của bài toán

d)

Dữ liệu của quá trình tính toán bài toán

6.

Với bài toán: Xác định giá trị lớn nhất trong dãy có n số nguyên X={x₁, x₂, ..., xₙ}, n là số nguyên dương. Hãy xác định kích thước của bài toán theo quan niệm thực nhất:

a)

n

b)

n+1

c)

n2

d)

nlogn

7.

Xác định Input của bài toán: Hoán đổi giá trị của 2 biến số nguyên x và y và dùng biến trung gian số nguyên z

a)

Ba biến số nguyên x, y, z

b)

Hai biến số nguyên x, y

c)

Hai biến số nguyên x, z

d)

Hai biến số nguyên y, z

8.

Phương pháp giả mã dùng để biểu diễn thuật toán là

a)

mượn một ngôn ngữ lập trình nào đó để viết chương trình

b)

dùng cấu trúc của một ngôn ngữ lập trình bậc cao để viết chương trình

c)

dùng cấu trúc của ngôn ngữ lập trình bậc thấp để mô tả thuật toán

d)

mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán

9.

Khi biểu diễn thuật toán bằng lưu đồ khối (sơ đồ khối), hình chữ nhật có ý nghĩa gì?

a)

Thực hiện thao tác kiểm tra dữ liệu theo điều kiện để phân nhánh thuật toán

b)

Thực hiện thao tác ghi và nhập dữ liệu

c)

Thực hiện thao tác nhập và xuất dữ liệu

d)

Thực hiện thao tác xử lý dữ liệu (gán, các phép tính cơ bản)

10.

Cho dãy số nguyên có n phần tử x₁, x₂, ..., xₙ và số nguyên k. Nếu thuật toán tìm thấy và đưa ra chỉ số thứ i đầu tiên thỏa mãn thì với điều kiện nào thuật toán sẽ dừng:

a)

i >= n

b)

i < n

c)

xᵢ = k

d)

xᵢ <> k

11.

Thuật toán được biểu diễn bằng lưu đồ khối sau, thực hiện:

a)

Đếm các phần tử chẵn của dãy số có n phần tử x₁, x₂,..., xₙ

b)

Tính tổng các phần tử chẵn của dãy số có n phần tử x₁, x₂,..., xₙ

c)

Tìm kiếm các phần tử chẵn của dãy số có n phần tử x₁, x₂,..., xₙ

d)

Sắp xếp các phần tử chẵn của dãy số có n phần tử x₁, x₂,..., xₙ

12.

Câu 14: Thuật toán được biểu diễn bằng lưu đồ khối sau thực hiện chức năng nào?

a)

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

b)

Tìm số lớn nhất trong dãy số

c)

Kiểm tra số nguyên tố

d)

Sắp xếp dãy số tăng dần

13.

Thuật toán được biểu diễn bằng lưu đồ khối sau, thực hiện:

a)

Đếm các phần tử chẵn của dãy số có n phần tử x₁, x₂, ..., xₙ

b)

Tính tổng các phần tử chẵn của dãy số có n phần tử x₁, x₂, ..., xₙ

c)

Tìm kiếm các phần tử chẵn của dãy số có n phần tử x₁, x₂, ..., xₙ

d)

Sắp xếp các phần tử chẵn của dãy số có n phần tử x₁, x₂, ..., xₙ

14.

Tìm giá trị lớn nhất của 2 số a, b; Tìm Ước số chung lớn nhất của 2 số a, b; Tìm bội số chung lớn nhất của 2 số a, b; Hoán đổi 2 số a, b

a)

Tìm giá trị lớn nhất của 2 số a, b

b)

Tìm Ước số chung lớn nhất của 2 số a, b

c)

Tìm bội số chung lớn nhất của 2 số a, b

d)

Hoán đổi 2 số a, b

15.

Độ phức tạp dữ liệu vào của bài toán theo quan niệm thứ nhất là

a)

số lượng dữ liệu vào của bài toán

b)

số lượng dữ liệu được xử lý của bài toán

c)

số lượng dữ liệu trung gian của bài toán

d)

số lượng dữ liệu đã được sử dụng vào của bài toán

16.

Thời gian trên máy Turing là:

a)

Thời gian cần thiết để thực hiện một dãy các bước chuyển hình trạng

b)

Thời gian cần thiết để thực hiện một bước chuyển hình trạng

c)

Thời gian cần thiết để thực hiện bước chuyển hình trạng đầu

d)

Thời gian cần thiết để thực hiện bước chuyển hình trạng cuối

17.

Với máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL, đơn vị nhớ là:

a)

Một chỗ nhớ để chứa một kí hiệu

b)

Một chỗ nhớ để chứa một dữ liệu

c)

Một chỗ nhớ để chứa một dữ liệu vào

d)

Một chỗ nhớ để chứa một dữ liệu ra

18.

Xác định Output của bài toán: Kiểm tra tính nguyên tố của số nguyên dương n

a)

n là hợp số

b)

n không là số nguyên tố

c)

n là số nguyên tố

d)

n là số nguyên tố hoặc n không là số nguyên tố

19.

Biểu diễn thuật toán theo ngôn ngữ tự nhiên là

a)

sử dụng ngôn ngữ chữ viết thường ngày

b)

sử dụng ngôn ngữ chữ viết thường ngày để liệt kê các bước của thuật toán

c)

sử dụng ngôn ngữ thường ngày để lập chương trình

d)

sử dụng ngôn ngữ chữ viết để vẽ thuật toán

20.

Với bài toán: Xác định giá trị lớn nhất trong dãy n số nguyên X={x₁, x₂, ..., xₙ}, n là số nguyên dương. Hãy chọn biểu diễn Input, Output đúng:

a)

Input: Dãy số nguyên X={x₁, x₂, ..., xₙ}, n nguyên dương. Output: Tìm giá trị lớn nhất Max của dãy X

b)

Input: Dãy số nguyên X={x₁, x₂, ..., xₙ} Output: Tìm số giá trị lớn nhất

c)

Input: Dãy số nguyên X={x₁, x₂, ..., xₙ}, n Output: Tìm giá trị lớn nhất

d)

Input: Dãy số nguyên X={x₁, x₂, ..., xₙ} Output: Tìm giá trị lớn nhất Max của X

21.

Cho dãy số nguyên có n phần tử: x₁, x₂, ..., xₙ. Nếu thuật toán tìm thấy và đưa ra chỉ số thứ i đầu tiên thỏa mãn xᵢ là số chẵn thì với điều kiện nào thuật toán sẽ dừng:

a)

A. i >= n

b)

B. i < n

c)

C. xᵢ là số chẵn

d)

D. xᵢ là số lẻ

22.

Thuật toán được biểu diễn bằng lưu đồ khối sau, thực hiện:

a)

Tìm giá trị lớn nhất của 2 số a, b

b)

Tìm Ước số chung lớn nhất của 2 số a, b

c)

Tìm bội số chung lớn nhất của 2 số a, b

d)

Giải phương trình bậc nhất

23.

Trong biểu diễn một bài toán trên máy tính, Input là

a)

Một dữ liệu vào của bài toán

b)

Các dữ liệu vào của bài toán

c)

Dữ liệu trung gian của bài toán

d)

Dữ liệu trong tính toán của bài toán

24.

Tính hữu hạn của thuật toán là

a)

thuật toán bao giờ cũng phải dừng lại sau một số hữu hạn bước

b)

thuật toán sẽ dừng lại sau một số bước thực hiện

c)

thuật toán sẽ dừng lại sau một số lần lặp các bước

d)

thuật toán bao giờ cũng phải dừng lại sau một số vô hạn bước thực hiện

25.

Với máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL, giá bộ nhớ là:

a)

Số chỗ nhớ để chứa dữ liệu vào và dữ liệu ra

b)

Số chỗ nhớ để chứa dữ liệu ra và các dữ liệu trung gian

c)

Số chỗ nhớ để chứa dữ liệu vào, dữ liệu ra và các dữ liệu trung gian

d)

Số chỗ nhớ để chứa dữ liệu được xử lý

26.

Thuật toán được biểu diễn bằng lưu đồ khối sau thực hiện chức năng nào?

a)

Tính tổng các phần tử của dãy số có n phần tử x1, x2, …, xn

b)

Đếm các phần tử của dãy số có n phần tử x1, x2, …, xn

c)

Tìm kiếm các phần tử của dãy số có n phần tử x1, x2, …, xn

d)

Sắp xếp các phần tử của dãy số có n phần tử x1, x2, …, xn

27.

Lưu đồ khối dùng để biểu diễn thuật toán là

a)

một hệ thống các nút (nút giới hạn, nút thao tác, nút điều kiện) có hình dạng khác nhau theo qui ước, thể hiện các chức năng khác nhau và được nối với nhau bởi các cung (mũi tên)

b)

một hệ thống các nút (nút giới hạn, nút điều kiện, mũi tên) có hình dạng khác nhau theo qui ước, thể hiện các chức năng khác nhau

c)

một hệ thống các nút (nút giới hạn, nút thao tác, mũi tên) được nối với nhau bởi các cung (mũi tên)

d)

một hệ thống các nút (nút giới hạn, nút thao tác, nút điều kiện, mũi tên) thể hiện các chức năng khác nhau và không được nối với nhau

28.

Xác định Input, Output cho bài toán tìm kiếm tuần tự giá trị k trong dãy n số nguyên khác nhau x₁, x₂, ..., xₙ

a)

Input: số nguyên dương n, dãy n số nguyên khác nhau x₁, x₂, ..., xₙ, số nguyên k Output: Vị trí i mà xᵢ = k hoặc thông báo không tìm thấy số nguyên k trong dãy

b)

Input: dãy n số nguyên khác nhau x₁, x₂, ..., xₙ, số nguyên k Output: Vị trí i mà xᵢ = k hoặc thông báo không tìm thấy số nguyên k trong dãy

c)

Input: dãy n số nguyên khác nhau x₁, x₂, ..., xₙ, số nguyên k Output: Vị trí i mà xᵢ = k

d)

Input: số nguyên dương n, dãy n số nguyên khác nhau x₁, x₂, ..., xₙ Output: Vị trí i mà xᵢ = k hoặc thông báo không tìm thấy số nguyên k trong dãy

29.

Giá về thời gian trên máy Turing là:

a)

Thời gian để thực hiện bước chuyển hình trạng đầu

b)

Thời gian để thực hiện bước chuyển hình trạng cuối

c)

Thời gian để thực hiện các bước chuyển hình trạng từ hình trạng đầu đến hình trạng cuối

d)

Thời gian để thực hiện các bước chuyển hình trạng trung gian

30.

Trong lưu đồ khối biểu diễn thuật toán: ( chọn 2 đáp án)

a)

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

b)

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

c)

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

d)

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

31.

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), cần:

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

a)

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

b)

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

c)

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

d)

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

32.

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à:

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

a)

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

b)

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

c)

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

d)

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

33.

Khi 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?

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

a)

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

b)

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

c)

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

d)

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

34.

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:

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

a)

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

b)

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

c)

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

d)

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

35.

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

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

a)

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

b)

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

c)

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

d)

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

36.

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:

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

a)

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

b)

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

c)

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

d)

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

37.

Đ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 đáp án đúng

scanf(&a,&b);

While(b!=0) {

r = a % b;

a = b;

b = r;

}

us = a;

Đ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 đáp án đúng

a)

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

b)

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

c)

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

d)

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

38.

Xác định tính đúng sai của các mệnh đề dưới đây về biểu diễn thuật toán bằng sơ đồ khối và giả mã:

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

a)

Đúng

b)

Sai

39.

Xác định tính đúng/sai của các mệnh đề dưới đây về các phương pháp biểu diễn thuật toán bằng giả mã

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

a)

Đúng

b)

Sai

40.

Xác định tính đúng/sai của các mệnh đề dưới đây về các phương pháp biểu diễn thuật toán bằng giả mã.

3 . 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

a)

Đúng

b)

Sai

41.

Xác định tính đúng/sai của các mệnh đề dưới đây về các phương pháp biểu diễn thuật toán bằng giả mã

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

a)

Đúng

b)

Sai

42.

Xác định tính đúng/sai của các mệnh đề dưới đây về các phương pháp biểu diễn thuật toán bằng giả mã

  1. 1. 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

a)

Đúng

b)

Sai

43.

Xác định tính đúng/sai của các mệnh đề dưới đây về các phương pháp biểu diễn thuật toán bằng giả mã

  1. 2. Trong biểu diễn thuật toán bằng giả mã, cấu trúc lặp được dùng là "for"

a)

Đúng

b)

Sai

44.

Xác định tính đúng/sai của các mệnh đề dưới đây về các phương pháp biểu diễn thuật toán bằng giả mã

3 . 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

a)

Đúng

b)

Sai

45.

Xác định tính đúng/sai của các mệnh đề dưới đây về các phương pháp biểu diễn thuật toán bằng giả mã

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

a)

Đúng

b)

Sai

46.

Xác định tính đúng sai của các mệnh đề dưới đây liên quan đến sơ đồ khối

1 . 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

a)

Đúng

b)

Sai

47.

Xác định tính đúng sai của các mệnh đề dưới đây liên quan đến sơ đồ khối

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

a)

Đúng

b)

Sai

48.

Xác định tính đúng sai của các mệnh đề dưới đây liên quan đến sơ đồ khối

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

a)

Đúng

b)

Sai

49.

Xác định tính đúng/sai của các mệnh đề dưới đây về sơ đồ khối:

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

a)

Đúng

b)

Sai

50.

Xác định tính đúng/sai của các mệnh đề dưới đây về sơ đồ khối và ngôn ngữ tự nhiên trong biểu diễn thuật toán

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

a)

Đúng

b)

Sai

51.

Xác định tính đúng/sai của các mệnh đề dưới đây về sơ đồ khối và ngôn ngữ tự nhiên trong biểu diễn thuật toán 2) Trong sơ đồ khối, không cần có điểm bắt đầu kết thúc

a)

Đúng

b)

Sai

52.

Xác định tính đúng/sai của các mệnh đề dưới đây về sơ đồ khối và ngôn ngữ tự nhiên trong biểu diễn thuật toán

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

a)

Đúng

b)

Sai

53.

Xác định tính đúng/sai của các mệnh đề dưới đây về sơ đồ khối và ngôn ngữ tự nhiên trong biểu diễn thuật toán

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

a)

Đúng

b)

Sai

54.

Khi thực hiện một thuật toán, người ta thường quan tâm tới

a)

chi phí về hệ điều hành và ngôn ngữ lập trình

b)

chi phí về cấu trúc dữ liệu

c)

chi phí thời gian

d)

chi phí thời gian và chi phí không gian (bộ nhớ)

55.

Chi phí thời gian của một quá trình tính toán là

a)

thời gian cần thiết để thiết kế thuật toán

b)

thời gian cần thiết để xây dựng thuật toán

c)

thời gian cần thiết để thực hiện một quá trình tính toán

d)

thời gian cần thiết để kiểm tra quá trình tính toán

56.

Chi phí không gian của một quá trình tính toán là

a)

số ô nhớ cần để chứa một dữ liệu

b)

số ô nhớ cần để chứa dữ liệu vào và ra

c)

số ô nhớ cần để kiểm tra một quá trình tính toán

d)

số ô nhớ cần để thực hiện một quá trình tính toán

57.

Giá về bộ nhớ trên máy Turing là

a)

Số đơn vị nhớ để ghi dữ liệu vào, dữ liệu ra

b)

Số đơn vị nhớ để ghi dữ liệu vào và kết quả trung gian

c)

Số đơn vị nhớ để ghi dữ liệu vào, dữ liệu ra và kết quả trung gian

d)

Số đơn vị nhớ để ghi kết quả trung gian

58.

Với máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL, giá về thời gian là:

a)

Số phép tính số học

b)

Số phép tính quan hệ

c)

Số phép tính logic

d)

Số phép tính căn bản

59.

Khi nói thời gian thực hiện của một chương trình là T(n) = Cn (C là hằng số) thì có nghĩa là

a)

chương trình đó cần Cn dữ liệu vào

b)

chương trình đó cần Cn dữ liệu ra

c)

chương trình đó cần Cn dữ liệu tính toán

d)

chương trình đó cần Cn chỉ thị thực thi

60.

Giả sử T(n) là thời gian thực hiện thuật toán P nếu T(n) có bậc là g(n) thì

a)

độ phức tạp dữ liệu vào của thuật toán P là g(n) hay O(g(n))

b)

độ phức tạp dữ liệu ra của thuật toán P là g(n) hay O(g(n))

c)

độ phức tạp của thuật toán P là g(n) hay O(g(n))

d)

độ phức tạp không gian của thuật toán P là g(n) hay O(g(n))

61.

Cách đánh giá thời gian thực hiện thuật toán độc lập với máy tính và các yếu tố liên quan tới máy tính sẽ dẫn tới khái niệm gọi là

a)

độ phức tạp của dữ liệu vào thuật toán

b)

độ phức tạp dữ liệu ra của thuật toán

c)

độ phức tạp tính toán của thuật toán

d)

độ phức tạp không gian của thuật toán

62.

Gọi A là một thuật toán tương ứng với một mô hình tính toán, e là bộ dữ liệu vào đã được mã hóa theo cách nào đó. Khi đó thuật toán A tính trên bộ dữ liệu e cần phải trả một giá nhất định bao gồm

a)

Giá thời gian lớn nhất tA(e)

b)

Giá bộ nhớ lớn nhất lA(e)

c)

Giá trung bình về thời gian tA(e) và bộ nhớ lA(e)

d)

Giá thời gian tA(e) và giá bộ nhớ lA(e)

63.

Nếu gọi n là kích thước dữ liệu vào của thuật toán T, thì thời gian thực hiện của thuật toán T có thể biểu diễn một cách tương đối như một hàm của n là

a)

A. T(n)

b)

B. O(n)

c)

C. logn

d)

D. nlogn

64.

Nếu T1(n) và T2(n) là thời gian thực hiện 2 chương trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)). Thời gian thực hiện của 2 chương trình nối tiếp nhau là 

a)

O(f(n) + g(n))T(n)=O(f(n)*g(n)) 

b)

T(n)=O(f(n))*O(g(n)) 

c)

T(n)=O(max(f(n),g(n))

d)

T(n)=max(f(n),g(n)) 

65.

Nếu T1(n) và T2(n) là thời gian thực hiện 2 đoạn chương trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)). Thời gian thực hiện 2 đoạn chương trình lồng nhau:

a)

T(n)=f(n)*g(n)

b)

T(n)=O(f(n))*g(n))

c)

T(n)=O(max(f(n),g(n)))

d)

T(n)=max(f(n),g(n))

66.

Nếu độ phức tạp của lệnh 1 và lệnh 2 đều là O(1) thì độ phức tạp của đoạn chương trình sau: for (i=1 ; i<=n ; i++) {Lệnh 1} for (j=1 ; j<=m ; j++) {Lệnh 2} được xác định bằng:

a)

O(n)

b)

O(m)

c)

O(n*m)

d)

O(max(n,m))

67.

Nếu độ phức tạp của lệnh là O(1) thì độ phức tạp của đoạn chương trình sau: 

for (i=1 ; i<=n ; i++) { 

    for (j=1 ; j<=m ; j++) {lệnh}

    for (k=1 ; k<= h ; k++) {lệnh}

} 

được xác định bằng: 

a)

O(n*m*h) 

b)

O(n+m*h) 

c)

O(n*(m+h)) 

d)

O(n*max(m,h)) 

68.

Nếu độ phức tạp của lệnh là O(1) thì độ phức tạp của đoạn chương trình sau:

for (i=1; i<=n; i++) {lệnh}

được xác định bằng

a)

O(1) 

b)

O(n)

c)

O(logn) 

d)

.O(nlogn) 

69.

Nếu độ phức tạp của lệnh là O(1) thì độ phức tạp của đoạn chương trình sau:

for (i=1; i<=n; i++)

       for (j=1; j<=n; j++)

                              {lệnh}

được xác định bằng 

a)

O(1) 

b)

O(n) 

c)

O(n²)

d)

O(nlogn) 

70.

Nếu T(n) là thời gian thực hiện đoạn chương trình P và T(n)=O(C*f(n)) với C là hằng số, thì

a)

T(n)=O(f(n))

b)

T(n)=O(logf(n)) 

c)

T(n)=O(nlog(f(n))) 

d)

T(n)=O(C*f(n))

71.

Khi xác định độ phức tạp của đoạn chương trình: 

for (i=1 ; i<=n ; i++) 

    for (j=1 ; j<=n ; j++) 

        {lệnh} 

Ta sử dụng quy tắc nào? 

a)

Quy tắc bỏ hằng số 

b)

Quy tắc nhân  

c)

Quy tắc cộng 

d)

Quy tắc lấy max 

72.

chọn đáp án

a)

1. Tính thời gian thực hiện của C1 và C2 

    2. Tính thời gian thực hiện của B 

    3. Tính thời gian thực hiện của A

b)

1. Tính thời gian thực hiện của B, C1 và C2 

    2. Tính thời gian thực hiện của C 

    3. Tính thời gian thực hiện của A 

c)

1. Tính thời gian thực hiện của B 

    2. Tính thời gian thực hiện của C1, C2 

    3. Tính thời gian thực hiện của A 

d)

1. Tính thời gian thực hiện của B, C1 

    2. Tính thời gian thực hiện của C2 

    3. Tính thời gian thực hiện của A

73.

đáp án

a)

1. Tính thời gian thực hiện của B, C3 

    2. Tính thời gian thực hiện của C, C1, C2 

    3. Tính thời gian thực hiện của A 

b)

1. Tính thời gian thực hiện của B, C1, C2 

    2. Tính thời gian thực hiện của C, C3 

    3. Tính thời gian thực hiện của A 

c)

1. Tính thời gian thực hiện của B, C1, C2, C3 

    2. Tính thời gian thực hiện của C 

    3. Tính thời gian thực hiện của A

d)

1. Tính thời gian thực hiện của C1, C2 

    2. Tính thời gian thực hiện của C 

    3. Tính thời gian thực hiện của A 

74.

Hàm f(n) được gọi là O(g(n)) hay có cấp là g(n) nếu tồn tại một hằng số c > 0 và một giá trị n0 sao cho

a)

f(n) ≥ c.g(n) với ∀n ≥ n₀

b)

f(n) ≤ c.g(n) với ∀n ≤ n₀

c)

f(n) < c.g(n) với ∀n ≥ n₀

d)

f(n) ≤ c.g(n) với ∀n ≥ n₀

75.

Xác định độ phức tạp cho đoạn chương trình sau: 

int s=0; 

for (int i=1; i<=n; ++i) 

    for (int j=1; j≤i; ++j) 

        s=s+1; 

printf("%d \n", s); 

a)

O(n) 

b)

O(n²) 

c)

O(logn) 

d)

O(nlogn)

76.

Xác định độ phức tạp cho đoạn chương trình sau: 

if (m<n) p = m; else p = n; 

for (i=0; i<=p; i++) 

    c[i]=a[i] + b[i]; 

if (p<m) 

    for (i=p+1; i<=m; i++) c[i] = a[i]; 

else 

    for (i=p+1; i<=n; i++) c[i] = b[i]; 

while (p>0 && c[p] = 0) p = p-1; 

a)

O(m*n) 

b)

O(max(m,n))

c)

O(m+n)

d)

O(logmn) 

77.

Xác định độ phức tạp cho đoạn chương trình sau: 

for (int i = 0; i < n; i++) { 

    for (int j = 0; j < i; j++) { 

        for (int k = j; k < n; k++) { 

            printf("%d %d %d\n", i, j, k); } } }

a)

O(n) 

b)

O(n²) 

c)

O(n³) 

d)

O(n logn) 

78.

Xác định độ phức tạp cho đoạn chương trình sau: 

s = 1; p = 1; 

for (i=1; i<=n; i++) { 

    p = p * x / i; 

    s = s + p; 

} 

a)

O(n)

b)

O(n²) 

c)

O(logn) 

d)

O(nlogn) 

79.

Xác định độ phức tạp cho đoạn chương trình sau: 

p = m+n; 

for (i=0; i<=p; i++) c[i] = 0; 

for (i=0; i<=m; i++) 

    for (j=0; j<=n; j++) 

        c[i+j] = c[i+j] + a[i] * b[j]; 

a)

O(m*n) 

b)

O(max(m,n))  

c)

O(m+n) 

d)

O(logmn) 

80.

Xác định độ phức tạp cho đoạn chương trình sau: 

for (int i = 0; i < n; i++) { 

    for (int j = 0; j < n; j++) { 

        for (int k = 0; k < logn; k++) { 

            printf("%d %d %d\n", i, j, k);  } } }

a)

O(n log n) 

b)

O(n² log n)

c)

O(logn) 

d)

O(n³) 

81.

Xác định độ phức tạp cho đoạn chương trình sau: 

int i = 0; 

while (i < n) { 

    int j = i; 

    while (j < n) { 

        printf("%d %d\n", i, j); 

        j += 2; }

    i++; 

} 

a)

O(n) 

b)

O(n²)

c)

O(n³) 

d)

O(n log n)

82.

Xác định độ phức tạp cho đoạn chương trình sau: 

for (int i = 0; i < n; i++) { 

    for (int j = 0; j < n / 2; j++) { 

        for (int k = 0; k < 10; k++) { 

            printf("%d %d %d\n", i, j, k); } } }

a)

O(n) 

b)

O(n²)

c)

O(n² *10) 

d)

O(n log n)

83.

Xác định độ phức tạp cho đoạn chương trình sau:

int x = 0, y = 0;

for (int i = 0; i < n; i++) { x=x+10;}

for (int  j = 0; j < m; j++) { y=y+100;}

printf("%d %d \n", x,y);

a)

O(max(n,m)

b)

O(lognm)

c)

O(nlogm)

d)

O(n*m)

84.

Xác định độ phức tạp cho đoạn chương trình sau:

void BS(int a[], int n) {

for(int i=0; i < n - 1 ;i++)

for(int j=n-1; j<i; j-) {

if (a[j] < a[j - 1])

int tg = a[j];a[j] = a[j-1];a[j-1] = tg;

}}}

for(int i=0; i<n; i++){ printf("%d \t",a[i]);}

a)

O(n²)

b)

O(n² logn)

c)

O(n logn)

d)

O(n)

85.

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:

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

a)

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

b)

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

c)

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

d)

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

86.

Cho đoạn chương trình sau (giả sử thao tác trong thân vòng lặp là O(1)):

…

scan(&n);

for(int i = 0; i < n; i++)

for(int j = 0; j<n; j++)

<thao tác trong thân vòng lặp>

Phát biểu nào dưới đây đúng:

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

a)

Tổng số thao tác là O(n²)

b)

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

c)

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

d)

Tổng số thao tác là O(n)

87.

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:

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

a)

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

b)

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

c)

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

d)

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

88.

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 vòng lặp có độ phức tạp O(n) và số lần lặp là n, thì độ phức tạp toàn vòng lặp là:

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

a)

n x O(n)

b)

O(n + n)

c)

O(n²)

d)

O(n)

89.

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(1) thì tổng số lần thao tác O(1) được thực hiện trong đoạn chương trình là:

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

a)

O(n²)

b)

n*n/2

c)

n²

d)

n

90.

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à:

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

a)

O(nlogn)

b)

O(n*n*n)

c)

O(n³)

d)

O(n²)

91.

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)

a)

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

b)

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

c)

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

d)

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

92.

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át biểu nào sau đây là đúng:

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

a)

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

b)

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

c)

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

d)

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

93.

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 là đúng:

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

a)

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

b)

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

c)

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

d)

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

94.

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)

a)

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

b)

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

c)

Vòng lặp lồng nhau

d)

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

95.

Độ 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}.

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

scanf(&a,&b);

while (b!=0) {

r = a % b;

a = b;

b = r;

}

us=a

a)

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

b)

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

c)

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

d)

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

96.

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++)

<thao tác thân vòng lặp>

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:

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

a)

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

b)

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

c)

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

d)

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

97.

Trong một đoạn chương trình có vòng lặp lồng nhau

for ( =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)

a)

O(n)

b)

O(logn)

c)

O(n²)

d)

O((n²) / 4)

98.

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)

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

b)

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

c)

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

d)

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

99.

Thuật toán được biểu diễn bằng lưu đồ khối sau, thực hiện:

a)

Nhập dãy số n phần tử .

b)

Xuất dãy số n phần tử .

c)

Đếm dãy số n phần tử .

d)

Duyệt dãy số n phần tử .

Similar Resources on Wayground

Information Security and Cryptography MCQs

100 questions

Information Security and Cryptography MCQs

quiz

Worksheet

•

University

ML Unit 4& 5 MCQ

100 questions

ML Unit 4& 5 MCQ

quiz

Worksheet

•

University

Đề cương ôn tập CD-LT – Môn: Thiết kế xây dựng mạng LAN

100 questions

Đề cương ôn tập CD-LT – Môn: Thiết kế xây dựng mạng LAN

quiz

Worksheet

•

University

ĐỀ CƯƠNG MẠNG MÁY TÍNH PHẦN 3

103 questions

ĐỀ CƯƠNG MẠNG MÁY TÍNH PHẦN 3

quiz

Worksheet

•

University

Tin CDR

100 questions

Tin CDR

quiz

Worksheet

•

University

Untitled Quiz

101 questions

Untitled Quiz

quiz

Worksheet

•

University

Aventures au CDI

100 questions

Aventures au CDI

quiz

Worksheet

•

6th Grade - University

Bài 9. Giao tiếp an toàn trên Internet

100 questions

Bài 9. Giao tiếp an toàn trên Internet

quiz

Worksheet

•

11th Grade - University