《《离散数学》期终试题-软件学院-2004-6.doc》由会员分享，可在线阅读，更多相关《《离散数学》期终试题-软件学院-2004-6.doc（3页珍藏版）》请在三一文库上搜索。
1、选择题20分10题多选题1, Let B=, A =(B), find the correct ones in following statements:(1) A (2) , A (3) ,A (4) ,A2, Let R be a relation on A=1,2,3,10, R=(x,y)|x+y = 10, x,yA, then R is:(1) reflexive (2) symmetric (3) transitive (4) antisymmetric3, Let |A| = n, how many binary operations can we define on A:2n
2、n2(1) 2n (2) n2 (3) n (4) n4, operation defined as following, which ones can not make (a,b,*) a monoid?(1) (2) (3) (4) 5, which ones are lattices in the following posets?(1)(2)(3)(4)6，Let directed graph D = , then:(1), EVV(2), EVV(3) E=VV(4) VVE7, In a connected undirected graph with n vertices, the
3、 number of edges is (1) at least n-1(2) at least n(3) at most n(n-1)/2(4) at most n2/28, which one is tautology?(1) (P(PQ)Q(2)P(PQ) (3) P(PQ) （4）(PQ)Q9,In the following sentences, which one is true?(1),(2),(3), (4),10,How many numbers must be chosen from 1 to 25 to ensure that one of them is a multi
4、ple of another?(1)12(2)13(3)14(4)15计算题25分1,Let p be the proposition “I will do every exercise in this book” and q be the proposition “I will get an A in this course.” Express each of the following as a combination of p and q:a), I will get an A in this course only if I will do every exercise in this
5、 book.b), I will get an A in this course and I will do every exercise in this book.c), Either I will not get an A in this course or I will not do every exercise in this book.d), For me to get an A in this course it is necessary and sufficient that I do every exercise in this book.2, What is the coef
6、ficient of x12y13 in the expansion of (2x-3y)25?3,compute the connectivity relation for R defined by the following matrix (detail steps needed):4, From point A, use Prims algorithm to find a minimum spanning tree in the following graph（detail steps needed）:EA3D2F46J7G53I6H5B3C22K14L6725,find a maxim
7、um flow in the following network by using the labeling algorithm.(Detail steps needed).21332244236431证明题：40分5题证明题(1), Let k be a positive integer. show that 1k+2K+nk is O(nk+1). Is it O(nk)? Why?(2), Let n=p1p2pk, where the pi are distinct primes. Show that Dn is a Boolean algebra.(3), Show that iso
8、morphism relation is an equivalent relation. Is homomorphism an equivalent relation too? Why?(4), Let A is a Boolean algebra. Define operation * as following:a*b = (ab)(ab)show that (A,*) is an Abelian group.(5), The order of an elements g of a goup G is the least positive integer n such that gn =1G
9、(or is if none exists). (5.1) Prove that if f is an isomorphism from group G to G, and g is an element in G, then g and f(g) in G must have the same order.(5.2) Let G be the group of all real numbers under addition(+), and H be the group of all non-zero real numbers under multiplication(). Show that G and H are not isomorphic.