基础知识
什么是数据结构？请简要描述常见的数据结构类型。
数据结构是组织和存储数据的方式，以便于高效访问和修改。常见的数据结构包括：
数组：固定大小的线性数据结构，支持随机访问。
链表：由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。
栈：后进先出（LIFO）的数据结构，支持 push 和 pop 操作。
队列：先进先出（FIFO）的数据结构，支持入队和出队操作。
哈希表：通过哈希函数将键映射到值的集合，支持快速查找。
树：层次结构的数据结构，常见的有二叉树、二叉搜索树等。
图：由节点和边组成的非线性数据结构，用于表示关系。解释时间复杂度和空间复杂度的概念。如何评估算法的效率？
时间复杂度：表示算法执行所需时间的增长率，通常用大 O 表示法表示（如 O(n)、O(log n)）。
空间复杂度：表示算法所需空间的增长率，也用大 O 表示法表示。
评估算法的效率通常通过分析其时间复杂度和空间复杂度，比较不同算法在处理相同问题时的性能。什么是递归？请给出一个递归的例子。
递归是指函数直接或间接调用自身的编程技术。递归通常由基本情况和递归情况组成。
例子：计算阶乘的递归函数
int factorial(int n) {
if (n == 0) {
return 1; // 基本情况
}
return n * factorial(n - 1); // 递归情况
}
- 描述栈和队列的区别，并给出它们的应用场景。
栈：
后进先出（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 和 current
current = 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); // 随机选择 pivot
pivotIndex = 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)); // 输出 100
printf("Value for key 2: %d\n", search(ht, 2)); // 输出 200
printf("Value for key 12: %d\n", search(ht, 12)); // 输出 300
delete(ht, 2);
printf("Value for key 2 after deletion: %d\n", search(ht, 2)); // 输出 -1
freeHashTable(ht);
return 0;
}
设计与应用
设计一个简单的任务调度系统，描述其数据结构和算法。
- 数据结构：使用队列来管理任务，使用结构体存储任务信息（如任务 ID、优先级、状态等）。
任务结构体（Task）：
用于表示一个任务的基本信息。
typedef struct Task {
int id; // 任务 ID
char name[50]; // 任务名称
int priority; // 任务优先级
int burst_time; // 任务所需的 CPU 时间
struct Task* next; // 指向下一个任务的指针
} Task;
任务队列（TaskQueue）：
用于存储待调度的任务。
typedef struct TaskQueue {
Task* front; // 队列前端
Task* rear; // 队列后端
} TaskQueue;
- 算法: 实现任务的添加、删除和调度算法（如优先级调度）。
任务添加：
将新任务添加到任务队列中，按照优先级排序（高优先级在前）。
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);
// 这里可以添加实际的执行逻辑
}
- 主函数示例
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;
}