Tài liệu Câu hỏi ôn tập toán rời rạc HVNNVN

Câu hỏi ôn tập Chương 2: Bài toán đếm Câu 1.1 Cho dãy số {an} xác định bởi hệ thức truy hồi (Dạng tuyến tính thuần nhất bậc 2, 3 với hệ số hằng) 1. Tìm công thức trực tiếp tính an theo n. 2. Tính am (với m cho trước). Câu 1.2 1. Tìm số nghiệm nguyên không âm của một phương trình. 2. Bằng phương pháp sinh phần tử kế tiếp liệt kê tất cả các tổ hợp chập k của n phần tử {1, 2, ..., n} theo thứ tự tự nhiên (chẳng hạn liệt kê 5 tổ hợp tiếp theo kể từ một tổ hợp cho trước). 3. Bằng phương pháp sinh phần tử kế tiếp liệt kê tất cả các hoán vị của n phần tử {1, 2, ..., n} theo thứ tự tự nhiên (chẳng hạn liệt kê 5 hoán vị tiếp theo kể từ một hoán vị cho trước). Câu 1.3 1. Có bao nhiêu xâu nhị phân có độ dài n trong đó có đúng k bít 0. 2. Có bao nhiêu cách lấy ra k phần tử trong n phần tử xếp trên một đường thẳng (hoặc xếp trên một đường tròn) sao cho không có hai phần tử kề nhau nào được lấy ra. 3. Dùng cây nhị phân, hãy liệt kê tất cả các xâu nhị phân có độ dài n và không có hai bít 1 đứng liền nhau. Chương 3: Các khái niệm cơ bản về đồ thị Câu 2.1 1. Tìm ma trận kề của G. Tìm ma trận liên thuộc của G. Tìm số đường đi khác nhau có độ dài k từ đỉnh xi đến đỉnh xj trong đồ thị? 2. Xác định bậc của các đỉnh? Xác định đỉnh cắt, cạnh cắt (cầu) của đồ thị G ? 3. Nêu định nghĩa đồ thị vô hướng liên thông. Đồ thị G có liên thông không? 4. Nêu định nghĩa đồ thị có hướng liên thông mạnh? Đồ thị G có liên thông mạnh không? 5. Nêu định nghĩa đồ thị định hướng được? Đồ thị G có định hướng được không? Tại sao? Hãy định hướng cho các cạnh của G để được một đồ thị có hướng liên thông mạnh (nếu có). 6. Nêu định nghĩa đồ thị phân đôi. Áp dụng thuật toán nhận biết đồ thị phân đôi, hãy chỉ ra G có phải là đồ thị phân đôi không? Hãy biểu diễn hình học đồ thị G dưới dạng phân đôi (nếu có). 7. Hai đồ thị sau có đẳng cấu với nhau không? 8. Nêu định nghĩa số ổn định ngoài của đồ thị. Tìm số ổn định ngoài của G. 9. Nêu định nghĩa số ổn định trong của đồ thị. Tìm số ổn định trong của G. 10. Nêu định nghĩa sắc số của đồ thị. Tìm sắc số của G. 11. Nêu định nghĩa nhân của đồ thị. Tìm tất cả các nhân có số phần tử ít nhất của G. 12. Tìm số màu tối thiểu để tô màu cho một bản đồ cho trước (sao cho các vùng có chung đường , 13. Lập lịch thi cho một tình huống cho trước (sao cho không có hai sinh viên nào phải thi hai môn vào cùng một thời điểm). Chương: 4, 5, 6 Câu 3.1 Cho đồ thị G không trọng số 1. Đồ thị G có phải đồ thị Euler, nửa Euler không? Tại sao? Tìm chu trình Euler hoặc đường đi Euler (nếu có). 2. Đồ thị G có phải đồ thị Hamilton, nửa Hamilton không? Tại sao? Tìm chu trình Hamilton hoặc đường đi Hamilton (nếu có). 3. Nêu định nghĩa cây khung của đồ thị. Tìm cây khung của G theo thuật toán ưu tiên chiều sâu. 4. Nêu định nghĩa cây khung của đồ thị. Tìm cây khung của G theo thuật toán ưu tiên chiều rộng. 5. Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị (ở đây độ dài của đường đi từ đỉnh A đến đỉnh B là số cạnh có mặt trong đường đi đó). 6. Giải bài toán người đưa thư Trung Hoa (hay tìm một hành trình ngắn nhất, tức là hành trình đi qua ít cạnh nhất) với đồ thị G cho trước. Câu 3.2 Cho cây nhị phân T. 1. Xác định các lá và chiều cao của cây. 2. Hãy duyệt cây T (đưa ra danh sách các đỉnh của cây T) theo thuật toán duyệt tiền thứ tự. 3. Hãy duyệt cây T (đưa ra danh sách các đỉnh của cây T) theo thuật toán duyệt trung thứ tự. 4. Hãy duyệt cây T (đưa ra danh sách các đỉnh của cây T) theo thuật toán duyệt hậu thứ tự. Câu 3.3 1. Nêu khái niệm mã tiền tố? Kiểm tra xem bảng mã đã cho có phải là mã tiền tố không? Tại sao? 2. Hãy áp dụng thuật toán Huffman, tìm mã tiền tố tối ưu nhất cho bản tin Y sử dụng các kí tự trong tập X với tần suất cho trước. Câu 3.4 Cho đồ thị G có trọng số (như hình vẽ hoặc cho bởi ma trận kề) 1. Nêu định nghĩa cây khung nhỏ nhất của đồ thị. 2. Áp dụng thuật toán Kruskal tìm cây khung nhỏ nhất của G. 3. Áp dụng thuật toán Prim tìm cây khung nhỏ nhất của G. 4. Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến đỉnh B của đồ thị. 5. Xem G là một mạng với đỉnh phát là A, đỉnh thu là B, khả năng thông qua trên các cung là trọng số cho trên hình vẽ. Biết luồng φ ban đầu bằng 0, áp dụng thuật toán Ford – Fulkerson hãy tìm luồng cực đại và lát cắt hẹp nhất của mạng G. Câu 3.5 Giải bài toán du lịch với ma trận chi phí cho trước. Câu 3.6. Cho đồ thị vô hướng đầy đủ Kn với n lẻ, các đỉnh được đánh số lần lượt từ 1 đến n. Liệt kê tất cả các chu trình Hamilton khác nhau và khác với chu trình 123…n1 của Kn. (Hai chu trình Hamilton được coi là khác nhau nếu chúng không có cạnh chung). (*bỏ qua*) Câu 3.7. Đồ thị sau là đồ thị phẳng hay không phẳng? Tại sao? Chương 7: Logic mệnh đềề 1. Áp dụng các luật logic mệnh đề (bảng giá trị chân lý) hoặc các công thức đồng nhất bằng nhau quan trọng hoặc thuật toán tìm dạng hội chuẩn tắc (tuyển chuẩn tắc) chứng minh công thức là đồng nhất đúng (đồng nhất sai). 2. Tìm công thức đối ngẫu của công thức cho trước. 3. Tìm công thức thu gọn, phủ định của một công thức cho trước trong logic vị từ. 4. Xác định giá trị chân lý của một công thức cho trước trong logic vị từ.