1、是否构成群 。4、 设G是n阶完全图，则G的边数m= 。5、 如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行 次这个加法指令。十、 选择 20% （每小题 2分）1、 在有理数集Q上定义的二元运算*，有，则Q中满足（ ）。A、 所有元素都有逆元； B、只有唯一逆元； C、时有逆元； D、所有元素都无逆元。2、 设S=0，1，*为普通乘法，则是（ ）。A、 半群，但不是独异点； B、只是独异点，但不是群；C、群； D、环，但不是群。3、图 给出一个格L，则L是（ ）。A、分配格； B、有补格； C、布尔格； D、 A,B,C都不对。3、 有向图D= ，则
2、长度为2的通路有（ ）条。A、0； B、1； C、2； D、3 。4、 在Peterson图中，至少填加（ ）条边才能构成Euler图。A、1； B、2； C、4； D、5 。十一、 判断 10% （每小题 2分）1、 在代数系统中如果元素的左逆元存在，则它一定唯一且。（ ）2、 设是群的子群，则中幺元e是中幺元。（ ）3、 设， +,为普通加法和乘法，则代数系统是域。（ ）4、 设G=是平面图，|V|=v, |E|=e，r为其面数，则v-e + r=2。（ ）5、 如果一个有向图D是欧拉图，则D是强连通图。（ ）四、证明 46%1、 设，是半群，e是左幺元且，使得，则是群。（10分）2、 循
3、环群的任何非平凡子群也是循环群。（10分）3、 设aH和bH是子群H在群G中的两个左陪集，证明：要末，要末 。（8分）4、 设，是一个含幺环，|A|3，且对任意，都有，则不可能是整环（这时称是布尔环）。（8分）5、 若图G不连通，则G的补图是连通的。（10分）五、布尔表达式 8%设是布尔代数上的一个布尔表达式，试写出其的析取范式和合取范式。六、图的应用 16%1、 构造一个结点v与边数e奇偶性相反的欧拉图。（6分）2、 假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的
4、编码信息。（10分）答案十一、 填空 10%（每小题2分）+30120012112022011、；2、，；3、 是；4、；5、9十二、 选择 10%（每小题 2分）题目12345答案CBDBD十三、 判断 10%（每小题2分）题目12345答案NYYNY十四、 证明 46%1、（10分）证明：（1）(2) e 是之幺元。事实上：由于e是左幺元，现证e是右幺元。（3）由（2），（3）知：为群。2、（10分）证明：设是循环群,G=(a)，设是的子群。且，则存在最小正整数m，使得：，对任意，必有，故： 即：所以但m是使的最小正整数，且，所以r=0即：这说明S中任意元素是的乘幂。 所以是以为生成元的循
5、环群。3、（8分）证明：对集合，只有下列两种情况：（1）； （2）对于，则至少存在，使得，即有，这时任意，有，故有同理可证：所以 4、（8分）证明：反证法：如果，是整环，且有三个以上元素，则存在即有：这与整环中无零因子条件矛盾。因此不可能是整环。5、（10分）证明：因为G=不连通，设其连通分支是，则有两种情况：（1） u , v，分别属于两个不同结点子集Vi，Vj，由于G(Vi) , G(Vj)是两连通分支，故(u , v)在不G中，故u , v 在中连通。（2） u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故(u , w),(w , v )均在中，故邻接边( u ,
6、w ) ( w , v ) 组成的路连接结点u和v，即u , v在中也是连通的。五、布尔表达式 8%函数表为：00000011010001111000101111011111析取范式：合取范式：六、 树的应用 16%1、（6分）解：2、（10分）解：根据权数构造最优二叉树：传输它们的最佳前缀码如上图所示，happy new year的编码信息为：10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最优二叉树求解过程如下：试卷十五试题与答案十二、 填空 20% （每空 2分）1、 如果有限集合A有n个元素，则|2A|= 。2、 某集合有101个
7、元素，则有 个子集的元素为奇数。3、 设S=a1，a2,，a8，Bi是S的子集，由B17表达的子集为 ， 子集a2,a6,a7规定为 。4、 由A1，A2,，An，生成的最小集的形式为 ，它们的并为 集，它们的交为 集。5、 某人有三个儿子，组成集合A=S1,S2,S3，在A上的兄弟关系具有 性质。6、每一个良序集必为全序集，而 全序集必为良序集。7、若是函数，则当f是的 ，是f的逆函数。十三、 选择 15% （每小题 3分）1、 集合的幂集为（ ）。A、；B、；C、；D、2、 下列结果正确的是（ ）。A、；B、；C、；D、；E、；F、AA=A 。3、 集合的最小集范式为（ ）（由A、B、C生
8、成）。A、 ； B、；C、 ； D、。4、 在（ ） 下有。A、；B、；C、；D、5、 下列二元关系中是函数的有（ ）。A、；B、；C、。三、 15% 用Warshall算法，对集合A=1，2，3，4，5微软等公司数据结构微软等公司数据结构+算法面试算法面试 100 题题(第第 1-100 题题)首次完整亮相首次完整亮相 作者:July、2010 年 12 月 6 日。 1. 更新： 现今， 这 100 题的答案已经全部整理出来了， 微软面试 100 题 2010 年版全部答案集锦： 2. 关于此 100 道面试题的所有一切详情，包括答案，资源下载，帖子维护， 答案更新，都请参考此文：横空出世
9、，席卷横空出世，席卷 Csdn 评微软等数据结构评微软等数据结构+ 算法面试算法面试 100 题题。 3. 以下 100 题中有部分题目整理自何海涛的博客 （ - 微软等 100 题系列 V0.1 版终于结束了。 从 2010 年 10 月 11 日当天最初发表前 40 题以来， 直至此刻， 整理这 100 题， 已有近 2 个月。 2 个月，因为要整理这 100 题，很多很多其它的事都被我强迫性的搁置一旁， 如今，要好好专心去做因这 100 题而被耽误的、其它的事了。 这微软等数据结构+算法面试 100 题系列系列(是的，系列)，到底现在、或此刻、或未来，对初 学者有多大的意义， 在此，我就
10、不给予评说了。 由他们自己来认定。所谓，公道自在人心，我相信这句话。 任何人，对以下任何资料、题目、或答案，有任何问题，欢迎联系我。 作者邮箱： zhoulei0907 786165179 作者声明： 转载或引用以下任何资料、或题目，请注明作者本人 July 及出处。 向您的厚道致敬，谢谢。 好了，请享受这完完整整的 100 题吧，这可是首次完整亮相哦。:D。 - 1.把二元查找树转变成排序的双向链表（树） 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / / 6 14 / / / / 4 8 12 16 转换成双向链
11、表 4=6=8=10=12=14=16。 首先我们定义的二元查找树 节点的数据结构如下： struct BSTreeNode int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node ; 2.设计包含 min 函数的栈（栈） 定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。 要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。 3.求子数组的最大和（数组） 题目： 输入一个整形数组，数
12、组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为 O(n)。 例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2， 因此输出为该子数组的和 18。 4.在二元树中找出和为某一值的所有路径（树） 题目：输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如 输入整数 22 和如下二元树 10 / / 5 12 / 4 7 则打印出两条路径：10, 12 和 10,
13、5, 7。 二元树节点的数据结构定义为： struct BinaryTreeNode / a node in the binary tree int m_nValue; / value of node BinaryTreeNode *m_pLeft; / left child of node BinaryTreeNode *m_pRight; / right child of node ; 5.查找最小的 k 个元素（数组） 题目：输入 n 个整数，输出其中最小的 k 个。 例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4 个数字为 1，2，3 和 4。 第 6 题（
14、数组） 腾讯面试题： 给你 10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数 要求下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下： 【0，1，2，3，4，5，6，7，8，9】 举一个例子， 数值: 0,1,2,3,4,5,6,7,8,9 分配: 6,2,1,0,0,0,1,0,0,0 0 在下排出现了 6 次，1 在下排出现了 2 次， 2 在下排出现了 1 次，3 在下排出现了 0 次. 以此类推. 第 7 题（链表） 微软亚院之编程判断俩个链表是否相交 给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。 为了简化问题，我们假设俩个链表均不带
15、环。 问题扩展： 1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列? 第 8 题（算法） 此贴选一些 比较怪的题，由于其中题目本身与算法关系不大，仅考考思维。特此并作一 题。 1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关， 这两个房间是 分割开的，从一间里不能看到另一间的情况。 现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。 有什么办法呢？ 2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一 块。 如果你只能将金条切割两次，你怎样分给这些工人? 3. 用一种算法来颠倒一个链接表的顺序。现在在
16、不用递归式的情况下做一遍。 用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。 用一种算法整理一个数组。你为什么选择这种方法? 用一种算法使通用字符串相匹配。 颠倒一个字符串。优化速度。优化空间。 颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”， 实现速度最快，移动最少。 找到一个子字符串。优化速度。优化空间。 比较两个字符串，用 O(n)时间和恒量空间。 假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有 的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现两次外，其他所有数字只出 现一次。假设你只能对这个数组
17、做一次处理，用一种算法找出重复的那个数字。如果你在运 算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗? 不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。 第 9 题（树） 判断整数序列是不是二元查找树的后序遍历结果 题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回 true，否则返回 false。 例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / / 6 10 / / / / 5 7 9 11 因此返回 true。 如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 fals
18、e。 第 10 题（字符串） 翻转句子中单词的顺序。 题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。 句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。 例如输入“I am a student.”，则输出“student. a am I”。 第 11 题（树） 求二叉树中节点的最大距离. 如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的， 我们姑且定义距离为两节点之间边的个数。 写一个程序， 求一棵二叉树中相距最远的两个节点之间的距离。 第 12 题（语法） 题目：求 1+2+n， 要求不能使用乘除法、 for、 while、 if、 else、
19、 switch、 case 等关键字以及条件判断语句 （A?B:C） 。 第 13 题（链表）： 题目：输入一个单向链表，输出该链表中倒数第 k 个结点。链表的倒数第 0 个结点为链表 的尾指针。 链表结点定义如下： struct ListNode int m_nKey; ListNode* m_pNext; ; 第 14 题（数组）： 题目：输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。 例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=
20、15，因此输出 4 和 11。 第 15 题（树）： 题目：输入一颗二元查找树，将该树转换为它的镜像， 即在转换后的二元查找树中，左子树的结点都大于右子树的结点。 用递归和循环两种方法完成树的镜像转换。 例如输入： 8 / / 6 10 / / 5 7 9 11 输出： 8 / / 10 6 / / 11 9 7 5 定义二元查找树的结点为： struct BSTreeNode / a node in the binary search tree (BST) int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of n
21、ode BSTreeNode *m_pRight; / right child of node ; 第 16 题（树）： 题目（微软）： 输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 例如输入 8 / / 6 10 / / / / 5 7 9 11 输出 8 6 10 5 7 9 11。 第 17 题（字符串）： 题目：在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff，则输出 b。 分析：这道题是 2006 年 google 的一道笔试题。 第 18 题（数组）： 题目：n 个数字（0,1,n-1）形成一个圆圈，从数字 0 开始， 每次从这
22、个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个 数字）。 当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。 求出在这个圆圈中剩下的最后一个数字。 July：我想，这个题目，不少人已经 见识过了。 第 19 题（数组、递归）： 题目：定义 Fibonacci 数列如下： / 0 n=0 f(n)= 1 n=1 / f(n-1)+f(n-2) n=2 输入 n，用最快的方法求该数列的第 n 项。 分析：在很多 C 语言教科书中讲到递归函数的时候，都会用 Fibonacci 作为例子。 因此很多程序员对这道题的递归解法非常熟悉，但.呵呵，你知道的。 第 20
23、 题（字符串）： 题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。 例如输入字符串345，则输出整数 345。 第 21 题（数组） 2010 年中兴面试题 编程求解： 输入两个整数 n 和 m，从数列 1，2，3.n 中 随意取几个数, 使其和等于 m ,要求将其中所有的可能组合列出来. 第 22 题（推理）： 有 4 张红色的牌和 4 张蓝色的牌，主持人先拿任意两张，再分别在 A、B、C 三人额头上贴 任意两张牌， A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的 牌， A 说不知道，B 说不知道，C 说不知道，然后 A 说知道了。 请教如何推
24、理，A 是怎么知道的。 如果用程序，又怎么实现呢？ 第 23 题（算法）： 用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。 3D 坐标系 原点(0.0,0.0,0.0) 圆形: 半径 r = 3.0 圆心 o = (*.*, 0.0, *.*) 正方形: 4 个角坐标; 1:(*.*, 0.0, *.*) 2:(*.*, 0.0, *.*) 3:(*.*, 0.0, *.*) 4:(*.*, 0.0, *.*) 第 24 题（链表）： 链表操作，单链表就地逆置， 第 25 题（字符串）： 写一个函数,它的原形是 int continumax(char *outputstr,char
25、 *intputstr) 功能： 在字符串中找出连续最长的数字串，并把这个串的长度返回， 并把这个最长数字串付给其中一个函数参数 outputstr 所指内存。 例如：abcd12345ed125ss123456789的首地址传给 intputstr 后，函数将返回 9， outputstr 所指的值为 123456789 26.左旋转字符串（字符串） 题目： 定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。 如把字符串 abcdef 左旋转 2 位得到字符串 cdefab。请实现字符串左旋转的函数。 要求时间对长度为 n 的字符串操作的复杂度为 O(n)，辅助内存为 O(
26、1)。 27.跳台阶问题（递归） 题目：一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。 求总共有多少总跳法，并分析算法的时间复杂度。 这道题最近经常出现，包括 MicroStrategy 等比较重视算法的公司 都曾先后选用过个这道题作为面试题或者笔试题。 28.整数的二进制表示中 1 的个数（运算） 题目：输入一个整数，求该整数的二进制表达中有多少个 1。 例如输入 10，由于其二进制表示为 1010，有两个 1，因此输出 2。 分析： 这是一道很基本的考查位运算的面试题。 包括微软在内的很多公司都曾采用过这道题。 29.栈的 push、pop 序列（栈） 题目：输入两个整
27、数序列。其中一个序列表示栈的 push 顺序， 判断另一个序列有没有可能是对应的 pop 顺序。 为了简单起见，我们假设 push 序列的任意两个整数都是不相等的。 比如输入的 push 序列是 1、2、3、4、5，那么 4、5、3、2、1 就有可能是一个 pop 系列。 因为可以有如下的 push 和 pop 序列： push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop， 这样得到的 pop 序列就是 4、5、3、2、1。 但序列 4、3、5、1、2 就不可能是 push 序列 1、2、3、4、5 的 pop 序列。 30.在从 1 到
28、 n 的正数中 1 出现的次数（数组） 题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。 例如输入 12， 从 1 到 12 这些整数中包含 1 的数字有 1， 10， 11 和 12， 1 一共出现了 5 次。 分析：这是一道广为流传的 google 面试题。 31.华为面试题（搜索）： 一类似于蜂窝的结构的图，进行搜索最短路径（要求 5 分钟） 32.（数组、规划） 有两个序列 a,b，大小都为 n,序列元素的值任意整数，无序； 要求：通过交换 a,b 中的元素，使序列 a 元素的和与序列 b 元素的和之间的差最小。 例如: var a=100,99
29、,98,1,2, 3; var b=1, 2, 3, 4,5,40; 33.（字符串） 实现一个挺高级的字符匹配算法： 给一串很长字符串，要求找到符合要求的字符串，例如目的串：123 1*3*2 ,12*3 这些都要找出来 其实就是类似一些和谐系统。 34.（队列） 实现一个队列。 队列的应用场景为： 一个生产者线程将 int 类型的数入列，一个消费者线程将 int 类型的数出列 35.（矩阵） 求一个矩阵中最大的二维矩阵(元素和最大).如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3 要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出
30、关键代码 第 36 题-40 题（有些题目搜集于 CSDN 上的网友，已标明）： 36.引用自网友：longzuo（运算） 谷歌笔试： n 支队伍比赛，分别编号为 0，1，2。n-1，已知它们之间的实力对比关系， 存储在一个二维数组 wnn中，wij 的值代表编号为 i，j 的队伍中更强的一支。 所以 wij=i 或者 j，现在给出它们的出场顺序，并存储在数组 ordern中， 比如 ordern = 4,3,5,8,1.，那么第一轮比赛就是 4 对 3， 5 对 8。. 胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排， 下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能
31、是 4 对 5,直至出现第一名 编程实现，给出二维数组 w，一维数组 order 和 用于输出比赛名次的数组 resultn， 求出 result。 37.（字符串） 有 n 个长为 m+1 的字符串， 如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配， 则两个字符串可以联接， 问这 n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。 38.（算法） 百度面试： 1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用 x 次天平， 最多可以从 y 个小球中找出较轻的那个，求 y 与 x 的关系式。 2.有一个很大很大的输入流，大到没有存储器可
32、以将其存储下来， 而且只输入一次，如何从这个输入流中随机取得 m 个记录。 3.大量的 URL 字符串，如何从中去除重复的，优化时间空间复杂度 39.（树、图、算法） 网易有道笔试： (1). 求一个二叉树中任意两个节点间的最大距离， 两个节点的距离的定义是 这两个节点间边的个数， 比如某个孩子节点和父节点间的距离是 1，和相邻兄弟节点间的距离是 2，优化时间空间复 杂度。 (2). 求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边， 有向图不再连通，描述算法。 40.百度研发笔试题（栈、算法） 引用自：zp155334877 1)设计一个栈结构，满足一下条件：min，pus
33、h，pop 操作的时间复杂度为 O(1)。 2)一串首尾相连的珠子(m 个)，有 N 种颜色(N2-3 和 2-3-5 并为 1-2-3-5 另外只能输出结果，不能修改两个链表的数据。 43.递归和非递归俩种方法实现二叉树的前序遍历。 44.腾讯面试题（算法）： 1.设计一个魔方（六面）的程序。 2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。 请用 5 分钟时间，找出重复出现最多的前 10 条。 3.收藏了 1 万条 url，现在给你一条 url，如何找出相似的 url。（面试官不解释何为相似） 45.雅虎（运算、矩阵）： 1.对于一个整数矩阵，存在一种运算，对矩阵中任意
34、元素加一时，需要其相邻（上下左右） 某一个元素也加一， 现给出一正数矩阵， 判断其是否能够由一个全零矩阵经过上述运算得到。 2.一个整数数组，长度为 n，将其分为 m 份，使各份的和相等，求 m 的最大值 比如3，2，4，3，6 可以分成3，2，4，3，6 m=1; 3,62,4,3 m=2 3,32,46 m=3 所以 m 的最大值为 3 46.搜狐（运算）： 四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（） 47.创新工场（算法）： 求一个数组的最长递减子序列 比如9，4，3，2，5，4，3，2的最长递减子序列为9，5， 4，3，2 48.微软（运算）： 一个数组是
35、由一个递减数列左移若干位形成的，比如4，3，2，1，6，5 是由6，5，4，3，2，1左移两位形成的，在这种数组中查找某一个数。 49.一道看上去很吓人的算法面试题（排序、算法）： 如何对 n 个数进行排序，要求时间复杂度 O(n)，空间复杂度 O(1) 50.网易有道笔试（sorry，与第 39 题重复）： 1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是 这两个节点间边 的个数， 比如某个孩子节点和父节点间的距离是 1，和相邻兄弟节点间的距离是 2，优化时间空间复 杂度。 2.求一个有向连通图的割点，割点的定义是， 如果除去此节点和与其相关的边，有向图不再连通，描述算法。
36、 - 51.和为 n 连续正数序列（数组）。 题目：输入一个正数 n，输出所有和为 n 连续正数序列。 例如输入 15， 由于 1+2+3+4+5=4+5+6=7+8=15， 所以输出 3 个连续序列 1-5、 4-6 和 7-8。 分析：这是网易的一道面试题。 52.二元树的深度（树）。 题目：输入一棵二元树的根结点，求该树的深度。 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为 树的深度。 例如：输入二元树： 10 / / 6 14 / / / 4 12 16 输出该树的深度 3。 二元树的结点定义如下： struct SBinaryTreeNode /
37、a node of the binary tree int m_nValue; / value of node SBinaryTreeNode *m_pLeft; / left child of node SBinaryTreeNode *m_pRight; / right child of node ; 分析：这道题本质上还是考查二元树的遍历。 53.字符串的排列（字符串）。 题目：输入一个字符串，打印出该字符串中字符的所有排列。 例如输入字符串 abc，则输出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。 分析：这是一道很好的考查对递归理
38、解的编程题， 因此在过去一年中频繁出现在各大公司的面试、笔试题中。 54.调整数组顺序使奇数位于偶数前面（数组）。 题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分， 所有偶数位于数组的后半部分。要求时间复杂度为 O(n)。 55.（语法） 题目：类 CMyString 的声明如下： class CMyString public: CMyString(char* pData = NULL); CMyString(const CMyString CMyString(void); CMyString private: char* m_pData; ; 请实现其赋值运算符
39、的重载函数，要求异常安全，即当对一个对象进行赋值时发生异常，对 象的状态不能改变。 56.最长公共字串（算法、字符串）。 题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中， 则字符串一称之为字符串二的子串。 注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。 请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。 例如：输入两个字符串 BDCABA 和 ABCBDAB，字符串 BCBA 和 BDAB 都是是它们的最 长公共子串， 则输出它们的长度 4，并打印任意一个子串。 分析：求最长公共子串（Longest Common Subseq
40、uence, LCS）是一道非常经典的动态规 划题， 因此一些重视算法的公司像 MicroStrategy 都把它当作面试题。 57.用俩个栈实现队列（栈、队列）。 题目：某队列的声明如下： template class CQueue public: CQueue() CQueue() void appendTail(const T / append a element to tail void deleteHead(); / remove a element from head private: T m_stack1; T m_stack2; ; 分析：从上面的类的声明中，我们发现在队列中有两个栈。 因此这道题实质上是要求我们用两个栈来实现一个队列。 相信大家对栈和队列的基
