嵌入式面试中常见的一些编程题目
嵌入式面试中常见的一些编程题目注：本文只是代码实现，并没有深入讲解实现原理，大家可以看一下主要会考什么，然后再具体针对性了解原理，也更有利于理解。
眼看26届秋招接近尾声，自己虽然很菜，但也在激烈的竞争中拿到了几个 offer，已经非常满意了，希望未来持续学习进步。
本文主要总结了嵌入式秋招中问的比较多的编程题目，总的来说，大部分不会涉及到复杂的算法题（我本身非科班，也没怎么刷题，秋招期间遇到手撕复杂算法的公司也是成功挂掉了），比较重要的是一些已有函数的实现，主要考察对数据在内存中分布的掌握，对C语言在嵌入式场景中理解的深度，比如 memcpy() 函数，遇到 dest 和 src 空间重合的问题是怎么处理的。其次就是各大排序，链表，字符串，数组的操作，二叉树的概念，遍历等等。
一、链表
链表的一些基础操作
[*]链表定义
struct Node {
int data;
struct Node* next;
}
[*]创建节点
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if(newNode == NULL)
printf("malloc failed!");
newNode->data = value;
newNode->next = NULL;
return newNode;
}
[*]头插法插入节点
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
newNode->next = head;
return newNode;// 新的头结点
}
[*]尾插法插入节点
struct Node* insertAtTail(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if(head == NULL)
return newNode;
struct Node* temp = head;
while(temp->next != NULL) {
temp = temp->text;
}
temp->next = newNode;
return head;
}
[*]遍历链表
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}1.实现链表的逆置
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) return NULL;
struct LiseNode* former;
struct ListNode* latter;
struct ListNode* mid = head;
while (mid != NULL) {
latter = mid->next;
mid->next = former;
former = mid;
mid = latter;
}
}2. 判断单链表中是否存在环
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
fast = head;
while(fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return NULL;
}3. 单链表相交，如何求交点
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
struct ListNode* p = headA;
struct ListNode* q = headB;
while(q != p) {
if (p == NULL)
p = headB;
else
p = p->next;
if (q == NULL)
q = headA;
else
q = q->next
}
return q;
}4. 求有环链表第一个入环点
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
fast = head;
while(fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return NULL;
}5. 写出链表的删除一个节点的程序
void deleteNode(Node** headRef, int key) {
Node* temp = *headRef;
Node* prev = NULL;
if (temp == NULL) return;
if (temp->data == key) {
*headRef = temp->next; // 头指针后移
free(temp); // 释放原头节点
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}6. 用递归算法实现两个有序链表的合并
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
if (pHead1 == NULL) return pHead2;
if (pHead2 == NULL) return pHead1;
if (pHead1->val > pHead2->val) {
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
} else {
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}
}二、二叉树
满二叉树：除了最后一层，所有的节点都是满的，并且所有节点都有两个子节点
完全二叉树：最后一层可以是单节点，所有节点连续几种在左边。
二叉搜索数：BST，左子树中的所有节点值都小于该节点值。右子树中的所有节点值都大于该节点值。
平衡二叉树：AVL，左右子节点的高度不超过1的BST。
// 定义二叉树节点结构
typedef struct Node {
int data; // 存储节点的数据
struct Node* left; // 指向左子节点
struct Node* right; // 指向右子节点
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败！\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 销毁二叉树
void destroyTree(Node* root) {
if (root == NULL) return;
destroyTree(root->left); // 递归释放左子树
destroyTree(root->right);// 递归释放右子树
free(root); // 释放当前节点
}
// 二叉树深度
int maxDepth(struct TreeNode* root){
if (root == NULL) return 0;
int lenLeft = maxDepth(root->left);
int lenRight = maxDepth(root->right);
return lenLeft > lenRight ? lenLeft + 1 : lenRight + 1;
}1. 遍历
// 中序遍历：创建一个数组，数组作为传入参数保存遍历的结果
/**
* returnNum: 保存遍历出的元素
* returnSize: 保存二叉树的大小
*/
void inTra(struct TreeNode* root, int *returnNum, int* returnSize)
{
if(root==NULL) return;
inTra(root->left, returnNum, returnSize);
returnNum[(*returnSize)++] = root->val;
inTra(root->right, returnNum, returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int *returnNum = (int *)malloc(sizeof(int)*101);
*returnSize = 0;
if(root==NULL) return NULL;
inTra(root,returnNum,returnSize);
return returnNum;
}不需要保存的遍历：
// 前序遍历：根 -> 左 -> 右
void preorderTraversal(Node* root) {
if (root == NULL) return;
printf("%d ", root->data);// 访问根节点
preorderTraversal(root->left);// 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
// 中序遍历：左 -> 根 -> 右
void inorderTraversal(Node* root) {
if (root == NULL) return;
inorderTraversal(root->left); // 遍历左子树
printf("%d ", root->data); // 访问根节点
inorderTraversal(root->right);// 遍历右子树
}
// 后序遍历：左 -> 右 -> 根
void postorderTraversal(Node* root) {
if (root == NULL) return;
postorderTraversal(root->left);// 遍历左子树
postorderTraversal(root->right); // 遍历右子树
printf("%d ", root->data); // 访问根节点
}2. 深度
int maxDepth(struct TreeNode* root) {
// 递归结束条件
if (root == NULL) return 0;
int l_depth = maxDepth(root->left);
int r_depth = maxDepth(root->right);
return (l_depth > r_depth ? l_depth : r_depth) + 1;
}3. 是否平衡二叉树
bool isAVL(struct TreeNode* root)
{
struct TreeNode* left= root->left;
struct TreeNode* right = root->right;
int l_dep = maxDepth(left);
int r_dep = maxDepth(right);
if (l_dep == r_dep) return true;
else if (l_dep > r_dep) return ((l_dep-r_dep) < 1 ? true : false);
else return ((r_dep-l_dep) < 1 ? true : false);
}三、排序查找算法及其改进
我想对于每一个经历过秋招的小伙伴们来说，十大排序基本都被问过（快速排序、归并排序、堆排序、冒泡排序、插入排序、选择排序、希尔排序、桶排序、基数排序）。
排序名称最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度快排$O(nlogn)$$O(nlogn)$$O(n^2)$$O(logn)$归并$O(nlogn)$$O(nlogn)$$O(nlogn)$$O(n)$插入$O(n)$$O(n^2)$$O(n^2)$$O(1)$冒泡$O(n)$$O(n^2)$$O(n^2)$$O(1)$堆排$O(nlogn)$$O(nlogn)$$O(nlogn)$$O(1)$选择$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$1. 快速排序
void quickSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int pivot = arr;
int l = left - 1;
int r = left;
for (; r < right; ++r) {
if (arr < pivot) {
l++;
swap(arr, arr);
}
}
int povitIndex = l + 1;
swap(arr, arr);
quickSort(arr, left, povitIndex - 1);
quickSort(arr, povitIndex + 1, right);
}2. 冒泡排序
// 双重循环，每次循环次数减1.长度为5的数组，第一次循环对比4次
void bubble_sort(int *arr, int n) {
int flag;
for (int i = 0; i < n-1; i++) {
flag = 0;
for (int j = 0; j < n-1-i; j++) {
if (arr > arr) {
swap(&arr, &arr);
flag = 1;
}
}
if (flag == 0) return;
}
}3. 归并排序
/*
* 归并排序的思想：
* 1. merge函数，传入一个以m为界限的左右分别排序好的数组，然后把这个数组合并
* 1.1 首先malloc两个数组L，R然后填充，然后使用? :填充arr
* 2. mergeSort函数递归执行，停止条件l>=r;
*/
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(arr.begin() + left, arr.begin() + left + n1); // 或 mid + 1
vector<int> R(arr.begin() + mid + 1, arr.begin() + mid + 1 + n2); // 或 right + 1
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) arr = L < R ? L : R;
while (i < n1) arr = L;
while (j < n2) arr = R;
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left)/2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}4. 堆排序
堆的数组表示：
对于数组中一个位置为i的节点（下标从0开始），
[*]父节点：(i-1)/2
[*]左子节点2i+1
[*]右子节点2i+2
最后一个非叶子节点的下标是n/2 - 1。n是数组长度。
最大堆：每个父节点大于子节点。
最小堆：每个子节点大于父节点。
构建最大堆，排序
/**
* @brief 堆化函数
*
* 这是堆排序的核心。它将以 i 为根的子树调整为大顶堆。
* 假设 i 的左右子树已经是大顶堆。
*
* @param arr待排序的数组
* @param n 数组的大小，也是堆中元素的总数
* @param i 当前需要堆化的子树的根节点索引
*/
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr > arr) largest = left;
if (right < n && arr > arr) largest = right;
if (largest != i) {
std::swap(arr, arr);
heapify(arr, n, largest);
}
}
void maxHeap(std::vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
}
void heapSort(std::vector<int>& arr) {
int n = arr.size();
maxHeap(arr);
for (int i = n - 1; i > 0; i--) {
std::swap(arr, arr);
heapify(arr, i, 0);
}
}使用priority_heap容器适配器实现的堆排列
void heapSortUsingPriorityQueue(std::vector<int>& arr) {
if (arr.empty()) {
return;
}
// 1. 创建一个最大堆（默认行为）
// 将数组中的所有元素放入优先队列
std::priority_queue<int> max_heap;
for (int val : arr) {
max_heap.push(val);
}
// 2. 依次取出最大元素，并存回原数组
// 此时元素是按从大到小的顺序被取出的
int index = 0;
while (!max_heap.empty()) {
arr = max_heap.top(); // 获取最大值
max_heap.pop(); // 从堆中移除
index++;
}
// 3. 因为得到的是降序序列，需要反转数组才能得到升序结果
std::reverse(arr.begin(), arr.end());
}5. 插入排序
// 从第二个数开始往前插入数，前面部分是排序好的，假如有n=5个数据，第一次插入a，第4次插入a。
// 所以外循环n-1次，从index=1开始。从j = i - 1依次向左比较，直到比较到最低位或者小于key的数。
// 两个关键点，i是需要插入的索引key=arr，i左边也就是j=i-1是排序好的节点，然后向左比对，当arr<key时，arr=key。
void insertSort(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i){
// i=2插入到前面排序好的数组，跟前面的一一比较
int key = arr;
int j = i-1;
while (j >= 0 && arr > key) {
arr = arr;
j--;
}
arr = key;
}
}6. 选择排序
// 选择排序函数（升序）
// 遍历数组，第一遍找出最小的放到第一个位置，第二遍从开始，找出最小的，以此类推
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr < arr) minIndex = j;
}
if (minIndex != i) swap(arr, arr);
}
}四、数组
二分查找法
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left)/2;
if (nums == target) return mid;
else if (nums < target) left = mid + 1;
else right = mid - 1;
}
return left;
}void mucpy(char *s1, char *s2) {
while(*s1++ = *s2++);
}#include #include #include #include using namespace std;// 图的邻接表表示vector graph = { {1, 2}, // 0 {0, 3, 4},// 1 {0, 4}, // 2 {1}, // 3 {1, 2} // 4};vector visited(5, false); // 记录节点是否被访问过// 深度优先搜索（DFS）- 递归实现void dfs(int node) { visited = true; cout 感谢发布原创作品，程序园因你更精彩 鼓励转贴优秀软件安全工具和文档！
页:
[1]