Giảng viên ra đề: (Ngày ra đề) Người phê duyệt: (Ngày duyệt đề)

(Chữ ký và Họ tên) (Chữ ký và họ tên)

Học kỳ / Năm học 1 2022-2023

ÔN TẬP Ngày thi 18-12-2022
Môn học Cấu trúc rời rạc cho KHMT
TRƯỜNG ĐH BÁCH KHOA - ĐHQG-HCM Mã môn học CO1007
KHOA KH & KT MÁY TÍNH Thời lượng 60 phút Mã đề 2210
Ghi chú: - Sinh viên được phép đem theo một tờ A4 viết tay và được dùng máy tính cầm tay.
- Sinh viên nộp lại đề sau khi thi.

In questions 1–7, we consider undirected graph G1 with incidence matrix as follows:

1. 
Which of the following matrices
 is the adjacency matrix
 of G1 ? 
0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0
 1 0 1 1 1 1 0 0 0   1 0 1 1 1 1 0 1 0 
   
 0 1 0 0 1 1 0 0 0   0 1 0 0 1 1 0 1 0 
   
 1 1 0 0 1 0 1 1 0   1 1 0 0 1 0 1 1 0
   

A.  1 1 1 1 0 1 1 1 1  B.  1 1 1 1 0 1 1 1 1
   

 0 1 1 0 1 0 0 1 1   0 1 1 0 1 0 0 1 1
   

 0 0 0 1 1 0 0 1 0   0 0 0 1 1 0 0 1 0
   

   
 0 0 0 1 1 1 1 0 1   0 0 0 1 1 1 1 0 1 
0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0
C. None of them. D. Both of them.
2. What is the chromatic number of graph G1 ?
A. 2 B. 3 C. 4 D. 5
3. Is G1 a bipartie graph?

A. Yes B. No
4. Could we consider G1 as a planar graph?

A. Yes B. No
5. Graph G1 has how many bridges?
A. 0 B. 1 C. 2 D. 3
6. What is the values of κ(G1 ), λ(G1 ) respectively?
A. λ(G1 ) = 3, κ(G1 ) = 3 B. λ(G1 ) = 2, κ(G1 ) = 3 C. λ(G1 ) = 1, κ(G1 ) = 2 D. None of them

7. Which of the following assertions is true for the graph G1 ?

A. The vertex cut of G1 is {C, F }{A, B}{B, C}
B. The edge cut of G1 is {E, F }{D, E}{E, H}
C. The vertex cut of G1 is {D, G}{H, G}{D, H}
D. None of the above assertions is correct

Mã đề: 2210 MSSV: ............................. Họ và tên SV: ....................................................................... Trang: 1

8. Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows:
(i) Select a box
(ii) Choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The
probabilities of selecting boxes P and Q are (1/3) and (2/3), respectively.
Given that a ball selected in the above process is a red ball, the probability that it came from the box P is:

A. 4/19 B. 5/19 C. 2/19 D. 19/30

9. An airline sells 62 tickets for a plane with capacity of 60 passengers. This is done because it is possible for
some people to not show up. The probability of a person not showing up for the flight is 0.1. All passengers
behave independently. Find the probability of the event that the airline does not have to arrange separate
tickets for excess people.
A. 0.788 B. 0.888 C. 0.988 D. 0.688
10. The probability that a person will get an electric contract is 2/5 and probability that he will not get plumbing
contract is 4/7 . If the probability of getting at least one contact is 2/3, what is the probability of getting
both ?
A. 17/105 B. 18/105 C. 17/106 D. 18/106

11. In a batch, there are 80% C programmers, and 40% are Java and C programmers. What is the probability
that a C programmer is also Java programmer?
A. 0.5 B. 0.6 C. 0.7 D. 0.4
12. In a computer science department, a student club can be formed with either 10 members from first year or
8 members from second year or 6 from third year or 4 from final year. What is the minimum no. of students
we have to choose randomly from department to ensure that a student club is formed?
A. 21 B. 25 C. 31 D. 17
13. The following graph below exists:

A. Hamilton circuit and B. Euler path

Euler path
C. Hamilton path D. Hamilton circuit
14. Which of the following graphs is isomorphic to G8 ?

A. C B. A and B. C. D D. B
15. Which one of the following statements is True about the bridge of a graph?
A. A tree has no bridge.
B. Every edge of a complete subgraph with size greater than or equal 3 is a bridge (A
complete subgraph is a subgraph consists of all choosen verticies and its incident
edges).
C. A graph with bridges cannot have a cycle.
D. A bridge cannot be part of a simple cycle.

Mã đề: 2210 MSSV: ............................. Họ và tên SV: ....................................................................... Trang: 2

16. Given the post-fix notations (binary tree): ABC/ − AK/L − ∗ ;Find the pre-fix notation
A. ∗ − A/BC/ − AKL B. ∗ − A/BC − /AKL
C. ∗ − /ABC − /ALK D. ∗ − A/BC − /LAK

17. If P (A|C) > P (B|C) and P (A|C) > P (B|C) then:

A. P (A) > P (B)
B. P (A) = P (B)
C. P (A) ≥ P (B)
D. P (A) ≤ P (B)
18. Consider the following graph G7 in order to find the shortest paths from vertex S to the others by Dijkstra
algorithm. The shortest path from S to T is (path; value) ?

A. S → A → C → D → T ; 11
B. S → D → T ; 10
C. There are more than one shortest path from S to T with the weight is 10
D. The minimum weight is 9
19. A graph G = (V, E) satisfies |E| ≤ 3|V | − 6. The min-degree of G is defined as min {degree(V )}. Therefore,
min-degree of G cannot be
A. 3 B. 4 C. 5 D. 6

Questions from 20–21, consider the following graph G8 in order to find the shortest paths from vertex A to the
others by Bellman-Ford algorithm.
Suppose that columns in the tracing table are ordered (from left to right) in alphabetical order (i.e., A → B → . . .).
Suppose that the initialization row corresponds to step 0.

20. Which of the following is the shortest path from A to G?

A. A → C → B → E → G; total weight = 5
B. Exists a shortest path from A to G with the total weight is 3
C. None of the above answers is correct
D. There exists a circle of negative length
21. Running the algorithm, which is obtained for step 4 ?
A. 0; 1; 3; 5; 2; 4; 7 B. 0; 1; 3; 5; 0; 4; 3 C. 0; 1; 3; 5; 0; 4; 5 D. 0; 3; 3; 5; 5; 4; ∞
22. The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing
order. Which of the following sequences can not be the degree sequence of any graph?
(I) 7,6,5,4,4,3,2,1 ; (II) 6,6,6,6,3,3,2,2 ; (III) 7,6,6,4,4,3,2,2 ; (IV) 8,7,7,6,4,2,1,1
A. I and II B. III and IV C. IV only D. II and IV

Mã đề: 2210 MSSV: ............................. Họ và tên SV: ....................................................................... Trang: 3

23. Which of the following statements is correct?
A. If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex
in G is at least n/3, then G has a Hamiltonian circuit.
B. If G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v) ≥ n/2
for every pair of non-adjacent vertices u and v in G, then G has a Hamiltonian circuit.
C. Both of them are in-correct
D. Both of them are correct
24. Given a binary tree where its pre-order traversal is 1, 2, 4, 5, 3, 6 and its in-order traversal is 4, 2, 5, 1, 6, 3.
Determine post-order traversal of this tree
A. 4, 5, 2, 3, 6, 1 B. 4, 2, 3, 5, 6, 1 C. 4, 6, 3, 2, 5, 1 D. Another solution
25. Which of the following combination can uniquely identify a tree.
A. In-order and Pre-order B. Post-order and Pre-order.
C. A and B are correct D. Non of them

Questions from 26–27, use the following graph G4 .

26. How many minimal spanning tree can be found by using Kruskal’s algorithm?
A. 2 B. 5 C. 3 D. 1
27. The total weight of minimum spanning trees found by Prim’s/ Kruskal’s algorithms is
A. 21 B. 30 C. 41 D. Tất cả đều sai

28. Apply Floyd-Warshall algorithm and determine the stopping matrix for the following graph

8
(G3 )
A 3 B

-4 3
7 2 1
C
E
-6 -5
D
A. L(3) B. L(4) C. L(5) D. L(2)

Mã đề: 2210 MSSV: ............................. Họ và tên SV: ....................................................................... Trang: 4

29. The number of emails arriving in HCMUT’s email server each day is a random variable W getting value
w > 0 (unit 10 emails). We scale W by a discrete random variable X and sort values of X in ascending
order. The values of W and X indicate the server’s load and are shown in the below table:

W 0 < w ≤ 100 100 < w ≤ 800 800 < w ≤ 2000 2000 < w
X 0 1 2 3
P [X = x] a b 0.2 0.05
The densities P [X = x] are estimated using historical data, and code X = 0 means very light load, X = 1
means light load, X = 2 means medium load and X = 3 is high load. You know further that E[X] = 1.
Then the pair (b, a) is
A. (b, a) = (0.3, 0.45)
B. (b, a) = (0.4, 0.35)
C. (b, a) = (0.35, 0.4)
D. (b, a) = (0.45, 0.3)
30. The probability for a hen giving an egg per day is 0.6. What is the minimum number of feeded hens in order
to obtain in daily average not less than 30 eggs?
A. 40. B. 45. C. 50. D. 55.

Mã đề: 2210 MSSV: ............................. Họ và tên SV: ....................................................................... Trang: 5

Solution 2210
1. A.

2. C.

3. B.

4. A.

5. A.

6. A.

7. D.

8. A.

9. C.

10. A.

11. A.

12. B.

13. D.

14. D.

15. D.

16. B.

17. A.

18. C.

19. D.

20. B.

21. C.

22. D.

23. C.

24. D.

25. A.

26. A.

27. A.

28. A.

29. D.

30. C.

Mã đề: 2211 MSSV: ............................. Họ và tên SV: ....................................................................... Trang: 1