心机婊!一道单选题需要考试这么多学问也?

转载自微信公众账号:开点工作室(ID:kaidiancs)

阿里2015笔试中起这般平等鸣题目:

于同令主流配置的PC上,调用f(35)所待的日子大概是()。

int f(int x){

int s = 0;

while(x++ >0)s+= f(x);

return max(s,1);

}

A.几毫秒B.几秒C.几分钟D.几小时

主题涉及到的知识点包括数据的表示与运算、时间复杂度。考查考生对拉动符号整数的意味、递归调用的执行进程、计算机体系特性、虚拟存储器、C语言语句等息息相关文化之明白与动能力。

数学及的剖析推导结果及电脑体系遭到的施行结果是起反差的。例如,在数学中一个勤得尽好,但以计算机被吃表示位数的范围,数的价值是简单的。用数学分析的办法,本题的递归是好住之,但让仓储容量的限定,在处理器被递归调用时见面来栈溢出之题目,导致程序不可知正常尽了。类似之题目还有多,这是平日编程时要小心的。

万一题目中之函数用C语言书写,要分析调用f(35)所需要的工夫,就得分析代码执行中循环执行次数及递归调用次数等于,下面深入剖析f(35)执行过程中留存的问题。

(1)程序是否会面终止?

调用f(35)时,入口参数x=35。从数学的角度理解while中之判断表达式“x++
>0”,会以为x每当增量后永久特别于0,这是一个永真式,从而做出错误结论:程序死循环。在微机中数值是来限制之,int型数据用补码表示,占4个字节,能表示的太要命正数是2-1
= 7FFFFFFFH。231的机器数是8000
0000H,其值为int型能代表的极度小负数-2147483648,因此当x= 8000
0000H时,x>
0的值也假,程序退出while循环,因此,若无考虑栈溢出,则程序能够实施了。

(2)使递归终止之顶特别x价值是稍微?

while(x++ >0)语句以Microsoft
VC中之机器代码如下,该语句的施行进程是:先拿x的价分别保存及EDX和EAX寄存器;然后对EAX寄存器内容加以1,以实现x=x+1操作;最后重复用EDX的情(x的旧值)进行x>0之条件判断。

mov       edx, dword ptr [ebp+8]

mov        eax,dword ptr [ebp+8]

add        eax, 1

mov       dword ptr [ebp+8], eax

test        edx, edx

jle         f+77h (00401097)

因此,当调用f(231-1)时,x= 231-1=7FFF FFFFH,先执行x=7FFF FFFFH+1
= 8000 0000H=231,然后,用旧的x=7FFF
FFFFH与0比较,比较结实为真正,故执行while循环体,在循环体中调用f(231)。

调用f(231)时,x也231= 8000
0000H,其真值为负数,因此,与0比较的结果也假,故跳出while循环体,程序结束。

综上所述,使递归终止之无比深x值是231,即执行f(231)时了递归调用。

(3)函数f(x)的递归调用情况怎么样?

f(x)是一个递归调用过程,并且递归调用在循环体内,因此调用关系比复杂。图1展示了f(231-4)执行着之递归调用情况。

图1f(231-4)执行着之递归调用情况

f(x)执行进程被,把执行f(x)过程体的总次数记为f(x)执行次数,把同坏递归调用的最好可怜次数记为f(x)递归深度。表1给闹了x啊无同值时,执行f(x)的次数与递归深度。这半单参数显示了f(x)函数的履行过程。

(4)递归调用过程的施行情况

系统会吃各国一个用户进程分配存放代码和数量的用户空间,用户空间被之栈区用来存放程序运行时经过调用的参数、返回地址、过程有变量等。随着程序的实践,栈区不断动态地自高地址为低地址增长要朝向反方向减退。

用户栈由若干单栈帧组成,每个过程对应一个栈帧,帧指针寄存器EBP指定一个栈帧的发端地址,栈指针寄存器ESP指向栈顶,当前栈帧的限定在EBP和ESP指向的区域之间。过程实行时,由于不断产生多少入栈,所以栈指针ESP会动态移动,而帧指针EBP固定不更换。在一个经过外对栈中信息之访问大多通过帧指针EBP进行。

IA-32规定,寄存器EAX、ECX和EDX是调用者保存寄存器,EBX、ESI、EDI寄存器是被调用者保存寄存器。若过程P调用经过Q时,P在用经常先在投机之栈区保存EAX、ECX和EDX、入口参数和归地址,接着跳反到Q执行。Q在大团结之栈帧中优先保存P的EBP值,并设置EBP指向当前Q栈帧的栈低,根据需要保存EBX、ESI、EDI,再以栈中给Q的有些变量分配空间。

以递归调用执行中,每个递归调用过程都发一个栈帧。栈帧中可能含如图2所著之信。

图3展示了在windows系统中f(x)函数调用时之有些机器指令。可以看到f(x)的栈帧至少有84B。系统分配为一个经过的用户栈只生些许的上空,因此,递归调用的次数是有限的。f(35)的递归深度是2147483614,即至少用2147483614×84字节,即超过170GB的栈帧空间。在32各类系统遭到,最酷虚拟地址空间就发生4GB,用户栈只是中间的同部分,所以f(35)在履行过程中见面起栈溢出底景象。

祈求3 f(x)函数调用时之有的机器指令

(5)f(35)在32员系统中的骨子里执行情况

假要于Intel
x86+windows+VC+C语言环境受到执f(35)。VC中默认分配栈的轻重缓急是1MB,虽然用户可调动栈大小,但堆栈的容量是少数的。按2MB底栈空间、栈大小按照80许节约计算:2MB÷80B≈26214,因此f(x)递归调用的次数不见面越26214-1=26213次。从图4.9负可以看,栈溢出时,f(x)函数体最多尽26213糟。栈溢出时每个f(x)函数体只以while语句被推行,假设每个f(x)函数体执行100修指令,即使指令平均CPI为3,时钟频率为2.4GHz,f(35)的履行时间也惟有出26213×100×3÷2.4GHz
≈3.2 ms左右时刻。

f(35)的行做了测试,在仓房大小是1MB时,递归调用11244糟后栈溢出;在库设置也2MB常常,递归调用22642潮后栈溢出,显然运行时刻仅仅生几乎毫秒。在Microsoft
VisualStudio 2012条件被运行,出现如图4所出示结果,表明出现了栈溢出(Stack
overflow)。

综上所述,答案为A。

通过可看到,虽然该题只是平鸣简单的挑题,其中蕴藏着的背景知识却非常丰富,该题完全可转换成一头面试中的归纳问题,考查应聘者是否会熟悉相关的背景知识,并且能基于这些基础知识进行合理可行的辨析。