搜索
C程序员面试(1)怎样才能检测到链表中存在循环面试者可能如下作答1.对访问过的每个元素做个标记，继续遍历这个链表，如果遇到某个已经做过标记的元素，说明链表存在循环。链表位于只读区域，无法在元素上做标记2.当访问每个元素时，把它存在一个数组里。检查每个后据元素，看看它是否已经存在数组中。(哈哈，也许有些人继续想用散列表来优化数组的访问)内存空间有限，无法创建一个足够长的数组。但是，可以假定如果链表中存在循环，那么它出现在前面的N个元素中3.设置一个指针，指向链表的头部。在接下去对直到第N个元素的访问中，把N-1个元素依次同指向的元素进行比较。然后指针移向下一个元素，把同后面的N-2个元素进行比较。根据这个方法依次进行比较，如果出现比较相等的情况，就说明前N个元素中存在循环，否则如果所有N个元素两两之间进行比较都不相等，说明链表中不存在循环。链表的长度是任意的，而且循环可能出现在任何位置。4.参考答案首先，排除一种情况：3个元素的链表，第2个元素的后面是第一个元素。设置两个指针P1和P2,P1指向一个元素，P2指向第3个元素，看看它们是否相等。如果相等就属于上述这种特殊情况。如果不等，把P1后移一个元素，P2后移两个元素。检查两个指针的值，如果相等，说明链表中存在循环。如果不相等，继续按照前述方法进行。如果出现两个指针都是NULL的情况，说明链表中不存在循环。如果链表中存在循环，用这种方法一定能检查出来，因为其中一个指针肯定能追上另一个(两个指针具有相同的值)，尽管可能要对这个链表经过几次遍历才能检测出来。(2)不同的增值语句有什么区别x=x+1;++x;x++;x+=1;需要提供适当的上下文才好找出其中的区别(1)x+=1;是在算法语言中表达x=x+1;的便捷方法(2)++x它先增加x的值，然后再在周围的表达式中使用x的值x++先在周围的表达式中使用x的值，然后再增加x的值(3)当x不是一个简单的变量而是一个涉及数组的表达式，像x+=1这样的形式是很有用的。如果你有一个复杂的数组引用，并需要证明同一种下标形式在两种引用中都可以使用，那么node[i3]+=-(0x01(i&0x7));就是你应该采用的方法。(4)左值(通常具有一个地址，它也可能是一个寄存器，也可能是地址或者寄存器加上一个位段)只被计算了一次。这意味着，表达式mango[j++]+=y;被当作mango[j]=mango[j]+y;j++;而不是mango[j++]=mango[j++]+y;有人解释说，这些区别与编译器的中间代码有关。例如，++x表示取地址x的地址，增加它的内容，然后把值放在寄存器中:x++则表示取x的地址，把它的值转入寄存器，然后增加在内存中的x的值(5)K&R认为++比直接加1更有效率。但是当代编译器在没有区别的上下文中，产生的代码相同的指令，它们应该是增加一个变量最快的一种指令。一般较短的形式比较长的形式更容易阅读一些。然而，过度简洁的代码也会导致代码难以阅读frotz[--j+i++]+=--y;改成--y;--j;frotz[j+i]=frotz[j+i]+y;i++;所以，不要在一行代码里实现太多的功能因为这并不会使编译器产生更有效率的代码，但会使你丧失调试代码的机会。K&R说:人人都知道调试比第一次编写代码要难上一倍。所以，如果在编写代码时就把自己的聪明发挥到极致，那么调试时又该怎么办呢？(3)库函数调用和系统调用简单的回答是库函数调用是语言或应用程序的一部分，而系统调用是操作系统的一部分。你要确保弄懂trap的含义。系统调用是操作系统内核发现一个trap或者中断之后进行的。库函数调用系统调用在ANSIC编译器中，C函数库是系统的各个操作系统的系统调用是不同的。符合Posix标准的OS，它们的系统调用是相同的吗？调用函数库的一个程序调用系统内核服务与用户程序相联系是操作系统的一个进入点在用户的地址空间执行在内核的地址空间执行运行时间属于“user”时间属于“system时间属于过程调用，开销较小需要切换到内核上下文环境然后在切换回来，开销较大在C函数库libc中大约300个程序UNIX中约90个系统调用典型调用systemfprintfmalloc----------chdirforkwritebrk但是，你必须记住：许多C函数库中的程序是通过系统调用来实现功能的。比如文件系统相关的操作windows中fopen大概就是调用CreateFile(4)文件描述符和文件指针系统IO调用有creat(),open(),read(),write(),close(),ioctl(),接受一个文件描述符，是一个整数，用于索引开放文件的每个进程表(per-processtable-of-open-file)为了确保程序的可移植性应该使用标准IO库调用，如fopen(0,fclose(),fputc(),fseek()等，它们绝大多数中的名字中带有一个f。这些调用都接受一个类型为FILE结构的指针(有时称为流指针)的参数。FILE指针指向一个流结构，在stdio.h中定义。结构的内容根据编译器的不同而有所不同，在UNIX中通常是OpenFile的每个进程表的一个条目。在典型情况下，它包含了流缓冲区、所有用于提示缓冲区有多少字节是实际的文件数据的变量以及提示流状态的标志(如ERROR和EOF)等所以，文件描述符就是OpenFile中的每个进程表的一个偏移量(如3)。它用于UNIX系统中，用于标识文件。FILE指针保存了一个FILE结构的地址。FILE结构用于表示开放的I/O流(如hex20938).它用于ANSIC标准的IO库调用中，用于标识文件。(5)确定一个变量unsigned还是signed函数的参数形式是在函数内部定义的，所以你无法用函数来实现这个目的。那么用宏。有符号数的本质就是对最左边的一个位取补将会改变它的符号。由于其他位与这个测试无关，所以你可以将它的所有位都取补。#defineISUNSIGNED(a)(a=0&&~a=0)ANSIC的类型提升规则(所有的表达式中，如果是个变量，因为编译器无法判断结果是否溢出，都对类型进行提升)charshortintbit(unsigned/signed)enum如果int能够完整的容纳原先的数据，否则将被转换为unsignedintgcc居然丢出这样一句话来warning:comparisonisalwaystrueduetolimitedrangeofdatatype如果是一个类型#defineISUNSIGNED(type)((type)0-1)0)预处理器（Preprocessor）1.用预处理指令#define声明一个常数，用以表明1年中有多少秒（忽略闰年问题）#defineSECONDS_PER_YEAR(60*60*24*365)UL我在这想看到几件事情：1)#define语法的基本知识（例如：不能以分号结束，括号的使用，等等）2)懂得预处理器将为你计算常数表达式的值，因此，直接写出你是如何计算一年中有多少秒而不是计算出实际的值，是更清晰而没有代价的。3)意识到这个表达式将使一个16位机的整型数溢出-因此要用到长整型符号L,告诉编译器这个常数是的长整型数。4)如果你在你的表达式中用到UL（表示无符号长整型），那么你有了一个好的起点。记住，第一印象很重要。2.写一个标准宏MIN，这个宏输入两个参数并返回较小的一个。#defineMIN(A,B)（（A）=(B)?(A):(B))这个测试是为下面的目的而设的：1)标识#define在宏中应用的基本知识。这是很重要的。因为在嵌入(inline)操作符变为标准C的一部分之前，宏是方便产生嵌入代码的唯一方法，对于嵌入式系统来说，为了能达到要求的性能，嵌入代码经常是必须的方法。2)三重条件操作符的知识。这个操作符存在C语言中的原因是它使得编译器能产生比if-then-else更优化的代码，了解这个用法是很重要的。3)懂得在宏中小心地把参数用括号括起来4)我也用这个问题开始讨论宏的副作用，例如：当你写下面的代码时会发生什么事？least=MIN(*p++,b);3.预处理器标识#error的目的是什么？如果你不知道答案，请看参考文献1。这问题对区分一个正常的伙计和一个书呆子是很有用的。只有书呆子才会读C语言课本的附录去找出象这种问题的答案。当然如果你不是在找一个书呆子，那么应试者最好希望自己不要知道答案。死循环（Infiniteloops）4.嵌入式系统中经常要用到无限循环，你怎么样用C编写死循环呢？这个问题用几个解决方案。我首选的方案是：while(1){}一些程序员更喜欢如下方案：for(;;){}这个实现方式让我为难，因为这个语法没有确切表达到底怎么回事。如果一个应试者给出这个作为方案，我将用这个作为一个机会去探究他们这样做的基本原理。如果他们的基本答案是：我被教着这样做，但从没有想到过为什么。这会给我留下一个坏印象。第三个方案是用gotoLoop:...gotoLoop;应试者如给出上面的方案，这说明或者他是一个汇编语言程序员（这也许是好事）或者他是一个想进入新领域的BASIC/FORTRAN程序员。数据声明（Datadeclarations）5.用变量a给出下面的定义a)一个整型数（Aninteger）b)一个指向整型数的指针（Apointertoaninteger）c)一个指向指针的的指针，它指向的指针是指向一个整型数（Apointertoapointertoanintege）rd)一个有10个整型数的数组（Anarrayof10integers）e)一个有10个指针的数组，该指针是指向一个整型数的。（Anarrayof10pointerstointegers）f)一个指向有10个整型数数组的指针（Apointertoanarrayof10integers）g)一个指向函数的指针，该函数有一个整型参数并返回一个整型数（Apointertoafunctionthattakesanintegerasanargumentandreturnsaninteger）h)一个有10个指针的数组，该指针指向一个函数，该函数有一个整型参数并返回一个整型数（Anarrayoftenpointerstofunctionsthattakeanintegerargumentandreturnaninteger）答案是：a)inta;//Anintegerb)int*a;//Apointertoanintegerc)int**a;//Apointertoapointertoanintegerd)inta[10];//Anarrayof10integerse)int*a[10];//Anarrayof10pointerstointegersf)int(*a)[10];//Apointertoanarrayof10integersg)int(*a)(int);//Apointertoafunctionathattakesanintegerargumentandreturnsanintegerh)int(*a[10])(int);//Anarrayof10pointerstofunctionsthattakeanintegerargumentandreturnaninteger人们经常声称这里有几个问题是那种要翻一下书才能回答的问题，我同意这种说法。当我写这篇文章时，为了确定语法的正确性，我的确查了一下书。但是当我被面试的时候，我期望被问到这个问题（或者相近的问题）。因为在被面试的这段时间里，我确定我知道这个问题的答案。应试者如果不知道所有的答案（或至少大部分答案），那么也就没有为这次面试做准备，如果该面试者没有为这次面试做准备，那么他又能为什么出准备呢？Static6.关键字static的作用是什么？这个简单的问题很少有人能回答完全。在C语言中，关键字static有三个明显的作用：1)在函数体，一个被声明为静态的变量在这一函数被调