Đề thi giữa kỳ 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 giữa kỳ 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!

70 35 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
TRƯỜNG ĐẠI HỌC C NG NGHỆ TH NG TIN – ĐHQG-HCM
BAN HỌC TẬP CÔNG NGHỆ PHẦN MỀM
TRƯỜNG ĐẠI HỌC ĐỀ THI THỬ
CÔNG NGHỆ THÔNG TIN M N: CẤU TRÚC RỜI RẠC
BAN HỌC TẬP CÔNG NGHỆ PHẦN MỀM
C u 1. Cho h m Boole f theo 4 biến x, y, z,t biết:
𝑓
−1
(0) ={1101,1010,1000,0010,0000,0111}
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. Cho v dụ về đơn đồ thị có 6 đỉnh:
a) Đồ thị đó vừa c chu tr nh Euler vừa c chu tr nh Hamilton (chỉ rı chu tr nh).
b) Đồ thị đó có chu trình Euler và chu trình Hamilton nhưng hai chu trình n y kh
ng trøng nhau.
c) Đồ thị c chu tr nh Euler (chỉ rõ chu trình) nhưng không có chu trình Hamilton.
d) Đồ thị c chu tr nh Hamilon (chỉ rõ chu trình) nhưng không có chu trình Euler.
C u 3. 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
1
lOMoARcPSD| 40425501
TRƯỜNG ĐẠI HỌC C NG NGHỆ TH NG TIN – ĐHQG-HCM
BAN HỌC TẬP C NG NGHỆ PHẦN MỀM
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 a đế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
------------------------------------------------------------------------------------------
Chœc cÆc bạn l m b i tốt!
2
Downloaded by Mai Le Thi Nguyet (hoathanvu729@gmail.com)
| 1/2
| | Tải xuống

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

Preview text:

lOMoAR cPSD| 40425501
TRƯỜNG ĐẠI HỌC C NG NGHỆ TH NG TIN – ĐHQG-HCM
BAN HỌC TẬP CÔNG NGHỆ PHẦN MỀM TRƯỜNG ĐẠI HỌC ĐỀ THI THỬ
CÔNG NGHỆ THÔNG TIN
M N: CẤU TRÚC RỜI RẠC
BAN HỌC TẬP CÔNG NGHỆ PHẦN MỀM
C u 1. Cho h m Boole f theo 4 biến x, y, z,t biết:
𝑓−1(0) ={1101,1010,1000,0010,0000,0111}
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. Cho v dụ về đơn đồ thị có 6 đỉnh:
a) Đồ thị đó vừa c chu tr nh Euler vừa c chu tr nh Hamilton (chỉ rı chu tr nh).
b) Đồ thị đó có chu trình Euler và chu trình Hamilton nhưng hai chu trình n y kh ng trøng nhau.
c) Đồ thị c chu tr nh Euler (chỉ rõ chu trình) nhưng không có chu trình Hamilton.
d) Đồ thị c chu tr nh Hamilon (chỉ rõ chu trình) nhưng không có chu trình Euler.
C u 3. 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 1 lOMoAR cPSD| 40425501
TRƯỜNG ĐẠI HỌC C NG NGHỆ TH NG TIN – ĐHQG-HCM
BAN HỌC TẬP C NG NGHỆ PHẦN MỀM
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 a đế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
------------------------------------------------------------------------------------------
Chœc cÆc bạn l m b i tốt! 2
Downloaded by Mai Le Thi Nguyet (hoathanvu729@gmail.com)