第一章 计算机系统知识 这一章看官方教程就可以了，不需要看其它的教材。如果其中有难以理解的问题，可以上 网查阅。 p17-p20 高速缓存中的地址映像方法和性能分析 p21-p22 软盘硬盘的容量计算方法（格式化和非格式化） p24-p25 cisc/risc 两个指令系统的不同 p29-p30 dma 作用的过程和特点 p31 流水线的作用原理 p34-p38 几种类型的处理机的按 flynn 法分类各处于那种类型 p41-p48 对称加密不对称加密原理及其代表算法认证模型和加密模型的工作流程密钥 管理数字签名和数字加密的过程和区别 ssl 和数字时间戳技术 第一章的其它内容一般都是记忆的。第二章程序设计语言基础 很多人都不喜欢编译原理，如果你能静下心来看一遍绝对可以看懂（我推荐清华的那本编 译原理） ，这一章考得比较少。 p84-p89 确定性有限自动机不确定性有限自动机和正规式之间的相互转化 一般每次 都有 2-3 分的题 编译原理其它的部分可以不用看了，除非你想深入了解，如果非要看你就看一下 90-98 的语法分析第三章操作系统知识 这一章最好是买本操作系统的教材，因为官方教程上写的不够清楚 p121-p123 进程和程序的不同（不要简单地背要理解） p123-p125 进程的三态和五态模型（这个一定要理解每个状态的转换需要的条件和每个 状态的特点） p127-p131 进程同步和互斥（上午下午都可能考，理解信号量的意义，最好要做练习） 临界区的特点 p135-p138 死锁的产生条件和处理策略特别注意银行家算法 p138-p139 线程和进程的区别和联系 p141-p144 分区的方式和特点和不足以及可变分区中的几种算法的特点分区保护 p144-p146 纯分页的原理和地址映射以及快表的概念和工作原理 p147-p149 段页式存储管理的地址映射 p149-p153 虚拟存储的原理和页面置换算法 工作集的概念 p161-p162 spooling 技术 p175-p177 作业管理的过程和调度算法 这一章大部分要理解考试一般 10 分左右（上午题）第四章系统开发和运行知识 这一章对于我们没有经验的人大部分内容要记，这一章可以看其它教材不看也可以。当然 看了更好。 p195 软件生存周期 p196 软件开发模型 p201 进度管理（两个图要理解）p208 cmm 五个级别的特点 p215-p219 数据流图（这是重中之重，要做题，下午题每年都考） p224-p226 变换分析 p227-p230 子系统的划分的标准模块结构图 p231 jackson 图的特点和设计 p242-p248 系统测试（重中之重）各种测试方法的应用范围特点 总的来说这一章记忆远多于理解，但还是尽量多看几次，这一章每年都有很多分的第五章网络基础知识 这一章内容多考试分比较少不用看其它的教材。 p264-p266 网络的拓扑结构 p266-p269 iso/osi 模型以及工作原理 p269-p276 组网设备 p280 csma/cd 工作原理以及工作的环境 p287-p292 tcp/ip 协议簇注意 tcp udp 的区别以及各协议对应在 iso/osi 模型中所在 的位置 p294-p296 子网掩码如何计算，ip 地址类型，计算子网的计算机数目（重中之重） p315-p321 防火墙的分类的四种体系结构 这一章考点比较分散，大家还是多看几遍书第七章数据库技术基础 这一章理解比较多 p371-p373 数据库的三级模式 p375-p380 e-r 模型（重中之重）记住每个图形的含义 p385 关系相关名词 p386-387 关系数据库模式以及完整性约束（重中之重） p399-p417 sql 语句（表操作语句是重点） p417-p426 数据库规范化和模式分解注意几个范式的特点（重中之重） 这一章下午有一道题，上午也有 5 分的样子这章是绝对的重点第八章数据结构 这章不会直接考察编程大家只要理解概念和理解算法即可推荐购买清华版数据结构（黄国 瑜, 叶乃菁编著） p461 串的模式匹配 p467-p481 二叉树的定义和特性树的存取结构数的三种遍历/霍夫曼树的建立/霍夫曼编 码/树二叉树森林之间的转换 p481-p483 图的相关概念 p483-p485 图的存储结构 p485-p488 图的遍历 p488-p495 最小生成树 p524-p526 哈西函数的构造处理冲突的方法 p527-p540 各种排序的思路性能分析（重中之重） 这章上午分数较多记忆性的不多大部分是理解的树，图，排序是最重要的第九章常用算法设计 这章主要下午题,主要考回溯法/贪心法/分治法,这章就看大家的实力了靠平时的积累多去 看程序！数据结构和算法数据结构和算法选择排序选择排序选择排序分为简单选择排序，堆排序 简单选择排序： 从元素中寻找最小的元素，将它和第一位替换，依次类推堆排序 首先知道什么是堆，堆是一颗二叉树，是满足什么条件的二叉树呢？ 但 KiK2i，Ki=K2i+1 Eg:对 46,79,56,38,40,84 建立一个大顶堆，求初始堆 首先建立完全二叉树，插入规则是按层次遍历插入 调整二叉树，使其符合堆的规则，一半从 n/2 的元素开始交换排序交换排序交换排序分为冒泡排序，快速排序 57 68 59 52 从小到大排序 冒泡排序快速排序快速排序（Quicksort）是对冒泡排序的一种改进。由 C. A. R. Hoare 在 1962 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对 这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个 数据变成有序序列。初始状态 49 38 65 97 76 13 27 进行一次快速排序之后划分为 27 38 13 49 76 97 65 分别对前后两部分进行快速排序 27 38 13 经第三步和第四步交换 后变成 13 27 38 完成排序。 76 97 65 经第三步和第四步交换后变 成 65 76 97 完成排序。 /参照数据结构（C 语言版） /调用：quicksortqsortpartitions int partitions(int a,int low,int high) int pivotkey=alow; /a0=alow; while(low=pivotkey) -high; alow=ahigh; while(low /#include #include “myfunc.h“ /存放于个人函数库中 main() int i,a11=0,11,12,5,6,13,8,9,14,7,10; for(i=0;i #include int main(void) int data10 = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81; int temp1010 = 0; int order10 = 0; int i, j, k, n, lsd; k = 0; n = 1; printf(“n 排序前: “); for(i = 0; i 10; i+) printf(“%d “, datai); putchar(n); while(n = 10) for(i = 0; i 10; i+) lsd = (datai / n) % 10); templsdorderlsd = datai; orderlsd+; printf(“n 重新排列: “); for(i = 0; i 10; i+) if(orderi != 0) for(j = 0; j orderi; j+) datak = tempij; printf(“%d “, datak); k+; orderi = 0; n *= 10; k = 0; putchar(n); printf(“n 排序后: “); for(i = 0; i 10; i+) printf(“%d “, datai); return 0; * Javapublic class RadixSort public static void sort(int number, int d) int k = 0;int n = 1;int temp = new intnumber.lengthnumber.length;int order = new intnumber.length;while(n = d) for(int i = 0; i number.length; i+) int lsd = (numberi / n) % 10); templsdorderlsd = numberi; orderlsd+; for(int i = 0; i number.length; i+) if(orderi != 0) for(int j = 0; j orderi; j+) numberk = tempij; k+; orderi = 0; n *= 10; k = 0; public static void main(String args) int data = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100; RadixSort.sort(data, 100);for(int i = 0; i data.length; i+) System.out.print(datai + “ “); 基数排序可以采用顺序存储方式。使用 R 数组存放待排序记录，用 r 个数组存放分配时的 r 个队列。分配一次和收集一次都需要 n 次移动，d 遍分配和收集，共需 2dn 移动。每个队列最大为 n，共需 rn 个结点。 若采用链式存储方式，在 R 数组中，每个记录设一个 next 字段，存放下一结点的下标（静态链表） 。记录的移动次数降为 0，辅助空间为 O(n+r)，分配时间 O(n)，收集时间O(n)，时间复杂度 O(d(n+r)。算法的稳定性算法的稳定性同样的关键字在排序中如果改变位置之后则算法就不稳定反之稳定算法的复杂度算法的复杂度Hash 表表Hash 表的冲突表的冲突关键字相同但是求出的 hash 地址相同，就是他们各自的值不相同但是取余之后 求出的结果却相同构造方法构造方法常用构造方法 直接定制法 除余法 基数转换法 平方取中法 折叠法 移位法 随机算法处理冲突方法处理冲突方法开放定址法 线性 双散链表 拉链法编译原理编译原理文法 终结符合非终结符 文法类型 0 型文法的定义 1 型文法上下文有关文法。应对于线性有限自动机 2 型文法上下文无关文法。 3 型文法正规文法。应对于有限状态自动机 正规式 正规式和正规文法之间的转换