【正文】 b， aba} (4) {1， 11， 101， 001， 0011} 答：（ 2） 5一個圖的哈密爾頓路是一條通過圖中 ( )的路。 答：所有結(jié)點一次且恰好一次 5在有向圖中，結(jié)點 v的出度 deg+(v)表示 ( )，入度 deg(v)表示 ( )。 答：以 v為起點的邊的條數(shù)， 以 v為終點的邊的條數(shù) 5設(shè) G是一棵樹，則 G 的生成樹有 ( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能確定 答： 1 5 n階無向完全圖 Kn 的邊數(shù)是 ( )， 每個結(jié)點的度數(shù)是 ( )。 答： 2 )1( ?nn , n1 60、一棵無向樹的頂點數(shù) n與邊數(shù) m關(guān)系是 ( )。 答： m=n1 6一個圖的歐拉回路是一條通過圖中 ( )的回路。 答：所有邊一次且恰好一次 6有 n個結(jié)點的樹，其結(jié)點度數(shù)之和是 ( )。 答： 2n2 6下面給出的集合中，哪一個不是前綴碼 ( )。 (1) {a， ab， 110， a1b11} (2) {01， 001， 000， 1} (3) {1， 2， 00， 01， 0210} (4) {12， 11， 101， 002， 0011} 答： (1) 6 n個結(jié)點的有向完全圖邊數(shù)是 ( )，每個結(jié)點的度數(shù)是 ( )。 答： n(n1),2n2 6一個無向圖有生成樹的充分必要條件是 ( )。 答：它是連通圖 6設(shè) G是一棵樹， n,m分別表示頂點數(shù)和邊數(shù)，則 9 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能確定。 答：（ 3） 6設(shè) T=〈 V,E〉是一棵樹，若 |V|1，則 T中至少存在 ( )片樹葉。 答： 2 6任何連通無向圖 G至少有 ( )棵生成樹，當(dāng)且僅當(dāng) G 是 ( )，G的生成樹只有一棵。 答： 1，樹 6設(shè) G是有 n個結(jié)點 m條邊的連通平面圖，且有 k個面，則 k等于 : (1) mn+2 (2) nm2 (3) n+m2 (4) m+n+2。 答：（ 1） 70、設(shè) T是一棵樹，則 T是一個連通且 ( )圖。 答：無簡單回路 7設(shè)無向圖 G有 16條邊且每個頂點的度數(shù)都是 2，則圖 G有 ( )個頂點。 (1) 10 (2) 4 (3) 8 (4) 16 答：（ 4） 7設(shè)無向圖 G有 18條 邊且每個頂點的度數(shù)都是 3，則圖 G有 ( )個頂點。 (1) 10 (2) 4 (3) 8 (4) 12 答： (4) 7設(shè)圖 G=V， E， V={a， b， c， d， e}， E={a,b,a,c,b,c,c,d,d,e},則 G是有向圖還是無向圖？ 答：有向圖 7任一有向圖中，度數(shù)為奇數(shù)的結(jié)點有 ( )個。 答：偶數(shù) 7具有 6 個頂點， 12條邊的連通簡單平面圖中，每個面都是由 ( )條邊圍成？ (1) 2 (2) 4 (3) 3 (4) 5 答：（ 3） 10 7在有 n個頂點的連通圖中，其邊數(shù)（ ）。 (1) 最多有 n1條 (2) 至少有 n1 條 (3) 最多有 n條 (4) 至少有 n 條 答：（ 2） 7一棵樹有 2個 2度頂點， 1 個 3度頂點， 3個 4度頂點，則其 1度頂點為（ ）。 (1) 5 (2) 7 (3) 8 (4) 9 答：（ 4） 7若一棵完全二元（叉）樹有 2n1個頂點，則它（ ）片樹葉。 (1) n (2) 2n (3) n1 (4) 2 答：（ 1） 7下列哪一種圖不一定是樹（ ）。 (1) 無簡單回路的連通圖 (2) 有 n個頂點 n1條邊的連通圖 (3) 每對頂點間都有通路的圖 (4) 連通但刪去一條邊便不連通的圖 答：（ 3） 80、連通圖 G是一棵樹當(dāng)且僅當(dāng) G中（ ）。 (1) 有些邊是割邊 (2) 每條邊都是割邊 (3) 所有邊都不是割邊 (4) 圖中存在一條歐拉路徑 答：（ 2） （數(shù)理邏輯部分） 二、求下列各公式的主析取范式和主合取范式： (P→ Q)? R 解： (P→ Q)? R? (? P? Q )? R ? (? P? R)? (Q? R) （析取范式） ? (? P? (Q? ? Q)? R)? ((? P? P)? Q? R) 11 ? (? P? Q? R)? (? P? ? Q? R)? (? P? Q? R)? (P? Q? R) ? (? P? Q? R)? (? P? ? Q? R)? (P? Q? R)（主析取范式） ? ((P→ Q)? R)? (? P? ? Q? ? R)? (? P? Q? ? R)? (P? ? Q? R) ? (P? Q? ? R)? ( P? ? Q? ? R)（ 原公式否定的主析取范式） (P→ Q)? R? (P? Q? R)? (P? ? Q? R)? (? P? Q? ? R) ? (? P? ? Q? R)? (? P? Q? R)（主合取范式） (P? R)? (Q? R)? ? P 解： (P? R)? (Q? R)? ? P（析取范式） ? (P? (Q? ? Q)? R)? ((P? ? P)? Q? R)? (? P? (Q? ? Q)? (R? ? R)) ? (P? Q? R)? (P? ? Q? R)? (P? Q? R)? (? P? Q? R) ? ( ? P? Q? R)? ( ? P? Q? ? R)? (? P? ? Q? R)? (? P? ? Q? ? R) ? (P ? Q ? R) ? (P ? ? Q ? R) ? ( ? P ? Q ? R) ? ( ? P ? Q ? ? R) ? (? P? ? Q? R)? (? P? ? Q? ? R) (主析取范式 ) ? （ (P? R)? (Q? R)? ? P） ? (P? ? Q? ? R)? (P? Q? ? R）（原公式否定的主析取范式） (P? R)? (Q? R)? ? P ? (? P? Q? R)? (? P? ? Q? R)（主合取范式） (? P→ Q)? (R? P) 解： (? P→ Q)? (R? P) ? (P? Q)? (R? P)（合取范式） ? (P? Q? (R? ? R))? (P? (Q? ? Q))? R) ? (P? Q? R)? (P? Q? ? R)? (P? Q? R)? (P? ? Q? R) ? (P? Q? R)? (P? Q? ? R)? (P? ? Q? R)（主合取范式） ? ((? P→ Q)? (R? P)) ? (P? ? Q? ? R)? (? P? Q? R)? (? P? ? Q? R)? (? P? Q? ? R) ? (? P? ? Q? ? R)（原公式否定 的主合取范式） (? P→ Q)? (R? P) ? (? P? Q? R)? (P? ? Q? ? R)? (P? Q? ? R)? (P? ? Q? R)? (P? Q? R) （主析取范式） Q→ (P? ? R) 12 解： Q→ (P? ? R) ? ? Q? P? ? R（主合取范式） ? （ Q→ (P? ? R)） ? (? P? ? Q? ? R)? (? P? ? Q? R)? (? P? Q? ? R)? (? P? Q? R) ? (P? ? Q? R)? (P? Q? ? R)? (P? Q? R）（原公式否定的主合取范式） Q→ (P? ? R) ? (P? Q? R)? (P? Q? ? R)? (P? ? Q? R)? (P? ? Q? ? R)? (? P? Q? ? R) ? (? P? ? Q? R)? (? P? ? Q? ? R）（主析取范式） P→ (P? (Q→ P)) 解： P→ (P? (Q→ P)) ? ? P? (P? (? Q? P)) ? ? P? P ? T (主合取范式 ) ? (? P? ? Q)? (? P? Q)? (P? ? Q)? (P? Q)（主析取范式） ? (P→ Q)? (R? P) 解： ? (P→ Q)? (R? P)? ? (? P? Q)? (R? P) ? (P? ? Q)? (R? P)（析取范式 ） ? (P? ? Q? (R? ? R))? (P? (? Q? Q)? R) ? (P? ? Q? R)? (P? ? Q? ? R)? (P? ? Q? R)? (P? Q? R) ? (P? ? Q? R)? (P? ? Q? ? R)? (P? Q? R)（主析取范式） ? (? (P→ Q)? (R? P))? (P? Q? ? R)? (? P? Q? R)? (? P? ? Q? R) ? (? P? ? Q? ? R)? (? P? Q? ? R)（原公式否定的主析取范式） ? (P→ Q)? (R? P)? (? P? ? Q? R)? (P? ? Q? ? R)? (P? Q? ? R) ? (P? Q? R)? (P? ? Q? R)（主合取范式） P? (P→ Q) 解： P? (P→ Q)? P? (? P? Q)? (P? ? P)? Q ? T(主合取范式 ) ? (? P? ? Q)? (? P? Q)? (P? ? Q)? (P? Q)（主析取范式） (R→ Q)? P 13 解： (R→ Q)? P? (? R? Q )? P ? (? R? P)? (Q? P) （析取范式） ? (? R? (Q? ? Q)? P)? ((? R? R)? Q? P) ? (? R? Q? P)? (? R? ? Q? P)? (? R? Q? P)? (R? Q? P) ? (P? Q? ? R)? (P? ? Q? ? R)? (P? Q? R)（主析取范式） ? ((R → Q) ? P) ? ( ? P ? ? Q ? ? R) ? ( ? P ? Q ? ? R ） ? (P ? ? Q ? R) ? (? P? Q? R)? (? P? ? Q? R)（原公式否定的主析取范式） (R→ Q)? P? (P? Q? R)? (P? ? Q? R)? (? P? Q? ? R) ? (P? ? Q? ? R)? (P? Q? ? R)（主合取范式） P→ Q 解： P→ Q? ? P? Q（主合取范式） ? (? P? (Q? ? Q))? ((? P? P)? Q) ? (? P? Q)? (? P? ? Q)? (? P? Q)? (P? Q) ? (? P? Q)? (? P? ? Q)? (P? Q)（主析取范式） P? ? Q 解： P? ? Q （主合取范式） ? (P? (? Q? Q))? ((? P? P)? ? Q） ? (P? ? Q)? (P? Q)? (? P? ? Q)? (P? ? Q） ? (P? ? Q)? (P? Q)? (? P? ? Q)（ 主析取范式 ） 1 P? Q 解： P? Q（主析取范式） ? (P? (Q? ? Q))? ((P? ? P)? Q) ? (P? ? Q)? (P? Q)? (P? Q)? (? P? Q) ? (P? ? Q)? (P? Q)? (? P? Q)（主合取范式） 1（ P? R） ?Q 解： （ P? R） ?Q ? ? (P? R)? Q ? (? P? ? R)? Q ? (? P? Q)? (? R? Q)（合取范式） ? (? P? Q? (R? ? R))? ((? P? P)? Q? ? R) 14 ? (? P? Q? R)? (? P? Q? ? R)? (? P? Q? ? R)? (P? Q? ? R) ? (? P? Q? R)? (? P? Q? ? R)? (? P? Q? ? R)? (P? Q? ? R) ? (? P? Q? R)? (? P? Q? ? R)? (P? Q? ? R)（主合取范式） ? （ P? R） ?Q ? (? P? ? Q? R)? (? P? ? Q? ? R)? (P? Q? R)? (P? ? Q? R)? (P? ? Q? ? R) （原公 式否定的主析取范式） （ P? R） ?Q ? (P? Q? ? R)? (P? Q? R)? (? P? ? Q? ? R)? (? P? Q? ? R) ? (? P? Q? R)（主析取范式） 1（ P?Q） ?R 解： （ P?Q）