1、1离散数学 2012 春学期图论部分综合练习辅导大家好！本学期的第二次教学辅导活动现在开始，本次活动主要是针对第二单元图论的重点学习内容进行辅导，方式同样是通过讲解一些典型的综合练习作业题目，帮助大家进一步理解和掌握图论的基本概念和方法图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等本次综合练习主要是复习这一单元的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题这样的安排也是为了让同学
2、们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习01 任务 A_0009试卷总分：100 测试时间：- 单项选择题 判断题 一、单项选择题（共 20 道试题，共 60 分。）1. （ ）和数据通信是计算机网络最基本的两大功能。 A. 资源共享B. 病毒管理C. 用户管理D. 站点管理满分：3 分2. 计算机网络系统是由通信子网和（ ）子网组成的。 A. 资源B. 数字C. 信息D. 模拟满分：3 分3. 网络资源子网负责（ ）。 A. 数据通信B. 数字认证机制C. 信息处理D. 路由满分：3 分24. 通信子网可分为点点通信线路通信子网与( ) 两类。 A. 城域网B. 广播信道通
3、信子网C. 无线网D. 星型网络满分：3 分5. 通常按网络覆盖的地理范围分类，可分为：局域网、（ ）和广域网三种。 A. 城域网B. 有线网C. 无线网D. 星型网络满分：3 分6. （ ）是指选用双绞线、同轴电缆或光纤作为传输介质的计算机网络。 A. 城域网B. 有线网C. 无线网D. 星型网络满分：3 分7. （ ）是面向连接的协议，用三次握手和滑动窗口机制来保证传输的可靠性和进行流量控制。 A. TCPB. IPC. UDPD. FTP满分：3 分8. （ ）协议规定网际层数据分组的格式。 A. TCPB. IPC. UDPD. FTP满分：3 分9. 一个功能完备的计算机网络需要指定
4、一套复杂的协议集。对于复杂的计算机网络协议来说，最好的组织方式是（ ）。 A. 连续地址编码模型B. 层次结构模型C. 分布式进程通信模型D. 混合结构模型满分：3 分310. 在 OSI 参考模型中，网络层的主要功能是( )。 A. 组织两个会话进程之间的通信，并管理数据的交换B. 数据格式变换、数据加密与解密、数据压缩与恢复C. 路由选择、拥塞控制与网络互连D. 确定进程之间通信的性质，以满足用户的需要满分：3 分11. 用于将 MAC 地址转换成（ ）地址的协议一般为 RARP 协议。 A. 实际B. 硬件C. TCPD. IP满分：3 分12. （ ）是计算机网络层次模型中每一层中用于
5、实现该层功能的活动元素，包括该层上实际存在的所有硬件与软件，如终端、电子邮件系统、应用程序、进程等。 A. 实体B. 连接C. 数据报D. 路由满分：3 分13. 网络协议由语法、（ ）和语序三大要素构成。 A. 实体B. 语义C. 数据报D. 路由满分：3 分14. 通信系统传输的信号一般有（ ）信号和模拟信号两种表示方式。 A. 数字B. 信道C. 数据D. 双向满分：3 分15. 数据通信按照信号传送方向和时间的关系，信道的通信方式可以分为三种：单工、（ ）和全双工。 A. 数字传输B. 半双工C. 信道传输D. 模拟传输满分：3 分416. 在单工通信方式中，信号只能向（ ）方向传输。
6、 A. 两个B. 一个C. 三个D. 四个满分：3 分17. 常用的数据交换技术有两大类：（ ）和存储转发交换。 A. 频率交换B. 信息交换C. 数字交换D. 电路交换满分：3 分18. 信道的多路复用技术有（ ）、时分多路复用、波分多路复用和码分多路复用。 A. 频分多路复用B. 信息交换C. 数字交换D. 电路交换满分：3 分19. 全双工通信支持下列（ ）数据流。 A. 单一方向B. 多个方向C. 两个方向且同时D. 两个方向，非同时满分：3 分20. 在半双工通信方式中，信号可以双向传送，但必须交替进行，在任一时刻只能向一个方向传送。例如：（ ）。 A. 对讲机B. 广播C. 以太网
7、通信D. 局域网满分：3 分01 任务 A_0009试卷总分：100 测试时间：- 单项选择题 判断题 二、判断题（共 20 道试题，共 40 分。）51. 资源共享和用户管理是计算机网络最基本的两大功能。 A. 错误B. 正确满分：2 分2. 计算机网络系统是由通信子网和资源子网组成的。 A. 错误B. 正确满分：2 分3. 资源子网负责信息处理。 A. 错误B. 正确满分：2 分4. 通信子网可分为点点通信线路通信子网与广播信道通信子网两类。 A. 错误B. 正确满分：2 分5. 局域网覆盖的地理范围从数百公里至数千公里，甚至上万公里。可以是一个地区或一个国家，甚至是世界几大洲，故又称远程
8、网。 A. 错误B. 正确满分：2 分6. 城域网是指选用双绞线、同轴电缆或光纤作为传输介质的计算机网络。 A. 错误B. 正确满分：2 分7. UDP 是面向连接的协议，用三次握手和滑动窗口机制来保证传输的可靠性和进行流量控制。A. 错误B. 正确满分：2 分8. 路由是计算机网络层次模型中每一层中用于实现该层功能的活动元素，包括该层上实际存在的所有硬件与软件，如终端、电子邮件系统、应用程序、进程等。 A. 错误B. 正确满分：2 分9. 网络协议由语法、实体和语序三大要素构成。 A. 错误B. 正确6满分：2 分10. 数据链路层是 OSI 参考模型的最低层，它直接面向原始比特流的传输。
9、A. 错误B. 正确满分：2 分11. 物理层负责建立相邻结点之间的数据链路，提供节点间可靠数据传输。 A. 错误B. 正确满分：2 分12. 数据链路层是 OSI 参考模型中最靠近用户的一层，负责为用户的应用程序提供网络服务。 A. 错误B. 正确满分：2 分13. TCP/IP 协议简化了层次设备，由下而上分别为网络接口层、网络层、表示层、应用层。 A. 错误B. 正确满分：2 分14. 通信系统传输的信号一般有模拟信号和双向信号两种表示方式。 A. 错误B. 正确满分：2 分15. 数据通信按照信号传送方向和时间的关系，信道的通信方式可以分为三种：单工、半单工和双工。 A. 错误B. 正
10、确满分：2 分16. 在单工通信方式中，信号只能向两个方向传输。 A. 错误B. 正确满分：2 分17. 在全双工通信方式中，信号可以双向传送数据，但不能同时传送。 A. 错误B. 正确满分：2 分18. 在半双工通信方式中，信号可以双向传送，但必须交替进行，在任一时刻只能向一个方向传送。例如：对讲机。 A. 错误B. 正确7满分：2 分19. 通信线路的连接可以有多种形式，对于计算机局域网络，主要有点到点和多点两种连接方式。 A. 错误B. 正确满分：2 分20. 在信道中数据的传输方式有串行通信和并行通信两种。通常，并行通信用于较远距离的数据传输，而串行通信则用于较近距离的数据传输。 A.
11、 错误B. 正确满分：2 分单项选择题 判断题 下面是本学期第 4，5 次形考作业中的部分题目发信人: 1132001200945标 题: 11 春计本尤俊 形成性考核作业 2发帖时间: 电大在线 BBS (11-17 20:41:17) 一、选择题1（ A ）是面向连接的协议，用三次握手和滑动窗口机制来保证传输的可靠性和进行流量控制。ATCP BIP CUDP DFTP2（ B ）协议规定网际层数据分组的格式。ATCP BIP CUDP DFTP3一个功能完备的计算机网络需要指定一套复杂的协议集。对于复杂的计算机网络协议来说，最好的组织方式是（ B ）。A连续地址编码模型 B层次结构模型C分
12、布式进程通信模型 D混合结构模型4在 ISO/OSI 参考模型中，网络层的主要功能是( C )。A组织两个会话进程之间的通信，并管理数据的交换B数据格式变换、数据加密与解密、数据压缩与恢复C路由选择、拥塞控制与网络互连D确定进程之间通信的性质，以满足用户的需要5用于将 MAC 地址转换成 IP 地址的协议一般为( B )。P29AARP BRARP CTCP DIP6（ A ）是计算机网络层次模型中每一层中用于实现该层功能的活动元素，包括该层上实际存在的所有硬件与软件，如终端、电子邮件系统、应用程序、进程等。看教材 p19A实体 B连接 C数据报 D路由7网络协议由语法、（ B ）和语序三大要
13、素构成。 P20A实体 B语义 C数据报 D路由8（ D ）是 OSI 参考模型的最低层，它直接面向原始比特流的传输。A表示层 B网络层 C数据链路层 D物理层9（ C ）负责建立相邻结点之间的数据链路，提供节点间可靠数据传输。A表示层 B网络层 C数据链路层 D物理层10（ A ）是 OSI 参考模型中最靠近用户的一层，负责为用户的应用程序提供网络服务。A应用层 B网络层 C数据链路层 D物理层11( B )协议，它源于 ARPANET 网，现在已经成为 Internet 互联网的通信协议。APPP BTCP/IP CDNS DFTP12TCP/IP 协议简化了层次设备，由下而上分别为网络接
14、口层、网络层、（ D ）、应用层。8A会话层 B表示层 C数据链路层 D传输层二、填空题1（ TCP/IP ）参考模型层次结构中，没有表示层和会话层。2对等实体之间交换数据或通信时所必须遵守的规则或标准的集合称为（ 协议 ）。P193. 国际标准化组织在 1977 年建立了一个分委员会来专门研究网络体系结构与网络协议的标准化问题，提出了（ 开放系统互联参考模型 osi ）。P214面向连接的服务具有连接建立、（ 数据传输 &nb一、单项选择题单项选择题主要是第 4 次形考作业的部分题目第 4 次作业同样也是由 10 个单项选择题组成，每小题 10 分，满分 100分在每次作业在关闭之前，允许大
15、家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目1设图 G，v V，则下列结论成立的是 ( ) Adeg(v )=2E B deg(v)=E C DV2)deg( Vdeg该题主要是检查大家对握手定理掌握的情况复习握手定理：定理 3.1.1 设 G 是一个图，其结点集合为 V，边集合为 E，则Vv|2)deg(也就是说，无向图 G 的结点的度数之和等于边数的两倍 正确答案：C2设无向图 G 的邻接矩阵为，0101则 G 的边数为( )A6 B5 C4 D3主要是检查对邻接矩阵的概念理解是否到位大家要复习
16、邻接矩阵的定义，要记住当给定的简单图是无向图时，邻接矩阵为对称的即当结点 vi 与 vj 相邻时，结点 vj 与 vi 也相邻，所以连接结点 vi 与 vj 的一条边在邻接矩阵的第 i 行第j 列处和第 j 行第 i 列处各有一个 1，题中给出的邻接矩阵中共有 10 个 1，故有102=5 条边正确答案：B3如右图所示，以下说法正确的是 ( ) A(a, e)是割边 ab cde9B( a, e)是边割集C( a, e) ,(b, c)是边割集 D(d, e)是边割集先复习割边、边割集的定义：定义 3.2.9 设无向图 G=为连通图，若有边集 E1E，使图 G 删除了E1 的所有边后，所得的子
17、图是不连通图，而删除了 E1 的任何真子集后，所得的子图是连通图，则称 E1 是 G 的一个边割集若某个边构成一个边割集，则称该边为割边（或桥）因为删除答案 A 或 B 或 C 中的边后，得到的图是还是连通图，因此答案A、B、 C 是错误的正确答案：D注：如果该题只给出图的结点和边，没有图示，大家也应该会做如：若图 G=，其中 V= a, b, c, d, e ，E= (a, b), (a, c) , (a, e) , (b, c) , (b, e ) , (c, e) , (e, d)，则该图中的割边是什么？4设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是( )A（a）
18、是强连通的 B（ b）是强连通的C（ c）是强连通的 D（d）是强连通的我们先复习强连通的概念：定义3.2.5 在简单有向图中，若在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G是单向（侧）连通的；若在任何结点偶对中，两结点对互相可达，则称图 G 是强连通的正确答案：A问：上面的图中，哪个仅为弱连通的？请大家要复习“弱连通”的概念5设完全图 K 有 n 个结点(n2)，m 条边，当（ ）时，K 中存在欧拉n回路Am 为奇数 Bn 为偶数 Cn 为奇数 Dm 为偶数我们先复习完全图的概念：定义 3.1.6 简单图 G=中，若每一对结点间都有边相连，则称该图为完全图有 n 个结点的无向
19、完全图记为 Kn由定义可知，无向完全图 Kn 中的任一结点 v 到其它结点都有一条边，共有n-1 条边，即每个结点的度数是 n-1，当 n 为奇数时，n-1 为偶数由定理 4.1.1 的推论10一个无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的结点度数都是偶数所以，正确答案应该是 C提示：前面提到 n 阶无向完全图 Kn 的每个结点的度数是 n-1，现在要问：无向完全图 Kn 的边数是多少？6设 G 是连通平面图，有 v 个结点，e 条边，r 个面，则 r= ( )Aev2 Bv e2 Cev 2 De v2本题主要检查大家是否掌握了欧拉定理定理4.3.2（欧拉定理） 设连通平面图G的
20、结点数为 v，边数为e，面数为r，则欧拉公式v-e+r =2成立由欧拉公式 v-e+r =2，得到 r = e- v+2所以，答案 A 是正确的问：如果连通平面图 G 有 4 个结点，7 条边，那么图 G 有几个面？7无向简单图 G 是棵树，当且仅当( )AG 连通且边数比结点数少 1 BG 连通且结点数比边数少 1CG 的边数比结点数少 1 DG 中没有回路可以运用教材中的定理 5.1.1，可以作出正确选择因为定理 5.1.1 中给出的图 T 为树的等价定义之一是图 T 连通且 e=v-1，其中 e 是边数，v 是结点数也就是说：无向简单图 G 是棵树，当且仅当 G 连通且边数比结点数少 1
21、正确答案：A注：由上面的树的等价定义可知，结点数 v 与边数 e 满足 e=v-1 关系的无向连通图就是树问当树 T 有 6 个结点，那么它有多少条边？8已知一棵无向树 T 中有 8 个结点，4 度，3 度，2 度的分支点各一个，T的树叶数为（ ）A8 B5 C4 D3设无向树 T 的树叶数为 x，因为树叶是度数为 1 的结点那么，由定理 3.1.1（握手定理） 设 G 是一个图，其结点集合为 V，边集合为 E，则，VvE|2)deg(得 4+3+2+x=2（8-1），即 x=5正确答案：B下面的内容主要是第 5 次形考作业的部分题目二、填空题1已知图 G 中有 1 个 1 度结点，2 个 2 度结点， 3 个 3 度结点，4 个 4 度结点，则 G 的边数是 也是检查大家对握手定理掌握的情况
