图论考试(中法)

《图论考试(中法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、山东科技大学2008—2009学年第一学期《图论》考试试卷（A卷）班级姓名学号题号一二三四总得分评卷人审核人得分一、填空题（每空2分，共30分）1.条边的图中全部顶点的总次数是100。2.100个顶点的星的最大顶点次数是。3.个顶点的图的生成子树中有个顶点和100条边。4.Peterson图（是、否）Euler图，（是、否）Hamilton图。5.的每个顶点次数为，总共有条边，有种完美匹配，它的平面嵌入的厚度下界为。6.对一个括号序列进行检测，从左向右数到第99个括号时，记录了右括号个，因此得出结论为坏括号序列。7.100个顶点的极大连通平

2、面图中最多有条边，个面。8.有向图的底图是连通的，则至少为一连通有向图；若存在一个以的某个顶点为根的外向树，则为一连通有向图。矚慫润厲钐瘗睞枥庑赖。二、画图题（每题5分，共15分）1.画出所有不同构的5顶点树。2.画出5次正则完全图，证明它是否为Euler图。3.画出面数最多的6顶点连通二分平面图的平面嵌入，并指出它有几个面。三、应用题（10分）1.有把钥匙和把锁混在一起，确定知道每把锁都能有一把钥匙打开，锁匠想把它们一对对的分开，那么有多少种分法是每对中的钥匙都无法打开锁的。聞創沟燴鐺險爱氇谴净。①给出求解上述问题的递归公式，并证明之；②

3、算出时问题的解。四、算法题（第1、2、3每题10分，4题15分，共45分）2/41.写出用Kruskal算法求图1生成子树的运行过程：图1①按算法的运行顺序写出每一轮所选的边；②写出对所选的边所进行的操作及其原因（指出算法如何判断所选边是否符合生成树的条件）；③给出算法终止的条件。（设算法按照下标由小到大的顺序遍历所有边，且对每条边，都有。）2.若有5字符出现的概率表为字符abcde出现概率0.20.160.130.280.23写出用Huffman算法求上表中5字符Huffman编码的运行过程：①依“左子概率小于右子”的原则，按算法的运行顺

4、序写出每一轮构造的由有序二元树组成的森林；②给出算法终止的条件；③按照“左0右1”的原则给出这5个字符的Huffman编码。图23.写出用Hungarian算法求图2完备匹配的运行过程：①按算法的运行顺序写出每一轮所选择的点，写出从该点出发构造的可增广轨；②按①中所求的可增广轨求出的本轮所得匹配；③给出算法终止的条件。（设初始匹配为，对算法中每条边都表示为，对顶点的遍历顺序为）图34.求图3的中国邮路问题，设为邮局。①写出求图3的“倍边”（重边）的过程；②写出用FE算法求Euler回路的过程；③给出算法终止的条件，列出最后所得的中国邮路。（

5、设算法按照下标由小到大的顺序遍历所有顶点，且对每条边，都有。）2/4山东科技大学2008—2009学年第一学期《图论》考试试卷（B卷）班级姓名学号题号一二三四总得分评卷人审核人得分一、填空题（每空2分，共30分）1.100个顶点的星中有条边。2.100条边的图中全部顶点的总次数是。3.100个顶点的图的生成子树中有个顶点和条边。4.Peterson图（是、否）Euler图，（是、否）Hamilton图。5.的每个顶点次数为，总共有条边，它种完美匹配，它的平面嵌入的厚度下界为。6.对一个好括号序列进行检测，从左向右至少数到第个括号时，会记录下

6、50个右括号。7.100个面的极大连通平面图中最多有条边，个顶点。8.对有向图，若存在一个以的某个顶点为根的内向树，则为一连通有向图；若存在一条有向Hamilton圈则为一连通有向图。残骛楼諍锩瀨濟溆塹籟。二、画图题（每题5分，共15分）1.画出所有不同构的只含一个圈的4顶点单图。2.画出3次正则完全二分图，证明它是否为Euler图。3.画出面数最多的5顶点连通平面图的平面嵌入，并指出它有几个面。三、应用题（10分）1.某次会议主席台上有个座位，但会议组织者把入座名单搞丢了，于是他们又重新摆上名字，那么有多少种摆法是每个座位上的名字都错了。

7、酽锕极額閉镇桧猪訣锥。①给出求解上述问题的递归公式，并证明之；②给出时问题的解。四、算法题（第1、2、3每题10分，4题15分，共45分）2/4图11.写出用Dijkstra算法求图1中从点出发的单源最短轨的运行过程：①按算法的运行顺序写出每一轮备选顶点集的变化和备选顶点的前驱；②写出每一轮求出的最短轨；③给出算法终止的条件。（设算法按照下标由小到大的顺序遍历所有顶点，且对每条边，都有。）2.若有5字符出现的概率表为字符abcde出现概率0.40.110.190.170.13写出用Huffman算法求上表中5字符Huffman编码的运行过程

8、：①依“左子概率小于右子”的原则，按算法的运行顺序写出每一轮构造的由有序二元树组成的森林；②给出算法终止的条件；③按照“左0右1”的原则给出这5个字符的Huffman编码。图23