程序员面试模拟试卷14
面试题
1.输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
///////////////////////////////////////////////////////////////////////
// Get depth of a binary tree
// Input: pTreeNode – the head of a binary tree
// Output: the depth of a binary tree
///////////////////////////////////////////////////////////////////////
int TreeDepth(SBinaryTreeNode *pTreeNode)
{
// the depth of a empty tree is 0
if(!pTreeNode)
return 0;
// the depth of left sub-tree
int nLeft = TreeDepth(pTreeNode->m_pLeft);
// the depth of right sub-tree
int nRight = TreeDepth(pTreeNode->m_pRight);
// depth is the binary tree
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
解析：这道题本质上还是考查二元树的遍历。
题目给出了一种树的深度的定义。当然，我们可以按照这种定义去得到树的所有路径，也就能得到最长路径以及它的长度。只是这种思路用来写程序有点麻烦。
我们还可以从另外一个角度来理解树的深度。如果一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树呢？那该树的深度就是其左、右子树深度的较大值再加1。
上面的这个思路用递归的方法很容易实现，只需要对遍历的代码稍作修改即可。
2.输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
void Permutation(char* pStr, char* pBegin);
/////////////////////////////////////////////////////////////////////////
// Get the permutation of a string,
// for example, input string abc, its permutation is
// abc acb bac bca cba cab
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr)
{
Permutation(pStr, pStr);
}
/////////////////////////////////////////////////////////////////////////
// Print the permutation of a string,
// Input: pStr – input string
// pBegin – points to the begin char of string
// which we want to permutate in this recursion
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr, char* pBegin)
{
if(!pStr || !pBegin)
return;
// if pBegin points to the end of string,
// this round of permutation is finished,
// print the permuted string
if(*pBegin == ’\\\\0’)
{
printf(\\
解析：这是一道很好的考查对递归理解的编程题，因此在过去一年中频繁出现在各大公司的面试、笔试题中。
我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。
既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。
3.输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);
/////////////////////////////////////////////////////////////////////////
// Devide an array of integers into two parts, odd in the first part,
// and even in the second part
// Input: pData – an array of integers
// length – the length of array
/////////////////////////////////////////////////////////////////////////
void ReorderOddEven(int *pData, unsigned int length)
{
if(pData == NULL || length
本文档预览：3600字符，共21792字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
