2025年高频c数据结构基础面试题及答案

2025年高频c数据结构基础面试题及答案1.数据结构基础概念类问题1：什么是数据结构，列举常见的数据结构类型数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它研究的是数据的组织、存储和操作方式，目的是为了更高效地处理数据。常见的数据结构类型包括：线性结构数组：是一种连续存储相同类型数据的线性数据结构，通过下标可以快速访问元素。例如，在C语言中定义一个整数数组`intarr[5]={1,2,3,4,5};`，可以使用`arr[2]`快速访问到数组中第3个元素（下标从0开始）。链表：由节点组成，每个节点包含数据域和指针域。链表分为单链表、双链表和循环链表。单链表的节点只有一个指向下一个节点的指针，双链表的节点有指向前一个节点和后一个节点的指针，循环链表的尾节点指向头节点。例如，单链表节点的C语言定义如下：```ctypedefstructNode{intdata;structNodenext;}Node;```栈：遵循后进先出（LIFO）原则的线性数据结构，只能在栈顶进行插入（入栈）和删除（出栈）操作。可以使用数组或链表来实现栈。队列：遵循先进先出（FIFO）原则的线性数据结构，有队头和队尾，元素从队尾插入（入队），从队头删除（出队）。同样可以使用数组或链表实现队列。非线性结构树：是一种层次结构，由节点和边组成，有一个根节点，每个节点可以有零个或多个子节点。常见的树有二叉树、二叉搜索树、AVL树、红黑树等。例如，二叉树节点的C语言定义如下：```ctypedefstructTreeNode{intdata;structTreeNodeleft;structTreeNoderight;}TreeNode;```图：由顶点和边组成，用于表示多对多的关系。图分为有向图和无向图，有向图的边有方向，无向图的边没有方向。问题2：简述数组和链表的优缺点数组的优点随机访问效率高：可以通过下标直接访问数组中的任意元素，时间复杂度为O(1)。例如，要访问数组`arr`的第`i`个元素，直接使用`arr[i]`即可。内存空间连续：数组在内存中是连续存储的，因此缓存命中率高，能提高访问速度。数组的缺点插入和删除效率低：在数组中插入或删除元素时，需要移动大量元素，时间复杂度为O(n)。例如，在数组中间插入一个元素，需要将插入位置之后的所有元素向后移动一位。大小固定：数组的大小在定义时就已经确定，不能动态扩展。如果需要存储更多元素，需要重新分配更大的数组并复制元素。链表的优点插入和删除效率高：在链表中插入或删除节点，只需要修改指针，时间复杂度为O(1)（如果已知要操作的节点位置）。例如，在单链表中插入一个新节点，只需要修改新节点的指针和前一个节点的指针。动态分配内存：链表的节点可以在需要时动态分配内存，不需要预先分配固定大小的空间。链表的缺点随机访问效率低：要访问链表中的某个节点，需要从头节点开始遍历，时间复杂度为O(n)。内存开销大：链表的每个节点除了存储数据外，还需要存储指针，增加了内存开销。2.栈和队列相关问题3：如何用数组实现一个栈以下是用数组实现栈的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;}```在这个实现中，使用一个数组`arr`来存储栈中的元素，`top`指针表示栈顶的位置。初始化时，`top`为-1表示栈为空。入栈操作将元素添加到`arr[++top]`位置，出栈操作返回`arr[top--]`位置的元素。问题4：如何用两个栈实现一个队列可以使用两个栈`stack1`和`stack2`来实现一个队列。`stack1`用于入队操作，`stack2`用于出队操作。具体实现如下：```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`中弹出元素。这样就实现了队列的先进先出特性。3.树相关问题5：简述二叉搜索树（BST）的特点和操作二叉搜索树（BST）是一种特殊的二叉树，具有以下特点：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值。对于树中的每个节点，其右子树中的所有节点的值都大于该节点的值。左右子树也分别是二叉搜索树。二叉搜索树的常见操作包括：插入操作：从根节点开始，比较要插入的值和当前节点的值。如果要插入的值小于当前节点的值，则递归地插入到左子树中；如果要插入的值大于当前节点的值，则递归地插入到右子树中。```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;}```查找操作：从根节点开始，比较要查找的值和当前节点的值。如果相等，则返回该节点；如果要查找的值小于当前节点的值，则递归地在左子树中查找；如果要查找的值大于当前节点的值，则递归地在右子树中查找。```cTreeNodesearch(TreeNoderoot,intdata){if(root==NULL||root->data==data){returnroot;}if(data<root->data){returnsearch(root->left,data);}returnsearch(root->right,data);}```删除操作：删除操作比较复杂，需要考虑三种情况：要删除的节点是叶子节点、只有一个子节点、有两个子节点。对于有两个子节点的情况，通常是找到右子树中的最小节点（或左子树中的最大节点）来替换要删除的节点。问题6：如何实现二叉树的前序、中序和后序遍历前序遍历：根节点->左子树->右子树```cvoidpreOrder(TreeNoderoot){if(root!=NULL){printf("%d",root->data);preOrder(root->left);preOrder(root->right);}}```中序遍历：左子树->根节点->右子树```cvoidinOrder(TreeNoderoot){if(root!=NULL){inOrder(root->left);printf("%d",root->data);inOrder(root->right);}}```后序遍历：左子树->右子树->根节点```cvoidpostOrder(TreeNoderoot){if(root!=NULL){postOrder(root->left);postOrder(root->right);printf("%d",root->data);}}```4.排序算法相关问题7：简述快速排序的原理和实现快速排序是一种分治算法，其基本原理是选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后分别对左右两部分递归地进行排序。以下是快速排序的C语言实现：```cinclude<stdio.h>//交换两个元素voidswap(inta,intb){inttemp=a;a=b;b=temp;}//分区函数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;}//快速排序函数voidquickSort(intarr[],intlow,inthigh){if(low<high){intpi=partition(arr,low,high);quickSort(arr,low,pi1);quickSort(arr,pi+1,high);}}//打印数组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`函数中，选择最后一个元素作为基准元素，将小于等于基准元素的元素交换到左边，大于基准元素的元素交换到右边，最后将基准元素放到正确的位置。`quickSort`函数递归地对左右两部分进行排序。问题8：比较冒泡排序、选择排序和插入排序的时间复杂度和稳定性冒泡排序时间复杂度：平均和最坏情况下为O(n^2)，最好情况下（数组已经有序）为O(n)。稳定性：是稳定的排序算法，因为在比较相邻元素时，如果相等不会交换它们的位置。原理：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。选择排序时间复杂度：无论最好、最坏还是平均情况，时间复杂度都是O(n^2)。稳定性：是不稳定的排序算法，例如，对于数组`[5,8,5,2]`，在选择最小元素时，会将第一个`5`和`2`交换位置，导致两个`5`的相对顺序改变。原理：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。插入排序时间复杂度：平均和最坏情况下为O(n^2)，最好情况下（数组已经有序）为O(n)。稳定性：是稳定的排序算法，因为在插入元素时，如果相等不会交换它们的位置。原理：将未排序数据插入到已排序序列的合适位置。5.哈希表相关问题9：简述哈希表的原理和冲突解决方法哈希表是一种根据键（key）直接访问内存存储位置的数据结构，它通过哈希函数将键映射到一个固定大小的数组中的某个位置。哈希函数的作用是将任意长度的键转换为一个固定长度的整数，这个整数就是数组的索引。哈希冲突是指不同的键通过哈希函数计算得到相同的索引。常见的冲突解决方法有：开放寻址法：当发生冲突时，通过一定的规则寻找下一个可用的位置。常见的开放寻址法有线性探测、二次探测和双重哈希。例如，线性探测是指当发生冲突时，依次检查下一个位置，直到找到一个空位置。链地址法：每个哈希槽（数组元素）是一个链表的头节点，当发生冲突时，将新的键值对插入到对应的链表中。这种方法的优点是实现简单，缺点是链表过长时查找效率会降低。问题10：如何用C语言实现一个简单的哈希表以下是一个用C语言实现的简单哈希表，使用链地址法解决冲突：```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;}}//哈希函数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;}//查找键对应的值intsearch(HashTableht,intkey){intindex=hashFunction(key);Nodecurrent=ht->table[index];while(current!=NULL){if