《离散数学》期终试题-软件学院.docVIP

选择题20分 10题多选题 1, Let B={?}, A =ρ(ρ(B)), find the correct ones in following statements: (1) ?∈A (2) {?,{ ? }}∈A (3) {?,{{?}}∈A (4) {?,{{?}}A 2, Let R be a relation on A={1,2,3,…,10}, R={(x,y)|x+y = 10, x,y∈A}, then R is: (1) reflexive (2) symmetric (3) transitive (4) antisymmetric 3, Let |A| = n, how many binary operations can we define on A: 2nn2(1) 2n (2) n2 (3) n 2n n2 4, operation defined as following, which ones can not make ({a,b},*) a monoid? (1) (2) LINK Word.Document.8 F:\\离散试卷.doc OLE_LINK1 \a \r (3) (4) 5, which ones are lattices in the following posets? (1)(2) (1) (2) (3) (4) 6，Let directed graph D = V,E, then: (1), EV×V (2), EV×V (3) E=V×V (4) V×VE 7, In a connected undirected graph with n vertices, the number of edges is (1) at least n-1 (2) at least n (3) at most n(n-1)/2 (4) at most n2/2 8, which one is tautology? (1) (P∧(P→Q))→Q (2)P→(P∨Q) (3) P→(P∧Q) （4）(P→Q)→Q 9,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 multiple 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 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 coefficient 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 Prim’s algorithm to find a minimum spanning tree in the following graph（detail steps needed）: E E A 3 D 2 F 4