數據結構複試常問問題詳解

一、基本的數據結構分類

1、數據結構是一個抽象的概念，可分為線性結構和非線性結構。線性結構有線性表、隊列、棧和數組。非線性結構有樹、圖等。
2、數組是一組連續的空間，每個元素佔用相同的空間。訪問數組元素的時間複雜度為O(1)。但插入和刪除操作的時間複雜度為O(n)。
3、鏈表是一種非連續的數據結構，由節點組成。單向鏈表和雙向鏈表，訪問元素的時間複雜度為O(n)，但插入和刪除操作時間複雜度為O(1)。
4、棧和隊列是特殊的線性結構，棧是後進先出，隊列是先進先出。
5、樹是一種以分支關係連接的非線性結構，由節點組成。樹形結構包括二叉樹、紅黑樹、AVL樹和B樹。
6、圖是一種由節點和邊組成的非線性結構。圖可分為有向圖和無向圖，根據邊權重不同可分為帶權圖和無權圖。

//示例代碼：鏈表的定義和實現
class Node{
public:
    int data;
    Node* next;
    Node(int val):data(val),next(nullptr){}
};
class LinkedList{
public:
    LinkedList():head(nullptr){}
    void add(int val){
        Node* temp=new Node(val);
        if(head==nullptr){
            head=temp;
        }else{
            temp->next=head;
            head=temp;
        }
    }
    void print(){
        Node* curr=head;
        while(curr!=nullptr){
            cout<data<next;
        }
    }
private:
    Node* head;
};

二、時間和空間複雜度

1、時間複雜度是算法在運行過程中，所需要計算的基本操作次數的數量級。用大O表示法表示，常用的有O(1)、O(logn)、O(n)、O(n^2)等。
2、空間複雜度是算法所需要佔用的內存空間數量級。常見的是O(1)和O(n)。
3、要注意最壞時間複雜度和平均時間複雜度的區別。循環語句、條件判斷語句和遞歸都可能影響算法的時間和空間複雜度。

//示例代碼：歸併排序
void MergeSort(int* arr,int l,int r){
    if(l>=r) return;
    int mid=(l+r)/2;
    MergeSort(arr,l,mid);
    MergeSort(arr,mid+1,r);
    int* temp=new int[r-l+1];
    int i=l,j=mid+1,k=0;
    while(i<=mid && j<=r){
        if(arr[i]<=arr[j]) temp[k++]=arr[i++];
        else temp[k++]=arr[j++];
    }
    while(i<=mid){
        temp[k++]=arr[i++];
    }
    while(j<=r){
        temp[k++]=arr[j++];
    }
    for(i=l,j=0;i<=r;i++,j++){
        arr[i]=temp[j];
    }
    delete[] temp;
}

三、遞歸和迭代

1、遞歸是一種經典的算法，可以簡化代碼，但可能會降低性能，容易出現堆棧溢出等問題。遞歸問題中必須有一個遞歸結束的條件。
2、迭代比遞歸效率高，但可能不如遞歸好理解。許多遞歸問題都可以轉化為循環，因此迭代使用較多。
3、注意遞歸和迭代的優缺點，合理運用二者。

//示例代碼：斐波那契數列的遞歸和迭代實現
//遞歸
int Fibonacci(int n){
    if(n==1 || n==2) return 1;
    else return Fibonacci(n-1)+Fibonacci(n-2);
}
//迭代
int Fibonacci(int n){
    if(n==1 || n==2) return 1;
    int pre=1,cur=1;
    for(int i=3;i<=n;i++){
        int temp=pre+cur;
        pre=cur;
        cur=temp;
    }
    return cur;
}

四、樹的遍歷方式

1、樹的遍歷方式包括先序遍歷、中序遍歷和後序遍歷。先序遍歷是先遍歷根節點，再遍歷左子樹和右子樹；中序遍歷是先遍歷左子樹，再遍歷根節點和右子樹；後序遍歷是先遍歷左子樹和右子樹，再遍歷根節點。
2、利用遞歸和棧都可以進行樹的遍歷。
3、應該注意到為了遍歷，不管是遞歸還是棧，都需要對樹的每個節點進行遍歷。對於算法的時間和空間複雜度都有一定的影響。

//示例代碼：二叉樹的後序遍歷實現
class Node{
public:
    int val;
    Node *left,*right;
    Node(int val):val(val),left(nullptr),right(nullptr){}
};
void PostOrder(Node* root){
    if(root==nullptr) return;
    PostOrder(root->left);
    PostOrder(root->right);
    cout<val<<" ";
}

五、哈希表

1、哈希表是一種常見的數據結構，可以快速查找某個元素。哈希表由一個數組和哈希函數組成，其中哈希函數將元素映射到數組的某個位置。如果有多個元素映射到同一位置，就需要使用鏈表解決衝突問題。
2、需要注意哈希表的建立、插入、刪除和查找操作，以及哈希函數的設計，如何解決哈希衝突等問題。
3、哈希表可以用來解決很多算法問題，如Lru Cache，Two Sum等。

//示例代碼：哈希表的實現--開放地址法
struct Node{
    int key;
    int val;
    Node(int k,int v):key(k),val(v){}
};
class HashTable{
public:
    HashTable(int size):size(size),used(0){
        table=new Node*[size];
        for(int i=0;ikey!=key){
            index=(index+1)%size;
        }
        if(table[index]==nullptr){
            table[index]=new Node(key,val);
            used++;
        }else{
            table[index]->val=val;
        }
    }
    void erase(int key){
        int index=hash(key);
        while(table[index]!=nullptr){
            if(table[index]->key==key) break;
            index=(index+1)%size;
        }
        if(table[index]==nullptr) return;
        else{
            delete table[index];
            table[index]=nullptr;
            used--;
        }
    }
    int get(int key){
        int index=hash(key);
        while(table[index]!=nullptr){
            if(table[index]->key==key) return table[index]->val;
            index=(index+1)%size;
        }
        return -1;
    }
    bool contains(int key){
        int index=hash(key);
        while(table[index]!=nullptr){
            if(table[index]->key==key) return true;
            index=(index+1)%size;
        }
        return false;
    }
private:
    int size,used;
    Node** table;
};