百面嵌入式专栏（笔试题）小米嵌入式软件工程师笔试题目解析

选择题

1.已经获得除CPU以外的所有所需资源的进程处于（）状态

A 就绪状态

B 阻塞状态

C 运行状态

D 活动状态

A

进程的五状态模型：

运行态：该进程正在执行。

就绪态：进程已经做好了准备，只要有机会就开始执行。

阻塞态（等待态）：进程在某些事情发生前不能执行，等待阻塞进程的事件完成。

新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中，通常是进程控制块已经创建但是还没有加载到内存中的进程。

退出态：操作系统从可执行进程组中释放出的进程，或由于自身或某种原因停止运行。

2.某二叉树的中序遍历序列为32145，后序遍历序列为32145，则前序遍历序列为

A 54123

B 32154

C 32541

D 54321

A

二叉树的中序遍历序列为 32145 ，后序遍历序列为32145 ，可知该树只有左子树结点，没有右子树结点， 5 为根结点。

中序遍历序列与后序遍历序列相同，说明该树只有左子树没有右子树，因此该树有 5 层，从顶向下依次为54123 。

具体分析过程也可以参考下北京联发科嵌入式软件工程师笔试题目解析

3.若已知一个栈的入栈顺序是1,2,3...,n,其输出序列为P1,P2,P3,....Pn,若P1是n,则Pi=（）？

A i

B n-i+1

C 不确定

D n-i

B

栈的排列遵循先进后（即后进先出）出的原则

因为P1是n，是出栈的第一个数字，说明在n之前进栈的数字都没有出栈。所以这个顺序是确定的。

还可以知道，最后出栈的一定是数字1，也就是Pn。代入这个式子，是正确的。

4（多选题）.下面协议中属于应用层协议的是（）

A ICMP、ARP

B FTP、 TELNET

C HTTP、SNMP

D SMTP、POP3

BD

1、物理层：以太网 、 调制解调器 、 电力线通信(PLC) 、SONET/SDH 、 G.709 、 光导纤维 、 同轴电缆、 双绞线等。

2、数据链路层：Wi-Fi(IEEE 802.11)、WiMAX(IEEE 802.16) 、ATM 、 DTM 、 令牌环 、以太网、FDDI、 帧中继、 GPRS 、 EVDO、HSPA 、HDLC 、 PPP 、 L2TP 、PPTP 、ISDN·STP、CSMA/CD等。

3、网络层协议：IP IPv4 、IPv6、 ICMP、ICMPv6·IGMP、IS-IS 、IPsec 、ARP 、RARP 、RIP等。

4、传输层协议：TCP、 UDP、TLS 、 DCCP、 SCTP 、 RSVP 、OSPF 等。

5、应用层协议：DHCP 、DNS、 FTP 、Gopher 、 HTTP、 IMAP4 、 IRC、 NNTP 、 XMPP、POP3 、SIP、 SMTP、SNMP 、SSH、TELNET 、 RPC 、RTCP 、RTP 、RTSP、SDP 、 SOAP、GTP、STUN 、NTP、SSDP 、 BGP 等。

5.下列程序段的时间复杂度是（）

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

A O(log2n)

B O(nlog2n)

C O(n)

D O(n*n)

C

当n<=1时执行return 1这一个语句，每次返回上一层都执行n*fact(n-1)这一个语句，共执行n-1次。因此共执行基本语句n次，时间复杂度为O(n)

6.下列排序算法中最好情况和最坏情况的时间复杂度相同的是？（）

A 堆排序

B 快速排序

C 冒泡排序

D 归并排序

A C D

堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)

快速排序最好和最坏情况下的时间复杂度分别为O(nlogn)和O(n^2 )

冒泡排序排序在最好和最坏情况下的时间复杂度均为O(nlogn)

归并排序在最好和最坏情况下的时间复杂度均为O(nlogn)

7.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是？（）

A n

B 2n

C n-1

D 2n-1

A

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。在归并排序中，核心步骤是将相邻的两个有序序列归并为一个有序序列。

题目中告诉我们，有两个各有n个元素的有序序列，要将这两个序列归并成一个有序序列，其方法是依次从小到大取每个序列中的元素进行比较，将较小的放进一个新的序列中，直到取完一个有序序列中的所有元素。再把另一个序列中剩下的元素放进新序列的后面即可。

最好的情况是一个有序序列中的最小元素大于另一个有序序列中的所有元素，这样只需要比较n次。

8.将递归算法转换为非递归算法通常需要使用（）

A 栈

B 队列

C 队列

D 广义表

D

9.在MySql中， productname regexp '[1-3]xiaomi'的含义是（）

A productname 匹配“xiaomi重复1次或5次”的字符串

B productname 匹配“xiaomi字符串前一个字符为1或3“的字符串

C productname 匹配“xiaomi重复1到3次”的字符串

D productname 匹配“xiaomi字符串前一个字符为1到3“的字符串

D

10.同个进程的不同线程以下不能被共享的是？（）

A 全局变量

B 堆

C 文件句柄

D 栈

B

线程共享的进程环境包括：

进程代码段、进程的公有资源（如全局变量，利用这些共享的数据，线程很容易的实现相互之间的通信）、进程打开的文件描述符、消息队列、信号的处理器、进程的当前目录、进程用户ID、进程组ID

线程独占资源：

线程ID、寄存器组的值、用户栈、内核栈（在一个进程的线程共享堆区（heap））、错误返回码、线程的信号屏蔽码、线程的优先级

专项选择题

1.下列Java函数的执行结果是什么（）

static boolean foo(charc)
{
	System.out.print(c);
    return true;
}
public static void main(string[] args){
    int i = 0;
    for(foo('B');foo('A')&&(i<2);foo('C'))
    {
		i++;
        foo('D');
    }
}

A BADCBDCB

B BACDBACD

C BADCADCA

D 运行时抛出异常

C

1.其实foo('B');就是初始化条件，只会执行一次，所以第一个打印的肯定是B。

2.因为i=0;循环条件是i<2 （由此可知，循环i等于2的时候就会停止循环)，所以0<2满足条件，接着会输出A。然后执行i++;i就变成1了，在输出D ，在最后输出C。一次循环后的结果是：BADC。

3.第二次循环的开始是foo('B');是初始条件，所以不会执行。直接从foo('A')开始，输出A，然后i为1，且小于2，此时循环体内再次执行i++；i的值为2了，再次输出D，最后输出C。第二次循环输出：ADC。

4.然后循环再次执行for(foo('B');foo('A')&&(i<2);foo('C'))，直接输出A。i的值在第二轮循环后的值变成了2，2<2不成立，终止循环，输出A。

故输出结果是：BADCADCA。

2.下列有关软链接表述正确的是？（）

A 不可以对不存在