程序员面试手册：概念、编程问题及面试题

图书标准信息

• 作者 [印]纳拉辛哈·卡鲁曼希（Narasimha Karumanchi） 著；爱飞翔 译
• 出版社 机械工业出版社
• 出版时间 2018-03
• 版次 1
• ISBN 9787111590118
• 定价 99.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 692页

【内容简介】

本书是面向程序员面试的参考书，书中囊括了各种编程解决方案，可以用来有效地应对面试、考试及校园招聘。内容涵盖了编程基础、架构设计、数据库技术、数据结构及算法等主要的话题，而且还介绍了趣味谜题以及非技术的问题。

【目录】

Contents 目　录 

译者序 

前　言 

致　谢 

第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　Perl94 

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　Python118 

2.5.1　什么是Python118 

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与RARP198 

5.13　子网199 

5.14　路由器的工作原理200 

5.15　单播、广播、多播201 

5.16　tracert/traceroute及ping命令的工作原理202 

5.17　什么是QoS203 

第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与BFS456 

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