[汇总 II]精选微软等数据结构+算法面试 100题[第 1-80 题]

—最新整理公布

昨日，11.19，最新整理了，第 61-80题，现在公布上传。另加上之前公布的第 1-60 题，在此做一次汇总上传，以飨各位。

可以这么说，绝大部分的面试题，都是这 100 道题系列的翻版，此微软等公司数据结构+算法面试 100 题系列，是极具代表性的经典面试题。我曾经暗暗问自己，不知道我是否把面试题基本上都搜集整理尽了，而当然，对你更重要的是，我自个还提供了答案下载，提供思路，呵。

所以，这份资料+答案，在网上是独一无二的。闲不多说，接下来，你可以尽情的享用了，朋友。

————————————————————————————————- 整理资源，下载地址：

答案系列：

1.[最新答案 V0.3 版]微软等数据结构+算法面试 100 题[第 21-40 题答案] http://download.csdn.net/source/2832862

2.[答案 V0.2 版]精选微软数据结构+算法面试 100 题[前 20 题]—修正 http://download.csdn.net/source/2813890

//此份答案是针对最初的 V0.1 版本，进行的校正与修正。

3.[[答案 V0.1 版]精选微软数据结构+算法面试 100 题前 25 题] http://download.csdn.net/source/2796735

题目系列：

4.[第一部分]精选微软等公司数据结构+算法经典面试 100 题[1-40 题] http://download.csdn.net/source/2778852

5.[第 1 题-60 题汇总]微软等数据结构+算法面试 100 题 http://download.csdn.net/source/2826690

更多资源，下载地址：

http://v_july_v.download.csdn.net/

若你对以上任何题目或任何答案，有任何问题，欢迎联系我： MyE-mail：

zhoulei0907@yahoo.cn

或者，直接回复于这俩帖上：

帖子维护，更新地址：

http://topic.csdn.net/u/20101119/22/544a8109-5018-43a9-a64e-2766e6e20f31.html [推荐] [整理]算法面试：精选微软经典的算法面试 100 题[前 40-60 题]（已结帖） http://topic.csdn.net/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html

—-July、2010 年 11 月 19 日。

1.把二元查找树转变成排序的双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

/ \

6 14

/ \ / \

8 12 16

转换成双向链表 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.求子数组的最大和

题目：

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)。

例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，因此输出为该子数组的和 18。

4.在二元树中找出和为某一值的所有路径

题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。

例如输入整数 22 和如下二元树

/ \

4 7

则打印出两条路径：10, 12 和 10, 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 题

腾讯面试题：

给你 10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下：

【0，1，2，3，4，5，6，7，8，9】

初看此题，貌似很难，10 分钟过去了，可能有的人，题目都还没看懂。

举一个例子，

数值: 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，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。

问题扩展：

1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列?

第 8 题

此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。 1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，

这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。

如果你只能将金条切割两次，你怎样分给这些工人?

★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。

★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。 ★用一种算法整理一个数组。你为什么选择这种方法? ★用一种算法使通用字符串相匹配。 ★颠倒一个字符串。优化速度。优化空间。

★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，实现速度最快，移动最少。

★找到一个子字符串。优化速度。优化空间。

★比较两个字符串，用 O(n)时间和恒量空间。

★假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?

★不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。

第 9 题

判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true，否则返回 false。

例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

/ \

6 10

/ \ / \

5 7 9 11

因此返回 true。

如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。

第 10 题

翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student.a am I”。

第 11 题

求二叉树中节点的最大距离…

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。

写一个程序，

求一棵二叉树中相距最远的两个节点之间的距离。

第 12 题

题目：求 1+2+…+n，

要求不能使用乘除法、for、while、if、else、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=15，因此输出 4 和 11。

第 15 题：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。

例如输入：

/ \

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 node BSTreeNode m_pRight; // right child of node

};

第 16 题：

题目（微软）：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入

/ \

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 开始，

每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。

当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。

第 19 题：

题目：定义 Fibonacci 数列如下：

/ 0 n=0

f(n)= 1 n=1

\ f(n-1)+f(n-2) n=2

输入 n，用最快的方法求该数列的第 n 项。

分析：在很多 C 语言教科书中讲到递归函数的时候，都会用 Fibonacci 作为例子。因此很多程序员对这道题的递归解法非常熟悉，但….呵呵，你知道的。。

第 20 题：题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数 345。

第 21 题

2010 年中兴面试题

编程求解：

输入两个整数 n 和 m，从数列 1，2，3…….n 中随意取几个数, 使其和等于 m ,要求将其中所有的可能组合列出来.

第 22 题：

有 4 张红色的牌和 4 张蓝色的牌，主持人先拿任意两张，再分别在 A、B、C 三人额头上贴任意两张牌，

A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，

A 说不知道，B说不知道，C 说不知道，然后 A说知道了。

请教如何推理，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 题：

链表操作，（1）.单链表就地逆置，（2）合并链表

第 25 题：

写一个函数,它的原形是 int continumax(char outputstr,char intputstr)

功能：

在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数 outputstr 所指内存。例如："abcd12345ed125ss123456789"的首地址传给 intputstr 后，函数将返回 9， outputstr所指的值为 123456789

26.左旋转字符串

题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。

如把字符串 abcdef 左旋转 2 位得到字符串 cdefab。请实现字符串左旋转的函数。要求时间对长度为 n 的字符串操作的复杂度为 O(n)，辅助内存为 O(1)。

27.跳台阶问题

题目：一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。求总共有多少总跳法，并分析算法的时间复杂度。

这道题最近经常出现，包括 MicroStrategy 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。

28.整数的二进制表示中 1 的个数题目：输入一个整数，求该整数的二进制表达中有多少个 1。例如输入 10，由于其二进制表示为 1010，有两个 1，因此输出 2。

分析：这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。

29.栈的 push、pop 序列题目：输入两个整数序列。其中一个序列表示栈的 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 到 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,98,1,2, 3];

var b=[1, 2, 3, 4,5,40];

33.

实现一个挺高级的字符匹配算法：给一串很长字符串，要求找到符合要求的字符串，例如目的串：123 1**32 ,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 写出关键代码

第 36 题-40 题（有些题目搜集于 CSDN 上的网友，已标明）： 36.引用自网友：longzuo

谷歌笔试：

n 支队伍比赛，分别编号为 0，1，2。。。。n-1，已知它们之间的实力对比关系，存储在一个二维数组 w[n][n]中，w[i][j] 的值代表编号为 i，j 的队伍中更强的一支。

所以 w[i][j]=i 或者 j，现在给出它们的出场顺序，并存储在数组 order[n]中，比如 order[n] = {4,3,5,8,1……}，那么第一轮比赛就是 4 对 3， 5 对 8。…….

胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是 4 对 5,直至出现第一名

编程实现，给出二维数组 w，一维数组 order 和用于输出比赛名次的数组 result[n]，求出 result。

37.

有 n 个长为 m+1 的字符串，

如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配，则两个字符串可以联接，问这 n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

38.

百度面试：

1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用 x 次天平，最多可以从 y 个小球中找出较轻的那个，求 y 与 x 的关系式。

2.有一个很大很大的输入流，大到没有存储器可以将其存储下来，

而且只输入一次，如何从这个输入流中随机取得 m 个记录。 3.大量的 URL 字符串，如何从中去除重复的，优化时间空间复杂度

39.

网易有道笔试：

(1).

求一个二叉树中任意两个节点间的最大距离，

两个节点的距离的定义是这两个节点间边的个数，

比如某个孩子节点和父节点间的距离是 1，和相邻兄弟节点间的距离是 2，优化时间空间复杂度。

(2). 求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。

40.百度研发笔试题

引用自：zp155334877

1)设计一个栈结构，满足一下条件：min，push，pop 操作的时间复杂度为 O(1)。 2)一串首尾相连的珠子(m 个)，有 N 种颜色(N<=10)，

设计一个算法，取出其中一段，要求包含所有 N 中颜色，并使长度最短。并分析时间复杂度与空间复杂度。

3)设计一个系统处理词语搭配问题，比如说中国和人民可以搭配，则中国人民人民中国都有效。要求：

系统每秒的查询数量可能上千次； 词语的数量级为 10W； *每个词至多可以与 1W 个词搭配

当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。

41.求固晶机的晶元查找程序晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，

照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，若匹配不过，照相机则按测好的晶元间距移到下一个位置。求遍历晶元盘的算法求思路。

42.请修改 append 函数，利用这个函数实现：两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5 另外只能输出结果，不能修改两个链表的数据。

43.递归和非递归俩种方法实现二叉树的前序遍历。

44.腾讯面试题：

1.设计一个魔方（六面）的程序。 2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。

请用 5 分钟时间，找出重复出现最多的前 10 条。

3.收藏了 1 万条 url，现在给你一条 url，如何找出相似的 url。（面试官不解释何为相似）

45.雅虎： 1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

2.一个整数数组，长度为 n，将其分为 m 份，使各份的和相等，求 m 的最大值

比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;

{3,6}{2,4,3} m=2

{3,3}{2,4}{6} m=3 所以 m 的最大值为 3

46.搜狐：四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

47.创新工场：

求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

48.微软：

一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

49.一道看上去很吓人的算法面试题：

如何对 n 个数进行排序，要求时间复杂度 O(n)，空间复杂度 O(1)

50.网易有道笔试：

1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是 1，和相邻兄弟节点间的距离是 2，优化时间空间复杂度。

2.求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。

51.和为 n 连续正数序列。

题目：输入一个正数 n，输出所有和为 n 连续正数序列。

例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出 3 个连续序列 1-5、4-6 和 7-8。分析：这是网易的一道面试题。

52.二元树的深度。

题目：输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。例如：输入二元树：

/ \

6 14

/ / \

4 12 16

输出该树的深度 3。

二元树的结点定义如下：

struct SBinaryTreeNode // 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。

分析：这是一道很好的考查对递归理解的编程题，因此在过去一年中频繁出现在各大公司的面试、笔试题中。

54.调整数组顺序使奇数位于偶数前面。题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为 O(n)。

55.

题目：类 CMyString 的声明如下：

class CMyString

{

public:

CMyString(char* pData = NULL); CMyString(const CMyString& str); ~CMyString(void);

CMyString& operator = (const CMyString& str);

private:

char* m_pData; };

请实现其赋值运算符的重载函数，要求异常安全，即当对一个对象进行赋值时发生异常，对象的状态不能改变。

56.最长公共字串。题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

例如：输入两个字符串 BDCABA 和 ABCBDAB，字符串 BCBA 和 BDAB 都是是它们的最长公共子串，

则输出它们的长度 4，并打印任意一个子串。

分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像 MicroStrategy 都把它当作面试题。

57.用俩个栈实现队列。题目：某队列的声明如下： template<typename T> class CQueue {

public:

CQueue() {} ~CQueue() {}

void appendTail(const T& node); // append aelement to tail

void deleteHead(); // remove a element from head

private:

T> m_stack1; T> m_stack2;

}; 分析：从上面的类的声明中，我们发现在队列中有两个栈。

因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，

因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。

58.从尾到头输出链表。题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下： struct ListNode

{

int m_nKey; ListNode* m_pNext;

};

分析：这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。 59.不能被继承的类。

题目：用 C++设计一个不能被继承的类。

分析：这是 Adobe 公司 2007 年校园招聘的最新笔试题。

这道题除了考察应聘者的 C++基本功底外，还能考察反应能力，是一道很好的题目。

60.在 O（1）时间内删除链表结点。

题目：给定链表的头指针和一个结点指针，在 O(1)时间删除该结点。链表结点的定义如下： struct ListNode

{

int m_nKey; ListNode* m_pNext;

};

函数的声明如下：

void DeleteNode(ListNode pListHead, ListNode pToBeDeleted);

分析：这是一道广为流传的 Google 面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。

———————————————————————————————————————————————- 现在首次公布整理的第 61-80 题（11.19 最新整理公布）：

61.找出数组中两个只出现一次的数字题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。

分析：这是一道很新颖的关于位运算的面试题。

62.找出链表的第一个公共结点。题目：两个单向链表，找出它们的第一个公共结点。

链表的结点定义为： struct ListNode

{

int m_nKey; ListNode* m_pNext;

};

分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，因此在微软的面试题中，链表出现的概率相当高。

63.在字符串中删除特定的字符。

题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。

分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，

因为写程序操作字符串能很好的反映我们的编程基本功。 64. 寻找丑数。

题目：我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。

例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。

求按从小到大的顺序的第 1500 个丑数。分析：这是一道在网络上广为流传的面试题，据说 google 曾经采用过这道题。

65.输出 1 到最大的 N 位数

题目：输入数字 n，按顺序输出从 1 最大的 n 位 10 进制数。比如输入 3，则输出 1、2、3 一直到最大的 3 位数即 999。

分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。

66.颠倒栈。

题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1 在栈顶。颠倒之后的栈为{5, 4, 3, 2, 1}，5 处在栈顶。

67.俩个闲玩娱乐。

1.扑克牌的顺子

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。 2-10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大小王可以看成任意数字。

2.n 个骰子的点数。

把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 S。输入 n，打印出 S 的所有可能的值出现的概率。

68.把数组排成最小的数。题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

例如输入数组{32, 321}，则输出这两个能排成的最小数字 32132。请给出解决问题的算法，并证明该算法。

分析：这是 09 年 6 月份百度的一道面试题，从这道题我们可以看出百度对应聘者在算法方面有很高的要求。

69.旋转数组中的最小元素。

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为 1。

分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是 O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

70.给出一个函数来输出一个字符串的所有排列。

分析：简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，还有逆序生成排列和一些不需要递归生成排列的方法。

印象中 Knuth 的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，也需要一定的灵感，有兴趣最好看看。

71.数值的整数次方。

题目：实现函数 double Power(double base, int exponent)，求 base的 exponent 次方。不需要考虑溢出。

分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后 30 秒写出如下的代码：

double Power(double base,int exponent) {

double result = 1.0;

for(int i = 1; i <= exponent; ++i)

result *= base; return result;

}

72.

题目：设计一个类，我们只能生成该类的一个实例。分析：只能生成一个实例的类是实现了 Singleton 模式的类型。

73.对策字符串的最大长度。题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出 4。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

74.数组中超过出现次数超过一半的数字题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

分析：这是一道广为流传的面试题，包括百度、微软和 Google 在内的多家公司都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，除了较好的编程能力之外，

还需要较快的反应和较强的逻辑思维能力。

75.二叉树两个结点的最低共同父结点题目：二叉树的结点定义如下： structTreeNode

{

int m_nvalue;

TreeNode m_pLeft; TreeNode m_pRight;

};

输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个

变种。 76.复杂链表的复制

题目：有一个复杂链表，其结点除了有一个还有一个 m_pSibling 指向链表中的任一结点或者

struct ComplexNode

{

int m_nValue;

ComplexNode* m_pNext;

ComplexNode* m_pSibling;

m_pNext 指针指向下一个结点外，

NULL。其结点的 C++定义如下：

};

下图是一个含有 5 个结点的该类型复杂链表。

图中实线箭头表示 m_pNext 指针，虚线箭头表示 m_pSibling 指针。为简单起见，指向 NULL 的指针没有画出。

请完成函数 ComplexNode Clone(ComplexNode pHead)，以复制一个复杂链表。

//图，接下来，自会补上。July、11.19. 分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，对数据结构透彻的理解以及扎实的编程功底。

77.关于链表问题的面试题目如下：

题一、给定单链表，检测是否有环。

使用两个指针 p1,p2 从链表头开始遍历，p1 每次前进一步，p2 每次前进两步。

如果 p2 到达链表尾部，说明无环，否则 p1、p2 必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。

题二、给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。

如果 head1==head2，那么显然相交，直接返回 head1。

否则，分别从 head1,head2 开始遍历两个链表获得其长度 len1 与 len2，假设 len1>=len2，那么指针 p1 由 head1 开始向后移动 len1-len2 步，指针 p2=head2，

下面 p1、p2 每次向后前进一步并比较 p1p2 是否相等，如果相等即返回该结点，否则说明两个链表没有交点。

题三、给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。

运用题一，我们可以检查链表中是否有环。

如果有环，那么 p1p2 重合点 p 必然在环中。从 p 点断开环，方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表，一条从 head 开始，另一条从 p2 开

始，

于是运用题二的方法，我们找到它们的第一个交点即为所求。

题四、只给定单链表中某个结点 p(并非最后一个结点，即 p->next!=NULL)指针，删除该结点。

办法很简单，首先是放 p 中数据,然后将 p->next 的数据 copy 入 p 中，接下来删除 p->next 即可。

题五、只给定单链表中某个结点 p(非空结点)，在 p 前面插入一个结点。

办法与前者类似，首先分配一个结点 q，将 q 插入在 p 后，

接下来将 p 中的数据 copy 入 q 中，然后再将要插入的数据记录在 p 中。

78.链表和数组的区别在哪里？

分析：主要在基本概念上的理解。但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，

谁比较仔细，谁获胜的机会就大。

1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？ 2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？ 3.请编写能直接实现 strstr()函数功能的代码。

80.阿里巴巴一道笔试题

引自 baihacker

问题描述:

12 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高, 问排列方式有多少种?

这个笔试题,很 YD,因为把某个递归关系隐藏得很深.

//第 81-100 题正在整理中（完）。

整理资源，下载地址：

答案系列：

1.[最新答案 V0.3 版]微软等数据结构+算法面试 100 题[第 21-40 题答案] http://download.csdn.net/source/2832862

2.[[答案 V0.2 版]精选微软数据结构+算法面试 100 题前 20 题]—修正 http://download.csdn.net/source/2813890

//此份答案是针对最初的 V0.1 版本，进行的校正与修正。

3.[[答案 V0.1 版]精选微软数据结构+算法面试 100 题前 25 题] http://download.csdn.net/source/2796735

题目系列：

4.[第一部分]精选微软等公司数据结构+算法经典面试 100 题[1-40 题] http://download.csdn.net/source/2778852 5.[第二部分]精选微软等公司结构+算法面试 100 题[前 41-60 题]： http://download.csdn.net/source/2811703

6.[第 1 题-60 题汇总]微软等数据结构+算法面试 100 题 http://download.csdn.net/source/2826690

更多资源，下载地址：

http://v_july_v.download.csdn.net/

—————————————————————————————- 若你对以上任何题目或任何答案，有任何问题，欢迎联系我：

MyE-mail：

zhoulei0907@yahoo.cn

MyQq： 786165179 注，Qq不闲聊，不帮解决作业问题，不帮解决其它编译程序等问题。有任何问题，请 qq 留言（只限这 100 道题范围之内）。最好是发我邮箱。谢谢。

或者，直接回复于这俩帖上：

帖子维护，更新地址： http://topic.csdn.net/u/20101119/22/544a8109-5018-43a9-a64e-2766e6e20f31.html [推荐] [整理]算法面试：精选微软经典的算法面试 100 题[前 40-60 题]（已结帖） http://topic.csdn.net/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html

作者声明：

本人July 对以上公布的所有任何题目或资源享有版权。转载以上公布的任何一题，或上传百度文库资源，请注明出处，及作者我本人。

向你的厚道致敬。谢谢。

July、2010 年 11 月 20 日。