2014版计算机网络高分笔记

出版时间：2013-5  出版社：机械工业出版社  作者：天勤论坛  
Tag标签：无  

前言

前言2014版修订说明：由于从2013年开始，部分高校采取了学校自主命题的方式，导致计算机网络科目考查的范围有所改变。故《2014版计算机网络高分笔记》相比于《2013版计算机网络高分笔记》增加了一些知识点的讲解（如果你所报考的学校采取统考，则可跳过），这些知识点的讲解全部归纳为一章，即最后一章非统考高校知识点补充，并且相对应地增加了一些习题。对于原先统考的知识点讲解，编者将近一年来论坛答疑的精华内容再一次融入了知识点讲解，使其更加完善。 一、针对非统考学生由于从2013年开始，部分高校采取了学校自主命题的方式，导致计算机网络科目考查的范围有所改变。故《2014版计算机网络高分笔记》相比于《2013版计算机网络高分笔记》增加了一些知识点的讲解（如果你所报考的学校采取统考，则可跳过），这些知识点的讲解全部归纳为一章，即第7章非统考高校知识点补充，并且相应地增加了一些习题。2014版增加的知识点如下：知识点一：组播路由算法知识点二：数据链路层之LLC子层知识点三：FDDI环知识点四：虚拟局域网由于“计算机网络”科目历年真题收集有限，暂时仅对以上知识点进行补充。但是，没有关系，笔者专门开设了一个回馈帖子。如果考生所报考的自主命题高校考查计算机网络科目，并且发现有些知识点没有讲到，可以在此贴中回复，笔者会不断更新知识点讲解并以PDF电子版的形式发布，供考生免费下载。二、针对统考学生对于原先统考的知识点讲解，笔者通过一年的答疑作了如下修改：改正了发现的错别字以及具有歧义的习题。将近一年来论坛答疑的精华内容再一次融入了知识点讲解，使其更加完善。推荐教材：《计算机网络》（第5版），谢希仁编著。2014版有如下特点：1．本书写作非常细致，让读者很容易上手为了让读者更加轻松地学习和理解计算机网络课程考研相关知识点，本书对于每个知识点都进行了非常细致的讲解。某些难点、抽象的概念还通过讲故事的方法去帮助读者学习和理解，可使读者每学习一个知识点即可掌握一个知识点。可以说，本书是一本极其容易上手的书。2．囊括成千上万位计算机专业考研学子的考研疑问天勤论坛作为一个计算机专业考研学习交流平台，每年都将积累成千上万条考研疑问，编者将具有代表性的疑问收录在本书中，并且给出最详细的讲解。3．及时总结、及时练习本书中每讲完一些易混易错的知识点都会进行总结。同时，为了让考生即学即用，加深印象，每章最后均给出了大量的经典习题。这些习题紧扣所讲知识点，让考生及时练习，巩固提高。为了方便考生检验学习效果，书中对所有练习题都给出了最详细的解答。4．题源的新颖性众所周知，计算机网络课程的题源是相当少的，所以出题老师已经将出题的意向转为软件工程师（以下简称软工）和网络工程师（以下简称网工）的历年考题。例如，选项中出现Ⅰ、Ⅱ、Ⅲ进行多选的题型就来源于“网工”和“软工”考试的历年真题。由此可知，“网工”和“软工”的习题是相当重要的。当然，考生不用自己花费时间去找，在本书中已经收录了近10年来“软工”和“网工”考试的历年真题，经过悉心的挑选，已把超纲的部分删除，最后筛选出来的都是最经典的考研题目。另外，编者也针对相应的考研知识点模仿此类题型，自创了不少高质量的题目，目的就是希望考生在平时做题的过程中能够更近距离地体验到做真题的感觉。阅读建议由于计算机网络这门课程的特殊性，建议考生先通读一遍教材，对计算网络科目形成一个宏观的框架。在这个框架中，考生肯定会存在很多的细节疑问，如“计算机网络为什么要分层”等非常抽象的问题，感觉这些知识就像是被硬塞进脑海一样，完全不知道为什么。没有关系，这是很正常的。请将这些疑问记在笔记本上，然后带着疑问通读本书，再通过一些经典习题的练习，相信可以解决考生大部分的疑问。当然，如果读者觉得还有疑问没能通过本书得到解决，可以将疑问发布至天勤论坛的“计算机网络答疑版块”，编者将会尽最大努力协助解决。编者

内容概要

内容推荐
本书针对近几年全国计算机学科专业综合考试大纲的“计算机网络”部分进行了深入解读，以一种独创的方式对考试大纲知识点进行了讲解，即从考生的视角剖析知识难点；以通俗易懂的语言取代晦涩难懂的专业术语；以成功考生的亲身经历指引复习方向；以风趣幽默的笔触缓解考研压力。读者对书中的知识点讲解有任何疑问都可与作者进行在线互动，为考生解决复习中的疑难点，提高考生的复习效率。
根据计算机专业研究生入学考试形势的变化（逐渐实行非统考）书中对大量非统考知识点进行了讲解，使本书所包含的知识点除覆盖统考大纲的所有内容外，还包括了各大自主命题高校所要求的知识点。

作者简介

作者简介
天勤论坛，取名自古训“天道酬勤”，意为考研路上，困苦实多，然而天自有道，勤恳付出者，必有应得之酬劳。天勤论坛由浙大、北航等多所计算机专业名校的研究生创办，团队所有成员皆亲身经历过计算机专业考研的磨炼，于是本着为考生服务的热情，共同搭建了此交流平台。
由天勤论坛组编的高分笔记系列计算机考研辅导书，融入了论坛答疑的精华内容，论坛组织了高分考生进行勘误，不断完善此套书籍。考生在书中遇到疑问，也可在线与作者进行交流。
为提高考生算法设计能力，团队搭建了专门针对计算机考研学子的在线算法测试平台——ACM俱乐部（acmclub.com），希望能借此帮助考生提高复习效率。

书籍目录

序 新版更新简介及互动服务 新版使用说明 前言 第1章绪论1 本章概略1 1.1针对考研数据结构的代码书写规范以及C&C++语言基础1 1.1.1考研综合应用题中算法设计部分的代码书写规范1 1.1.2考研中的C&C++语言基础杂谈3 1.2算法的时间复杂度与空间复杂度分析基础11 1.2.1考研中的算法时间复杂度杂谈11 1.2.2例题选讲11 1.2.3考研中的算法空间复杂度分析13 1.3数据结构和算法的基本概念13 1.3.1数据结构的基本概念13 1.3.2算法的基本概念14 习题15 习题答案16 第2章线性表19 大纲要求19 考点与要点分析19 核心考点19 基础要点19 本章知识体系框架图19 知识点讲解20 2.1线性表的基本概念与实现20 2.2线性表的基本操作23 2.2.1线性表的定义23 2.2.2线性表的结构定义23 2.2.3顺序表的算法操作24 2.2.4单链表的算法操作27 2.2.5双链表的算法操作32 2.2.6循环链表的算法操作33 真题仿造34 真题仿造答案与讲解34 上机实战35 习题+历年真题36 习题答案+历年真题答案40 第3章栈、队列和数组52 大纲要求52 考点与要点分析52 核心考点52 基础要点52 本章知识体系框架图52 知识点讲解53 3.1栈和队列的基本概念53 3.1.1栈的基本概念53 3.1.2队列的基本概念53 3.2栈和队列的存储结构、算法与应用53 3.2.1本章所涉及的数据结构定义53 3.2.2顺序栈的基本算法操作55 3.2.3链栈的基本算法操作56 3.2.4栈的应用58 3.2.5顺序队的算法操作61 3.2.6链队的算法操作63 3.3特殊矩阵的压缩存储65 真题仿造67 真题仿造答案与讲解68 上机实战71 习题+历年真题71 习题答案+历年真题答案76 第4章串（非统考补充内容）88 知识点讲解88 4.1串数据类型的定义88 4.1.1串的定义88 4.1.2串的结构定义88 4.1.3串的基本操作89 4.2串的模式匹配算法92 4.2.1一种简单的模式匹配算法92 4.2.2KMP算法93 习题98 习题答案99 上机实战108 第5章数组和稀疏矩阵（非统考补充内容）109 知识点讲解109 5.1数组和稀疏矩阵109 5.1.1多维数组109 5.1.2稀疏矩阵110 习题115 习题答案116 上机实战124 第6章树与二叉树125 大纲要求125 考点与要点分析125 核心考点125 基础要点125 本章知识体系框架图125 知识点讲解126 6.1树的基本概念126 6.1.1树的定义126 6.1.2树的基本术语126 6.1.3树的存储结构127 6.2二叉树127 6.2.1二叉树的定义127 6.2.2二叉树的主要性质128 6.2.3二叉树的存储结构129 6.2.4二叉树的遍历算法130 6.2.5线索二叉树的基本概念和构造138 6.3树和森林141 6.3.1孩子兄弟存储结构141 6.3.2森林与二叉树的转换142 6.3.3树和森林的遍历142 6.4树与二叉树的应用143 6.4.1二叉排序树与平衡二叉树143 6.4.2赫夫曼树和赫夫曼编码143 真题仿造145 真题仿造答案与解析146 上机实战147 习题+历年真题147 习题答案+历年真题答案153 第7章图168 大纲要求168 考点与要点分析168 核心考点168 基础要点168 本章知识体系框架图168 知识点讲解169 7.1图的基本概念169 7.2图的存储结构170 7.2.1邻接矩阵170 7.2.2邻接表172 7.3图的遍历算法操作172 7.3.1深度优先搜索遍历172 7.3.2广度优先搜索遍历174 7.3.3例题选讲175 7.4最小（代价）生成树177 7.4.1普里姆算法和克鲁斯卡尔算法177 7.4.2例题选讲182 7.5最短路径183 7.5.1迪杰斯特拉算法183 7.5.2弗洛伊德算法189 7.6拓扑排序191 7.6.1AOV网191 7.6.2拓扑排序191 7.6.3例题选讲193 7.7关键路径194 7.7.1AOE网194 7.7.2关键路径194 真题仿造197 真题仿造答案解析198 上机实战199 习题+历年真题200 习题答案+历年真题答案205 第8章排序218 大纲要求218 考点与要点分析218 核心考点218 基础要点218 本章知识体系框架图219 知识点讲解219 8.1排序的基本概念219 8.1.1排序219 8.1.2稳定性219 8.1.3排序算法的分类219 8.2插入类排序220 8.2.1直接插入排序220 8.2.2折半插入排序222 8.2.3希尔排序222 8.3交换类排序224 8.3.1起泡排序224 8.3.2快速排序225 8.4选择类排序227 8.4.1简单选择排序227 8.4.2堆排序228 8.5二路归并排序231 8.6基数排序232 8.7外部排序235 8.7.1基本概念235 8.7.2归并排序法235 8.7.3败者树237 真题仿造239 真题仿造答案与解析240 上机实战241 习题+历年真题241 习题答案+历年真题答案246 第9章查找256 大纲要求256 考点与要点分析256 核心考点256 基础要点256 本章知识体系框架图256 知识点讲解257 9.1查找的基本概念、顺序查找法、折半查找法257 9.1.1查找的基本概念257 9.1.2顺序查找法258 9.1.3折半查找法258 9.2二叉排序树、平衡二叉树261 9.2.1二叉排序树261 9.2.2平衡二叉树263 9.3B—树及其基本操作、B+树的基本概念266 9.3.1B—树的基本概念266 9.3.2B—树的基本操作267 9.3.3B+树的基本概念272 9.4散列表272 9.4.1散列表的概念272 9.4.2散列表的建立方法以及冲突解决方法273 9.4.3散列表的性能分析276 真题仿造278 真题仿造答案与解析278 上机实战279 习题+历年真题279 习题答案+历年真题答案284 第10章考研中某些算法的分治法解释296 附录300 附录A历年真题分值、考点统计表300 附录B历年真题考点索引表302 参考文献304 考研中某些算法的分治法解释305 天勤考研高分笔记系列书籍之考研公共课305 考研政治306 考研数学306 考研英语306

章节摘录

版权页：   插图：   31.解析：D。以太网地址由48bit组成，使用6个字节表示。而IPv4的地址由32bit组成，使用4个字节表示。 32.解析：C。以太网采用CSMA／CD技术，当网络上的流量越多，负载越大时，发生冲突的几率也会越大。当工作站发送的数据帧因冲突而传输失败时，会采用二进制后退算法后退一段时间后重新发送数据帧。二进制后退算法可以动态地适应发送站点的数量，后退延时的取值范围与重发次数n形成二进制指数关系。当网络负载小时，后退延时的取值范围也小；而当负载大时，后退延时的取值范围也随着增大。二进制后退算法的优点是把后退延时的平均取值与负载的大小联系起来。所以，二进制后退算法考虑了网络负载对冲突的影响。 33.解析：D。 按总线争用协议来分类，CSMA有3种类型。 1）非坚持CSMA。一个站点在发送数据帧之前，先要对介质进行检测。如果没有其他站点在发送数据，则该站点开始发送数据。如果介质被占用，则该站点不会持续监听介质，而等待一个随机的延迟时间后再监听。采用随机的监听延迟时问可以减少冲突的可能性，但其缺点也是很明显的：即使有多个站点有数据要发送，因为此时所有站点可能都在等待各自的随机延迟时间，而介质仍然可能处于空闲状态，这样就使得介质的利用率较低，所以排除选项A。 2）1一坚持CSMA。当一个站点要发送数据帧时，它就监听介质，判断当前时刻是否有其他站点正在传输数据。如果介质被占用，该站点将会持续监听直至介质空闲。一旦该站点检测到介质空闲，它就立即发送数据帧，所以D选项是正确的。如果产生冲突，则等待一个随机时间再监听。之所以叫“1—坚持”，是因为当一个站点发现介质空闲的时候，它传输数据帧的概率是1。1—坚持CSMA的优点是只要介质空闲，站点就立即发送；它的缺点是假如有两个或两个以上的站点有数据要发送，冲突就不可避免，排除选项8。 3）p.坚持CSMA。p—坚持CSMA是非坚持CSMA和1—坚持CSMA的折中。p—坚持CSMA应用于划分时槽的介质，其工作过程如下：当一个站点要发送数据帧的时候，它先检测介质。若介质空闲，则该站点按照概率p的可能性发送数据，而有1—p的概率会把要发送数据帧的任务延迟到下一个时槽。按照这样的规则，若下一个时槽也是空闲的，则站点同样按照概率P的可能性发送数据，所以说如果处理得当P坚持型监听算法还是可以减少网络的空闲时间的，排除C。 34.解析：D。在使用静态地址的系统上，如果有重复的硬件地址，那么这两个设备都不能通信。在局域网上，每个设备必须有一个唯一的硬件地址。 35.解析：B。以太网有最小帧长度限制，设置最小帧长是为了区分开噪声和因发生碰撞而异常终止的短帧，它必须要大于648。 36.解析：C。一般来说，在第i次碰撞后，站点会在0～21—1中之间随机选择一个数M，然后等待M倍的争用期再发送数据。 37.解析：C。以太网在到达10次冲突之后，随机数的区间固定在最大值1023上，以后不再增加。如果连续超过16次冲突，则丢弃。

编辑推荐

《2014版计算机网络高分笔记(第2版)》较之去年的第一版有了重大更新：1.为非统考的考生增加常考知识点的讲解。2.作者通过微博和微信与读者交流，收集读者反馈信息，并将《2014版计算机网络高分笔记(第2版)》的更新信息第一时间发布给读者。3.开通在线程序测评系统，考生可登陆相关网站进行上机练习，巩固所学知识点。4.改正所发现的错别字，并进一步优化讲解方式。5.修正代码中出现的bug，并优化解题代码。

名人推荐

如果你是毫无基础或者基础薄弱，特别是跨考计算机专业的同学，那么我诚挚地向你推荐“高分笔记系列”书籍，它以通俗易懂的讲解让你快速入门，使你更有信心打败计算机考研中专业课这个拦路虎，从而分出更多时间和精力复习公共课，最终取得理想的成绩！ ——小景润（总分401，专业课120，跨考浙大计算机） 天勤的《八套考研模拟卷》，正如书中所述，原创之逼近真题程度，特别是知识点总结，在我的脑海形成了完整的知识体系。本人的跨考之路深受其恩惠，在此推荐给大家。有天勤作伴的你，只需要用心研读&&用心笔记，就可以return success了。 ——许利宁（总分380，专业课127，跨考清华计算机） 对于计算机专业的同学，复习关键在“点”。“高分笔记系列”针对于各个点的把握非常全面，结构清晰，详略得当。一遍详读深刻理解，一遍泛读过滤点滴，一遍速读查补缺漏，事可成矣！ ——杨学轶（总分384，专业课129，报考北航计算机）

用户评论 (总计6条)

•   总共买了两本，一本是新的，另一本感觉像旧书，不仅边角折过，第一页还被撕掉了，就像之前有人写过名字然后撕掉一样。
•   还不错啦！其实这种资料都差不多
•   跟大纲的顺序一致，看起来方便一些。框架不错，重点疑点总结很好，好好看，祝大家成功
•   挺不错的，写的挺好！！！
•   不错，还是觉得详细但框架不够清晰，总体看完了，知识点都明白了，但是没理清条理。。
•   书的质量还不错啦 比想象的好