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

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

岗位：嵌入式软件工程师（25届校招）(J12042)

题型：4 道单选题，2 道填空题， 3 道简答题，3 道编程题

1、单选题

1.1

已知 5 个元素的出栈序列是 1,2,3,4,5,6 则对应的入栈顺序可能是 ==（B）==

1. 6，2，4，3，1，5
2. 1，3，2，5，4，6
3. 3，6，1，4，5，2
4. 2，3，1，5，4，6

解答：

只有选项 B 正确
1 -> push -> pop -> 1
3 -> push
2 -> push -> pop -> 2
-> pop -> 3
5 -> push
4 -> push -> pop -> 4
-> pop -> 5
6 -> push -> pop -> 6

1.2

下面哪种同步机制不能在中断上下文使用 ==（D）==

1. 自旋锁
2. 原子操作
3. 内存屏障信号量
4. 信号量

解答：

中断上下文是执行中断处理程序的特殊环境，禁止发生睡眠操作，而信号量/互斥量可能会导致睡眠，因此不能在中断上下文中使用，选择选项 D

1.3

求整数 n（n>=0）阶乘的算法如下，其时间复杂度是 ==（D）==

int fact(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * fact(n - 1);
}

1. O(logn)
2. O(nlogn)
3. O(n^2)
4. O(n)

解答：

该函数用于计算 n!，需要循环 n 次，每次循环执行一次乘法操作，且乘法运算的复杂度是常数时间 O(1)，时间复杂度为 O(n)，选择选项 D

1.4

有如下一段代码，假设 x 初始为 8191，则执行完 count 值为 ==（C）==

int count = 0;
while (x) {
    count++;
    x = x & (x - 1);
}

1. 8191
2. 26
3. 13
4. 1

解答：

这段代码的作用是计算一个整数的二进制表示中有多少个 1，而十进制 8191 用二进制表示为 0001 1111 1111 1111，一共有 13 个 1，因此选择选项 C

2、填空题

2.1

进程间的通信方式有 1 , 2 , 3 , 4 , 5 等

解答：

1. 管道
2. 共享内存
3. 信号量
4. 消息队列
5. 套接字

2.2

下面代码的时间复杂度是多少？

int a[n][n];
sum = 0;
for (i = n / 2; i < n; i++) {
    for (j = i; j < n; j++) {
        sum += a[i][j];
    }
}

解答：

==O（n^2）==

关键是计算出循环次数，当外层 i=n/2 时， 内层循环 n/2 次；当外层 i=n-1 时，内存循环 1 次，因此总共循环次数为：

忽略低阶项和常数系数，时间复杂度为 O(n^2)

3、问答题

3.1

自旋锁和互斥锁的区别及各自的应用场景？

解答（抛砖引玉）：

1. 自旋锁和互斥锁都是常见的同步机制，主要是用来对共享资源的保护
2. 自旋锁在获取锁失败时不会使线程进入休眠状态，而是持续不断的循环（占用CPU）检查锁是否可用
3. 互斥锁在获取锁失败时会使线程进入休眠状态，​等待锁可用是唤醒线程，避免忙等待占用CPU时间
4. 自旋锁一般用在短时间