第七章网络安全 7-01 计算机网络都面临哪几种威胁？主动攻击和被动攻击的区别是什么？对于计算机网 络的安全措施都有哪些？ 答：计算机网络面临以下的四种威胁：截获（），中断()，篡改(),伪造（）。 网络安全的威胁可以分为两大类：即被动攻击和主动攻击。 主动攻击是指攻击者对某个连接中通过的进行各种处理。如有选择地更改、删除、 延迟这些。甚至还可将合成的或伪造的送入到一个连接中去。主动攻击又可进一步 划分为三种，即更改报文流；拒绝报文服务；伪造连接初始化。被动攻击是指观察和分析某一个协议数据单元而不干扰信息流。即使这些数据对 攻击者来说是不易理解的，它也可通过观察的协议控制信息部分，了解正在通信的协议 实体的地址和身份，研究的长度和传输的频度，以便了解所交换的数据的性质。这种被 动攻击又称为通信量分析。 还有一种特殊的主动攻击就是恶意程序的攻击。恶意程序种类繁多，对网络安全威胁 较大的主要有以下几种：计算机病毒；计算机蠕虫；特洛伊木马；
逻辑炸弹。 对付被动攻击可采用各种数据加密动技术，而对付主动攻击，则需加密技术与适当的 鉴别技术结合。 7-02 试解释以下名词：（1）重放攻击；（2）拒绝服务；（3）访问控制；（4）流量分析； （5）恶意程序。 答：（1）重放攻击：所谓重放攻击（）就是攻击者发送一个目的主机已接收 过的包，来达到欺骗系统的目的，主要用于身份认证过程。（2）拒绝服务：( )指攻击者向因特网上的服务器不停地发送大量 分组，使因特网或服务器无法提供正常服务。 （3）访问控制：（）也叫做存取控制或接入控制。必须对接入网络的权限 加以控制，并规定每个用户的接入权限。 （4）流量分析：通过观察的协议控制信息部分，了解正在通信的协议实体的地址和 身份，研究的长度和传输的频度，以便了解所交换的数据的某种性质。这种被动攻击又 称为流量分析（）。 （5）恶意程序：恶意程序（）通常是指带有攻击意图所编写的
《运筹学》第八章图与网络分析习题 1.思考题 (１)解释下列名词，并说明相互之间的区别与联系：①顶点，相邻，关联边； ②环，多重边，简单图；③链，初等链；④圈，初等圈，简单拳；⑤ 回 路，初等路；⑥节点的次，悬挂点，孤立点；⑦）连通图，连同分图， 支 撑子图；⑧有向图，基础图，赋权图。⑨子图，部分图，真子图． (２)通常用记号Ｇ＝（Ｖ，Ｅ）表示一个图，解释Ｖ及Ｅ的涵义及这个表达式 的涵义． (３)通常用记号Ｄ＝（Ｖ，Ａ）表示一个有向图，解释Ｖ及Ａ的涵义及这个表 达式的涵义． (４) 图论中的图与一般几何图形的主要区别是什么？ (５) 试述树与图的区别与联系． (６) 试述 求最短路问题的Ｄijkstra 算法的基本思想及其计算步骤． (７) 试述寻求最大流的标号法的步骤与方法． (８) 简述最小费用最大流的概念及其求解的基本思想和方法． (９) 通常用记号Ｎ＝（Ｖ，Ａ，Ｃ）表示一个网络，试解释这个表达式的涵义． (10) 在最大流问题中，为什么当存在增广链时，可行流不是最大流？ (11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。 2.判断下列说法是否正确 (1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何 形状无关。 (2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 (3) 如果一个图G 从V 1到各点的最短路是唯一的，则连接V 1到各点的最短路，再去掉重 复边，得到的图即为最小支撑树。 (4 )图G 的最小支撑树中从V 1到V n 的通路一定是图G 从V 1到V n 的最短路。 (5) {f ij =0}总是最大流问题的一个可行流。 (6 )无孤立点的图一定是连通图。 (7) 图中任意两点之间都有一条简单链，则该图是一棵树。 (8) 求网络最大流的问题总可以归结为求解一个线性规划问题。 (9)在图中求一点Ｖ１到另一点Ｖn 的最短路问题总可以归结为一个整数规划问题 (10) 图G 中的一个点V 1总可以看成是G 的一个子图。 3.证明：在人数超过2的人群中，总有两个人在这群人中恰有相同的朋友数。 4.已知九个人921,,,v v v ，1v 和两个人握过手，32,v v 各和四个人握过手， 7654,,,v v v v 各和五个人握过手，98,v v 各和六个人握过手。证明这九个人中，一定可 以找出三个人互相握过手。 5．用破圈法和避圈法求下图的部分树 C7 V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9 C 1 C 2 C 3 C 4 C 5 C 6 C 8 C 9 C 10 C 11 C 12 C 13 C 14
第七章图与网络分析 一、单项选择题 1．关于可行流，以下叙述不正确的是（） A.可行流的流量大于零而小于容量限制条件 B．在网络的任一中间点，可行流满足流人量=流出量 C．各条有向边上的流量均为零的流是一个可行流 D．可行流的流量小于或等于容量限制条件而大于或等于零 2．关于最小树，以下叙述（）正确。 A.最小树是一个网络中连通所有点而边数最少的图 B．最小树是一个网络中连通所有的点，而权数最少的图 C．一个网络中的最大权边必不包含在其最小树内 D．一个网络的最小树一般是唯一的。 3．最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（） A. 边缘结点 B.未接结点 C.已接结点 D.最重要结点 4.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（） A.连接的总长度最大 B.连接的总长度最小 C.连接的总长度为0 D.计算总长度5．最小树问题就是在网络图中，找出若干条边，连接（） A.相邻结点 B.头尾结点 C.部分结点 D.所有结点 6．任一树中的边数和它的点数之间的关系是（） A.边数等于点数减1 B.边数等于点数加1 C.点数等于边数减1 D.点数等于边数加1 7．最大流问题中，对于一个可行流，V i V j有向边上的流量f ij必须满足的条件之一是（） A.0≤f ij≥c ij B.0≥f ij≤c ij C. 0≤f ij≤c ij D. 0≥f ij≥c ij 8.一个连通图中的最小树可能不唯一，其权（） A.是唯一确定的 B.可能不唯一 C.可能不存在 D.一定有多个 二、多项选择题 1.关于图论中图的概念，以下叙述正确的的（） A.图中的边可以是有向边，也可以是无向边 B.图中的各条边上可以标注权 C.结点数等于边数的连通图必含圈 D.结点数等于边数的图必连通 E.图中的边只能是有向边 2.关于最短路，以下叙述不正确的有（） A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的 B．从起点出发到终点的最短路是唯一的 C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上 E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上 3.关于增广链，以下叙述正确的有（） A．增广链是一条从发点到收点的有向路，这条路上各条边的方向必一致 B．增广链是一条从发点到收点的有向路，这条路上各条边的方向可不一致 C．增广链上与发收点方向一致的边必是非饱和边，方向相反的边必是流量大于零的边 D．增广链上与发收点方向一致的边必是流量小于容量的边，方向相反的边必是流量等于零的边 E．增广链上与发收点方向一致的边必是流量为零的边，方向相反边必是流量大于零的边4.在下图中，根据（a）生成的支撑树有（）
第二节欧拉图和哈密尔顿回路 一、欧拉图 欧拉（Euler）在1736年发表的关于图论方面的第一篇论文，解决了一个著名问题，称为哥尼斯堡七桥问题，从而使他成为图论的创始人。问题是这样的：十八世纪的德国有座哥尼斯堡城，在流贯全城的普格尔河两岩和河中两个岛之间架设了七座桥，如图6.10（a）所示。当时那里的居民热衷于这样一个游戏，即一个散步者能否从任一陆地出发，走过每座桥一次且仅走过一次，最后回到原地。问题乍看起来很简单，但当时谁也不明白为什么没有人能够成功。 为了弄清这个问题，欧拉将每一块陆地用一顶点表示，每一座桥用连接相应的两个顶点的连线（即边）来代替，从而得到一个“图”（图 6.10（b））。这个“图”使问题变得简洁明了。直观上不难发现，为了能回到原来的陆地，要求与每个顶点（陆地）相关联的边数是偶数，这样才能保证从一条边出去，从另一条边回来。由于在图6.10（b）中，与四个顶点相连的边数都是奇数，因而不可能 自任一顶点出发过每条边一次且仅一次而回到原地。 （a）图6.10（b）欧拉并不限于处理这个特殊事例，他推广了这个问题，提出并证明了下述定理。 定义1 在连通无向图G中，若存在经过每条边恰好一次的一个圈或一条链，就称此圈或链为欧拉圈或欧拉链。或图G含一条欧拉圈，则称它为欧拉图。 显然，欧拉圈或欧拉链都可“一笔画出”；反之，若一个图能一笔画出，则它必然是欧拉圈或欧拉链。 定理1连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。 事实上，若G是欧拉图，C是其欧拉圈，则由定义，C包含G的所有边，由于图连通，故亦包含所有顶点。C是任一中间顶点每出现一次，必与两条不同的边相关联，另因C的起点也是终点，故所有顶点都是偶次顶点。 定理2 连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。 上述定理提供了判断一笔画问题的准则：若连通无向图G无奇次顶点，则可由任一点起一笔画成并回到起点；若有两个奇次顶点，则由一奇次顶点起到另一奇次顶点终可一笔画成。为能将一个图一笔画下去，当去掉已画出部分时，乘下的部分不应成为不连通图。 二、哈密尔顿回路 1859年英国数学家哈密尔顿（Hamilton）提出了一种名为周游世界的游戏。
《运筹学》习题答案 一、单选题 1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ ）B A.任意网络 B.无回路有向网络 C.混合网络 D.容量网络 2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（ ）B A.非线性问题的线性化技巧 B.静态问题的动态处理 C.引入虚拟产地或者销地 D.引入人工变量 3.静态问题的动态处理最常用的方法是？B A.非线性问题的线性化技巧 B.人为的引入时段 C.引入虚拟产地或者销地 D.网络建模 4.串联系统可靠性问题动态规划模型的特点是（ ）D A.状态变量的选取 B.决策变量的选取 C.有虚拟产地或者销地 D.目标函数取乘积形式 5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。C A.降低的 B .不增不减的 C .增加的 D .难以估计的 6.最小枝权树算法是从已接接点出发，把( )的接点连接上C A.最远 B.较远 C.最近 D.较近 7.在箭线式网络固中，( )的说法是错误的。D A.结点不占用时间也不消耗资源 B.结点表示前接活动的完成和后续活动的开始 C.箭线代表活动 D.结点的最早出现时间和最迟出现时间是同一个时间 8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。C A.1200 B.1400 C.1300 D.1700 9.在求最短路线问题中，已知起点到A ，B ，C 三相邻结点的距离分别为15km ，20km,25km ，则（ ）。D A.最短路线—定通过A 点 B.最短路线一定通过B 点 C.最短路线一定通过C 点 D.不能判断最短路线通过哪一点 10.在一棵树中，如果在某两点间加上条边，则图一定( )A A.存在一个圈 B.存在两个圈 C .存在三个圈 D .不含圈 11.网络图关键线路的长度( )工程完工期。C A.大于 B.小于 C.等于 D.不一定等于 600 700 300 500 400 锅炉房 1 2 3
计算机网络课后题答案第七章 第七章网络安全 7-01 计算机网络都面临哪几种威胁？主动攻击和被动攻击的区别是什么？对于计算机网 络的安全措施都有哪些？ 答：计算机网络面临以下的四种威胁：截获( interception )，中断 (interruption) ，篡改 (modification), 伪造( fabrication )。 网络安全的威胁可以分为两大类：即被动攻击和主 动攻击。 主动攻击是指攻击者对某个连接中通过的 PDU 进行各种处理。如有选择地更改、 删除、延迟这些PDU 。甚至还可将合成的或伪造的 PDU 送入到一个连接中去。主动攻击 又可进一步划分为三种，即更改报文流；拒绝报文服务；伪造连接初始化。 被动攻击是指观察和分析某一个协议数据单元 PDU 而不干扰信息流。即使这些数据对攻 击者来说是不易理解的，它也可通过观察 PDU 的协议控制信息部分，了解正在通信的协 议实体的地址和身份，研究 PDU 的长度和传输的频度，以便了解所交换的数据的性质。 这种被动攻击又称为通信量分析。 还有一种特殊的主动攻击就是恶意程序的攻击。恶意程序种类繁多，对网络安全威胁较大 的主要有以下几种：计算机病毒；计算机蠕虫；特洛伊木马； 对付被动攻击可采用各种数据加密动技术，而对付主动攻击， 技术结合。 7-02 试解释以下名词：( 1)重放攻击；( 2)拒绝服务； 析；( 5) 恶意程序。 ( 1)重放攻击：所谓重放攻击( replay attack )就是攻击者发送一个目的主机已接收过 的包，来达到欺骗系统的目的，主要用于身份认证过程。 (2)拒绝服务：DoS(De nial of Service)指攻击者向因特网上的服务器不停地发送大量分 组，使因特网或服务器无法提供正常服务。 (3)访问控制：(access control )也叫做存取控制或接入控制。必须对接入网络的权限 加以控制，并规定每个用户的接入权限。 ( 4)流量分析：通过观察 PDU 的协议控制信息部分，了解正在通信的协议实体的地址和 身份，研究 PDU 的长度和传输的频度，以便了解所交换的数据的某种性质。这种被动攻 击又称为流量分析( traffic analysis )。 5)恶意程序：恶意程序( rogue program )通常是指带有攻击意图所编写的一段程序。 7-03 为什么说，计算机网络的安全不仅仅局限于保密性？试举例说明，仅具有保密性的 计算机网络不一定是安全的。 逻辑炸弹。 则需加密技术与适当的鉴别 3)访问控制；( 4)流量分