wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Phân tích thiết kế thuật toán

Total questions: 78

Worksheet time: 39mins

Name
Class
Date
1.

Thuật toán tìm kiếm nhị phân có thể phân loại phương pháp nào bên dưới

a)

Quy hoạch động

b)

Vét cạn

c)

Tham lam

d)

Chia để trị

2.

có 4 thuật toán A1, A2, A3, A4 có độ phức tạp lần lượt log(n), nlog(n), log(log(n)), n/log(n) thuật toán nào là tốt nhất

a)

A1

b)

A2

c)

A3

d)

A4

3.

Phương pháp quay lui không thể giải quyết bài toán nào

a)

Bài toán mạch Hamiliton

b)

Bài toán người bán hàng

c)

Bài toán n quân hậu

d)

Bài toán tổng tập con

4.

Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân

a)

0(Nlog(N))

b)

Log(N)

c)

1

d)

N

5.

Khi chuyển biểu thức (12 - a) * (b + 9) / (d * 4) sang biểu diễn dạng hậu tố ta được biểu thức nào

a)

/12a - b9 + d4*

b)

12a - b9 + *d4*/

c)

4b d9 + a12 - */

d)

12 - a * b + 9 / d * d

6.

Trong quy hoạch động, kỹ thuật lưu trữ các giá trị tính toán trước đó gọi là

a)

Mapping

b)

Saving value property

c)

Storing value property

d)

Memorization

7.

kết quả chương trình sau:

Thuật toán knapsack:

a)

100

b)

Lỗi thực thi

c)

180

d)

220

8.

Chiến lược giải quyết 1 bài toán bầng cách kết hợp các lời giải tối ưu của các bài toán khác nhau được gọi là

a)

Quy hoạch động

b)

Tham lam

c)

Chia để trị

d)

Đệ quy

9.

Thuật toán qui lui nhanh hơn thuật toán vét cạn

a)

Đúng

b)

Sai

10.

Bạn được cấp không giới hạn 3 tờ tiền có mệnh giá 5, 7, 9 số tiền nào dưới đây bạn không thể ghép được bằng các mệnh giá bên trên

a)

50

b)

21

c)

13

d)

23

11.

Nên sử dụng chiến lược quy hoạch động để giải quyết bài toán nào sau đây

a)

Mergersort

b)

Tìm kiếm nhị phân

c)

Longest common subsequence

12.

Nếu 1 bài toán có thể chia thành các bài toán con được sử dụng lại nhiều lần, thì bài toán đó có tính chất là

a)

Ghi nhớ

b)

Cấu trúc con tối ưu

c)

Tham lam

d)

Các bài toán con gối nhau

13.

Bạn được tặng 1 chiếc balo có thể mang theo trọng lượng 60kg, có 4 vật phẩm lần lượt có trọng lượng 20, 30 40, 70kg - giá trị 70, 80, 90, 200USD. Giá trị tối đa USD của các vật phẩm mà bạn có thể mang bằng cách sử dụng balo là

a)

160

b)

90

c)

200

d)

170

14.

Độ phức tạp về thời gian khi áp dụng thuật toán vét cạn để giải quyết bài toán balo knapsacl là

a)

2^n

b)

n^3

c)

n

d)

n^t

15.

Phương trình đệ quy về tối ưu thời gian tháp HN với N đĩa là

a)

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

b)

T(n) = 2T(N/2) + C

c)

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

d)

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

16.

Có 3 loại tờ tiền với mệnh giá 1, 3, 4 tìm số cách ghép tờ tiền trên để được tổng số tiền là 7, biết rằng số tờ tiền mỗi loại ko giới hạn và thứ tự các tờ tiền không quan trọng

a)

3

b)

4

c)

5

d)

6

17.

Phương pháp nào có thể giải quyết được bài toán balo

a)

Vét cạn

b)

Đệ quy

c)

Quy hoạch động

d)

Tất cả đều đúng

18.

Bước đầu tiên trong giải quyết vấn đề là gì

a)

Xác định vấn đề

b)

Đoán lời giải

c)

Hiểu vấn đề

d)

Không phải đáp án trên

19.

Lợi thế của pp đệ quy so với lặp là gì

a)

Chiếm nhiều bộ nhớ hơn

b)

Viết mã dài hơn

c)

Viết mã ít hơn, dễ triển khai hơn

d)

cần ít bộ nhớ hơn

20.

Cho mảng arr = { 2, 5, 7, 99, 899}, giả sử key = 899. Chúng ta phải thực hiện đệ quy mấy lần để tìm được key(Tìm kiếm nhị phân)?

a)

5

b)

2

c)

3

d)

4

21.

Một bài toán quy hoạch động có những tính chất nào

a)

Các bài toán con gối nhau( overlapping subperoblems)

b)

Cả cấu trúc con tối ưu và các bài toán con gối nhau

c)

Cấu trúc con tối ưu( optimal substructure)

d)

Cách tiếp cận tham lam

22.

Thuật toán Kruskal thường dùng để

a)

Tìm cây khung nhỏ nhất

b)

Tìm đường đi ngắn nhất

c)

Duyệt đồ thị

d)

Tìm chu trình Euler

23.

Lời giải đệ quy của bài toán Tháp Hà Nội là 1 ví dụ minh họa của thuật toán được thiết kế theo chiến lược nào

a)

Quay lui (Backtracking)

b)

Quy hoạch động (Dynamic programming)

c)

Tham lam (Greedy algorithm)

d)

Chia để trị (Divide an conquer)

24.

Hai đại lượng đo chính dùng để đánh giá tính hiệu quả của 1 thuật toán là

a)

Data and space

b)

Complexiry and capacity

c)

Processor and memory

d)

Time and space

25.

Độ phức tạp của hàm fun() là

a)

O(n^2)

b)

O(nLogn)

c)

O(n)

d)

O(nLognLogn)ynamic

26.

Cây không gian trạng thái của bài toán quy hoạch lui được xây dựng bằng cách nào

a)

Breadth-first search

b)

Depth-first search

c)

Nearest neighbour first

d)

Twice around the tree

27.

Khi thuật toán quay lui tìm được 1 lời giải hoàn chỉnh, nó sẽ làm gì

a)

Không làm gì cả

b)

Chuyển qua 1 đường đi khác

c)

Tiếp tục tìm kiếm các lời giải khả thi khác

d)

Quay lại gốc

28.

Thuật toán sắp xếp nào sau đây có thể xem là sự cải tiến của thuật toán sắp xếp cây nhị phân

a)

Heap sort

b)

Quick sort

c)

Selection sort

d)

Insertion sort

29.

Mục tiêu chính của việc sử dụng phương pháp tiếp cận từ trên xuống(top down) trong quy hoạch động đối với 1 bài toán là

a)

Giảm cả độ phức tạp thời gian và không gian

b)

Tăng cả độ phức tạp thời gian và không gian

c)

Giảm độ phức tạp thời gian, tăng độ phức tạp không gian

d)

Tăng độ phức tạp thời gian, giảm độ phức tạp không gian

30.

Cây lựa chọn được xây dựng để triển khai thuật toán quay lui (backtracking) được gọi là

a)

Cây không gian trạng thái (State-space tree)

b)

Cây biểu đồ trạng thái (State-chart tree)

c)

Cây nốt (Node tree)

d)

Cây quay lui (Backtracking tree)

31.

Phát biểu nào sau đây đúng về tính chất của thuật toán?

a)

Thuật toán không cần đầu vào, chỉ cần đầu ra.

b)

Thuật toán phải có tính dừng, tức là kết thúc sau một số hữu hạn bước.

c)

Thuật toán không cần rõ ràng, miễn là cho ra kết quả đúng.

d)

Thuật toán không cần tính đúng đắn.

32.

Trong thuật toán QuickSort, cách chọn chốt (pivot) nào sau đây là hợp lý?

a)

Luôn chọn phần tử đầu tiên làm chốt.

b)

Chọn phần tử có giá trị trung bình trong mảng làm chốt.

c)

Bất kỳ phần tử nào trong mảng cũng có thể được chọn làm chốt.

d)

Chọn phần tử lớn nhất trong mảng làm chốt.

33.

Ba giai đoạn chính của thuật toán quy hoạch động là:

a)

Phân rã, Giải bài toán con, Tổng hợp lời giải.

b)

Giải bài toán con, Ghi nhận kết quả, Tổng hợp lời giải.

c)

Phân rã, Giải các bài toán con và ghi nhận lời giải, Tổng hợp lời giải.

d)

Phân rã, Giải bài toán con, Ghi nhận kết quả.

34.

Cho hai dãy X = <a, b, c, b, d, a, b> và Y = <b, d, c, a, b, a>. Dãy con chung dài nhất của X và Y là:

a)

<b, c, a>

b)

<c, a, b>

c)

<b, c, a, a>

d)

<b, c, b, a>

35.

Khẳng định nào sau đây phù hợp nhất với chiến lược thiết kế tham lam?

a)

Giải thuật thiết kế kiểu từ trên xuống (top-down).

b)

Đưa ra quyết định tốt nhất trong hiện tại và không xem xét lại quyết định trong quá khứ.

c)

Giải thuật thiết kế kiểu từ dưới lên (bottom-up).

d)

Phân chia bài toán ban đầu thành các bài toán con để giải.

36.

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

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(log n)

37.

Trong bài toán cái túi 0-1, phương pháp nào sau đây thường được sử dụng để giải?

a)

Tham lam

b)

Quy hoạch động

c)

Chia để trị

d)

Nhánh và cận

38.

Thuật toán Dijkstra dùng để giải bài toán nào?

a)

Tìm cây bao trùm tối thiểu

b)

Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác

c)

Tô màu đồ thị

d)

Tìm chu trình Hamilton

39.

Thuật toán Kruskal yêu cầu đồ thị phải thỏa mãn điều kiện nào?

a)

Đồ thị phải là có hướng

b)

Đồ thị phải không có chu trình

c)

Đồ thị phải liên thông và không có trọng số âm

d)

Đồ thị có thể có trọng số âm

40.

Thuật toán tham lam phù hợp nhất với bài toán nào sau đây?

a)

Bài toán cái túi 0-1

b)

Bài toán cây bao trùm tối thiểu (Kruskal)

c)

Dãy con chung dài nhất (LCS)

d)

Bài toán người thương gia du hành (TSP)

41.

Giai đoạn nào sau đây không thuộc quy trình của quy hoạch động?

a)

Xác định bài toán con

b)

Ghi nhận kết quả của bài toán con

c)

Phân chia bài toán thành hai phần bằng nhau

d)

Tổng hợp lời giải từ các bài toán con

42.

Kỹ thuật chia để trị (Divide and Conquer) được sử dụng trong thuật toán nào sau đây?

a)

Prim

b)

MergeSort

c)

Knapsack

d)

Dijkstra

43.

Thuật toán quay lui (Backtracking) thường được sử dụng để giải bài toán nào?

a)

Tìm đường đi ngắn nhất

b)

Bài toán N quân hậu

c)

Sắp xếp mảng

d)

Tìm cây bao trùm tối thiểu

44.

Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) là:

a)

O(n)

b)

O(log n)

c)

O(n²)

d)

O(n log n)

45.

Trong thuật toán HeapSort, cấu trúc dữ liệu nào được sử dụng chính?

a)

Mảng

b)

Danh sách liên kết

c)

Heap

d)

Đồ thị

46.

Bài toán tô màu đồ thị (Graph Coloring) thường sử dụng kỹ thuật nào?

a)

Tham lam

b)

Quy hoạch động

c)

Chia để trị

d)

Tìm kiếm nhị phân

47.

Thuật toán nhánh và cận (Branch and Bound) thường được sử dụng để giải bài toán nào?

a)

Sắp xếp mảng

b)

 Bài toán người thương gia du hành (TSP)

c)

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

d)

Tìm cây bao trùm tối thiểu

48.

Độ phức tạp không gian của thuật toán Floyd-Warshall là:

a)

O(n)

b)

O(n²)

c)

O(n³)

d)

O(log n)

49.

Tính chất nào sau đây là bắt buộc đối với một thuật toán?

a)

Có nhiều hơn một đầu ra

b)

Có tính dừng (kết thúc sau số bước hữu hạn)

c)

Không cần tính đúng đắn

d)

Chỉ cần đầu vào, không cần đầu ra

50.

Độ phức tạp thời gian của thuật toán có vòng lặp lồng nhau với n lần lặp cho mỗi vòng là bao nhiêu?

a)

O(n)

b)

O(n²)

c)

O(n log n)

d)

O(log n)

51.

Ký hiệu Big-O biểu thị điều gì trong phân tích thuật toán?

a)

Giới hạn dưới của độ phức tạp

b)

Giới hạn trên của độ phức tạp

c)

Độ phức tạp chính xác

d)

Độ phức tạp trung bình

52.

Thuật toán MergeSort có độ phức tạp thời gian trung bình là bao nhiêu?

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(log n)

53.

Trong thuật toán QuickSort, trường hợp xấu nhất xảy ra khi chốt (pivot) được chọn là:

a)

Phần tử giữa của mảng

b)

Phần tử đầu tiên hoặc cuối cùng trong mảng đã được sắp xếp

c)

Phần tử ngẫu nhiên

d)

Phần tử trung vị

54.

Thuật toán tìm kiếm nhị phân (Binary Search) yêu cầu điều kiện nào sau đây?

a)

Dữ liệu phải được sắp xếp

b)

Dữ liệu phải là danh sách liên kết

c)

Dữ liệu phải là đồ thị

d)

Dữ liệu không cần sắp xếp

55.

Thuật toán tham lam (Greedy) phù hợp nhất với bài toán nào sau đây?

a)

Bài toán cái túi 0-1

b)

Bài toán cây bao trùm tối thiểu (Kruskal)

c)

Dãy con chung dài nhất (LCS)

d)

Bài toán người thương gia du hành (TSP)

56.

Giai đoạn nào sau đây không thuộc quy trình của quy hoạch động?

a)

Xác định bài toán con

b)

Ghi nhận kết quả của bài toán con

c)

Phân chia bài toán thành hai phần bằng nhau

d)

Tổng hợp lời giải từ các bài toán con

57.

Kỹ thuật chia để trị (Divide and Conquer) được sử dụng trong thuật toán nào sau đây?

a)

Prim

b)

MergeSort

c)

Knapsack

d)

Dijkstra

58.

Thuật toán quay lui (Backtracking) thường được sử dụng để giải bài toán nào?

a)

Tìm đường đi ngắn nhất

b)

Bài toán N quân hậu

c)

Sắp xếp mảng

d)

Tìm cây bao trùm tối thiểu

59.

Thuật toán Dijkstra dùng để giải bài toán nào?

a)

Tìm cây bao trùm tối thiểu

b)

Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác

c)

Tô màu đồ thị

d)

Tìm chu trình Hamilton

60.

Độ phức tạp thời gian của thuật toán Prim trong đồ thị có n đỉnh và e cạnh (sử dụng hàng đợi ưu tiên) là:

a)

O(n²)

b)

O(e log n)

c)

O(n log n)

d)

O(e + n)

61.

Thuật toán Kruskal yêu cầu đồ thị phải thỏa mãn điều kiện nào?

a)

Đồ thị phải là có hướng

b)

Đồ thị phải không có chu trình

c)

Đồ thị phải liên thông và không có trọng số âm

d)

Đồ thị có thể có trọng số âm

62.

Trong bài toán cái túi 0-1, phương pháp nào thường được sử dụng để giải?

a)

Tham lam

b)

Quy hoạch động

c)

Chia để trị

d)

Nhánh và cận

63.

Cho hai dãy X = <A, B, C, A> và Y = <B, C, A, B>. Độ dài của dãy con chung dài nhất (LCS) là:

a)

2

b)

3

c)

4

d)

5

64.

Bài toán cái túi phân đoạn (Fractional Knapsack) thường được giải bằng kỹ thuật nào?

a)

Quy hoạch động

b)

Tham lam

c)

Quay lui

d)

Nhánh và cận

65.

Bài toán tô màu đồ thị (Graph Coloring) thường sử dụng kỹ thuật nào?

a)

Tham lam

b)

Quy hoạch động

c)

Chia để trị

d)

Tìm kiếm nhị phân

66.

Thuật toán nhánh và cận (Branch and Bound) thường được sử dụng để giải bài toán nào?

a)

Sắp xếp mảng

b)

Bài toán người thương gia du hành (TSP)

c)

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

d)

Tìm cây bao trùm tối thiểu

67.

Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) là:

a)

O(n)

b)

O(log n)

c)

O(n²)

d)

O(n log n)

68.

Trong thuật toán HeapSort, cấu trúc dữ liệu nào được sử dụng chính?

a)

Mảng

b)

Danh sách liên kết

c)

Heap

d)

Đồ thị

69.

Thời gian thực thi trung bình của thuật toán QuickSort là:

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(log n)

70.

Thuật toán nào sau đây không thuộc kỹ thuật tham lam?

a)

Huffman Coding

b)

Dijkstra’s Algorithm

c)

Dynamic Programming

d)

Kruskal’s Algorithm

71.

Trong bài toán dãy con tăng dài nhất (LIS), phương pháp nào thường được sử dụng?

a)

Tham lam

b)

Quy hoạch động

c)

Chia để trị

d)

Quay lui

72.

Độ phức tạp không gian của thuật toán Floyd-Warshall là:

a)

O(n)

b)

O(n²)

c)

O(n³)

d)

O(log n)

73.

Thuật toán nào sau đây phù hợp để giải bài toán tìm đường đi ngắn nhất trong đồ thị có trọng số âm?

a)

Dijkstra’s Algorithm

b)

Bellman-Ford Algorithm

c)

Prim’s Algorithm

d)

Kruskal’s Algorithm

74.

Trong bài toán cái túi 0-1, nếu sử dụng tham lam, kết quả có luôn tối ưu không?

a)

Có, luôn tối ưu

b)

Không, không luôn tối ưu

c)

Chỉ tối ưu khi không có giới hạn trọng lượng

d)

Tùy thuộc vào cách chọn phần tử

75.

Thuật toán nào sau đây sử dụng hàng đợi ưu tiên?

a)

Breadth First Search (BFS)

b)

Dijkstra’s Algorithm

c)

Depth First Search (DFS)

d)

MergeSort

76.

Độ phức tạp thời gian của thuật toán Bubble Sort trong trường hợp xấu nhất là

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(log n)

77.

Trong quy hoạch động, kỹ thuật nào được sử dụng để tránh tính toán lại các bài toán con đã giải?

a)

Memoization

b)

Greedy Choice

c)

Backtracking

d)

Divide and Conquer

78.

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

a)

Tìm đường đi ngắn nhất

b)

Bài toán người thương gia du hành (TSP)

c)

Sắp xếp mảng

d)

Tìm kiếm nhị phân

Similar Resources on Wayground

1810 - Unit 3 - CH 9 - 12

80 questions

1810 - Unit 3 - CH 9 - 12

quiz

Worksheet

•

University

CNXH

76 questions

CNXH

quiz

Worksheet

•

University

Quizz 1 - 5 | Xây dựng và phát triển thương hiệu | Chiến Pandaz

75 questions

Quizz 1 - 5 | Xây dựng và phát triển thương hiệu | Chiến Pandaz

quiz

Worksheet

•

University

ÔN TẬP

80 questions

ÔN TẬP

quiz

Worksheet

•

12th Grade - University

Ujian Elektronika Digital

80 questions

Ujian Elektronika Digital

quiz

Worksheet

•

University

Four Corners 1, Units 1 - 6 Test

77 questions

Four Corners 1, Units 1 - 6 Test

quiz

Worksheet

•

8th Grade - University

KOMFIL PRELIM/MIDTERM EXAM

77 questions

KOMFIL PRELIM/MIDTERM EXAM

quiz

Worksheet

•

University

Parcial 1: bases científicas y lingüísticas

73 questions

Parcial 1: bases científicas y lingüísticas

quiz

Worksheet

•

University