數(shù)據(jù)結(jié)構面試的時候我們需要面試題，大家可以看看下面的數(shù)據(jù)結(jié)構面試題與答案哦！

　　數(shù)據(jù)結(jié)構面試題與答案

　　1、給出一個函數(shù)來輸出一個字符串的所有排列。

　　ANSWER 簡單的回溯就可以實現(xiàn)了。當然在排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學，

　　還有逆序生成排列和一些不需要遞歸生成排列的方法。

　　印象中Knuth 的'第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學功底，也需要一定的靈感，有興趣最好看看。

　　ANSWER:

　　Have done this.

　　2、題目：設計一個類，我們只能生成該類的一個實例。

　　分析：只能生成一個實例的類是實現(xiàn)了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、題目：實現(xiàn)函數(shù)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。

　　分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的

　　加強版。

　　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.數(shù)組中超過出現(xiàn)次數(shù)超過一半的數(shù)字

　　題目：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個數(shù)字。

　　分析：這是一道廣為流傳的面試題，包括百度、微軟和Google 在內(nèi)的多家公司都

　　曾經(jīng)采用過這個題目。要幾十分鐘的時間里很好地解答這道題，

　　除了較好的編程能力之外，還需要較快的反應和較強的邏輯思維能力。

　　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;

　　}