C语言与数据结构及算法经典面试题目
C语言基础
1. int main() 和 void main()的区别是什么?
答案解析: int main()是C语言标准定义的主函数形式, 返回值表示程序执行状态 (0表示成功, 非0表示错误)。void main()非标准, 可能导致未定义行为, 部分编译器接受但不推荐。
示例代码:
int main() {
return 0; // 表示程序正常退出
}
2. const 关键字的作用是什么?
答案解析: const 用于定义常量, 防止变量被修改。修饰指针时, 需区分const int *p (指针指向的数据不可改) 和 int *const p (指针本身不可改)。
示例代码:
const int a = 10; // a不可修改
int b = 20;
const int *p = &b; // p指向的数据不可改
// *p = 30; // 错误
p = &a; // 正确
3. static 关键字在C语言中的作用?
答案解析: static 修饰局部变量时, 使其生命周期延长至程序结束, 存储在静态存储区; 修饰全局变量或函数时, 限制其作用域为当前文件。
示例代码:
#include <stdio.h>
void func() {
static int count = 0; // 保留值
count++;
printf("%d\n", count);
}
4. volatile 关键字的作用?
答案解析: volatile 告诉编译器变量可能被外部修改, 防止优化 (如寄存器缓存)。常用于多线程或硬件寄存器访问。
示例代码:
volatile int flag = 0; // 防止编译器优化
5. sizeof 和 strlen 的区别?
答案解析: sizeof 是操作符, 返回变量或类型的字节大小; strlen 是函数, 返回字符串长度 (不含\0)。
示例代码:
#include <stdio.h>
#include <string.h>
char str[] = "hello";
// printf("%zu\n", sizeof(str)); // 6 (含\0)
// printf("%zu\n", strlen(str)); // 5
指针与内存管理
6. 什么是野指针?如何避免?
答案解析: 野指针是指向非法内存的指针, 可能导致程序崩溃。避免方法: 初始化指针为NULL, 使用后置空, 检查指针有效性。
示例代码:
int *p = NULL; // 初始化为NULL
if (p != NULL) {
*p = 10; // 安全访问
}
7. 指针和引用的区别?
答案解析: 指针是存储地址的变量, 可变且可为空; 引用 (C++特性, C无引用) 是变量别名, 不可变且不可为空。C中常用指针模拟引用行为。
示例代码:
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
8. 解释内存泄漏及其检测方法。
答案解析: 内存泄漏指动态分配的内存未释放。检测方法: 使用工具如Valgrind, 手动检查malloc/free配对。
示例代码:
#include <stdlib.h>
int *p = malloc(sizeof(int));
if (p) {
*p = 10;
free(p); // 防止泄漏
p = NULL;
}
9. malloc 和 calloc 的区别?
答案解析: malloc 分配指定字节内存, 未初始化; calloc 分配并初始化为0。
示例代码:
#include <stdlib.h>
int *p1 = malloc(10 * sizeof(int)); // 未初始化
int *p2 = calloc(10, sizeof(int)); // 初始化为0
10. 什么是段错误 (Segmentation Fault)?
答案解析: 段错误通常由访问非法内存引起, 如解引用NULL指针、越界访问数组等。
示例代码:
int *p = NULL;
// *p = 10; // 将导致段错误
数据结构
链表
11. 实现单链表的逆序。
答案解析: 遍历链表, 逐个改变指针方向, 需三个指针 (prev, curr, next) 防止断链。时间复杂度O(n), 空间复杂度O(1)。
示例代码:
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
12. 检测链表中是否有环。
答案解析: 使用快慢指针(Floyd算法), 快指针每次走两步, 慢指针走一步, 若相遇则有环。时间复杂度O(n), 空间复杂度O(1)。
示例代码:
#include <stdbool.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
13. 合并两个有序链表。
答案解析: 递归或迭代比较节点值, 构造新链表。时间复杂度O(n+m), 空间复杂度O(1)(迭代)或O(n+m)(递归)。
示例代码:
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
struct ListNode* tail = &dummy;
dummy.next = NULL;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
14. 删除链表倒数第N个节点。
答案解析: 使用双指针, 快指针先走N步, 慢指针跟进, 找到倒数第N个节点前驱, 删除目标节点。时间复杂度O(n), 空间复杂度O(1)。
示例代码:
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummy = {0, head};
struct ListNode *fast = &dummy, *slow = &dummy;
for (int i = 0; i <= n; i++) fast = fast->next;
while (fast) {
fast = fast->next;
slow = slow->next;
}
struct ListNode* temp = slow->next;
slow->next = slow->next->next;
free(temp); // 在C中，记得释放被删除节点的内存
return dummy.next;
}
15. 查找链表中间节点。
答案解析: 快慢指针法, 慢指针走一步, 快指针走两步, 快指针到末尾时慢指针指向中间。时间复杂度O(n), 空间复杂度O(1)。
示例代码:
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
栈与队列
16. 用两个栈实现队列。
答案解析: 一个栈用于入队, 另一个栈用于出队, 需将入队栈元素倒序压入出队栈。入队O(1), 出队均摊O(1)。
示例代码:
// 伪代码，具体实现依赖栈的API
typedef struct {
Stack *stack1; // 入队栈
Stack *stack2; // 出队栈
} MyQueue;
void myQueuePush(MyQueue* obj, int x) {
stackPush(obj->stack1, x);
}
int myQueuePop(MyQueue* obj) {
if (stackIsEmpty(obj->stack2)) {
while (!stackIsEmpty(obj->stack1)) {
stackPush(obj->stack2, stackPop(obj->stack1));
}
}
return stackPop(obj->stack2);
}
17. 实现一个栈，支持获取最小元素 (MinStack)。
答案解析: 用两个栈, 一个存数据, 一个存当前最小值。每次压入时, 更新最小值栈。时间复杂度O(1)。
示例代码:
// 伪代码，具体实现依赖栈的API
typedef struct {
Stack *dataStack;
Stack *minStack;
} MinStack;
void minStackPush(MinStack* obj, int x) {
stackPush(obj->dataStack, x);
int currentMin = stackIsEmpty(obj->minStack) ? x : stackTop(obj->minStack);
stackPush(obj->minStack, (x < currentMin) ? x : currentMin);
}
int minStackGetMin(MinStack* obj) {
return stackTop(obj->minStack);
}
18. 判断括号字符串是否有效。
答案解析: 用栈检查括号匹配, 遇到左括号入栈, 右括号检查栈顶是否匹配。时间复杂度O(n), 空间复杂度O(n)。
示例代码:
#include <stdbool.h>
#include <string.h>
bool isValid(char *s) {
int n = strlen(s);
if (n % 2 != 0) return false;
char stack[n];
int top = -1;
for (int i = 0; s[i]; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
stack[++top] = s[i];
} else {
if (top == -1) return false;
if (s[i] == ')' && stack[top] != '(') return false;
if (s[i] == ']' && stack[top] != '[') return false;
if (s[i] == '}' && stack[top] != '{') return false;
top--;
}
}
return top == -1;
}
树与图
19. 实现二叉树的前序遍历。
答案解析: 前序遍历(根-左-右)可用递归或迭代(栈)。时间复杂度O(n), 空间复杂度O(h), h为树高。
示例代码 (递归):
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void preorderTraversal(struct TreeNode* root, int* res, int* returnSize) {
if (!root) return;
res[(*returnSize)++] = root->val;
preorderTraversal(root->left, res, returnSize);
preorderTraversal(root->right, res, returnSize);
}
20. 判断二叉树是否为二叉搜索树 (BST)。
答案解析: 中序遍历BST应为递增序列, 检查遍历结果是否满足。时间复杂度O(n), 空间复杂度O(h)。
示例代码:
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool isValidBSTHelper(struct TreeNode* root, long min, long max) {
if (!root) return true;
if (root->val <= min || root->val >= max) return false;
return isValidBSTHelper(root->left, min, root->val) &&
isValidBSTHelper(root->right, root->val, max);
}
bool isValidBST(struct TreeNode* root) {
return isValidBSTHelper(root, -2147483649L, 2147483648L); // LONG_MIN, LONG_MAX
}
... 更多问题填充 ...