2_计算机学院_离散数学期末考试_2011年春季_试卷B1

课程组长（签字）系主任（签字）学院姓名学号选课/座号号任课老师………密………封………线………以………内………答………题………无………效……第1页共6页电子科技大学2010-2011学年第2学期期末考试A卷课程名称：_离散数学(双语)考试形式：闭卷考试日期：2011年月日考试时长：120分钟课程成绩构成：平时10%，期中10%，实验10%，期末70%本试卷试题由__7___部分构成，共___6__页。题号一二三四五六七八九十合计得分–––I.MultipleChoice(20%,10questions,2pointseach)（A）1.SupposeS={1,2,3,4,5}.Find().PSa)32b)5cd（B）2Whichoftheseimplicationsisfalse?a)If1+1=3then2+2=5b)If1+1=2then2+2=5c)If1+1=2then2+2=4d)If1+1=3then2+2=4（B）3.Thebestbig-Ofunctionfor(x2)log2(x21)log2(x31)isa)x(log2x)2b)xlog2x.c)x2.d)(log2x)2.（B）4.Howmanybitstringsoflength10haveexactlysix0s?a)210b)C(10,6).c)26d)36（D）5.If1111011100110001RM,thenRisnot(a)reflexive(b)antisymmetric(c)transitive.(d)symmetric（C）6.Supposef:RRhasthefollowingpropertyforallrealnumbersxandy:ifxythenf(x)f(y).Whichofthefollowingistrue?a)fmustbeboth1-1andontoR.b)fisnotnecessarily1-1andnotnecessarilyontoR.c)fmustbe1-1butisnotnecessarilyontoR.d)fisontoRbutisnotnecessarily1-1.（C）7.Sisacollectionofstringsofsymbols.Itisrecursivelydefinedby1)aandbbelongtoS;2)ifstringXbelongstoS,sodoesXb.WhichofthefollowingdoesNOTbelongtoS?a)abbbb)bbbc)bad)a（B）8.Giventheinductivedefinition:f(1)=2,f(2)=2andf(n)=2f(n-1)+f(n-2)forn2.f(5)is:a)8b)34得分课程组长（签字）系主任（签字）学院姓名学号选课/座号号任课老师………密………封………线………以………内………答………题………无………效……第2页共6页c)14d)36（C）9.Whichoneofthesepropositionsisdifferentfromtheotherthree?(Forthisproblem,fandgarenon-negativefunctions.)a)g(x)=(f(x))b)ck[(xk)(f(x)c·g(x))]c)ck[(xk)(f(x)c·g(x))]d)¬ck[(xk)(f(x)c·g(x))]（D）10.Whichofthesepropositionsisfalse(thedomainisthesetofrealnumbers)?a)xy(x≠=0x·y=1)b)yx(x+y=x)c)xy[(x≠=y)z(xzyyzx)]d)xyz(xzy)II.TrueorFalse(10%,10questions,1pointeach)（F）1.Thefollowingsentenceisaproposition:“x+49.”（T）2.Thereisnosimplegraphwith8vertices,whosedegreesare01234567.（T）3.(pq)(pq)isequivalenttoq.（T）4.Theproposition((pq)q)pisatautology.（T）5..A(BC)(AB)C.（F）6.Thesetaaisthepowersetofsomeset（T）7.SupposeBxx,thenP(B).（F）8.gNNwhereg(n)anyintegern,describesafunctionwiththegivendomainandcodomain（T）9.SupposegABandfBC,wherefgis1-1andfis1-1.gmustbe1-1?（F）10.Forallintegersabc,ifa(bc),thenabandacIII.FillintheBlanks(20%,10questions,2pointseach)1.Writeapropositionequivalenttopqusingonlypqandtheconnective:pq.2.Writethenegationofthestatement“Allintegersendinginthedigit7areodd.”ingoodEnglish:Someintegersendinginthedigit7arenotodd.3.Find1i[11,1i].{1}4.SupposeP(x,y)isapredicateandtheuniverseforthevariablesxandyis{1,2,3}.SupposeP(1,3),P(2,1),P(2,2),P(2,3),P(2,3),P(3,1),P(3,2)aretrue,andP(x,y)isfalseotherwise.ThetruthvalueofstatementxyP(xy)isTrue.5.Supposethevariablexrepresentsstudentsandyrepresentscourses,andT(xy):studentxistakingcoursey.WritethestatementxyT(xy)ingoodEnglishwithoutusingvariablesinyouranswers:Everystudentistakingatleastonecourse.6.Find311.jjiij257.10011.8.Aninverseof17modulo19is9.9.IfR(12)(14)(23)(31)(42),thesymmetricclosureofRis得分得分课程组长（签字）系主任（签字）学院姓名学号选课/座号号任课老师………密………封………线………以………内………答………题………无………效……第3页共6页(12)(13)(14)(21)(23)(24)(31)(32)(41)(42).10.Thesmallestequivalencerelationon123thatcontains(12)and(23)is:(11)(12)(13)(21)(22)(23)(31)(32)(33).IV.AnswertheQuestions(30%,6questions,5pointseach)：1.Findapropositionusingonlypq,andtheconnectivethathasthegiventruthtable.pq?TTFTFFFTTFFF(pq).2.Letf(x)x33.Findf(S)ifSis:(a)210123.(b)012345.Ans:(a)31029.(b)0292141.3.InthequestionsbelowsupposegABandfBCwhereABC1234,g(14)(21)(31)(42)andf(13)(22)(34)(42).Findfg.Ans:(12)(23)(33)(42).4.Amessagehasbeenencryptedusingthefunctionf(x)(x5)mod26.IfthemessageincodedformisJCFHY,decodethemessage.Ans:EXACT.5.Describearecursivealgorithmforcomputing32nwherenisanonnegativeinteger.得分课程组长（签字）系主任（签字）学院姓名学号选课/座号号任课老师………密………封………线………以………内………答………题………无………效……第4页共6页Ans:Thefollowingprocedurecomputes32n:procedurepower(n:nonnegativeinteger)ifn0thenpower(n)3elsepower(n)power(n1)power(n1).6.Representtheexpressionx+((x⋅y+x)/y)usingabinarytrees.V.(6%)Provethat(q(pq))pisatautologyusingpropositionalequivalenceandthelawsoflogic.Ans:(())(())(()())()()()()qpqpqpqpqpqqpqppqppqppqppGradingrubric:-3pointsformakingwrongassumptions.-2pointsfornotbeingabletocompletetheproof.-1to-3pointsforillegalusageofequivalencerules.得分课程组长（签字）系主任（签字）学院姓名学号选课/座号号任课老师………密………封………线………以………内………答………题………无………效……第5页共6页VI.(7%)Foranundisclosedreason,theGermanmilitaryoftenneedstotransmitamassiveamountofintegersthroughitscommunicationchannels.TheyuseASCIIencodingforthistransmission,sothateachdigitisencodedasaneight-bitstring.Becausealloftheircommunicationisinterceptedbyforeignintelligence,itiswellknownthroughouttheworldthatthefrequenciesofthedigitsthattheGermanstransmitareasfollows:HelptheGermanmilitarybydevelopinganoptimalvariable-lengthencodingfortheircommunication.UseaHuffmancodingtreeforthedevelopmentoftheencoding,andthenwritedowntheresultingbi