C语言心机婊!一道单选题需求考试这么多知识吗?

转发自微信公众账号:开点工作室(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位系统中的实际履行意况

假若在英特尔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。

因此可以看来,即使该题只是一道简单的选料题,其中富含着的背景知识却万分丰裕,该题完全能够变换成一道面试中的综合难点,考查应聘者是或不是可以熟练有关的背景知识,并且能够按照那一个基础知识举办合理实用的辨析。