Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Chương 2: Hiểu.
Thuật toán đệ quy, quay lui
Câu 1
Một giải thuật đệ qui được thực hiện thông qua hai bước:
A)
Bước phân tích và bước thay thế ngược lại
B)
Bước tính toán và phân tích
C)
Bước thay thế ngược lại và phân tích
D)
Bước phân tích và bước tính toán
Đáp án
A
Câu 2
Khi thiết kế thuật toán đệ quy thì ta cần xác định các yêu cầu sau
A)
Xác định được phần cơ sở và phần đệ quy
B)
Xác định được phần cơ sở và phần truy hồi
C)
Xác định được phần suy biến và phần quy nạp
D)
Xác định được phần dừng và phần lặp vô hạn
Đáp án
A
Các nguyên lý đếm
Câu 1
Cho tập A1, A2 với N(A1)=12, N(A2)=18,
21 AA
.
N(
21 AA
)=
A)
18
B)
12
C)
30
D)
6
Đáp án
C
Câu 2
Cho tập A1, A2 với N(A1)=12, N(A2)=18,
1
21 AA
.
N(
21 AA
)=
A)
30
B)
18
C)
12
D)
29
Đáp án
D
Câu 3
Cho tập A1, A2 với N(A1)=15, N(A2)=18,
6
21 AA
.
N(
21 AA
)=
A)
33
B)
27
C)
18
D)
15
Đáp án
B
Câu 4
Cho tập A1, A2 với N(A1)=12, N(A2)=18,
.
Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
N(
21 AA
)=
A)
18
B)
30
C)
12
D)
0
Đáp án
A
Câu 5
Cho biết số phần tử của
321 AAA
nếu mỗi tập có 100 phần tử và
các tập hợp là đôi một rời nhau?
A)
200
B)
300
C)
100
D)
0
Đáp án
B
Câu 6
Cho biết số phần tử của
321 AAA
nếu mỗi tập có 100 phần tử và
nếu có 50 phần tử chung của mỗi cặp 2 tập và có 10 phần tử chung
của cả 3 tập?
A)
250
B)
160
C)
200
D)
300
Đáp án
B
Câu 7
Giả sử trong một nhóm 6 người mỗi cặp hai người hoặc là bạn, hoặc
là thù của nhau. Khi đó:
A)
Trong nhóm không tồn tại ba người là bạn của nhau hoặc là kẻ thù
của nhau.
B)
Trong nhóm có ba người là bạn của nhau hoặc là kẻ thù của nhau.
C)
Có ba người là thù của nhau
D)
Có ba người là bạn của nhau
Đáp án
B
Tổ hợp, hoán vị
Câu 1
Số hàm từ tập có k phần tử vào tập có n phần tử.
A)
( nk)
`B)
(n -k)!
C)
( kn )
D)
( n! / k!)
Đáp án
A
Câu 2
Cho n là số nguyên dương, khi đó
n
k
knC
0
).(
là
A)
2n-1
B)
2n
C)
2n+1
D)
2n -1
Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Đáp án
B
Câu 3
Cho n và k là các số nguyên dương với
kn
. Khi đó:
A)
C(n+1,k) = C(n,k-1) + C(n,k)
B)
C(n+1,k) = C(n-1,k)+ C(n-1,k-1)
C)
C(n+1,k) = C(n,k) + C(n-1,k)
D)
C(n+1,k) = C(n-1,k-1) + C(n, k-1)
Đáp án
A
Câu 4
Cho x,y là 2 biến và n là một số nguyên dương. Khi đó :
A)
n
j
jjnn yxjnCyx
0
),()(
B)
n
j
jjnn yxjnCyx
1
),()(
C)
n
j
jnn yxjnCyx
0
),()(
D)
n
j
jnjn yxjnCyx
0
),()(
Đáp án
A
Câu 5
Hệ số của x12y13 trong khai triển (x+y)25 là :
A)
25!
B)
!12!13
!25
C)
!12
!13
D)
!13
!25
Đáp án
B
Câu 6
Cho n là số nguyên dương, khi đó
n
k
kknC
0
),()1(
là:
A)
1
B)
-1
C)
0
D)
2
Đáp án
C
Câu 7
Hoán vị nào dưới đây là hoán vị kế tiếp của hoán vị 2 1 3 4 5 6 7 8 9
A)
2 3 1 4 5 6 7 8 9
B)
2 1 4 3 5 6 7 8 9
C)
2 1 3 4 5 6 7 9 8
D)
3 1 2 4 5 6 7 8 9
Đáp án
C
Câu 8
Cho n, r là các số nguyên không âm sao cho r <= n. Khi đó:
A)
C(n,r) = C(n+r-1,r)
Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B)
C(n,r) = C(n, r-1)
C)
C(n,r) = C(n,n-r)
D)
C(n,r) = C(n-r,r)
Đáp án
C
Chương 2. Biết.
Thuật toán và các đặc trưng
Câu 1
Thuật toán được định nghĩa :
A)
Là một dãy các bước mỗi bước mô tả các thao tác được thực hiên để giải
quyết bài toán
B)
Là một dãy vô hạn các bước mỗi bước mô tả các thao tác được thực hiên
để giải quyết bài toán ban đầu.
C)
Là một dãy hữu hạn các bước, mỗi bước mô tả chính sách 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)
Là một dãy tuần tự các bước được thực hiên để giải quyết bài toán
Đáp án
C
Câu 2
Khi xây dựng một thuật toán cần chú ý đến các đặc trưng sau đây:
A)
Nhập, xuất, tính xác định, tính hữu hạn, tính hiệu quả, tính đúng đắn
B)
nhập, xuất, tính xác định, tính hiệu quả, tính tổng quát, tính đúng đắn
C)
nhập, xuất, tính xác định, tính hữu hạn, tính hiệu quả, tính tổng quát, tính
đúng đắn.
D)
xuất, tính xác định, tính hữu hạn, tính hiệu quả, tính tổng quát, tính đúng đắn
Đáp án
C
Câu 3
Các phương pháp thường dùng để biểu diễn thuật toán trước khi viết
chương trình là:
A)
Dùng ngôn ngữ tự nhiên, dùng ngôn ngữ lập trình, viết chương trình
B)
Dùng sơ đồ khối, dùng ngôn ngữ lập trình, viết chương trình
C)
Dùng ngôn ngữ tự nhiên, dùng ngôn ngữ lập trình, dùng mã nhị phân
D)
Dùng ngôn ngữ tự nhiên, dùng sơ đồ khối, dùng giả mã
Đáp án
D
Đệ quy và quay lui
Câu 1
Liệt kê là phương pháp:
A)
Đưa ra một công thức cho lời giải bài toán
B)
Chỉ ra nghiệm tốt nhất theo một nghĩa nào đó của bài toán.
C)
Đưa ra danh sách tất cả các cấu hình tổ hợp có thể có.
D)
Chỉ ra một nghiệm hoặc chứng minh bài toán không có nghiệm
Đáp án
C
Câu 2
Một thuật toán liệt kê phải đảm bảo:
A)
Không duyệt các cấu hình không thuộc tập các cấu hình
Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B)
Không bỏ xót và không lặp lại bất kì một cấu hình nào.
C)
Không bỏ xót một cấu hình nào.
D)
Không duyệt lại các cấu hình đã duyệt
Đáp án
B
Câu 3
Định nghĩa bằng đệ qui là phương pháp:
A)
Định nghĩa đối tượng thông qua chính nó.
B)
Định nghĩa đối tượng thông qua các đối tượng trừu tượng.
C)
Định nghĩa đối tượng thông qua các đối tượng đã xác định
D)
Định nghĩa đối tượng thông qua các đối tượng khác.
Đáp án
A
Câu 4
Nội dung chính của thuật toán quay lui là:
A)
Xây dựng toàn bộ các thành phần của cấu hình bằng cách thử tất cả các
khả năng
B)
Xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả
năng.
C)
Xây dựng mỗi thành phần của cấu hình bằng cách thử tất cả các khả
năng
D)
Xây dựng bất kì thành phần nào của cấu hình bằng cách thử tất cả các
khả năng
Đáp án
B
Câu 5
Thuật toán được qọi là đệ quy nếu
A)
giải quyết bài toán bằng cách chia nhỏ bài toán ban đầu tới các bài toán cơ sở
B)
giải quyết bài toán bằng cách chia đôi bài toán ban đầu thành các bài toán
con
C)
giải quyết bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán
cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn.
D)
giải quyết bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán
cũng như vậy nhưng có dữ liệu đầu vào bằng một nửa.
Đáp án
C
Câu 6
Cấu trúc của chương trình con đệ quy qồm:
A)
Phần dễ giải quyết và phần khó giải quyết
B)
Phần cơ sở và phần đệ quy
C)
Phần cơ sở và phần quy nạp
D)
Phần hữu hạn và phần quy nạp
Đáp án
B
Các nguyên lý đếm
Câu 1
Nội dung của nguyên lý Dirichlet được phát biểu :
A)
Nếu A và B là hai tập hợp thì :
B)
Nếu có N đồ vật được đặt vào K hộp thì sẽ tồn tại một hộp chứa ít
nhất hộp
C)
Nếu A và B là hai tập hợp rời nhau thì :
D)
Nếu A và B là hai tập hợp thì :
Đáp án
B