Font size
WorksheetsTOÁN RỜI RẠC - BÀI 4
Total questions: 30
Worksheet time: 19mins
Một lớp học có 10 học sinh nam và 15 học sinh nữ. Hỏi có bao nhiêu cách chọn một học sinh từ lớp học này?
25
20
10
15
Cho đoạn mã sau: Độ phức tạp thời gian của đoạn mã này là gì?
O(n2 + m)
O(n2)
O(n + m)
O(n * m)
Cho đoạn mã sau: Độ phức tạp thời gian của đoạn mã này là gì?
O(n2)
O(m2)
O(n * m)
O(n + m)
Cho đoạn mã sau: Độ phức tạp thời gian của đoạn mã này là gì?
O(n3)
O(n2)
O(n)
O(n log n)
Cho đoạn mã sau: Độ phức tạp thời gian của đoạn mã này là gì?
O(n/m)
O(max(n, m))
O(min(n, m))
O(n * m)
Cho đoạn mã sau: Độ phức tạp thời gian của đoạn mã này là gì?
O(n)
O(n2)
O(n3)
O(n log n)
Cho đoạn mã sau: Độ phức tạp thời gian của đoạn mã này là gì?
O(n1/n2)
O(min(n1,n2))
O(n1 * n2)
O(n1 + n2)
Trường học có 100 học sinh. Trong đó, có 50 học sinh biết lập trình Python, 30 học sinh biết lập trình Java và 10 học sinh biết lập trình cả hai ngôn ngữ.
Có bao nhiêu học sinh trong trường biết lập trình ít nhất một ngôn ngữ?
(a)
Có bao nhiêu học sinh không biết lập trình Python và cũng không biết lập trình Java?
(a)
Trong một cuộc khảo sát, có 100 người thích trà, 80 người thích cả phê và 40 người thích cả hai. Hỏi có bao nhiêu người thích ít nhất một trong hai loại đồ uống này?
120
140
160
100
Một trường đại học có 400 sinh viên biết tiếng Anh, 300 sinh viên biết tiếng Pháp và 100 sinh viên biết cả hai ngôn ngữ. Hỏi có bao nhiêu sinh viên biết ít nhất một ngôn ngữ?
700
500
400
600
Thuật toán sinh được sử dụng để làm gì?
Để nhân đôi kích thước của một mảng
Để tìm kiếm phần tử trong mảng đã sắp xếp
Để sắp xếp một danh sách các số
Để liệt kê tất cả các hoán vị của một tập hợp
Thuật toán sinh tổ hợp k phần tử từ n phần tử (1 ≤ k ≤ n) là gì?
Sinh tất cả các số nguyên tố nhỏ hơn n
Sinh tất cả các hoán vị của n phần tử
Sinh tất cả các tập con có k phần tử từ n phần tử
Sinh tất cả các dãy con liên tiếp từ một dãy có n phần tử
Thuật toán sinh dãy nhị phân độ dài n có độ phức tạp thời gian là bao nhiêu?
O(n)
O(n!)
O(2n)
O(n log n)
Thuật toán nào sau đây có thể được sử dụng để sinh tất cả các hoán vị của một tập hợp n phần tử?
Thuật toán Binary Search
Thuật toán Bubble Sort
Thuật toán quay lui (Backtracking)
Thuật toán Quicksort
Thuật toán quay lui thường được sử dụng để giải quyết loại bài toán nào?
Sắp xếp một danh sách các số
Tính toán giá trị của một hàm toán học
Tạo ra tất cả các tổ hợp hoặc hoán vị thỏa mãn một điều kiện nào đó
Tìm kiếm tuần tự trong một danh sách
Trong bài toán "N‑Queens", thuật toán quay lui được sử dụng để làm gì?
Sắp xếp các quân hậu theo thứ tự từ nhỏ đến lớn
Tìm đường đi ngắn nhất trên bàn cờ
Tìm tổng số quân hậu có thể đặt trên bàn cờ
Tìm tất cả các cách sắp xếp N quân hậu trên bàn cờ N x N sao cho không quân hậu nào tấn công nhau
Thuật toán quay lui có thể được sử dụng để giải bài toán nào sau đây?
Sắp xếp nhanh (Quicksort)
Tìm kiếm nhị phân
Giải câu đố Sudoku
Tính tích các phần tử trong mảng
Trong thuật toán quay lui liệt kê dãy nhị phân, khi nào thì thuật toán sẽ quay lui (backtrack)?
Khi tìm được hai dãy nhị phân
Khi chưa tìm thấy một lời giải
Khi đã tìm thấy một lời giải có bit 1 đứng đầu
Khi đã tìm thấy một lời giải hoặc khi gặp phải một bước không thể tiếp tục đi sâu thêm
Trong bài toán tìm đường đi mê cung, thuật toán quay lui hoạt động như thế nào?
Tính tổng số bước đi cần thiết để đi từ điểm bắt đầu đến điểm kết thúc
Thử tất cả các bước đi có thể từ điểm hiện tại và quay lui nếu gặp ngõ cụt
Tìm đường đi ngắn nhất từ điểm bắt đầu đến điểm kết thúc
Tìm tất cả các đường đi có thể từ điểm bắt đầu đến điểm kết thúc
Khi giải bài toán phân chia tập hợp thành hai phần có tổng bằng nhau bằng thuật toán quay lui, thuật toán sẽ làm gì?
Tìm tất cả các cách chia tập hợp thành hai phần bất kỳ
Tính tổng của tập hợp và chia đôi kết quả để tìm hai phần
Chọn lần lượt từng phần tử và thử đặt nó vào một trong hai phần, quay lui nếu không thành công
Sắp xếp tập hợp theo thứ tự tăng dần và sau đó chia đôi
Khi giải bài toán phân chia tập hợp thành hai phần có tổng bằng nhau bằng thuật toán quay lui, thuật toán sẽ làm gì?
Tìm tất cả các cách chia tập hợp thành hai phần bất kỳ
Tính tổng của tập hợp và chia đôi kết quả để tìm hai phần
Chọn lần lượt từng phần tử và thử đặt nó vào một trong hai phần, quay lui nếu không thành công
Sắp xếp tập hợp theo thứ tự tăng dần và sau đó chia đôi
Cho tập A = {0, 1, 2, 3}. Có bao nhiêu số chẵn, mỗi số gồm 3 chữ số khác nhau được thành lập từ A?
8
12
6
10
Cho thuật toán sau:
Hãy cho biết thuật toán trên có chức năng làm gì?
Liệt kê các chỉnh hợp chập K của N
Liệt kê các tổ hợp chập K của N
Liệt kê các hoán vị của tập gồm N phần tử
Liệt kê các chỉnh hợp lặp chập K của N
Cho chương trình sau:
Hãy cho viết trong thủ tục để quy thực hiện thuật toán quay lui, việc kiểm tra điều kiện chấp nhận phương án để cử cho cấu hình bộ phận thứ i thể hiện dòng lệnh thứ bao nhiêu?
21
Không có lệnh kiểm tra điều kiện chấp nhận
25
22
Hãy cho biết, trong các đặc điểm sau, đặc điểm nào là thế mạnh của thuật toán quy lui so với thuật toán sinh?
Trong quá trình thử các cấu hình, thuật toán tránh được phải thử nhiều trường hợp chưa hoàn chỉnh, điều này làm giảm thời gian thực hiện thuật toán
Chi phí không gian lưu trữ thấp
Dễ cài đặt
Độ chính xác cao
Cho tập A = {0,2,4,6,8}. Có bao nhiêu số gồm 4 chữ số khác nhau được thành lập từ A?
5
96
120
24
Hỏi trong tập X = {1, 2, ..., 1000} có bao nhiêu số không chia hết cho bất cứ số nào trong các số 3, 4, 7?
429
571
725
165
Hỏi trong tập X = {1, 2, ..., 10000} có bao nhiêu số chia hết cho một trong các số 2, 5, 9?
6445
8111
1777
3555
Cho thuật toán sau:
Hãy cho biết, thuật toán có chức năng làm gì?
Liệt kê các tổ hợp của tập B
Đếm số hoán vị gồm N phần tử lấy từ tập B
Liệt kê chỉnh hợp
Liệt kê các hoán vị của tập B
01111110
11111111
10000001
10000000
