笔试题总结 (1)

阿里的部分笔试题总结。

原文链接：https://blog.csdn.net/weixin_43730955/article/details/89163131

1. 下面哪一个不是动态链接库的优点？（F）
   A.共享
   B.装载速度快
   C.开发模式好
   D.减少页面交换

   知识补充
   1）动态链接库：
   a.动态链接提供了一种方法，使进程可以调用不属于其可执行代码的函数。
   b.使用动态链接库可以更为容易地将更新应用于各个模块，而不会影响该程序的其他部分。
   c.动态链接库文件，是一种不可执行的二进制程序文件，它允许程序共享执行特殊任务所必需的代码和其他资源。
   https://baike.baidu.com/item/动态链接库/100352?fr=aladdin#4

   2)动态链接库的优缺点
   a. 更加节省内存并减少页面交换；
   b. DLL文件与EXE文件独立，只要输出接口不变（即名称、参数、返回值类型和调用约定不变），更换DLL文件不会对EXE文件造成任何影响，因而极大地提高了可维护性和可扩展性；
   c.不同编程语言编写的程序只要按照函数调用约定就可以调用同一个DLL函数；
   d.适用于大规模的软件开发，使开发过程独立、耦合度小，便于不同开发者和开发组织之间进行开发和测试。
   e. 使用动态链接库的应用程序不是自完备的，它依赖的DLL模块也要存在，如果使用载入时动态链接，程序启动时发现DLL不存在，系统将终止程序并给出错误信息。而使用运行时动态链接，系统不会终止，但由于DLL中的导出函数不可用，程序会加载失败；速度比静态链接慢。当某个模块更新后，如果新模块与旧的模块不兼容，那么那些需要该模块才能运行的软件，统统撕掉。这在早期Windows中很常见。

   3）静态链接库：
   所谓静态链接库，说白了就是在你把写好的代码编译的时候，就把你引用的库一起给编进去了，从此后你编出来的执行程序跟外面都不再有任何关系，即使这个库更新了，你也搭不上边儿，其次，如果系统中许多类似的程序都需要用到这个库，那么各自在编译的时候都需要把这个库给编进去，浪费存储空间（加载到内存里应该也是浪费内存空间的）。linux系统中静态库的名字一般叫xxx.a, 所以如果你看到一个以 .a结束的文件那么它多半就是一个静态链接库文件。

   4)静态链接库的优缺点：
   a.代码装载速度快，执行速度略比动态链接库快；
   b.只需保证在开发者的计算机中有正确的.LIB文件，在以二进制形式发布程序时不需考虑在用户的计算机上.LIB文件是否存在及版本问题，可避免DLL地狱等问题。
   c.使用静态链接生成的可执行文件体积较大，包含相同的公共代码，造成浪费；

2. n个数值选出最大m个数（3<m<n）的最小算法复杂度是（A）
   A.O(n)
   B.O(nlogn)
   C.O(logn)
   D.O(mlogn)
   E.O(nlogm)
   F.O(mn)

   知识补充:
   1)最简单的方法：将n个数排序，排序后的前k个数就是最大的k个数，这种算法的复杂度是O（nlogn）。
   2)O（n）的方法：利用快排的patition思想，基于数组的第k个数来调整，将比第k个数小的都位于数组的左边，比第k个数大的都调整到数组的右边。
   3)O(nlogm）的方法：先创建一个大小为m的最小堆，接下来我们每次从输入的n个整数中读入一个数，如果这个数比最小堆的堆顶元素还要大，那么替换这个最小堆的堆顶并调整。
   4）部分快排 时间复杂度 O(N) ，存储复杂度 O(N)；堆排序 时间复杂度 O(NlogM) 空间复杂度 O(M) 。如果数组能存下的话，O(N) 是最小时间复杂度。但是你可能面临从（文件）流中读取数据，O(N) 的空间复杂度超过内存限制的情况，这种情况下就该用优先队列了。

3. 由权值分别为1、12、13、4、8的叶子节点生成一颗哈夫曼树，它的带权路径长度为(F)
   A.12
   B.68
   C.43
   D.6
   E.25
   F.81

   • 哈夫曼树的权重为每个叶子节点到根节点的距离与叶节点的加权和。
   • 哈夫曼树一定是满二叉树
   • 哈夫曼树中权重小的叶节点一定比权重大的节点距离更远
   • 存在这样一株哈夫曼树，使得权重最小的两个叶节点的父节点相同。
   • 哈夫曼的构建：从数据中选择最小的两个数作为叶节点，然后将子树放回去，继续找最小的点，直至所有点都加入树中。

4. 阿里巴巴国际站的股票代码是1688，这个数字具有这样的特性，首先是个首位为1的4位数，其次恰巧有且仅有1个数字出现了两次。类似的数字还有：1861,1668等。这样的数字一共有(F)个。
   A.144
   B.180
   C.216
   D.270
   E.288
   F.432

   求解方法：首先第一个数字是固定为1的，要求数字中有且只有一个数字出现两次，分为两种情况，即还有一次1出现，和1不在出现。

   当1出现两次时，表示后面三位数有一个为1，其他两个不为1的数不同，那么先随机选一个数a，其有九种可能，再选一个数b，其有8种可能；于是后面三个数字 1,a,b, 可以随机排列 有C(3,2)中可能，总共为 9x8x3 = 216种。

   当1只出现在第一位时，先选择重复数字a，有9种可能，再选择不同数字b，有8种可能，(a,a,b)所有可能组合有3中，所以这种情况有 3x9x8=216种

   共有432种

5. 工程师M发明了一种游戏：M将一个小球随机放入完全相同的三个盒子中的某一个，玩家选中装有球的盒子即获胜；开始时M会让玩家选择一个盒子（选择任何一个获胜概率均为1/3）;玩家做出选择后，M会打开没有被选择的两个盒子中的一个空盒，此时M会询问玩家是否更改选择（可以坚持第一次选择，也可以选择另一个没有打开的盒子），下列叙述正确的有（E）。
   A.改选后，玩家获胜的概率还是1/3
   B.若不改选，玩家的获胜概率是1/2
   C.无论怎么选择，获胜的概率都是1/2
   D.坚持原来的选择获胜概率更高
   E.选择另一个没有被打开的盒子获胜概率更高
   F.获胜概率取决于随机因素（如小球的实际位置）
   解析： 首先玩家获胜概率是1/3， 去掉一个空盒时，玩家此时的获胜概率为1/2. 那么改选之后获胜的概率如何计算呢？

   假设第一次选择事件表示为A， 该选事件表示为B，那么A=1表示有球，于是

   P(B=1|A) = P(B=1|A=1)P(A=1) + P(B=1|A=0)P(A=0) = 2/3

   P(B=0|A) = P(B=0|A=1)P(A=1) + P(B=0|A=0)P(A=0) = 1/3

   所以改选之后获胜概率更大。

6. 以下哪种方式，在读取磁盘上多个顺序数据块时的效率最高？（C）
   A.中断控制方式
   B.DMA方式
   C.通道方式
   D.程序直接访问方式
   E.循环检查I/O方式
   F.以上访问方式都一样
   知识补充:主要原因在于通道方式可以并行处理。

   中断控制是指I/O完成任务后触发中断读取数据。

   DMA指直接存储器访问，这个比中断更有优势，因为开辟了一个空间用于缓存I/O的结果，一定程度I/O和程序并行。

   通道方式：比DMA先进的地方是，每次可以处理多个块，而不只是一个块。

   直接访问，即程序查询I/0的状态，可能中断

   循环检查则是不断循环的查询I/O是否准备好。

1. 下列不是进程间的通信方式的是（B）
   A.管道
   B.回调
   C.共享内存
   D.消息队列
   E.socket
   F.信号量
   知识补充:
   1)管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
   2)信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
   3) 消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
   4) 共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
   5) 套接字( socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

2. 已知IBM的PowerPC是big-endian字节序列而Intel的X86是little-endian字节序，如果在地址啊存储的整形值时0x04030201，那么地址为a+3的字节内存储的值在PowerPC和Intel X86结构下的值分别是？（A）
   A.1 4
   B.1 3
   C.4 1
   D.3 1
   E.4 4
   F.1 1
   知识补充:
   大端从大地址结束，小端相反，两者都是从数据低位开始存起；
   假设从上至下地址递增，则
   PowerPC（大）： Intel X86（小）：
   04 01 低
   03 02 |
   02 03 |
   01 04 高
   a+3指向最大的地址，所以分别为1 4

3. 在TCP/IP建立连接过程中，客户端或服务器的状态转移说法错误的是(D)？
   A. 经历SYN_RECV状态
   B.经历SYN_SEND状态
   C.经历ESTABLISHED状态
   D.经历TIME_WAIT状态
   E.服务器在收到syn包时将加入半连接队列
   F.服务器收到客户端的ack包后将从半连接队列删除
   知识补充:
   1)Tcp/Ip有3次握手：第一次握手：客户端向服务器端发送SYN包（syn＝j），进入SYN_SEND状态，等待服务器确认。第二次握手：服务器收到SYN包，确认SYN，此时syn＝j+1，同时发送一个SYN包（syn＝k）即SYN＋ACK包，此时服务器进入SYN_RECV状态；第三次握手：客户端收到SYN＋ACK包，向服务器发送ACK确认包，此时客户端和服务器端均进入ESTABLISHED状态。
   2)其中有一个半连接状态：服务器维护一个半连接队列，该队列卫每个客户端SYN包开设一个条目，标明服务器已经接到SYN包，并向客户端发出确认，这些条目表示的连接处于SYN_RECV状态，得到客户端的确认后进入ESTABLISHED状态。
   3)TIME_WAIT是断开连接时的状态
   4)TCP连接的建立与终止 :http://www.cnblogs.com/newwy/p/3234536.html

4. 已知一棵二叉树的先序和中序遍历序列如下：先序：A、B、C、D、E、F、G、H、I，J中序：C、B、A、E、F、D、I、H、J、G其后序遍历序列为：(E)
   A.C、B、D、E、A、G、I、H、J、F
   B.C、B、D、A、E、G、I、H、J、F
   C.C、E、D、B、I、J、H、G、F、A
   D.C、E、D、B、I、H、J、G、F、A
   E.C、B、F、E、I、J、H、G、D、A
   F.C、B、F、E、I、H、J、G、D、A
   知识补充:

   先序： 根->左->右

   中序： 左 -> 根->右

   后序： 左-> 右->根

   1)先序，中序，后序，已知中序和先序或者中序和后序两种遍历结果，就可以逆向推导出整颗树
   a.由先序，知A是根
   b.由中序，知B、C为A左子树，D、E、F、G、H、I、J为A右子树
   c.由先序，知B为A左子树根
   d.由中序，知C为B左子树
   e.由先序，知D为A右子树根
   f.由中序，知E、F为D左子树，G、H、I、J位D右子树
   g.由先序，知E为D左子树根
   h.由中序，知F为E左子树
   i.由先序，知G为D右子树根
   j.由中序，知H、I、J为G左子树
   k.由先序，知H为G左子树根
   l.由中序，知I为H左子树，J为H右子树
   m.树推导构造完毕

5. 同一个进程中的线程不共享的部分是(F)

   A.信号
   B.堆
   C.文件描述符
   D.进程组id
   E.代码段
   F.栈空间

   知识补充:

   1)线程共享的环境包括：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。
   2)进程拥有这许多共性的同时，还拥有自己的个性。有了这些个性，线程才能实现并发性。这些个性包括：
   a.线程ID: 每个线程都有自己的线程ID，这个ID在本进程中是唯一的。进程用此来标
   识线程。
   b.寄存器组的值: 由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线
   程切换到另一个线程上 时，必须将原有的线程的寄存器集合的状态保存，以便
   将来该线程在被重新切换到时能得以恢复。
   c.线程的堆栈: 堆栈是保证线程独立运行所必须的。线程函数可以调用函数，而被调用函数中 又是可以层层嵌套的，所以线程必须拥有自己的函数堆栈， 使得函数调用可以正常执行，不 受其他线程的影响。
   d.错误返回码: 由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调用
   后设置了errno值，而在该 线程还没有处理这个错误，另外一个线程就在此时
   被调度器投入运行，这样错误值就有可能被修改。所以，不同的线程应该拥有自己的错误返 回码变量。
   e.线程的信号屏蔽码:由于每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都共享同样的信号处理器。
   f.线程的优先级:由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数就是线程的优先级。

1. 下面关于系统调用的描述中,错误的是(B)

   A.系统调用把应用程序的请求传输给系统内核执行
   B.系统调用中被调用的过程运行在”用户态”中
   C.利用系统调用能够得到操作系统提供的多种服务
   D.是操作系统提供给编程人员的接口
   E.系统调用给用户屏蔽了设备访问的细节
   F.系统调用保护了一些只能在内核模式执行的操作指令

   知识补充: 调用程序是运行在用户态，而被调用的程序是运行在系统态, 被调用的过程运行在内核。

2. 在动态分区分配方案中,系统回收主存,合并空闲空间时需修改空闲区表,以下哪种情况空闲区会减1?（F）
   A.只要回收主存,空闲区数就会减一
   B.空闲区数和主存回收无关
   C.无上邻空闲区,也无下邻空闲区
   D.有上邻空闲区,但无下邻空闲区
   E.有下邻空闲区,但无上邻空闲区
   F.有上邻空闲区,也有下邻空闲区
   知识补充: 1) 在分区分配方案中，回收一个分区时有几种不同的邻接情况，在各种情况下应如何处理？ 答：有四种：上邻，下邻，上下相邻，上下不相邻。
   a.回收分区的上邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表。
   b.回收分区的下邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表。
   c.回收分区的上、下邻分区都是空闲的（空闲区个数为2），需要将三个空闲区合并成一个更大的空闲区（空闲区个数为1 ），然后修改空闲区表、
   d.回收分区的上、下邻分区都不是空闲的，则直接将空闲区记录在空闲区表中。

3. 下面关于虚拟局域网VLAN的叙述错误的是(D)
   A.VLAN是由局域网网段构成的与物理位置无关的逻辑组
   B.利用以太网交换机可以很方便地实现VLAN
   C.每一个VLAN的工作站可处在不同的局域网中
   D.不同VLAN内的用户可以相互之间直接通信
   E.VLAN可以强化网络安全和网络管理
   F.VLAN能灵活控制广播活动
   VLAN（Virtual Local Area Network）的中文名为”虚拟局域网”。
   知识补充:
   1)虚拟局域网（VLAN）是一组逻辑上的设备和用户，这些设备和用户并不受物理位置的限制，可以根据功能、部门及应用等因素将它们组织起来，相互之间的通信就好像它们在同一个网段中一样，由此得名虚拟局域网。VLAN是一种比较新的技术，工作在OSI参考模型的第2层和第3层，一个VLAN就是一个广播域，VLAN之间的通信是通过第3层的路由器来完成的。与传统的局域网技术相比较，VLAN技术更加灵活，它具有以下优点： 网络设备的移动、添加和修改的管理开销减少；可以控制广播活动；可提高网络的安全性。
   2)在计算机网络中，一个二层网络可以被划分为多个不同的广播域，一个广播域对应了一个特定的用户组，默认情况下这些不同的广播域是相互隔离的。不同的广播域之间想要通信，需要通过一个或多个路由器。这样的一个广播域就称为VLAN。

4. 刚毕业的小王上班有两路公交车都可以从家到公司.如果只等A车,平均需要5分钟才等到;如果只等B车,平均需要7分钟才能等到.假定两辆车运行时间独立,那么小王平均需要等多长时间才能等到A车或B车?（C）
   A.2分钟
   B.2分35秒
   C.2分55秒
   D.3分钟
   E.5分钟
   F.6分钟

   知识补充:
   35分钟内一共来了12辆车
   平均每 35/12 min 来一辆
   35/12min = 2min55s

5. 一个黑色袋子中装有5个红球，5个蓝球，5个黄球，从中抽取三次，每次抽一个球，取完不放回，则每种颜色球各得一个的概率是（F）
   A.1/5
   B.1/4
   C.1/3
   D.12/91
   E.20/91
   F.25/91
   知识补充:
   1)最开始是0个球，第一次不管怎么选都会选一个和以前不同颜色的球，所以第一次选择颜色不同的球概率为1；
   2)第一次选择之后，还剩14个球，其中 被第一次选走的那个颜色只有4个，剩下的两种颜色的球个数不变，都为5，然后选一个与第一次颜色不同的球的概率是：10/14， 这是第二次选择
   3)第二次选择之后，还剩13个球，其中被第一次和第二次选中的球，各有4个，剩下的没选到颜色的球还是5个，这次选中还没选到的这个颜色的球的概率是：5/13
   4)所以选择三个不同颜色总的概率为：1（10/14）（5/13） = 25/91.

6. 下面哪种协议在数据链路层？（F）

   A.ARP
   B.ICMP
   C.FTP
   D.UDP
   E.HTTP
   F.VPN
   知识补充:
   ICMP是网络层，UDP是传输层，FTP和HTTP是应用层 。目前VPN隧道协议主要有4种：点到点隧道协议PPTP、第二层隧道协议L2TP、网络层隧道协议IPSec以及SOCKS v5协议。其中，PPTP和L2TP工作在数据链路层，IPSec工作在网络层，SOCK v5工作在会话层。

7. 一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为（C）
   A.(11 5 7 2 3 17)
   B.(11 5 7 2 13 3)
   C.(17 11 7 2 3 5)
   D.(17 11 7 5 3 2)
   E.(17 7 11 3 5 2)
   F.(17 7 11 3 2 5)
   知识补充:
   如果堆的有序状态因为某个节点变得比它的父节点更大而打破，那么就需要通过交换它和它的父节点来修复堆。