程序员面试手册 概念、编程问题及面试题PDF电子书下载

第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