1、程序员面试-6 及答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：28，分数：100.00)1.虚拟地址、逻辑地址、线性地址、物理地址有什么区别 （分数：3.00）_2.Cache 替换算法有哪些 （分数：3.00）_3.库函数与系统调用有什么不同 （分数：3.00）_4.静态链接与动态链接有什么区别 （分数：3.00）_5.静态链接库与动态链接库有什么区别 （分数：3.00）_6.用户态和核心态有什么区别 （分数：3.00）_7.用户栈与内核栈有什么区别 （分数：3.00）_8.如何用递归实现数组求和 （分数：3.00）_9.如何用一个 for 循环打印出一个二维数组
2、 （分数：3.00）_10.在顺序表中插入和删除一个结点平均移动多少个结点 （分数：3.00）_11.如何用递归算法判断一个数组是否是递增 （分数：3.00）_12.如何分别使用递归与非递归实现二分查找算法 （分数：3.00）_13.如何在排序数组中，找出给定数字出现的次数 （分数：4.00）_14.如何计算两个有序整型数组的交集 （分数：4.00）_15.如何找出数组中重复次数最多的数 （分数：4.00）_16.如何在 O(n)的时间复杂度内找出数组中出现次数超过了一半的数 （分数：4.00）_17.如何找出数组中唯一的重复元素 （分数：4.00）_18.如何判断一个数组中的数值是否连续相邻
3、 （分数：4.00）_19.如何找出数组中出现奇数次的元素 （分数：4.00）_20.如何找出数列中符合条件的数对的个数 （分数：4.00）_21.如何寻找出数列中缺失的数 （分数：4.00）_22.如何判定数组是否存在重复元素 （分数：4.00）_23.如何重新排列数组使得数组左边为奇数，右边为偶数 （分数：4.00）_24.如何把一个整型数组中重复的数字去掉 （分数：4.00）_25.如何找出一个数组中第二大的数 （分数：4.00）_26.如何寻找数组中的最小值和最大值 （分数：4.00）_27.如何将数组的后面 m 个数移动为前面 m 个数 （分数：4.00）_28.如何计算出序列的前
4、n 项数据 （分数：4.00）_程序员面试-6 答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：28，分数：100.00)1.虚拟地址、逻辑地址、线性地址、物理地址有什么区别 （分数：3.00）_正确答案：()解析：虚拟地址是指由程序产生的由段选择符和段内偏移地址组成的地址。这两部分组成的地址并没有直接访问物理内存，而是要通过分段地址的变换处理后才会对应到相应的物理内存地址。 逻辑地址指由程序产生的段内偏移地址。有时直接把逻辑地址当成虚拟地址，两者并没有明确的界限。 线性地址是指虚拟地址到物理地址变换之间的中间层，是处理器可寻址的内存空间(称为线性地址空间)中的地址。程
5、序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段基址就生成了一个线性地址。如果启用了分页机制，那么线性地址可以再经过变换产生物理地址。若是没有采用分页机制，那么线性地址就是物理地址。 物理地址是指现在 CPU 外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果。 虚拟地址到物理地址的转化方法是与体系结构相关的，一般有分段与分页两种方式。以 x86 CPU 为例，分段分页都是支持的。内存管理单元负责从虚拟地址到物理地址的转化。逻辑地址是段标识十段内偏移量的形式，MMU 通过查询段表，可以把逻辑地址转化为线性地址。如果 CPU 没有开启分页功能，那么线性地址就是物理地址；如果 C
6、PU 开启了分页功能，MMU 还需要查询页表来将线性地址转化为物理地址：逻辑地址(段表)线性地址(页表)物理地址。 映射是一种多对一的关系，即不同的逻辑地址可以映射到同一个线性地址上；不同的线性地址也可以映射到同一个物理地址上。而且，同一个线性地址在发生换页以后，也可能被重新装载到另外一个物理地址上，所以这种多对一的映射关系也会随时间发生变化。2.Cache 替换算法有哪些 （分数：3.00）_正确答案：()解析：数据可以存放在 CPU 或者内存中。CPU 处理快，但是容量少；内存容量大，但是转交给 CPU 处理的速度慢。为此，需要 Cache(缓存)来做一个折中。最有可能的数据先从内存调入
7、Cache，CPU 再从 Cache读取数据，这样会快许多。然而，Cache 中所存放的数据不是 50%有用的。CPU 从 Cache 中读取到有用数据称为“命中”。 由于主存中的块比 Cache 中的块多，所以当要从主存中调一个块到 Cache 中时，会出现该块所映射到的一组(或一个)Cache 块已全部被占用的情况。此时，需要被迫腾出其中的某一块，以接纳新调入的块，这就是替换。 Cache 替换算法有随机算法、FIFO 算法、LRU 算法、LFU 算法和 OPT 算法。 1)随机算法(RAND)。随机算法就是用随机数发生器产生一个要替换的块号，将该块替换出去，此算法简单、易于实现，而且它不
8、考虑 Cache 块过去、现在及将来的使用情况。但是由于没有利用上层存储器使用的“历史信息”、没有根据访存的局部性原理，故不能提高 Cache 的命中率，命中率较低。 2)先进先出(FIFO)算法。先进先出(First In First Out,FIFO)算法是将最先进入 Cache 的信息块替换出去。FIFO 算法按调入 Cache 的先后决定淘汰的顺序，选择最早调入 Cache 的字块进行替换，它不需要记录各字块的使用情况，比较容易实现，系统开销小，其缺点是可能会把一些需要经常使用的程序块(如循环程序)也作为最早进入 Cache 的块替换掉，而且没有根据访存的局部性原理，故不能提高 Cac
9、he 的命中率。因为最早调入的信息可能以后还要用到，或者经常要用到，如循环程序。此法简单、方便，利用了主存的“历史信息”， 但并不能说最先进入的就不经常使用，其缺点是不能正确反映程序局部性原理，命中率不高，可能出现一种异常现象。例如，Solar16/65 机 Cache 采用组相连方式，每组 4 块，每块都设定一个两位的计数器，当某块被装入或被替换时该块的计数器清为 0，而同组的其他各块的计数器均加1，当需要替换时就选择计数值最大的块被替换掉。 3)近期最少使用(LRU)算法。近期最少使用(Least Recently Used,LRU)算法是将近期最少使用的 Cache 中的信息块替换出去。
10、该算法较先进先出算法要好一些，但此法也不能保证过去不常用将来也不常用。 LRU 算法是依据各块使用的情况，总是选择那个最近最少使用的块被替换。这种方法虽然比较好地反映了程序局部性规律，但是这种替换方法需要随时记录 Cache 中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU 算法相对合理，但实现起来比较复杂，系统开销较大。通常需要对每一块设置一个称为计数器的硬件或软件模块，用以记录其被使用的情况。 实现 LRU 策略的方法有多种，例如计数器法、寄存器栈法及硬件逻辑比较对法等，下面简单介绍计数器法的设计思路。 计数器方法：缓存的每一块都设置一个计数器。计数器的操作规则如下： 被调入或者
11、被替换的块，其计数器清“0”，而其他的计数器则加“1”。 当访问命中时，所有块的计数值与命中块的计数值要进行比较，如果计数值小于命中块的计数值，则该块的计数值加“1”；如果块的计数值大于命中块的计数值，则数值不变。最后将命中块的计数器清为“0”。 需要替换时，则选择计数值最大的块被替换。 4)最优替换算法(OPT 算法)。使用最优化替换算法(OPTimal replacement algorithm)时必须先执行一次程序，统计 Cache 的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换，以达到最优的目的。 前面介绍的几种页面替换算法主要是以主存储器中页面调度情况
12、的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的，显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。 要实现 OPT 算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT 算法只是一种理想化的算法，然而它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其他页面替换算法好坏的标准。在其他条件相同的情况下，哪一种页面替换算法的命中率与 OPT 算法最接近，那
13、么它就是一种比较好的页面替换算法。5)近期最少使用算法(LFU 算法)。近期最少使用(Least Frequently Used algorithm，LFU)算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。3.库函数与系统调用有什么不同 （分数：3.00）_正确
14、答案：()解析：库函数调用是语言或应用程序的一部分，它是高层的，完全运行在用户空间，为程序员提供调用真正的在幕后完成实际事务的系统调用接口。而系统函数是内核提供给应用程序的接口，属于系统的一部分。函数库调用是语言或应用程序的一部分，而系统调用是操作系统的一部分。 库函数与系统调用的区别见下表。 库函数与系统调用的区别 库函数 系统调用 在所有的 ANSI C 编译器版本中，C 库函数是相同的 各个操作系统的系统调用是不同的 它调用函数库中的一段程序(或函数) 它调用系统内核的服务 与用户程序相联系 是操作系统的一个入口点 在用户地址空间执行 在内核地址空间执行 它的运行时间属于“用户时间” 它
15、的运行属于“系统时间” 属于过程调用，调用开销较小 需要在用户空间和内核上下文环境间切换，开销较大 在 C 库函数 libc 中有大约 300 个函数 在 UNIX 中有大约 90 个系统调用 典型的 C 函数库调用：system fprintfmalloc 典型的系统调用：chdir fork write brk 库函数调用通常比行内展开的代码慢，因为它需要付出函数调用的开销。但系统调用比库函数调用还要慢很多，因为它需要把上下文环境切换到内核模式。4.静态链接与动态链接有什么区别 （分数：3.00）_正确答案：()解析：静态链接是指把要调用的函数或者过程直接链接到可执行文件中，成为可执行文件
16、的一部分。换句话说，函数和过程的代码就在程序的 exe 文件中，该文件包含了运行时所需的全部代码。静态链接的缺点是当多个程序都调用相同函数时，内存中就会存在这个函数的多个拷贝，这样就浪费了内存资源。 动态链接是相对于静态链接而言的，动态链接所调用的函数代码并没有被复制到应用程序的可执行文件中去，而是仅仅在其中加入了所调用函数的描述信息(往往是一些重定位信息)。仅当应用程序被装入内存开始运行时，在操作系统的管理下，才在应用程序与相应的动态链接库(dynamic link library，dll)之间建立链接关系。当要执行所调用 dll 中的函数时，根据链接产生的重定位信息，操作系统才转去执行 d
17、ll中相应的函数代码。 静态链接的执行程序能够在其他同类操作系统的机器上直接运行。例如，一个 exe 文件是在 Windows 2000 系统上静态链接的，那么将该文件直接复制到另一台 Windows 2000 的机器上，是可以运行的。而动态链接的执行程序则不可以，除非把该 exe 文件所需的 dll 文件都一并复制过去，或者对方机器上也有所需的相同版本的 dll 文件，否则是不能保证正常运行的。5.静态链接库与动态链接库有什么区别 （分数：3.00）_正确答案：()解析：静态链接库就是使用的.lib 文件，库中的代码最后需要链接到可执行文件中去，所以静态链接的可执行文件一般比较大一些。 动态
18、链接库是一个包含可由多个程序同时使用的代码和数据的库，它包含函数和数据的模块的集合。程序文件(如.exe 文件或.dll 文件)在运行时加载这些模块(也即所需的模块映射到调用进程的地址空间)。 静态链接库和动态链接库的相同点是它们都实现了代码的共享。不同点是静态链接库 lib 中的代码被包含在调用的 exe 文件中，该 lib 中不能再包含其他动态链接库或者静态链接库了。而动态链接库 dll 可以被调用的 exe 动态地“引用”和“卸载”，该 dll 中可以包含其他动态链接库或者静态链接库。6.用户态和核心态有什么区别 （分数：3.00）_正确答案：()解析：核心态与用户态是操作系统的两种运行
19、级别，它用于区分不同程序的不同权利。核心态就是拥有资源多的状态，或者说访问资源多的状态，也称之为特权态。相对来说，用户态就是非特权态，在此种状态下访问的资源将受到限制。如果一个程序运行在特权态，则该程序就可以访问计算机的任何资源，即它的资源访问权限不受限制。如果一个程序运行在用户态，则其资源需求将受到各种限制。例如，如果要访问操作系统的内核数据结构，如进程表，则需要在特权态下才能办到。如果要访问用户程序里的数据，则在用户态下就可以了。 Intel CPU 提供 Ring0Ring3 4 种级别的运行模式。Ring0 级别最高，Ring3 最低。 用户态：Ring3 运行于用户态的代码则要受到处
20、理器的诸多检查，它们只能访问映射其地址空间的页表项中规定的在用户态下可访问页面的虚拟地址，且只能对任务状态段(TTS)中 I/O 许可位图(I/O Permission Bitmap)中规定的可访问端口进行直接访问。 核心态：Ring0 在处理器的存储保护中，核心态或者特权态(与之相对应的是用户态)是操作系统内核所运行的模式。运行在该模式的代码，可以无限制地对系统存储、外部设备进行访问。 当一个任务(进程)执行系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态(或简称为内核态)。此时处理器处于特权级最高的(0 级)内核代码中执行。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈
21、。每个进程都有自己的内核栈。当进程在执行用户自己的代码时，则称其处于用户运行态(用户态)。即此时处理器在特权级最低的(3 级)用户代码中运行。 核心态下 CPU 可执行任何指令，在用户态下 CPU 只能执行非特权指令。当 CPU 处于核心态时，可以随意进入用户态；而当 CPU 处于用户态时，用户从用户态切换到核心态只有在系统调用和中断两种情况下发生。一般程序一开始都是运行于用户态，当程序需要使用系统资源时，就必须通过调用软中断进入核心态。 核心态和用户态各有优势：运行在核心态的程序可以访问的资源多，但可靠性、安全性要求高，维护管理都较复杂；用户态程序访问的资源受限，但可靠性、安全性要求低，自然
22、编写维护起来都较简单。一个程序到底应该运行在核心态还是用户态取决于其对资源和效率的需求。 那么什么样的功能应该在核心态下实现呢?首先，CPU 管理和内存管理都应该在核心态实现。这些功能可不可以在用户态下实现呢?当然能，但是不太安全。就像一个国家的军队(CPU 和内存在计算机里的地位就相当于一个国家的军队的地位)交给老百姓来管一样，是非常危险的。所以从保障计算机安全的角度来说，CPU 和内存的管理必须在核心态实现。 诊断与测试程序也需要在核心态下实现，因为诊断和测试需要访问计算机的所有资源。输入输出管理也一样，因为要访问各种设备和底层数据结构，也必须在核心态实现。 对于文件系统来说，则可以一部分
23、放在用户态，一部分放在核心态。文件系统本身的管理，即文件系统的宏数据部分的管理，必须放在核心态，不然任何人都可能破坏文件系统的结构；而用户数据的管理，则可以放在用户态。编译器、网络管理的部分功能、编辑器用户程序，自然都可以放在用户态下执行。7.用户栈与内核栈有什么区别 （分数：3.00）_正确答案：()解析：内核在创建进程的时候，在创建 task_struct 的同时，会为进程创建相应的堆栈。每个进程会有两个栈，一个用户栈，存在于用户空间；一个内核栈，存在于内核空间。当进程在用户空间运行时，CPU 堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；当进程在内核空间时，CPU 堆栈指针寄存器里
24、面的内容是内核栈空间地址，使用内核栈。 当进程因为中断或者系统调用而陷入内核态时，进程所使用的堆栈也要从用户栈转到内核栈。进程陷入内核态后，先把用户态堆栈的地址保存在内核栈之中，然后设置堆栈指针寄存器的内容为内核栈的地址，这样就完成了用户栈向内核栈的转换；当进程从内核态恢复到用户态之后时，把内核栈中保存的用户态的堆栈的地址恢复到堆栈指针寄存器即可。这样就实现了内核栈和用户栈的互转。 那么，知道从内核转到用户态时用户栈的地址是在陷入内核的时候保存在内核栈里面的，但是在陷入内核的时候，如何知道内核栈的地址?关键在进程从用户态转到内核态的时候，进程的内核栈总是空的。这是因为当进程在用户态运行时，使用
25、的是用户栈，当进程陷入到内核态时，内核栈保存进程在内核态运行的相关信息，但是一旦进程返回到用户态后，内核栈中保存的信息无效，会全部恢复，因此每次进程从用户态陷入内核的时候得到的内核栈都是空的，所以在进程陷入内核的时候，直接把内核栈的栈顶地址给堆栈指针寄存器就可以了。8.如何用递归实现数组求和 （分数：3.00）_正确答案：()解析：给定一个含有 n 个元素的整型数组 a，求 a 中所有元素的和。 如果不要求递归求解，最简单的方法，也是最容易想到的方法只需要进行一次循环，然后求和即可。程序示例如下： #includestdio.h int main() int a=3,6,8,2,1; int
26、i; int len=sizeof(a)/sizeof(a0); int sum=0; for(i=0;ilen;i+) sum+=ai; printf(“%d/n“,sum); return 0; 程序输出结果： 20 问题的难点在于如何使用递归上。如果使用递归，则需要考虑如何进行递归执行的开始以及终止条件，首先如果数组元素个数为 0，那么和为 0。同时，如果数组元素个数为 n，那么先求出前 n-1 个元素之和，再加上 an-1即可。此时可以完成递归功能。程序代码如下： #includestdio.h int GetSum(int*a,int n) return n=0?0:GetSum(a
27、,n-1)+an-1; int main() int a=3,6,8,2,1; int length=sizeof(a)/sizeof(a0); printf(“%d/n“,GetSum(a,length); return 0; 程序输出结果： 209.如何用一个 for 循环打印出一个二维数组 （分数：3.00）_正确答案：()解析：常规的可以通过两层 for 循环嵌套来进行二维数组的输出，设二维数组 arrayMAXXMAXY，其中MAXX 表示的是二维数组的行数，MAXY 表示的是二维数组的列数，程序代码如下： #includestdio.h #define MAXX 2 #define
28、 MAXY 3 void printArray() int arrayMAXXMAXY=1,2,3,4,5,6; for(int i=0;iMAXX;i+) for(int j=0;jMAXY;j+) printf(“%d/n“,arrayij); int main() printArray(); return 0; 而题目要求是只使用一次 for 循环，此时就需要明白二维数组在内存中是按照行存储的还是列存储的了(默认情况是行存储的)，所以可以将数组 array 看成一个一维数组，i 标识该数组在一维数组中的位置，则 array 在二维数组中的行号和列号分别i/MAXY、i%MAXY。具体实现
29、代码如下： #includestdio.h #define MAXX 2 #define MAXY 3 void printArray() int arrayMAXXMAXY=1,2,3,4,5,6); for(int i=0;iMAXX*MAXY;i+) printf(“%d/n“,arrayi/MAXYi%MAXY); int main() printArray(); return 0; 再例如，对于一个三维数组而言，也可以采用类似的方法实现。程序示例代码如下： #includestdio.h int main() int a223:1,6,3,5,4,15,3,5,33,23,12,7;
30、 for(int i=0;i12;i+) printf(“%d“,ai/6(i/3)%2i%3); printf(“/n“); return 0; 程序输出结果： 1 6 3 5 4 15 3 5 33 23 12 7 上例中，需要考虑的是，数组中每一维数字的取值顺序问题。由于该数组为多维数组，第一维，前 6 次循环都取 0，后 6 次取 1，于是 i/6 可以满足要求；第二维，前 3 次为 0，再 3 次为 1，再 3 次为 0，再 3 次为 1，用量化的思想，i/3 把 12 个数字分为 4 组，每组 3 个，量化为 0、1、2、3，为了要得到0、1、0、1，这里就需要对(0、1、2、3)
31、%2=(0、1、0、1)，于是(i/3)%2；最后一维需要的是(0、1、2;0、1、2;0、1、2;0、1、2;)，即 i%3。10.在顺序表中插入和删除一个结点平均移动多少个结点 （分数：3.00）_正确答案：()解析：在等概率情况下，顺序表中插入一个结点需平均移动 n/2 个结点。删除一个结点需平均移动(n-1)/2 个结点。具体的移动次数取决于顺序表的长度 n 以及需插入或删除的位置 i。i 越接近 n 则所需移动的结点数越少。11.如何用递归算法判断一个数组是否是递增 （分数：3.00）_正确答案：()解析：判断一个数组中的元素是否递增，最容易想到的解决办法就是遍历数组，然后判断相邻的
32、两个数组元素的大小是否满足下标小的元素其值也越小。如果不满足，则不是递增数组。 本题要求使用递归的算法，设数组为 a，则递归数组满足以下条件： 1)如果数组长度为 1，则该数组为递增，返回 true。 2)若果数组长度为 n(n2)，则先比较最后两个元素是否递增，如果最后两个元素递增，则再递归比较除去最后一个元素的前 n-1 个元素是否递增。 具体实现代码如下： #includestdio.h bool isIncrease(int a,int n) if(n=1) return true; return (an-1=an-2) int main() int array=1,2,3,3,4,5
33、); int len=sizeof(array)/sizeof(array0); if(isIncrease(array,len) printf(“数组1,2,3,3,4,5是递增数组/n“); else printf(“数组1,2,3,3,4,5不是递增数组/n“); return 0; 程序输出结果： 1,2,3,3,4,5 是递增数组12.如何分别使用递归与非递归实现二分查找算法 （分数：3.00）_正确答案：()解析：二分查找法也称为折半查找法，它的思想是每次都与序列的中间元素进行比较。二分查找的一个前提条件是数组是有序的，假设数组 array 为递增序列，findData 为要查找的
34、数，n 为数组长度，首先将 n个元素分成个数大致相同的两半，取 arrayn/2与将要查找的值 findData 进行比较，如果 findData 等于 arrayn/2，则找到 fmdData，算法终止；如果 findDataarrayn/2，则只要在数组 array 的左半部分继续搜索 findData；如果 findDataarrayn/2，则只需要在数组 array 的右半部分继续搜索即可。二分查找可以使用递归和非递归的方法来解决，以下是示例代码： #includestdio.h 非递归算法，如果存在返回数组位置，不存在则返回-1 int BinarySeareh(int array,
35、int len, int findData) if(array=NULLlen=0) return -1; hat start=0; int end=len-1; while(start=end) int mid=start+(end-start)/2; if(arraymid=findData) return mid; else if(findDataarray mid ) end=mid-1; else start=mid+1; return -1; int BinarySearchRecursion(int array,int findData, int start,int end) i
36、f(startend) return -1; int mid=start+(end-start)/2; if(arraymid=findData) return mid; else if(findDataarraymid) return BinarySearchRecursion(array,findData, start,mid-1); else return BinarySearchRecursion(array,findData,mid+1 ,end); int BinarySearchRecursion(int array,int len,int findData) if(array=
37、NULLlen=0) return -1; return BinaryS earchRecursion(array,findData,0,len-1); int main() int array=1,2,3,4,5,6,7,8; int len=sizeof(array)/sizeof(int); int index=BinarySearch(array,len,4); int index2=BinarySearchRecursion(array,len,9); print f(“%d/n%d/n“,index,index2); return 0; 程序输出结果： 3 -1 需要注意的是，二分查找算法的时间复杂度为 O(logn)，最坏情况下的时间复杂度为 O(logn)。13.如何在排序数组中，找出给定数字出现的次数 （分数：4.00）_
