1一个连通的无向图G

欧拉回路⼀个定理的证明
定理:当G是⽆奇度结点的连通⽆向图时，G必有欧拉回路。

⽹上基本上没有证明，让⼈很不爽。

⾸先，如果⼀个联通⽆向图，点度均为偶数，必有⼀个简单环。

因为如果没有简单环，那么图是树，E=V-1
每个点不能是孤⽴点，度>=2
E>=V*2/2
E>=V
与E=V-1⽭盾，所以必有简单环。

那么为了找出欧拉路径，可以先随意找⼀个简单环。

在原图中删去它上的边，并更新点的度数。

现在，原图变成了若⼲满⾜性质点度均为偶数的联通块。

（显然，减⼀个环上的边，不会改变点度的奇偶性）
⼜因为联通块是联通的，所以可以递归做。

现在只需要证明，联通块的欧拉回路和原图的简单环可以并在⼀起。

⼀个环和另⼀个环可以并在⼀起，当且仅当它们的点集有交集（显然）
那么，现在只需要证明每个联通块的欧拉回路（本质是⼀种环）与原图的简单环，有交点。

（结论　１）
反证法，
如果没有交点，那么该联通块内的点的所有相邻的边还存在。

（因为没有删去）
所以该联通块内存在⼀点，连了某些联通块外的点（要不然，这个联通块就与世隔绝了）。

由假设有，某些外点与环上的点⽆交集。

所以某些外点必定属于另⼀分割出的联通块。

所以这就不是⼀个极⼤的联通块，与假设⽭盾。

所以就证明了结论　１，
所以证明该定理。

1、设简单图G所有结点的度数之和为12，则G一定有_____条边。

问题反馈【教师释疑】正确答案：【6 】62、设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X 上的等价关系，R应取_______. 问题反馈【教师释疑】正确答案：【{〈a,c〉,〈c,b〉} 】{〈a,c〉,〈c,b〉}3、命题公式的任意两个不同极小项的合取式一定为_________. 问题反馈【教师释疑】正确答案：【永假式】永假式4、一个公式在等价意义下，_______范式写法是唯一的。

问题反馈【教师释疑】正确答案：【主析取】主析取5、若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为_______ 问题反馈【教师释疑】正确答案：【P∧┐Q 】P∧┐Q6、设R是A上的二元关系,且RRR为R的子集,可以肯定R应是_____关系。

问题反馈【教师释疑】正确答案：【传递】传递7、设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。

则R×S ＝__________________, 问题反馈【教师释疑】正确答案：【{(1,3),(2,2)} 】{(1,3),(2,2)}8、设谓词的定义域为{a, b},将表达式"任意xR(x)→彐xS(x)"中量词消除，写成与之对应的命题公式是__________________. 问题反馈【教师释疑】正确答案：【(R(a)∧R(b))→(S(a)∨S(b)) 】(R(a)∧R(b))→(S(a)∨S(b))9、设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; 问题反馈【教师释疑】正确答案：【{3} 】{3}10、设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________ 问题反馈【教师释疑】正确答案：【12 】1211、设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A∩B＝_________________________; 问题反馈【教师释疑】正确答案：【{4} 】{4}12、设A={a, b, {a, b}}，B={a, b}，则B－A =________ 问题反馈【教师释疑】正确答案：【Φ】Φ13、设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

《图论》期末考试模拟题（答案） ⼀、选择题 1、给定⽆向图如图所⽰，下⾯给出的顶点集⼦集中，是点割集的为（A,B,C,D）。

A. {b, d} B. {d} C. {a, c} D. {g, e} bf 内容需要下载⽂档才能查看 2、设V＝{a,b,c,d},与V能构成强连通图的边集E＝（ A ）。

A. {,,,,} B. {,,,,} C. {,,,,} {,,,,} 3、⼀个连通的⽆向图G，如果它的所有结点的度数都是偶数，那么它具有⼀条（ B ）。

A. 哈密尔顿回路 B. 欧拉回路 C. 哈密尔顿通路 D. 欧拉通路 4、如图所⽰各图，其中存在哈密顿回路的图是（ A, C ）。

内容需要下载⽂档才能查看 第 1 页共 5 页 图论期末考试题⽬参考 《图论》 5. 下图中既是欧拉图，⼜是哈密尔顿图的有（D）。

5、设G是有5个顶点的完全图，则G（ B ）。

D. ⽆哈密尔顿路 E. 可以⼀笔画出 F. 不能⼀笔画出 G. 是平⾯图 6、设G是连通简单平⾯图，G中有11个顶点5个⾯，则G中的边是（ D ）。

A. 10 B. 12 C. 16 D. 14 ⼆、填空题 1、完全图K8具有（ 28 ）条边。

2、图G如图所⽰， ab fc 那么图G的割点是（ a, f ）。

e d 3、⽆向图G为欧拉图，当且仅当G是连通的，且G中⽆（奇数度）结点。

第 2 页共 5 页 图论期末考试题⽬参考 《图论》 4、连通有向图D含有欧拉回路的充分必要条件是（ D中每个结点的⼊度＝出度）。

5、 n个结点、m条边的⽆向连通图是树当且仅当m=__（3）___。

(1) n+1 (2) n (3) n-1 (4)2n-1 三、 1、设图G=(P,E) 中有12条边，6个度数为3的顶点，其余顶点的度数均⼩于3，求G⾄少有多少个顶点。

解答：设G有n个顶点，由定理1， ∑d i=1nG(vi)=2m=24 (|E|=m) 由题设 24<3×6+3(n?6) ∴ 3n>24 即 n>8 因此，G中⾄少有9个顶点。

图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。

E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。

注意：元素可以重复出现的集合称作多重集合。

某元素重复出现的次数称作该元素的重复度。

例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。

从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。

1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。

E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。

通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。

与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。

通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。

⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。

（2）顶点数称作图的阶，n个顶点的图称作n阶图。

（3）⼀条边也没有的图称作零图，n阶零图记作N n。

1阶零图N1称作平凡图。

平凡图只有⼀个顶点，没有边。

（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。

（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。

（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。

（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。

《数据结构与算法》考研真题精选一、选择题1．图中有关路径的定义是（）。

A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。

A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。

A．n-l B．n C．n+l D．2n5．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１）C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。

A．0 B．1 C．n-1 D．n7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

A．1/2 B．2 C．1 D．48．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。

A．5 B．6 C．8 D．99．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A．逆拓扑有序B．拓扑有序C．无序的10．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。

A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表11．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连，则只要检查（）的第i行第j列的元素是否为零即可。

A．mA B．A C．A m D．Am-115. 下列说法不正确的是（）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( )A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )A.10B.12C.16D.143.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( )A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( )A.〈Z，+，/〉B.〈Z，/〉C.〈Z，-，/〉D.〈P(A)，∩〉6.下列各代数系统中不含有零元素的是( )A.〈Q，*〉Q是全体有理数集，*是数的乘法运算B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C.〈Z， 〉，Z是整数集， 定义为x xy=xy,∀x,y∈ZD.〈Z，+〉，Z是整数集，+是数的加法运算7.设A={1,2,3}，A上二元关系R的关系图如下：R具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )A.R∪I AB.RC.R∪{〈c,a〉}D.R∩I A9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}10.下列式子正确的是( )A. ∅∈∅B.∅⊆∅C.{∅}⊆∅D.{∅}∈∅11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R下为真的是( )A.( ∀x)( ∀y)( ∀z)(A(x,y))→A(f(x,z),f(y,z))B.( ∀x)A(f(a,x),a)C.(∀x)(∀y)（A(f(x,y),x))D.(∀x)(∀y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(∀x)(A(x)→B)等价于( )A.(∃x)A(x)→BB.(∀x)A(x)→BC.A(x)→BD.(∀x)A(x)→(∀x)B13.谓词公式(∀x)(P(x,y))→(∃z)Q(x,z)∧(∀y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q15.以下命题公式中，为永假式的是( )A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。

离散数学选择题单项选择题第⼀章命题逻辑1．下列语句，哪⼀个是真命题：（ B ）A ．我正在说谎B ．如果1+1=0，那么雪是⿊的C ．9+5＞18D ．存在最⼤的质数2．下⾯哪⼀个命题是假命题（ A ）A ．如果2是偶数，那么⼀个公式的析取范式唯⼀B ．如果2是偶数，那么⼀个公式的析取范式不唯⼀C ．如果2是奇数，那么⼀个公式的析取范式唯⼀D ．如果2是奇数，那么⼀个公式的析取范式不唯⼀3．下⾯哪个联结词运算不可交换（ B ）A ．∧；B ．→C ．∨D ．?4．设P ：天下⼤⾬，Q ：他乘公共汽车上班。

命题“只有天下⼤⾬，他才乘公共汽车上班”符号化为（ B ）A ．P →QB ．Q →PC ．P ?QD ． ?P →Q5．设P ：天下钉⼦，Q ：我去B 城。

命题“除⾮天下钉⼦，否则我去B 城”符号化为：（ C ）A ．P → QB ．Q → PC ．?P → QD ．Q →┐P6．设P ：我们划船，Q ：我们跳舞，命题“我们不能既划船⼜跳舞”符号化为（ B ）A ．P V Q 2）┐（P ∧Q ） C ．┐P ∧┐Q D ．┐P ∧Q7．令P ：今天下雪了，Q ：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A ．P →┐QB ．P∨┐QC ．P∧Q8．设P ：我将去镇上，Q ：我有时间，命题“我将去镇上，仅当我有时间”，符号化为（ A ）。

A ．P → QB 、Q → PC 、P ?QD 、┐P∨┐Q9．下⾯哪⼀个命题公式是重⾔式（ D ）A ．（P ∨R ）∧（P → Q ）B ．P →（Q ∨R ）C ．（P ∨Q ）?（Q ∨R ）D ．（P →（Q → R ））→（P → Q ）→（P →R ）10．下⾯哪⼀组命题公式不是等价的（ C ）A ．（P →Q ）∧（Q →P ），P ?QB ． ?（P ?Q ），（P ∧┐Q ）∨（┐P ∧Q ）C ．P →（Q ∨R ），┐P ∧（Q ∨R ）D ． P →（Q ∨R ），（P ∧┐Q ）→ R11．下⾯哪个命题公式是重⾔式（ B ）A ．（P → Q ）∧（Q →P ）B ．（P ∧Q ）→PC ．（┐P ∨Q ）∧┐（┐P ∧Q ）D ．（P →Q ）→P12．下列公式哪⼀个是两个命题变元P ，Q 的⼩项（ C ）A ．P∧┐P∧QB ．┐P∨QC ．┐P∧QD ．┐P∨P∨Q13．⼀个公式在等价意义下，下⾯哪个写法是唯⼀的。

离散数学题集1.下列语句不是命题的是( C )。

合代数A.黄金是非金属。

11.设S是自然数集，则下列运算中不满足交换律的是( B )。

B.要是他不上场，我们就不会输。

A.a*b=|a-b| B.a*b=ab C.他跑100米只用了10秒钟，你说他是不是运动健将呢? C.a*b=max{a,b} D.他跑100米只用了10秒钟，他是一个真正的运动健将。

D.a*b=min{a,b} 2.关于命题变元P和Q的大项M01表示( D )。

12.设图G′=<V′，E′>是图的生成子图，则必须( a )。

A.?P?QB.?P?Q A.V′=V B.V′?C.P??QD.P??Q V但E′=EC.E′=ED.E′?，,,3.公式(x)(y)(P(x,z)?Q(y))S(x,y)中的(x)的辖域是( B )。

E且V′?V，13.设有向图G有5个结点，4条边，且有一条有向路经过每A.(y)(P(x,z)?Q(y))B.P(x,z)?Q(y)C.P(x,z)D.S(x,z) 个结点一次，则图G满足的最大连通性是( )。

4.下列等价式不成立的是( D )。

A.不连通 B.弱连,通，,A.?(x)A(x)(x)?A(x),C.单侧连通 D.强连通，,B.?(x)A(x)(x)?A(x),14.一个连通图G具有以下何种条件时，能一笔画出:即从某,,,C.(x)(A(x)?B(x))(x)A(x)?(x)B(x),结点出发，经过图中每边仅一次回到该结点。

( A )。

,,,D.(x)(A(x)?B(x))(x)A(x)?(x)B(x)A.G没有奇数度结点B.G有1个奇数，,5.公式(x)(y)(P(x,y)?Q(z))?R(x)中的x( )。

A.只是约束变元度结点B.只是自由变元C.G有2个奇数度结点D.G没有或有2C.既是约束变元又是自由变元个奇数度结点D.既非约束变元又非自由变元二、填空题(每小题2分，共30分) 6.设A={a,{a}}，则下列各式正确的是( )。

数据结构复习题精选复习题精选⼀选择题1.数据结构被定义为(D,S),其中D表⽰( )的有限集合。

A .数据结构 B.数据元素 C.数据项 D.存储影像2.线性表的链式存储结构是⼀种( )存储结构.A.随机存取B.顺序存取C.索引存取D.散列存取3.从逻辑上可以把数据结构分为（）两⼤类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、⾮线性结构D．初等结构、构造型结构4.下列数据中，（）是⾮线性数据结构。

A．栈 B. 队列 C. 完全⼆叉树 D. 堆5.若线性表采⽤链式存储结构，每个元素占⽤4个存储单元，第⼀个元素的存储地址为100,则第12个元素的存储地址是( )A.112B.144C.148D.⽆法确定6.设⼀个链表最常⽤的操作是在末尾插⼊结点和删除尾结点，则选⽤( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表7.若某线性表最常⽤的操作是存取任⼀指定序号的元素和在最后进⾏插⼊和删除运算，则利⽤（）存储⽅式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表8.下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元。

B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作。

C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元。

D．线性表采⽤链接存储，便于插⼊和删除操作。

9.在单链表指针为p的结点之后插⼊指针为s的结点，正确的操作是：（）。

A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s;10.在单链表中，已知q是p的前驱，若在q和p之间插⼊s，正确的操作是：（）。

离散数学复习题一. 有两个小题1．分别说明联结词⌝、∧、∨、→和↔的名称，再分别说明它们在自然语言中表示什么含义。

解：(1) ⌝叫做否定。

(2) ∧叫做合取。

(3) ∨叫做析取。

(4) →叫做蕴涵。

(5) ↔叫做等价。

“⌝”表示“…不成立”，“不…”。

“∧”表示“并且”、“不但…而且...”、“既…又...”等。

“∨”表示“或者”，是可兼取的或。

“→”表示如果… ，则…；只要… ，就…；只有… , 才…；仅当… 。

“↔”表示“当且仅当”、“充分且必要”。

2解：二. 将下面命题写成符号表达式。

(3,4题要使用句后给定的谓词。

)1.如果小张去，则小王与小李都不去，否则小王与小李不都去。

解：设P：小张去。

Q：小王去。

R：小李去。

此命题的表达式为：(P→(⌝Q∧⌝R))∧(⌝P→⌝(Q∧R))2.我们不能既划船又跑步。

解：令 P:我们划船。

Q:我们跑步。

此命题的表达式为⌝(P∧Q)3.有些运动员是大学生。

(L(x): x是运动员，S(x): x是大学生。

)解：∃x(L(x)∧S(x))4.每个运动员都钦佩一些教练。

( L(x):x是运动员，A(x,y):x钦佩y，J(x):x是教练。

)解：∀x(L(x)→∃y(J(y)∧A(x,y)))三. 有三个问题1.先说明什么叫永真式(也叫重言式)。

解：A(P1,P2,…,Pn) 是含有命题变元P1,P2,…, Pn的命题公式，如不论对P1,P2,…, Pn作任何指派，都使得A(P1,P2,…,Pn) 为真，则称之为重言式，也称之为永真式。

2.指出下面的命题公式中哪些是永真式(只写题号即可)。

(1). (P∨Q)→P (2). P→(P∨Q)(3). (P∧(P→Q))→Q (4). (P∧Q)→Q解:(2),(3),(4)为永真式。

3.然后对上面的永真式任选其中一个给予证明(方法不限)。

证明 (4). (P∧Q)→Q设前件(P∧Q)为真，则得Q为真。

所以(P∧Q)→Q是永真式。

离散数学作业一、选择题1、下列语句中哪个是真命题（C ）。

A ．我正在说谎。

B ．如果1+2=3，那么雪是黑色的。

C ．如果1+2=5，那么雪是白色的。

D ．严禁吸烟！2、设命题公式))((r q p p G →∧→=，则G 是（ C ）。

A. 恒假的B. 恒真的C. 可满足的D. 析取式 3、谓词公式),,(),,(z y x yG x z y x F ∃∀→中的变元x （ C ）。

A ．是自由变元但不是约束变元 B ．既不是自由变元又不是约束变元 C ．既是自由变元又是约束变元 D ．是约束变元但不是自由变元4、设A={1，2，3}，则下列关系R 不是等价关系的是（C ）A ．R={<1，1>，<2，2>，<3，3>}B ．R={<1，1>，<2，2>，<3，3>，<2，3>，<3，2>}C ．R={<1，1>，<2，2>，<3，3>，<1，4>}D ．R={<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，3>，<2，1>，<3，1>，<3，2>} 5、设R 为实数集，映射σ=R →R ，σ（x ）= -x 2+2x-1，则σ是（ D ）。

A ．单射而非满射 B ．满射而非单射 C ．双射 D ．既不是单射，也不是满射 6、下列二元运算在所给的集合上不封闭的是（ D ） A. S={2x-1|x ∈Z +}，S 关于普通的乘法运算 B. S={0，1}，S 关于普通的乘法运算 C. 整数集合Z 和普通的减法运算D. S={x | x=2n ，n ∈Z +}，S 关于普通的加法运算7、*运算如下表所示，哪个能使（{a,b}，*）成为含幺元半群（ D ）b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a *A B C D8、下列图中是欧拉图的是（ A ）。

旅行售货员问题传统的旅行售货员问题可以概述如下：设有n个城市，以V1 ，V2 ，…V n表示之，用d ij表示城市V i到城市V j之间的距离，一个推销员从某城市(不妨假设从城市V1)出发到其他城市去一次而且仅一次，然后回到原来的城市(城市V1)，问其应该选择什么样的行走路线才能使得总的旅行路程最短。

把这个问题抽象成图论问题就是给定一个连通无向图G(V,E)，其中V＝{V1 ,V2,…V n}是顶点(城市)的集合，E是顶点间边的集合，表示相应城市间的旅行路线，即E={e=(V i,V j)；顶点V i与V j间有边e},每个边e∈E上有非负权重w(e)=w(V i,V j)=d ij，表示顶点V i即城市V i到顶点V i(即城市V j)的距离，问题就是要确定图G的一个圈，它过每个顶点一次且仅一次，而且使得该圈的总权(即圈上所有边的权之和)最小。

这个圈在图论里称为Hamilton圈，简称H圈。

由于G(V,E)的边是无向的，相邻的边和顶点可以通过边进入顶点，也可以通过顶点进入边。

这样，寻找售货员最优旅行路线的问题就可以归结为如下的图论问题：给定连通图G(V,E)，对每条边e= (V i,V j)∈E对应的顶点V i与V j间添加反向边e'=(V j,V i)，得到双倍于G的另外一个连通图G'=(V,E')，求E1⊆E'使得G1(V,E1)为H圈且总权为∑w(e)最∈E1e小。

为叙述方便，若e= (V i ,V j )，则记为e i ,j ∈E,而相应的添加边为e j ,i 。

与边e i ,j ∈E '相对应，设定一个0-1整数变量x i ,j 。

若e i ,j ∈E '，即称边是从V i 到V j 的，或称为弧。

这样，我们就可以把无向图理解为有向图D (V,E)。

每一个E 1⊆E '唯一对应一组x i ,j 的值，反之亦然。

我们称x i ,j 为E 1的值系。

离散数学总分：100 考试时间：100分钟一、单项选择题1、一个无向图G是一个二元组〈V，E〉,V代表(正确答案：B,答题答案：)A、边集B、顶点集C、环D、路径2、最佳前缀码可由（）算法求出(正确答案：A,答题答案：)A、HuffmanB、PERTC、DijkstraD、Kruskal3、带权为2、3、5、7、8、9的最优树T，权W(T)＝（）(正确答案：B,答题答案：)A、82B、83C、84D、854、设n阶无向连通图G有m条边，则（)(正确答案：A,答题答案：)A、m≥n－1B、m≤n－1C、m=n－1D、m≥n5、经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路)，称为（）(正确答案：A,答题答案：)A、欧拉通路B、简单通路C、初级通路D、哈密尔顿通路6、入度为0的顶点称为（）(正确答案：B,答题答案：)A、树根B、树叶C、边D、顶点7、按中序行遍法，其行遍结果为((dce)bf)a(gih)，则按后序行遍法其结果为（）(正确答案：A,答题答案：)A、a(b(cde) )(igh)fB、a(b(cde) f)(igh)C、((dec)fb)(ghi) aD、(b(cde) f)(igh)a8、设T＝〈V，E〉是n阶非平凡树，则T中至少有（）片树叶.(正确答案：C,答题答案：)A、1B、2C、3D、49、设有向简单图D的度数列为2,2,3,3，入度列为0,0,2,3，D的出度列为（）.(正确答案：B,答题答案：)A、2,2,1,0B、2,2,3,3C、0,0,2,3D、2,2,5,610、设G＝〈V，E〉是n阶无向简单图，若G中任何顶点都与其余的n－1个顶点相邻，则称G为n阶（）(正确答案：A,答题答案：)A、无向图B、无向完全图C、完全图D、有向简单图二、多项选择题1、简单图为（）(正确答案：AB,答题答案：)A、不含平行边B、不含环C、不含顶点D、不含单边2、下面给出的符号串集合中，哪些是前缀码？(正确答案：ABD,答题答案：)A、B1＝{0,10,110,1111}B、B2＝{1,01,001,000}C、B3＝{1,11,101,001,0011}D、B4＝{b，c，aa，ac，aba，abb，abc }3、树的行遍法有（）(正确答案：ABC,答题答案：)A、中序B、前序C、后序D、顺序4、无向图G为欧拉图，则（）(正确答案：ABC,答题答案：)A、G是连通的B、G中无奇度顶点C、所有顶点的入度等于出度D、奇数个顶点5、无向图G具有欧拉通路，当且仅当G是（）(正确答案：AB,答题答案：)A、连通图B、有零个或两个奇度顶点C、回路D、奇数个顶点6、根据边是否有方向，图可分为（）(正确答案：CD,答题答案：)A、连通图B、树C、有向图D、无向图7、两图同构，则（）(正确答案：ABC,答题答案：)A、顶点个数相同B、边的条数相同C、每个顶点的度相同D、有多重边8、特殊的图有（）(正确答案：ABCD,答题答案：)A、二部图B、欧拉图C、哈密尔顿图D、平面图9、下列各组数中，哪些能够成无向图的度数列？(正确答案：ABC,答题答案：)A、1,1,1,2,3B、2,2,2,2,2C、3,3,3,3D、1,2,3,4,510、若图G中任意两个结点u和v，都有从u到v和从v到u的通路，则称G是（）(正确答案：A,答题答案：)A、强连通图B、弱连通图C、单向连通图D、连通图三、判断题1、强连通图一定是单向连通图。