Đề thi Toán Rời Rạc - ĐH GTVT

Bé m«n khoa häc m¸y tÝnh §Ò 11: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Có bao nhiêu cách chọn 8 tờ giấy bạc trong số 10 tờ 20 nghìn, 20 tờ 50 nghìn và 100 tờ 100 nghìn? Giải thích? b. Giải công thức truy hồi với các điều kiện đầu sau: an = 5an -1 – 6an -2 n>=2, a0 = 0, a1 = 1. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng xÐt xem hai c«ng thøc sau cã t­¬ng ®­¬ng kh«ng? P ↔ Q vµ ⌐P ↔ ⌐ Q B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


3. Cho R lµ quan hÖ trªn tËp {1, 2, 3, 4} chøa c¸c cÆp ®­îc s¾p (1, 2), (2, 3), (2, 2), (3, 2) (3, 4), (4, 4), (4, 1). Hái R cã tÝnh chÊt ph¶n x¹, ®èi xøng vµ b¾c cÇu kh«ng ? T¹i sao? TÝnh R-1 , R2 , R3. 4. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Kruskal. Chän ®Ønh G lµm gèc c©y khung ®ã. §¸nh sè ®Ønh sao cho nh·n cña gèc nhá h¬n nh·n cña ngän . Nªu c¸ch duyÖt c©y khung ®ã theo tiÒn, trung vµ hËu thø tù. G 4 6 5 2 3 5 4 5 4 2 3 7 5. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh S ®Õn ®Ønh Z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n Dijkstra. S 2 13 4 7 9 6 4 2 9 Z Bé m«n khoa häc m¸y tÝnh §Ò 10: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Có bao nhiêu xâu nhị phân khác nhau có thể lập được, nếu dùng 6 chữ số 1 và 8 chữ số 0 ? Giải thích? b. Giải công thức truy hồi với các điều kiện đầu sau: an = 4an -1 – 4an -2 n>=2, a0 = 6, a1 = 8. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: ((P ( Q) ( (P ( R)) ( (P ( (Q ( R) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


3. Quan hÖ “chia hÕt” trªn tËp c¸c sè nguyªn d­¬ng cã ph¶i lµ quan hÖ cã c¸c tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu kh«ng (“a chia hÕt cho b, nÕu a = k.b, víi k lµ sè nguyªn”)? T¹i sao? 4. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Prim. G 7 6 5 2 3 5 4 4 4 2 3 7 5. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh S ®Õn ®Ønh Z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n DÞkstra: S 2 13 4 7 9 6 4 2 9 Z Bé m«n khoa häc m¸y tÝnh §Ò 12: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Có bao nhiêu xâu nhị phân có độ dài 10 và không chứa 8 chữ số 1 liên tiếp? Giải thích? b. Giải công thức truy hồi với các điều kiện đầu sau: an = 6an -1 - 8an -2 n>=2, a0 = 4, a1 = 10. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: ((P ( Q) ∧ (P ( R)) ( (P ( (Q ∧ R)) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


3. 3. Cho R lµ quan hÖ trªn tËp {1, 2, 3, 4} chøa c¸c cÆp ®­îc s¾p (1, 3), (2, 1), (2, 4), (3, 1) (3, 2), (4, 4), (4, 2). Hái R cã tÝnh chÊt ph¶n x¹, ®èi xøng vµ b¾c cÇu kh«ng ? T¹i sao? TÝnh R-1 , R2 , R3. 4. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Prim. Chän ®Ønh G lµm gèc c©y khung ®ã. §¸nh sè ®Ønh sao cho nh·n cña gèc nhá h¬n nh·n cña ngän . Nªu c¸ch duyÖt c©y khung ®ã theo tiÒn, trung vµ hËu thø tù. G 3 6 4 5 2 5 3 4 2 5 4 3 5. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh S ®Õn ®Ønh Z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n Dijkstra: S 3 12 2 6 9 7 5 2 9 Z Bé m«n khoa häc m¸y tÝnh §Ò 11: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Có bao nhiêu cách chọn 8 tờ giấy bạc trong số 10 tờ 20 nghìn, 20 tờ 50 nghìn và 100 tờ 100 nghìn? Giải thích? b. Giải công thức truy hồi với các điều kiện đầu sau: an = 5an -1 – 6an -2 n>=2, a0 = 0, a1 = 1. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng xÐt xem hai c«ng thøc sau cã t­¬ng ®­¬ng kh«ng? P ↔ Q vµ ⌐P ↔ ⌐ Q B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


3. Quan hÖ “chia hÕt” trªn tËp c¸c sè nguyªn d­¬ng cã ph¶i lµ quan hÖ cã c¸c tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu kh«ng (“a chia hÕt cho b, nÕu a = k.b, víi k lµ sè nguyªn”)? T¹i sao? 4. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Prim. G 7 6 5 2 3 5 4 4 4 2 3 7 5. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh S ®Õn ®Ønh Z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n DÞkstra: S 2 13 4 7 9 6 4 2 9 Z Bé m«n khoa häc m¸y tÝnh §Ò 14: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Mét nhµ xuÊt b¶n cã 3000 cuèn s¸ch nh­ nhau. Cã bao nhiªu c¸ch cÊt chóng vµo 3 kho A, B, C. NÕu biÕt kho A chøa Ýt nhÊt 1000 cuèn th× cã bao nhiªu c¸ch. b. Giải công thức truy hồi với các điều kiện đầu sau: an = - 4an -1 + 5an -2 n>=2, a0 = 2, a1 = 8. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: ((P ( Q) ∧ (Q ( R)) ( (P ( R) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


Cho ∥ lµ quan hÖ song song trªn V lµ tËp c¸c vÐc t¬ trong kh«ng gian. Hái ∥ cã tÝnh chÊt ph¶n x¹, ®èi xøng vµ b¾c cÇu kh«ng? Quan hÖ ∥ cã lµ t­¬ng ®­¬ng kh«ng? 4. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Kruscal. Chän ®Ønh G lµm gèc c©y khung ®ã. §¸nh sè ®Ønh sao cho nh·n cña gèc nhá h¬n nh·n cña ngän . Nªu c¸ch duyÖt c©y khung ®ã theo tiÒn, trung vµ hËu thø tù. G 3 7 4 3 2 3 3 4 2 6 4 3 5. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh S ®Õn ®Ønh Z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n Dijkstra: S 4 19 3 8 10 7 2 2 9 Z Bé m«n khoa häc m¸y tÝnh §Ò 15: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Có thÓ t¹o ®­îc bao nhiªu ho¸n vÞ kh¸c nhau tõ c¸c ch÷ c¸i cña tõ PEPPERCORN. Vµ cã bao nhiªu ho¸n vÞ kh«ng cã 3 ch÷ P ®øng c¹nh nhau. b. Giải công thức truy hồi với các điều kiện đầu sau: an = 7an -1 – 10 an -2 n>=2, a0 = 2, a1 = 1. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng xÐt xem hai c«ng thøc sau cã t­¬ng ®­¬ng kh«ng? (P ∧ Q) → R vµ ¬R → (⌐ P v ⌐Q) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


3. Cho ~ lµ quan hÖ ®ång d¹ng trªn T lµ tËp c¸c tam gi¸c trªn mÆt ph¼ng. Hái quan hÖ ~ cã c¸c tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu kh«ng? Quan hÖ ~ cã lµ t­¬ng ®­¬ng kh«ng? 4. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Prim. Chän ®Ønh G lµm gèc c©y khung ®ã. §¸nh sè ®Ønh sao cho nh·n cña gèc nhá h¬n nh·n cña ngän . Nªu c¸ch duyÖt c©y khung ®ã theo tiÒn, trung vµ hËu thø tù. G 8 4 3 2 3 5 4 5 2 2 3 6 5. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh S ®Õn ®Ønh Z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n DÞkstra: S 6 17 2 10 9 6 4 2 11 Z Bé m«n khoa häc m¸y tÝnh §Ò 5: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. b. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: ((P ( Q) & (Q ( R)) ( (P ( R) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng rót gän cña hµm Boole sau:


3. Quan hÖ ®ång d¹ng trªn tËp c¸c tam gi¸c cã ph¶i lµ quan hÖ t­¬ng ®­¬ng kh«ng? T¹i sao? 4. a. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ bªn. G 7 4 4 2 3 5 6 4 2 3 b. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn ®Ønh z trong ®å thÞ sau: Bé m«n khoa häc m¸y tÝnh §Ò 5: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. b. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: ((P ( Q) & (Q ( R)) ( (P ( R) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng rót gän cña hµm Boole sau:


3. Quan hÖ ®ång d¹ng trªn tËp c¸c tam gi¸c cã ph¶i lµ quan hÖ t­¬ng ®­¬ng kh«ng? T¹i sao? 4. a. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ bªn. G 7 4 4 2 3 5 6 4 2 3 b. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn ®Ønh z trong ®å thÞ sau: §Ò 6: m«n to¸n rêi r¹c, thêi gian 90 phót §èi víi mét x©u ký tù L ta cã phÐp to¸n lÊy phÇn tö ®Çu tiªn cña x©u lµ head(L) vµ phÐp lÊy khóc ®u«i cña x©u L sau khi bá phÇn tö ®Çu tiªn lµ tail (L). ViÕt thñ tôc ®Ö qui t×m x©u nghÞch ®¶o cña mét x©u ký tù L. 2. Dïng kü thuËt quay lui vÏ c©y liÖt kª ®Ó t×m xem cã tËp con cña tËp sau, mµ tæng c¸c phÇn tö cña tËp con ®ã b»ng 45: { 28, 24, 19, 15, 11, 9, 2} Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: (P ( (Q & R)) ( ((P ( Q) & (P ( R)) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. T×m d¹ng rót gän cña hµm Boole sau:
5. a. Nªu thø tù th¨m viÕng ®Ønh cña ®« thÞ sau theo chiªu s©u vµ theo chiÓu réng víi ®Ønh ®Çu lµ ®Ønh G. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ trªn. 5 2 2 5 1 2 4 3 4 6. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn ®Ønh z trong ®å thÞ sau: §Ò 7 m«n to¸n rêi r¹c, thêi gian 90 phót ViÕt thñ tôc ®Ö qui tÝnh tæ hîp chËp k tõ n phÇn tö Cnk . 2. Dïng kü thuËt quay lui vÏ c©y liÖt kª ®Ó t×m xem cã tËp con cña tËp sau, mµ tæng c¸c phÇn tö cña tËp con ®ã b»ng 47: { 28, 24, 19, 15, 11, 9, 4} Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c¸c ®¼ng thøc sau: (P v Q) ( R = (R ( ((P & ( Q) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. T×m d¹ng rót gän cña hµm Boole sau:
5 a. Nªu thø tù th¨m viÕng ®Ønh cña ®« thÞ sau theo chiªu s©u vµ theo chiÓu réng víi ®Ønh ®Çu lµ ®Ønh G. b. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ trªn. 3 5 1 2 5 2 3 4 3 2 3 5 9. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn ®Ønh z trong ®å thÞ sau: §Ò 8: m«n to¸n rêi r¹c, thêi gian 90 phót ViÕt thñ tôc ®Ö qui t×m gi¸ trÞ cña mét ®a th÷c bËc n: Dn = a0 + a1x0 + a2x02 + .. + an-1x0n-1+anx0n . 2. Dïng kü thuËt quay lui vÏ c©y liÖt kª ®Ó t×m xem cã tËp con cña tËp sau, mµ tæng c¸c phÇn tö cña tËp con ®ã b»ng 50: { 28, 24, 19, 15, 11, 9, 7} Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c¸c ®¼ng thøc sau: (Q.R) ( P = ( P( (( Q ( ( R) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. 5. T×m d¹ng rót gän cña hµm Boole sau:
6 a. Nªu thø tù th¨m viÕng ®Ønh cña ®« thÞ sau theo chiªu s©u vµ theo chiÓu réng víi ®Ønh ®Çu lµ ®Ønh G. b. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ trªn. 4 1 3 2 3 2 7 2 6 3 5 1 9. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn ®Ønh z trong ®å thÞ sau: Bé m«n khoa häc m¸y tÝnh §Ò 9: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Có bao nhiêu xâu nhị phân khác nhau có thể lập được, nếu dùng 6 chữ số 1 và 8 chữ số 0 ? Giải thích? b. Giải công thức truy hồi với các điều kiện đầu sau: an = 4an -1 – 4an -2 n>=2, a0 = 6, a1 = 8. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: ((P ( Q) ( (P ( R)) ( (P ( (Q ( R) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


3. Quan hÖ “chia hÕt” trªn tËp c¸c sè nguyªn d­¬ng cã ph¶i lµ quan hÖ thø tù bé phËn kh«ng (“a chia hÕt cho b, nÕu a = k.b, víi k lµ sè nguyªn”)? T¹i sao? TËp c¸c sè nguyªn d­¬ng víi quan hÖ “chia hÕt” cã t¹o thµnh dµn kh«ng? 4. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Prim. G 7 6 5 2 3 5 4 4 4 2 3 7 5. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh S ®Õn ®Ønh Z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n DÞkstra: S 2 13 4 7 9 6 4 2 9 Z Bé m«n khoa häc m¸y tÝnh §Ò 5: m«n to¸n rêi r¹c HÖ ChÝnh qui, thêi gian 90 phót 1. a. Cho phương trình x1 + x2 + … + x5 = 19, hỏi có bao nhiêu nghiệm nguyên, không âm? Giải thích? b. Giải công thức truy hồi với các điều kiện đầu sau: an = 5an -1 – 6an -2 n>=2, a0 = 0, a1 = 1. 2. a. Dïng phÐp biªn ®æi t­¬ng ®­¬ng chøng minh c«ng thøc sau lµ h»ng ®óng: ((P ( Q) & (Q ( R)) ( (P ( R) B¹n h·y lÊy mét vÝ dô cô thÓ minh ho¹ cho kh¼ng ®Þnh trªn. b. T×m d¹ng tuyÓn chuÈn t¾c rót gän cña hµm Boole sau:


3. Quan hÖ “®ång d¹ng” trªn tËp c¸c tam gi¸c cã ph¶i lµ quan hÖ t­¬ng ®­¬ng kh«ng? T¹i sao? T×m ®Æc tr­ng cña c¸c líp t­¬ng ®­¬ng? 4. a. T×m c©y khung nhá nhÊt cña ®å thÞ ë h×nh vÏ sau theo c¸c b­íc cña thuËt to¸n Kruskal. G 7 4 4 2 3 5 6 5 4 2 3 3 b. T×m ®­êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn ®Ønh z trong ®å thÞ sau theo c¸c b­íc cña thuËt to¸n DÞkstra: S 2