研发实习题目

Behindrain 2017-11-03

展开全文

下面哪一个不是动态链接库的优点？

装载速度快

优点：共享、开发模式好、减少页面交换

1 静态链接库的优点

(1) 代码装载速度快，执行速度略比动态链接库快；

(2) 只需保证在开发者的计算机中有正确的.LIB文件，在以二进制形式发布程序时不需考虑在用户的计算机上.LIB文件是否存在及版本问题，可避免DLL地狱等问题。

2 动态链接库的优点

(1) 更加节省内存并减少页面交换；

(2) DLL文件与EXE文件独立，只要输出接口不变（即名称、参数、返回值类型和调用约定不变），更换DLL文件不会对EXE文件造成任何影响，因而极大地提高了可维护性和可扩展性；

(3) 不同编程语言编写的程序只要按照函数调用约定就可以调用同一个DLL函数；

(4) 适用于大规模的软件开发，使开发过程独立、耦合度小，便于不同开发者和开发组织之间进行开发和测试。

3 不足之处

(1) 使用静态链接生成的可执行文件体积较大，包含相同的公共代码，造成浪费；

(2) 使用动态链接库的应用程序不是自完备的，它依赖的DLL模块也要存在，如果使用载入时动态链接，程序启动时发现DLL不存在，系统将终止程序并给出错误信息。而使用运行时动态链接，系统不会终止，但由于DLL中的导出函数不可用，程序会加载失败；速度比静态链接慢。当某个模块更新后，如果新模块与旧的模块不兼容，那么那些需要该模块才能运行的软件，统统撕掉。这在早期Windows中很常见。

n个数值选出最大m个数（3<m<n）的最小算法复杂度是

剑指offer第30题

1.最简单的方法：将n个数排序，排序后的前k个数就是最大的k个数，这种算法的复杂度是O（nlogn）

2.O（n）的方法：利用快排的patition思想，基于数组的第k个数来调整，将比第k个数小的都位于数组的左边，比第k个数大的都调整到数组的右边，这样调整后，位于数组右边的k个数最大的k个数(这k个数不一定是排好序的）

3.O(nlogk）的方法：先创建一个大小为k的最小堆，接下来我们每次从输入的n个整数中读入一个数，如果这个数比最小堆的堆顶元素还要大，那么替换这个最小堆的堆顶并调整。

由权值分别为1、12、13、4、8的叶子节点生成一颗哈夫曼树，它的带权路径长度为()

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

分两种情况讨论：

（1）若这个四位数的重复数字为1，那么首先从三个空位中选出一个给1，第二步从剩下9个可选数字中选出2个有序的排列到剩下的两个空位中去，那么有C(1，3)*A(2，9)=3*(9!/(9-2)!)=3*9*8=216种可能；

（2）若这个四位数的重复数字不为1，那么首先从9个可选数字中选出一个作为重复数字(C(1,9))，并放到三个空位中的两个（这两个数字相同，故只涉及组合）(C(2, 3))，然后从剩下8个数字中选出一个（它的位置在重复数字确定后就自然固定了，不可选）即可，故有C(1,9)*C(2, 3)*C(1, 8)=216种可能。

总共：216+216=432

工程师M发明了一种游戏：M将一个小球随机放入完全相同的三个盒子中的某一个，玩家选中装有球的盒子即获胜；开始时M会让玩家选择一个盒子（选择任何一个获胜概率均为1/3）;玩家做出选择后，M会打开没有被选择的两个盒子中的一个空盒，此时M会询问玩家是否更改选择（可以坚持第一次选择，也可以选择另一个没有打开的盒子），下列叙述正确的有（

这道题目容易弄错的地方就在于，把第二次选择当作整个游戏。如果跳过前面的排除，直接跳到第二次选择：你现有的和剩下的一个盒子中只有一个装了球。当然换或者不换获胜的概率都是 1/2，但是综合前面的情况来看，第二次选择获胜有两种情况：

1. 不修改选择并获胜，表示第一次已经选对。概率为：1/3 * 1/2 = 1/6

2. 修改选择并获胜，表示第一次选错。概率为：2/3 * 1/2 = 2/6

综上可知，第二次选择中修改选择后获胜的概率较大。

注意，这里的 2/6 并不是整个游戏中改选的获胜概率！第二次选择，胜负的概率各为 1/2，这里的 2/6 只是第二次选择中通过改选达到获胜的概率。

那整个游戏中改选获胜的概率是多少呢？3 个盒子可能不容易看清，我们把问题改成：有 10 个盒子，选择完成之后移除 8 个空盒子。那么第一次选择的盒子有球的概率是 1/10，剩下 9 个盒子有球的概率是 9/10；移除 8 个空盒子相当于告诉你这 8 个盒子有球的概率为 0，但是 9个盒子有球的总概率为 9/10 是没有变的，这就表明剩下的那个盒子有球的概率是 9/10，如果改选这个盒子获胜的概率就是 9/10。同理，对于 3 个盒子，改选获胜的概率是 2/3，A 错。）。

以下哪种方式，在读取磁盘上多个顺序数据块时的效率最高？

答案选C，通道方式。

（1）程序直接访问方式跟循环检测IO方式，应该是一个意思吧，是最古老的方式。CPU和IO串行，每读一个字节（或字），CPU都需要不断检测状态寄存器的busy标志，当busy=1时，表示IO还没完成；当busy=0时，表示IO完成。此时读取一个字的过程才结束，接着读取下一个字。

（2）中断控制方式：循环检测先进些，IO设备和CPU可以并行工作，只有在开始IO和结束IO时，才需要CPU。但每次只能读取一个字。

（3）DMA方式：Direct Memory Access，直接存储器访问，比中断先进的地方是每次可以读取一个块，而不是一个字。

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

下列不是进程间的通信方式的是（）

回调

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

已知IBM的PowerPC是big-endian字节序列而Intel的X86是little-endian字节序，如果在地址啊存储的整形值时0x04030201，那么地址为a+3的字节内存储的值在PowerPC和Intel X86结构下的值分别是？

大端从大地址开始存储，小端相反，两者都是从数据低位开始存起；
假设从上至下地址递增，则
PowerPC（大）：                    Intel X86（小）：
04                                            01                    低
03                                            02                      |
02                                            03                      |
01                                            04                     高
a+3指向最大的地址，所以分别为1 4

在TCP/IP建立连接过程中，客户端或服务器的状态转移说法错误的是？

错：经历TIME_WAIT状态。

对：

经历SYN_RECV状态
经历SYN_SEND状态
经历ESTABLISHED状态
服务器在收到syn包时将加入半连接队列
服务器收到客户端的ack包后将从半连接队列删除

Tcp/Ip有3次握手：第一次握手：客户端向服务器端发送SYN包（syn＝j），进入SYN_SEND状态，等待服务器确认。第二次握手：服务器收到SYN包，确认SYN，此时syn＝j+1，同时发送一个SYN包（syn＝k）即SYN＋ACK包，此时服务器进入SYN_RECV状态；第三次握手：客户端收到SYN＋ACK包，向服务器发送ACK确认包，此时客户端和服务器端均进入ESTABLISHED状态。

其中有一个半连接状态：服务器维护一个半连接队列，该队列卫每个客户端SYN包开设一个条目，标明服务器已经接到SYN包，并向客户端发出确认，这些条目表示的连接处于SYN_RECV状态，得到客户端的确认后进入ESTABLISHED状态。

10.

sizeof(bu)的值是()

设有四个元素A、B、C、D顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是

进栈出栈顺序问题解题思路：

栈之根本——先进后出（first in，lastout），自己在做题的时候可以画入栈和出栈图，这样就很明显得知出栈顺序了。做多了题目之后，你会发现不用画图了，直接在脑子里可以想象这个过程，则答案很容易就出来了，反正我是一个一个看着答案排除的。自己刷题总结下来的一些技巧。

11.

#pragma pack(2)

class BU

{

int number; // 4

union UBffer

{

char buffer[13]; // 13

int number; // 4

}ubuf; // union的大小取决于它所有的成员中，占用空间最大的一个成员的大小，并且需要内存对齐，这里因为#pragma pack(2)，所以union的大小为14，如果不写#pragma pack(2)，那么union大小为16【因为与sizeof（int）=4对齐】

void foo(){} //0

typedef char*(*f)(void*); //0

enum{hdd,ssd,blueray}disk; // 4

}bu;

因此sizeof（union） = 4+14 +0 +0 +4 = 22

12.

同一个进程中的线程不共享的部分是()栈空间

信号、堆、文件描述符、进程组id、代码段

线程共享的环境包括：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

进程拥有这许多共性的同时，还拥有自己的个性。有了这些个性，线程才能实现并发性。这些个性包括：

1.线程ID
每个线程都有自己的线程ID，这个ID在本进程中是唯一的。进程用此来标

识线程。

2.寄存器组的值
由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线

程切换到另一个线程上时，必须将原有的线程的寄存器集合的状态保存，以便

将来该线程在被重新切换到时能得以恢复。

    3.线程的堆栈
       堆栈是保证线程独立运行所必须的。
       线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程

必须拥有自己的函数堆栈，使得函数调用可以正常执行，不受其他线程的影

响。

4.错误返回码
由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调用

后设置了errno值，而在该线程还没有处理这个错误，另外一个线程就在此时

被调度器投入运行，这样错误值就有可能被修改。
所以，不同的线程应该拥有自己的错误返回码变量。

5.线程的信号屏蔽码
由于每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都共享同样的信号处理器。

6.线程的优先级
由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数就是线程的优先级。

涉及多线程程序涉及的时候经常会出现一些令人难以思议的事情，用堆和栈分配一个变量可能在以后的执行中产生意想不到的结果，而这个结果的表现就是内存的非法被访问，导致内存的内容被更改。

理解这个现象的两个基本概念是：在一个进程的线程共享堆区，而进程中的线程各自维持自己堆栈。

在 windows 等平台上，不同线程缺省使用同一个堆，所以用 C 的 malloc （或者 windows 的 GlobalAlloc）分配内存的时候是使用了同步保护的。如果没有同步保护，在两个线程同时执行内存操作的时候会产生竞争条件，可能导致堆内内存管理混乱。比如两个线程分配了统一块内存地址，空闲链表指针错误等。

Symbian 的线程一般使用独立的堆空间。这样每个线程可以直接在自己的堆里分配和释放，可以减少同步所引入的开销。当线程退出的时候，系统直接回收线程的堆空间，线程内没有释放的内存空间也不会造成进程内的内存泄漏。

但是两个线程使用共用堆的时候，就必须用 critical section 或者 mutex 进行同步保护。否则程序崩溃时早晚的事。如果你的线程需要在共用堆上无规则的分配和释放任何数量和类型的对象，可以定制一个自己的 allcator，在 allocator 内部使用同步保护。线程直接使用这个 allocator 分配内存就可以了。这相当于实现自己的 malloc，free。但是更建议你重新审查一下自己的系统，因为这种情况大多数是不必要的。经过良好的设计，线程的本地堆应该能够满足大多数对象的需求。如果有某一类对象需要在共享堆上创建和共享，这种需求是比较合理的，可以在这个类的 new 和 delete 上实现共享保护。

13.

下面关于系统调用的描述中,错误的是()系统调用中被调用的过程运行在"用户态"中

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

调用程序是运行在用户态，而被调用的程序是运行在系统态

14.

在动态分区分配方案中,系统回收主存,合并空闲空间时需修改空闲区表,以下哪种情况空闲区会减1?

有上邻空闲区,也有下邻空闲区

在分区分配方案中，回收一个分区时有几种不同的邻接情况，在各种情况下应如何处理？答：有四种：上邻，下邻，上下相邻，上下不相邻。

（1）回收分区的上邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表。

（2）回收分区的下邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表。

（3）回收分区的上、下邻分区都是空闲的（空闲区个数为2），需要将三个空闲区合并成一个更大的空闲区（空闲区个数为1 ），然后修改空闲区表、

（4）回收分区的上、下邻分区都不是空闲的，则直接将空闲区记录在空闲区表中。

15.

下面关于虚拟局域网VLAN的叙述错误的是()不同VLAN内的用户可以相互之间直接通信

VLAN是由局域网网段构成的与物理位置无关的逻辑组利用以太网交换机可以很方便地实现VLAN 每一个VLAN的工作站可处在不同的局域网中 vLAN可以强化网络安全和网络管理 VLAN能灵活控制广播活动

VLAN（Virtual Local Area Network）的中文名为"虚拟局域网"。

虚拟局域网（VLAN）是一组逻辑上的设备和用户，这些设备和用户并不受物理位置的限制，可以根据功能、部门及应用等因素将它们组织起来，相互之间的通信就好像它们在同一个网段中一样，由此得名虚拟局域网。VLAN是一种比较新的技术，工作在OSI参考模型的第2层和第3层，一个VLAN就是一个广播域，VLAN之间的通信是通过第3层的路由器来完成的。与传统的局域网技术相比较，VLAN技术更加灵活，它具有以下优点：网络设备的移动、添加和修改的管理开销减少；可以控制广播活动；可提高网络的安全性。

在计算机网络中，一个二层网络可以被划分为多个不同的广播域，一个广播域对应了一个特定的用户组，默认情况下这些不同的广播域是相互隔离的。不同的广播域之间想要通信，需要通过一个或多个路由器。这样的一个广播域就称为VLAN。

16.