程序员笔试面试.doc

《程序员笔试面试.doc》由会员分享，可在线阅读，更多相关《程序员笔试面试.doc（53页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、先发基本问题，再发编程问题.想成为嵌入式程序员应知道的 0x10 个基本问题:1：(void *)ptr 和 (*(void*)ptr 的结果是否相同？其中 ptr 为同一个指针 .(void *)ptr 和 (*(void*)ptr 值是相同的 2：int main()int x=3;printf(“%d“,x);return 1;问函数既然不会被其它函数调用，为什么要返回 1？ mian 中，c 标准认为 0 表示成功，非 0 表示错误。具体的值是某中具体出错信息1，要对绝对地址 0x100000 赋值，我们可以用 (unsigned int*)0x100000 = 1234;那么要是想让

2、程序跳转到绝对地址是 0x100000 去执行，应该怎么做？ *(void (*)( )0x100000 ) ( );首先要将 0x100000 强制转换成函数指针,即: (void (*)()0x100000然后再调用它: *(void (*)()0x100000)();用 typedef 可以看得更直观些: typedef void(*)() voidFuncPtr; *(voidFuncPtr)0x100000)();2，已知一个数组 table，用一个宏定义，求出数据的元素个数 #define NTBL #define NTBL (sizeof(table)/sizeof(table0

3、)面试题: 线程与进程的区别和联系? 线程是否具有相同的堆栈? dll 是否有独立的堆栈? 进程是死的，只是一些资源的集合，真正的程序执行都是线程来完成的，程序启动的时候 操作系统就帮你创建了一个主线程。每个线程有自己的堆栈。 DLL 中有没有独立的堆栈，这个问题不好回答，或者说这个问题本身是否有问题。因为 DLL 中的代码是被某些线程所执行，只有线程拥有堆栈，如果 DLL 中的代码是 EXE 中的线程所 调用，那么这个时候是不是说这个 DLL 没有自己独立的堆栈？如果 DLL 中的代码是由 DLL 自己创建的线程所执行，那么是不是说 DLL 有独立的堆栈？以上讲的是堆栈，如果对于堆来说，每个

4、 DLL 有自己的堆，所以如果是从 DLL 中动态分配的内存，最好是从 DLL 中删除，如果你从 DLL 中分配内存，然后在 EXE 中，或者另外一个 DLL 中删除，很有可能导致程序崩溃unsigned short A = 10; printf(“A = %un“, A);char c=128; printf(“c=%dn“,c);输出多少？并分析过程 第一题，A 0xfffffff5,int 值 为11，但输出的是 uint。所以输出 4294967285 第二题，c0x10,输出的是 int，最高位为 1，是负数，所以它的值就是 0x00 的补码就是 128，所以输出128。 这两道题都

5、是在考察二进制向 int 或 uint 转换时的最高位处理。分析下面的程序： void GetMemory(char *p,int num) *p=(char *)malloc(num); int main() char *str=NULL;GetMemory(strcpy(str,“hello“);free(str);if(str!=NULL)strcpy(str,“world“); printf(“n str is %s“,str);getchar(); 问输出结果是什么？希望大家能说说原因，先谢谢了 输出 str is world。 free 只是释放的 str 指向的内存空间,它本身的

6、值还是存在的. 所以 free 之后，有一个好的习惯就是将 str=NULL.此时 str 指向空间的内存已被回收,如果输出语句之前还存在分配空间的操作的话,这段存储 空间是可能被重新分配给其他变量的, 尽管这段程序确实是存在大大的问题（上面各位已经说得很清楚了） ，但是通常会打印出 world 来。 这是因为，进程中的内存管理一般不是由操作系统完成的，而是由库函数自己完成的。 当你 malloc 一块内存的时候，管理库向操作系统申请一块空间（可能会比你申请的大一些） ，然后在这块空间中记录一些管理信息（一般是在你申请的内存前面一点） ，并将可用内存 的地址返回。但是释放内存的时候，管理库通常

7、都不会将内存还给操作系统，因此你是可 以继续访问这块地址的，只不过。 。 。 。 。 。 。 。楼上都说过了，最好别这么干。char a10,strlen(a)为什么等于 15？运行的结果#include “stdio.h“ #include “string.h“void main() char aa10; printf(“%d“,strlen(aa); sizeof()和初不初始化，没有关系； strlen()和初始化有关。char (*str)20;/*str 是一个数组指针，即指向数组的指针*/ char *str20;/*str 是一个指针数组，其元素为指针型数据*/long a=0x

8、801010; a+5=?0x801010 用二进制表示为：“1000 0000 0001 0000 0001 0000” ，十进制的值为 8392720， 再加上 5 就是 8392725 罗1)给定结构 struct A char t:4;char k:4;unsigned short i:8;unsigned long m;问 sizeof(A) = ? 给定结构 struct A char t:4; 4 位char k:4; 4 位unsigned short i:8; 8 位 unsigned long m; / 偏移 2 字节保证 4 字节对齐 ; / 共 8 字节 2)下面的函数

9、实现在一个数上加一个数，有什么错误？请改正。 int add_n ( int n ) static int i = 100;i += n;return i; 当你第二次调用时得不到正确的结果，难道你写个函数就是为了调用一次？问题就出在 static 上？/ 帮忙分析一下 #include #include #include #include #include #include typedef struct AA int b1:5;int b2:2; AA; void main() AA aa;char cc100;strcpy(cc,“0123456789abcdefghijklmnopqrs

10、tuvwxyz“);memcpy(cout 0 分析： struct bit int a:3; int b:2; int c:3; ; int main() bit s; char *c=(char*) coutint main(void) int *p;int arr100;p = return 0; 解答： 搞错了,是指针类型不同, int *p; /二级指针/得到的是指向第一维为 100 的数组的指针 #include int main(void) int *p, *q; int arr100; q = arr; p = return 0; 下面这个程序执行后会有什么错误或者效果:#de

11、fine MAX 255int main() unsigned char AMAX,i;/i 被定义为 unsigned charfor (i=0;i #include int main(void) int MAX = 10; int *a = (int *)malloc(MAX * sizeof(int); int *b;FILE *fp1; FILE *fp2;fp1 = fopen(“a.txt“,“r“); if(fp1 = NULL) printf(“error1“);exit(-1); fp2 = fopen(“b.txt“,“w“); if(fp2 = NULL) printf(

12、“error2“);exit(-1); int i = 0;int j = 0;while(fscanf(fp1,“%d“, j+; if(i = MAX) MAX = 2 * MAX; b = (int*)realloc(a,MAX * sizeof(int); if(b = NULL) printf(“error3“); exit(-1); a = b; for(;-j = 0;)fprintf(fp2,“%dn“,aj);fclose(fp1); fclose(fp2);return 0; 第二题. #include int main(void) unsigned long int i,

13、j,k;printf(“please input the numbern“); scanf(“%d“,if( i % 2 = 0)j = i / 2; else j = i / 2 + 1;printf(“The result is n“);for(k = 0; k void main() unsigned long int a,i=1; scanf(“%d“, if(a%2=0) for(i=1;i void test(FILE *fread, FILE *fwrite) char buf1024 = 0;if (!fgets(buf, sizeof(buf), fread)return;t

14、est( fread, fwrite );fputs(buf, fwrite); int main(int argc, char *argv) FILE *fr = NULL;FILE *fw = NULL;fr = fopen(“data“, “rb“);fw = fopen(“dataout“, “wb“);test(fr, fw);fclose(fr);fclose(fw);return 0; 在对齐为 4 的情况下 struct BBB long num；char *name;short int data;char ha;short ba5; *p; p=0x1000000; p+0x

15、200=_; (Ulong)p+0x200=_; (char*)p+0x200=_;希望各位达人给出答案和原因，谢谢拉 解答：假设在 32 位 CPU 上，sizeof(long) = 4 bytes sizeof(char *) = 4 bytes sizeof(short int) = sizeof(short) = 2 bytes sizeof(char) = 1 bytes由于是 4 字节对齐， sizeof(struct BBB) = sizeof(*p) = 4 + 4 + 2 + 1 + 1/*补齐*/ + 2*5 + 2/*补齐*/ = 24 bytes (经 Dev-C+验证

16、)p=0x1000000; p+0x200=_;= 0x1000000 + 0x200*24(Ulong)p+0x200=_;= 0x1000000 + 0x200(char*)p+0x200=_;= 0x1000000 + 0x200*4你可以参考一下指针运算的细节写一段程序，找出数组中第 k 大小的数，输出数所在的位置。例如2，4，3，4，7中，第 一大的数是 7，位置在 4。第二大、第三大的数都是 4，位置在 1、3 随便输出哪一个均可。 函数接口为：int find_orderk(const int* narry,const int n,const int k) 要求算法复杂度不能是

17、O(n2） 谢谢！ 可以先用快速排序进行排序，其中用另外一个进行地址查找 代码如下，在 VC+6.0 运行通过。给分吧-/快速排序#includeusingnamespacestd;intPartition (int*L,intlow,int high) inttemp = Llow; intpt = Llow;while (low = pt)-high; Llow = Lhigh; while (low t;while (t != -1) narrysum = t; addrsum - 1 = t; sum+;cin t; sum -= 1; QSort (narry,1,sum);for

18、(int i = 1; i k;intaa = 1; intkk = 0; for (;) if (aa = k) break; if (narrykk != narrykk + 1) aa += 1; kk+; cout next!=NULL qa=qa-next; else ra-next=pa; pa=pa-next; if(pa-next!=NULL) ra-next=pa; if(qa-next!=NULL) ra-next=qa; return R; 2、运用四色定理，为 N 个局域举行配色，颜色为 1、2、3、4 四种，另有数组 adjN，如 adjij=1 则表示 i 区域与

19、j 区域相邻，数组 colorN，如 colori=1,表示 i 区域的颜色为 1 号颜色。 四色填充 3、用递归算法判断数组 aN是否为一个递增数组。 递归的方法，记录当前最大的，并且判断当前的是否比这个还大，大则继续，否则返回 false 结束：bool fun( int a, int n ) if( n= =1 ) return true; if( n= =2 ) return an-1 = an-2; return fun( a,n-1) 4、编写算法，从 10 亿个浮点数当中，选出其中最大的 10000 个。 用外部排序，在数据结构书上有 计算方法导论在找到第 n 大的数的算法上加工

20、 5、编写一 unix 程序，防止僵尸进程的出现.同学的 4 道面试题，应聘的职位是搜索引擎工程师，后两道超级难， （希望大家多给一些算 发） 1.给两个数组和他们的大小，还有一动态开辟的内存，求交集，把交集放到动态内存 dongtai，并且返回交集个数 long jiaoji(long* a,long b,long* alength,long blength,long* dongtai)2.单连表的建立，把a-z26 个字母插入到连表中，并且倒叙，还要打印！ 方法 1： typedef struct val int date_1;struct val *next; *p;void main(

21、void) char c;for(c=122;c=97;c-) p.date=c;p=p-next;p.next=NULL; 方法 2： node *p = NULL; node *q = NULL;node *head = (node*)malloc(sizeof(node); head-data = ;head-next=NULL;node *first = (node*)malloc(sizeof(node);first-data = a;first-next=NULL;head-next = first; p = first;int longth = z - b; int i=0; w

22、hile ( idata = b+i;temp-next=NULL;q=temp;head-next = temp; temp-next=p;p=q; i+; print(head);3.可怕的题目终于来了 象搜索的输入信息是一个字符串，统计 300 万输入信息中的最热门的前十条，我们每次输 入的一个字符串为不超过 255byte,内存使用只有 1G, 请描述思想，写出算发（c 语言） ，空间和时间复杂度， 4.国内的一些帖吧，如 baidu,有几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样 设计这个系统速度最好，请描述思想，写出算发（c 语言） ，空间和时间复杂度，#include s

23、tring.h main(void) char *src=“hello,world“;char *dest=NULL;dest=(char *)malloc(strlen(src);int len=strlen(str);char *d=dest;char *s=srclen;while(len-!=0)d+=s-;printf(“%s“,dest); 找出错误！ #include “string.h“ #include “stdio.h“ #include “malloc.h“ main(void) char *src=“hello,world“;char *dest=NULL;dest=(

24、char *)malloc(sizeof(char)*(strlen(src)+1);int len=strlen(src);char *d=dest;char *s=src+len-1;while(len-!=0)*d+=*s-; *d=0;printf(“%s“,dest); 1. 简述一个 Linux 驱动程序的主要流程与功能。2. 请列举一个软件中时间换空间或者空间换时间的例子。 void swap(int a,int b) int c; c=a;a=b;b=a; -空优 void swap(int a,int b) a=a+b;b=a-b;a=a-b; 6. 请问一下程序将输出什么结

25、果？ char *RetMenory(void) char p = “hellow world”;return p; void Test(void) char *str = NULL;str = RetMemory();printf(str); RetMenory 执行完毕，p 资源被回收，指向未知地址。返回地址，str 的内容应是不可预测 的, 打印的应该是 str 的地址写一个函数,它的原形是 int continumax(char *outputstr,char *intputstr) 功能： 在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其 中一个函数参数

26、 outputstr 所指内存。例如：“abcd12345ed125ss123456789“的首地址传给 intputstr 后，函数将返回 9，outputstr 所指的值为 123456789int continumax(char *outputstr, char *inputstr) char *in = inputstr, *out = outputstr, *temp, *final; int count = 0, maxlen = 0;while( *in != 0 ) if( *in 47 /*delete the number*/if(sign using namespace

27、std;void itochar(int num);void itochar(int num) int i = 0; int j ; char stra10; char strb10; while ( num ) strai+=num%10+48; num=num/10; strai = 0; for( j=0; j num; itochar(num); return 0; 前几天面试，有一题想不明白,请教大家！typedef struct int a:2;int b:2;int c:1;test;test t;t.a = 1;t.b = 3;t.c = 1;printf(“%d“,t.a);

28、printf(“%d“,t.b);printf(“%d“,t.c);谢谢! t.a 为 01,输出就是 1 t.b 为 11，输出就是1 t.c 为 1，输出也是-1 3 个都是有符号数 int 嘛。 这是位扩展问题 01 11 1编译器进行符号扩展求组合数： 求 n 个数（1.n）中 k 个数的组合.如：combination(5,3)要求输出：543，542，541，532，531，521，432，431，421，321， #includeint pop(int *); int push(int ); void combination(int ,int );int stack3=0; to

29、p=-1;int main() int n,m; printf(“Input two numbers:n“); while( (2!=scanf(“%d%*c%d“, printf(“Input error! Again:n“); combination(n,m); printf(“n“); void combination(int m,int n) int temp=m; push(temp); while(1) if(1=temp) if(pop( else if( push(-temp) printf(“%d%d%d “,stack0,stack1,stack2);/? pop( int

30、 push(int i) stack+top=i; if(top=0) return 0; else return 1; 1、用指针的方法，将字符串“ABCD1234efgh”前后对调显示 #include #include #include int main() char str = “ABCD1234efgh“;int length = strlen(str);char * p1 = str;char * p2 = str + length - 1;while(p1 double getValue() double result = 0;int i = 2;while(i 2006-4-1

31、7 10:17:34白日?做梦!一级(初级)user1100342313244691482695883free131012（删除）345(删除)670（删除） ，如此循环直到 最后一个数被删除。 方法 1：数组 #include using namespace std; #define null 1000int main() int arr1000; for (int i=0;i using namespace std; #define null 0 struct node int data; node* next; ; int main() node* head=new node; head

32、-data=0; head-next=null; node* p=head; for(int i=1;idata=i; tmp-next=null; head-next=tmp; head=head-next; head-next=p; while(p!=p-next) p-next-next=p-next-next-next;p=p-next-next; coutdata; return 0; 方法 3：通用算法 #include #define MAXLINE 1000 /元素个数 /*MAXLINE 元素个数 a 元素数组 R 指针场 suffix 下标 index 返回最后的下标序号

33、values 返回最后的下标对应的值 start 从第几个开始 K 间隔 */ int find_n(int a,int R,int K,intint front_node,current_node;suffix=0;if(s=0) current_node=0;front_node=MAXLINE-1;else current_node=s;front_node=s-1;while(Rfront_node!=front_node) printf(“%dn“,acurrent_node);Rfront_node=Rcurrent_node;if(K=1) current_node=Rfront

34、_node;continue;for(int i=0;inumber=key) Head=Pointer-next; free(Pointer); break; Back = Pointer;Pointer=Pointer-next; if(Pointer-number=key) Back-next=Pointer-next; free(Pointer); break; void delete(Node* p) if(Head = Node)while(p) 有一个 16 位的整数，每 4 位为一个数，写函数求他们的和。 解释： 整数 1101010110110111 和 1101+0101+

35、1011+0111 感觉应该不难，当时对题理解的不是很清楚，所以写了一个函数，也不知道对不对。 疑问：既然是 16 位的整数，1101010110110111 是 2 进制的，那么函数参数怎么定义呢，请 大虾指教。 答案：用十进制做参数，计算时按二进制考虑。 /* n 就是 16 位的数，函数返回它的四个部分之和 */ char SumOfQuaters(unsigned short n) char c = 0;int i = 4;doc += n n = n 4; while (-i);return c; 有 1,2,.一直到 n 的无序数组,求排序算法,并且要求时间复杂度为 O(n),空间

36、复杂度 O(1),使 用交换,而且一次只能交换两个数.（华为） #includeint main() int a = 10,6,9,5,2,8,4,7,1,3;int len = sizeof(a) / sizeof(int);int temp;for(int i = 0; i next; while(q!=NULL) r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; return head; 2 写出程序删除链表中的所有接点 void del_all(node *head) node *p; while(head!=NULL) p=h

37、ead-next; free(head); head=p; cout src ) 282 d = (char *)dst + len - 1;283 s = (char *)src + len - 1;284 while ( len = 4 ) 285 *d- = *s-;286 *d- = *s-;287 *d- = *s-;288 *d- = *s-;289 len -= 4;290 291 while ( len- ) 292 *d- = *s-;293 294 else if ( dst = 4 ) 298 *d+ = *s+;299 *d+ = *s+;300 *d+ = *s+;3

38、01 *d+ = *s+;302 len -= 4;303 304 while ( len- ) 305 *d+ = *s+;306 307 308 return dst;309 公司考试这种题目主要考你编写的代码是否考虑到各种情况，是否安全（不会溢出） 各种情况包括： 、参数是指针，检查指针是否有效 、检查复制的源目标和目的地是否为同一个，若为同一个，则直接跳出 、读写权限检查 、安全检查，是否会溢出 memcpy 拷贝一块内存，内存的大小你告诉它 strcpy 是字符串拷贝，遇到0结束/* memcpy 拷贝不重叠的内存块 */ void memcpy(void* pvTo, void*

39、pvFrom, size_t size) void* pbTo = (byte*)pvTo; void* pbFrom = (byte*)pvFrom;ASSERT(pvTo != NULL /检查输入指针的有效性 ASSERT(pbTo=pbFrom+size | pbFrom=pbTo+size);/检查两个指针指向的内存是否重叠while(size0) *pbTo+ = *pbFrom+; return(pvTo); 华为面试题：怎么判断链表中是否有环？ bool CircleInList(Link* pHead) if(pHead = = NULL | pHead-next = = N

40、ULL)/无节点或只有一个节点并且无自环 return (false);if(pHead-next = = pHead)/自环 return (true); Link *pTemp1 = pHead;/step 1 Link *pTemp = pHead-next;/step 2 while(pTemp != pTemp1 pTemp = pTemp-next-next; if(pTemp = = pTemp1) return (true); return (false); 两个字符串，s,t;把 t 字符串插入到 s 字符串中，s 字符串有足够的空间存放 t 字符串 void insert(

41、char *s, char *t, int i) memcpy( memcpy( sstrlen(s)+strlen(t)=0; 1。编写一个 C 函数，该函数在一个字符串中找到可能的最长的子字符串，且该字符串是 由同一字符组成的。 char * search(char *cpSource, char ch) char *cpTemp=NULL, *cpDest=NULL;int iTemp, iCount=0;while(*cpSource)if(*cpSource = ch)iTemp = 0;cpTemp = cpSource;while(*cpSource = ch) +iTemp,

42、+cpSource;if(iTemp iCount) iCount = iTemp, cpDest = cpTemp;if(!*cpSource) break;+cpSource;return cpDest; 2。请编写一个 C 函数，该函数在给定的内存区域搜索给定的字符，并返回该字符所在位 置索引值。 int search(char *cpSource, int n, char ch) int i;for(i=0; inext,并随后删除原 next 指向的节点。#include void foo(int m, int n) printf(“m=%d, n=%dn“, m, n); int

43、main() int b = 3;foo(b+=3, +b);printf(“b=%dn“, b); return 0; 输出：m=7,n=4,b=7(VC6.0) 这种方式和编译器中得函数调用关系相关即先后入栈顺序。不过不同 编译器得处理不同。也是因为 C 标准中对这种方式说明为未定义，所以 各个编译器厂商都有自己得理解，所以最后产生得结果完全不同。因为这样，所以遇见这种函数，我们首先要考虑我们得编译器会如何处理 这样得函数，其次看函数得调用方式，不同得调用方式，可能产生不同得 结果。最后是看编译器优化。2.写一函数，实现删除字符串 str1 中含有的字符串 str2. 第二个就是利用一个

44、KMP 匹配算法找到 str2 然后删除（用链表实现的话，便捷于数组）/*雅虎笔试题(字符串操作) 给定字符串 A 和 B,输出 A 和 B 中的最大公共子串。 比如 A=“aocdfe“ B=“pmcdfa“ 则输出“cdf“ */ /Author: azhen #include #include #includechar *commanstring(char shortstring, char longstring) int i, j;char *substring=malloc(256);if(strstr(longstring, shortstring)!=NULL) /如果，那么返回

45、 shortstring return shortstring; for(i=strlen(shortstring)-1;i0; i-) /否则，开始循环计算 for(j=0; jstrlen(str2) /将短的字符串放前面 comman=commanstring(str2, str1); else comman=commanstring(str1, str2);printf(“the longest comman string is: %sn“, comman); 11.写一个函数比较两个字符串 str1 和 str2 的大小，若相等返回 0，若 str1 大于 str2 返回 1，若 s

46、tr1 小于 str2 返回1 int strcmp ( const char * src,const char * dst) int ret = 0 ;while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) +dst; if ( ret 0 )ret = 1 ;return( ret ); 3,求 1000！的未尾有几个 0（用素数相乘的方法来做，如 72=2*2*2*3*3）; 求出 1-1000 里,能被 5 整除的数的个数 n1,能被 25 整除的数的个数 n2,能被 125 整除的数 的个数 n3, 能被 625 整除的数的个数 n4. 1000!末尾的零的个数=n1+n2+n3+n4; #include #define NUM 1000int find5(int num) int ret=0; while(num%5=0) num/=5; ret+; return ret; int main() int result