Kiểm Tra 20-12-2023 Ca 2 Kiểm Tra Đề 3
Câu 1: (2 điểm) Giải cá
c hệ thức truy hồi với các điều kiện đầu sau:
an = 6an-1 - 8an-2 với n ≥ 2, a0 = 4 ,a1 = 10.
Câu 2: (3 điểm) Áp dụng thuật toán nhánh cận giải bài toán người du lịch với ma trận chi phí như sau: ∞ 14 10 40 08 ∞ 18 24 30 12 ∞ 24 10 40 34 ∞ Câu 3: (2 điểm) Cho đồ thị sau: 1 3 5 7 2 4 6 8
1. Lập ma trận kề biểu diễn đồ thị trên?
2. Định nghĩa đồ thị Euler, đồ thị nửa Euler?
3. Đồ thị trên có chu trình Euler không? Vì sao? Nếu có hãy tìm chu trình Euler đó?
Câu 4: (3 điểm): Cho đồ thị sau a 42 b 4 10 14 3 c 3 1 11 d e f 5 20 9 15 7 g h
1. Duyệt đồ thị trên theo phương pháp Duyệt theo chiều sâu – DFS trên (Đỉnh bắt đầu là đỉnh b)
2. Dùng thuật toán Prim tìm cây khung nhỏ nhất của đồ thị trên (Đỉnh bắt đầu là đỉnh e) Đề số 4
Câu 1: (2 điểm) Giải cá
c hệ thức truy hồi với các điều kiện đầu sau:
an = 5an-1 + 6an-2 với n ≥ 2, a0 = 4, a1 = 1 . Câu 2: (3 điểm)
Cho thời gian gia công các chi tiết trên 2 máy A và B trong bảng sau. Hãy lập
lịch gia công cho các chi tiết này sao cho thời gian gia công là ít nhất. Vẽ sơ đồ Gantt
cho lịch gia công tối ưu. Chi tiết D1 D2 D3 D4 D5 Máy A 5 7 7 8 4 B 8 5 2 7 6 Câu 3: (2 điểm) Cho đồ thị sau 5 7 1 3 2 6 8 4
1. Lập danh sách về kề biểu diễn đồ thị trên?
2. Định nghĩa đồ thị Hamilton, đồ thị nửa Hamilton? 3. Đồ t ị
h trên có chu trình Hamilton không? Vì sao? Nếu có hãy tìm chu trình Hamilton đó?
Câu 4: (3 điểm): Cho đồ thị sau
1. Duyệt đồ thị trên theo phương pháp Duyệt theo chiều rộng – BFS (Đỉnh bắt đầu là đỉnh 2)
2. Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 3 đến tất cả các
đỉnh còn lại của đồ thị.