1、程序员面试模拟试卷 2及答案与解析 1 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 比如将二元查找树 10 / 6 14 / / 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 2 定义栈的数据结构，要求添加一个 min函数，能够得到栈的最小元素。要求函数 min、 push以及 pop的时间复杂度都是 O(1)。 3 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)。 例如输入的数组为 1, -2,
2、 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，因此输出为该子数组的和 18。 4 输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数 22和如下二元树 10 / 5 12 / 4 7 则打印出两条路径： 10, 12和 10, 5, 7。 二元树结点的数据结构定义为： struct BinaryTreeNode / a node in the binary tree int m_nValue; / value of node BinaryTreeNode *m
3、_pLeft; / left child of node BinaryTreeNode *m_pRight; / right child of node ; 程序员面试模拟试卷 2答案与解析 1 【正确答案】 思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调 整所有结点。 思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点
4、已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。 参考代码： 首先我们定义二元查找树结点的数据结构如下： struct BSTreeNode / a node in the binary search tree int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node ; 思路一对应的代码： / / Covert a sub binar
5、y-search-tree into a sorted double-linked list / Input: pNode - the head of the sub tree / asRight - whether pNode is the right child of its parent / Output: if asRight is true, return the least node in the sub-tree / else return the greatest node in the sub-tree / BSTreeNode* ConvertNode(BSTreeNode
6、* pNode, bool asRight) if(!pNode) return NULL; BSTreeNode *pLeft = NULL; BSTreeNode *pRight = NULL; / Convert the left sub-tree if(pNode-m_pLeft) pLeft = ConvertNode(pNode-m_pLeft, false); / Connect the greatest node in the left sub-tree to the current node if(pLeft) pLeft-m_pRight = pNode; pNode-m_
7、pLeft = pLeft; / Convert the right sub-tree if(pNode-m_pRight) pRight = ConvertNode(pNode-m_pRight, true); / Connect the least node in the right sub-tree to the current node if(pRight) pNode-m_pRight = pRight; pRight-m_pLeft = pNode; BSTreeNode *pTemp = pNode; / If the current node is the right chil
8、d of its parent, / return the least node in the tree whose root is the current node if(asRight) while(pTemp-m_pLeft) pTemp = pTemp-m_pLeft; / If the current node is the left child of its parent, / return the greatest node in the tree whose root is the current node else while(pTemp-m_pRight) pTemp =
9、pTemp-m_pRight; return pTemp; / / Covert a binary search tree into a sorted double-linked list / Input: the head of tree / Output: the head of sorted double-linked list / BSTreeNode* Convert(BSTreeNode* pHeadOfTree) / As we want to return the head of the sorted double-linked list, / we set the secon
10、d parameter to be true return ConvertNode(pHeadOfTree, true); 思路二对应的代码： / / Covert a sub binary-search-tree into a sorted double-linked list / Input: pNode - the head of the sub tree / pLastNodeInList - the tail of the double-linked list / void ConvertNode(BSTreeNode* pNode, BSTreeNode* BSTreeNode *
11、pCurrent = pNode; / Convert the left sub-tree if (pCurrent-m_pLeft != NULL) ConvertNode(pCurrent-m_pLeft, pLastNodeInList); / Put the current node into the double-linked list pCurrent-m_pLeft = pLastNodeInList; if(pLastNodeInList != NULL) pLastNodeInList-m_pRight = pCurrent; pLastNodeInList = pCurre
12、nt; / Convert the right sub-tree if (pCurrent-m_pRight != NULL) ConvertNode(pCurrent-m_pRight, pLastNodeInList); / / Covert a binary search tree into a sorted double-linked list / Input: pHeadOfTree - the head of tree / Output: the head of sorted double-linked list / BSTreeNode* Convert_Solution1(BS
13、TreeNode* pHeadOfTree) BSTreeNode *pLastNodeInList = NULL; ConvertNode(pHeadOfTree, pLastNodeInList); / Get the head of the double-linked list BSTreeNode *pHeadOfList = pLastNodeInList; while(pHeadOfList return pHeadOfList; 2 【正确答案】 我 看到这道题目时，第一反应就是每次 push一个新元素时，将栈里所有逆序元素排序。这样栈顶元素将是最小元素。但由于不能保证最后 pu
14、sh进栈的元素最先出栈，这种思路设计的数据结构已经不是一个栈了。 在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次 push一个新元素进栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。 乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被 pop出去，如何才能得到下一个最小元素？ 因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置） 是不够的。我们需要一个辅助栈。每次 push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗） push到辅助栈中；每次 pop一个
15、元素出栈的时候，同时 pop辅助栈。 参考代码： #include #include template class CStackWithMin public: CStackWithMin(void) virtual CStackWithMin(void) T const T void push(const T void pop(void); const T private: Tm_data;/ theelements of stack size_tm_minIndex;/ the indicesof minimum elements ; / get the last element of mu
16、table stack template T / get the last element of non-mutable stack template const T / insert an elment at the end of stack template void CStackWithMin:push(const T / set the index of minimum elment in m_data at the end of m_minIndex if(m_minIndex.size() = 0) m_minIndex.push_back(0); else if(value vo
17、id CStackWithMin:pop() / pop m_data m_data.pop_back(); / pop m_minIndex m_minIndex.pop_back(); / get the minimum element of stack template const T assert(m_minIndex.size() 0); return m_datam_minIndex.back(); 举个例子演示上述代码的运行过程： 步骤 数据栈 辅助栈 最小值 1.push 3 3 0 3 2.push 4 3,4 0,0 3 3.push 2 3,4,2 0,0,2 2 4.p
18、ush 1 3,4,2,1 0,0,2,3 1 5.pop 3,4,2 0,0,2 2 6.pop 3,4 0,0 3 7.push 0 3,4,0 0,0,2 0 讨论：如果思路正确，编写上述代码不是一件很难的事情。但如果能注意一些细节无疑能在面试中加分。比如我在上面的代码中做了如下的工作： ? 用模板类实现。如果别人的元素类型只是 int类型，模板将能给面试官带来好印象； ? 两个版本的 top函数。在很多类中，都需要提供 const和非 const版本的成员访问函数； ? min函数中 assert。把代码写的尽量安全是每个软件公司对程序员的要求； ? 添加一些注释。注释既能提高代码的可
19、读性，又能增加代码量，何乐而不为？ 总之，在面试时如果时间允许，尽量把代码写的漂亮一些。说不定代码中的几个小亮点就能让自己轻松拿到心仪的 Offer。 3 【正确答案】 如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是 ，由于长度为 n的数组有 O(n2)个子数组；而且求一个长度为 n的数组的和的时间复杂度为 O(n)。因此这种思路的时间是 O(n3)。 很容易理解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。基于这样的思路，我们可以写出
20、如下代码。 参考代码： / / Find the greatest sum of all sub-arrays / Return value: if the input is valid, return true, otherwise return false / bool FindGreatestSumOfSubArray ( int *pData, / an array unsigned int nLength, / the length of array int int nCurSum = nGreatestSum = 0; for(unsigned int i = 0; i nGrea
21、testSum) nGreatestSum = nCurSum; / if all data are negative, find the greatest element in the array if(nGreatestSum = 0) nGreatestSum = pData0; for(unsigned int i = 1; i nGreatestSum) nGreatestSum = pDatai; return true; 讨论：上述代码中有两点值得和大家讨论一下： ? 函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志。如果函数返回值的是子数组和的最大值，那么当输入
22、一个空指针是应该返回什么呢？返回 0？那这个函数的用户怎么区分输入无效和子数组和的最大值刚好是 0这两中情况呢？基于这个考虑，本人认为把子数组和的最大值以引用的方式放到参数列表中，同时让函数返回一个函数是否正常执行的标志。 ? 输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时，子数组和 的最大值就是数组中的最大元素。 4 【正确答案】 当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结点并且当前路径的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到父结点
23、。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是根结点到父结点的路径。我们不难看出保存路径的数据结构实际上是一个栈结构，因为路径要与递归调用状态一致，而递归调用本 质就是一个压栈和出栈的过程。 参考代码： / / Find paths whose sum equal to expected sum / void FindPath ( BinaryTreeNode* pTreeNode, / a node of binary tree int expectedSum, / the expected sum std:vector currentSum
24、+= pTreeNode-m_nValue; path.push_back(pTreeNode-m_nValue); / if the node is a leaf, and the sum is same as pre-defined, / the path is what we want. print the path bool isLeaf = (!pTreeNode-m_pLeft if(currentSum = expectedSum for(; iter != path.end(); + iter) std:coutm_pLeft) FindPath(pTreeNode-m_pLe
25、ft, expectedSum, path, currentSum); if(pTreeNode-m_pRight) FindPath(pTreeNode-m_pRight, expectedSum, path, currentSum); / when we finish visiting a node and return to its parent node, / we should delete this node from the path and / minus the nodes value from the current sum currentSum -= pTreeNode-m_nValue; /!I think here is no use path.pop_back();
