电子科大图论10年研究生试卷(A4模板)

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：120分钟一．填空题(每题3分，共18分)1．4个顶点的不同构的简单图共有__11___个；2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。

则G 中顶点数至少有__9___个；3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____;4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_.5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。

图G二．单项选择(每题3分，共21分)1．下面给出的序列中，是某简单图的度序列的是( A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2．已知图G 如图所示，则它的同构图是（ D ）3． 下列图中，是欧拉图的是（ D ）4． 下列图中，不是哈密尔顿图的是（B ）5． 下列图中，是可平面图的图的是（B ）AC DA B CD6．下列图中，不是偶图的是（ B ）7．下列图中，存在完美匹配的图是（B ）三．作图(6分)1．画出一个有欧拉闭迹和哈密尔顿圈的图；2．画出一个有欧拉闭迹但没有哈密尔顿圈的图；3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。

解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五．(8分)求下图G 的色多项式P k (G).解：用公式(G P k -G 的色多项式：)3)(3)()(45-++=k k k G P k 。

六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。

解：设该树有n 1个1度顶点，树的边数为m.一方面：2m=n 1+2n 2+…+kn k另一方面：m= n 1+n 2+…+n k -1 v v 13图G由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。

图论作业3一、填空题1. 完全图K2n共有个不同的完美匹配。

2. 超方体Q6的最小覆盖包含的点数为。

3. 图K m,n (m≤n)的最小覆盖包含的点数为。

4. 完全图K60能分解为个边不重的一因子之并。

5. 完全图K61能分解为个边不重的二因子之并。

6. 假设G是具有n个点、m条边、k个连通分支的无圈图，则G的荫度为。

7. 图G是由3个连通分支K1, K2, K4组成的平面图，则其共有个面。

8. 设图G与K5同胚，则至少从G中删掉条边才可能使其成为可平面图。

9. 设连通平面图G具有5个顶点，9条边，则其面数为。

10. 若图G是10阶极大平面图，则其面数等于。

11. 若图G是10阶极大外平面图，其内部面共有个。

二、不定项选择题1. 关于非平凡树T，下面说法错误的是( )(A) T至少包含一个完美匹配；(B) T至多包含一个完美匹配；(C) T的荫度大于1；(D) T是只有一个面的平面图；(E) T的对偶图是简单图。

2. 下列说法正确的是( )(A) 三正则的偶图存在完美匹配；(B) 无割边的三正则图一定存在完美匹配；(C) 有割边的三正则图一定没有完美匹配；(D) 有完美匹配的三正则图一定没有割边；(E) 三正则哈密尔顿图存在完美匹配。

3. 下列说法正确的是( )(A) 在偶图中，最大匹配包含的边数等于最小覆盖包含的点数；(B) 任一非平凡正则偶图包含完美匹配；(C) 任一非平凡正则偶图可以1-因子分解；(D) 偶度正则偶图可以2-因子分解；(E) 非平凡偶图的最大匹配是唯一的。

4. 下列说法中错误的是( )(A) 完全图K101包含1-因子；(B) 完全图K101包含2-因子；(C) 完全图K102包含1-因子；(D) 完全图K102包含2-因子；(E) 图G的一个完美匹配实际上就是它的一个1因子；(F) 图G的一个2-因子实际上就是它的一个哈密尔顿圈。

5. 下列说法正确的是( )(A) 方体Q n可以1-因子分解；(B) 非平凡树可以1-因子分解；(C) 无割边的3正则图可以1-因子分解；(D) 有割边的3正则图一定不可以1-因子分解；(E) 可1-因子分解的3正则图一定是哈密尔顿图。

电子科技大学研究生试卷（考试时间: 17:30 至19:30 , 共2 小时）课程名称网络体系与协议教师学时40 学分 2教学方式课堂教学考核日期2010 年1月14 日成绩一．选择题（每题2分，共30分）（注：以下每道选择题中提供三个答案，选择其中最贴切的一个答案）1.[ b ]全双工和半双工通信分别指：a. 两种通信分别是双向的和单向的；b. 两种通信都是双向的；c. 两种通信没有差别2.[ c ]同步传输的目的是a. 实现数据bit的同步；b. 实现帧同步；c. 实现信号的同步3.[ c ]链路层通信指：a. 物理层上实体的通信；b. 信道上传输帧；c. 通过逻辑信道与其它站点的通信4.[ a ]信道传输速率与信道延迟的关系是：a. 信道延迟与传输速率没有关系b.传输速率越高、信道延迟越小；b.传输速率越高、信道延迟越大5.[ c ]分段和重组的目的是为了：a.提高通信效率；b. 为上层提供动态的PDU长度；c. 适应下层对PDU长度的要求6.[ c ]不同站点上的两个实体(A和B)称为对等实体，若：a. 层次相同、协议相同的实体； b. A实体的PDU传输路径经过B实体；c. A实体与B实体在交换PDU7.[ a ]SAP指：a. 协议区分数据流的方法b. 协议提供的服务；c. 使用服务的方法；8.[ b ]面向连接的通信需要：a. 事先建立数据链路；b. 事先建立一条逻辑链路；c. 不需要建立链路9.[ a ]封装上层送下来的PDU时，a. 在原来的PDU首部前面再增加一个首部；b.去掉原来PDU的首部再封装新的首部；c. 如果原来的PDU有首部，就不再封装新首部10.[ a ]网络层与链路层的不同主要在于：a. 网络层需要与多个链路层接口而链路层只与一个物理层接口；b. 网络层和链路层在不同的层次；c. 网络层需要中继而链路层不需要中继11.[ c ]协议是指：a. 实体处理接收和发送PDU的功能和规则；b. 实体与下层实体的接口规则；c. 实体与对等实体的通信规则12. [ c ]链路层的上层实体是：a. 网络层实体；b. 网络层或更上层的实体；c.不清楚是哪层的实体13. [ a ]协议外中继主要原因为：a.与协议栈的层次有关；b. 为了不影响协议本身的功能；c. 仅在不同协议间中继时采用14. [ c ]隧道技术是指：a.在链路层上建一条专用链路称为“隧道”；b.在网络层各实体上建立的一条专门传输路径；c.在任意层上建立的两个点间的固定通信15. [ b ] 互连、互通、互操作指：a. 相同的意思；b. 不同层次上的通信；c. 网络层及以下各层的协议转换和通信二． 简答题：（每题5分，共40分） 1. 每个节点有一个全双工信道接口。

电⼦科技⼤学研究⽣⼊学考试812历年真题（2007-2016）电⼦科技⼤学地理信息系统基础历年真题（2007-2016）2007年电⼦科技⼤学攻读硕⼠学位研究⽣⼊学试题考试科⽬：424 地理信息系统基础⼀、名词解释（每⼩题6分，共48分）1.地理信息2.栅格数据结构3.空间索引4.数字⾼程模型5.地图投影6.地理数据互操作7.⽮量数据结构8.空间关系⼆、分析并⽐较⽮量数据结构与栅格数据结构的优缺点。

（16分）三、简述WebGIS的实现技术。

（16分）四、简述格⽹DEM的应⽤领域。

（16分）五、简述什么是3S（GIS、RS、GPS）集成，并举例说明。

（16分）六、地理信息系统软件的体系结构与功能作⽤。

（16分）七、试综合利⽤空间分析⽅法，根据现有Roads（道路图）、Streams（河流图）、Forest（森林图），找出满⾜以下条件的可砍伐林⽊的适宜森林区域范围。

请绘出各步骤结果草图以及流程图，并进⾏简要说明。

条件如下：①在道路300⽶（假定⼤约相当于下图②中0.3厘⽶）范围内的林⽊不能砍伐；②在河流500⽶（假定⼤约相当于图③中0.5厘⽶）范围内的林⽊不能砍伐。

（22分）2008年电⼦科技⼤学攻读硕⼠学位研究⽣⼊学试题考试科⽬：812 地理信息系统基础⼀、名词解释（每⼩题8分，共48分）1.空间叠加分析是指在统⼀空间参照系统条件下，每次将同⼀地区两个地理对象的图层进⾏叠加，以产⽣空间区域的多重属性特征，或建⽴地理对象之间的空间对应关系。

2.游程编码结构是逐⾏将相邻同值的⽹格合并，并记录合并后⽹格的值，以及合并⽹格的长度，其⽬的是压缩栅格数据量，消除数据间的冗余。

3.栅格数据结构基于栅格模型的数据结构简称为栅格数据结构，指将空间分割成有规则的格⽹，在各个格⽹上给出相应属性值来表⽰地理实体的⼀种数据组织形式。

点由⼀个单元格⽹表⽰，其数值与邻近⽹格值明显不同；线段由⼀串有序的相互连接的单元⽹格表⽰，各个格⽹的值⽐较⼀致，但与领域的值差异较⼤；多边形由聚集在⼀起的相互连接的单元⽹格组成，区域内部的格⽹值相同或差异较⼩，但与领域的值差异较⼤。

重庆邮电大学08-09学年度第一学期《图论及其应用》研究生考试试题（A ）（时间120分钟）1、设>=<ϕ,,E V G 是任意图，其中12{,,,}n V x x x =，12{,,,},m E e e e =则n 阶方阵)(ij a A =称为G 的邻接矩阵。

其中ij a 为 。

2、图>=<E V V G ,,21是二分图的充要条件是： 。

3、n K (n ≥3)中从任意指定一个顶点出发,有（ ）个不同的圈。

A.n ！ B.（n-1）！ C.（n-2）！ D.（n-3）！ 4、设T 是顶点数至少为5的树,则()x T =( ) A.2 B.3 C.4 D.5 5、带权为1,2,3,4,5,6的最优二叉树的权为 ( )。

A.48 B.49 C.50 D.51 6、若G 为长度是奇数的圈，则()x G =( ). 7、以0，1为构成元素，写出一个三阶格雷码。

8、设连通图G 具有欧拉回路的充要条件是 。

9、写出所有的正凸多面体： 。

10、设G 是任意平面图，则()G δ应满足的条件 。

二、(6分)画出4阶3条边的所有非同构的无向简单图。

三、(6分)证明：若无向图G 中恰有两个奇度顶点，则这两个奇度顶点必然连通。

————密———————————— —封————————————线————————————————————————————年级：专业： 班级：姓名：学号：—————————————————————————————————————————————————————————————四、(10分)已知完全二分图5,5K ,其中112345{,,,,}V x x x x x =，212345{,,,,}V y y y y y =,且5,5K 的权矩阵为A ，求5,5K 的最优匹配，并求出权和。

3554122022244100110012133A ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦五、(10分)用普林算法求下图1的一棵最小生成树.六、(10’)画一个四阶五条边的欧拉图，并做出该图的对偶图.七、(10分)通过布尔变量的运算，求下图3的全部极小支配集。

1电子科技大学研究生试卷（考试时间： 至 ，共__2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2013__年_6__月__20__日 成绩 考核方式： （学生填写）一．填空题(每空2分，共20分)1． n 阶k 正则图G 的边数m =_____。

2．4个顶点的不同构单图的个数为________。

3．完全偶图,r s K (,2r s ≥且为偶数)，则在其欧拉环游中共含____条边。

4．高为h 的完全2元树至少有_______片树叶。

5. G 由3个连通分支124,,K K K 组成的平面图，则其共有_______个面。

6. 设图G 与5K 同胚，则至少从G 中删掉_______条边，才可能使其成为可平面图。

7. 设G 为偶图，其最小点覆盖数为α，则其最大匹配包含的边数为________。

8. 完全图6K 能分解为________个边不重合的一因子之并。

9. 奇圈的边色数为______。

10. 彼得森图的点色数为_______。

二．单项选择(每题3分，共15分) 1．下面说法错误的是( )学 号 姓 名 学 院…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效……………………2(A) 图G 中的一个点独立集，在其补图中的点导出子图必为一个完全子图；(B) 若图G 连通，则其补图必连通； (C) 存在5阶的自补图； (D) 4阶图的补图全是可平面图. 2．下列说法错误的是（ ） (A) 非平凡树是偶图；(B) 超立方体图(n 方体,1n ≥)是偶图； (C) 存在完美匹配的圈是偶图； (D) 偶图至少包含一条边。

3.下面说法正确的是( )(A) 2连通图一定没有割点（假定可以有自环）； (B) 没有割点的图一定没有割边；(C) 如果3阶及其以上的图G 是块，则G 中无环，且任意两点均位于同一圈上；(D) 有环的图一定不是块。

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：120分钟一.填空题(每题3分，共18分)1. 4个顶点的不同构的简单图共有__11—;2. 设无向图G中有12条边，已知G中3度顶点有6个，其余顶点的度数均小于3。

则G中顶点数至少有__9―;3. 设n阶无向图是由k(k 2)棵树构成的森林，则图G的边数m=_n-k _______4. 下图G是否是平面图？答—是___;是否可1-因子分解？答—是_.5. 下图G的点色数(G) __________ ,边色数(G) __5 ________ 。

图G二.单项选择(每题3分，共21分)1. 下面给出的序列中，是某简单图的度序列的是(A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2. 已知图G如图所示，贝卩它的同构图是(D )3. 下列图中，是欧拉图的是(D)4. 下列图中，不是哈密尔顿图的是(B )ABC5.下列图中，是可平面图的图的是(B )6. 下列图中，不是偶图的是(B )7. 下列图中，存在完美匹配的图是(B )三. 作图(6分)1. 画出一个有欧拉闭迹和哈密尔顿圈的图；2. 画出一个有欧拉闭迹但没有哈密尔顿圈的图;3. 画出一个没有欧拉闭迹但有哈密尔顿圈的图;四. (10分)求下图的最小生成树，并求其最小生成树的权值之和。

解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五. (8分)求下图G 的色多项式P k (G).解：用公式P k (G e) P k (G) P 「(G?eh 可得G 的色多项式：P k (G) (k )5 3(k )4 侏)3、k(k 1)2(k 2)(k 3)。

六. (10分)一棵树有n 图个顶点的度数为2, n a 个顶点的度数为3,…，m 个顶点的度数为k ，而其余顶点的度数为1,求1度顶点的个数。

解：设该树有n 1个1度顶点，树的边数为 m.一方面：2m=n+2n 2+…+kn k另一方面： m= m+n 2+…+n k -1 解:由上面两式可得：n 1=门2+2皿+…+(k-1)n k七证明：(8分)设G是具有二分类(X,Y)的偶图，证明(1)G不含奇圈；(2) 若|X |工| Y |，则G是非哈密尔顿图。

2019电⼦科技⼤学研究⽣试卷答案电⼦科技⼤学研究⽣试卷（考试时间：⾄，共 2 ⼩时）课程名称图论及应⽤教师学时 60 学分 3 教学⽅式堂上授课考核⽇期 2019 年 5 ⽉⽇成绩考核⽅式：（学⽣填写）⼀．填空题(每空3分，共15分) 1. 图G 的邻接矩阵为0111101111001100?? ? ? ? ? ???, 则G 的⽣成树的棵数为 8 . 2. 设1G 是11(,)n m 简单图,2G 是22(,)n m 简单图,则1G 和2G 的(Cartesian)积图12G G ?的边数()m G =1221n m n m +. 3. 图1中最⼩⽣成树T 的权值()W T = 23 .4. 图2中S 到T 的最短路的长度为 8 .5. 设G 是n 阶简单图,且不包含三⾓形,则其边数⼀定不超过24n . ⼆．单项选择题(每题3分，共15分) 学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………⽆……………效……………………座位号图1 图21. 关于彼得森(Petersen)图, 下⾯说法正确的是 ( B )A. 彼得森图是哈密尔顿图;B. 彼得森图是超哈密尔顿图;C. 彼得森图可1-因⼦分解;D. 彼得森图是可平⾯图.2. 下⾯说法正确的是 ( C )A. 有割点的三正则图⼀定没有完美匹配;B. 有割边的三正则图⼀定没有完美匹配;C. 存在哈密尔顿圈的三正则图必能1因⼦分解;D. 正则的哈密尔顿图必能2因⼦分解.3. 关于图的度序列, 下⾯说法正确的是 ( B )A. 任意两个有相同度序列的图都同构;B. 若图G 度弱于图H ，则图G 的边数⼩于等于图H 的边数;C. 若⾮负整数序列12(,,,)n d d d π=满⾜1ni i d =∑为偶数，则它⼀定是图序列;D. 如果图G 所有顶点的度和⼤于或等于图H 所有顶点的度和，则图G 度优于图H.4. 关于图的补图, 下⾯说法错误的是 ( A )A. 若图G 连通，则其补图必连通;B. 若图G 不连通，则其补图必连通;C. 图G 中的⼀个点独⽴集，在其补图中的点导出⼦图必为⼀个团;D. 存在5阶的⾃补图.5. 关于欧拉图, 下⾯说法正确的是 ( D )A. 每个欧拉图有唯⼀的欧拉环游;B. 每个顶点的度均为偶数的图是欧拉图;C. 欧拉图中⼀定没有割点;D. 欧拉图中⼀定没有割边.(三).(10分)若阶为25且边数为62的图G 的每个顶点的度只可能为3，4，5或6，且有两个度为4的顶点，11个度为6的顶点，求G 中5度顶点的个数。