Đề kiểm cuối kì tra toán rời rạc | Đại học Kinh tế Kỹ thuật Công nghiệp

Dưới đây là mẫu đề kiểm tra cuối kỳ môn Toán Rời Rạc dành cho sinh viên Đại học Kinh tế Kỹ thuật Công nghiệp. Đề kiểm tra này bao gồm các câu hỏi lý thuyết và bài tập ứng dụng thực tiễn để kiểm tra kiến thức của sinh viên về môn học. Trình bày khái niệm tập hợp và phân loại các loại tập hợp. Cho ví dụ minh họa.

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

Môn: Toán rời rạc (KTKTCN)

Trường: Đại học Kinh tế kỹ thuật công nghiệp

Thông tin:

5 trang 6 ngày trước

Tác giả:

Profile Dung Dang
Kiểm Tra 20-12-2023 Ca 2
Kiểm Tra
Đề 3
Câu 1: (2 điểm) Gi i hả các ệ c truy h i v i thứ ồ ớ các điều kiện đầu sau:
a =
n
6a
n-1
- 8a
n-2
v i 2, aớ n ≥
0
= a4,
1
= 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:
Câu 3: (2 điểm)
Cho đồ thị sau:
1. L p ma tr n k u diậ ậ ề biể ễn đồ thị trên?
2. Định nghĩa đồ Euler, đồ thị 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 ế
đó?
∞
14
10
40
08
∞
18
24
30
12
∞
24
10
40
34
∞
1
2
3
6
8
4
5
7
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 sâu – (Đỉnh DFS trên
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)
a
b
c
f
14
10
11
3
15
5
9
Đề ố s 4
Câu 1: (2 điểm) Gi i hả các ệ c truy h i v i thứ ồ ớ các điều kiện đầu sau:
a =
n
5a
n-1
+ 6a
n-2
v i ớ n ≥ 2, a
0
= 4, a =
1
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 ế
Máy
D1
D2
D3
D4
D5
A
5
7
7
8
4
B
8
5
2
7
6
Câu 3: (2 điểm)
Cho đồ thị sau
1. L danh sách v k ập ề ề biểu di ễn đồ thị trên?
2. Định nghĩa đồ Hamilton, đồ thị thị n a Hamilton? ử
3. Đồ ị th trên có chu trình Hamilton không? Vì sao? N u có hãy tìm chu trình ế
Hamilton đó?
1
2
3
6
8
4
5
7
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 – (Đỉnh BFS
bắt đầu là đỉnh 2)
2. 3 Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh đến tất cả các
đỉnh còn lại của đồ thị.
| 1/5
| | Tải xuống

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

Preview text:

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ị.