2021考研新大纲解析王道考研——计算机统考WWW.CSKAOYAN.COM王道考研/CSKAOYAN.COM自我介绍一哈子咸鱼学长王道数据结构、操作系统、计组主讲本科：BIT软件工程读研：PKU大数据技术考研成绩：总分386，专业课143工作经历：两年多游戏服务器开发王道考研/CSKAOYAN.COM教育部考试中心大纲王道书每一章开头部分王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM科目小题大题分值数据结构11222+23计组11222+23操作系统10220+15计网8116+918年较特殊DS大题25分计网大题7分（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网……发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？题型和分值王道考研/CSKAOYAN.COM换个说法而已，基本概念如：表头元素、表尾元素、表长早就这么考了早就这么考了王道考研/CSKAOYAN.COM2018真题2010真题王道考研/CSKAOYAN.COMC语言二维数组的存储原理王道考研/CSKAOYAN.COM关注外部排序算法的比较，一定是基于归并思想换个说法而已，基本概念如：表头元素、表尾元素、表长早就这么考了早就这么考了王道考研/CSKAOYAN.COM外部排序的比较：不同的归并树导致的磁盘I/O次数差异，很方便结合磁盘读写次数进行考察王道考研/CSKAOYAN.COM磁盘内存读磁盘写磁盘45272813725142944183813197394124015516304311132012342443461732647222110332335输⼊缓冲区1输⼊缓冲区2424836“归并排序”要求各个⼦序列有序，每次读⼊两个块的内容，进⾏内部排序后写回磁盘输出缓冲区9826构造初始“归并段”数据结构+操作系统的综合，可以在大题合起来考初始归并段的长度不同，算法性能的差异归并的路数不同，算法性能的差异归并段长度不同+多叉哈夫曼树王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM时间开销分析读、写各16次，还要进⾏内部排序R1R2R3R4R5R6R7R8R1’R2’R3’R4’R1’’R2’’有序⽂件读、写磁盘次数=32+32*3=128次注：磁盘是慢速设备，读写次数太多导致时间开销⼤幅增加读、写各16次，还要进⾏内部归并读、写各16次，还要进⾏内部归并读、写各16次，还要进⾏内部归并外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间归并趟数⽂件总块数*2⽣成8个初始归并段，每个段占两块王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM内存读磁盘写磁盘4个输⼊缓冲区输出缓冲区磁盘⽣成初始归并段的“内存⼯作区”越⼤，初始归并段越⻓892627125364248452837初始归并段只有4个15516304311132012342443461...
