1、程序员面试-8 及答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：28，分数：100.00)1.什么是泛型编程 （分数：3.00）_2.栈与队列的区别有哪些 （分数：3.00）_3.vector 与 list 的区别有哪些 （分数：3.00）_4.如何实现循环队列 （分数：3.00）_5.如何使用两个栈模拟队列操作 （分数：3.00）_6.如何进行选择排序 （分数：3.00）_7.如何进行插入排序 （分数：3.00）_8.如何进行冒泡排序 （分数：3.00）_9.如何进行归并排序 （分数：3.00）_10.如何进行快速排序 （分数：3.00）_11.如何进行希尔排序 （
2、分数：3.00）_12.如何进行堆排序 （分数：3.00）_13.各种排序算法有什么优劣 （分数：4.00）_14.基础知识 （分数：4.00）_15.如何递归实现二叉树的遍历 （分数：4.00）_16.已知先序遍历和中序遍历，如何求后序遍历 （分数：4.00）_17.如何非递归实现二叉树的后序遍历 （分数：4.00）_18.如何使用非递归算法求二叉树的深度 （分数：4.00）_19.如何判断两棵二叉树是否相等 （分数：4.00）_20.如何判断二叉树是否是平衡二叉树 （分数：4.00）_21.什么是霍夫曼编解码 （分数：4.00）_22.什么是拓扑排序 （分数：4.00）_23.什么是 DF
3、S?什么是 BFS （分数：4.00）_24.如何求关键路径 （分数：4.00）_25.如何求最短路径 （分数：4.00）_26.top K 问题 （分数：4.00）_27.重复问题 （分数：4.00）_28.排序问题 （分数：4.00）_程序员面试-8 答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：28，分数：100.00)1.什么是泛型编程 （分数：3.00）_正确答案：()解析：泛型编程(Generic Programming)的目的是为了发明一种语言机制，能够帮助实现一个通用的标准容器库。通用的标准容器库是指能够实现这样一种功能：例如，用一个 List 类存放
4、所有可能类型的对象，而泛型编程可以让程序员编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。泛型与模板类似，指具有在多种数据类型上皆可操作的含意。 STL 巨大，而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。2.栈与队列的区别有哪些 （分数：3.00）_正确答案：()解析：栈与队列是在程序设计中被广泛使用的两种重要的线性数据结构，都是在一个特定范围的存储单元中存储的数据，这些数据都可以重新被取出使用，与线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表
5、结构。不同的是，栈就像一个很窄的桶先存进去的数据只能最后才能取出来，是 LIFO(Last In First Out，后进先出)，它将进出顺序逆序，即先进后出，后进先出。栈结构如图1 所示。队列像日常排队买东西的人的“队列”，先排队的人先买，后排队的人后买，是 FIFO (First In First Out，先进先出)的，它保持进出顺序一致，即先进先出，后进后出。队列结构如图 2 所示。 图 1 栈结构示意图3.vector 与 list 的区别有哪些 （分数：3.00）_正确答案：()解析：vector 为存储的对象分配一块连续的地址空间，对 vector 中的元素随机访问效率很高。在 v
6、ector中插入或者删除某个元素，需要将现有元素进行复制、移动。如果 vector 中存储的对象很大，或者构造函数复杂，则在对现有元素进行拷贝时开销较大，因为拷贝对象要调用拷贝构造函数。对于简单的小对象，vector 的效率优于 list。vector 在每次扩张容量的时候，将容量扩展 2 倍，这样对于小对象来说，效率是很高的。 list 表示非连续的内存区域，并通过一对指向首尾元素的指针双向链接起来从而允许向前和向后两个方向进行遍历，list 中的对象是离散存储的。在 list 的任意位置插入与删除元素的效率都很高，指针必须被重新赋值，但是不需要用拷贝元素来实现移动。它对随机访问的支持并不好
7、，访问一个元素需要遍历中间的元素，另外每个元素还有两个指针的额外空间开销，随机访问某个元素需要遍历 list。在 list 中插入元素，尤其是在首尾插入元素，效率很高，只需要改变元素的指针即可。 vector 内部使用顺序存储，访问速度快，但是删除数据比较耗费性能。list 内部使用链式存储，访问速度慢，但是删除数据比较快。 一般应遵循下面的原则： 1)需要高效的随机存取，而不在乎插入和删除的效率，使用 vector。 2)需要大量的插入和册 0 除，而不关心随机存取，则应使用 list。 3)需要随机存取，而且关心两端数据的插入和删除，则应使用 deque。4.如何实现循环队列 （分数：3.
8、00）_正确答案：()解析：在队列的顺序存储结构中，除了使用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需要另外设置两个指针 front 和 rear 分别指示队列头元素以及队列尾元素的位置。初始化建空队列时，令 front=rear=0，每当插入新的队列尾元素时，“尾指针增 1”，而每当删除队列头元素时，则执行“头指针增 1”。因此，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。 为充分利用向量空间，克服“假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue
9、)。循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear 来判别队列是“空”还是“满”。 解决这个问题的方法至少有两种： 1)另外设置一个标志位来区别队列是“空”还是“满”。 2)少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)”上作为队列呈“满”状态的标志。队满时：(rear+1)%n=front，n 为队列长度(所用数组大小)，由于 rear、front 均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。 算法示例如下： #define MAXSIZE 1000
10、 typedef int ElemType; typedef struct ElemType dataMAXSIZE; int front; int rear; CircSeqQueue; 顺序循环队列的初始化 void QueueInitial(CircSeqQueue *pQ) pQ-front=pQ-“rear=0; 顺序循环队列判空 int IsEmpty(CircSeqQueue *pQ) return pQ-front=pQ-rear; 顺序循环队列判满 int IsFull(CircSeqQueue *pQ) return (pQ-rear+1)%MAXSIZE= =pQ-fro
11、nt; 元素进队列 void EnQueue(CircSeqQueue *pQ,ElemType e) if(IsFull(pQ) printf(“列队溢出!/n“); exit(1); pQ-rear=(pQ-rear+1)%MAXSIZE; pQ-datapQ-rear=e; 元素出队列 ElemType DeQueue(CircSeqQueue *pQ) if(IsEmpty(pQ) printf(“空队列!/n“); exit(1); pQ-front=-(pQ-front+1)%MAXSIZE; return pQ-datapQ-front; 取对头元素 ElemType GetFr
12、ont(CircSeqQueue *pQ) if(IsEmpty(pQ) printf(“队列为空!/n“); exit(1); return pQ-data(pQ-front+1)%MAXSIZE; 循环队列置空 void MakeEmpty(CircSeqQueue *pQ) pQ-front=pQ-rear=0;5.如何使用两个栈模拟队列操作 （分数：3.00）_正确答案：()解析：题目要求用两个栈来模拟队列，栈 A 与栈 B 模拟队列 Q，A 为插入栈，B 为弹出栈，以实现队列 Q。 假设 A 和 B 都为空，可以认为栈 A 提供入队列的功能，栈 B 提供出队列的功能。 入队列：入栈
13、A。 出队列分两种情况考虑： 1)如果栈 B 不为空，则直接弹出栈 B 的数据。 2)如果栈 B 为空，则依次弹出栈 A 的数据，放入栈 B 中，再弹出栈 B 的数据。 #includeiostream #includestack using namespace std; template typename T class QueueByDoubleStack public: size_t size(); bool empty(); void push(T t); void pop(); T top(); private: stackT s1; stackT s2; ; template ty
14、pename T size_t QueueByDoubleStackT:size() retum s1.size()+s2.size(); template typename T bool QueueByDoubleStackT:empty() return s1.empty() template typename T void QueueByDoubleStackT:push(T t) s1.push(t); template typename T void QueueByDoubleStackT:pop() if (s2.empty() while(!s1.empty() s2.push(
15、s1.top(); s1.pop(); s2.pop(); template typename T T QueueByDoubleStackT:top() if(s2.empty() while(!s1.empty() s2.push(s1.top(); s1.pop(); return s2.top(); int main() QueueByDoubleStackint q; for (int i=0;i10;+i) q.push(i); while(!q.empty() coutq.top() “; q.pop(); coutendl; return 0; 程序输出结果： 0 1 2 3
16、4 5 6 7 8 9 引申：如何使用两个队列实现栈? 可以采用两种方法实现，入栈：所有元素依次入队列 q1。例如，将 A、B、C、D 四个元素入栈，从队列尾部到队列首部依次为 D、C、B、A，出栈的时候判断栈元素个数是否为 1，如果为 1，则队列 q1 出列；如果不为 1，则队列 q1 所有元素出队列，入队列 q2，最后一个元素不入队列 B，输出该元素，队列 q2 所有元素入队列 q1。例如，将 D、C、B、A 出列，D 输出来，C、B、A 入队列 q2，最后返回到队列 q1 中，实现了后进先出。6.如何进行选择排序 （分数：3.00）_正确答案：()解析：选择排序是一种简单直观的排序算法，
17、它的基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。以数组38,65,97,76,13,27,49)为例，具体步骤如下： 第一趟排序后：13 65 97 76 38 27 49 第二趟排序后：13 27 97 76 38 65 49 第三趟排序后：13 27 38 76 97 65 49 第四趟排序后：13 27 38 4997 65 76 第五趟排序后：13 27 38 49 65 97 76 第
18、六趟排序后：13 27 38 49 65 76 97 最后排序结果：13 27 38 49 65 76 97 程序示例如下： #includestdio.h void SelectSort(int *a,int n) int i; int j; int temp=0; int flag=0; for(i=0;in-1;i+) temp=ai; flag=i; for(j=i+1;jn;j+) if(ajtemp) temp=aj; flag=j; if(flag!=i) aflag=ai; ai=temp; int main() int i=0; int a=5,4,9,8,7,6,0,1,3
19、,2; int len=sizeof(a)/sizeof(a0); SelectSort(a, len); for(i=0; ilen; i+) printf(“%d“, ai); printf(“/n“); return 0; 程序输出结果： 0 1 2 3 4 5 6 7 8 9 从简单选择排序的过程来看，它的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。无论是最好情况，还是最差情况，其比较次数都是一样的，第 i 趟排序需要进行 n-i 次。而对于交换次数而言，最好的情况是有序，需要交换 0 次；最差的情况，即逆序时，交换次数为 n-1 次，基于最终的排序时间是比较与交换的次数
20、总和，因此总的时间复杂度依然为 O(n 2 )。7.如何进行插入排序 （分数：3.00）_正确答案：()解析：对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列；接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。以数组38，65，97，76，13，27，49为例，直接插入排序具体步骤如下： 第一步插入 38 以后：38 65 97 76 13 27 49 第二步插入 65 以后：38 65 97 76 13 27 49 第三步插入 97 以后：38 65 97 76 13 27 49 第四步插入
21、76 以后：38 65 76 97 13 27 49 第五步插入 13 以后：13 38 65 76 97 27 49 第六步插入 27 以后：13 27 38 65 76 97 49 第七步插入 49 以后：13 27 38 49 65 76 97 程序示例如下： #includestdio.h void InsertSort(int par_array,int array_size) int i,j; int temp; for(i=1;iarray_size;i+) temp=par_arrayi; for(j=i-1;j=0;j-) if(temppar_arrayj) par_arr
22、ayj+1=par_arrayj; else break; par arrayj+1=temp; int main() int i=0; int a =5,4,9,8,7,6,0,1,3,2; int len=sizeof(a)/sizeof(a0); InsertSort(a, len); for(i=0;ilen; i+) printf(“%d“, ai); printf(“n“); return 0; 程序输出结果： 0 1 2 3 4 5 6 7 8 98.如何进行冒泡排序 （分数：3.00）_正确答案：()解析：冒泡排序顾名思义就是整个过程就像气泡一样往上升，单向冒泡排序的基本思想是
23、(假设由小到大排序)：对于给定的 n 个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换其位置，进行一轮比较和换位后，n 个记录中的最大记录将位于第 n 位；然后对前(n-1)个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个时为止。 以数组36，25，48，12，25，65，43，57为例，具体排序过程如下： 一趟排序的过程如下： R136 25 25 25 25 25 25 25 R225 36 36 36 36 36 36 36 R348 48 48 12 12 12 12 12 R412 12 12 48 25 25 25 25 R525
24、 25 25 25 48 48 48 48 R665 65 65 65 65 65 43 43 R743 43 43 43 43 43 65 57 R857 57 57 57 57 57 57 65 则经过多趟排序后的结果如下： 初始状态：36 25 48 12 25 65 43 57 1 趟排序：25 36 12 25 48 43 57 65 2 趟排序：25 12 25 36 43 4857 65 3 趟排序：12 25 25 36 4348 57 65 4 趟排序：12 25 25 3643 48 57 65 5 趟排序：12 25 2536 43 48 57 65 6 趟排序：12 2
25、525 36 43 48 57 65 7 趟排序：1225 25 36 43 48 57 65 程序示例如下： #includestdio.h void Swap(int temp=a; a=b; b=temp; void BubbleSort(int array,int len) int i,j; for(i=0;ilen-1;+i) for(i=len-1;ji;-j) if(arrayjarrayj-1) Swap(arrayj,arrayj-1); int main() int i=0; int a=5,4,9,8,7,6,0,1,3,2; int len=sizeof(a)/size
26、of(a0); BubbleSort(a, len); for(i=0;ilen;i+) printf(%d“,ai); printf(“/n“); return 0; 程序输出结果： 0 1 2 3 4 5 6 7 8 9 引申：如何进行双向冒泡排序? 双向冒泡排序是冒泡排序的一种优化，它的基本思想是首先将第一个记录的关键字和第二个记录的关键字进行比较，若为“逆序”(即 L.r1.keyL.r2.key)，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依次类推，直至第 n-1 个记录的关键字和第 n 个记录的关键字比较过为止。这是第一趟冒泡排序，其结果是使得关键字最大的记录被安置
27、到最后一个记录的位置上。 第一趟排序之后进行第二趟冒泡排序，将第 n-2 个记录的关键字和第 n-1 个记录的关键字进行比较，若为“逆序”(即 L.rn-1.keyL.rn-2.key)，则将两个记录交换，然后比较第 n-3 个记录和 n-2 个记录的关键字。依次类推，直至第 1 个记录的关键字和第 2 个记录的关键字比较过为止。其结果是使得关键字最小的记录被安置到第一个位置上。 再对其余的 n-2 个记录进行上述同样的操作，其结果是使关键字次大的记录被安置到第 n-1 个记录的位置，使关键字次小的记录被安置到第 2 个记录的位置。 一般地，第 i 趟冒泡排序是：若 i 为奇数，则从 L.ri
28、/2+1L.rn-i/2依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这 n-i+1 个记录中关键字最大的记录被交换到第 n-i/2 的位置上；若 i 为偶数，则从 L.rn-i/2L.ri/2依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这 n-i+1 个记录中关键字最小的记录被交换到第 i/2 的位置上。整个排序过程需要进行 K(1Kn)趟冒泡排序，同样判别冒泡排序结束的条件仍然是“在一趟排序过程中没有进行过交换记录的操作”。 程序示例如下： #includestdio.h void Swap(int temp=a; a=b; b=temp; voi
29、d Bubble2Sort(int array,int length) int left=1; int right=length-1; int t; do 正向的部分 for(int i=right;i=left;i-) if(arrayjarrayi-1) Swap(arrayi,arrayi-1); t=i; left=t+1; 反向的部分 for(i=left;iright+1;i+) if(arrayiarrayi-1) Swap(arrayi,arrayi-1); t=i; right=t-1; while(left=right); int main() int i=0; int a
30、=5,4,9,8,7,6,0,1,3,2; int len=sizeof(a)/sizeof(a0); Bubble2Sort(a, len); for(i=0;ilen;i+) printf(“%d“, ai); printf(“/n“); return 0; 程序输出结果： 0 1 2 3 4 5 6 7 8 99.如何进行归并排序 （分数：3.00）_正确答案：()解析：归并排序是利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思，即递归地将数组折半地分离为单个数组。例如，数组2，
31、6，1，0会先折半，分为2，6和1，0两个子数组，然后再折半将数组分离，分为2，6和1，0。“并”就是将分开的数据按照从小到大或者从大到小的顺序在放到一个数组中。如上面的2、6合并到一个数组中是2，6，1、0合并到一个数组中是0，1，然后再将2，6和0，1合并到一个数组中即为0，1，2，6。 具体而言，归并排序算法的原理如下：对于给定的一组记录(假设共有 n 个记录)，首先将每两个相邻的长度为 1 的子序列进行归并，得到 n/2(向上取整)个长度为 2 或 1 的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列为止。 所以，归并排序的关键就是两步：第一步，划分子表；第二步，合并
32、半子表。以数组49，38，65，97，76，13，27为例，排序过程如下： 10.如何进行快速排序 （分数：3.00）_正确答案：()解析：快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。其原理是：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。 具体算法步骤如下： 1)分解：将输入的序列 arraym,.,n划分成两个非空子序列 arraym,.,k和 arrayk+1,.,n，使arraym,.,k中任一
33、元素的值不大于 arrayk+1,.,n中任一元素的值。 2)递归求解：通过递归调用快速排序算法分别对 arraym,.,k和 arrayk+1,.,n进行排序。 3)合并：由于对分解出的两个子序列的排序是就地进行的，所以在 arraym,.,k和 arrayk+1,.,n都排好序后，不需要执行任何计算 arraym,.,n就已排好序。 以数组49，38，65，97，76，13，27，49为例。 第一趟排序过程如下： 初始化关键字49 38 65 97 76 13 27 49 第一次交换后：27 38 65 97 76 13 49 49 第二次交换后：27 38 49 97 76 13 65
34、49 j 向左扫描，位置不变，第三次交换后：27 38 13 97 76 49 65 49 i 向右扫描，位置不变，第四次交换后：27 38 13 49 76 97 65 49 j 向左扫描27 38 13 49 76 97 65 49 整个排序过程如下： 初始化关键字49 38 65 97 76 13 27 49 一趟排序之后：27 38 134976 97 65 49 二趟排序之后：1327384949 657697 三趟排序之后：13 27 38 49 496576 97 最后的排序结果：13 27 38 49 49 65 76 97 程序示例如下： #include stdio.h v
35、oid Sort(int array, int low, int high) int i,j; int index; if(low=high) return; i=low; j=high; index=arrayi; while(ij) while(ij if(ij) arrayi+=arrayj; while(ij if(ij) arrayj-=arrayi; arrayi=index; Sort(array, low, i-1); Sort(array, i+1, high); void QuickSort(int array, int len) Sort(array, 0, len-1)
36、; int main() int i=0; int a=5,4,9,8,7,6,0,1,3,2; int len=sizeof(a)/sizeof(a0); QuickSort(a,len); for(i=0; ilen;i+) printf(“%d“,ai); printf(“/n“); return 0; 程序输出结果： 0 1 2 3 4 5 6 7 8 9 当初始的序列整体或局部有序时，快速排序的性能将会下降，此时快速排序将退化为冒泡排序。 快速排序的相关特点如下： (1)最坏时间复杂度 最坏情况是指每次区间划分的结果都是基准关键字的左边(或右边)序列为空，而另一边的区间中的记录项仅比排序前少了一项，即选择的基准关键字是待排序的所有记录中最小或者最大的。例如，若选取第一个记录为基准关键字，当初始序列按递增顺序排列时，每次选择的基准关键字都是所有记录中的最小者，这时记录与基准关键字的比较次数会增多。因此，在这种情况下，需要进行(n-1)次区间划分。对于第k(0kn)次区间划分，划分前的序列长度为(n-k+1)，需要进行(n-k)次记录的比较。当 k 从 1(n-1)时，进行的比较次数总共为
