离散数学有大题

总复习题（一）一．单选题1(C)。一连通的平面图，5个顶点3个面，则边数为（）。、4、5、6、72、(A)。如果一个简单图，则称为自补图，非同构的无向4阶自补图有（）个。、1、2、3、43、(D)。为无环有向图，为的关联矩阵，则（）。、是的终点、与不关联、与关联、是的始点4、(B)。一连通的平面图，8个顶点4个面，则边数为。、9、10、11、125、(D)。如果一个简单图，则称为自补图，非同构的3阶有向完全图的子图中自补图有个。、1、2、3、46、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。、13、12、11、107、(D)。有向图的通路包括。、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路8、(D)。一连通的平面图，9个顶点5个面，则边数为。、9、10、11、129、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。、13、12、11、1010、(D)。有向图的通路包括。、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路11、(D)。一连通的平面图，9个顶点5个面，则边数为。、9、10、11、1212、(B)。为有向图，为的邻接矩阵，则。、邻接到的边的条数是５、接到的长度为４的通路数是５、长度为４的通路总数是５、长度为４的回路总数是５13、(C)。在无向完全图中有个结点，则该图的边数为（）。A、B、C、D、14、(C)。任意平面图最多是（）色的。A、3B、4C、5D、615、(A)。对与10个结点的完全图，对其着色时，需要的最少颜色数为（）。A、10B、9C、11D、1216、(C)。对于任意的连通的平面图，且每个面的次数至少为有，其中，分别为的阶数、边数。、、、、二．判断题1、(A)。有向图的关联矩阵要求图是无环图。（）2、(A)。是某图的度数序列。（）3、(A)。无向连通图的点的连通关系是等价关系（）4、(B)。是某图的度数序列。（）5、(A)。V和E分别为无向连通图G1的点割集和边割集.G1-E的连通分支个数为2。()6、(A)。彼得森图不是哈密尔顿图。（）7、(B)。是平面图。（）8、(B)。设是平面图，若，则它们的对偶图。（）9、(A)。是平面图。（）10、(A)。一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。（）11、(B)。平面图中，任何两条边除端点外可以有其他交点。（）12、(B)。余树一定是树。（）13、(A)。为无向连通图，是的生成子图，并且是树，则是的生成树。（）14、(A)。是非平凡的无向树，则至少有两片树叶（）15、(B)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有4片树叶。()16、(A)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有5片树叶。()17、(B)。已知n(n>=2)阶无向简单树具有n-1条边，他一定是树。()18、(A)。一个连通无向图中，存在两个结点和，如果结点和的每一条路都通过结点，则结点比为割点。（）19、(A)。一个有向图，如果中有一个回路，至少包含每个结点一次，则是强连通。20、(A)。给定图，则关于树的定义是每一对结点之间有且仅有一条路。（）21、(A)。完全叉树是每一个结点的出度等于或0的根树。（）22、(A)。在正则叉树中，所有的树叶层次相同。（）23、(B)。树中分支点的通路长度为外部通路长度。（）24、(B)。树中树叶的通路长度为内部通路长度。（）25、(A)。任何一棵二叉树的树叶可对应一个前缀码。（）26、(A)。任何一个前缀码都对应一棵二叉树。（）三．综合题1.证明:若图是自对偶的，则e=2v-2.2.T是一棵树,有两个2度结点，一个3度结点，三个4度结点，T有几片树叶？解：设树T有x片树叶，则T的结点数n=2+1+3+xT的边数m=n-1=5+x又由得2·（5+x）=2·2+3·1+4·3+x

所以x=9，即树T有9片树叶。3.图所示的赋权图G表示七个城市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。解：最小生成树为因此如图TG架线使各城市间能够通讯，且总造价最小，最小造价为：Ｗ(Ｔ)＝１＋３＋４＋８＋９＋23＝484.求出下所示图的邻接矩阵和可达性矩阵，并找出v1解：邻接矩阵v5.求下图的一棵最小生成树.解：因为图中n＝8，所以按算法要执行n－1＝7次，其过程见下图中(1)~(7)。6.v1到v4,v4到v1长为3的通路各有多少条?求出下所示图的邻接矩阵和可达性矩阵v1到v4长为3的通路0条，v4到v1长为3的通路3条。总复习题二1、(B)。设是半群，其中为非空集合，如果是上满足交换律的二元运算，则称为。、半群、可交换半群、可交换群、域2、(D)。设是代数系统，其中为非空集合，如果,+是上的二元运算，则称环、为半群、为阿贝尔群、乘法对加法适合分配律、满足A、B、C三条3、(D)。设是环，如果乘法适合交换律，则称环。、整环、除环、域、交换环4、(B)。设代数系统是个独异点，对任意，且均有逆元，则为（）。A、B、C、D、5、(D)。设代数系统是个独异点，则还需满足（）条件，代数系统为群。A、运算封闭B、运算可结合C、运算可交换D、每个元素有逆元6、(B)。代数系统中，如果存在为等幂元，则（）。A、B、C、D、7、(B)。设是个群，是的平凡子群，则=（）。A、B、C、D、8、(D)。在群中，对于，必存在，使得，则为（）。A、B、C、D、9、(C)。设代数系统是群，则运算满足（）条件，是阿贝尔群。A、运算封闭B、运算可结合C、运算可交换D、每个元素有逆元判断题1、(A)。为独异点，且中任意元素都存在逆元，则为一个群。（）2、(A)。为代数系统，为二元运算，如果是可结合的，且中任意元素都存在逆元，则为一个群。（）3、(B)。为独异点，且中任意元素都存在逆元，则为一个半群。（）三．综合题1.设∘运算为Q上的二元运算，∀x,y∈Q,x°y=x+y+2x∙y(1)指出∘运算的性质.(2)求∘运算的单位元、零元和所有可逆元.解：(1)∘运算可交换，可结合.任取x,yQ,x∘y=x+y+2xy=y+x+2yx=y∘x,任取x,y,zQ,(x∘y)∘z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyzx∘(y∘z)=x+(y+z+2yz)+2x(y+z+2yz=x+y+z+2xy+2xz+2yz+4xyz(2)设∘运算的单位元和零元分别为e和，则对于任意x有x∘e=x成立，即x+e+2xe=xe=0由于∘运算可交换，所以0是幺元.对于任意x有x∘=成立，即x++2x=x+2x=0=1/2给定x，设x的逆元为y,则有x∘y=0成立，即x+y+2xy=0(x≠1/2)因此当x1/2时，是x的逆元.2.S=P({1,2}),为对称差运算，写出<s,>的运算表，并判断此代数系统是一个群。解：{1}{2}{1,2}{1}{2}{1,2}{1}{2}{1,2}{1}{1.2}{2}{2}{1,2}{1}{1,2}{2}{1}3.证明S110=1,2,5,10,11,22,55,110关于解解(1)不难验证S110关于gcd和lcm运算构成格.(略)(2)验证分配律x,y,z∈S110有

gcd(x,lcm(y,z))=lcm(gcd(x,y),gcd(x,z))

(3)验证它是有补格,1作为S110中的全下界,110为全上界,1和110互为补元,2和55互为补元,5和22互为补元,10和11互为补元,从而证明了<S110,gcd,lcm>为布尔代数.总复习题三一．证明下列公式等值（1）┐(p∨q)⇔┐p∧┐q（2）p→(q→r)⇔(p∧q)→r（3）(p∨q)→r⇔(p→r)∧(q→r)（4）（p→q)∧p→q⇔1二．（1）求(pq)r公式的析取范式与合取范式以及成真赋值成假赋值。解(pq)r(pq)r（析取范式）①(pq)(pq)(rr)(pqr)(pqr)m6m7②r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7③②,③代入①并排序，得(pq)rm1m3m5m6m7（主析取范式）(pq)r(pr)(qr)（合取范式）④prp(qq)r(pqr)(pqr)M0M2⑤qr(pp)qr(pqr)(pqr)M0M4⑥⑤,⑥代入④并排序，得(pq)rM0M2M4（主合取范式）成真赋值为001,011,101,110,111，成假赋值为000,010,100.（2）已知命题公式A中含3个命题变项p,q,r，并知道它的成真赋值为001,010,111,求A的主析取范式和主合取范式，及A对应的真值函数.解：A的主析取范式为m1m2m7A的主合取范式为M0M3M4M5M6pqpqrFpqrF00001000001110100101110001101111三．构造下面推理的证明：（1）若明天是星期一或星期三，我明天就有课.若我明天有课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期三.解(1)设命题并符号化设p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课(2)写出证明的形式结构前提：(pq)r,rs,s结论：pq(3)证明①rs前提引入②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置换（2）2是素数或合数.若2是素数，则2是无理数.若2是无理数，则4不是素数.所以，如果4是素数，则2是合数.解用附加前提证明法构造证明(1)设p：2是素数，q：2是合数，r：2是无理数，s：4是素数(2)推理的形式结构前提：pq,pr,rs结论：sq(3)证明①s附加前提引入②pr前提引入③rs前提引入④ps②③假言三段论⑤p①④拒取式⑥pq前提引入⑦q⑤⑥析取三段论（3）前提：(pq)r,rs,s,p结论：q证明用归缪法①q结论否定引入②rs前提引入③s前提引入④r②③拒取式⑤(pq)r前提引入⑥(pq)④⑤析取三段论⑦pq⑥置换⑧p①⑦析取三段论⑨p前提引入pp⑧⑨合取（4）(P（Q∨R))∧(┐S┐Q)∧(P∧┐S)R.证：（1）P∧┐SP（2）PT（1）I1（3）┐ST（1）I1（4）P（Q∨R)P（5）Q∨RT(2)，(4)I11（6）┐S┐QP（7）┐QT(3)，(6)I11（8）RT(5)，(7)I11四．求下列公式的前束范式。解：五．将下列命题符号化。(1)所有的人都长着黑头发；(2)有的人登上过月球；(3)没有人登上过木星；(4)在美国留学的学生未必都是亚洲人。解：令解：令M(x)：x为人。(1)

令F(x)：x长着黑头发。则x(M(x)→F(x))。(2)

令G(x)：x登上过月球。则x(M(x)∧G(x))。(3)

令H(x)：x登上过木星。则┐x(M(x)∧H(x))。(4)

令F(x)：x是在美国留学的学生;G(x)：x是亚洲人。则┐x(F(x)→G(x))。六．给定解释I如下：（a）

个体域D={2,3};（b）

D中特定元素，a=2;（c）

D上特定函数f(x)为：f(2)=3,f(3)=2。（d）

D上特定谓词：G(x,y):G(2,2)=G(2,3)=G(3,2)=1,G(3,3)=0;L(x,y):L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;F(x)：F(2)=0,F(3)=1在I下求下列各式的真值。(1)x(F(x)∧G(x,a));(2)x(F(f(x)∧G(x,f(x)));(3)xyL(x,y);(4)yxL(x,y)A(F(2)∧G(2,2))∧A(F(2)∧G(2,2))∧(F(3)∧G(3,2))(0∧1)∧(1∧1)0(2)B(F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3)))(F(3)∧G(2,3))∨(F(2)∧G(3,2))(1∧1)∨(0∧1)1(3)C(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))(1∨0)∧(0∨1)1(4)D(L(2,2)∧L(2,3))∨(L(3,2)∧L(3,3))(1∧0)∨(0∧1)0七．求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？S={x|xS={x|xZ∧1x1000}A={x|xS∧x可被5整除}B={x|xS∧x可被6整除}C={x|xS∧x可被8整除}|A|=|A|=int(1000/5)=200|B|=int(1000/6)=166|C|=int(1000/8)=125|A∩B|=int(1000/lcm(5,6))=33|A∩C|=int(1000/lcm(5,8))=25|B∩C|=in