笔试面试01 c/c++

基础知识

1. 什么是数据结构？请简要描述常见的数据结构类型。
   数据结构是组织和存储数据的方式，以便于高效访问和修改。常见的数据结构包括：
   数组：固定大小的线性数据结构，支持随机访问。
   链表：由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。
   栈：后进先出（LIFO）的数据结构，支持 push 和 pop 操作。
   队列：先进先出（FIFO）的数据结构，支持入队和出队操作。
   哈希表：通过哈希函数将键映射到值的集合，支持快速查找。
   树：层次结构的数据结构，常见的有二叉树、二叉搜索树等。
   图：由节点和边组成的非线性数据结构，用于表示关系。

2. 解释时间复杂度和空间复杂度的概念。如何评估算法的效率？
   时间复杂度：表示算法执行所需时间的增长率，通常用大 O 表示法表示（如 O(n)、O(log n)）。
   空间复杂度：表示算法所需空间的增长率，也用大 O 表示法表示。
   评估算法的效率通常通过分析其时间复杂度和空间复杂度，比较不同算法在处理相同问题时的性能。

3. 什么是递归？请给出一个递归的例子。
   递归是指函数直接或间接调用自身的编程技术。递归通常由基本情况和递归情况组成。

例子：计算阶乘的递归函数

int factorial(int n) {if (n == 0) {return 1; // 基本情况}return n * factorial(n - 1); // 递归情况
}

4. 描述栈和队列的区别，并给出它们的应用场景。
   栈：
   后进先出（LIFO）结构。
   应用场景：函数调用管理、表达式求值、撤销操作。
   队列：
   先进先出（FIFO）结构。
   应用场景：任务调度、消息队列、打印任务管理。

编程题

编写一个函数，反转一个链表。

struct ListNode {int val;struct ListNode *next;
};struct ListNode* reverseList(struct ListNode* head) {struct ListNode *prev = NULL, *current = head, *next = NULL;while (current != NULL) {next = current->next; // 保存下一个节点current->next = prev; // 反转指针prev = current;       // 移动 prev 和 currentcurrent = next;}return prev; // 新的头节点
}

编写一个 C 程序，判断一个字符串是否是回文。

int isPalindrome(char *s) {int left = 0, right = strlen(s) - 1;while (left < right) {if (s[left] != s[right]) {return 0; // 不是回文}left++;right--;}return 1; // 是回文
}

给定一个数组，编写一个函数，找出数组中的最大值和最小值。

void findMaxMin(int arr[], int size, int *max, int *min) {*max = arr[0];*min = arr[0];for (int i = 1; i < size; i++) {if (arr[i] > *max) {*max = arr[i];}if (arr[i] < *min) {*min = arr[i];}}
}

算法题

实现快速排序算法。

void quickSort(int arr[], int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}
}int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}

实现二分搜索算法。

int binarySearch(int arr[], int size, int target) {int left = 0, right = size - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标}if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 未找到目标
}

编写一个函数，找出斐波那契数列的第 n 项。

unsigned long long fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n - 1) + fibonacci(n - 2);
}

进阶题

给定一个无序数组，编写一个函数找出其中的第 k 大元素。

#include <stdio.h>
#include <stdlib.h>// 交换两个整数
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 分区函数
int partition(int arr[], int left, int right, int pivotIndex) {int pivotValue = arr[pivotIndex];swap(&arr[pivotIndex], &arr[right]); // 将 pivot 移到末尾int storeIndex = left;for (int i = left; i < right; i++) {if (arr[i] > pivotValue) { // 找第 k 大元素，使用大于swap(&arr[storeIndex], &arr[i]);storeIndex++;}}swap(&arr[storeIndex], &arr[right]); // 将 pivot 移回return storeIndex;
}// 快速选择函数
int quickSelect(int arr[], int left, int right, int k) {if (left == right) {return arr[left]; // 只有一个元素}int pivotIndex = left + rand() % (right - left + 1); // 随机选择 pivotpivotIndex = partition(arr, left, right, pivotIndex);// 计算 pivot 的位置if (k == pivotIndex) {return arr[k]; // 找到第 k 大元素} else if (k < pivotIndex) {return quickSelect(arr, left, pivotIndex - 1, k); // 在左侧} else {return quickSelect(arr, pivotIndex + 1, right, k); // 在右侧}
}// 主函数
int findKthLargest(int* nums, int numsSize, int k) {// k 是第 k 大元素，转换为索引return quickSelect(nums, 0, numsSize - 1, k - 1);
}// 测试
int main() {int arr[] = {3, 2, 1, 5, 6, 4};int k = 2; // 找出第 2 大元素int size = sizeof(arr) / sizeof(arr[0]);int result = findKthLargest(arr, size, k);printf("The %dth largest element is %d\n", k, result);return 0;
}

实现一个简单的哈希表。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 10 // 哈希表大小// 哈希表节点
typedef struct Node {int key;int value;struct Node* next; // 链表中的下一个节点
} Node;// 哈希表结构
typedef struct HashTable {Node** table; // 指向节点指针的数组
} HashTable;// 哈希函数
int hash(int key) {return key % TABLE_SIZE;
}// 创建哈希表
HashTable* createHashTable() {HashTable* ht = malloc(sizeof(HashTable));ht->table = malloc(sizeof(Node*) * TABLE_SIZE);for (int i = 0; i < TABLE_SIZE; i++) {ht->table[i] = NULL; // 初始化为 NULL}return ht;
}// 插入键值对
void insert(HashTable* ht, int key, int value) {int index = hash(key);Node* newNode = malloc(sizeof(Node));newNode->key = key;newNode->value = value;newNode->next = ht->table[index]; // 插入到链表头部ht->table[index] = newNode;
}// 查找值
int search(HashTable* ht, int key) {int index = hash(key);Node* current = ht->table[index];while (current != NULL) {if (current->key == key) {return current->value; // 找到值}current = current->next;}return -1; // 未找到
}// 删除键值对
void delete(HashTable* ht, int key) {int index = hash(key);Node* current = ht->table[index];Node* prev = NULL;while (current != NULL) {if (current->key == key) {if (prev == NULL) {ht->table[index] = current->next; // 删除头节点} else {prev->next = current->next; // 删除中间或尾节点}free(current);return;}prev = current;current = current->next;}
}// 释放哈希表
void freeHashTable(HashTable* ht) {for (int i = 0; i < TABLE_SIZE; i++) {Node* current = ht->table[i];while (current != NULL) {Node* temp = current;current = current->next;free(temp);}}free(ht->table);free(ht);
}// 测试
int main() {HashTable* ht = createHashTable();insert(ht, 1, 100);insert(ht, 2, 200);insert(ht, 12, 300); // 12 会与 2 哈希到同一位置printf("Value for key 1: %d\n", search(ht, 1)); // 输出 100printf("Value for key 2: %d\n", search(ht, 2)); // 输出 200printf("Value for key 12: %d\n", search(ht, 12)); // 输出 300delete(ht, 2);printf("Value for key 2 after deletion: %d\n", search(ht, 2)); // 输出 -1freeHashTable(ht);return 0;
}

设计与应用

设计一个简单的任务调度系统，描述其数据结构和算法。

1. 数据结构：使用队列来管理任务，使用结构体存储任务信息（如任务 ID、优先级、状态等）。
   任务结构体（Task）：
   用于表示一个任务的基本信息。

typedef struct Task {int id;                // 任务 IDchar name[50];        // 任务名称int priority;         // 任务优先级int burst_time;       // 任务所需的 CPU 时间struct Task* next;    // 指向下一个任务的指针
} Task;

任务队列（TaskQueue）：
用于存储待调度的任务。

typedef struct TaskQueue {Task* front;          // 队列前端Task* rear;           // 队列后端
} TaskQueue;

2. 算法: 实现任务的添加、删除和调度算法（如优先级调度）。
   任务添加：
   将新任务添加到任务队列中，按照优先级排序（高优先级在前）。

void enqueue(TaskQueue* queue, Task* newTask) {if (queue->front == NULL) {queue->front = newTask;queue->rear = newTask;newTask->next = NULL;} else {Task* current = queue->front;Task* previous = NULL;// 找到插入位置while (current != NULL && current->priority >= newTask->priority) {previous = current;current = current->next;}if (previous == NULL) {// 插入到队列前端newTask->next = queue->front;queue->front = newTask;} else {// 插入到中间或后端newTask->next = current;previous->next = newTask;}if (current == NULL) {// 更新队列后端queue->rear = newTask;}}
}

任务调度：
从队列中取出优先级最高的任务并执行。

Task* dequeue(TaskQueue* queue) {if (queue->front == NULL) {return NULL; // 队列为空}Task* taskToExecute = queue->front;queue->front = queue->front->next;if (queue->front == NULL) {queue->rear = NULL; // 队列变为空}return taskToExecute;
}

任务执行：
模拟任务的执行过程，输出任务信息。

void executeTask(Task* task) {printf("Executing Task ID: %d, Name: %s, Priority: %d, Burst Time: %d\n",task->id, task->name, task->priority, task->burst_time);// 这里可以添加实际的执行逻辑
}

3. 主函数示例

int main() {TaskQueue queue = {NULL, NULL}; // 初始化任务队列// 创建一些任务Task task1 = {1, "Task 1", 2, 5, NULL};Task task2 = {2, "Task 2", 1, 3, NULL};Task task3 = {3, "Task 3", 3, 2, NULL};// 添加任务到队列enqueue(&queue, &task1);enqueue(&queue, &task2);enqueue(&queue, &task3);// 执行任务Task* task;while ((task = dequeue(&queue)) != NULL) {executeTask(task);}return 0;
}

给定一个图，编写一个函数实现深度优先搜索（DFS）和广度优先搜索（BFS）。

#include <stdio.h>
#include <stdlib.h>#define MAX 100 // 最大节点数// 图的邻接表节点
typedef struct Node {int vertex;struct Node* next;
} Node;// 图的结构
typedef struct Graph {Node* adjList[MAX];int visited[MAX];int numVertices;
} Graph;// 创建图
Graph* createGraph(int vertices) {Graph* graph = malloc(sizeof(Graph));graph->numVertices = vertices;for (int i = 0; i < vertices; i++) {graph->adjList[i] = NULL;graph->visited[i] = 0; // 初始化访问状态}return graph;
}// 添加边
void addEdge(Graph* graph, int src, int dest) {Node* newNode = malloc(sizeof(Node));newNode->vertex = dest;newNode->next = graph->adjList[src];graph->adjList[src] = newNode;// 如果是无向图，添加反向边newNode = malloc(sizeof(Node));newNode->vertex = src;newNode->next = graph->adjList[dest];graph->adjList[dest] = newNode;
}// 深度优先搜索（DFS）
void DFS(Graph* graph, int vertex) {graph->visited[vertex] = 1; // 标记为已访问printf("%d ", vertex); // 处理节点Node* temp = graph->adjList[vertex];while (temp) {int connectedVertex = temp->vertex;if (!graph->visited[connectedVertex]) {DFS(graph, connectedVertex);}temp = temp->next;}
}// 广度优先搜索（BFS）
void BFS(Graph* graph, int startVertex) {int queue[MAX], front = 0, rear = 0;graph->visited[startVertex] = 1; // 标记为已访问queue[rear++] = startVertex; // 入队while (front < rear) {int currentVertex = queue[front++]; // 出队printf("%d ", currentVertex); // 处理节点Node* temp = graph->adjList[currentVertex];while (temp) {int connectedVertex = temp->vertex;if (!graph->visited[connectedVertex]) {graph->visited[connectedVertex] = 1; // 标记为已访问queue[rear++] = connectedVertex; // 入队}temp = temp->next;}}
}// 主函数
int main() {Graph* graph = createGraph(5); // 创建一个包含 5 个节点的图addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);printf("DFS traversal starting from vertex 0:\n");DFS(graph, 0);printf("\n");// 重置访问状态for (int i = 0; i < graph->numVertices; i++) {graph->visited[i] = 0;}printf("BFS traversal starting from vertex 0:\n");BFS(graph, 0);printf("\n");return 0;
}