数据结构面试题与答案

1、数据结构面试题与答案数据结构面试的时候我们需要面试题，大家可以看看下面的数据结构面试题与答案哦！数据结构面试题与答案1、给出一个函数来输出一个字符串的所有排列。ANSWER 简单的回溯就可以实现了。当然在排列的产生也有很多种算法，去看看组合数学，还有逆序生成排列和一些不需要递归生成排列的方法。印象中Knuth 的第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，也需要一定的灵感，有兴趣最好看看。ANSWER:Have done this.2、题目：设计一个类，我们只能生成该类的一个实例。分析：只能生成一个实例的.类是实现了Singleton 模式的类型。ANSWERIm not

2、good at multithread programming. But if we set a lazy initialization, the “if” condition could be interrupted thus multiple constructor could be called, so we must add synchronized to the if judgements, which is a loss of efficiency. Putting it to the static initialization will guarantee that the co

3、nstructor only be executed once by the java class loader.public class Singleton private static Singleton instance = new Singleton();private synchronized Singleton() public Singleton getInstance() return instance();This may not be correct. Im quite bad at this.3、题目：实现函数double Power(double base, int e

4、xponent)，求base 的exponent 次方。不需要考虑溢出。分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30 秒写出如下的代码：double Power(double base, int exponent)double result = 1.0;for(int i = 1; i <= exponent; +i)result *= base;return result;ANSWERdouble power(double base, int exp) if (exp = 1) return base;double half = power(base, exp &g

5、t;> 1);return (exp & 1) = 1) ? base : 1.0) half half;4、输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。ANSWERBuild a suffix tree of x and inverse(x), the longest anagram is naturally found.Suffix tree can be built in O(n) t

6、ime so this is a linear time solution.74.数组中超过出现次数超过一半的数字题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。分析：这是一道广为流传的面试题，包括百度、微软和Google 在内的多家公司都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。ANSWERDelete every two different digits. The last one that left is the getMajor(int a, int n) int x, cnt=0;for (int i=0;