Đề thi Giữa kì môn Toán rời rạc - Trường Đại học Bách khoa Hà Nội

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

MSSV:..................

Họ và tên:......................................................

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

MSSV: . . . . . . . . . . . . . . . . . . . . .

Họ tên SV: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Số thứ tự

Học phần: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mã HP: . . . . . . . . . . . . . . . . . . . .

Bài thi [X] giữa kỳ [ ] 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

Tờ .../ ...

Đề 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. Làm bài luôn vào đề thi.

1. Xét M là ghép cặp ký hiệu bởi các đường nét đậm trong đồ thị sau.

a

c

e

b

d

A

B

C

D

E

(a) Tìm một đường mở cho M bắt đầu tại đỉnh b.

(b) Dùng đường mở vừa tìm được để xây dựng ghép cặp M⁰kích thước 4.

(c) Kiểm tra xem liệu còn đường mở nào cho M⁰không. Giải thích ngắn gọn.

(d) Liệu M⁰có phải ghép cặp cực đại.

1

2

2. Ngày mai, Viện CNTT&TT sẽ có 10 cuộc họp. Các cuộc họp có thời gian như sau:

Cuộc họp 1: 11h – 12h29

2: 15h – 16h29

6: 9h – 12h29

7: 14h – 16h29

8: 9h – 10h29

9: 13h – 14h29

10: 15h – 16h29

3: 9h – 10h29

4: 11h – 12h29

5: 13h – 14h29

Do tính riêng tư, tại một thời điểm, mỗi phòng họp chỉ diễn ra nhiều nhất một cuộc họp. Hãy

xếp lịch họp cho Viện dùng ít phòng nhất. Hãy giải thích ngắn gọn tại sao cách xếp của bạn

lại dùng ít phòng nhất.

3. Hãy dùng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh A tới tất cả các đỉnh khác

của đồ thị sau. Yêu cầu: Vẽ bảng mô tả thuật toán.

5

1

E

F

G

H

1

4

2

6

1

8

6

A

B

C

D

1

2

1

3

4. Xác định Pru¨fer code của cây sau:

2

3

1

0

4

5

6

5. Xây dựng cây với Pru¨fer code là (1, 1, 0, 4, 2, 0, 1, 4).

6. Thực hiện thuật toán DFS trên đồ thị G sau. Vẽ rừng DFS với các thông tin post và pre trên

mỗi đỉnh. Nếu cần quyết định thứ tự các đỉnh thăm, bạn hãy sử dụng thứ tự từ điển. Hãy liệt

kê các cạnh ngược (back edge).

G

D

A

H

I

E

F

C

B

7. Hãy tìm các thành phần liên thông mạnh của đồ thị trong bài tập 6. Gợi ý: Tính toán trên đồ

thị G^Rvà sử dụng thông tin post từ bài tập trước.

4

8. Có bốn sinh viên a, b, c, d muốn thực tập tại bốn công ty A, B, C, D. 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 thích Công ty

Công ty thích Sinh viên

a

b

c

A B C

D C

A B C

D A

D

A

D

B

A

B

C

D

a b c

b a c

d

b

B

a d

c

a

d

C

d

c

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?

9. Hãy mô tả một thuật toán nhận đầu vào là đồ thị có hướng G = (V, E), và xác định xem liệu

có hay không một đỉnh s ∈ V thỏa mãn: từ s ta có thể tới được mọi đỉnh của G. Phân tích

thời gian chạy của thuật toán và giải thích tại sao nó chạy đúng.