Đề thi cuối học kỳ 1 năm 2020-2021 - Cấu trúc rời rạc | Trường Đại học CNTT Thành Phố Hồ Chí Minh

Đề thi cuối học kỳ 1 năm 2020-2021 - Cấu trúc rời rạc | Trường Đại học CNTT Thành Phố Hồ Chí Minh được được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!

57 29 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc rời rạc

Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

2 trang 7 tháng trước

Tác giả:

Profile Mai Nguyệt
lOMoARcPSD| 40425501
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH ĐỀ THI CUỐI KỲ MÔN CTRR
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN Học kỳ I, năm học 2020-2021
BỘ MÔN TOÁN – LÝ Ngày thi: /01/2021
Thời gian làm bài: 90 phút
Không được sử dụng tài liệu
Câu 1. (4.0 điểm) Cho hàm Boole f theo 4 biến x y z t, , , , biết: f
1
(0) {1000,
0111, 0000, 1111, 1010, 1101}.
a) Hãy tìm dạng nối rời chính tắc của hàm f .
b) Hãy tìm các công thức đa thức tối tiểu của hàm f .
c) Hãy vẽ sơ đồ mạch cho một công thức đa thức tối tiểu của hàm f vừa tìm được. Câu 2.
(1.0 điểm) Một nước có 10 thành phố. Hãy thiết lập một mạng đường hàng không thỏa 2
điều kiện:
+) Mỗi thành phố có đường hàng không nối trực tiếp với đúng 3 thành phố khác
+) Từ mỗi thành phố có đường hàng không đi tới một thành phố tùy ý sao cho trên đường
hành trình tới đích có thể đi qua các thành phố khác, mỗi thành phố đi qua đúng một lần.
Câu 3. (5.0 điểm) Cho đồ thị G sau:
a) G có chu trình (đường đi) Euler không? Tại sao? Nếu có hãy chỉ ra một chu trình
(đường đi) Euler của G.
b) Hãy chỉ ra một chu trình (đường đi) Hamilton của G (nếu có).
c) Dùng thuật toán Djikstra tìm đường đi ngắn nhất từ đỉnh c đến các đỉnh còn lại của G
(trình bày thuật toán trên cùng một bảng).
d) Hãy tìm cây khung có trọng số lớn nhất T của G (trình bày thuật toán).
------------------------------------ Hết
Cán bộ coi thi không giải thích gì thêm
Trưởng BM Toán - Lý
CAO THANH TÌNH
| 1/2
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

lOMoAR cPSD| 40425501
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
ĐỀ THI CUỐI KỲ MÔN CTRR
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Học kỳ I, năm học 2020-2021 BỘ MÔN TOÁN – LÝ Ngày thi: /01/2021
Thời gian làm bài: 90 phút
Không được sử dụng tài liệu
Câu 1. (4.0 điểm) Cho hàm Boole f theo 4 biến x y z t, , , , biết: f 1(0) {1000,
0111, 0000, 1111, 1010, 1101}.
a) Hãy tìm dạng nối rời chính tắc của hàm f .
b) Hãy tìm các công thức đa thức tối tiểu của hàm f .
c) Hãy vẽ sơ đồ mạch cho một công thức đa thức tối tiểu của hàm f vừa tìm được. Câu 2.
(1.0 điểm) Một nước có 10 thành phố. Hãy thiết lập một mạng đường hàng không thỏa 2 điều kiện:
+) Mỗi thành phố có đường hàng không nối trực tiếp với đúng 3 thành phố khác
+) Từ mỗi thành phố có đường hàng không đi tới một thành phố tùy ý sao cho trên đường
hành trình tới đích có thể đi qua các thành phố khác, mỗi thành phố đi qua đúng một lần.
Câu 3. (5.0 điểm) Cho đồ thị G sau:
a) G có chu trình (đường đi) Euler không? Tại sao? Nếu có hãy chỉ ra một chu trình
(đường đi) Euler của G.
b) Hãy chỉ ra một chu trình (đường đi) Hamilton của G (nếu có).
c) Dùng thuật toán Djikstra tìm đường đi ngắn nhất từ đỉnh c đến các đỉnh còn lại của G
(trình bày thuật toán trên cùng một bảng).
d) Hãy tìm cây khung có trọng số lớn nhất T của G (trình bày thuật toán).
------------------------------------ Hết
Cán bộ coi thi không giải thích gì thêm Trưởng BM Toán - Lý CAO THANH TÌNH