2015年同等學(xué)力在職研究生考試已經(jīng)結(jié)束,沒能報考的考生,從現(xiàn)在起可以為2016年的考試做準(zhǔn)備了。為了幫助考生更好的完成備考工作,唯學(xué)網(wǎng)小編為考生準(zhǔn)備了大量的輔導(dǎo)資料及試題,下面是小編準(zhǔn)備的同等學(xué)力計算機(jī)提升練習(xí)題及答案,以供各位考生查看了解。
1. 證明或推翻下列命題:“設(shè)平面上有 100 個點,其中任意兩點間的距離至少是1,則最多有300 對點距離恰好是1”。
解答與評分標(biāo)準(zhǔn):
命題成立(2 分)。
無向圖 G=,V 是平面上的這100 個點,兩個點相鄰當(dāng)且僅當(dāng)這兩點距離恰好是1(2 分)。
每個頂點的度數(shù)不超過 6(3 分)。
根據(jù)握手定律(3 分),
2|E|=頂點度數(shù)之和≤100*6, 所以這個圖的邊數(shù)不超過300(2 分)。
2. 所謂 n 維網(wǎng)格就是一個無向圖G=,其中V={ | 1≤ij≤mj,1≤j≤n},E={(v1,v2)| v1 和v2 恰好只在一個坐標(biāo)上相差1}。討論當(dāng)mj 和n 取哪些正整數(shù)值時,G 是哈密頓圖,并給出證明。
解答與評分標(biāo)準(zhǔn):
分情況討論。注意 G 的頂點數(shù)是m1*m2*m3*…*mn。
(1) 所有mj 都為1:G 是平凡圖,是哈密頓圖(2 分)。
(2) 恰好有一個mj 大于1:G 是長度大于1 的初級路徑,不是哈密頓圖(2 分)。
(3) 至少有兩個mj 大于1:G 是偶圖(無奇數(shù)長度回路)(2 分)。
(3a) m1*m2*m3*…*mn 是偶數(shù):G 是哈密頓圖,用歸納法構(gòu)造哈密頓回路(2 分)。
(3b) m1*m2*m3*…*mn 是奇數(shù):G 不是哈密頓圖,偶哈密頓圖兩部分頂點數(shù)相等,總頂點數(shù)是偶數(shù)(2 分)。
3. 證明或推翻下列命題:“任意給定平面上有限個點,則連接這些點的最短哈密頓回路的長度不超過連接這些點的最小生成樹(不添加額外頂點)的長度的2 倍。子圖的長度就是這個子圖上的邊的長度之和!
解答與評分標(biāo)準(zhǔn):
命題成立(2 分)。
(課本圖論部分最后一章定理)先求最小生成樹奇數(shù)度頂點之間的“最小”匹配,加入匹配“邊”得到歐拉圖(3 分)。
沿著歐拉回路前進(jìn),“抄近路”避開已經(jīng)訪問過的頂點,就得出哈密頓回路(3 分)。
由于距離的三角形不等式,這條哈密頓回路長度不超過最小生成樹長度的2 倍(2 分)。
4. 畫出所有非同構(gòu)的 5 階根樹。
解答與評分標(biāo)準(zhǔn):
9 種(每種1 分,重復(fù)畫扣0.5 分,全畫10 分)。非同構(gòu)的5 階樹共有3種,分別選一個頂點做根。
5.證明或推翻下列命題:“設(shè)連通簡單平面圖G 的最小度δ(G)≥4,則G 的點色數(shù)χ(G)≥3.”
解答與評分標(biāo)準(zhǔn):
假設(shè)χ(G)<3.(反證法分情況討論2 分)
χ(G)=1 當(dāng)且僅當(dāng)G 為n 階零圖,與已知矛盾。(4 分)
χ(G)=2 當(dāng)且僅當(dāng)G 為二部圖,因為G 為平面圖,只能為K2,s 或Kr,2. 此時必有δ(G)=2, 與已知矛盾。(4 分)
6. 證明或推翻下列命題:“設(shè)⊕表示集合的對稱差運算,則對于任意集合A和B 成立:P(A)⊕P(B)=P(A)⊕P(C)⇔B=C”。
解答與評分標(biāo)準(zhǔn):
命題成立(2分)
證明:⊕有消去律,P(A)⊕P(B)=P(A)⊕P(C)⇔P(B)=P(C) (3分)
P(B)=P(C)⇔B=C (3分)
其他細(xì)節(jié)(2分)
7. 證明或推翻下列命題:“設(shè) R 是從A 到B 的二元關(guān)系,則下列兩個條件互為充要條件。條件一:存在C⊆A 且D⊆B”使得R=C×D。條件二:對于A中任意x1,x2 和B 中y1,y2,有(x1Ry1∧x2Ry2)→x1Ry2.”
解答與評分標(biāo)準(zhǔn):
命題成立(2 分)。
條件一 ⇒ 條件二:x1∈C,y2∈D(3 分)。
條件二⇒ 條件一:C=dom(R),D=ran(R)(3 分)。
其他細(xì)節(jié)(2 分)
8. 設(shè) A={1,2,…,10},定義A 上的二元關(guān)系R={|x,y∈A∧x+y=10},說明R具有哪些性質(zhì)并說明理由。
解答與評分標(biāo)準(zhǔn):
討論 5 種性質(zhì)(各2 分)。
非自反:<1,1>不屬于A。
非反自反:<5,5>∈A。
對稱:定義。
非反對稱:<3,7>,<7,3>∈A 但7 不等于3。
非傳遞:<3,7>,<7,3>∈A 但<3,3>不屬于A。
以上是同等學(xué)力計算機(jī)提升練習(xí)題及答案,以供大家備考使用?忌绻氆@得更多在職研究生相關(guān)資訊,如在職研究生報名時間、考試時間以及報考條件、相關(guān)知識,敬請關(guān)注唯學(xué)網(wǎng),小編會在第一時間作出相關(guān)報道!
|
|
||
|
|