最新匹配网络习题解

习题1：求1uH 电感与5欧电阻串联电路在10MHz 、100MHz 、1GHz 下的并联等效电路（分别计算出相应的元件值）。

解：222s s ps 22s sp 2s p s s p(1)1(1)s s R X R Q R R R X X X X Q R X Q R X ⎧+==+⎪⎪⎨+⎪==+⎪⎩==习题2：某接收机输入回路的简化电路如图所示。

已知C 1=5pF ，C 2=15pF ，Ｒs =75 Ω，ＲL =300 Ω。

为了使电路匹配，即负载ＲL 等效到ＬＣ回路输入端的电阻Ｒ′L ＝Ｒs ， 线圈初、次级匝数比Ｎ1／Ｎ2应该是多少？ 解：电容接入系数p1为：480025.0300/'25.015552112211====+=+=p RL RL c c c p电感接入系数p2为：1429.0)21/(22/112/12/1211125.04800/7522=-=+=+===p p N N N N N N N N N p p习题3：试设计一个г型匹配网络，使100Ω的电阻性负载在100MHz 时转换为50Ω。

（1）画出匹配网络的电路结构； （2）计算匹配网络的元件值；解：（1）因须将阻抗从大变为小，故电路结构如X1R=100Rin=50图。

其中X1、X2为性质相反的电抗元件。

将X2和R 变为串联结构，则： 22'50100(1)5012210022'50(11/)12'50R Q R Q X X X X Q X X ==+=====+==● 若X1＝50，则X2＝－100，有：150/(2)50/(21006)7.968()79.6()12 1.5911()15.9()(2)100L f e e H nH C e F pF f πππ===-===-= ● 若X1＝－50，则X2＝100，有：11 3.1811()31.8()(2)502100/(2)100/(21006) 1.597()159()C e F pF f L f e e H nH πππ==-====-=X1X2'R ’=50Rin=50。

第四章网络层1.网络层向上提供的服务有哪两种？是比较其优缺点。

网络层向运输层提供“面向连接”虚电路（Virtual Circuit）服务或“无连接”数据报服务前者预约了双方通信所需的一切网络资源。

优点是能提供服务质量的承诺。

即所传送的分组不出错、丢失、重复和失序（不按序列到达终点），也保证分组传送的时限，缺点是路由器复杂，网络成本高；后者无网络资源障碍，尽力而为，优缺点与前者互易2.网络互连有何实际意义？进行网络互连时，有哪些共同的问题需要解决？网络互联可扩大用户共享资源范围和更大的通信区域进行网络互连时，需要解决共同的问题有：不同的寻址方案不同的最大分组长度不同的网络接入机制不同的超时控制不同的差错恢复方法不同的状态报告方法不同的路由选择技术不同的用户接入控制不同的服务（面向连接服务和无连接服务）不同的管理与控制方式3.作为中间设备，转发器、网桥、路由器和网关有何区别？中间设备又称为中间系统或中继(relay)系统。

物理层中继系统：转发器(repeater)。

数据链路层中继系统：网桥或桥接器(bridge)。

网络层中继系统：路由器(router)。

网桥和路由器的混合物：桥路器(brouter)。

网络层以上的中继系统：网关(gateway)。

4.试简单说明下列协议的作用：IP、ARP、RARP和ICMP。

IP协议：实现网络互连。

使参与互连的性能各异的网络从用户看起来好像是一个统一的网络。

网际协议IP是TCP/IP体系中两个最主要的协议之一，与IP协议配套使用的还有四个协议。

ARP协议：是解决同一个局域网上的主机或路由器的IP地址和硬件地址的映射问题。

RARP：是解决同一个局域网上的主机或路由器的硬件地址和IP地址的映射问题。

ICMP：提供差错报告和询问报文，以提高IP数据交付成功的机会因特网组管理协议IGMP：用于探寻、转发本局域网内的组成员关系。

5.IP地址分为几类？各如何表示？IP地址的主要特点是什么？分为ABCDE 5类;每一类地址都由两个固定长度的字段组成，其中一个字段是网络号net-id，它标志主机（或路由器）所连接到的网络，而另一个字段则是主机号host-id，它标志该主机（或路由器）。

时间复杂度：最大匹配算法的时间复杂度 较高，为指数级别，因此在实际应用中受 到限制。
应用场景：最大匹配算法在计算机科学、 运筹学、经济学等领域有广泛的应用， 例如在解决指派问题、工作调度问题等 方面。
匹配的应用场景
计算机科学：匹配算法在计算机科学中广泛应用于图算法、数据结构等领域 物理学：在物理学中，匹配理论用于描述粒子相互作用和量子场论中的现象 经济学：匹配理论在经济学中用于研究市场均衡和劳动力市场匹配等问题 社会学：在社会学中，匹配理论用于研究婚姻匹配、教育匹配和职业匹配等现象
电力网络优化： 在网络中合理 分配电力，降 低能耗并提高 电力系统的稳
定性。
通信网络设计： 优化通信网络 的数据传输， 提高网络的吞 吐量和可靠性。
物流配送：通 过优化物流配 送网络，提高 配送效率并降 低运输成本。
网络流算法的分类
最大流算法：寻找从源点到汇点的最大流量 最小割算法：确定将源点划分为两个子集的最小割点集合 最小费用流算法：在满足容量限制和流量平衡的前提下，寻找最小费用流 最短路径算法：寻找从源点到汇点的最短路径
优化目标：最小化 总流量，使得流量 分配均匀，避免拥 堵和瓶颈
算法实现： Dijkstra算法、 Bellman-Ford算 法等
应用场景：交通网 络、通信网络、电 力网络等
多源多汇问题
定义：多个源点和 多个汇点在网络中 同时进行流量的传 输
优化目标：寻找最 优解，使得总流量 传输成本最低或传 输时间最短
最小割问题的应用：在网络流问题中，最 小割问题被广泛应用于解决流量最大化和 容量限制问题。
最小割问题的求解方法：常见的求解最小 割问题的算法有Kruskal算法和Prim算法。
最小割问题的性质：最小割问题具有NP 难解性质，即目前没有已知的多项式时 间复杂度的算法来求解最小割问题。

4-34 与下列掩码相对应的网络前缀各有多少比特？ （1）192.0.0.0； （2）240.0.0.0； （3）255.224.0.0； （4）255.255.255.252。
答案：点分十进制的地址化成二进制记法，1的个数就是前缀的 个数。 （1）11000 00000，对应的网络前缀是2比特 （2）11110 00000，对应的网络前缀是4比特 （3）11111111 11100 00000000，对应的网络前缀是11比特 （4）11111111 11111111 11111111 11111100，对应的网络前缀 是30比特
6次
当用户A向用户B发送数据时，详细描述A是如何通过网关和ARP协议与B进 行通讯的，包传输过程中源和目的的ip地址以及mac地址是如何变化的。
4-20. 设某路由器建立了如下路由表（这三列分别是目的网络、 子网掩码和下一跳路由器，若直接交付则最后一列表示应当 从哪一个接口转发出去）：
目的网络
子网掩码
答：212=（）2，56=（）2 132=（10000100）2 133=（10000101）2 134=（10000110）2 135=（10000111）2 所以共同的前缀有22位，即11010100 00111000 100001，聚合的 CIDR地址块是：212.56.132.0/22
4-31以下地址中的哪一个和86.32/12匹配？请说明理由。 （1）86.33.224.123；（2）86.79.65.216；（3）86.58.119.74； （4）86.68.206.154。
子网网络号
129.250.1.0 129.250.2.0 129.250.3.0 129.250.4.0 129.250.5.0 129.250.6.0 129.250.7.0 129.250.8.0 129.250.9.0 129.250.10.0 129.250.11.0 129.250.12.0 129.250.13.0 129.250.14.0 129.250.15.0 129.250.16.0

分布参数元件是在主传输线上串联一 段传输线或并联支节构成。在距负载某处 可以并联一段终端短路或终端开路的传输 线，此并联传输线称为支节（或短截线）。
本节讨论用单支节、双支节及四分之 一波长阻抗变换器实现匹配网络的方法， 这种方法可以适用于微带线、带状线、同 轴线及平行双导线，本节画图时用平行双 导线说明匹配网络的结构。
信源与负载之间的共轭匹配，是使传 输线的输入阻抗与信源的内阻互为共轭复 数，此时信源的功率输出为最大。 电路匹配是通过匹配网络实现的。
匹配关系到系统的传输效率、功率容 量和工作稳定性，其重要性主要表现在3个 方面。
（1）从信源到负载实现最大功率传 输。 （2）减小线路反射，目的是减小噪 声干扰，提高信噪比。 （3）传输相同功率时线上电压驻波 系数最小，功率承受能力最大。
第5章 匹配网络
在射频电路的设计中，阻抗匹配是最 重要的概念之一，是电路和系统设计时必 须考虑的重要问题。
在匹配网络的设计中，解析方法很繁 杂，本章只讨论用史密斯圆图的设计方法。 史密斯圆图在射频电路的分析中是一个必 须的工具，尤其在匹配网络的设计中显得 更为重要。
本章首先讨论匹配网络的目的及选择 准则，然后讨论集总参数元件电路的匹配 网络设计、分布参数元件电路的匹配网络 设计和混合参数元件电路的匹配网络设计。
T形匹配网络如图5.11(a)所示，π形匹 配网络如图5.11(b)所示，这里用例题介绍 按预定Qn值设计T形和π形匹配网络的方法。
图5.11 T形和π形匹配网络
图5.12 例5.5用图
图5.13 例5.6用图
5.3 分布参数元件电路的匹配 网络设计
随着工作频率的提高，波长不断减小， 当波长与元器件尺寸或电路尺寸相当时， 可以采用分布参数元件实现匹配网络。

第5章1判断题1-1 TCP/IP是ARPAnet中最早使用的通信协议。

〔×〕1-2 TCP/IP最早应用在ARPAnet中。

〔√〕1-3 由于在TCP协议的传输过程中，传输层需要将从应用层接收到的数据以字节为组成单元划分成多个字节段，然后每个字节段单独进展路由传输，所以TCP是面向字节流的可靠的传输方式。

〔√〕1-4 ARP缓存只能保存主动查询获得的IP和MAC的对应关系，而不会保存以广播形式接收到的IP和MAC的对应关系。

〔×〕1-5 ARP欺骗只会影响计算机，而不会影响交换机和路由器等设备。

〔×〕1-6 DHCP服务器只能给客户端提供IP地址和网关地址，而不能提供DNS的IP地址。

〔×〕1-7 TCP和UDP一样都是面向字节流的数据传输方式。

〔×〕1-8 在使用DNS的网络中，只能使用域名来访问网络，而不能使用IP地址。

〔×〕1-9 DNS缓存中毒是修改了用户端计算机缓存中的解析记录，将域名指向错误的IP地址。

〔×〕1-10 在DNSSEC系统中，只要在DNS服务器之间进展安全认证，而不需要在DNS客户端进展安全认证。

〔×〕2 填空题2-1 在网络接口层，将添加了网络首部的协议数据单元称网络组分组或数据帧。

2-2 用户在通过ADSL拨号方式上网时，IP地址与相关参数是DHCP服务器分配的。

2-3 TCP SYN泛洪攻击属于一种典型的DOS攻击。

2-4 DNS同时调用了TCP和UDP的53端口，其中 UTP 53 端口用于DNS客户端与DNS服务器端的通信，而 TCP 53 端口用于DNS区域之间的数据复制。

3 选择题3-1 下面关于IP协议的描述，不正确的答案是〔 B 〕A. 提供一种“尽力而为〞的服务B. 是一种面向连接的可靠的服务C. 是TCP/IP体系网络层唯一的一个协议D. 由于IP协议的PDU称为分组，所以IP网络也称为分组网络3-2 下面关于ARP工作原理的描述，不正确的答案是〔 C 〕A. 是通过IP地址查询对应的MAC地址B. ARP缓存中的数据是动态更新的C. ARP请求报文可以跨网段传输D. ARPA是通过AMC查询对应的IP地址3-3 ARP欺骗的实质是〔 A 〕A. 提供虚拟的MAC与IP地址的组合B. 让其他计算机知道自己的存在C. 窃取用户在网络中传输的数据D. 扰乱网络的正常运行3-4 在Windows操作系统中，对网关IP和MAC地址进展绑定的操作为〔 C 〕A. ARP –a 192.168.0.1 00-0a-03-aa-5d-ffB. ARP –d 192.168.0.1 00-0a-03-aa-5d-ffC. ARP –s 192.168.0.1 00-0a-03-aa-5d-ffD. ARP –g 192.168.0.1 00-0a-03-aa-5d-ff3-5 无法提供DHCP服务的设备可能是〔 C 〕A. 无线路由器B. 交换机C. 集线器D. 运行Windows 2008操作系统的计算机3-6 DHCP Snooping的功能是〔 B 〕A. 防止ARP欺骗B. 防止DHCP欺骗C. 进展端口与MAC地址的绑定D. 提供基于端口的用户认证3-7 TCP SYN泛洪攻击的原理是利用了〔 A 〕A. TCP三次握手过程B. TCP面向流的工作机制C. TCP数据传输中的窗口技术D. TCP连接终止时的FIN报文3-8 在Windows操作系统中，如果要显示当前TCP和UDP的详细通信情况，可以运行〔 D 〕A. ARP –aB. ipconfig/allC. netstat –nabD. ne -ab3-9 DNS的功能是〔 B 〕A. 建立应用进程与端口之间的对应关系B. 建立IP地址与域名之间的对应关系C. 建立IP地址与MAC地址之间的对应关系D. 建立设备端口与MAC地址之间的对应关系3-10 当用户通过域名访问某一合法时，打开的却是一个不健康的，发生该现象的原因可能是〔 D 〕A. ARP欺骗B. DHCP欺骗C. TCP SYN攻击D. DNS缓存中毒3-11 DNSSEC中并未采用〔 C 〕A.数字签名技术B. 公钥加密技术C. 对称加密技术D. 报文摘要技术第6章1判断题1-1 计算机病毒只会破坏计算机的操作系统，而对其他网络设备不起作用。

习题解答汇编
习题解答汇编
第1章 第2章 第3章 第4章 第5章 第6章 第7章 第8章
高级培训
1
习题解答汇编
第１章
1.1 解：
（1）1—1端短接时，谐振电感
L
1
02C
(2
1 106 )2 100 10 12
253 H
高级培训
2
习题解答汇编
（2）1－1端接时，因为
0
1 CxC Cx C
0L
所以
（提示：可以参考教材中例3.4电路进行修改）
高级培训
40
习题解答汇编
第4章
4.1 解：如题4.1图所示。
（a）
题4.1图
高级培训
（b）
41
习题解答汇编
(c)
题4.1图
高级培训
42
习题解答汇编
4.2 解：（a）不能，不能满足三点式法则。 （b）不能，同上。 （c）能，满足三点式法则。 （d）能，两级反相放大。 （e）不能。若第二级负载C2改为电阻则有可能产生振荡。
高级培训
23
习题解答汇编
2.6 解: (提示:此题可以参照教材图2.2.1画出晶体管共基 极Y参数等效电路,然后再画出放大器等效电路.)
根据条件可以求得:
C C Cob 28pF,
g g P g ob n 2 g L 288S
Au0
n y fb g
17.4
BW g 1.64MHz
高级培训
43
习题解答汇编 4.3 解：（1）可将此电路用共基电路等效,如题4.3图所示。
题4.3图
高级培训
44
习题解答汇编
f0
2
1
2.6MHz

本文所有的习题均来自教师上课布置的题目和书上，答案是一家之言，仅供参考。

第一章计算机概论1.术语解释计算机网络网络拓扑结构局域网城域网广域网通信子网资源子网2.计算机网络的的发展可以划分为几个阶段？每个阶段各有什么特点？3.以一个你所熟悉的因特网应用为例，说明你对计算机网络定义和功能的理解。

4.计算机网络如何分类？请分别举出一个局域网、城域网和广域网的实例，并说明它们之间的区别。

5.何为计算机网络的二级子网结构？请说明它们的功能和组成。

6.常用的计算机网络的拓扑结构有哪几种？各自有何特点？试画出它们的拓扑结构图。

7.计算机网络具有哪些功能？8.目前，计算机网络应用在哪些方面？第二章网络体系结构与网络协议1.解释下列术语网络体系结构服务接口协议实体协议数据单元数据封装数据解封装2.在OSI参考模型中，保证端-端的可靠性是在哪个层次上完成的？CA．数据连路层B．网络层C．传输层D．会话层3.数据的加密和解密属于 OSI 模型的功能。

BA．网络层 B．表示层 C．物理层 D．数据链路层4.O SI 参考模型包括哪 7 层？5.同一台计算机之间相邻层如何通信？6.不同计算机上同等层之间如何通信？7.简述 OSI参考模型各层的功能。

8.简述数据发送方封装的过程。

9.O SI 参考模型中每一层数据单元分别是什么？10.在 TCP/IP协议中各层有哪些主要协议？11.试说明层次、协议、服务和接口的关系12.计算机网络为什么采用层次化的体系结构？13.试比较 TCP/IP 模型和 OSI 模型的异同点。

计算机网络为什么采用层次化的体系结构？【要点提示】采用层次化体系结构的目的是将计算机网络这个庞大的、复杂的问题划分成若干较小的、简单的问题。

通过“分而治之”，解决这些较小的、简单的问题，从而解决计算机网络这个大问题（可以举例加以说明）。

2.81．用生活中的实例说明面向连接的网络服务与无连接的网络服务解析：面向连接的网络服务与无连接的网络服务就相当于生活中的电话系统和普通邮政系统所提供服务。

参考答案习题9.1 定义9.4定义的流和，满足流的三个性质吗？如果满足，请证明，如果不满足，哪一个性质最有可能被违背。

不满足。

给定流网络G =(V , E )，设f 1和f 2为V ×V 到R 上的函数。

定义如下：对所有u ，v ∈V),(),(),)((2121v u f v u f v u f f +=+容量约束性质可能被违背反对称性质：),)(( )),(),(( ),(),( ),(),(),)((2121212121u v f f u v f u v f u v f u v f v u f v u f v u f f +−=+−=−−=+=+流守恒性质： 000 ),(),( )),(),((),)((212121=+=+=+=+∑∑∑∑∈∈∈∈V v V v Vv V v v u f v u f v u f v u f v u f f9.2 亚当教授有两个孩子，不幸地是两个孩子互不喜欢，他们不仅拒绝一同上学，而且甚至不愿意走过对方当天走过的街区。

两个孩子对他们在拐角处交叉的路径并不会产生问题。

幸运地是，教授的房子和学校都是在拐角处，但是他并不确定是否该把他的两个孩子送到同一所学校。

教授有镇上的一份地图。

试说明如何将决定两个孩子是否可以上同一所学校的问题建模为一个最大流问题。

每个拐角设为一个顶点，如果在顶点u 和v 之间有街道，则画边(u ,v )和(v ,u )，每条边的容量设为1。

教授家设为源点，学校设为汇点。

如果存在一条大小为2的流，就可以确定两个孩子可以上同一所学校。

9.3 在图9.2(a)中，通过割}),,{},,,({3142t v v v v s 的流是多少？该割的容量是多少？流量为19，容量：319.4 证明引理9.2。

9.5 证明对任意一对顶点u 和v 、任意的容量函数c 和流f ，有(,)(,)(,)(,)f f c u v c v u c u v c v u +=+),(),(),(),(),(),(u v f u v c v u f v u c u v c v u c f f −+−=+（按照定义）),(),(u v c v u c +=（反对称性质）9.6 给定一个网络),(E V G =，证明G 的最大流总可以被至多由||E 条增广路径所组成的序列找到。

……
Best Pairing k Supervisor %老板编号% with Employee %员工编号%
…… Supervisor %老板编号% with Employee %员工编号%
Data Set 2, Best average difference: %最优平均排名% Best Pairing 1 Supervisor %老板编号% with Employee %员工编号% …… Supervisor %老板编号% with Employee %员工编号%
输出： 对于每一组测试数据，输出一行，包含一个整数，即最少需要花费的价钱。
题解： 最小费用最大流的做法请见费用流题解。KM 算法的建图和最小费用最大流的一 样，写法不同，我用这题做了我的 KM 模板。不得不说，在这道题上，KM 算法 能比 SPFA 费用流跑得快得多了（0ms：125ms）。
POJ3565【基础】
a1+a2+a3.......a1+a2+...ak。求和之后变为 a1*k + a2*(k-1) + a3*(k-2) +……+ ak。这个我想了很久才想清楚，只能说……题目描述得实在是精简（不 相信的话请去看原题……）。 因此，对每个机器，最多可以处理 n 个玩具，所以可以拆成 n 个点，1~n 分别 代表某个玩具在这个机器上倒数第几个被加工的，所以我们对于每个玩具 i， 机器 j 中拆的每个点 k，连接一条 m[i][j]*k 权值的边。 如果是用最小费用最大流的话只要再加上超级源点和超级汇点就可以了。如果 是 KM 算法的话，构图和费用流构图方式一样，只是不需要源点和汇点以及相关 的边。
实际上最优匹配的题目，大多数都可以通过最小费用最大流来解决，因为他们 的条件与要求几乎都是一样的。不过总体上来说，KM 算法 O（N^3）（N 代表点 数，E 代表边数）的稳定性总是要优于费用流的算法的，因为 SPFA 费用流的时 间复杂度不稳定，并且一般在 O（N*E^2）到 O(N^2*E)之间徘徊，除非是稀松 图，否则费用流的效率很难和 KM 算法比肩。因此这次的代码里面我有部分的题 目用了两种做法，有些题目只用了 KM 算法。

第五章练习题答案5.1 网络互连有何实际意义？进行网络互连时，有哪些共同的问题需要解决？答：网络互连使得相互连接的网络中的计算机之间可以进行通信，也就是说从功能上和逻辑上看，这些相互连接的计算机网络组成了一个大型的计算机网络。

网络互连可以使处于不同地理位置的计算机进行通信，方便了信息交流，促成了当今的信息世界。

需要解决的问题有：不同的寻址方案；不同的最大分组长度；不同的网络介入机制；不同的超时控制；不同的差错恢复方法；不同的状态报告方法；不同的路由选择技术；不同的用户接入控制；不同的服务（面向连接服务和无连接服务）；不同的管理与控制方式；等等。

注：网络互连使不同结构的网络、不同类型的机器之间互相连通，实现更大范围和更广泛意义上的资源共享。

5.2 转发器、网桥和路由器都有何区别？答：1）转发器、网桥、路由器、和网关所在的层次不同。

转发器是物理层的中继系统。

网桥是数据链路层的中继系统。

路由器是网络层的中继系统。

在网络层以上的中继系统为网关。

2）当中继系统是转发器或网桥时，一般并不称之为网络互连，因为仍然是一个网络。

路由器其实是一台专用计算机，用来在互连网中进行路由选择。

一般讨论的互连网都是指用路由器进行互连的互连网络。

5.3 试简单说明IP、ARP、RARP和ICMP协议的作用。

答：IP：网际协议，TCP/IP 体系中两个最重要的协议之一，IP 使互连起来的许多计算机网络能够进行通信。

无连接的数据报传输. 数据报路由。

ARP（地址解析协议）实现地址转换，将IP地址映射成物理地址。

RARP（逆向地址解析协议）将物理地址映射成IP 地址。

ICMP：Internet 控制消息协议，进行差错控制和传输控制，减少分组的丢失。

注：ICMP 协议帮助主机完成某些网络参数测试，允许主机或路由器报告差错和提供有关异常情况报告，但它没有办法减少分组丢失，这是高层协议应该完成的事情。

IP 协议只是尽最大可能交付，至于交付是否成功，它自己无法控制。

计算机网络练习题及答案一、填空1、计算机网络按照规模可以分为局域网、城域网和广域网。

3、交换式局域网的核心是交换机，当交换机的端口为100Mbps时，如果该端口是全双工的，那么其带宽是200MBPS 。

4、广域网一般由局域网和城域网组成。

5、网络互联的类型一般可以分成4种，分别是：局域网与局域网互联、局域网与城域网互联、局域网和广域网与局域网互联和局域网和广域网与广域网互联。

6、路由器的路由可以分为静态和动态两类。

7、文件传输使用的FTP协议，远程登陆使用TELNET协议。

8、对于子网IP地址不足的问题，我们通常采用修改子网掩码方法来解决，而对于一些不能分配给DHCP客户机的IP地址，我们可以通过设置排除地址来解决。

9、计算机网络是计算机技术与通信技术相结合的产物。

12、广域网的基本结构可分为资源子网和通信子网两部分。

13、按照信号方向与时间关系，数据通信可分为单工通信、半双工通信和全双工通信三种。

14、差错控制编码通常可分为检错码和纠错码两种。

15、计算机网络中，出现差错的主要原因是噪声，噪声可分为随机热噪声和冲击噪音两类。

16、从目前发展情况来看，局域网可分为共享介质局域网和交换式局域网两类。

17、决定局域网性能的主要技术要素是网络拓扑、传输介质和控制访问三方面。

18、调制解调器中把数字信号转换成模拟信号过程称为调制。

19、网关属于高层网络互连设备。

20、IP地址能够唯一地确定Internet上每台计算机的系统位置。

二、选择1、计算机网络发展过程中，（A ）对计算机网络的形成与发展影响最大。

A、ARPANETB、OCYOPUSC、DATAPACD、Newhall2、目前实际存在与使用的广域网基本都是采用（D ）拓扑。

A、网状B、环型C、星型D、总线型3、计算机网络分为广域网、城域网、局域网，其划分的主要依据是网络的（C ）。

A、拓扑结构B、控制方式C、作用范围D、传输介质4、两台计算机利用电话线路传输数据信号时需要的设备是（A ）A、调制解调器B、网卡C、中继器D、集线器5、（C ）这种数字数据编码方式属于自含时钟编码。

计算机网络典型例题分析解答典型例题分析解答一、填空题1网络层/Network是OSI参考模型中的第三层介于运输/TmsPOEt/T层和数据链路层之间。

1.【解析】网络层在OSI参考模型中位于第三层,它的主要功能是实现两个端系统之间的数据透明传送,具体功能包括路由选择、阻塞控制和网际互连等。

【答案】网络层/Network、运输/TmsPOEt/T2.在虚电路操作方式中,为了进行数据传输,网络的源节点和目的节点之间要建立一条逻辑电路,称之为____。

2.【解析】虚电路不是专用的,每个节点到其它任一节点之间可能有若干条虚电路支持特定的两个端系统之间的数据传输,两个端系统之间也可以有多条虚电路为不同的进程服务,这些虚电路的实际路径可能相同也可能不同。

【答案】虚电路3.虚电路服务是OSI____层向运输层提供的一种可靠的数据传送服务,它确保所有分组按发送____到达目的地端系统。

3.【解析】在分组交换方式中,通信子网有虚电路和数据报两种操作方式,提供虚电路和数据报两种服务。

虚电路操作方式中,为了进行数据传输,网络的源节点和目的节点之间要建立一条逻辑通路,称之为虚电路。

虚电路服务是网络层向运输层提供的一种使所有分组按顺序到达目的端系统的可靠的数据传送方式。

【答案】网络、顺序4.在数据报服务方式中,网络节点要为每个____选择路由,在____服务方式中,网络节点只在连接建立时选择路由。

4.【解析】在数据报操作方式中,每个分组被称为一个数据报,每个数据报自身携带地址信息,若干个数据报构成一次要传送的报文或数据块.数据报服务是指端系统的网络层同网络节点中的网络层之间,一致地按照数据报操作方式交换数据。

虚电路服务是面向连接的服务,数据报服务是无连接的服务。

【答案】分组/数据报、虚电路5.当到达通信子网中某一部分的分组数量过多时,使该部分网络来不及处理,从而使网络性能下降,若出现网络通信业务陷入停顿,我们就称这种现象为____。

URL匹配算法题在当今的互联网时代，URL（统一资源定位符）是人们访问网络资源的主要方式。

一个好的URL匹配算法可以大大提高网站的SEO（搜索引擎优化）效果，从而提升网站的流量和用户访问量。

下面我们将探讨一种常见的URL匹配算法题，并给出相应的解决方案。

问题描述：给定一个URL列表，其中每个URL都包含一个或多个关键词。

我们需要根据这些关键词将URL分类到相应的类别中。

要求算法的时间复杂度尽可能低，并且能够处理大量的URL数据。

解决方案：为了解决这个问题，我们可以使用一种叫做“最长公共前缀”的算法。

该算法的基本思想是，如果两个URL有公共的前缀，那么它们应该属于同一个类别。

具体步骤如下：1.对每个URL进行预处理，将URL中的关键词提取出来，并存储到一个哈希表中。

这样可以快速地查找和匹配关键词。

2.遍历URL列表，对于每个URL，查找其最长公共前缀。

如果有多个关键词共享同一个前缀，则将它们归为同一类别。

3.如果某个URL没有找到公共前缀，则将其归为未分类的类别。

算法的时间复杂度为O(n^2)，其中n是URL列表的长度。

这是因为我们需要对每个URL进行最长公共前缀的查找。

但是，由于使用了哈希表进行关键词的快速查找，所以实际的运行时间可能会更快。

此外，为了处理大量的URL数据，我们可以使用分布式计算框架（如Hadoop）来并行处理数据。

这样可以大大提高算法的效率，并能够处理更大的数据集。

总结：URL匹配算法题是一个经典的计算机问题，它可以应用于各种实际场景中。

通过使用最长公共前缀算法，我们可以快速地将URL分类到相应的类别中。

同时，通过使用分布式计算框架，我们可以处理大量的数据，进一步提高算法的效率。

1.D解释：这是一道命中率的计算题设命中率为x3x+30(1-x)=3.27解得：x=0.992.D这道题一个是考查直接映像、全相联、组相联，以及在具体映射时候是如何实现的。

这里有个基本的计算，那就是1M=10 00 00H这样是不是就比较醒目了：内存地址范围Cache地址范围3800000H-38FFFFFH 000000H-0FFFFFH8800000H-88FFFFFH 100000H-1FFFFFH5900000H-59FFFFFH 200000H-2FFFFFH6700000H-67FFFFFH 300000H-3FFFFFH3.B解释：著作权法是目前世界各国针对计算机软件采用的最普遍的法律保护模式。

著作权法主要针对计算机软件的“作品性”进行保护，并不保护软件的思想以及其“功能性”。

4.A对于软件需求还不明晰，或者暂时不能提出完整的软件需求的时候，可以使用渐增式开发方法来完成软件的一步一步的开发，当软件开发结束，需求也就明朗了。

5.CGantt图可以：表示任务分解成子任务情况；表示每个任务的开始时间和完成时间，线段的长度表示子任务完成所需要的时间；表示子任务之间的并行和串行关系。

Gantt图只能表示任务之间的并行与串行的关系，难以反映多个任务之间存在的复杂关系，不能直观表示任务之间相互依赖制约关系，以及哪些任务是关键字任务等信息.6.D基于计算机的信息系统主要包括：1、计算机硬件系统2、计算机软件系统3、数据及其存储介质4、通信系统5、信息收集、处理设备6、规章制度7、工作人员7.A继承性是面向对象程序设计语言不同于其他语言的主要特点。

8.B类库体现了语言成熟标志9.A显而易见了，B，C莫名其妙，D:除非编写一个1+1=2的程序，否则怎么可能事先就计算出LOC呢？10.D组件就是一些相互协作的类，这应该属于概念的范畴。

11.A这里多说一点，也希望在遇到类似问题的时候，大家能多把总结性的内容写下来，跟大家共享，否则下次考的时候换一个v.92可能又要讨论半天了。

点连通度，边连通度，最小度数的关系 定理8.1
网络，容量，流量，可行流，最大流， 割容量，最小割
匹配，v关于M饱和，完美匹配，最大匹 配，完全匹配
交错路，增广路，定理8.8(最大匹配的充 要条件。
邻集，霍尔定理
点覆盖和独立集,边覆盖和边独立集 定理 8.11,推论 8.1,定理 8.12,科尼格
(König)定理
二、基本算法和计算 最小权通路, 路及权 点着色数和面着色数 最小生成树,最优树（w(T)). 最大流，最小割，最大流的值，割容量 点连通度，边连通度 0(G) ,0(G),1(G),1(G)。
三、证明及判别 1.判别 强连通， (半)Euler图,(半)Hamilton图，找出(回)路 有关结论是否成立
8-15：证明一棵树最多只有一个完美匹 配。
8-16：对于n=2,3,4,5，分别找出一个没有 完美匹配的n-正则简单图的例子。
8-17：证明二分图G具有完美匹配当且仅 当对任意V的子集A，
|Γ（A）|≥A成立。
8.18,8.19,8.20,8.21,8.22
一、基本概念
顶点度数，(G),定理5.1,5.2
2.证明
(1)证明连通：任两点连通。
反证，不连通：1）若干连通分支
2）存在2个顶点，它们之间没有路
(2)证明G为树：树的等价定义证明方法， 利用树的等价定义；证明G有生成树， 可证明G连通，再用定理7.3
(3)利用Euler公式，推论6.1和6.2，及定 理6.2的证明方法，结合定理5.1;做过的 习题
在图论证明中，注意基本概念和结论的运用，
通过加点，加边，删点，删边，使之满足定理 条件。

寻找最大匹配--增广路算法
Step5 利用数组pred所记录的信息，从节点q反向追踪确
定一条p-q 增广路P，执行增广操作M＝M⊕P. 置所有N 中节点i的标号为label(i)=‘null’,转Step1.
Example 利用增广路算法求如下网络的最大匹配：
4 1 5 2 6 3 7
⊕
非二部基数匹配问题
广路P。执行增广操作M＝M⊕P。置所有N中节点的标号为 ‘null’,转Step1.
非二部图的匹配算法举例
利用非二部图的匹配算法求下网络N的最大匹配：
4 1 2 3 6 9
4 1 2 3 6 9 7 8 5
5
已知初始匹配为 M＝{(2,3),(4,5),(6,7)}.
7
8
最大匹配M＝
{(1,2),(3,6),(4,5),(7,8)}
称p-q交错路为花茎(stem)，称q-q奇圈为花朵(blossom)， p为根(root)，q为花蒂(base)。 For example
花朵的收缩
对于网络N的匹配M和花朵W，网络N关于W的 收缩（记为N/W)定义为： (1) 用人工节点w代替花朵W，即增加人工节点w 而删去花朵W中的所有节点； (2)修改原网络中的弧，即所有原来与W中节点相 邻的节点变成与w相邻。
4
Example
6 2 3 7
P 14273 1 P2 142736
P3 15
1 5
寻找最大匹配--增广路算法
根据Theorem 2，如果从某个暴露点p出 发找不到增广路，则可以把该节点p以及 它所关联的弧从N中删去，而不影响最大 匹配的基数. For example
寻找最大匹配--增广路算法
如果j为匹配点且label(j)=‘null’,令pred(j)=i,label(j)=‘inner’, List=List∪{j}.转Step2.(注：所有相邻点均要考虑？碰到末端？）