计算机网络(本)2012形考性考核作业1及答案tanlijun.doc

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