Đề thi Cuối kì môn Toán rời rạc
Đề thi mô n: TOÁ N RỜI RẠC – K56
Thời gian: 90 phút
Đề thi mô n: TOÁ N RỜI RẠC – K56
Thời gian: 90 phút
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề)
Bài 1:
Bài 1:
1a) Trong không gian 3 chiều có bao nhiêu đường đi từ điểm (0,0,0) đến điểm
(25, 35, 55) nếu mỗi bước đi có một trong ba toạ độ tăng lên 1, hai toạ độ còn lại
giữ nguyên.
1a) Trong không gian 3 chiều có bao nhiêu đường đi từ điểm (0,0,0) đến điểm
(30, 40, 50) nếu mỗi bước đi có một trong ba toạ độ tăng lên 1, hai toạ độ còn lại
giữ nguyên.
1b) Có bao nhiêu đơn đồ thị vô hướng với n đỉnh ?
1b) Tính tổng số bậc của đơn đồ thị đủ Kn.
Bài 2: Xét hai mệnh đề
Bài 2: Xét hai mệnh đề
(P1): Với mọi số nguyên dương lẻ m, luôn tìm được số nguyên dương n sao cho
(P1): Với mọi số nguyên dương lẻ m, luôn tìm được số nguyên dương n sao cho
2n – 1 chia hết cho m.
2n – 1 chia hết cho m.
(P2): Với mọi số nguyên dương m, n, đồ thị hai phía đầy đủ Km,n luôn chứa chu
trình Hamilton.
(P2): Với mọi số nguyên dương m, n, đồ thị hai phía đầy đủ Km,n luôn chứa chu
trình Hamilton.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi biến nguyên sau:
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi biến nguyên sau:
10ꢀꢁ + 17ꢀꢂ + 30ꢀꢃ + 40ꢀꢄ → ꢅꢆꢀ
3ꢀꢁ + 5ꢀꢂ + 7ꢀꢃ + 8ꢀꢄ ≤ 28
ꢀ ≥ 0, ꢀ ∈ ℤ, ꢈ = 1,2,3,4
11ꢀꢁ + 18ꢀꢂ + 31ꢀꢃ + 41ꢀꢄ → ꢅꢆꢀ
3ꢀꢁ + 5ꢀꢂ + 7ꢀꢃ + 8ꢀꢄ ≤ 29
ꢀ ≥ 0, ꢀ ∈ ℤ, ꢈ = 1,2,3,4
ꢇ
ꢇ
ꢇ
ꢇ
Bài 4: Cho G=(V,E) là đồ thị có hướng mà giữa hai đỉnh bất kì u,v của nó luôn
có hoặc là cạnh (u,v), hoặc là cạnh (v,u), nhưng không đồng thời có cả hai. Kí
hiệu deg+(v) và deg-(v) tương ứng là bán bậc ra và bán bậc vào của đỉnh v. Chứng
minh rằng với đồ thị G đã cho, đẳng thức sau đây luôn đúng:
Bài 4: Cho G=(V,E) là đồ thị có hướng mà giữa hai đỉnh bất kì u,v của nó luôn
có hoặc là cạnh (u,v), hoặc là cạnh (v,u), nhưng không đồng thời có cả hai. Kí
hiệu deg+(v) và deg-(v) tương ứng là bán bậc ra và bán bậc vào của đỉnh v. Chứng
minh rằng với đồ thị G đã cho, đẳng thức sau đây luôn đúng:
ꢉ [degꢊ(ꢋ)]ꢂ = ꢉ [degꢎ(ꢋ)]ꢂ
ꢉ [degꢊ(ꢋ)]ꢂ = ꢉ [degꢎ(ꢋ)]ꢂ
ꢌ∈ꢍ
ꢌ∈ꢍ
ꢌ∈ꢍ
ꢌ∈ꢍ
Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán
Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại:
Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán
Dijkstra tìm đường đi ngắn nhất từ đỉnh B đến các đỉnh còn lại:
Đề thi mô n: TOÁ N RỜI RẠC – K55
Thời gian: 90 phút
Đề thi mô n: TOÁ N RỜI RẠC – K55
Thời gian: 90 phút
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề)
Bài 1:
1a) Tìm số nghiệm nguyên (x,y) của bất phương trình:
Bài 1:
1a) Tìm số nghiệm nguyên của bất phương trình:
| | | |
3 ꢀ + ꢏ ≤ ꢐ , với n là số nguyên dương.
ꢀ + ꢏ + ꢖ ≤ 25 , với điều kiện ꢀ, ꢏ ≥ 2, 0 < ꢖ < 6
1b) Một hình lập phương có cạnh bằng 15 chứa 11000 điểm. Chứng minh rằng
1b) Một hình vuông có cạnh bằng 1 chứa 101 điểm. Chứng minh rằng có ít nhất 5
tồn tại một hình cầu bán kính bằng 1 chứa ít nhất 6 điểm trong số 11000 điểm đã
điểm trong số 101 điểm nói trên nằm trong một hình tròn bán kính bằng 1/7.
cho.
Bài 2: Xét hai mệnh đề
(P1): Trong số 10 người bất kì bao giờ cũng tìm được 2 người có tổng số tuổi chia
hết cho 16, hoặc hiệu số tuổi chia hết cho 16.
(P2): Trong không gian cho 9 điểm có toạ độ nguyên, luôn tìm được ít nhất 2
điểm mà đoạn thẳng nối chúng đi qua điểm có toạ độ nguyên.
Bài 2: Xét hai mệnh đề
(P1): Trong một đơn đồ thị luôn có ít nhất 2 đỉnh cùng bậc.
(P2): Trong mặt phẳng cho 5 điểm phân biệt có toạ độ nguyên, luôn tìm được ít
nhất 2 điểm mà trung điểm đoạn thẳng nối chúng có toạ độ nguyên.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Bài 3: Sử dụng hàm sinh giải công thức đệ quy:
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Bài 3: Sử dụng hàm sinh giải công thức đệ quy:
ꢆꢒ = 4, ꢆꢁ = 12
ꢆꢒ = 2, ꢆꢁ = 5
ꢆꢓ = 4ꢆꢓꢎꢁ − 4ꢆꢓꢎꢂ + ꢐꢂ (ꢐ ≥ 2)
ꢑ
ꢑ
ꢆꢓ = ꢆꢓꢎꢁ + 2ꢆꢓꢎꢂ + 2ꢓ (ꢐ ≥ 2)
Bài 4: Cho G=(V,E) là đồ thị có v đỉnh và e cạnh. còn m và M tương ứng là bậc
nhỏ nhất và bậc lớn nhất của các đỉnh của G. Chứng minh hệ bất đẳng thức:
Bài 4: Cho G=(V,E) là đơn đồ thị hai phía có v đỉnh và e cạnh. Chứng minh bất
đẳng thức sau:
ꢋꢂ
ꢔ ≤
4
2ꢔ
ꢅ ≤
≤ ꢕ
ꢋ
Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán
Kruskal tìm cây khung lớn nhất của đồ thị:
Bài 5: Xét đồ thị vô hướng có trọng số như dưới đây, trình diễn thuật toán Prim
tìm cây khung lớn nhất của đồ thị:
Đề thi mô n: TOÁ N RỜI RẠC – K54
Thời gian: 90 phút
Đề thi mô n: TOÁ N RỜI RẠC – K54
Thời gian: 90 phút
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề)
Bài 1:
Bài 1:
1a) Trong tổng số 2504 sinh viên của khoa công nghệ thông tin, có 1876 theo học
ngôn ngữ Pascal, 999 học môn ngôn ngữ Fortran và 345 học môn ngôn ngữ C.
Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C,
290 học cả Pascal và C. Nếu 189 sinh viên học cả ba ngôn ngữ Pascal, Fortran và
C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong cả 3
ngôn ngữ nói trên.
1a) Hiệu trưởng mời 2n (ꢐ ≥ 2) sinh viên giỏi đến dự tiệc. Mỗi sinh viên giỏi
quen ít nhất n sinh viên giỏi khác đến dự tiệc. Chứng minh rằng luôn luôn có thể
xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi
giữa hai người mà sinh viên đó quen.
1b) Đếm số xâu nhị phân 13 bit chứa hai số 0 liên tiếp.
1b) Một đô vật tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta
thi đấu ít nhất một trận, nhưng toàn bộ anh ta không thi đấu quá 125 trận. Chứng
tỏ rằng, có những giờ liên tiếp anh ta thi đấu 24 trận.
Bài 2: Xét mệnh đề sau: “Trong 102 người có chiều cao khác nhau đứng thành
một hàng luôn tìm được 11 người có chiều cao tăng dần hoặc giảm dần mà không
cần thay đổi thứ tự của họ trong hàng”.
Bài 2: Xét mệnh đề sau: “Trong n+1 số nguyên dương, mỗi số không vượt quá
2n, tồn tại ít nhất một số chia hết cho một số khác”.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mệnh đề trên.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mệnh đề trên.
Bài 3: Trình diễn 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ư dưới đây (giả sử xuất phát từ A):
Bài 3: Trình diễn 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ư dưới đây (giả sử xuất phát từ A):
A
0
91
B
C
D
E
A
0
81
B
C
D
E
A
B
C
D
E
55 87 70 76
81 57 39
81 58
A
B
C
D
E
43 80 69 72
92 58 39
82 43
0
0
80 77
99 83 64
56 91 82 88
0
70 77
95 73 17
26 91 82 78
0
0
89
0
0
89
0
Bài 4: Một ngôi chùa linh thiêng có 5 trụ bằng kim cương. Người ta đúc các
dây xích bằng vàng để nối các trụ lại với nhau, với điều kiện mỗi trụ chỉ được
nối với đúng 3 trụ khác. Chứng minh rằng không thể tìm được cách nối thoả
mãn điều kiện trên.
Bài 4: Giả sử đơn đồ thị phẳng liên thông có 6 đỉnh, mỗi đỉnh đều có bậc là 4.
Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền ?
Bài 5: Trình diễn thuật toán Ford-Fulkerson tìm luồng cực đại và lát cắt hẹp nhất
trong mạng sau:
Bài 5: Trình diễn thuật toán Ford-Fulkerson tìm luồng cực đại và lát cắt hẹp nhất
trong mạng sau:
Đề thi mô n: TOÁ N RỜI RẠC – K53
Thời gian: 90 phút
Đề thi mô n: TOÁ N RỜI RẠC – K53
Thời gian: 90 phút
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề)
Bài 1:
Bài 1:
a) Trong tập 2009 số nguyên dương đầu tiên có bao nhiêu số không chia hết cho
bất kì số nào trong các số 11, 13, 15, 17.
a) Từ các chữ số 1,2,3,4,5,6,7, người ta lập tất cả các số có 5 chữ số (5 chữ số này
đôi một khác nhau). Tính tổng của tất cả các số này.
b) Trên một lưới ô vuông các số nguyên cho hai điểm A(3,2) và B(100, 99). Hỏi
có bao nhiêu đường đi khác nhau từ A đến B mà không cắt đường thẳng y=x (chỉ
cho phép đi trên cạnh các ô vuông theo chiều sang phải hoặc lên trên) ?
b) Trong tập A = {1,2,…,30000} có bao nhiêu số không chia hết cho bất cứ số
nào trong các số 6, 8, 9 ?
Bài 2:
Bài 2: Cho G=(V,E) là một đơn đồ thị vô hướng liên thông. Chứng minh rằng:
a) Nếu tất cả các đỉnh của G đều có bậc là 2 thì G là đồ thị Euler.
b) Nếu tất cả các cạnh của G là cầu thì G là một cây.
a) Có 20 đội bóng thi đấu trong một giải. Mỗi đội phải đấu một trận với các đội
còn lại. Chứng minh rằng luôn có hai đội bóng có số trận đã đấu là như nhau (tính
cả trường hợp chưa đấu trận nào).
b) Chứng minh rằng cây là đồ thị hai phía.
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi:
7ꢀꢁ + 15ꢀꢂ + 26ꢀꢃ + 34ꢀꢄ → ꢅꢆꢀ
3ꢀꢁ + 4ꢀꢂ + 8ꢀꢃ + 9ꢀꢄ ≤ 25
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi:
16ꢀꢁ + 9ꢀꢂ + 7ꢀꢃ + 5ꢀꢄ → ꢅꢆꢀ
ꢀ ≥ 0, ꢀ ∈ ℤ, ꢈ = 1,2,3,4
6ꢀꢁ + 5ꢀꢂ + 3ꢀꢃ + 2ꢀꢄ ≤ 17
ꢇ
ꢇ
ꢀ ≥ 0, ꢀ ∈ ℤ, ꢈ = 1,2,3,4
ꢇ
ꢇ
Bài 4: Giải công thức đệ quy:
ꢆꢁ = 6, ꢆꢂ = 42
Bài 4: Giải công thức đệ quy:
ꢑ
ꢆꢒ = 1, ꢆꢁ = 2
ꢆꢓ = ꢆꢓꢎꢁ + 6ꢆꢓꢎꢂ + 6ꢐ (ꢐ ≥ 3)
ꢑ
ꢆꢓ = 8ꢆꢓꢎꢁ − 16ꢆꢓꢎꢂ + 6ꢐ + 2 (ꢐ ≥ 2)
Bài 5: Trong mạng G=(V,E) cho luồng f như sau:
Bài 5: Trong mạng G=(V,E) cho luồng f như sau:
a) Xây dựng đồ thị tăng luồng Gf.
b) Cho biết luồng f có cực đại không ? Nếu không, hãy thực hiện tìm luồng
cực đại và lát cắt hẹp nhất của mạng trên.
a) Xây dựng đồ thị tăng luồng Gf. Từ đó chứng minh f là luồng cực đại.
b) Đưa ra giá trị luồng cực đại và lát cắt hẹp nhất.
Đề thi mô n: TOÁ N RỜI RẠC – K52
Thời gian: 90 phút
Đề thi mô n: TOÁ N RỜI RẠC – K52
Thời gian: 90 phút
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề)
Bài 1:
Bài 1:
a) Trường ĐHBKHN tiến hành phát học bổng cho sinh viên. Biết rằng có ba loại
học bổng, hỏi cần trao học bổng cho ít nhất bao nhiêu sinh viên để chắc chắn rằng
trong số họ có ít nhất 13 người nhận học bổng cùng loại ?
a) Trường ĐHBKHN tiến hành phát học bổng cho sinh viên. Biết rằng có năm
loại học bổng, hỏi cần trao học bổng cho ít nhất bao nhiêu sinh viên để chắc chắn
rằng trong số họ có ít nhất 28 người nhận học bổng cùng loại ?
b) Một máy bán tem tự động chỉ nhận loại tiền xu 1$, tiền giấy 1$ và tiền giấy 5$.
Tìm số cách đưa 30 $ vào máy (có chú ý đến thứ tự của xu và giấy bỏ vào).
b) Tìm số cách đặt các dấu ngoặc đơn vào tích của n + 1 số ꢀꢒꢀꢁ … ꢀꢓ để xác định
thứ tự của phép nhân. Ví dụ có 5 cách đặt dấu ngoặc đơn cho tích ꢀꢒꢀꢁꢀꢂꢀꢃ để
(
)
(
)
(
)(
)
các định thứ tự phép nhân: ꢗ ꢀꢒꢀꢁ ꢀꢂꢘꢀꢃ, ꢗꢀꢒ ꢀꢁꢀꢂ ꢘꢀꢃ, ꢀꢒꢀꢁ ꢀꢂꢀꢃ ,
Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số:
(
)
(
)
ꢀꢒꢗ ꢀꢁꢀꢂ ꢀꢃꢘ, ꢀꢒ(ꢀꢁ ꢀꢂꢀꢃ ).
A
0
B
5
0
∞
∞
1
C
∞
4
0
2
D
3
6
∞
0
∞
∞
E
∞
∞
4
2
0
F
∞
∞
3
∞
2
Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số:
A
B
C
D
E
F
∞
∞
∞
∞
∞
A
0
B
3
C
∞
3
D
3
E
∞
1
F
∞
∞
1
A
B
C
D
E
F
∞
∞
∞
∞
∞
0
4
∞
0
∞
∞
∞
∞
∞
∞
∞
∞
0
1
∞
∞
3
2
0
∞
∞
∞
0
∞
1
0
a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh E đến các đỉnh
còn lại của đồ thị G.
b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng
cực đại và lát cắt nhỏ nhất của mạng G.
c) Gọi G’ là phiên bản vô hướng của G (tức là không xét tới hướng của các cung
trên G). Thực hiện thuật toán Kruskal tìm cây khung nhỏ nhất của đồ thị G’.
a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh C đến các đỉnh
còn lại của đồ thị G.
b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng
cực đại và lát cắt nhỏ nhất của mạng G.
c) Gọi G’ là phiên bản vô hướng của G (tức là không xét tới hướng của các cung
trên G). Thực hiện thuật toán Prim tìm cây khung nhỏ nhất của đồ thị G’.
Bài 3: Giải công thức đệ quy sau:
ꢆꢒ = −2, ꢆꢁ = 0, ꢆꢂ = 5
Bài 3: Giải công thức đệ quy sau:
ꢑ
ꢆꢓ = 7ꢆꢓꢎꢁ − 16ꢆꢓꢎꢂ + 12ꢆꢓꢎꢃ + ꢐ4ꢓ (ꢐ ≥ 3)
ꢆꢒ = 1, ꢆꢁ = 4
ꢑ
ꢆꢓ = 4ꢆꢓꢎꢁ − 3ꢆꢓꢎꢂ + 2ꢓ + ꢐ + 3 (ꢐ ≥ 2)
5 trang
20220
Free
Bạn đang xem tài liệu "Đề thi Cuối kì môn Toán rời rạc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_thi_cuoi_ki_mon_toan_roi_rac.pdf
