❗❗如果本文对您有帮助，请不要吝啬您的评论、点赞、收藏与小花，这对我非常重要！谢谢！❗❗

本文所涉及的题目均为基于个人学习和理解重新表述的内容，仅供学习交流之用，不代表任何实际考试题目。如有雷同，纯属巧合。

岗位：嵌入式开发工程师

题型：

必做：12 道选择题，3 道编程题
选做：Linux（3 道选择题） + C++（7 道选择题） + 数据库（3 道选择题）

1、选择题

1.1

请问如下哈夫曼树的带权路径长度为 ==（A）==

Click To View Image

1. 19
2. 20
3. 17
4. 21

解答：

树的带权路径长度：从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和
哈夫曼树（最优二叉树）：带权路径长度达到最小的树
如上图所示的哈夫曼树的带权路径长度为：1*3 + 2*3 + 3*2 + 4*1 = 19

1.2

某程序的段表如下，则逻辑地址（1, 262）对应的物理地址为 ==（B）==

段号 段首址 段长度

0	400K	80K
1	128K	40K
2	780K	20K
3	1000K	30K

1. 780K + 2
2. 128K + 262
3. 130K
4. 390K

解答：

逻辑地址（1, 262）表示段号为 1，段内偏移为 262 的地址
段号为 1 的段首地址为 128K ，因此其表示的物理地址为 128K+262，选择 B 选项

1.3

以下哪种设备是数据链路层设备 ==（D）==

1. 路由器
2. 集线器
3. 适配器
4. 网桥

解答：

路由器，工作在网络层
集线器，工作在物理层
网络适配器，工作在数据链路层
网桥，工作在数据链路层

1.4

TCP 三次握手中，第二次握手后即收到 SYN+ACK 后，发起链接一方（客户端），处于哪个连接状态 ==（D）==

1. SYN-SETN
2. LISTEN
3. SYN-RECEIVED
4. ESTABLISHED

解答：

第二次握手时服务器发送 SYN-ACK 给客户端，客户端收到后进入 ESTABLISHED 状态，服务器端从 LISTEN 状态进入 SYN-RECEIVED 状态

1.5

汉诺塔问题是经典的递归问题。汉诺塔问题的描述大概是这样的：

总共有 A，B，C 三根圆柱，在 A 柱上从上到下，从小到大依次套着 n 个圆盘。现在我们要使用最少的步数将 A 柱上的所有圆盘移动到 C 柱上，并且移动后圆盘依旧从上到下、从小到大摆放在 C 柱上。

移动的过程遵从下面的规则：

1. 大圆盘不能压在小圆盘上面
2. 每次只能移动一个圆盘
3. 每次只能移动柱子最顶端的圆盘

本题要研究的与经典汉诺塔问题有些许不同，为双重汉诺塔问题，它的问题描述是这样的：

双重汉诺塔的包含 2n 个圆盘，它们有 n 种不同的尺寸，每一种尺寸的圆盘有两个。初始时依旧全部放在 A 柱子上，从上到下依次按照 1~2n 编号，即 2i-1 和 2i 的大小尺寸相同，但 2i-1 在 2i 的上面。现在要将所有圆盘移动到 C 柱上，且移动后编号从上到下依旧递增，即为 1~2n。

下面为双重汉诺塔输出移动过程中圆盘具体大小尺寸的部分代码段，将下列序号的内容填入（1），（1）中可以包含多个语句（语句可以重复填写），则正确的答案应该为 ==（①）==

① Move(n,sPos,tPos);
② Move(n,sPos,ePos);
③ Move(n,ePos,tPos);
④ Move(n,tPos,ePos);

int step;

void Move(int id, char from, char to) {
    printf("第%d步：将%d号型盘子%c-->%c\n", ++step, id, from, to);
    return;
}

void Hanoi(int n, char sPos, char tPos, char ePos) {
    if (n == 1) {
        Move(n, sPos, ePos);
    } else {
        Hanoi(n - 1, sPos, ePos, tPos);
        Move(n, sPos, ePos);
        Move(n, sPos, ePos);
        Hanoi(n - 1, tPos, sPos, ePos);
    }
}

void solve(int n, char sPos, char tPos, char ePos) {
    if (n == 1) {
        //_____(1)______
    } else {
        Hanoi(n - 1, sPos, tPos, ePos);
        Move(n, sPos, tPos);
        Hanoi(n - 1, ePos, sPos, tPos);
        Move(n, sPos, ePos);
        Hanoi(n - 1, tPos, ePos, sPos);
        Move(n, tPos, ePos);
        Hanoi(n - 1, sPos, tPos, ePos);
    }
}

1.6

某主存容量为 50MB，初始时刻 T0 全部分区空闲，采用 Best Fit 算法分配和释放内存，从初始到 T1 时刻，分配释放顺序为：分配 12MB，分配 23MB，释放 12MB，分配 9MB，分配 11MB，此时主存最大空闲分区大小是 ==（X）==

1. 6MB
2. 8MB
3. 9MB
4. 7MB

解答（存疑）：

最佳适应算法（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小
分配 12MB，再分配 23MB，| 12MB ❌ | 23MB ❌ | 15MB ✔ |
释放 12MB，| 12MB ✔ | 23MB ❌ | 15MB ✔ |
分配 9MB，使用能满足要求的最小空闲分区，| 9MB ❌ | 3MB ✔ | 23MB ❌ | 15MB ✔ |
分配 11MB，同理，| 9MB ❌ | 3MB ✔ | 23MB ❌ | 11MB ❌ | 4MB ✔ |
此时主存最大空闲分区大小应该为 4MB ？

1.7

由序列 1，2，4，5，6 构成的哈夫曼树是 ==（X）==

1. A. Click To View Image
2. B. Click To View Image
3. C. Click To View Image
4. D. Click To View Image

1.8

以下是某系统在某一时刻的状态，问当前系统状态 ==（A）==

ALLOCATION MAX AVAILABLE

	A B C	A B C	A B C
P0	0 0 3	0 0 4	1 4 0
P1	1 0 0	1 7 5
P2	1 3 5	2 3 5
P3	0 0 2	0 6 4
P4	0 0 1	0 6 5

1. 安全
2. 死锁
3. 不确定
4. 不安全

1.9

请问查找一个 N 个节点的单链表的倒数第 K 个节点的时间复杂度最快为？（N 很大，且远大于 K）==（A）==

1. O(N)
2. O(N^2)
3. O(K)
4. O(logN)
5. O(NlogN)

解答：

单链表可以使用快慢指针找到倒数第 K 个节点，流程如下：

1. 先让快指针移动 K 个节点
2. 然后同步移动快慢指针，每次移动一个节点
3. 当快指针指向最后一个节点时，此时慢指针就指向了倒数第 K 个节点

整个过程只需遍历一遍链表即可，因此时间复杂度为 O(N)，选择 A 选项

1.10

设有一棵 200 个节点的完全二叉树，从该树的根开始，每一层从左到右依次给节点进行编号，即根节点的编号为 1，那么编号为 99 的节点的左孩子编号是 ==（B）==

1. 99
2. 198
3. 199
4. 100

解答：

在完全二叉树中，对于编号为 i 的节点，左孩子编号为 2i，右孩子编号为 2i+1

1.11

下哪种设备可以实现以太网中的数据包转发 ==（C）==

1. 适配器
2. 集线器
3. 以太网交换机
4. 转发器

解答：

1. 适配器用于连接设备到网络，不具备数据包的转发功能
2. 集线器工作在物理层，只会将收到的数据广播给所有端口
3. 以太网交换机工作在数据链路层，能够根据 MAC 地址智能地将数据包转发到正确的端口
4. 转发器主要用于增强信号或延长网络传输距离，不具备数据包的转发功能

1.12

将关键字序列 {10, 14, 18, 32, 60, 25, 70,