2、（A.G连通且边数比结点数少1C.G的边数比结点数少1A）.B.G连通且结点数比边数少1D.G中没有回路.「0110■010011100000100101010■D.3则G的边数为（B）.A.6B.5C.46.设A={a,b}fB={1,2},R29弘是A到B的二元关系，且&={S2>,},R2={,,<*,1>},R3={,},则（B）不是从A到B的函数.A.川和&B.R2C./?3D.&和心7.若集合A的元素个数为10,则其幕集的元素个数为（
3、A）.A.1024B.10C.100D.18.设完全图K”有舁个结点（«^2）,m条边，当（C）时，K”中存在欧拉回路.A.加为奇数B.77为偶数C.〃为奇数D.加为偶数、111109.已知图G的邻接矩阵为01011000000110101111则G有（D）.10、〃阶无向完全图K“中的边数为(A)(A)咛(3)呼11•在图G=中，结点总度数与边数的关系是(C)Adeg(vz)=2
4、e
5、(B)deg(v,)=
6、EIC^deg(v)=2
7、E
8、D^deg(v)=
9、E
10、12.设有向图(a)、
11、(方)、(c)与(〃)如图一所示，则下列结论成立的是(D).(a)(b)(c)(d)图一A.(«)是强连通的C.(c)是强连通的A.(b)是强连通的D・(M)是强连通的13.下列公式(C)为重言式.A.rP心Q—ZQB.(Qt("))人(NQ))C・(Pt(「QtP))㈠(「Pt(PtQ))D.(^Pv(Pa0)㈠Q14.设A={1,2,3,4,5,6,7,8},R是A上的整除关系，B={2,4,6},则集合B的最大元、最小元、上界、下界依次为(B).A.8、2、8、2B.无、2、无、2D.8、
12、1、6、1B.6、2>6、215•无向完全图&的不同构的生成子图的个数为(C)(A)6(B)5(C)4(D)3二、填空题(每小题3分，本题共15分)1.设集合A={a,/;},那么集合4的幕集是一{0血，几⑷M”2.设集合A={0,1,2},B={1,2,3,4,},R是A到B的二元关系,R={xeAUyg3且x,yeAnB}则R的有序对集合为KI,1>，vl,2>,<2,1>,<2,2>}3.设集合A={1,2}上的关系R={<2,2>,vl,2>},则在R中仅需加入一个元素_<1,
13、1>就可使新得到的关系为自反的.4.若A={1,2},R={xeA,yeA,x+y<4},则7?的自反闭包为—0」＞42＞42＞今＜2」＞1.设A={q,/?},B={1,2},C={4,5},从A到B的函数戶{,G,2>},从B到C的函数g={vl,5>,<2,4>},则父于等于匕a,5>,<肌4>.2.无向连通图在结点数卩与边数a满足关系吋是树.3.设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去4条边后使之变成树.4.已知一棵无向树卩中有8个结点，4
14、度，3度，2度的分支点各一个，卩的树叶数为5.5.无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且连通6.无向图G是欧拉图的充分必要条件是_G是连通的且结点度数都是偶数7.设G是连通平面图，叫匕厂分别表示G的结点数，边数和面数，则u,e和广满足白勺关系式v-e+r=2.8.设连通平面图G的结点数为5,边数为6,则面数为・9.(Vx)(P(x)->Q(x)V^(xfy))屮的自由变元为.10.设个体域D={a,b}t则谓词公式(X/Q4(x)AOx)B(Q消去量词后的等值式为—(a)JB
15、(b)).11.命题公式Pt(Qx/P)的真值是.三、逻辑公式翻译(每小题6分，本题共12分)1.将语句“雪是黑色的翻译成命题公式.设P：雪是黑色的，则命题公式为：P.2.将语句“他不去学校・”翻译成命题公式.解：设P：他去学校，则命题公式为：「只3.将语句“小王是个学生，小李是个职员，而小张是个军人・”翻译成命题公式.设P：小王是个学生，Q：小李是个职员，R：小张是个军人.则命题公式为：P!Q/R.4.将语句“如果所有人今天都去参加活动，则明天的会议取消・”翻译成命题公式.解：设P：所有人
