第1章 编程基础 1
1.1变量 1
1.2数据类型 1
1.3数据结构 2
1.4抽象数据类型 3
1.5内存与变量 3
1.6指针 4
1.6.1指针的声明 4
1.6.2指针的使用 5
1.6.3指针的操纵 6
1.6.4数组与指针 7
1.6.5动态内存分配 7
1.6.6函数指针 7
1.7参数传递的方式 8
1.7.1实际参数与形式参数 8
1.7.2参数传递的语义 8
1.7.3各种编程语言所支持的参数传递方式 9
1.7.4按值传递 9
1.7.5按结果传递 10
1.7.6有可能发生的参数冲突 10
1.7.7按值-结果传递 11
1.7.8按引用传递（别名机制） 11
1.7.9按名称传递 12
1.8绑定 12
1.8.1静态绑定（前期绑定） 13
1.8.2动态绑定（后期绑定） 13
1.9作用域 13
1.9.1静态作用域 13
1.9.2动态作用域 14
1.10存储类别 15
1.10.1存储类别为auto的变量 15
1.10.2存储类别为extern的变量 16
1.10.3存储类别为register的变量 18
1.10.4存储类别为static的变量 19
1.11存储空间的安排 19
1.12编程方式 22
1.12.1无结构的编程 22
1.12.2过程式的编程 22
1.12.3模块式的编程 22
1.12.4面向对象的编程 23
1.13面向对象编程的基本概念 23
1.13.1类与对象 24
1.13.2封装 24
1.13.3抽象 25
1.13.4数据隐藏 25
1.13.5多态 25
1.13.6继承 26
1.13.7继承的类型 26
1.13.8动态绑定 27
1.13.9消息传递 28
第2章 脚本语言 83
2.1解释器与编译器 83
2.1.1编译器 83
2.1.2解释器 84
2.1.3编译器与解释器的区别 84
2.2什么是脚本语言 84
2.3 shell脚本编程 85
2.3.1命令的重定向与管道 85
2.3.2变量 86
2.3.3命令行参数 87
2.3.4命令替换 88
2.3.5算术扩展 88
2.3.6控制结构 88
2.3.7函数 92
2.4 Perl 94
2.4.1从“Hello world！”程序开始 94
2.4.2 Perl的命令行参数 95
2.4.3 Perl的数据类型与变量 95
2.4.4引用 98
2.4.5声明变量 98
2.4.6变量的作用域 99
2.4.7字符串字面量 99
2.4.8 Perl的标准输入端 100
2.4.9 Perl语言的运算符 101
2.4.10条件语句 110
2.4.11循环 113
2.4.12子例程 115
2.4.13字符串操作 117
2.4.14包／模块 118
2.5 Python 118
2.5.1什么是Python 118
2.5.2布尔类型 119
2.5.3整数 119
2.5.4字符串 119
2.5.5列表与元组 121
2.5.6函数 122
2.5.7把代码包装成模块 123
第3章 与设计有关的面试题 124
3.1术语介绍 124
3.2技巧 125
3.3可供练习的其他设计问题 179
第4章 操作系统的概念 180
4.1术语介绍 180
4.2与操作系统概念有关的问题 183
第5章 计算机网络的基础知识 188
5.1介绍 188
5.2局域网与广域网 188
5.3数据包分割与多路复用 189
5.4终端设备 190
5.5中介设备 190
5.6集线器、交换机与路由器的定义 191
5.7介质 192
5.8端对端网络与客户端／服务器网络 192
5.9互联网是如何运作的 193
5.10 OSI模型与TCP／IP模型的区别 196
5.11客户端／服务器结构与互联网 197
5.12 ARP与RARP 198
5.13子网 199
5.14路由器的工作原理 200
5.15 单播、广播、多播 201
5.16 tracert／traceroute及ping命令的工作原理 202
5.17什么是QoS 203
第6章 数据库概念 204
6.1术语介绍 204
6.2与数据库概念有关的问题 206
第7章 智力题 213
7.1智力题 213
第8章 算法介绍 217
8.1什么是算法 217
8.2为什么要做算法分析 218
8.3算法分析的目标 218
8.4什么是运行时间分析 218
8.5怎样对比不同的算法 218
8.6什么是增长率 219
8.7几种常见的增长形式 219
8.8算法分析的类型 220
8.9渐近表示法 221
8.10大O表示法 221
8.11大Ω表示法 222
8.12大？表示法 223
8.13算法分析为什么又叫渐近分析 225
8.14渐近分析指南 225
8.15三种表示法的性质 227
8.16常用的对数公式与求和公式 227
8.17分治算法的主定理 227
8.18与分治算法的主定理有关的问题 228
8.19递减式递推（减而治之）算法的主定理 229
8.20另一种递减式递推（减而治之）算法的主定理 229
8.21与算法分析有关的问题 230
第9章 递归与回溯 240
9.1介绍 240
9.2什么是递归 240
9.3为什么要用递归的办法解决问题 240
9.4递归函数的格式 241
9.5演示递归调用时的内存占用情况 241
9.6递归与迭代 242
9.7运用递归时的注意事项 243
9.8递归算法举例 243
9.9与递归有关的问题 243
9.10什么是回溯 245
9.11回溯算法举例 245
9.12与回溯有关的问题 245
第10章 链表 248
10.1什么是链表 248
10.2将链表用作抽象的数据类型 248
10.3为什么要用链表 249
10.4数组概述 249
10.5比较链表、数组与动态数组 250
10.6单链表 251
10.7双链表 256
10.8循环链表 261
10.9节省内存的双链表 266
10.10松散链表 268
10.11跳跃链表 273
10.12与链表有关的问题 276
第11章栈 295
11.1什么是栈 295
11.2怎样使用栈 296
11.3将栈用作抽象数据类型 296
11.4栈的运用 296
11.5实现 297
11.6对比各种实现方式 302
11.7与栈有关的问题 303
第12章 队列 324
12.1什么是队列 324
12.2如何使用队列 324
12.3将队列用作抽象数据类型 325
12.4异常 325
12.5运用 325
12.6实现 326
12.7与队列有关的问题 331
第13章树 337
13.1什么是树 337
13.2术语表 337
13.3二叉树 339
13.4二叉树的类型 339
13.5二叉树的性质 340
13.6遍历二叉树 342
13.7泛化树（N叉树） 362
13.8通过线索二叉树来遍历 369
13.9表达式树 376
13.10异或树 379
13.11二叉搜索树 380
13.12平衡二叉搜索树 395
13.13 AVL树 396
13.14其他形式的树 413
13.14.1红黑树 413
13.14.2伸展树 414
13.14.3扩充树（增强树） 414
13.14.4区间树（区段树） 415
13.14.5替罪羊树 416
第14章 优先级队列与堆 418
14.1什么是优先级队列 418
14.2将优先级队列用作抽象数据结构 418
14.3运用 419
14.4实现 419
14.5堆与二叉堆 420
14.6二叉堆 421
14.7与优先级队列和堆有关的问题 428
第15章 图算法 442
15.1介绍 442
15.2术语表 442
15.3图的运用 446
15.4将图用作抽象的数据结构 446
15.4.1邻接矩阵 446
15.4.2邻接列表 447
15.4.3邻接集合 449
15.4.4表示图的方法的对比 449
15.5图的遍历 449
15.5.1深度优先搜索（DFS） 450
15.5.2广度优先搜索（BFS） 454
15.5.3对比DFS与BFS 456
15.6拓扑排序 457
15.7最短路径算法 458
15.8最小生成树 465
15.9与图算法有关的问题 469
第16章 排序 475
16.1什么是排序 475
16.2为什么要排序 475
16.3排序算法的分类方式 475
16.3.1按照比较的次数来分类 475
16.3.2按照交换操作的次数来分类 476
16.3.3按照内存使用量来分类 476
16.3.4按照是否递归来分类 476
16.3.5按照是否稳定来分类 476
16.3.6按照适应性来分类 476
16.4其他的分类方式 476
16.5冒泡排序 477
16.6选择排序 478
16.7插入排序 479
16.8希尔排序 481
16.9归并排序 483
16.10堆排序 485
16.11快速排序 485
16.12树排序 488
16.13线性时间的排序算法 489
16.14计数排序 489
16.15 桶排序 490
16.16基数排序 490
16.17拓扑排序 491
16.18外部排序 491
16.19与排序有关的问题 492
第17章 搜索 500
17.1什么是搜索 500
17.2为什么要搜索 500
17.3各种类型的搜索 500
17.4在无序的数据中执行线性搜索 501
17.5在已经排好序／有序的数组中执行线性搜索 501
17.6二分搜索 501
17.7对比几种基本的搜索算法 502
17.8符号表与哈希 502
17.9字符串搜索算法 502
17.10与搜索有关的问题 503
第18章 选择算法 530
18.1什么是选择算法 530
18.2通过排序来选择 530
18.3基于分区的选择算法 531
18.4线性选择算法——中位数的中位数算法 531
18.5把最小的k个元素找出来 531
18.6与选择算法有关的问题 531
第19章 符号表 541
19.1介绍 541
19.2什么是符号表 541
19.3实现符号表 542
19.4比较实现符号表的各种方式 543
第20章 哈希 544
20.1什么是哈希 544
20.2为什么要使用哈希 544
20.3将哈希表用作抽象数据结构 544
20.4哈希技术的原理 545
20.5哈希技术的组成要素 546
20.6哈希表 546
20.7哈希函数 547
20.8负载因子 547
20.9冲突 547
20.10冲突解决技术 548
20.11单独链接法 548
20.12开放定址 548
20.12.1线性探测 548
20.12.2二次探测 549
20.12.3二次哈希 550
20.13比较各种冲突解决技术 550
20.14哈希技术如何把复杂度降为O（1） 551
20.15 哈希技术 551
20.16哪些问题不适合用哈希表解决 551
20.17 Bloom过滤器 552
20.17.1工作原理 552
20.17.2选择合适的哈希函数 553
20.17.3设置长度合适的位向量 553
20.17.4空间方面的优势 553
20.17.5时间方面的优势 554
20.17.6实现 554
20.18与哈希有关的问题 554
第21章 字符串算法 565
21.1介绍 565
21.2字符串匹配算法 565
21.3蛮力法 566
21.4 Rabin-Karp字符串匹配算法 566
21.5用有限状态机来实现字符串匹配算法 567
21.5.1状态机的运作过程 568
21.5.2构建有限状态机时的注意事项 568
21.5.3 匹配算法 568
21.6 KMP算法 569
21.6.1前缀表 569
21.6.2匹配算法 571
21.7 Boyce-Moore算法 573
21.8适合用来保存字符串的数据结构 573
21.9用哈希表来保存字符串 574
21.10用二叉搜索树来存放字符串 574
21.11前缀树 574
21.11.1什么是前缀树 574
21.11.2为什么要使用前缀树 575
21.11.3声明前缀树 575
21.11.4向前缀树中插入字符串 576
21.11.5在前缀树中查找字符串 576
21.11.6用前缀树来表示字符串有什么缺点 577
21.12三元搜索树 577
21.12.1声明三元搜索树 577
21.12.2向三元搜索树中插入字符串 578
21.12.3在三元搜索树中查找字符串 580
21.12.4显示三元搜索树中的全部字符串 580
21.12.5在三元搜索树中查找最长的字符串 581
21.13比较二叉搜索树、前缀树及三元搜索树 581
21.14后缀树 581
21.14.1前缀与后缀 582
21.14.2规律 582
21.14.3什么是后缀树 582
21.14.4构建后缀树 582
21.14.5运用后缀树 585
21.15 与字符串有关的问题 585
第22章 算法设计技巧 591
22.1介绍 591
22.2分类 591
22.3按实现方式分类 591
22.3.1递归算法与迭代算法 591
22.3.2过程式算法与声明式（非过程式）算法 592
22.3.3串行算法、并行算法、分布式算法 592
22.3.4确定性的算法与非确定性的算法 592
22.3.5精确算法与近似算法 592
22.4按设计方式分类 592
22.4.1贪婪算法 592
22.4.2分治算法 593
22.4.3动态规划算法 593
22.4.4线性规划算法 593
22.4.5归约（转化并治理）算法 593
22.5其他分类方式 594
22.5.1按研究领域划分 594
22.5.2按复杂程度划分 594
22.5.3随机化的算法 594
22.5.4分支定界与回溯 594
第23章 贪婪算法 595
23.1介绍 595
23.2贪婪算法的策略 595
23.3哪些问题适合用贪婪算法求解 595
23.4贪婪算法是否能应对所有的问题 596
23.5贪婪算法的优点与缺点 596
23.6可以运用贪婪算法的场合 596
23.7理解贪婪算法 596
23.8与贪婪算法有关的问题 599
第24章 分治算法 606
24.1介绍 606
24.2什么是分治策略 606
24.3分治技术是否能用来解决所有的问题 606
24.4用示意图来说明分治技术 607
24.5理解分治技术 607
24.6分治技术的优点 608
24.7分治技术的缺点 608
24.8分治算法的主定理 609
24.9分治算法的适用场合 609
24.10与分治技术有关的问题 609
第25章 动态规划 623
25.1介绍 623
25.2什么是动态规划策略 623
25.3什么样的问题适合用动态规划来解决 624
25.4动态规划技术能否应对所有的问题 624
25.5动态规划的方式 624
25.5.1自下而上的动态规划 624
25.5.2自上而下的动态规划 624
25.5.3两种规划方向的对比 624
25.6动态规划算法示例 625
25.7理解动态规划 625
25.7.1斐波那契数列 625
25.7.2求某数的阶乘 627
25.7.3最长的公共子序列 628
25.8与动态规划有关的问题 631
第26章 复杂度类 668
26.1介绍 668
26.2多项式时间／指数时间 669
26.3什么是判定性问题 669
26.4判定过程 669
26.5什么是复杂度类 669
26.6复杂度类的类型 669
26.6.1 P类 669
26.6.2 NP类 670
26.6.3反NP类 670
26.6.4 P、 NP与反NP之间的关系 670
26.6.5 NP困难类 670
26.6.6 NP完全类 671
26.6.7 P、 NP、反NP、NP困难与NP完全之间的关系 671
26.6.8 P是否等于NP 671
26.7归约 672
第27章 其他概念 675
27.1介绍 675
27.2与位运算有关的技巧 675
27.2.1按位与 675
27.2.2按位或 675
27.2.3按位异或 676
27.2.4左移位 676
27.2.5右移位 676
27.2.6按位取反 676
27.2.7判断第K个二进制位有没有设置（或者说是不是1） 676
27.2.8设置第K个二进制位（也就是将其设为1） 677
27.2.9清除第K个二进制位 （也就是将其设为0） 677
27.2.10切换第K个二进制位 677
27.2.11把值为1且最靠右的二进制位设置成0 677
27.2.12把值为1且最靠右的二进制位标出来 677
27.2.13把值为0且最靠右的二进制位标出来 678
27.2.14判断某数是不是2的幂 678
27.2.15与2的幂相乘 678
27.2.16与2的幂相除 678
27.2.17求出与2的幂相除的余数 678
27.2.18将二进制表示形式反转 678
27.2.19统计值为1的二进制位个数 679
27.2.20创建掩码，以便将尾部连续出现的0标注出来 680
27.2.21把奇数位置上的二进制位与偶数位置上的二进制位互换 680
27.2.22用不做除法的方式来求平均值 680
27.3其他编程问题 680
第28章 非技术问题 686
28.1面试技巧 686
28.2非技术问题举例 688