2013年计算机专业基础综合历年统考真题及思路分析

　　《天勤计算机考研系列：2013年计算机专业基础综合历年统考真题及思路分析》汇集了2009年-2012年的全国硕士研究生入学计算机专业课统考试题（编号408）。首先，编者不但对所有试题均给出了详细解答，而且对于部分试题做到一题多解，部分试题的解法甚至比标准答案的解法更简捷、更省时省力。其次，编者仍然沿用高分笔记系列书籍的特色，从心理学角度出发，为考生指出了一些可能的错误解法，并点评错因，提醒考生引以为戒。最后，针对每道真题中涉及的大纲知识点都做了详细的归纳总结，使考生对于考题中经常出现的知识点进行了强化。

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

目录：
前言
第1篇  数 据 结 构
第1章  绪  论    1
1.1  数据结构的基本概念未考    1
1.2  算法及其分析[2,0]    1
1.3  递归算法设计未考    2
第2章  线性表    3
2.1  线性表的定义未考    3
2.2  顺序表[0,1]    3
2.3  单链表[0,2]    5
2.4  双链表未考    9
2.5  循环链表未考    9
2.6  有序表[0,1]    9
第3章  栈、队列和数组    14
3.1  栈[4,0]    14
3.2  队列[3,0]    18
3.3  数组和稀疏矩阵未考    19
第4章  树与二叉树    20
4.1  树的概念[1,0]    20
4.2  二叉树的概念[2,0]    20
4.3  二叉树的遍历[1,0]    21
4.4  二叉树的构造[2,0]    22
4.5  树和二叉树的相互转换[2,0]    23
4.6  线索二叉树[1,0]    24
4.7  二叉排序树[1,0]    25
4.8  平衡二叉树[3,0]    25
4.9  赫夫曼树[1,0]    28
第5章  图    29
5.1  图的基本概念[2,0]    29
5.2  图的存储结构未考    30
5.3  图的遍历[1,0]    30
5.4  最小生成树[1,0]    30
5.5  最短路径[2,0]    31
5.6  拓扑排序[3,0]    32
5.7  关键路径[0,1]    34
第6章  查  找    36
6.1  查找的基本概念未考    36
6.2  线性表[1,0]    36
6.3  B-树[2,0]    36
6.4  B+树未考    38
6.5  散列表[1,1]    38
第7章  排  序    40
7.1  排序的基本概念未考    40
7.2  插入排序[3,0]    40
7.3  交换排序[3,0]    41
7.4  选择排序[2,0]    42
7.5  归并排序[0,1]    44
7.6  基数排序未考    45
7.7  外排序未考    45
第2篇  计算机组成原理
第8章  计算机系统概述    46
8.1  计算机的发展历程未考    46
8.2  计算机硬件的基本组成[1,0]    46
8.3  计算机软件的分类未考    47
8.4  计算机的工作过程[1,0]    47
8.5  计算机性能指标[1,0]    47
第9章  数据的表示和运算    49
9.1  进位计数制及其相互转换未考    49
9.2  真值和机器数[1,0]    49
9.3  BCD码未考    49
9.4  校验码未考    49
9.5  定点数的表示[1,1]    49
9.6  定点数的运算[1,0]    51
9.7  浮点数的表示[3,0]    52
9.8  浮点数的加/减运算[1,0]    54
9.9  算术逻辑单元（ALU）未考    55
第10章  存储器层次结构    56
10.1  存储器的分类[1,0]    56
10.2  存储器的层次化结构未考    56
10.3  半导体存储器[1,0]    56
10.4  只读存储器未考    57
10.5  Flash存储器[1,0]    57
10.6  主存储器与CPU的连接[4,0]    57
10.7  双口RAM和多模块存储器未考    59
10.8  高速缓冲存储器[3,2]    59
10.9  虚拟存储器[1,1]    66
第11章  指令系统    69
11.1  指令格式未考    69
11.2  指令的寻址方式[3,1]    69
11.3  CISC和RISC的基本概念[1,0]    72
第12章  中央处理器    74
12.1  CPU的功能和基本结构[1,0]    74
12.2  指令执行过程[2,0]    74
12.3  硬布线控制器与微程序控制器[2,1]    75
12.4  指令流水线[3,1]    78
12.5  多核处理器未考    81
12.6  中断系统[4,0]    81
第13章  总  线    84
13.1  总线的基本概念未考    84
13.2  总线的分类[2,0]    84
13.3  总线的组成和性能指标[2,0]    85
13.4  总线仲裁未考    86
13.5  总线操作和定时未考    86
13.6  总线标准[2,0]    86
第14章  输入输出系统    88
14.1  I/O系统基本概念未考    88
14.2  输入输出设备[1,0]    88
14.3  外存储器未考    88
14.4  I/O接口未考    88
14.5  程序查询方式[1,0]    89
14.6  程序中断方式[0,1]见14.7    89
14.7  DMA方式[0,1]    89
14.8  通道方式未考    90
第3篇  操作系统
第15章  操作系统概述    91
15.1  操作系统的概念未考    91
15.2  操作系统的特征[1,0]    91
15.3  操作系统的发展与分类[1,0]    92
15.4  操作系统的主要功能未考    92
15.5  中断和异常[1,0]    92
15.6  用户态与核心态[2,0]    93
15.7  系统调用[2,0]    94
15.8  操作系统的体系结构未考    95
第16章  进程管理    96
16.1  进程的概念和特点[1,0]    96
16.2  进程的三态转化[1,0]    96
16.3  进程的控制[2,0]    97
16.4  线程的概念及线程与进程的比较[2,0]    98
16.5  进程通信未考    99
16.6  处理机的三级调度概念和
      调度的基本原则[1,0]   99
16.7  常见进程调度算法[2,0]    100
16.8  同步与互斥的概念未考    101
16.9  互斥实现的软件方法和硬件方法[1,0]    101
16.10  信号量机制[1,0]    103
16.11  经典同步问题[0,2]    104
16.12  管程未考    116
16.13  死锁的原因和必要条件[1,0]    116
16.14  安全性算法和银行家算法[2,0]    116
第17章  内存管理    119
17.1  应用程序的编译和链接[1,0]    119
17.2  交换和覆盖未考    119
17.3  分区分配[2,0]    119
17.4  内部碎片和外部碎片未考    120
17.5  基本分页、基本分段存储管理方式[2,0]    120
17.6  虚拟存储器[1,0]    121
17.7  请求分页管理方式[1,1]    122
17.8  页面置换算法[0,2]    124
17.9  抖动现象与缺页率[1,0]    130
第18章  文件管理    132
18.1  文件的基本概念[1,0]    132
18.2  文件的逻辑结构未考    132
18.3  目录结构[1,0]    132
18.4  文件共享[1,0]    133
18.5  文件保护未考    133
18.6  文件系统的层次结构未考    133
18.7  目录实现未考    133
18.8  文件的外存分配方式（物理结构）[2,2]    133
18.9  文件存储空间管理未考    137
18.10  磁盘的结构和访问时间未考    137
18.11  磁盘调度算法[1,1]    137
18.12  磁盘管理[1,0]    141
第19章  设备管理    142
19.1  I/O设备的分类与功能未考    142
19.2  I/O控制方式未考    142
19.3  I/O软件层次结构[3,0]    142
19.4  缓冲区[1,0]    143
19.5  设备分配与回收未考    144
19.6  SPOOLing（假脱机）技术未考    144
第4篇  计算机网络
第20章  计算机网络体系结构    145
20.1  计算机网络的概念与组成未考    145
20.2  计算机网络的功能未考    145
20.3  计算机网络的分类未考    145
20.4  计算机网络体系结构[2,0]    145
20.5  ISO/OSI模型和TCP/IP模型[2,0]    146
20.6  计算机网络性能指标[1,0]    147
第21章  物理层    149
21.1  带宽、码元、波特率与速率[1,0]    149
21.2  奈奎斯特定理[1,0]    149
21.3  香农定理未考    150
21.4  编码与调制未考    150
21.5  电路交换、报文交换与分组交换未考    150
21.6  数据报与虚电路未考    150
21.7  传输介质未考    150
21.8  物理层接口特性[1,0]    150
21.9  中继器未考    151
21.10  集线器未考    151
第22章  数据链路层    152
22.1  数据链路层的功能未考    152
22.2  组帧未考    152
22.3  差错控制未考    152
22.4  编码与调制未考    152
22.5  流量控制、可靠传输与滑动窗口机制未考    152
22.6  停止-等待协议未考    152
22.7  后退N帧协议（GBN）[2,0]    152
22.8  选择重传协议（SR）[1,0]    153
22.9  信道划分介质访问控制未考    154
22.10  随机访问介质访问控制[2,1]    154
22.11  令牌传递协议未考    156
22.12  以太网[2,1]    156
22.13  PPP协议未考    159
22.14  HDLC协议未考    159
22.15  网桥未考    159
22.16  交换机未考    159
第23章  网络层    160
23.1  异构网络互连未考    160
23.2  静态路由、动态路由与层次路由未考    160
23.3  IPv4分组与IPv4地址[0,1]    160
23.4  NAT未考    162
23.5  子网划分、CIDR[3,1]    162
23.6  ARP、DHCP、ICMP协议[2,0]    166
23.7  IPv6未考    167
23.8  自治系统与域内、域间路由未考    167
23.9  RIP[1,0]    167
23.10  OSPF协议未考    168
23.11  BGP协议未考    168
23.12  IP组播未考    168
23.13  移动IP未考    168
23.14  路由器[3,0]    168
第24章  传输层    171
24.1  传输层的功能与寻址未考    171
24.2  端口未考    171
24.3  无连接服务与面向连接服务未考    171
24.4  UDP协议未考    171
24.5  TCP段与流量控制[3,0]    171
24.6  TCP连接管理[1,0]    172
24.7  TCP拥塞控制[1,0]    173
第25章  应用层    175
25.1  客户/服务器模型与P2P模型未考    175
25.2  DNS[1,0]    175
25.3  FTP[1,0]    176
25.4  电子邮件[1,0]    176
25.5  WWW未考    177
25.6  HTTP未考    177
参考文献    178