新东方在线网络课堂 同等学力 新东方在线 > 同等学力 > 同等学力 > 同等学力计算机 > 正文

2016同等学力申硕计算机基础练习题(3)

2015-12-01 12:17:29 来源:新东方在线 同等学力资料下载

  2016同等学力申硕计算机复习进行中,新东方在线分享相关练习题,赶快来练习吧!

  2016同等学力申硕计算机基础练习题(3)

  1. 证明或推翻下列命题:“设平面上有 100 个点,其中任意两点间的距离至少是1,则最多有300 对点距离恰好是1”。

  解答与评分标准:

  命题成立(2 分)。

  无向图 G=,V 是平面上的这100 个点,两个点相邻当且仅当这两点距离恰好是1(2 分)。

  每个顶点的度数不超过 6(3 分)。

  根据握手定律(3 分),

  2|E|=顶点度数之和≤100*6, 所以这个图的边数不超过300(2 分)。

  2. 所谓 n 维网格就是一个无向图G=,其中V={ | 1≤ij≤mj,1≤j≤n},E={(v1,v2)| v1 和v2 恰好只在一个坐标上相差1}。讨论当mj 和n 取哪些正整数值时,G 是哈密顿图,并给出证明。

  解答与评分标准:

  分情况讨论。注意 G 的顶点数是m1*m2*m3*…*mn。

  (1) 所有mj 都为1:G 是平凡图,是哈密顿图(2 分)。

  (2) 恰好有一个mj 大于1:G 是长度大于1 的初级路径,不是哈密顿图(2 分)。

  (3) 至少有两个mj 大于1:G 是偶图(无奇数长度回路)(2 分)。

  (3a) m1*m2*m3*…*mn 是偶数:G 是哈密顿图,用归纳法构造哈密顿回路(2 分)。

  (3b) m1*m2*m3*…*mn 是奇数:G 不是哈密顿图,偶哈密顿图两部分顶点数相等,总顶点数是偶数(2 分)。

  3. 证明或推翻下列命题:“任意给定平面上有限个点,则连接这些点的最短哈密顿回路的长度不超过连接这些点的最小生成树(不添加额外顶点)的长度的2 倍。子图的长度就是这个子图上的边的长度之和。”

  解答与评分标准:

  命题成立(2 分)。

  (课本图论部分最后一章定理)先求最小生成树奇数度顶点之间的“最小”匹配,加入匹配“边”得到欧拉图(3 分)。

  沿着欧拉回路前进,“抄近路”避开已经访问过的顶点,就得出哈密顿回路(3 分)。

  由于距离的三角形不等式,这条哈密顿回路长度不超过最小生成树长度的2 倍(2 分)。

  4. 画出所有非同构的 5 阶根树。

  解答与评分标准:

  9 种(每种1 分,重复画扣0.5 分,全画10 分)。非同构的5 阶树共有3种,分别选一个顶点做根。

  5.证明或推翻下列命题:“设连通简单平面图G 的最小度δ(G)≥4,则G 的点色数χ(G)≥3.”

  解答与评分标准:

  假设χ(G)<3.(反证法分情况讨论2 分)

  χ(G)=1 当且仅当G 为n 阶零图,与已知矛盾。(4 分)

  χ(G)=2 当且仅当G 为二部图,因为G 为平面图,只能为K2,s 或Kr,2. 此时必有δ(G)=2, 与已知矛盾。(4 分)


本文关键字: 同等学力计算机 同等学力申硕

分享到:

课程试听换一换

  • 2016同等学力英语+经济学综合全程联报班

    ¥1980.013003试听

    翁华

    新东方在线名师,主讲:同等学力英语、在职联考英语,2002年6月毕业于天津外国语大学英语系早在大学期间...

    2016同等学力...
  • 2016同等学力经济学串讲班

    ¥500.013041试听

    张乃岳

    张乃岳,新东方在线名师。教授,毕业于北京大学,拥有计算机、数学、金融学以及统计学等五个学位。曾在...

    2016同等学力...
  • 2016年 同等学力法学综合全程班

    ¥800.013015试听

    陈璐琼

    陈璐琼老师:新东方在线优秀名师,北京大学法学博士,陈老师有多年的考研法硕辅导、司法考试辅导经验,...

    2016年 同等...
  • 2016年 同等学力英语+法学综合全程班

    ¥2380.012991试听

    翁华

    新东方在线名师,主讲:同等学力英语、在职联考英语,2002年6月毕业于天津外国语大学英语系早在大学期间...

    2016年 同等...
  • 2016同等学力工商管理串讲班

    ¥500.012994试听

    张乃岳

    张乃岳,新东方在线名师。教授,毕业于北京大学,拥有计算机、数学、金融学以及统计学等五个学位。曾在...

    2016同等学力...
  • 2016同等学力英语+工商管理全程联报班

    ¥1980.012986试听

    翁华

    新东方在线名师,主讲:同等学力英语、在职联考英语,2002年6月毕业于天津外国语大学英语系早在大学期间...

    2016同等学力...
  • 2016同等学力临床医学全程班

    ¥1680.013209试听

  • 2016同等学力英语基础恢复班

    ¥500.013710试听

    翁华

    新东方在线名师,主讲:同等学力英语、在职联考英语,2002年6月毕业于天津外国语大学英语系早在大学期间...

    2016同等学力...
  • 2016同等学力英语技巧提高班

    ¥400.012984试听

    翁华

    新东方在线名师,主讲:同等学力英语、在职联考英语,2002年6月毕业于天津外国语大学英语系早在大学期间...

    2016同等学力...
  • 2016同等学力英语真题精讲班

    ¥800.012984试听

    翁华

    新东方在线名师,主讲:同等学力英语、在职联考英语,2002年6月毕业于天津外国语大学英语系早在大学期间...

    2016同等学力...
  • 2016同等学力英语冲刺抢分班

    ¥500.012989试听

    翁华

    新东方在线名师,主讲:同等学力英语、在职联考英语,2002年6月毕业于天津外国语大学英语系早在大学期间...

    2016同等学力...
  • 2016同等学力英语全程班

    ¥1780.014435试听

    屠皓民

    新东方在线名师,有着丰富的教学经验,主讲在职申硕英语课程。屠老师的课堂气氛活跃,知识性和趣味性相...

    2016同等学力...
  • 同等学力_法学综合考点点拨【免费注册即...

    ¥200.012264试听

  • 同等学力_临床医学考点点拨【免费注册即...

    ¥200.012264试听

  • 同等学力_英语提分秘籍【免费注册即可领...

    ¥200.012265试听

相关推荐

版权及免责声明

1,"新东方在线"上的内容,包括文章、资料、资讯等, 本网注明"稿件来源:新东方在线"的,其版权 均为"新东方在线"或北京新东方迅程网络科技有限公司所有 ,任何公司、媒体、网站或个人未经授权不得转载、链接、转贴或以其他方式使用。已经得到 "新东方在线"许可 的媒体、网站,在使用时必须注明"稿件来源:新东方",违者本网站将依法追究责任。

2, "新东方在线" 未注明"稿件来源:新东方"的 文章、资料、资讯等 均为转载稿,本网站转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如其他媒体、网站或个人从本网站下载使用,必须保留本网站注明的"稿件来源",并自负版权等法律责任。如擅自篡改为 " 稿件来源:新东方 " ,本网站将依法追究其法律责任。

3,如本网转载稿涉及版权等问题,请作者见稿后在两周内与新东方在线联系。

  • 新东方在线99网络学习节
  • 2019考研课程 重磅上线

热点资讯更多>>

实用 • 工具

交流 • 下载

同等学力课程排行榜本周本月

同等学力公开课更多>>

同等学力英语基础语法入门 w 28分35秒
1 同等学力英语基础语法入门
同等学力西方经济学-微观经济学(供给曲线) w 10分52秒
2 同等学力西方经济学-微观经济学(供给曲线)
同等学力法学民法诉讼时效 w 13分57秒
3 同等学力法学民法诉讼时效
同等学力工商管理财务管理 w 05分54秒
4 同等学力工商管理财务管理
同等学力临床医学内科学-骨髓增生异常综合征 w 22分08秒
5 同等学力临床医学内科学-骨髓增生异常综合征

推荐阅读