资源描述：
《离散数学-2006`2007(2)-试卷B参考答案及评分细则.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、*密*参考答案及评分细则西南科技大学2006——2007学年第2学期《离散数学J》期末考试试卷（B卷）计算机科学与技术学院课程代码143140320命题单位软件教研室一、解：图（1）能画出，比如：v1-v2-v3-v4-v7-v8-v3-v7-v6-v2-v5-v6-v1-v5。(3分)图（2）不能一笔画出，（1分）因为图（1）中奇度数顶点数为4。（2分）二、解：图（1）存在哈密尔顿回路，比如：v1-v2-v3-v4-v5-v6-v7-v8-v1。（3分）图（2）不存在哈密尔顿回路，（1分）因为，取V'
2、={v2,v6}，则连通分支数w(G-V')＝3＞
3、V'
4、＝2，因而该图不是哈密尔顿图。(2分)三、（4分）四、解：由握手定理知，图G中所有顶点度数之和为边数的两倍，（2分）图G中所有顶点度数之和为2×3＋3×4＋4×5＝38（1分）因此G中共有19条边。（1分）第1页共6页*密*参考答案及评分细则西南科技大学2006——2007学年第2学期《离散数学J》期末考试试卷（B卷）五、解：最优二元树参考如下图：（4分）W(T)＝1×4＋2×4＋5×3＋3×3＋3×3＋6×2＋7×2＝71（1分）六、解：前序遍
5、历：∧∨P∧┐PQ∧∨┐PQ┐R（3分）中序遍历：P∨┐P∧Q∧┐P∨Q∧┐R（3分）后序遍历：PP┐Q∧∨P┐Q∨R┐∧∧（3分）七、解：列公式┐(Q→P)∧P和┐((P∧Q)→P)的真值表如下（真值表共8分，每项2分）：PQ┐(Q→P)∧P┐((P∧Q)→P)0000010010001100因为真值表的最后两列完全相同，所以公式┐(Q→P)∧P和┐((P∧Q)→P)等值。（2分）第2页共6页*密*参考答案及评分细则西南科技大学2006——2007学年第2学期《离散数学J》期末考试试卷（B卷）八、解：
6、A×B＝{,,,,,}（4分）r(R)={,,,,}（a分）s(R)={,,,}（a分）t(R)={,,}（2分）九、解：设参加英语学习小组用集合A表示，参加数学学习小组用集合A表示。12则
7、AA∪
8、5017=−=33（3分）12
9、AAAAAA∩∪
10、
11、=+−
12、
13、
14、
15、
16、26213314=+−=（5分）所以，121212有14个学
17、生既参加了英语学习小组又参加了数学学习小组。（2分）若画出文氏图给5分。十、解：要设计一个方案使各城市间能够通讯且总造价最小，即求该图的最小生成树。如下图（4分）。第3页共6页*密*参考答案及评分细则西南科技大学2006——2007学年第2学期《离散数学J》期末考试试卷（B卷）最小生成树的权值即为最小总造价：1＋2＋3＋5＋7＝18。（2分）十一、证明：平面图G有k个连通分支，每个连通分支都是连通平面图。图G的每个连通分支都满足欧拉公式。（1分）设G的第i个连通分支有n个顶点，m条边，r个面，则有：ii
18、inmr−+=2（2分）iiikkk∑∑∑nmrkiii−+=2（1分）iii===111kkk而∑nni=，∑mmi=，∑rrki=+−1（2分）i=1i=1i=1故nmrk−++−=12k（1分）因此，nmrk−+=+1。（1分）十二、解：（1）设该树的树叶个数为x。根据树的性质和握手定理有：（2分）3×2＋1×3＋x×1＝2（3＋x＋1－1）x=3所以，T中有7个结点。（2分）（2）符合题设条件的无向树有以下三种：第4页共6页*密*参考答案及评分细则西南科技大学2006——2007学年第2学期《离
19、散数学J》期末考试试卷（B卷）（每个2分）十三、解：（1）将G中结点按v1，v2，v3，v4，v5排序，则G的邻接矩阵为⎡⎤01010⎢⎥00001⎢⎥A=⎢⎥01010（4分）⎢⎥00001⎢⎥⎢⎥⎣⎦101004（2）为了求G中长度为4的路径数目，计算A⎡⎤04040⎢⎥00004⎢⎥4A=⎢⎥04040（2分）⎢⎥00004⎢⎥⎢⎥⎣⎦40400所以长度为4的路径数为32（1分），长度为4的回路数为0（1分）。（3）可达性矩阵为：第5页共6页*密*参考答案及评分细则西南科技大学2006——2007
20、学年第2学期《离散数学J》期末考试试卷（B卷）⎡⎤11111⎢⎥11111⎢⎥P=⎢⎥11111（2分），⎢⎥11111⎢⎥⎢⎥⎣⎦11111所以该图为强连通图。（2分）第6页共6页
