2025年高頻c數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)面試題及答案1.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)概念類問題1：什么是數(shù)據(jù)結(jié)構(gòu)，列舉常見的數(shù)據(jù)結(jié)構(gòu)類型數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的組織、存儲和操作方式，目的是為了更高效地處理數(shù)據(jù)。常見的數(shù)據(jù)結(jié)構(gòu)類型包括：線性結(jié)構(gòu)數(shù)組：是一種連續(xù)存儲相同類型數(shù)據(jù)的線性數(shù)據(jù)結(jié)構(gòu)，通過下標(biāo)可以快速訪問元素。例如，在C語言中定義一個整數(shù)數(shù)組`intarr[5]={1,2,3,4,5};`，可以使用`arr[2]`快速訪問到數(shù)組中第3個元素（下標(biāo)從0開始）。鏈表：由節(jié)點組成，每個節(jié)點包含數(shù)據(jù)域和指針域。鏈表分為單鏈表、雙鏈表和循環(huán)鏈表。單鏈表的節(jié)點只有一個指向下一個節(jié)點的指針，雙鏈表的節(jié)點有指向前一個節(jié)點和后一個節(jié)點的指針，循環(huán)鏈表的尾節(jié)點指向頭節(jié)點。例如，單鏈表節(jié)點的C語言定義如下：```ctypedefstructNode{intdata;structNodenext;}Node;```棧：遵循后進先出（LIFO）原則的線性數(shù)據(jù)結(jié)構(gòu)，只能在棧頂進行插入（入棧）和刪除（出棧）操作?？梢允褂脭?shù)組或鏈表來實現(xiàn)棧。隊列：遵循先進先出（FIFO）原則的線性數(shù)據(jù)結(jié)構(gòu)，有隊頭和隊尾，元素從隊尾插入（入隊），從隊頭刪除（出隊）。同樣可以使用數(shù)組或鏈表實現(xiàn)隊列。非線性結(jié)構(gòu)樹：是一種層次結(jié)構(gòu)，由節(jié)點和邊組成，有一個根節(jié)點，每個節(jié)點可以有零個或多個子節(jié)點。常見的樹有二叉樹、二叉搜索樹、AVL樹、紅黑樹等。例如，二叉樹節(jié)點的C語言定義如下：```ctypedefstructTreeNode{intdata;structTreeNodeleft;structTreeNoderight;}TreeNode;```圖：由頂點和邊組成，用于表示多對多的關(guān)系。圖分為有向圖和無向圖，有向圖的邊有方向，無向圖的邊沒有方向。問題2：簡述數(shù)組和鏈表的優(yōu)缺點數(shù)組的優(yōu)點隨機訪問效率高：可以通過下標(biāo)直接訪問數(shù)組中的任意元素，時間復(fù)雜度為O(1)。例如，要訪問數(shù)組`arr`的第`i`個元素，直接使用`arr[i]`即可。內(nèi)存空間連續(xù)：數(shù)組在內(nèi)存中是連續(xù)存儲的，因此緩存命中率高，能提高訪問速度。數(shù)組的缺點插入和刪除效率低：在數(shù)組中插入或刪除元素時，需要移動大量元素，時間復(fù)雜度為O(n)。例如，在數(shù)組中間插入一個元素，需要將插入位置之后的所有元素向后移動一位。大小固定：數(shù)組的大小在定義時就已經(jīng)確定，不能動態(tài)擴展。如果需要存儲更多元素，需要重新分配更大的數(shù)組并復(fù)制元素。鏈表的優(yōu)點插入和刪除效率高：在鏈表中插入或刪除節(jié)點，只需要修改指針，時間復(fù)雜度為O(1)（如果已知要操作的節(jié)點位置）。例如，在單鏈表中插入一個新節(jié)點，只需要修改新節(jié)點的指針和前一個節(jié)點的指針。動態(tài)分配內(nèi)存：鏈表的節(jié)點可以在需要時動態(tài)分配內(nèi)存，不需要預(yù)先分配固定大小的空間。鏈表的缺點隨機訪問效率低：要訪問鏈表中的某個節(jié)點，需要從頭節(jié)點開始遍歷，時間復(fù)雜度為O(n)。內(nèi)存開銷大：鏈表的每個節(jié)點除了存儲數(shù)據(jù)外，還需要存儲指針，增加了內(nèi)存開銷。2.棧和隊列相關(guān)問題3：如何用數(shù)組實現(xiàn)一個棧以下是用數(shù)組實現(xiàn)棧的C語言代碼：```cinclude<stdio.h>include<stdlib.h>defineMAX_SIZE100typedefstructStack{intarr[MAX_SIZE];inttop;}Stack;//初始化棧voidinitStack(Stacks){s->top=-1;}//判斷棧是否為空intisEmpty(Stacks){returns->top==-1;}//判斷棧是否已滿intisFull(Stacks){returns->top==MAX_SIZE1;}//入棧操作voidpush(Stacks,intdata){if(isFull(s)){printf("Stackisfull!\n");return;}s->arr[++(s->top)]=data;}//出棧操作intpop(Stacks){if(isEmpty(s)){printf("Stackisempty!\n");return-1;}returns->arr[(s->top)--];}//獲取棧頂元素intpeek(Stacks){if(isEmpty(s)){printf("Stackisempty!\n");return-1;}returns->arr[s->top];}intmain(){Stacks;initStack(&s);push(&s,1);push(&s,2);printf("Topelement:%d\n",peek(&s));printf("Poppedelement:%d\n",pop(&s));return0;}```在這個實現(xiàn)中，使用一個數(shù)組`arr`來存儲棧中的元素，`top`指針表示棧頂?shù)奈恢?。初始化時，`top`為-1表示棧為空。入棧操作將元素添加到`arr[++top]`位置，出棧操作返回`arr[top--]`位置的元素。問題4：如何用兩個棧實現(xiàn)一個隊列可以使用兩個棧`stack1`和`stack2`來實現(xiàn)一個隊列。`stack1`用于入隊操作，`stack2`用于出隊操作。具體實現(xiàn)如下：```cinclude<stdio.h>include<stdlib.h>defineMAX_SIZE100typedefstructStack{intarr[MAX_SIZE];inttop;}Stack;//初始化棧voidinitStack(Stacks){s->top=-1;}//判斷棧是否為空intisEmpty(Stacks){returns->top==-1;}//判斷棧是否已滿intisFull(Stacks){returns->top==MAX_SIZE1;}//入棧操作voidpush(Stacks,intdata){if(isFull(s)){printf("Stackisfull!\n");return;}s->arr[++(s->top)]=data;}//出棧操作intpop(Stacks){if(isEmpty(s)){printf("Stackisempty!\n");return-1;}returns->arr[(s->top)--];}typedefstructQueue{Stackstack1;Stackstack2;}Queue;//初始化隊列voidinitQueue(Queueq){initStack(&q->stack1);initStack(&q->stack2);}//入隊操作voidenqueue(Queueq,intdata){push(&q->stack1,data);}//出隊操作intdequeue(Queueq){if(isEmpty(&q->stack2)){while(!isEmpty(&q->stack1)){push(&q->stack2,pop(&q->stack1));}}if(isEmpty(&q->stack2)){printf("Queueisempty!\n");return-1;}returnpop(&q->stack2);}intmain(){Queueq;initQueue(&q);enqueue(&q,1);enqueue(&q,2);printf("Dequeuedelement:%d\n",dequeue(&q));return0;}```入隊操作直接將元素壓入`stack1`，出隊操作時，如果`stack2`為空，則將`stack1`中的所有元素依次彈出并壓入`stack2`，然后從`stack2`中彈出元素。這樣就實現(xiàn)了隊列的先進先出特性。3.樹相關(guān)問題5：簡述二叉搜索樹（BST）的特點和操作二叉搜索樹（BST）是一種特殊的二叉樹，具有以下特點：對于樹中的每個節(jié)點，其左子樹中的所有節(jié)點的值都小于該節(jié)點的值。對于樹中的每個節(jié)點，其右子樹中的所有節(jié)點的值都大于該節(jié)點的值。左右子樹也分別是二叉搜索樹。二叉搜索樹的常見操作包括：插入操作：從根節(jié)點開始，比較要插入的值和當(dāng)前節(jié)點的值。如果要插入的值小于當(dāng)前節(jié)點的值，則遞歸地插入到左子樹中；如果要插入的值大于當(dāng)前節(jié)點的值，則遞歸地插入到右子樹中。```cTreeNodeinsert(TreeNoderoot,intdata){if(root==NULL){TreeNodenewNode=(TreeNode)malloc(sizeof(TreeNode));newNode->data=data;newNode->left=newNode->right=NULL;returnnewNode;}if(data<root->data){root->left=insert(root->left,data);}elseif(data>root->data){root->right=insert(root->right,data);}returnroot;}```查找操作：從根節(jié)點開始，比較要查找的值和當(dāng)前節(jié)點的值。如果相等，則返回該節(jié)點；如果要查找的值小于當(dāng)前節(jié)點的值，則遞歸地在左子樹中查找；如果要查找的值大于當(dāng)前節(jié)點的值，則遞歸地在右子樹中查找。```cTreeNodesearch(TreeNoderoot,intdata){if(root==NULL||root->data==data){returnroot;}if(data<root->data){returnsearch(root->left,data);}returnsearch(root->right,data);}```刪除操作：刪除操作比較復(fù)雜，需要考慮三種情況：要刪除的節(jié)點是葉子節(jié)點、只有一個子節(jié)點、有兩個子節(jié)點。對于有兩個子節(jié)點的情況，通常是找到右子樹中的最小節(jié)點（或左子樹中的最大節(jié)點）來替換要刪除的節(jié)點。問題6：如何實現(xiàn)二叉樹的前序、中序和后序遍歷前序遍歷：根節(jié)點->左子樹->右子樹```cvoidpreOrder(TreeNoderoot){if(root!=NULL){printf("%d",root->data);preOrder(root->left);preOrder(root->right);}}```中序遍歷：左子樹->根節(jié)點->右子樹```cvoidinOrder(TreeNoderoot){if(root!=NULL){inOrder(root->left);printf("%d",root->data);inOrder(root->right);}}```后序遍歷：左子樹->右子樹->根節(jié)點```cvoidpostOrder(TreeNoderoot){if(root!=NULL){postOrder(root->left);postOrder(root->right);printf("%d",root->data);}}```4.排序算法相關(guān)問題7：簡述快速排序的原理和實現(xiàn)快速排序是一種分治算法，其基本原理是選擇一個基準(zhǔn)元素，將數(shù)組分為兩部分，使得左邊部分的元素都小于等于基準(zhǔn)元素，右邊部分的元素都大于等于基準(zhǔn)元素，然后分別對左右兩部分遞歸地進行排序。以下是快速排序的C語言實現(xiàn)：```cinclude<stdio.h>//交換兩個元素voidswap(inta,intb){inttemp=a;a=b;b=temp;}//分區(qū)函數(shù)intpartition(intarr[],intlow,inthigh){intpivot=arr[high];inti=low1;for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);returni+1;}//快速排序函數(shù)voidquickSort(intarr[],intlow,inthigh){if(low<high){intpi=partition(arr,low,high);quickSort(arr,low,pi1);quickSort(arr,pi+1,high);}}//打印數(shù)組voidprintArray(intarr[],intsize){for(inti=0;i<size;i++){printf("%d",arr[i]);}printf("\n");}intmain(){intarr[]={10,7,8,9,1,5};intn=sizeof(arr)/sizeof(arr[0]);quickSort(arr,0,n1);printf("Sortedarray:\n");printArray(arr,n);return0;}```在`partition`函數(shù)中，選擇最后一個元素作為基準(zhǔn)元素，將小于等于基準(zhǔn)元素的元素交換到左邊，大于基準(zhǔn)元素的元素交換到右邊，最后將基準(zhǔn)元素放到正確的位置。`quickSort`函數(shù)遞歸地對左右兩部分進行排序。問題8：比較冒泡排序、選擇排序和插入排序的時間復(fù)雜度和穩(wěn)定性冒泡排序時間復(fù)雜度：平均和最壞情況下為O(n^2)，最好情況下（數(shù)組已經(jīng)有序）為O(n)。穩(wěn)定性：是穩(wěn)定的排序算法，因為在比較相鄰元素時，如果相等不會交換它們的位置。原理：重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。選擇排序時間復(fù)雜度：無論最好、最壞還是平均情況，時間復(fù)雜度都是O(n^2)。穩(wěn)定性：是不穩(wěn)定的排序算法，例如，對于數(shù)組`[5,8,5,2]`，在選擇最小元素時，會將第一個`5`和`2`交換位置，導(dǎo)致兩個`5`的相對順序改變。原理：在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。插入排序時間復(fù)雜度：平均和最壞情況下為O(n^2)，最好情況下（數(shù)組已經(jīng)有序）為O(n)。穩(wěn)定性：是穩(wěn)定的排序算法，因為在插入元素時，如果相等不會交換它們的位置。原理：將未排序數(shù)據(jù)插入到已排序序列的合適位置。5.哈希表相關(guān)問題9：簡述哈希表的原理和沖突解決方法哈希表是一種根據(jù)鍵（key）直接訪問內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)，它通過哈希函數(shù)將鍵映射到一個固定大小的數(shù)組中的某個位置。哈希函數(shù)的作用是將任意長度的鍵轉(zhuǎn)換為一個固定長度的整數(shù)，這個整數(shù)就是數(shù)組的索引。哈希沖突是指不同的鍵通過哈希函數(shù)計算得到相同的索引。常見的沖突解決方法有：開放尋址法：當(dāng)發(fā)生沖突時，通過一定的規(guī)則尋找下一個可用的位置。常見的開放尋址法有線性探測、二次探測和雙重哈希。例如，線性探測是指當(dāng)發(fā)生沖突時，依次檢查下一個位置，直到找到一個空位置。鏈地址法：每個哈希槽（數(shù)組元素）是一個鏈表的頭節(jié)點，當(dāng)發(fā)生沖突時，將新的鍵值對插入到對應(yīng)的鏈表中。這種方法的優(yōu)點是實現(xiàn)簡單，缺點是鏈表過長時查找效率會降低。問題10：如何用C語言實現(xiàn)一個簡單的哈希表以下是一個用C語言實現(xiàn)的簡單哈希表，使用鏈地址法解決沖突：```cinclude<stdio.h>include<stdlib.h>defineTABLE_SIZE10typedefstructNode{intkey;intvalue;structNodenext;}Node;typedefstructHashTable{Nodetable[TABLE_SIZE];}HashTable;//初始化哈希表voidinitHashTable(HashTableht){for(inti=0;i<TABLE_SIZE;i++){ht->table[i]=NULL;}}//哈希函數(shù)inthashFunction(intkey){returnkey%TABLE_SIZE;}//插入鍵值對voidinsert(HashTableht,intkey,intvalue){intindex=hashFunction(key);NodenewNode=(Node)malloc(sizeof(Node));newNode->key=key;newNode->value=value;newNode->next=ht->table[index];ht->table[index]=newNode;}//查找鍵對應(yīng)的值intsearch(HashTableht,intkey){intindex=hashFunction(key);Nodecurrent=ht->table[index];while(current!=NULL){if