Đề thi giữa kỳ 2019 môn Toán rỏi rạc | Trường Đại học Bách khoa Hà Nội

Đề thi giữa kỳ 2019 môn Toán rỏi rạc | Trường Đại học Bách khoa Hà Nội. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

Cấu trúc đề thi giữa kỳ môn Toán Rời Rạc
Mỗi bài 01 điểm. Làm bài luôn vào đề.
Yêu cầu: Viết sáng sủa ngắn gọn; Không nháp vào bài thi.
Bài 1. Chứng minh một số tính chất đơn giản về đồ thị cây.
Bài 2. Tìm cặp ghép hoặc tìm đường đi (chu trình) Hamilton.
Bài 3. Thuật toán Dijkstra hoặc Prim.
Bài 4. Thuật toán Kruskal hoặc cấu trúc dữ liệu Disjoint Set.
Bài 5. Tô màu đồ thị.
Bài 6. Tìm thành phần liên thông mạnh.
Bài 7. Tính toán Pr
¨
ufer code của cây.
Bài 8. Bài toán Hôn nhân bền vững.
Bài 9. Luồng cực đại lát cắt cực tiểu.
Bài 10. Bài tập sáng tạo.
1
2
Họ tên:...................................................... MSSV:..................
TRƯỜNG ĐẠI HỌC BÁCH KHOA NỘI
VIỆN CÔNG NGHỆ THÔNG TIN TRUYỀN THÔNG
Họ tên SV: .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MSSV: . . . . . . . . . . . . . . . . . . . . .
Học phần: Toán Rời Rạc . . . . . . . . . . . . . . . . . . . . . . . . HP: . . . . . . . . . . . . . . . . . . . .
Bài thi [ ] giữa kỳ [X] cuối kỳ . . . . . . . . . . . . Ngày thi:. . . . . . . . . . . . . . . . .
Số thứ tự
Điểm của bài thi Chữ của (các) cán bộ chấm thi Chữ của cán bộ coi thi
Đề mẫu thi giữa kỳ môn Toán Rời Rạc
Thời gian 90 phút. Không sử dụng tài liệu.
1. Một cây 2n đỉnh bậc 1, 3n đỉnh bậc 2, n đỉnh bậc 3 không đỉnh bậc khác. Hãy xác
định xem n bằng bao nhiêu, từ đó tìm số đỉnh số cạnh trong cây.
2. Liệu ta thể ghép cặp đầy đủ cho đồ thị hai phần dưới đây không? Nếu đậm một ghép
cặp như vậy. Nếu không hãy chứng minh.
A B
C
D E F
a
b
c
d
e
f
3
3. Hãy dùng thuật toán Dijkstra để xây dựng cây tả đường đi ngắn nhất từ đỉnh A tới tất
cả các đỉnh khác của đồ thị sau:
A B
C
D
E F
G
H
1
8
4
2
6
6
1
2
1
1
1
15
4. Hãy dùng thuật toán Kruskal để tìm cây bao trùm nhỏ nhất cho đồ thị trong Bài tập 3.
5. Xét đồ thị G thu được từ đồ thị trong Bài 3 sau khi bỏ đi trọng số trên cạnh. Hãy tìm cách
màu đồ thị này dùng ít màu nhất thể. Tại sao số màu bạn dùng lại ít nhất?
4
6. Hãy tìm các thành phần liên thông mạnh của đồ thị sau.
A B
C
D E F
G
H I
7. (a) Xác định Pr
¨
ufer code của cây sau:
2
3
0
4
5
1
(b) Xây dựng cây với Pr
¨
ufer code (0, 0, 0, 4, 2, 0, 1, 0).
8. năm sinh viên a, b, c, d, e muốn thực tập tại năm công ty A, B, C, D, E. Sau đây danh sách
xếp hạng mức độ ưa thích của các sinh viên của các công ty (trái nhất thích nhất):
Sinh viên Công ty
a B A D E C
b D B A C E
c B E C D A
d A D C B E
e B D A E C
Công ty Sinh viên
A e a b d c
B c b d a e
C b c d e a
D a e d c b
E d b e c a
Hãy dùng thuật toán kén chồng để tìm một cặp ghép ổn định. Cặp ghép ổn định này phải
duy nhất không? Tại sao?
5
9. Hãy tìm luồng cực đại lát cắt cực tiểu của mạng sau đây.
s
a
b
c
d
e
t
3
3
10
2
1
4
1
5
1
2
5
10. Cho một tập các biến x
1
, x
2
, . . . , x
n
, một tập các ràng buộc bằng nhau x
i
= x
j
hoặc khác
nhau x
i
6= x
j
. Bạn hãy thiết kế thuật toán kiểm tra liệu các biến thể thỏa mãn mọi ràng
buộc.
Ví dụ, các ràng buộc x
1
= x
2
, x
2
= x
3
, x
3
= x
4
, x
1
6= x
4
không thể thỏa mãn.
| 1/5

Preview text:

Cấu trúc đề thi giữa kỳ môn Toán Rời Rạc
Mỗi bài 01 điểm. Làm bài luôn vào đề.
Yêu cầu: Viết sáng sủa và ngắn gọn; Không nháp vào bài thi.
Bài 1. Chứng minh một số tính chất đơn giản về đồ thị và cây.
Bài 2. Tìm cặp ghép hoặc tìm đường đi (chu trình) Hamilton.
Bài 3. Thuật toán Dijkstra hoặc Prim.
Bài 4. Thuật toán Kruskal hoặc cấu trúc dữ liệu Disjoint Set.
Bài 5. Tô màu đồ thị.
Bài 6. Tìm thành phần liên thông mạnh.
Bài 7. Tính toán Pr¨ ufer code của cây.
Bài 8. Bài toán Hôn nhân bền vững.
Bài 9. Luồng cực đại và lát cắt cực tiểu.
Bài 10. Bài tập sáng tạo. 1 2
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
Họ và tên:...................................................... MSSV:..................
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Họ tên SV: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MSSV: . . . . . . . . . . . . . . . . . . . . . Số thứ tự
Học phần: Toán Rời Rạc . . . . . . . . . . . . . . . . . . . . . . . .
Mã HP: . . . . . . . . . . . . . . . . . . . .
Bài thi [ ] giữa kỳ [X] cuối kỳ . . . . . . . . . . . .
Ngày thi: . . . . . . . . . . . . . . . . . Điểm của bài thi
Chữ ký của (các) cán bộ chấm thi
Chữ ký của cán bộ coi thi
Đề mẫu thi giữa kỳ môn Toán Rời Rạc
Thời gian 90 phút. Không sử dụng tài liệu.
1. Một cây có 2n đỉnh bậc 1, 3n đỉnh bậc 2, n đỉnh bậc 3 và không có đỉnh bậc khác. Hãy xác
định xem n bằng bao nhiêu, từ đó tìm số đỉnh và số cạnh trong cây.
2. Liệu ta có thể ghép cặp đầy đủ cho đồ thị hai phần dưới đây không? Nếu có tô đậm một ghép
cặp như vậy. Nếu không hãy chứng minh. a b c d e f A B C D E F 3
3. Hãy dùng thuật toán Dijkstra để xây dựng cây mô tả đường đi ngắn nhất từ đỉnh A tới tất
cả các đỉnh khác của đồ thị sau: 5 1 1 E F G H 1 4 6 2 1 8 6 A B C D 1 2 1
4. Hãy dùng thuật toán Kruskal để tìm cây bao trùm nhỏ nhất cho đồ thị trong Bài tập 3.
5. Xét đồ thị G thu được từ đồ thị trong Bài 3 sau khi bỏ đi trọng số trên cạnh. Hãy tìm cách tô
màu đồ thị này dùng ít màu nhất có thể. Tại sao số màu bạn dùng lại là ít nhất? 4
6. Hãy tìm các thành phần liên thông mạnh của đồ thị sau. G H I D E F A B C 7. (a) Xác định Pr¨ ufer code của cây sau: 2 3 1 0 5 4
(b) Xây dựng cây với Pr¨
ufer code là (0, 0, 0, 4, 2, 0, 1, 0).
8. Có năm sinh viên a, b, c, d, e muốn thực tập tại năm công ty A, B, C, D, E. Sau đây là danh sách
xếp hạng mức độ ưa thích của các sinh viên và của các công ty (trái nhất là thích nhất): Sinh viên Công ty Công ty Sinh viên a B A D E C A e a b d c b D B A C E B c b d a e c B E C D A C b c d e a d A D C B E D a e d c b e B D A E C E d b e c a
Hãy dùng thuật toán kén chồng để tìm một cặp ghép ổn định. Cặp ghép ổn định này có phải
là duy nhất không? Tại sao? 5
9. Hãy tìm luồng cực đại và lát cắt cực tiểu của mạng sau đây. 2 a d 3 1 2 10 3 s b 1 t 1 4 5 5 c e
10. Cho một tập các biến x =
1, x2, . . . , x , và một tập các ràng buộc bằng nhau hoặc khác n xi x j nhau x
. Bạn hãy thiết kế thuật toán kiểm tra liệu các biến có thể thỏa mãn mọi ràng i 6= x j buộc.
Ví dụ, các ràng buộc x = = = 1 x2, x2 x3, x3
x4, x1 6= x4 là không thể thỏa mãn.