Phần 1
Câu 11:
Có bao nhiêu cách xếp 5 người vào một băng ghế có 7 chỗ?
A. 2520
B. 21
C. 120
D. 5040

Câu 12:
Cho tập các chữ số {0, 1, 2, 3, 4, 5}. Có bao nhiêu số có 3 chữ số khác nhau được tạo thành từ tập
đã cho?
A. 120

B. 100

C. 90

D. Tất cả đều sai

Câu 13:
Có bao nhiêu cách chọn 4 đề thi khác nhau trong bộ đề có 10 đề thi cho 4 đợt thi (mỗi đợt thi sử
dụng 1 đề)?
A. 210

B. 840

C. 5040

D. Tất cả đều sai

Câu 14:

Giả sử có tám vận động viên chạy thi. Người về nhất sẽ được nhận huân chương vàng, người về
nhì nhận huân chương bạc, người về ba nhận huy chương đồng. Có bao nhiêu cách trao huy chương
nếu tất cả các kết cục đều có thể xảy ra?
A. 56

B. 336

C. 24

D. Tất cả đều sai

Câu 15:
Một nhóm học sinh có 7 em nam và 3 em nữ. Người ta cần chọn ra 5 em trong nhóm tham gia
đồng diễn thể dục. Trong 5 em được chọn, u cầu khơng có q một em nữ. Hỏi có bao nhiêu
cách chọn?
A. 252
B. 21
C. 126
D. Tất cả đều sai

Câu 16:
Cho A = {1,2,3,4,5,6,7,8,9}. Có bao nhiêu tập con của A có chứa phần tử 1?
A. 128
B. 256
C. 64
D. 512
Câu 17:
Có bao nhiêu cách xếp 4 công nhân từ 10 công nhân vào 4 công việc khác nhau?
A. 5040
B. 400

C. 5060
D. 24
Câu 18:
Có bao nhiêu số chẵn có 2 chữ số mà 2 chữ số đó khác nhau:


A. 40

B. 41

C. 45

D. Tất cả đều sai

Câu 19:
Có bao nhiêu xâu nhị phân độ dài 8 không chứa 6 số 0 liền nhau?
A. 64
D. 128
B. 246
C. 256
Câu 20:
Có 8 người đi vào thang máy của một tòa nhà 13 tầng. Hỏi có bao nhiêu cách để mỗi người đi vào
một tầng khác nhau
A. 51891800
B. 51891820
C. 51891840
D. 51891860
Câu 21:
Có 8 người đi vào thang máy của một tòa nhà 13 tầng. Hỏi có bao nhiêu cách để 8 người này, mỗi
người đi vào 1 tầng bất kì nào đó

A. 813
B. 138
C. 8!
D. 13!
Câu 22:
Trong các số nguyên dương có đúng 3 chữ số, có bao nhiêu số chia hết cho 3 nhưng không chia
hết cho 4
A. 128
B. 225
C. 450
D. Tất cả đều sai


Phần II
Câu 1:
Sau khi thực hiện đoạn lệnh sau:
S =0;
for ( int i = 1; i <= 3; i++)
for ( int j =5; j >= 3; j--)
S = S + 1;
S có giá trị bằng bao nhiêu
A. 6
B. 7
C. 8

D. 9

Câu 2:
Hoán vị theo thứ tự từ điển đi liền sau hoán vị 45321 là:
A. 51234


B. 45312

C. 45231

D. 54321

Câu 3:
Dãy nhị phân đi liền sau dãy 1 0 1 1 1 là:
A. 1 1 1 1 0

B. 1 0 1 1 0

C. 1 1 0 0 0

D. 1 1 0 0 1

Câu 4:
Tìm tổ hợp chập 4 từ tập {1, 2, 3, 4, 5, 6} đi liền sau tổ hợp {1, 3, 4, 6} là:
A. {1, 3, 4, 5}

B. {1, 4, 5, 6}

C. {1, 3, 5, 6}

D. {1, 4, 3, 6}

Câu 5:
Hoán vị theo thứ tự từ điển đi liền sau hoán vị 51342 là:
A. 51423

B. 51324
C. 51432
D. 51243
Câu 6:
Dãy nhị phân đi liền sau dãy 1 1 0 0 1 1 là:
A. 1 1 0 0 0 1
B. 1 1 0 0 1 0
C. 1 1 0 1 0 0

D. 1 1 0 1 0 1

Câu 7:
Tìm tổ hợp chập 3 từ tập {1, 2, 3, 4, 5, 6} đi liền sau tổ hợp {1, 5, 6} là:
A. {1, 6, 5}
B. {2, 5, 6}
C. {2, 3, 4}
D. {6, 5, 1}
Câu 8:
Mỗi sinh viên trong một trường đại học đều có 1 quê ở trong 50 thành phố. Cần phải tuyển bao
nhiêu sinh viên để đảm bảo có ít nhất 100 người cùng thành phố
A. 4951
B. 5000
A. 495
D. Tất cả đều sai


Câu 9:
Một lớp có 50 học sinh. Phải có ít nhất bao nhiêu học sinh có tháng sinh giống nhau?
A. 4
B. 5

C. 6
D. 7
Câu 10:
Giải bài toán cái túi
f(x) = 10x1 + 5x2 + 3x3 + 6x4  max,
5 x1 + 3 x2 + 2 x3 + 4 x4  8,
xj  Z+ , j =1, 2, 3, 4.
theo thuật toán nhánh cận ta được nghiệm trị tối ưu:
A. f* = 13
B. f* = 14
C. f* = 15

D. Tất cả đều sai

Câu 11:
Giải bài toán cái túi sau theo thuật toán nhánh cận
f(x) = 10x1 + 4x2 + 3x3 + 6x4 + x5  max
4x1 + 2x2 + 2x3 + 4x4 + x5  23,
xj  Z+ , j =1, 2, 3, 4, 5.
theo thuật toán nhánh cận ta được nghiệm trị tối ưu:
A. f* = 50
B. f* = 55
C. f* = 60

D. Tất cả đều sai

Câu 12:
Giải bài toán người du lịch với ma trận chi phí sau:

Ta được Chi phí nhỏ nhất là

A. 20
B. 23

C. 25

Câu 13:

Giải bài tốn người du lịch với ma trận chi phí sau:

D. Tất cả đều sai


Ta được Chi phí nhỏ nhất là
A. 81
B. 104

D. Tất cả đều sai

C. 114

Câu 14:

Thời gian gia công các chi tiết trên các máy được cho trong bảng sau:

Sử dụng thuật tốn Jonhson ta tìm được lịch gia cơng tối ưu với thời gian hồn thành việc gia cơng
là
A. T(π) = 26
A. T(π) = 28
A. T(π) = 30
D. Tất cả đều sai

Câu 15:

Hệ thức truy hồi cho số các cách đi lên n bậc thang nếu một người có thể bước 1 hoăc 2 bậc một
lần là
A. an = an-1+ an-2
B. an = an-1+ 2an-2
C. an = 2an-1+ an-2
D. Tất cả đều sai
Câu 16:

Giả sử số vi trùng trong một quần thể sẽ tăng gấp 3 sau mỗi giờ. Công thức truy hồi tính số vi
trùng sau n giờ là
A. an = an-1

B. an = 3+ an-1

C. an = 3an-1

D. Tất cả đều sai

Câu 17:

Hệ thức truy hồi để tim số lần di chuyển đĩa ít nhất cần thực hiện để thực hiện xong nhiệm vụ đặt
ra trong trò chơi tháp Hà nội là
A. hn = 2hn-1
sai

B. hn = 2hn-1 + 1

C. hn = 2hn-1 - 1


Câu 18:

Hệ thức truy hồi để tính số các xâu nhị phân độ dài n khơng có hai số 0 liên tiếp là

D. Tất cả đều


A. an = an-1 + an-2

A. an = an-1 - an-2

A. an = an-1 * an-2

Câu 19:

Nghiệm của hệ thức truy hồi an = an-1+ 2an-2 với a0 = 2, a1 = 7 là
A. 𝑎𝑛 = 3.2𝑛
B. 𝑎𝑛 = 3.2𝑛 + (−1)𝑛
C. 𝑎𝑛 = 3.2𝑛 − (−1)𝑛
D. Tất cả đều sai
Câu 20:

Nghiệm của hệ thức truy hồi an = 6an-1 - 9an -2 ,với a0=1, a1=6 là
A. 𝑎𝑛 = 3𝑛
B. 𝑎𝑛 = 3𝑛 + 𝑛(3)𝑛
C. 𝑎𝑛 = 3𝑛 − 𝑛(3)𝑛
D. Tất cả đều sai

D. Tất cả đều sai



Phần 3
Câu 11:

Đồ thị sau có mấy chu trình Euler

A. 0

B. 1

C. 2

D. Tất cả đều sai

Câu 12:
Trong các các đồ thị sau đồ thị nào là đồ thị phẳng:

G1

A. G1

B. G2

G2

C. G3

D. Cả 3 đồ thị trên


Câu 12:
Đồ thị phân đơi đầy đủ Kn,m có bao nhiêu đỉnh và bao nhiêu cạch
A. Có n+m đỉnh, n+m cạnh
B. Có n*m đỉnh, n+m cạnh
C. Có n*m đỉnh, n*m cạnh
D. Có n+m đỉnh, n*m cạnh

G3


Câu 13:
Với đồ thị sau

Đâu khơng phải là chu trình Hamilton
A. 1, 4, 2, 5, 3, 6, 1
B. 3, 6, 2, 5, 1, 4, 3
C. 2, 5, 3, 6, 1, 4, 2
D. 1, 5, 2, 3, 4, 6, 1

Câu 14:
Cho đồ thị G có trọng số như hình sau

G là đồ thị có phải đồ thị Euler khơng? Vì sao?
A. Có vì các đỉnh của đồ thị đều có bậc chẵn
B. Khơng, vì nó chứa các đỉnh bậc lẻ (a,k,m,c,d,h)
C. Khơng, vì nó chứa các đỉnh bậc chẵn (a,k,m,c,d,h)
D. Có, vì nó chứa các đỉnh bậc chẵn (a,k,m,c,d,h)

Câu 15:
Chu trình Hamilton là…?



A. Chu trình sơ cấp đi qua tất cả các cạnh của đồ thị
B. Là chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần
C. Chu trình đơn đi qua tất cả các đỉnh của đồ thị
D. Là chu trình sơ cấp đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần

Câu 16:
Hãy cho biết đồ thị nào sau đây là đồ thị Euler?

A. Đồ thị A
B. Đồ thị B
C. Đồ thị C
D. Đồ thị D

Câu 17:
Cây là đồ thị vơ hướng liên thơng…?
A. Khơng có chu trình Hamilton
B. Khơng có đỉnh treo
C. Khơng có chu trình
D. Khơng có chu trình Euler.

Câu 18:
Giả sử G=(V,E) là đồ thị vơ hướng liên thơng có n đỉnh. T là cây khung (cây bao trùm) của đồ thị G.
Khẳng định nào sau đây khơng tương đương với các khẳng định cịn lại?
A. T liên thơng, khơng có chu trình
B. T liên thơng, có n-1 cạnh
C. T khơng có chu trình, có n-1 cạnh
D. T liên thơng và các đỉnh đều có bậc chẵn


Câu 19:
Phát biểu nào sau đây là chính xác nhất:
Cho đồ thị G =<V,E>. Chu trinh đơn trong G là:
A. Chu trình mà trong chu trình đó mỗi cạnh xuất hiện đúng một lần.
B. Chu trình mà trong chu trình đó mỗi đỉnh xuất hiện đúng một lần.
C. Chu trình đi qua tất cả các cạnh của G.
D. Chu trình đi qua tất cả các đỉnh của G.


Câu 20:
Phát biểu nào sau đây là chính xác nhất:
Cho đồ thị G =<V,E>. Chu trinh đơn trong G là:
A. Chu trình mà trong chu trình đó mỗi cạnh xuất hiện đúng một lần.
B. Chu trình mà trong chu trình đó mỗi đỉnh xuất hiện đúng một lần.
C. Chu trình đi qua tất cả các cạnh của G.
D. Chu trình đi qua tất cả các đỉnh của G.


Phần 4
Câu 3:
Luồng cực đại từ nguồn phát s tới nguồn thu t trong đồ thị sau là bao nhiêu:

A. 27

B. 28

C. 29

D. 30


Câu 4:
Đồ thị sau có bao nhiêu cây khung khác nhau

A. 12

B. 14

C. 16

D. 18

Câu 7:
Áp dụng thuật tốn Ford-Bellman để tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị
sau. Khi k=1 thì d[2], Truoc[2] là cặp giá trị nào sau đây:


A. 4, 1

B. 3, 4

C. 2, 1

D. Tất cả đều sai

Câu 9:
Xét đồ thị sau, hãy cho biết phần tử [4, 1] của ma trận D cuối cùng sau khi thực hiện thuật tốn Floyd để
tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại của đồ thị này.

A. 8


B. 9

C. 10

D. 11

Câu 10:
Xét đồ thị sau, hãy cho biết phần tử [1, 3] của ma trận d cuối cùng sau khi thực hiện thuật toán Floyd
trên đồ thị này.

A. 5

Câu 11:

B. 6

C. 7

D. 8


Xét đồ thị sau, hãy cho biết phần tử [3, 2] của ma trận d cuối cùng sau khi thực hiện thuật toán Floyd trên
đồ thị này.

A. 8

B. 9

C. 10


D. 11

Câu 12:
Xét đồ thị sau, hãy cho biết phần tử [3, 2] của ma trận p cuối cùng sau khi thực hiện thuật toán Floyd trên
đồ thị này.

A. 1

B. 2

C. 3

D. 4

Câu 13:
Xét đồ thị với ma trận như sau, hãy cho biết phần tử [3, 2] của ma trận d cuối cùng sau khi thực hiện thuật
toán Floyd trên đồ thị này

0

6


4
0
11
1

A. 8
Câu 14:


8
3
0
5
B. 9

2
7

0
C. 10

D. 11


Đường đi ngắn nhất từ đỉnh a đến đỉnh z có độ dài là

A. 14

B. 15

C. 16

D. 17

Câu 16:
Cho đồ thị G như hình vẽ, cây khung nhỏ nhất tìm được theo thuật toán Prim là?



A. T={(3,4),(3,6),(2,3),(3,5),(5,6),(5,8),(8,11),(8,9),(9,10),(1,2)}
B. T={(3,4),(3,6),(2,3),(6,10), (5,6),(5,8), (8,11),(8,9),(9,10),(1,2)}
C. T={(3,4),(3,6),(2,3),(6,7), (5,6),(6,8), (8,11),(8,9),(9,10),(1,2)}
D. T={(3,4),(3,6),(2,3),(6,7), (5,6),(5,8), (8,11),(8,9),(9,10),(1,2)}

Câu 18:
Cho đồ thị như hình vẽ:

Thuật tốn Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại, nhãn cực tiểu của đỉnh 5
là bao nhiêu?
A. 14
B. 11
C. 6
D. 13


Câu 19:
Thứ tự nào sau đây là thứ tự duyệt cây sau đây bằng các thuật toán duyệt tiền tự

A. d, b, g, e, a, c, i, h, j, f
B. a, b, d, e, g, c, f, h, i, j
C. d, g, e, b, i, j, h, f, c, a
D. Tất cả đều sai