2015年同等學(xué)力在職研究生考試已經(jīng)結(jié)束,沒(méi)能報(bào)考的考生,從現(xiàn)在起可以為2016年的考試做準(zhǔn)備了。為了幫助考生更好的完成備考工作,唯學(xué)網(wǎng)小編為考生準(zhǔn)備了大量的輔導(dǎo)資料及試題,下面是小編準(zhǔn)備的同等學(xué)力計(jì)算機(jī)練習(xí)題及答案,以供各位考生查看了解。
一、判斷以下命題的真假.如果為真在后面括弧內(nèi)打✔,否則打×.
1.A={x|x∈N 且(x,5)=1},則構(gòu)成代數(shù)系統(tǒng),+為普通加法 ( )
2.∀x, y∈R,xoy=|x−y|,則0 為的單位元 ( )
3.∀x, y∈R,xoy=x+y+xy,則∀x∈R,x−1=−x/(1+x) ( )
4.整環(huán)的積代數(shù)不一定是整環(huán) ( )
5.格同態(tài)具有保序性 ( )
6.在有補(bǔ)格中,∀a∈L,求a 的補(bǔ)是L 的一元運(yùn)算 ( )
解答:1. × 2. × 3. ×. 4. ✔ 5. ✔ 6. ×
二、證明題
1. 證明或推翻下列命題:“設(shè)平面上有 100 個(gè)點(diǎn),其中任意兩點(diǎn)間的距離至少是1,則最多有300 對(duì)點(diǎn)距離恰好是1”。
解答與評(píng)分標(biāo)準(zhǔn):
命題成立(2 分)。
無(wú)向圖 G=,V 是平面上的這100 個(gè)點(diǎn),兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)這兩點(diǎn)距離恰好是1(2 分)。
每個(gè)頂點(diǎn)的度數(shù)不超過(guò) 6(3 分)。
根據(jù)握手定律(3 分),
2|E|=頂點(diǎn)度數(shù)之和≤100*6, 所以這個(gè)圖的邊數(shù)不超過(guò)300(2 分)。
2. 所謂 n 維網(wǎng)格就是一個(gè)無(wú)向圖G=,其中V={ | 1≤ij≤mj,1≤j≤n},E={(v1,v2)| v1 和v2 恰好只在一個(gè)坐標(biāo)上相差1}。討論當(dāng)mj 和n 取哪些正整數(shù)值時(shí),G 是哈密 頓圖,并給出證明。
解答與評(píng)分標(biāo)準(zhǔn):
分情況討論。注意 G 的頂點(diǎn)數(shù)是m1*m2*m3*…*mn。
(1) 所有mj 都為1:G 是平凡圖,是哈密頓圖(2 分)。
(2) 恰好有一個(gè)mj 大于1:G 是長(zhǎng)度大于1 的初級(jí)路徑,不是哈密頓圖(2 分)。
(3) 至少有兩個(gè)mj 大于1:G 是偶圖(無(wú)奇數(shù)長(zhǎng)度回路)(2 分)。
(3a) m1*m2*m3*…*mn 是偶數(shù):G 是哈密頓圖,用歸納法構(gòu)造哈密頓回路(2 分)。
(3b) m1*m2*m3*…*mn 是奇數(shù):G 不是哈密頓圖,偶哈密頓圖兩部分頂點(diǎn)數(shù)相等,總頂點(diǎn)數(shù)是偶數(shù)(2 分)。
3. 證明或推翻下列命題:“任意給定平面上有限個(gè)點(diǎn),則連接這些點(diǎn)的最短
哈密頓回路的長(zhǎng)度不超過(guò)連接這些點(diǎn)的最小生成樹(shù)(不添加額外頂點(diǎn))的
長(zhǎng)度的2 倍。子圖的長(zhǎng)度就是這個(gè)子圖上的邊的長(zhǎng)度之和。”
解答與評(píng)分標(biāo)準(zhǔn):
命題成立(2 分)。
(課本圖論部分最后一章定理)先求最小生成樹(shù)奇數(shù)度頂點(diǎn)之間的“最小”匹配,加入匹配“邊”得到歐拉圖(3 分)。
沿著歐拉回路前進(jìn),“抄近路”避開(kāi)已經(jīng)訪問(wèn)過(guò)的頂點(diǎn),就得出哈密頓回路(3 分)。
由于距離的三角形不等式,這條哈密頓回路長(zhǎng)度不超過(guò)最小生成樹(shù)長(zhǎng)度的2 倍(2 分)。
以上是同等學(xué)力計(jì)算機(jī)練習(xí)題及答案。考生如果想獲得更多在職研究生相關(guān)資訊,如在職研究生報(bào)名時(shí)間、考試時(shí)間以及報(bào)考條件、相關(guān)知識(shí),敬請(qǐng)關(guān)注唯學(xué)網(wǎng),小編會(huì)在第一時(shí)間作出相關(guān)報(bào)道!
|
|
||
|
|