TRƯỜNG ĐẠI HỌC BÁCH KHOA Họ tên: _____________
KHOA KHOA HỌC & KỸ THUẬT MÁY TÍNH MSSV: _____________
—————————————————
ĐỀ KIỂM TRA HỌC KỲ 1 - NIÊN KHÓA 2016-2017
Môn thi: Cấu trúc rời rạc cho KHMT Thời gian làm bài: 90 phút
Mã đề thi: 1611 Đề thi gồm 5 trang. Được phép dùng tài liệu.
Không được viết nháp vào đề. Thang điểm cao nhất là 10.
Với câu hỏi trắc nghiệm, sinh viên chọn đáp án chính xác nhất .
Với phần điền vào chỗ trống, sinh viên trả lời trực tiếp vào đề thi và nộp lại đề sau khi làm bài.
Trong các câu 1–6, xét đồ thị vô hướng G1có ma trận kề (adjacency matrix) như sau:
A B C D E F G H I
A
B
C
D
E
F
G
H
I
011001100
100000110
100111000
001010000
001101010
101010010
110000011
010011100
000000100
A1B2
C2
D1E3
F2
G3
H1
I1
(G1)
Câu 1. (L.O.1.2) Trong đồ thị G1, có tồn tại đường đi và chu trình Euler không?
Acó đường đi và chu trình Euler
Bcó đường đi Euler BAG BHF ACF EDC EHGI nhưng không có chu trình Euler
Ccó đường đi Euler là BAGBHDCAF CEF HGI và chu trình Euler là BAGBHGDCAF HEF CDCB
Dkhông có đường đi và không có chu trình Euler
Câu 2. (L.O.1.2) Phát biểu nào sau đây là đúng. (Câu này có 2 đáp án đúng, sinh viên chọn một trong
hai đáp án đúng đều được trọn điểm.)
ATrong G1, tồn tại đường đi và chu trình Hamilton
BG1không là đồ thị phân đôi
CG1là đồ thị phẳng
DCác đáp án khác đều đúng
Câu 3. (L.O.1.2) Đồ thị G1có bao nhiêu thành phần liên thông (connected components)?
A0
B1
C2
D3
Câu 4. (L.O.1.2) Số màu tối thiểu để tô màu tất cả các đỉnh trong đồ thị G1là bao nhiêu sao cho 2 đỉnh
liền kề bất kỳ đều không cùng màu?
A2
B3
C4
D5
Câu 5. (L.O.1.2) Các cạnh nào là cạnh cắt (cut edge, bridge) trong đồ thị?
ACA
BGI
CCác đáp án khác đều sai.
DKhông tồn tại cạnh cắt trong đồ thị.
Câu 6. (L.O.1.2) Các đỉnh nào là đỉnh cắt (cut vertex, articulation point) trong đồ thị?
AG
BAvà C
CGvà I
DKhông có đỉnh nào.
EA
Trong các câu 7–10, ta sử dụng đồ thị G2dưới đây:
Mã đề: 1611
Người ra đề: TS. Huỳnh Tường Nguyên Trang 1/5
F
A G
D E
B
C
12
5
8 6
4
9
11
10
11
5
9
13
8
(G2)
Câu 7. (L.O.4.1) Trong đồ thị G2, sử dụng giải thuật Prim và xuất phát từ đỉnh B, cạnh thứ ba được
tìm thấy là cạnh nào?
AEF hoặc CD
BEF
CAB
DEF hoặc BC (B→F→E→Choặc B→C→F→E)
Câu 8. (L.O.4.1) Trong đồ thị G2, sử dụng giải thuật Kruskal, chúng ta nên chọn cạnh thứ ba là cạnh
nào?
ADE
BBF
CBC
DBF hoặc BC
Câu 9. (L.O.4.1) Trong đồ thị G2, sử dụng giải thuật Prim hoặc Kruskal, chúng ta thu được cây khung
nhỏ nhất có tổng trọng số là bao nhiêu?
A39
B37
C38 (EF (4) + BC(5) + BF (5) + DE(6) + EG(8) + CA(10))
D43
Trong các câu hỏi 10–11, chúng ta cùng xét hai đồ thị vô hướng G1và G2được xác định lần lượt bởi
ma trận kề (adjacency matrix) và ma trận liên thuộc (incident matrix) như dưới đây.
(G1)A B C D E
A
B
C
D
E
01011
10010
00010
11101
10010
(G2)e1e2e3e4e5e6e7
A
B
C
D
E
1000110
0101000
0110100
1011001
0000011
Câu 10. (L.O.2.1) G1có G2đẳng cấu không?
ACó
BKhông
Câu 11. (L.O.2.1) Nếu có, hãy xác định hàm dẳng cấu (isomorphism function) từ tập các đỉnh của G1
vào tập các đỉnh của G2(nêu thứ tự các đỉnh của G1vào câu A, và ảnh của nó vào câu B); và nếu
không, hãy nêu ra tối thiểu 3 lý do vào các câu A, B, C bên dưới.
Asố cạnh
Bsố đỉnh bậc 1
Csố lượng tam giác
Trong các câu hỏi 12–13, chúng ta cùng xét một giải đấu vòng loại gồm nngười tham gia thi đấu. Mỗi
trận đấu sẽ có 2 người thi với nhau để phân biệt thắng thua (không có trường hợp hòa nhau).
Câu 12. (L.O.2.2, L.O.4.1) Chứng minh rằng tại bất kỳ thời điểm nào của
giải đấu, luôn có 2 vận động viên có cùng số lượng trận đã thi đấu.
Mô hình hóa lại bài toán bằng một đồ thị vô hướng biểu diễn các trận đấu đã xảy ra. Ứng
dụng nguyên lý Dirichlet cho thấy rằng luôn tồn tại 2 đỉnh có bậc cùng nhau (do không tồn
tại cùng lúc có 1 đỉnh bậc 0 và 1 đỉnh bậc n).
Câu 13. (L.O.2.3) Khi n+ 1 trận đấu đã được hoàn thành,
Atồn tại một vận động viên đã thi đấu tối thiểu 3 trận.
Btồn tại một vận động viên đã thi đấu tối thiểu 4 trận.
Ctồn tại vận động viên có tối thiểu ntrận thắng.
Dtồn tại vận động viên chưa từng đấu trận nào.
Mã đề: 1611
Người ra đề: TS. Huỳnh Tường Nguyên Trang 2/5
Trong các câu 14–15, ta xét đồ thị G6dưới đây để tìm đường đi ngắn nhất từ đỉnh Ađến tất cả các
đỉnh còn lại bằng giải thuật Dijkstra:
A
B
C
D
E
F
G
H
(G6)
5
411
8
4
12
9
4
7
7
4
72S A B C D E F G H
∅0∞∞∞∞∞∞∞
A 5 4 8 ∞11 ∞ ∞
C 5 8 13 8 ∞ ∞
B 8 9 8 ∞17
D 9 8 15 17
F 9 12 15
E 12 15
G 14
Sử dụng giải thuật Dijkstra trong đồ thị G6, một bảng lưu vết các giá trị tương ứng với các đỉnh theo
thứ tự bảng chữ cái (nghĩa là cột đầu tương ứng với đỉnh A, cột kế tương ứng với đỉnh B). Gọi dòng 1
là dòng khởi tạo giá trị - tương ứng với "0; ∞;∞;∞;∞;∞;∞;∞”.
Câu 14. (L.O.4.1) Theo giải thuật, chúng ta thu được gì ở dòng 6.
A0; 5; 4; 8; 9; 8; ∞;∞
B0; 5; 4; 8; 9; 8; 12; 15
C0; 5; 4; 8; 9; 8; 12; 17
D0; 5; 4; 8; 9; 8; 15; 17
Câu 15. (L.O.4.1) Theo giải thuật, chúng ta thu được gì ở dòng số 7.
A0; 5; 4; 8; 9; 8; 12; 15
B0; 5; 4; 8; 9; 8; 12; 16
C0; 5; 4; 8; 9; 8; 12; 14
D0; 5; 4; 8; 8; 9; 12; 15
Trong các câu 16–17, ta xét đồ thị G7dưới đây để tìm đường đi ngắn nhất từ đỉnh Ađến tất cả các
đỉnh còn lại bằng giải thuật Bellman-Ford:
A
BC
D E
FG
HI
(G7)
6
8
4
-5 3
-5
3
-4 -3
5
3 -1
-2
3-4 Step A B C D E F G H I
0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 6A 4A 8A ∞ ∞ ∞ ∞ ∞
2 -1C 3D 11D 7C ∞ ∞ 2B
3 -2C 0I 8E 10F -5B
4 -7I 5F 3F -6B
5 -8I -2F -4F
6 -3F -5F
7
Giả sử bảng lưu vết sắp xếp các đỉnh theo thứ tự bảng chữ cái (nghĩa là cột đầu tương ứng với đỉnh
A, cột kế tương ứng với đỉnh B). Dòng khởi tạo đầu tiên tương ứng với Step=0, ta thu được các giá trị
0; ∞;∞;∞;∞;∞;∞;∞;∞.
Câu 16. (L.O.4.1) Sử dụng giải thuật Bellman-Ford trong đồ thị G7, chúng ta thu được gì ở dòng tương
ứng với Step=3.
A0; −2C; 3D; 8A; 11D; 0I; 8E; 10F;−5B.(không
có trong các đề khác,
nên đáp án nào cũng
được điểm)
B0; −2C; 3D; 8A;∞; 0I; 8E;∞;−5B.
C0; −2C; 3D; 8A; 11D; 7C; 8E;∞;−5B.
D0; −2C; 3D; 8A; 11D; 0I; 8E;∞;−5B.
E0; −2C; 3D; 8A;∞; 6C; 8E;∞;−5B.
Mã đề: 1611
Người ra đề: TS. Huỳnh Tường Nguyên Trang 3/5
Câu 17. (L.O.4.1) Giải thuật Bellman-Ford áp dụng trong đồ thị G4sẽ kết thúc với Step bằng mấy?
A7
B6
C9
DGiải thuật không dừng
Trong các câu 18–19, ta xét đồ thị G5dưới đây để tìm đường đi ngắn nhất từ đỉnh Ađến tất cả các
đỉnh còn lại bằng giải thuật Floyd-Warshall:
A B
C D
(G5)-3
-2
5
-2
63
-6
32
L(0) =L(1) =
00−30−20∞0
5000−2030
603000∞0
∞020−6000
L(3) =
00−30−5200
4300−2030
60300062
03−33−6000
L(4) =
00−30−6400
3400−3430
60300062
03−33−6000
Câu 18. (L.O.4.1) Sử dụng giải thuật Floyd-Warshall trong đồ thị G5, xác định L(2).
A
00−30−5202
5000−2030
60300062
7220−6000
(không có trong các đề khác, nên đáp án nào cũng được điểm)
B
00−30−20∞0
5000−2030
603100∞0
∞020−6000
C
00−30−5200
5000−2030
60300062
7220−6000
D
00−30−5000
5000−2030
60310060
7220−6000
E
00−3050∞0
5000−2030
603100∞0
∞020−6000
Câu 19. (L.O.4.1) Sau khi áp dụng giải thuật Floyd-Warshall trong đồ thị G5, số lượng ma trận khác
nhau được tìm thấy là bao nhiêu ?
AKhông xác định do giải thuật không dừng
B2
C3
D4
Câu 20. (L.O.1.2) Đầu mút của cạnh cắt có phải là đỉnh cắt không? Vì sao?
Ađầu mút của cạnh cắt là đỉnh cắt
Bcó thể không phải vì có thể là đỉnh treo
Cđầu mút của cạnh cắt không là đỉnh cắt
Dtùy trường hợp, đôi khi đầu mút của cạnh cắt là đỉnh cắt
Câu 21. (L.O.4.1) Giải thuật Dijkstra có thể áp dụng cho đồ thị có hướng và có trọng số âm không?
Atùy trường hợp, nếu thay đổi thứ tự xét các đỉnh thì có thể áp dụng
Bcó thể áp dụng nếu đồ thị không chứa chu trình có tổng trọng số là âm
Ccác đáp án khác đều sai
Dkhông thể vì không đảm bảo tính tối ưu qua mỗi bước lặp
Trong các câu 22–23, xét mẫu dữ liệu sau: 1, 5, 2, 6, 8, 3, 5, 2, 10, 4.
Câu 22. (L.O.3.1) Giá trị trung bình và giá trị trung vị của mẫu trên là:
A4.6 và 4.5
B4.5 và 4.6
C4.6 và 5
D5 và 4
Mã đề: 1611
Người ra đề: TS. Huỳnh Tường Nguyên Trang 4/5
Câu 23. (L.O.3.1) Tứ phân vị thứ 3 của mẫu trên là:
A4
B5.75
C5
D6.2
Câu 24. (L.O.3.2) Một xạ thủ có 4 viên đạn và bắn vào một mục tiêu ở xa đến khi nào trúng mục tiêu đó
hoặc hết đạn thì ngừng bắn. Biết rằng khả năng bắn trúng mục tiêu ở mỗi lần bắn là 80%.Tính kì
vọng của số viên đạn mà xạ thủ này dùng.
A1,2416.
B1,5.
C2.
D1,248.
Câu 25. (L.O.2.3) Hãy cho biết trung thứ tự (in-order traversal) của một cây nhị phân biết rằng tiền thứ tự
(pre-order traversal) là GABDIJHCF E và hậu thứ tự (post-order traversal) là BIJDAF CEHG.
G
A
B D
I J
H
C
F
E
ABGIDJ ACF HE
BBAIDJ GCF HE
CBGIDJ AF CHE
DABCDEF GHIJ
Trong các câu 26–27, bài toán về quản lý hệ thống cấp nước được xem xét như sau.
Hai nguồn nước s1và s2được cung cấp cho 8 thành phố A,B,C,D,E,E,G,Hvà I. Sự liên thông
giữa các thành phố và nguồn nước được thể hiện qua đồ thị G9bên dưới trong đó trọng số của một cung
(u, v)thể hiện khả năng truyền tải nước nguồn (m3/h) từ thành phố u(hoặc từ nguồn u) đến thành phố
v.
s1
s2
A
B
C
D
E
F
G H
I
(G9)10
10
10
11
6
8
5
2
7
3
2
24
4
8
710
s
s1
s2
A
B
C
D
E
F
G H
I
(G(1)
9)
20
10
10
10
10
11
6
8
5
2
7
3
2
24
4
8
710
Mã đề: 1611
Người ra đề: TS. Huỳnh Tường Nguyên Trang 5/5