2002-2003学年第二学期a

《2002-2003学年第二学期a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、装订线内请勿答题信息科学技术学院2002-2003学年第二学期本科生期末考试试卷考试科目：集合论与图论考试时间：2003年6月专业级班姓名学号毛题号一二三四五六七八九十总分得分（注意：从下列1-5题中选做3道，从下列6-10题中选做3道，每题10分，试卷总计60分，平时成绩40分，期末总评100分。）1．证明或推翻下列命题：“设Å表示集合的对称差运算，则对于任意集合A和B成立：P(A)ÅP(B)=P(A)ÅP(C)ÛB=C”。（10分）解答与评分标准：命题成立（2分）。证明：Å有消去律，P(A)ÅP(B)=P(A)Å

2、P(C)ÛP(B)=P(C)（3分）。P(B)=P(C)ÛB=C（3分）。其他细节（2分）2．证明或推翻下列命题：“设R是从A到B的二元关系，则下列两个条件互为充要条件。条件一：存在CÍA且DÍB”使得R=C´D。条件二：对于A中任意x1,x2和B中y1,y2，有(x1Ry1Ùx2Ry2)®x1Ry2.”解答与评分标准：命题成立（2分）。条件一Þ条件二：x1ÎC，y2ÎD（3分）。-3-条件二Þ条件一：C=dom(R)，D=ran(R)（3分）。其他细节（2分）1．设A={1,2,…,10}，定义A上的二元关系R={

3、

4、x,yÎAÙx+y=10}，说明R具有哪些性质并说明理由。解答与评分标准：讨论5种性质（各2分）。非自反：<1,1>不属于A。非反自反：<5,5>ÎA。对称：定义。非反对称：<3,7>,<7,3>ÎA但7不等于3。非传递：<3,7>,<7,3>ÎA但<3,3>不属于A。2．比较下列集合的基数大小并给出证明：A´A，P(A)，2®A，A®2.解答与评分标准：

5、A´A

6、=

7、2®A

8、=

9、A

10、2（2分），

11、P(A)

12、=

13、A®2

14、=2

15、A

16、（2分）。分情况讨论：(1)A为空集：注意A®2={空关系}，

17、A´A

18、=

19、

20、2®A

21、=0<

22、P(A)

23、=

24、A®2

25、=1。（1分）(2)A为有限集且

26、A

27、=1：

28、A´A

29、=

30、2®A

31、=

32、A

33、2=1<2=2

34、A

35、=

36、P(A)

37、=

38、A®2

39、。（1分）(3)A为有限集且

40、A

41、=2：

42、A´A

43、=

44、2®A

45、=

46、A

47、2=4=2

48、A

49、=

50、P(A)

51、=

52、A®2

53、。（1分）(4)A为有限集且

54、A

55、=3：

56、A´A

57、=

58、2®A

59、=

60、A

61、2=9>8=2

62、A

63、=

64、P(A)

65、=

66、A®2

67、。（1分）(5)A为有限集且

68、A

69、>4：

70、A´A

71、=

72、2®A

73、=

74、A

75、2<2

76、A

77、=

78、P(A)

79、=

80、A®2

81、。（1分）(6)A为无限集：

82、

83、A´A

84、=

85、2®A

86、=

87、A

88、2=

89、A

90、<2

91、A

92、（康托定理）=

93、P(A)

94、=

95、A®2

96、（1分）。注(1)(2)(5)(6)结果相同，可合并。3．在一种计算机信息检索的模型中，一个文件是由一些关键字组成的，而一个倒排文件是由含有某个关键字的所有文件组成的。一次查询的输入是一个关键字，输出是这个关键字的倒排文件，一次查询的开销就是包含这个关键字的文件个数。多次查询就是查询一个关键字序列（其中可能有重复关键字）中的每个关键字，多次查询的开销-3-是各次查询的开销之和，其中重复查询同一个关键字的开销之只计算一次。假设关键字

97、和文件的个数都是有限的，试用集合论或图论的术语来描述这个模型，并给出上述斜体字概念的形式化定义。解答与评分标准：集合论：文件集合D={d1,d2,…,dn}，关键字集合K={k1,k2,…,km}，倒排文件集合K’={k1’,k2’,…,km’}与关键字集合K一一对应。D包含于P(K)，K’包含于P(D)，ki属于dj当且仅当dj属于ki’（4分）。查询是从K到P(D)的函数Q：K®P(D)，查询k是求Q(k)（2分），查询k的开销是

98、Q(k)

99、（2分）。多次查询(s1,s2,…,st)就是求(Q(s1),Q(s2)

100、,…,Q(st))，多次查询的开销是对不同的si求

101、Q(si)

102、之和（2分）。图论：二部图G=，D为文件集合，K为关键字集合，E为边集合，(d,k)是E中的边当且仅当文件d含有关键字k（4分）。文件d的内容就是d的相邻顶点集合（邻域），倒排文件k的内容就是k的邻域，查询k就是求k的邻域（2分），查询k的开销就是k的度数（2分）。多次查询就是求一组关键字的邻域，多次查询的开销就是这组关键字顶点的度数之和，重复关键字只计算一次（2分）。1．证明或推翻下列命题：“设平面上有100个点，其中任意两点间的距离至少

103、是1，则最多有300对点距离恰好是1”。解答与评分标准：命题成立（2分）。无向图G=，V是平面上的这100个点，两个点相邻当且仅当这两点距离恰好是1（2分）。每个顶点的度数不超过6（3分）。根据握手定律（3分），2

104、E

105、=顶点度数之和£100*6,所以这个图的边数不超过300（2分）。2．所谓n维网格就是一个无向图G=，其中