SIZEOF CONST 预处理题目:1. sizeof相关系列问题 a. 对于 struct s{char a;int b}; sizeof(s) = 8; 因为当结构体内元素长度都小于处理器位数（32位＝4字节）的时候，便以结构体中最长的数据元素为对齐条件,a 按 1 字节对齐，b 按 4 字节对齐，所以s默认对其参数为8 struct A{short a1;short a2;short a3};sizeof(A)=6; 原因同上，结构体按最长元素short(2字节对齐)。b. 对于 int a[200]; sizeof(a) = 200* sizeof(int) = 800; 对整个数组大小评测 int* a = new int[200]; sizeof(a) = 4; 对指针大小进行评测 char str[]="012345"; sizeof(str) = 7; str 是一个字符数组，数组最初大小未定，由具体值"012345"来决定，6*sizeof(char) = 6，还有隐含的"\0"，所以一共7位。 char str[]="s\n";sizeof(str) = 3; 回车"\n" 是一个字符，可以查看ASCII表。还有\r、\t等等字符c. 这种使用位域的也有，其中元素最大为1字节大小=8 bits，元素按照1字节进行对齐， sizeof(b) = 1 + 1(4 bits+2bits < 8 bits) + 1(3bits) = 3. struct b { char a:8; char b:4; char c:2; char d:3; }; 写出运行结果: union V { struct X { unsigned char s1:2; unsigned char s2:3; unsigned char s3:3; } x; unsigned char c; } v; v.c = 100; printf("%d", v.x.s3); 100 的2进制是1100100 去掉后面的5位余11放入x.s3中 结果:3d. 对于空的类进行评测 class A {}; sizeof(A) = 1;默认空类是有一个占位符的 对于虚函数 class A{ virtual test()}; class B:public A{};sizeof(A)=4;sizeof(B) =4 任何含有虚函数的类拥有一个vptr指针，用来指向虚函数表vtable。sizeof(vptr) = 4 class A{static int a;}; sizeof(A) = 1; 对于静态成员变量是分配在全局存储区的，所以A还是相当于空类。 class C:public virtual A {}; sizeof(C)=4; 对于虚拟继承的类拥有虚函数表，所以空类C含有vptr. e. 设有以下说明和定义： typedef union {long i; int k[5]; char c;} DATE; // sizeof(int)*5 = 20 struct data { int cat; DATE cow; double dog;} too; //4+20+8 = 32 DATE max; 则语句 printf("%d",sizeof(struct date)+sizeof(max));的执行结果是：52 对于union联合来说，取其中最大元素长度来做为联合大小。f. 使用malloc或者new 分配内存，void *pp = malloc(10); sizeof(p) = 4；跟指针一样,sizeof 只能测出静态数组的长度，无法检测动态分配的或外部数组大小h. 下面函数输出结果：对于char str[100]或者char str[] 参数都退化为char* str,这样的函数即使传入char s[10] 也是可以的 void Func(char str[100]) { printf("%d\n", sizeof(str)); } char s[10]; //函数对数组长度并没有检验 Func(s); 结果:sizeof(char*)=4 如何强制str为100位数组？ 可以如此声明 char (&str)[100] 理解顺序:1.str声明为一个引用 2.引用一个100元素数组 3. 数组元素每个为int大小 void Func(char (&str)[100]) { printf("%d\n", sizeof(str)); } char s[100]; Func(s); //这里必须给定100位长度char数组 结果：100*sizeof(char) = 1002. CONST 常见题目: a. const 与 #define有什么不同 答案: 1. const 常量有数据类型，而宏没有数据类型。编译器可以对const 常量进行类型检查，而对宏只进行字符替换没有类型检查。 2. 有些编译器可以对const常量进行调试，但不能对宏常量进行调试 3. const 可以用来修饰函数参数、函数返回值，C++还可以用来修饰函数，定义内中某个成员函数为常量函数3. 写一个标准宏MIN，这个宏输入两个参数并返回较小的一个 答案: #define MIN(A,B) ((A)<=(B) ? (A):(B)) 1. 宏是方便的产生嵌入代码的唯一方法。 2. 三重条件操作符对编译器来说可以产生比if-then-else更优化的代码。 3. 必须把宏中的参数用括号括起来 4. 内联函数和宏的差别是什么? 答案: 内联函数和普通函数相比可以加快程序运行的速度，因为不需要中断调用。编译时内联函数代码直接嵌入到目标代码中，而宏只是字符替换。内联函数要做类型检查，相对于宏更安全可靠。 inline只用于如下情况： 1. 一个函数被不断调用。 2. 函数只有简单的几行，且函数内不包含for、while、switch等语句. 5. const 符号常量；(1)const char *p(2)char const *p(3)char * const p说明上面三种描述的区别:1和2相同，如果const位于星号的左侧，则const就是用来修饰指针所指向的变量，即指针指向为常量，不能修改指针指向对象的内容如果const位于星号的右侧，const就是修饰指针本身，即指针本身是常量，不能修改指针的指向 2)写出二分查找的代码.int bfind(int* a,int len,int val){ int m = len/2; int l = 0; int r = len; while(l!=m && r!= m) { if(a[m] > val) { r = m; m = (m+l)/2; } else if(a[m] < val) { l = m; m = (m+r)/2; } else return m; } return -1; //没有找到}常见字符串面试题：1)写出在母串中查找子串出现次数的代码.int count1(char* str,char* s){ char* s1; char* s2; int count = 0; while(*str!='\0') { s1 = str; s2 = s; while(*s2 == *s1&&(*s2!='\0')&&(*s1!='\0')) { s2++; s1++; } if(*s2 == '\0') count++; str++; } return count;}2）查找第一个匹配子串位置,如果返回的是s1长度len1表示没有找到size_t find(char* s1,char* s2) { size_t i=0; size_t len1 = strlen(s1) size_t len2 = strlen(s2); if(len1-len2<0) return len1; for(;i<len1-len2;i++) { size_t m = i; for(size_t j=0;j<len2;j++) { if(s1[m]!=s2[j]) break; m++; } if(j==len) break; } return i<len1-len2?i:len1; }3)实现strcpy函数char *strcpy(char *destination, const char *source) { assert(destination!=NULL&&source!=NULL); char* target = destinaton; while(*destinaton++=*source++); return target ; } 出现次数相当频繁4)实现strcmp函数int strcmp11(char* l,char* r){ assert(l!=0&&r!=0); while(*l == *r &&*l != '\0') l++,r++; if(*l > *r) return 1; else if(*l == *r) return 0; return -1;}5) 实现字符串翻转void reserve(char* str){ assert(str != NULL); char * p1 = str; char * p2 = str-1; while(*++p2); //一般要求不能使用strlen p2 -= 1; while(p1<p2) { char c = *p1; *p1++ = *p2; *p2-- = c; }}6）、用指针的方法，将字符串“ABCD1234efgh”前后对调显示//不要用strlen求字符串长度，这样就没分了代码如下: char str123[] = "ABCD1234efgh"; char * p1 = str123; char * p2 = str123-1; while(*++p2); p2 -= 1; while(p1<p2) { char c = *p1; *p1++ = *p2; *p2-- = c; } 7) 给定字符串A和B,输出A和B中的最大公共子串。比如A="aocdfe" B="pmcdfa" 则输出"cdf"＃i nclude<stdio.h>＃i nclude<stdlib.h>＃i nclude<string.h> char *commanstring(char shortstring[], char longstring[]){ int i, j; char *substring=malloc(256); if(strstr(longstring, shortstring)!=NULL) //如果……，那么返回shortstring return shortstring; for(i=strlen(shortstring)-1;i>0; i--) //否则，开始循环计算 { for(j=0; j<=strlen(shortstring)-i; j++) { memcpy(substring, &shortstring[j], i); substring[i]='\0'; if(strstr(longstring, substring)!=NULL) return substring; } } return NULL;} main(){ char *str1=malloc(256); char *str2=malloc(256); char *comman=NULL; gets(str1); gets(str2); if(strlen(str1)>strlen(str2)) //将短的字符串放前面 comman=commanstring(str2, str1); else comman=commanstring(str1, str2); printf("the longest comman string is: %s\n", comman);} 8) 判断一个字符串是不是回文int IsReverseStr(char *str){ int i,j; int found=1; if(str==NULL) return -1; char* p = str-1; while(*++p!= '\0'); --p; while(*str==*p&&str<p) str++,p--; if(str < p) found = 0; return found;} 9)写函数完成内存的拷贝void* memcpy( void *dst, const void *src, unsigned int len ){ register char *d; register char *s; if (len == 0) return dst; if ( dst > src ) //考虑覆盖情况 { d = (char *)dst + len - 1; s = (char *)src + len - 1; while ( len >= 4 ) //循环展开，提高执行效率 { *d-- = *s--; *d-- = *s--; *d-- = *s--; *d-- = *s--; len -= 4; } while ( len-- ) { *d-- = *s--; } } else if ( dst < src ) { d = (char *)dst; s = (char *)src; while ( len >= 4 ) { *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; len -= 4; } while ( len-- ) { *d++ = *s++; } } return dst;} 10）写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)功能：在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数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 && *in < 58 ) { for(temp = in; *in > 47 && *in < 58 ; in++ ) count++; } else in++; if( maxlen < count ) { maxlen = count; count = 0; final = temp; } } for(int i = 0; i < maxlen; i++) { *out = *final; out++; final++; } *out = '\0'; return maxlen;} 11) 编写一个 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, ++cpSource; if(iTemp > iCount) iCount = iTemp, cpDest = cpTemp; if(!*cpSource) break; } ++cpSource; } return cpDest;} 排序算法:*7)写出快速排序或者某种排序算法代码快速排序:int partition(int* a,int l,int r){ int i=l-1,j=r,v=a[r]; while(1) { while(a[++i]<v); while(a[--j]>v) if(j<=i) break; if(i>=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); return i;}void qsort(int* a,int l,int r){ if(r>l) { int i = partition(a,l,r); qsort(a,l,i-1); qsort(a,i+1,r); }}有兴趣可以看看下面2个。一般面试不会要求的改进1:void qsort(int* a,int l,int r){ while(l<r) //防止过多递归 { int i = partition(a,l,r); qsort(a,l,i-1); l = i+1; }}改进2：void qsort(int* a,int l,int r){ while(l<r) { if(r-l<32) //防止分割恶化 { insertsort(a+l,r-l+1); //后面的插入排序 return; } int i = partition(a,l,r); qsort(a,l,i-1); l = i+1; }}冒泡排序: 出现次数相当频繁void buble(int *a,int n){ for(int i=0;i<n;i++) { for(int j=1;j<n-i;j++) { if(a[j]<a[j-1]) { int temp=a[j]; a[j] = a[j-1]; a[j-1] = temp; } } }}插入排序：void insertsort(int* a,int n){ int key; for(int j=1;j<n;j++) { key = a[j]; for(int i=j-1;i>=0&&a[i]>key;i--) { a[i+1] = a[i]; } a[i+1] = key; }}链表题目：1)将一个单链表逆序struct list_node{ list_node(int a,list_node* b):data(a),next(b) //这个为了测试方便 {} int data; list_node* next;};// 认为头节点存在，如果list类内函数不用判断头结点是否为空. 不是类内部函数得判断头结点 void reserve(list_node* phead) { list_node* p = phead->next; if(p == NULL || p->next == NULL) return; //只有头节点或一个节点 list_node* p1=p->next; p->next=NULL; while(p1!=NULL) { p = p1->next; p1->next = phead->next; phead->next = p1; p1 = p; }}测试程序： list lt; lt.phead = new list_node(0,0); lt.phead->next = new list_node(1,0); lt.phead->next->next = new list_node(2,0); lt.phead->next->next->next = new list_node(3,0); lt.reserve(); list_node * p = lt.phead; while(p) { cout<<p->data<<endl; p = p->next; }2)循环链表的节点对换和删除。//双向循环list_node* earse(list_node* node){ // if(node == rear) return node->next; //对于头节点可判断也可不判断。最好加上 list_node* next = node->next; next->prev = node->prev; node->prev->next = next; delete node; retrun next;}//单项循环list_node* earse(list_node* node){ // if(node == rear) return node->next; //对于头节点可判断也可不判断。最好加上 list_node* p = rear; while(p->next != node) p=p->next; p->next = node->next; delete node; retrun p->next;} 3) 有双向循环链表结点定义为： struct node { int data; struct node *front,*next; }; 有两个双向循环链表A，B，知道其头指针为：pHeadA,pHeadB，请写一函数将两链表中data值相同的结点删除 BOOL DeteleNode(Node *pHeader, DataType Value){ if (pHeader == NULL) return; BOOL bRet = FALSE; Node *pNode = pHead; while (pNode != NULL) { if (pNode->data == Value) { if (pNode->front == NULL) { pHeader = pNode->next; pHeader->front = NULL; } else { if (pNode->next != NULL) { pNode->next->front = pNode->front; } pNode->front->next = pNode->next; } Node *pNextNode = pNode->next; delete pNode; pNode = pNextNode; bRet = TRUE; / /不要break或return, 删除所有 } else { pNode = pNode->next; } } return bRet;} void DE(Node *pHeadA, Node *pHeadB){ if (pHeadA == NULL || pHeadB == NULL) { return; } Node *pNode = pHeadA; while (pNode != NULL) { if (DeteleNode(pHeadB, pNode->data)) { if (pNode->front == NULL) { pHeadA = pNode->next; pHeadA->front = NULL; } else { pNode->front->next = pNode->next; if (pNode->next != NULL) { pNode->next->front = pNode->front; } } Node *pNextNode = pNode->next; delete pNode; pNode = pNextNode; } else { pNode = pNode->next; } }} 4) 写出程序删除链表中的所有接点void del_all(node *head){ node *p; while(head!=NULL) { p=head->next; free(head); head=p; } cout<<"释放空间成功!"<<endl;}5 线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；可以参考 stl 函数 merge()Linklist *unio(Linklist *p,Linklist *q){ linklist *R,*pa,*qa,*ra; pa=p; qa=q; R=ra=p; while(pa->next!=NULL&&qa->next!=NULL) { if(pa->data>qa->data) { ra->next=qa; 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;}6 怎么判断链表中是否有环？bool CircleInList(Link* pHead){ if(pHead = = NULL || pHead->next = = NULL)//无节点或只有一个节点并且无自环 return (false); if(pHead->next = = pHead)//自环 return (true); Link *pTemp1 = pHead;//step 1 Link *pTemp = pHead->next;//step 2 while(pTemp != pTemp1 && pTemp != NULL && pTemp->next != NULL) { pTemp1 = pTemp1->next; pTemp = pTemp->next->next; } if(pTemp = = pTemp1) return (true); return (false);}常识题：4 static有什么用途？（请至少说明两种）1). 在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。 2). 在模块内（但在函数体外），一个被声明为静态的变量可以被模块内所用函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。 3). 在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的模块的本地范围内使用。 经常问5. 引用与指针有什么区别？1) 引用必须被初始化，不存在指向空值的引用，一个引用必须指向某个对象。指针不必立即初始化。2) 引用初始化以后不能改变使其指向其他对象，但可以修改其指向对象的内容。指针可以被改变指向其他的对象。3) 在使用引用之前不需要测试它是否为空，相反指针应该总被测试防止其为空。 4) 重载操作符必须使用引用才能完成串式操作6. 全局变量和局部变量在内存中是否有区别？如果有，是什么区别？全局变量储存在全局静态存储区，局部变量在堆栈static变量和static 函数各有什么特点？答:static变量：在程序运行期内一直有效，如果定义在函数外，则在编译单元内可见，如果在函数内，在在定义的block内可见；static函数：在编译单元内可见；static全局变量与普通的全局变量有什么区别？static全局变量只能在本模块中调用，不能在其他文件单元中被引用.而全局变量可以使用extern在任何地方引用static函数与普通函数有什么区别：static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝程序的局部变量存在于（堆栈）中，全局变量存在于（静态区 ）中，动态申请数据存在于（ 堆）中。16. 什么是平衡二叉树？左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于17. 什么构造函数不能声明为虚函数？答案: 虚函数采用一种虚调用的办法。虚调用是一种可以在只有部分信息的情况下工作的机制,特别允许我们调用一个只知道接口而不知道其准确对象类型的函数。但如果要创建一个对象势必要知道其准确类型因此构造函数不能为虚。 8. 冒泡排序算法的时间复杂度是什么 O(n^2) 快速排序 o(nlgn) 9. 写出float x 与“零值”比较的if语句。 if(x>0.000001&&x<-0.000001) 其实浮点0在内存中也是0,这个问题角度不太好。 10.进程间通信的方式有?进程间通信的方式有 共享内存， 管道 ，Socket ，消息队列等11. c和c++中的struct有什么不同？c和c++中struct的主要区别是c中的struct不可以含有成员函数，而c++中的struct可以。c++中struct和class的主要区别在于默认的存取权限不同，struct默认为public，而class默认为private12.纯虚函数如何定义？使用时应注意什么？virtual void f()=0;是接口，子类必须要实现 13.数组和链表的区别数组：数据顺序存储，固定大小连表：数据可以随机存储，大小可动态改变 14. 线程与进程的区别和联系? 线程是否具有相同的堆栈? dll是否有独立的堆栈?进程是死的，只是一些资源的集合，真正的程序执行都是线程来完成的，程序启动的时候操作系统就帮你创建了一个主线程。 每个线程有自己的堆栈。DLL中有没有独立的堆栈，这个问题不好回答，或者说这个问题本身是否有问题。因为DLL中的代码是被某些线程所执行，只有线程拥有堆栈，如果DLL中的代码是EXE中的线程所调用，那么这个时候是不是说这个DLL没有自己独立的堆栈？如果DLL中的代码是由DLL自 己创建的线程所执行，那么是不是说DLL有独立的堆栈？ 以上讲的是堆栈，如果对于堆来说，每个DLL有自己的堆，所以如果是从DLL中动态分配的内存，最好是从DLL中删除，如果你从DLL中分配内存，然后在EXE中，或者另外一个DLL中删除，很有可能导致程序崩溃 15. 一语句实现x是否为2的若干次幂的判断int i = 512;cout << boolalpha << ((i & (i - 1)) ? false : true) << endl; 对于2取余快速做法就是 &(2-1), & 相对于除法、取余指令要快很多，一般+ - * 等只消耗很少cpu周期（个位数）,而除法至少是100个cpu周期以上. cout<<boolalpha<<((i & 1) ? false : true) << endl; //这样更好一些. 如果求除4余数就是&3，除8余数是&7等等，注意只有2的倍数做除数才可以这么做。计算结果题目：1class A{ virtual void func1()； void func2();}Class B: class A{ void func1(){cout << "fun1 in class B" << endl;} virtual void func2(){cout << "fun2 in class B" << endl;}} A, A中的func1和B中的func2都是虚函数.B, A中的func1和B中的func2都不是虚函数.C, A中的func2是虚函数.，B中的func1不是虚函数.D, A中的func2不是虚函数，B中的func1是虚函数.答:A2 输出下面程序结果。 class A { public: virtual void print(void) { cout<<"A::print()"<<endl; } };class B:public A { public: virtual void print(void) { cout<<"B::print()"<<endl; }; }; class C:public B{public: virtual void print(void) { cout<<"C::print()"<<endl; }};void print(A a) { a.print(); } void main(void) { A a, *pa,*pb,*pc; B b; C c; pa=&a; pb=&b; pc=&c; a.print(); b.print(); c.print(); pa->print(); //多态 pb->print(); pc->print(); print(a); print(b); print(c); }答案:A::print()B::print()C::print()A::print()B::print()C::print()A::print()A::print()A::print() 3. 写出程序运行结果 int sum(int a){auto int c=0;static int b=3;c+=1;b+=2;return(a+b+c);} void main(){ int I; int a=2; for(I=0;I<5;I++) { printf("%d,", sum(a)); }}// static会保存上次结果，记住这一点，剩下的自己写输出：8,10,12,14,16, 4 求函数返回值，输入x=9999; int func （ x ）{ int countx = 0; while ( x ) { countx ++; x = x&(x-1); } return countx; } 结果呢？知道了这是统计9999的二进制数值中有多少个1的函数，且有9999＝9×1024＋512＋256＋159×1024中含有1的个数为2；512中含有1的个数为1；256中含有1的个数为1；15中含有1的个数为4；故共有1的个数为8，结果为8。1000 - 1 = 0111，正好是原数取反。这就是原理。用这种方法来求1的个数是很效率很高的。不必去一个一个地移位。循环次数最少。 算法题：1.用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。循环链表，用取余操作做//这样写感觉不是太好,置1表示被访问过。void joe(int n,int m){ int *a = new int[n]; int i=0; int pos=0; while(i<n) { int c=m; pos %= n; while(c) { c--; while(a[pos]==1) { pos++; pos %= n; } pos++; pos %= n; } a[pos-1] = 1; cout<<pos<<" "; i++; } delete[] a;}方法2：int Josephu(int n, int m){ int flag, i, j = 0; int *arr = (int *)malloc(n * sizeof(int)); for (i = 0; i < n; ++i) arr[i] = 1; for (i = 1; i < n; ++i) { flag = 0; while (flag < m) { if (j == n) j = 0; if (arr[j]) ++flag; ++j; } arr[j - 1] = 0; printf("第%4d个出局的人是：%4d号\n", i, j); } free(arr); return j;}int main(){ int n, m; scanf("%d%d", &n, &m); printf("最后胜利的是%d号！\n", Josephu(n, m)); system("pause"); return 0;}链表实现：＃i nclude <stdio.h>＃i nclude <malloc.h>typedef struct Node{ int index; struct Node *next;}JosephuNode;int Josephu(int n, int m){ int i, j; JosephuNode *head, *tail; head = tail = (JosephuNode *)malloc(sizeof(JosephuNode)); for (i = 1; i < n; ++i) { tail->index = i; tail->next = (JosephuNode *)malloc(sizeof(JosephuNode)); tail = tail->next; } tail->index = i; tail->next = head; for (i = 1; tail != head; ++i) { for (j = 1; j < m; ++j) { tail = head; head = head->next; } tail->next = head->next; printf("第%4d个出局的人是：%4d号\n", i, head->index); free(head); head = tail->next; } i = head->index; free(head); return i;}int main(){ int n, m; scanf("%d%d", &n, &m); printf("最后胜利的是%d号！\n", Josephu(n, m)); system("pause"); return 0;}2、有10亿个浮点数，求出其中最大的10000个 ,用了标准库的，不让用的话，只能自己写堆函数 vector<float> bigs(10000,0); vector<float>::iterator it; for(it=bigs.begin();it!=bigs.end();it++) { *it = (float)rand()/7; //数据都是用随机数模拟的 } cout<<bigs.size()<<endl; make_heap(bigs.begin(),bigs.end(),greater<float>() ); float ff; time_t t1,t2; time(&t1); for(int i=0;i<1000000000;i++) { ff = (float) rand()/7; if(ff>bigs[0]) { pop_heap(bigs.begin(),bigs.end(),greater<float>()); bigs.pop_back(); bigs.push_back(ff); push_heap(bigs.begin(),bigs.end(),greater<float>()); } } time(&t2); cout<<(long)(t2-t1)<<endl;如果要写堆排序可以用:swap是std内部函数可以交换数组中两个数, 这里省点事void fixdown(int*a,int k,int n){ while(2*k<=n) { int j=2*k; if(j<n&&a[j]<a[j+1]) ++j; if(a[j] < a[k] )break; swap(a[j],a[k]); k = j; }}void heapsort(int* a,int n){ int k = n/2; int* p = a-1; for(int i=k;i>0;i--) { fixdown(p,k,n); } while(n>0) { swap(p[n],p[1]); fixdown(p,1,--n); }}3 .在不用第三方参数的情况下，交换两个参数的值 感觉比较:( , bt 而且还是基础题。方法一: i=i+j; j=i-j; i=i-j;方法二： i^=j; j^=i; i^=j;方法三： a = a+b-(b=a)对于方法一、三 i=i+j 如果i、j是两个比较大的数，i+j可能越界，所以方法二更好一些 4）输出和为一个给定整数的所有组合例如n=55=1+4；5=2+3（相加的数不能重复）则输出1，4；2，3。 ＃i nclude <stdio.h> int main(void){ unsigned long int i,j,k; printf("please input the number\n"); scanf("%d",&i); if( i % 2 == 0) j = i / 2; else j = i / 2 + 1; printf("The result is \n"); for(k = 0; k < j; k++) printf("%d = %d + %d\n",i,k,i - k); return 0;} 5） 写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数 是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。函数接口为：int find_orderk(const int* narry,const int n,const int k) 要求算法复杂度不能是O(n^2）,应该 o(nlgn)吧 n^2 也太容易了冒泡排序都可以谢谢！可以先用快速排序进行排序，其中用另外一个进行地址查找代码如下，在VC++6.0运行通过。给分吧^-^ ，鄙视明明是个 partial_sort, 全排sort 效率差多了贴一份标准库代码，以后把堆排序所有函数不上。template<class _RanIt, class _Ty> inline void _Partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Ty *) { // order [First, _Last) up to _Mid, using operator< std::make_heap(_First, _Mid); for (_RanIt _Next = _Mid; _Next < _Last; ++_Next) if (*_Next < *_First) _Pop_heap(_First, _Mid, _Next, _Ty(*_Next), _Dist_type(_First)); // replace top with new largest std::sort_heap(_First, _Mid); }6)求1000！的未尾有几个0（用素数相乘的方法来做，如72=2*2*2*3*3）; 求出1->1000里,能被5整除的数的个数n1,能被25整除的数的个数n2,能被125整除的数的个数n3,能被625整除的数的个数n4.1000!末尾的零的个数=n1+n2+n3+n4;＃i nclude<stdio.h>#define NUM 1000 int find5(int num){ int ret=0; while(num%5==0) { num/=5; ret++; } return ret;}int main(){ int result=0; int i; for(i=5;i<=NUM;i+=5) { result+=find5(i); } printf(" the total zero number is %d\n",result); return 0;} 7). 编程实现：把十进制数(long型)分别以二进制和十六进制形式输出，不能使用printf系列库函数char* test3(long num) { char* buffer = (char*)malloc(11); buffer[0] = '0'; buffer[1] = 'x'; buffer[10] = '\0'; char* temp = buffer + 2; for (int i=0; i < 8; i++) { temp[i] = (char)(num<<4*i>>28); temp[i] = temp[i] >= 0 ? temp[i] : temp[i] + 16; temp[i] = temp[i] < 10 ? temp[i] + 48 : temp[i] + 55; }return buffer;} 8)输入N, 打印 N*N 矩阵比如 N = 3，打印： 螺旋矩阵1 2 38 9 47 6 5 N = 4，打印： 1 2 3 412 13 14 511 16 15 610 9 8 7解答：1 #define N 15int s[N][N];void main(){ int k = 0, i = 0, j = 0; int a = 1; for( ; k < (N+1)/2; k++ ) { while( j < N-k ) s[i][j++] = a++; i++; j--; while( i < N-k ) s[i++][j] = a++; i--; j--; while( j > k-1 ) s[i][j--] = a++; i--; j++; while( i > k ) s[i--][j] = a++; i++; j++; } for( i = 0; i < N; i++ ) { for( j = 0; j < N; j++ ) cout << s[i][j] << '\t'; cout << endl; }} 9) 斐波拉契数列递归实现的方法如下： int Funct( int n ){ if(n==0) return 1; if(n==1) return 1; retrurn Funct(n-1) + Funct(n-2);}如何不使用递归，来实现上述函数？解答：int Funct( int n ) // n 为非负整数{ int a=1; int b=1; int c; if(n==0 || n == 1) return 1; for(int i=1;i<n;i++) { c=a+b; a=b; b=c; } return b;}10)将一个数字字符串转换为数字."1234" -->1234int atoii(char* s){ assert(s!=NULL); int num = 0; int temp; while(*s>'0' && *s<'9') { num *= 10; num += *s-'0'; s++; } return num;}出现次数相当频繁 11). 编程实现：把十进制数(long型)分别以二进制和十六进制形式输出，不能使用printf系列库函数char* test3(long num) { char* buffer = (char*)malloc(11); buffer[0] = '0'; buffer[1] = 'x'; buffer[10] = '\0'; char* temp = buffer + 2; for (int i=0; i < 8; i++) { temp[i] = (char)(num<<4*i>>28); temp[i] = temp[i] >= 0 ? temp[i] : temp[i] + 16; temp[i] = temp[i] < 10 ? temp[i] + 48 : temp[i] + 55; } return buffer;} 12)实现任意长度的整数相加或者相乘功能。void bigadd(char* num,char* str,int len){ for(int i=len;i>0;i--) { num[i] += str[i]; int j = i; while(num[j]>=10) { num[j--] -= 10; num[j] += 1; } }}13、用递归算法判断数组a[N]是否为一个递增数组。递归的方法，记录当前最大的，并且判断当前的是否比这个还大，大则继续，否则返回false结束：bool fun( int a[], int n ){ if( n= =1 ) return true; if( n= =2 ) return a[n-1] >= a[n-2]; return fun( a,n-1) && ( a[n-1] >= a[n-2] );}14、运用四色定理，为N个局域举行配色，颜色为1、2、3、4四种，另有数组adj[][N]，如adj[i][j]=1则表示i区域与j区域相邻，数组color[N]，如color[i]=1,表示i区域的颜色为1号颜色。四色填充正在看图的程序，以后补一个15.给两个数组和他们的大小，还有一动态开辟的内存，求交集，把交集放到动态内存dongtai，并且返回交集个数long jiaoji(long* a[],long b[],long* alength,long blength,long* dongtai[])如果让用库，放入两个set 中，然后调用set_difference 函数。不让的话就先排序，然后依次比较了。16 象搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,请描述思想，写出算发（c语言），空间和时间复杂度.跟10亿浮点数的相同，使用堆做部分排序时间复杂度 Nlog10 。 空间？？ 用10的信息空间17.国内的一些帖吧，如baidu,有几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（c语言），空间和时间复杂度，每一个主题都有上亿的跟帖子，那baidu 就崩溃了。 天知道想问什么？？ 18.用两个栈实现一个队列的功能？要求给出算法和思路！设2个栈为A,B, 一开始均为空.入队:将新元素push入栈A;出队:(1)判断栈B是否为空；(2)如果不为空，则将栈A中所有元素依次pop出并push到栈B；(3)将栈B的栈顶元素pop出； 19 求组合数： 求n个数（1....n）中k个数的组合.... 如：combination(5,3) 要求输出：543，542，541，532，531，521，432，431，421，321，＃i nclude<stdio.h> int pop(int *);int push(int );void combination(int ,int ); int stack[3]={0};top=-1; int main(){ int n,m; printf("Input two numbers:\n"); while( (2!=scanf("%d%*c%d",&n,&m)) ) { fflush(stdin); 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(&temp)&&stack[0]==n) //当栈底元素弹出&&为可能取的最小值，循环退出 break; } else if( push(--temp)) { printf("%d%d%d ",stack[0],stack[1],stack[2]); pop(&temp); } }} int push(int i){ stack[++top]=i; if(top<2) return 0; else return 1;}int pop(int *i){ *i=stack[top--]; if(top>=0) return 0; else return 1;} 找错题：1.下面是C语言中两种if语句判断方式。请问哪种写法更好？为什么？ int n; if (n == 10) // 第一种判断方式 if (10 == n) // 第二种判断方式如果少了个=号,编译时就会报错,减少了出错的可能行,可以检测出是否少了=2.下面的代码有什么问题？void DoSomeThing(...){ char* p; ... p = malloc(1024); // 分配1K的空间 if (NULL == p) return; ... p = realloc(p, 2048); // 空间不够，重新分配到2K if (NULL == p) return; ...}A:p = malloc(1024); 应该写成： p = (char *) malloc(1024*sizeof(char)); 没有释放p的空间，造成内存泄漏。3.下面的代码有什么问题？并请给出正确的写法。void DoSomeThing(char* p){ char str[16]; int n; assert(NULL != p); sscanf(p, "%s%d", str, n); if (0 == strcmp(str, "something")) { ... }}A:sscanf(p, "%s%d", str, n); 这句该写成：scanf(p, "%s%d", str, &n); 如果 %s 在前必须指定长度，不然sscanf 不知何时取字符串结束 scanf(p)--------------------------------------------------------------------------4.下面代码有什么错误?Void test1() { char string[10]; char *str1="0123456789"; strcpy(string, str1); } 数组越界--------------------------------------------------------------------------5.下面代码有什么问题?Void test2() { char string[10], str1[10]; for(i=0; i<10;i++) { str1[i] ='a'; } strcpy(string, str1); } str1没有置字符串结束符'\0' , 数组越界--------------------------------------------------------------------------6.下面代码有什么问题?Void test3(char* str1) { char string[10]; if(strlen(str1)<=10) { strcpy(string, str1); } } ==数组越界==strcpy拷贝的结束标志是查找字符串中的\0 因此如果字符串中没有遇到\0的话 会一直复制，直到遇到\0,上面的123都因此产生越界的情况 建议使用 strncpy 和 memcpy--------------------------------------------------------------------------7.下面代码有什么问题?#define MAX_SRM 256 DSN get_SRM_no() { static int SRM_no; //是不是这里没赋初值？ int I; for(I=0;I<MAX_SRM;I++,SRM_no++) { SRM_no %= MAX_SRM; if(MY_SRM.state==IDLE) { break; } } if(I>=MAX_SRM) return (NULL_SRM); else return SRM_no; } // 网上有写：系统会初始化static int变量为0,但该值会一直保存,所谓的不可重入.. 扯淡.答案: 函数永远返回NULL_SRM ，因为最后i是等于MAX_SRM的，SRM_no 最大会是256 ，而不是255。连个都是后++产生的问题。8. 下面代码有什么问题?void GetMemory(char *p){ p=(char *)malloc(100);}void Test(void){ char *str=NULL; GetMemory=(str); strcpy(str,"hello world"); printf(str);}A:错误--参数的值改变后，不会传回,GetMemory并不能传递动态内存，Test函数中的 str一直都是 NULL。strcpy(str, "hello world");将使程序崩溃。9 下面这个程序执行后会有什么错误或者效果: #define MAX 255 int main(){ unsigned char A[MAX]; //i被定义为unsigned char for (unsigned char i=0;i<=MAX;i++) A[i]=i;}解答：死循环加数组越界访问（C/C++不进行数组越界检查）MAX=255 数组A的下标范围为:0..MAX-1,这是其一..其二.当i循环到255时,循环内执行: A[255]=255;这句本身没有问题..但是返回for (i=0;i<=MAX;i++)语句时,由于unsigned char的取值范围在(0..255),i++以后i又为0了..无限循环下去. 10、请找出下面代码中的所以错误说明：以下代码是把一个字符串倒序，如“abcd”倒序后变为“dcba” 1、＃i nclude"string.h"2、main()3、{4、 char*src="hello,world";5、 char* dest=NULL;6、 int len=strlen(src);7、 dest=(char*)malloc(len);8、 char* d=dest;9、 char* s=src[len];10、 while(len--!=0) 11、 d++=s--;12、 printf("%s",dest);13、 return 0;14、} 答：方法1：int main(){char* src = "hello,world";int len = strlen(src);char* dest = (char*)malloc(len+1);//要为\0分配一个空间char* d = dest;char* s = &src[len-1];//指向最后一个字符while( len-- != 0 )*d++=*s--;*d = 0;//尾部要加\0printf("%s\n",dest);free(dest);// 使用完，应当释放空间，以免造成内存汇泄露return 0;} 11.找错题: 1.请问下面程序有什么错误? int a[60][250][1000],i,j,k; for(k=0;k<=1000;k++) for(j=0;j<250;j++) for(i=0;i<60;i++) a[i][j][k]=0;把循环语句内外换一下, 造成大量的内存页失效
评论