【www.longjiam.com--语文题库】
数据结构面试的时候我们需要面试题，大家可以看看下面的数据结构面试题与答案哦！
数据结构面试题与答案1、给出一个函数来输出一个字符串的所有排列。
ANSWER+简单的回溯就可以实现了。当然在排列的产生也有很多种算法，去看看组合数学，
还有逆序生成排列和一些不需要递归生成排列的方法。
印象中Knuth+的第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，也需要一定的灵感，有兴趣最好看看。
ANSWER:
Have+done+this.
2、题目：设计一个类，我们只能生成该类的一个实例。
分析：只能生成一个实例的类是实现了Singleton+模式的类型。
ANSWER
I’m+not+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+constructor+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.+I’m+quite+bad+at+this...
3、题目：实现函数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;
}
ANSWER
…
double+power(double+base,+int+exp)+{
if+(exp+==+1)+return+base;
double+half+=+power(base,+exp+>>+1);
return+(((exp+&+1)+==+1)+?+base+:+1.0)+half+half;
}
4、输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的
加强版。
ANSWER
Build+a+suffix+tree+of+x+and+inverse(x),+the+longest+anagram+is+naturally+found.
Suffix+tree+can+be+built+in+O(n)+time+so+this+is+a+linear+time+solution.
74.数组中超过出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
分析：这是一道广为流传的面试题，包括百度、微软和Google+在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。
ANSWER
Delete+every+two+different+digits.+The+last+one+that+left+is+the+one.
int+getMajor(int+a[],+int+n)+{
int+x,+cnt=0;
for+(int+i=0;+i<n;+i++)+{
if+(cnt+==+0)+{
x+=+a[i];+cnt++;
}+else+if+(a[i]==x)+{
cnt+++;
}+else+{
cnt+--;
}
}
return+x;
}
上一篇：测试工程师面试笔试题
下一篇：百科知识竞赛题300题