数据结构复试常问问题详解

一、基本的数据结构分类

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;
};