Bài giảng Ngân hàng câu hỏi thi tự luận

Nội dung text: Bài giảng Ngân hàng câu hỏi thi tự luận

1. NGÂN HÀNG CÂU HỎI THI TỰ LUẬN Tên học phần: Toán rời rạc 1 Mã học phần: Ngành đào tạo : Công nghệ thông tin Trình độ đào tạo: Đại học 1. Sử dụng bảng giá trị, chứng minh : (p q) = (p v q) 2. Sử dụng bảng giá trị, chứng minh : (p v (p  q)) = p  q 3. Sử dụng bảng giá trị, chứng minh : (p  q) (p v q) = T 4. Sử dụng bảng giá trị, chứng minh : (p  q) = (p q)  (q p) 5. Sử dụng bảng giá trị, chứng minh : p (q r) = q (p  r) 6. Sử dụng bảng giá trị, chứng minh : (p r)  (q r) = (p  q) r 7. Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh hoán vị theo thứ tự từ điển, tìm 4 hoán vị liền kề tiếp theo của hoán vị 568397421. 8. Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh hoán vị theo thứ tự từ điển, tìm 4 hoán vị liền kề tiếp theo của hoán vị 458796321. 9 . Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh hoán vị theo thứ tự từ điển, tìm 4 hoán vị liền kề tiếp theo của hoán vị 139587642. 10. Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh hoán vị theo thứ tự từ điển, tìm 4 hoán vị liền kề tiếp theo của hoán vị 236897541. 11 . Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh tổ hợp chập k của một tập hợp theo thứ tự từ điển, hãy tạo 4 tổ hợp chập 4 liền kề tiếp theo của tổ hợp 2,6,8,9.
2. 12. Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh tổ hợp chập k của một tập hợp theo thứ tự từ điển, hãy tạo 4 tổ hợp chập 4 liền kề tiếp theo của tổ hợp 3,5,7,8. 13. Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh tổ hợp chập k của một tập hợp theo thứ tự từ điển, hãy tạo 4 tổ hợp chập 4 liền kề tiếp theo của tổ hợp 4,6,7,9. 14. Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh tổ hợp chập k của một tập hợp theo thứ tự từ điển, hãy tạo 4 tổ hợp chập 4 liền kề tiếp theo của tổ hợp 1,5,6,8. 15. Có bao nhiêu biển số xe bắt đầu bằng 2 hoặc 3 chữ cái in hoa và kết thúc là 3 hoặc 4 chữ số, biết rằng có 26 chữ cái trong bảng chữ cái tiếng anh? (VD : RS 0912 là 1 biển số). 16. Có bao nhiêu biển số xe bắt đầu bằng 3 hoặc 4 chữ cái in hoa và kết thúc là 2 hoặc 3 chữ số, biết rằng có 26 chữ cái trong bảng chữ cái tiếng anh? (VD : ABZ 09 là 1 biển số). 17. Có bao nhiêu số nguyên trong khoảng từ 1000 đến 5000 chia hết cho 6 hoặc 9 ? 18. Có bao nhiêu số nguyên trong khoảng từ 5000 đến 9999 chia hết cho 8 hoặc 12 ? 19. Giả sử tất cả các số điện thoại trên thế giới đều theo quy tắc, bắt đầu bằng mã quốc gia dài từ 1 đến 3 chữ số, tức là có dạng X, XX hoặc XXX ; tiếp theo là 10 chữ số dạng NXX- NXX-XXXX trong đó N có thể nhận giá trị từ 1 đến 6, X biểu thị một chữ số từ 0 đến 9. Theo cách đánh số này, sẽ có tối đa bao nhiêu số điện thoại có thể dùng ? 20. Giả sử tất cả các số điện thoại trên thế giới đều theo quy tắc, bắt đầu bằng mã quốc gia dài từ 1 đến 3 chữ số, tức là có dạng X, XX hoặc XXX ; tiếp theo là 10 chữ số dạng NNX- NXX-XXXX trong đó N có thể nhận giá trị từ 5 đến 9, X biểu thị một chữ số từ 0 đến 9. Theo cách đánh số này, sẽ có tối đa bao nhiêu số điện thoại có thể dùng ? 21. Lớp học có 55 bạn nam và 35 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam bằng số bạn nữ, biết rằng đội văn nghệ cần ít nhất 6 thành viên và nhiều nhất 10 thành viên. 22. Lớp học có 60 bạn nam và 42 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam bằng số bạn nữ, biết rằng đội văn nghệ cần ít nhất 4 thành viên và nhiều nhất 8 thành viên.
3. 23. Lớp học có 50 bạn nam và 20 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam đúng bằng 2 lần số bạn nữ, biết rằng đội văn nghệ cần ít nhất 6 thành viên và nhiều nhất 12 thành viên. 24. : Lớp học có 60 bạn nam và 25 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam đúng bằng 2 lần số bạn nữ, biết rằng đội văn nghệ cần ít nhất 3 thành viên và nhiều nhất 9 thành viên. 25. Trong kỳ thi tuyển sinh đại học khối A, các thí sinh thi trắc nghiệm môn Lý và Hóa, mỗi môn thi có 50 câu hỏi. Mỗi câu hỏi có đúng 4 phương án trả lời và chỉ được lựa chọn tối đa 1 phương án. Mỗi câu trả lời đúng được 0.2 điểm, câu trả lời sai hoặc không trả lời thì không được điểm. a) Hãy cho biết có bao nhiêu cách điền phiếu trắc nghiệm môn Lý. b) Cần có ít nhất bao nhiêu thí sinh tham gia để có ít nhất 10 sinh viên có tổng điểm Lý và Hóa bằng nhau. Biết rằng điểm thi không được làm tròn. 26. Trong kỳ thi tuyển sinh đại học khối A, các thí sinh thi trắc nghiệm môn Lý và Hóa, mỗi môn thi có 40 câu hỏi. Mỗi câu hỏi có đúng 5 phương án trả lời và chỉ được lựa chọn tối đa 1 phương án. Mỗi câu trả lời đúng được 0.25 điểm, câu trả lời sai hoặc không trả lời thì không được điểm. a) Hãy cho biết có bao nhiêu cách điền phiếu trắc nghiệm môn Hóa. b) Cần có ít nhất bao nhiêu thí sinh tham gia để có ít nhất 10 sinh viên có tổng điểm Lý và Hóa bằng nhau, biết rằng điểm thi không được làm tròn. 27. Một bài thi trắc nghiệm có 30 câu hỏi, mỗi câu hỏi có 5 phương án trả lời và chỉ có 1 phương án đúng. Mỗi câu trả lời đúng được 3 điểm, trả lời sai bị trừ 1 điểm, nếu không trả lời thì câu đó nhận 0 điểm. Biết rằng tổng điểm thấp nhất là 0. Hãy cho biết: a) Có bao nhiêu cách điền phiếu trắc nghiệm (mỗi câu chỉ được chọn tối đa 1 phương án). b) Cần bao nhiêu sinh viên tham gia thi để đảm bảo có ít nhất 2 sinh viên có cùng kết quả thi. 28. Một bài thi trắc nghiệm có 35 câu hỏi, mỗi câu hỏi có 4 phương án trả lời và chỉ có 1 phương án đúng. Mỗi câu trả lời đúng được 3 điểm, trả lời sai bị trừ 1 điểm, nếu không trả lời thì câu đó nhận 0 điểm. Biết rằng tổng điểm thấp nhất là 0. Hãy cho biết: a) Có bao nhiêu cách điền phiếu trắc nghiệm (mỗi câu chỉ được chọn tối đa 1 phương án). b) Cần bao nhiêu sinh viên tham gia thi để đảm bảo có ít nhất 2 sinh viên có cùng kết quả thi.
4. 29. Phương trình x1 + x2 + x3 = 13 có bao nhiêu nghiệm nguyên không âm thỏa mãn a) x1 1, x2 3, x3 0 b) x1 0, x2 3, x3 5 30. Phương trình x1 + x2 + x3 = 15 có bao nhiêu nghiệm nguyên không âm thỏa mãn a) x1 2, x2 0, x3 4 b) x1 1, x2 0, x3 7 31. Phương trình x1 + x2 + x3 = 14 có bao nhiêu nghiệm nguyên không âm thỏa mãn a) x1 0, x2 3, x3 1 b) x1 0, x2 6, x3 3, 32. Phương trình x1 + x2 + x3 = 16 có bao nhiêu nghiệm nguyên không âm thỏa mãn c) x1 2, x2 0, x3 2 d) x1 6, x2 3, x3 0 33. a) Giải hệ thức truy hồi sau a0 = 2, a1 = 6, an = 3an-1 - 2an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n chứa 3 số 0 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 7. 34. a) Giải hệ thức truy hồi sau a0 = 4, a1 = 8, an = an-1 + 2an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n chứa 3 số 1 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 6. 35. a) Giải hệ thức truy hồi sau a0 = 1, a1 = 5, an = -an-1 + 6an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, bắt đầu bằng số 1 và có chứa 2 số 1 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 7.
5. 36. a) Giải hệ thức truy hồi sau a0 = 6, a1 = 7, an = an-1 + 6an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, kết thúc bằng số 1 và có chứa 2 số 1 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 6. 37. a) Giải hệ thức truy hồi sau a0 = 5, a1 = 4, an = an-1 + 2an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, bắt đầu bằng số 0 và có chứa 2 số 1 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 7. 38. a) Giải hệ thức truy hồi sau a0 = 8, a1 = 3, an = -an-1 + 2an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, kết thúc bằng số 0 và có chứa 2 số 1 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 6. 39. a) Giải hệ thức truy hồi sau a0 = 5, a1 = 2, an = -3an-1 + 4an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, bắt đầu bằng số 1 và có chứa 2 số 0 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 7. 40. a) Giải hệ thức truy hồi sau a0 = 6, a1 = 9, an = 3an-1 + 4an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, kết thúc bằng số 1 và có chứa 2 số 0 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 6. 41. a) Giải hệ thức truy hồi sau a0 = 6, a1 = 9, an = 7an-1 - 12an-2 với n 2
6. b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, bắt đầu bằng số 0 và có chứa 2 số 0 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 7. 41. a) Giải hệ thức truy hồi sau a0 = 8, a1 = 7, an = -an-1 + 12an-2 với n 2 b) Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, kết thúc bằng số 0 và có chứa 2 số 0 liên tiếp. c) Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n = 6. 42. Hãy tìm nghiệm của công thức truy hồi với điều kiện đầu dưới đây: a) an = 3an-1 với a0 =2. b) an = -4an-1 - 4an-2 với n 2 và a0 =0 và a1 =1. c) an = 14an-1 - 49an-2 với n 2 và a0 =3 và a1 = 35. 43. Hãy tìm nghiệm của công thức truy hồi với điều kiện đầu dưới đây: a) an = an-1 + 2 với a0 =3. b) an = -4an-1 - 4an-2 với n 2 và a0 =0 và a1 =1. c) an = 13an-1 - 22an-2 với n 2 và a0 =3 và a1 = 15. 44. Hãy tìm nghiệm của công thức truy hồi với điều kiện đầu dưới đây: a) an = an-1 + 2n + 3 với a0 =4. b) an = -6an-1 - 9an-2 với n 2 và a0 =3 và a1 =-3. c) an = 2an-1 + 5an-2 - 6an-3 với n 3 và a0 =7 và a1 =-4, a2 =8. 45. Hãy tìm nghiệm của công thức truy hồi với điều kiện đầu dưới đây: n a) an = an-1 + 2 với a0 =1. b) an = 14an-1 - 49an-2 với n 2 và a0 =3 và a1 = 35. c) an = 2an-1 + an-2 - 2an-3 với n 3 và a0 =3 và a1 =6, a2 =0. 46. Hãy tìm nghiệm của công thức truy hồi với điều kiện đầu dưới đây: n a) an = an-1 + 2 với a0 =1. b) an = -13an-1 - 22an-2 với n 2 và a0 =3 và a1 = 15. c) an = 2an-1 + 5an-2 - 6an-3 với n 3 và a0 =7 và a1 =-4, a2 =8. 46. Hãy tìm nghiệm của công thức truy hồi với điều kiện đầu dưới đây: a) an = -4an-1 - 4an-2 với n 2 và a0 =0 và a1 =1. b) an = 2an-1 + an-2 - 2an-3 với n 3 và a0 =3 và a1 =6, a2 =0. c) an = 7an-2 + 6an-3 với n 3 và a0 =9 và a1 =10, a2 =32.
7. 47. Phương trình x1 + x2 + x3 + x4 + x5 +x6 = 24 có bao nhiêu nghiệm nguyên không âm sao cho a) xi 2 với i=1, 2, 3, 4, 5, 6? b) 1 x1 5 và x3 8? c) 1 x1 5 và 3 x2 7? d) 1 x1 5 và 3 x2 7 và x3 8? 48. Hãy tìm tất cả các số tự nhiên có 7 chữ số thỏa mãn: a) Số có 7 chữ số tạo thành một số thuận nghịch; b) Số có 7 chữ số tạo thành một số thuận nghịch và có tất cả các chữ số đều khác 0; c) Số có 7 chữ số có tổng các chữ số là 18; 49. Hãy tìm tất cả các số tự nhiên có 9 chữ số thỏa mãn: a) Số có 9 chữ số tạo thành một số thuận nghịch; b) Số có 9 chữ số tạo thành một số thuận nghịch và có tất cả các chữ số đều khác 0; c) Số có 7 chữ số có tổng các chữ số là 19; 50. Hãy tìm tất cả các số tự nhiên có 10 chữ số thỏa mãn: a) Số có 10 chữ số tạo thành một số thuận nghịch; b) Số có 10 chữ số tạo thành một số thuận nghịch và có tất cả các chữ số đều khác 0; c) Số có 10 chữ số có tổng các chữ số là 18. 51. a) Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n và không có k số 1 liên tiếp? b) Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n có ít nhất một dãy k số 1 liên tiếp? 52. a) Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n và không có k số 0 liên tiếp? b) Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n có ít nhất một dãy k số 0 liên tiếp? 53. a) Một hệ thống máy tính coi một xâu các chữ số hệ thập phân là một từ mã hợp lệ nếu nó chứa một số chẵn chữ số 1. Ví dụ 1231407869 là hợp lệ, 120987045608 là không hợp lệ. Giả sử an là số các từ mã độ dài n. Hãy tìm hệ thức truy hồi và điều kiện đầu cho an? b) Giải hệ thức truy hồi an = 2an-1 + an-2 - 2an-3 với n 3 và a0 =3 và a1 =6, a2 =0. 54. Phương trình x1 x2 x3 x4 x5 x6 25 có bao nhiêu nghiệm nguyên không âm thỏa mãn a) x1 1, x2 2, x3 3, x4 4, x5 5 , x6 6? b) 2 x1 7, 4 x2 8; x3 5?
8. 55. a) Một hệ thống máy tính coi một xâu các chữ số hệ thập phân là một từ mã hợp lệ nếu nó chứa một số lẻ chữ số 0. Ví dụ 1231407869 là hợp lệ, 12098704568 là không hợp lệ. Giả sử an là số các từ mã độ dài n. Hãy tìm hệ thức truy hồi và điều kiện đầu cho an? b) Giải hệ thức truy hồi an = 7an-2 + 6an-3 với n 3 và a0 =9 và a1 =10, a2 =32. 56. Phương trình x1 x2 x3 x4 x5 x6 28 có bao nhiêu nghiệm nguyên không âm thỏa mãn a) x1 1, x2 2, x3 3, x4 4, x5 5 , x6 6? b) 1 x1 6, 4 x2 9; x3 4? 57. Dùng bảng chân lý để chứng minh luật giao hoán: a) p  q q  p b) p  q q  p 58. Dùng bảng chân lý để chứng minh luật kết hợp a) p  q  r p  q  r b) p  q  r p  q  r 59. Dùng bảng chân lý để chứng minh luật phân phối a) p  q  r p  q  p  r b) p  q  r p  q  p  r 60. Dùng bảng chân lý để chứng minh luật De Morgan a) p  q p  q b) p  q p  q 61. Dùng bảng chân lý để chứng minh các mệnh đề kéo theo dưới đây là hằng đúng. a) p  q p b) p p  q c) p p q d) p  q p q e) p q p f) p q q 62. Dùng bảng chân lý để chứng minh các mệnh đề kéo theo dưới đây là hằng đúng. a) p  p  q  q b)  p q  q r  p r c) p  p q  q d)  p  q  p r  q r  r 63. Chứng minh các cặp mệnh đề dưới đây là tương đương. a) p  q p  q  p  q b) p q q p c) p  q p  q d) p  q p  q
9. 64. Không dùng bảng chân lý chứng minh các mệnh đề kéo theo dưới đây là hằng đúng. a) p  q p b) p p  q c) p p q d) p  q p q e) p q p f) p q q 65. Không dùng bảng chân lý chứng minh các mệnh đề kéo theo dưới đây là hằng đúng. a) p  p  q  q b)  p q  q r  p r c) p  p q  q d)  p  q  p r  q r  r 66. Không dùng bảng chân lý, chứng minh các cặp mệnh đề dưới đây là tương đương. a) p  q p  q  p  q b) p q q p c) p  q p  q d) p  q p  q 67. Cho A, B, C là các tập hợp. Chứng minh rằng: a) B A  C A B  C A b) A B A  B c) A  B  A  B A d) A  B  C A  B  C e) A B C A B B C 68. a) Trình bày thuật toán nhánh cận giải bài toán cái túi? b) Áp dụng thuật toán nhánh cận giải bài toán cái túi dưới đây, chỉ rõ kết quả theo mỗi bước thực hiện của thuật toán? 5x1 x2 9x3 3x4 max, 4x1 2x2 7x3 3x4 10, x j 0,1, j 1,2,3,4.
10. 69. a) Trình bày thuật toán nhánh cận giải bài toán cái túi? b) Áp dụng thuật toán nhánh cận giải bài toán cái túi dưới đây, chỉ rõ kết quả theo mỗi bước thực hiện của thuật toán? 7x1 3x2 2x3 x4 max, 5x1 3x2 6x3 4x4 12, x j 0,1, j 1,2,3,4 70. a) Trình bày thuật toán nhánh cận giải bài toán cái túi? b) Áp dụng thuật toán nhánh cận giải bài toán cái túi dưới đây, chỉ rõ kết quả theo mỗi bước thực hiện của thuật toán? 30x1 19x2 13x3 38x4 20x5 6x6 8x7 19x8 10x9 11x10 max, 15x1 12x2 9x3 27x4 15x5 5x6 8x7 20x8 12x9 15x10 62 x j 0,1, j 1,2,10. 71. Giải bài toán người du lịch với ma trận chi phí như sau: 31 15 23 10 17 16 24 07 12 12 34 03 25 54 25 15 20 33 50 40 16 10 32 03 23 18 20 13 28 21 72. Giải bài toán người du lịch với ma trận chi phí như sau: 03 93 13 33 09 04 77 42 21 16 45 17 36 16 28 39 90 80 56 07 28 46 88 33 25 03 88 18 46 92