离散期末练习试卷.doc

上海应用技术学院20082009学年第一学期 离散数学 期末试卷（A） 课程代码: B204216 学分: 4 考试时间: 100 分钟课程序号: 3404 班级： 学号： 姓名: 我已阅读了有关的考试规定和纪律要求，愿意在考试中遵守考场规则，如有违反将愿接受相应的处理。题 号一二三四五六七八九十总 分应得分202010101210108100实得分 试卷共 6 页，请先查看试卷有无缺页，然后答题。一选择题(10 x 2 =20)1. 下列命题中命题（ ）为假。A. “如果2是偶数，则一个公式的主析取范式唯一。”B. “如果2是偶数，则一个公式的析取范式唯一。” C. “如果2是奇数，则一个公式的析取范式唯一。” D. “如果2是奇数，则一个公式的主析取范式唯一。”2. 命题公式的成真赋值为（ ）。A. 001 B. 110 C. 100 D. 0103. 集合A=x| x是单词“command”中的字母，B=x,a,b,c,d,则|AB|=（ ）。A. 7 B. 8 C. 4 D. 34. .若个体域为0，1，2，3，下列公式中值为真的是（）。A.x$y(x+y=0) B.$yx(x+y=0)C.xy(x+y=0) D. $x$y(x+y=0)5. 设集合 S=0,1,1,2,3,2,3,4,5,集合( )是S中所有元素的交集。A. 0,1,2,3,4,5 B. 1 C. D. 0,16. 若AB且BC则 （ ）。A. AC =B B. AB= A C. AC =A D. AC =B7. 在自然数集合N上，下列运算中（ ）满足结合律。A. a * b = | a-b | B. a * b = a+2b C. a * b = max( a,b ) D. a * b = a b8. 以下关系中（ ）不具有传递性。A.S= , , , B. S= , C. S=,D. S=, 9. 以下命题中（ ）是假命题。A.“群满足结合律”B.“群中只有一个幺元”C.“群中无零元”D.“群满足交换律”10设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）。A3B4C5D6二填空题(2 x 10 = 20)1. 设A=1,2,3,4，RAA，R=，,，则R的自反闭包r(R)=_ _，对称闭包t(R)=_ _。2. A=-1,0，1，则独异点，它的幺元为 ，-1的逆元为 。3. 设F(x)表示“x是奇数”，H(x)表示“x是偶数”，G(x) 表示“x是整数”，用谓词公式表示命题“所有整数要么是奇数要么是偶数。” 。4. 有向图中任意两点间均相互可达 ，此图为 连通图。若任二顶点间至少从一个顶点到另一个顶点是可达的，则称此图为 连通图5设A=a,b,B=0,1,则A与B的笛卡尔积AB= 。 6设命题P：天下雨，Q：我进城，R：我有空。用自然语言写出下列命题。（PQ）（RQ）： 。7具有n个元素的集合A的子集个数是 。三设A=1,2,3,4，它的一个划分=1，3，2，4。 （10）1写出对应的等价关系R；（3）2画出R的关系图；（3）3写出A中元素关于R的等价类。（4）四写出命题公式( p ( p q ) r的真值表，并按真值表写出主析取范式和主合取范式。（10）五有带权图G如下(12)1写出图G的邻接矩阵（3）2求最小生成树和树权T（w）。（写出每一步生成过程）（7）3找出图中的“割点”（2）ef162115181118cbda19六给定权 1，4， 6 ， 7， 8，11，22，36，构造一棵最优二元树，并计算该二元树的权（写出构造的过程）。（10）七设有集合Z4 =0，1，2，3，+4 为定义在Z4 上的模4加法（两数相加后除以4的余数）（10）1构造的运算表；（4）2证明是一个群；（6） 八构造推理证明(8)前提：pq , pr , st , sr,t结论：q上海应用技术学院20082009学年第一学期离散数学期末考试（A）试卷标准答案一 选择题（20） BADDC CCADB二 填空题（20）1. ， 2. 1，-13. 4. 强， 单向5. ，6. 若天不下雨并且我有空，那么我进城。7. 2n三 （10分）(1)R=,(2)图略(3)1=3=1,3 , 2=2, 4=4四（10分） 主析取范式 m0 m1 m2m3 m5m6 m7主合取范式 M0五 有带权图G如下(12分) 最小生成树如下：bacdfew(t)=11+15+16+18+21=81A(G)=95六 给定权 1，4， 6 ， 7， 8，11，22，36，构造一棵最优二元树，并计算二叉树的权（写出构造的过程）。（10分）15145678223736221111 权=(1+4)*5+6*4+(7+8+11)*3+(36+22)*2 = 243七设有集合Z4 =0，