本篇内容包括有：嵌入式软件开发笔试题型、知识点，如何准备笔试

笔试是非常关键的一个环节，不论你有多大的才干和多么广博的知识，如果未能通过笔试，则无缘下面的面试，所以千万不要让自己卡在笔试上。相关公司笔试真题见该专栏已发布的题目。

目前几乎所有的公司都要求进行笔试，笔试编程语言大多是是自行选择，而外企的话要要求具备一定的英语基础。

题型

(1) 纯编程题。例如：华为3道编程题，每道题的分值分别是100，200，300分；百度也是3道编程题，满分100分；亚马逊两道编程题，全英文的；阿里云笔试两道编程题；

(2) 纯选择题。例如：TCL；

(3) 选择题+编程题。例如：OPPO 20道选择题+3道编程题；蔚来10道单选+5道多选+3道编程题；中兴选择题+两道编程题；intel 35道选择题+3道编程题；

(4) 选择题+判断题+填空题+简答题+编程题。例如：大疆嵌入式单选+多选+判断+填空+简答+两道编程；大疆测试开发单选+多选+简答题；联发科10道不定项+1道简答题+7道填空题+1道编程题；摩尔线程30道单选+6道简答题（包含程序题）；经纬恒润10道单选+6道多选+5道填空+2道编程；比特大陆/算能15道不定项+5道填空题+3道简答题（算是编程题）；

(5) 纯是行测题。例如京东硬件产品经理岗；

知识点

(1) 选题/填空题考核知识点：

涉及到C/C++语言、数据结构与算法、操作系统知识点一般是Linux、Android知识点、计算机网络内容一般是TCP/IP、数学逻辑推理或计算题；

具体的公司会添加响应的知识点考核，例如intel的笔试，考察的内容有：operating system，computer graphics, C, C++, data structure, algorithms，5G，计算机组成原理，还包括了各种芯片知识等等。

(2) 编程题考核知识点：

字符串，由于字符串是程序里经常需要处理的数据类型，因此有很多针对字符串处理的题目，华为笔试第一个大概率就是字符串的处理题；

链表、栈、队列，考核链表偏多；

排序算法，常用的冒泡、选择、插入、快排、归并排序等，笔试直接考核这种题型比较少，一般会在面试手撕或者口述代码输出结果，例如快排13254，写出每次排序后的输出；

二叉树，核心就是树的递归和树的遍历；

深度优先搜索、广度优先搜索、回溯法、动态规划、二分法、双指针、哈希表使用等等。

笔试准备

如何应对选择题？

(1) 看书，整理与梳理相关的知识点，其实也能为面试做准备。主要是C/C++语言、操作系统、计算机网路等。作者主要看的书籍有《C程序设计》、《C++ Primer Plus》（前面18章内容）、《数据结构》（陈越）、《大话数据结构》、《趣学算法》、《操作系统导论》（主要是前面31章内容）、《正点原子MP157开发指南》、《linux设备驱动开发详解》等；

(2) 牛客网-题目-（专项练习-C语言、C++、Linux、FreeRTOS等）

(3) 往年企业笔试选择题真题

如何应对编程题？

对于我们来说，编程题就是为了应对笔试和面试中的手撕。所以推荐三本有益于笔试的书籍，分别是《代码随想录》《剑指offer》《LeetCode 101》。

到底如何科学刷题？你可以按照以下的路径去刷200道经典题型：

链表、栈、队列

链表的基本知识：

单链表：单链表中的节点只能指向节点的下一个节点

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点

循环链表：链表首尾相连

链表的存储方式：链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表经典题：

1. 反转链表LeetCode 206

2. 相交链表LeetCode 160

3. 合并两个有序链表LeetCode 21

4. 分隔链表LeetCode 86

5. 环形链表II (LeetCode 142)

6. 反转链表II (LeetCode 92)

7. 复制带随机指针的链表(LeetCode 138)

栈的基本知识：

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

栈顶top：线性表允许插入和删除的那一端。

栈底bottom：固定的，不允许进行插入和删除的另一端。

由于只能在栈顶进行插入和删除操作，故进栈顺序为a1,a2, … ,an，出栈顺序为an, … ,a2,a1。故栈的操作特性是后进先出LIFO。

C++栈的基本用法：

push(): 向栈内压入一个成员；

pop(): 从栈顶弹出一个成员；

empty(): 如果栈为空返回true，否则返回false；

top(): 返回栈顶，但不删除成员；

size(): 返回栈内元素的大小；

例子：

#include<iostream>
#include<stack>
using namespace std;


int main()
{
    stack <int>stk;
    //入栈
    for(int i=0;i<50;i++){
        stk.push(i);
    }
    cout<<"栈的大小:"<<stk.size()<<endl;
    while(!stk.empty())
    {
        cout<<stk.top()<<endl;
        stk.pop();
    }
    cout<<"栈的大小:"<<stk.size()<<endl;
    return 0;
}

栈经典题：

1. 有效的括号LeetCode 20

2. 基本计算器LeetCode 224

3. 最小栈LeetCode 155

4. 验证栈序列LeetCode 946

5. 每日温度LeetCode 739

队列的基本知识：

队列是限制结点插入操作固定在一端进行,而结点的删除操作固定在另一端进行的线性表。允许插入的一端称为队尾（tail），允许删除的一端称为队头（front）。队头和队尾各用一个”指针”指示,称为队头指针和队尾指针。

顺序队列：

循环队列：

队列为满的条件：(rear+1) % MaxSize == front

队列为空的条件：front == rear

队列中元素的个数：(rear- front + maxSize) % MaxSize

入队：rear = (rear + 1) % maxSize

出队：front = (front + 1) % maxSize

C++单向队列的基本操作：

queue入队，如例：q.push(x); 将x 接到队列的末端。

queue出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问queue队首元素，如例：q.front()，即最早被压入队列的元素。

访问queue队尾元素，如例：q.back()，即最后被压入队列的元素。

判断queue队列空，如例：q.empty()，当队列空时，返回true。

访问队列中的元素个数，如例：q.size()

C++双向队列的基本操作：

添加函数：

头部添加元素：deq.push_front(const T& x);

末尾添加元素：deq.push_back(const T& x);

任意位置插入一个元素：deq.insert(iterator it, const T& x);

任意位置插入 n 个相同元素：deq.insert(iterator it, int n, const T& x);

插入另一个向量的 [forst,last] 间的数据：deq.insert(iterator it, iterator first, iterator last);

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;

	// 头部增加元素
	deq.push_front(4);
	// 末尾添加元素
	deq.push_back(5);
	// 任意位置插入一个元素
	deque<int>::iterator it = deq.begin();
	deq.insert(it, 2);
	// 任意位置插入n个相同元素
	it = deq.begin(); // 必须要有这句
	deq.insert(it, 3, 9);
	// 插入另一个向量的[forst,last]间的数据
	deque<int> deq2(5,8);
	it = deq.begin(); // 必须要有这句
	deq.insert(it, deq2.end() - 1, deq2.end());

	// 遍历显示
	for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " "; // 输出：8 9 9 9 2 4 5
	cout << endl;

	return 0;
}

删除函数：

头部删除元素：deq.pop_front();

末尾删除元素：deq.pop_back();

任意位置删除一个元素：deq.erase(iterator it);

删除 [first,last] 之间的元素：deq.erase(iterator first, iterator last);

清空所有元素：deq.clear();

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	for (int i = 0; i < 8; i++)
		deq.push_back(i);

	// 头部删除元素
	deq.pop_front();
	// 末尾删除元素
	deq.pop_back();
	// 任意位置删除一个元素
	deque<int>::iterator it = deq.begin();
	deq.erase(it);
	// 删除[first,last]之间的元素
	deq.erase(deq.begin(), deq.begin()+1);

	// 遍历显示
	for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " ";
	cout << endl;

	// 清空所有元素
	deq.clear();

	// 遍历显示
	for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " "; // 输出：3 4 5 6
	cout << endl;

	return 0;
}

访问函数：

下标访问：deq[1]; // 并不会检查是否越界

at 方法访问：deq.at(1); // 以上两者的区别就是 at 会检查是否越界，是则抛出 out of range 异常

访问第一个元素：deq.front();

访问最后一个元素：deq.back();

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	for (int i = 0; i < 6; i++)
		deq.push_back(i);

	// 下标访问
	cout << deq[0] << endl; // 输出：0
	// at方法访问
	cout << deq.at(0) << endl; // 输出：0
	// 访问第一个元素
	cout << deq.front() << endl; // 输出：0
	// 访问最后一个元素
	cout << deq.back() << endl; // 输出：5

	return 0;
}

队列经典题：

1. 用栈实现队列LeetCode 232

2. 滑动窗口最大值LeetCode 239

3. 设计循环双端队列LeetCode 641

4. 移除链表元素LeetCode 203

5. K 个一组翻转链表LeetCode 25

6. 回文链表LeetCode 234

7. 奇偶链表LeetCode 328

8. 从尾到头打印链表（剑指Offer 06）

9. 链表中倒数第 k 个节点（剑指Offer 22）

排序、贪心、哈希

排序算法基本知识

稳定：如果a原本在b前面，而a=b时，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b时，排序之后a可能出现在b的后面。

冒泡排序：

void bubbleSort(vector<int> &arr) {
    int temp = 0;
    for (int i =arr.size() - 1; i>0; i--) { // 每次需要排序的长度
        for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

 针对所有的元素重复以上的步骤，除了最后一个。

 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

选择排序：

void selectionSort(vector<int> &arr) {
    int temp, min = 0;
    for (int i = 0; i < arr.size() - 1; i++) {
        min = i;
        // 循环查找最小值
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

实现逻辑：

①第一轮从下标为 1 到下标为 n-1 的