首页 > 全部 > 程序员面试 > 程序员面试模拟试卷14

程序员面试模拟试卷14

本单篇文档共21792字,内容预览3600字,预览为有答案版,源文件无水印,下载后包含无答案空白卷版和有答案版,同时也有计算机类整科真题模拟题,讲义课件,思维导图,易错高频题等下载。
程序员面试 模拟试卷 3129人下载
价格: 2.00 原价:¥8.00
收藏

程序员面试模拟试卷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版点下载

剩余未完,查看全文
收藏
程序员面试模拟试卷14

推荐资源

客服

扫码添加客服微信

热线

官方客服

如遇问题,请联系客服为您解决

电话客服:

客服微信:pujinet

工作时间:9:00-18:00,节假日休息

公众号

扫码关注微信公众号