第七章网络安全 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 十名学生参加六门课程的考试。由于选修内容不同，考试门数也不一样。下表给出了每个学生应参加考试的课程（打⊙的）： 学生考试课程 A B C D E F 1 ⊙⊙⊙ 2 ⊙⊙ 3 ⊙⊙ 4⊙⊙⊙ 5⊙⊙⊙ 6 ⊙⊙ 7⊙⊙⊙ 8 ⊙⊙ 9 ⊙⊙⊙ 10⊙⊙⊙ 规定考试在三天内结束，每天上下午各安排一门。学生希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考试日程表。 参考答案 把同一个研究生参加的考试课程用边连接，得图如下。由图看出，课程A只能同E排在一天，B同C排在一天，D同F在一天。再据题意，考试日程表只能是下表： B E 上午下午 第一天 A E A F 第二天 C B 第三天 D F D C 2 求下图的最小生成树和最大生成树：
V6 3 需 参考答案 将每小块稻田及水源地各用一个点表示，连接这些点的树图的边数即为至少要挖开的堤埂数。（至少挖开11条） 4. 请用标号法求下图所示的最短路问题，弧上数字为距离：
参考答案 路线为1－2－4－6，距离为9个单位 5 用Dijkstra标号法求下图中始点到各顶点的最短路，弧上数字为距离： v3 3 v5 1 5 4 v1 2 4 v2 2 v4 参考答案 1－2，3，4，5最短路：3*,1*,5*,4* 6最短路问题：某公司使用一种设备，此设备在一定年限内随着时间的推移逐渐损坏。每年购买价格和不同年限的维修使用费如下表所示。假定公司在第一年开始时必须购买一台此设备，请建立此问题的网络图，确定设备更新方案，使维修费和新设备购置费的总数最小。说明解决思路和方法，不必求解。 年份 1 2 3 4 5 价格20 21 23 24 26 使用年限0－1 1－2 2－3 3－4 4－5 费用8 13 19 23 30 参考答案 弧（i，j）的费用或“长度”等于j－i年里的设备维修费加上第i年购买的新设备的价格。例如，弧（1，4）的费用为（8＋13＋19）＋20＝60
计算机网络课后题答案第七章 第七章网络安全 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)流量分
第5章习题参考答案 1．请在括号填入适当答案。在CPU中： (1)保存当前正在执行的指令的寄存器是（ IR ）； (2)保存当前正在执行的指令地址的寄存器是（ AR ） (3)算术逻辑运算结果通常放在（ DR ）和（通用寄存器）。 2．参见图5.15的数据通路。画出存数指令“STO Rl，(R2)”的指令周期流程图，其含义是将寄存器Rl的容传送至(R2)为地址的主存单元中。标出各微操作信号序列。 解： STO R1, (R2)的指令流程图及微操作信号序列如下：
STO R1, (R2) R/W=R DR O, G, IR i R2O, G, AR i R1O, G, DR i R/W=W 3．参见图5.15的数据通路，画出取数指令“LAD (R3)，R0”的指令周期流程图，其含义是将(R3)为地址主存单元的容取至寄存器R2中，标出各微操作控制信号序列。 解： LAD R3, (R0)的指令流程图及为操作信号序列如下：
PC O , G, AR i R/W=R DR O , G, IR i R 3O , G, AR i DR O , G, R 0i R/W=R LAD (R3), R0 4．假设主脉冲源频率为10MHz ，要求产生5个等间隔的节拍脉冲，试画出时序产生器的逻辑图。 解：
5．如果在一个CPU 周期中要产生3个节拍脉冲；T l ＝200ns ，T 2=400ns ，T 3=200ns ，试画出时序产生器逻辑图。 解：取节拍脉冲T l 、T 2、T 3的宽度为时钟周期或者是时钟周期的倍数即可。所以取时钟源提供的时钟周期为200ns ，即，其频率为5MHz.；由于要输出3个节拍脉冲信号，而T 3的宽度为2个时钟周期，也就是一个节拍电位的时间是4个时钟周期，所以除了C 4外，还需要3个触发器——C l 、C 2、C 3；并令 211C C T *=；321C C T *=；313C C T =，由此可画出逻辑电路图如下：