数据结构课程实习

《数据结构课程实习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、填空题1・{3};{{3},{1,3},{2,3},{1,2,3}}.2.22■3.1={(a,1),(b,1)},2={(a,2),(b,2)},3={(a,1),(b,2)},4={(a,2),(b,1)};3,4.4.(PAQAR)・5.12,3.6.{4},{1,2,3,4},{1,2}.7.自反性；对称性；传递性.8.(1,0,0),(1,0,1),(1,1,0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x

2、TWx〈0,

3、xR};{x

4、1

5、OWxWl,xR}.12.12;6.13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14.x(P(x)VQ(x)).15.21.16.(R(a)AR(b))->(S(a)VS(b)).17.{(1,3),(2,2)};{(1,1),(1,2),(1,3)}.二、选择题1.C.2.D.3.B.4.5.D.6.C.7.C.&A.9.D.10.B.11.13.A.14.A.15.D三、计算证明题1.812642139B.B.(1)(2)

6、B无上界，也无最小上界。下界1,3;最大下界是3.(3)A无最大元，最小元是1,极大元&12,90+;极小元是1.2.R二{(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)1423(2)MR11110111001100013.(1)•=((x))=(x)+3=2x+3=2x+3・(2)•=((x))=(x)+3=(x+3)+3=x+6,(3)•=((x))=(x)+3=x/4+3,(4)•=((x))=(x)/4=2x/4二x/2,(5)••=•(

7、•)=•+3=2x/4+3=x/2+3・4.(1)P(a,f(a))AP(b,f(b))二P(3,f(3))AP(2,f(2))二P(3,2)AP(2,3)二l/二0.(2)xyP(y,x)=x(P(2,x)VP(3,x))=(P(2,2)VP(3,2))A(P(2,3)VP(3,3))二(0V1)A(0V1)二1A1二1.5.(1)8412621⑵无最大元，最小元1,极大元&12;极小元是1.(3)B无上界,无最小上界。下界1,2;最大下界2.6.G二(P->Q)V(QA(P-R))二(PVQ)V(QA(PVR))二(P

8、AQ)V(QA(PVR))二(PAQ)V(QAP)V(QAR)二(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)二(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)二m3Vm4Vm5Vm6Vm7=(3,4,5,6,7).7.G二(xP(x)VyQ(y))-xR(x)二(xP(x)VyQ(y))VxR(x)二(xP(x)AyQ(y))VxR(x)二(xP(x)AyQ(y))VzR(z)二xyz((P(x)AQ(y))VR(z))9.(1)r(R)=RU1A

9、={(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(R)=RUR1={(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},t(R)=RUR2UR3UR4={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)关系图:adadadbcr(R)bcs(R)bct(R)11.G=(PAQ)V(PAQAR)=(PAQAR)V(PAQAR)V(PAQAR)=m6Vm7Vm3=(3,6,7)H二(PV(

10、QAR))A(QV(PAR))=(PAQ)V(QAR))V(PAQAR)=(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)=(PAQAR)V(PAQAR)V(PAQAR)=m6Vm3Vm7=(3,6,7)G,II的主析取范式相同，所以G二IL⑴MS(2)R・S={(a,b),(c,d)},RUS={(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R1={(a,a),(c,a),(c,b),(d,c)},S1・R1={(b,a),(d,c)}.四证明题1.证明：

11、{P-Q,R-S,PVR}蕴涵QVS(1)PVR(2)RfP(3)PfQ⑷R-Q(5)Q-R(6)RfS(7)Q-S(8)QVSPQ(l)PQ(2)(3)Q(4)PQ(5)(6)Q(7)(4)C-B(5)B-C(6)C(7)CT(8)D(9)A-DPQBQ⑶⑸PQ⑹(7)D(