1)sizeof相关系列问题, const相关系列问题a. 对于 struct s{char a;int b} sizeof(s) = 8 因为内存对齐 b. 对于struct s{int a;char b} sizeof(s) = 5 这里不需要内存对齐，对齐只向上不向下，这种考得少c. 对于 int a[200] sizeof(a) = 200* sizeof(int) = 800 对整个数组评测 ，int* a = new int[200] , sizeof(a) = 4 对指针评测d. 这种使用位域的也有，从上到下最多相加不大于8便占1个位置， bits = 1 + 1(4+2 < 8) + 1(3) = 3. 其中元素最大为1个char 大小 8 位struct bits{ char a:8; char b:4; char c:2; char d:3;};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; //没有找到}3)写出在母串中查找子串出现次数的代码.int count1(char* str,char* s){ char* s1; char* s2; int count = 0; while(*str!='') { s1 = str; s2 = s; while(*s2 == *s1&&(*s2!='')&&(*s1!='0')) { s2++; s1++; } if(*s2 == '') count++; str++; } return count;}查找第一个匹配子串位置,如果返回的是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; }*4)写出快速排序或者某种排序算法代码快速排序: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(l>=r) return; int i = partition(a,l,r); qsort(a,l,i-1); qsort(a,i+1,r);}冒泡排序: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; }}出现次数相当频繁5)写出查找从一个集合中输出所有子集合的算法.????*6)实现strcpy函数char *strcpy(char *destination, const char *source) { assert(destination!=NULL&&source!=NULL);char* target = destinaton;while(*destinaton++=*source++); return target ; } 出现次数相当频繁*7)实现strcmp函数int strcmp11(char* l,char* r){ assert(l!=0&&r!=0); while(*l == *r &&*l != '') l++,r++; if(*l > *r) return 1; else if(*l == *r) return 0; return -1;}//实现字符串翻转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; }}出现次数相当频繁8)将一个单链表逆序struct list_node{ list_node(int a,list_node* b):data(a),next(b) //这个为了测试方便 {} int data; list_node* next;}; 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; }9)循环链表的节点对换和删除。//双向循环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;}*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)实现任意长度的整数相加或者相乘功能。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; } }}*12)写函数完成内存的拷贝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;}出现次数相当频繁13 static有什么用途？（请至少说明两种）1.限制变量的作用域2.设置变量的存储域，只在定于变量的源文件内可见经常问14. 引用与指针有什么区别？1) 引用必须被初始化，指针不必。2) 引用初始化以后不能被改变，指针可以改变所指的对象。3) 不存在指向空值的引用，但是存在指向空值的指针。4) 重载操作符使用引用可以完成串试操作经常问15. 全局变量和局部变量在内存中是否有区别？如果有，是什么区别？全局变量储存在全局静态存储区，局部变量在堆栈16. 什么是平衡二叉树？左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于117. 什么函数不能声明为虚函数？constructor13. 冒泡排序算法的时间复杂度是什么？O(n^2)18. 写出float x 与“零值”比较的if语句。 if(x>0.000001&&x<-0.000001) 这个都够古董的, 恐怕是8086以前的事情吧. 汇编早都可以用一条指令比较了. 既然想考精度，就换个不是0的，比如0.00002 ， if(x-0.00002>0.000001&&x-0.0002<-0.000001) 19.用户输入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++; }}20、设有以下说明和定义：typedef union {long i; int k[5]; char c;} DATE; // sizeof(int)*5 = 20struct data { int cat; DATE cow; double dog;} too; //4+20+8 = 32DATE max;则语句 printf("%d",sizeof(struct date)+sizeof(max));的执行结果是：___52____21、用指针的方法，将字符串“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; }22、有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;发表于 @ 2006年05月20日 08:13:00 | 评论 (0) C/C++常见问题希望这个贴子能给正在找工作的朋友一点帮助.如果代码里面有 while(*p) 判断字符串结束的，要用 *p!='' 代替。1)sizeof相关系列问题, const相关系列问题a. 对于 struct s{char a;int b} sizeof(s) = 8 因为内存对齐 b. 对于struct s{int a;char b} sizeof(s) = 5 这里不需要内存对齐，对齐只向上不向下，这种考得少c. 对于 int a[200] sizeof(a) = 200* sizeof(int) = 800 对整个数组评测 ，int* a = new int[200] , sizeof(a) = 4 对指针评测d. 这种使用位域的也有，从上到下最多相加不大于8便占1个位置， bits = 1 + 1(4+2 < 8) + 1(3) = 3. 其中元素最大为1个char 大小 8 位struct bits{ char a:8; char b:4; char c:2; char d:3;};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; //没有找到}3)写出在母串中查找子串出现次数的代码.int count1(char* str,char* s){ char* s1; char* s2; int count = 0; while(*str!='') { s1 = str; s2 = s; while(*s2 == *s1&&(*s2!='')&&(*s1!='0')) { s2++; s1++; } if(*s2 == '') count++; str++; } return count;}查找第一个匹配子串位置,如果返回的是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; }*4)写出快速排序或者某种排序算法代码快速排序: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(l>=r) return; int i = partition(a,l,r); qsort(a,l,i-1); qsort(a,i+1,r);}冒泡排序: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; }}出现次数相当频繁5)写出查找从一个集合中输出所有子集合的算法.????*6)实现strcpy函数char *strcpy(char *destination, const char *source) { assert(destination!=NULL&&source!=NULL);char* target = destinaton;while(*destinaton++=*source++); return target ; } 出现次数相当频繁*7)实现strcmp函数int strcmp11(char* l,char* r){ assert(l!=0&&r!=0); while(*l == *r &&*l != '') l++,r++; if(*l > *r) return 1; else if(*l == *r) return 0; return -1;}//实现字符串翻转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; }}出现次数相当频繁8)将一个单链表逆序struct list_node{ list_node(int a,list_node* b):data(a),next(b) //这个为了测试方便 {} int data; list_node* next;}; 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; }9)循环链表的节点对换和删除。//双向循环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;}*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)实现任意长度的整数相加或者相乘功能。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; } }}*12)写函数完成内存的拷贝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;}出现次数相当频繁13 static有什么用途？（请至少说明两种）1.限制变量的作用域2.设置变量的存储域，只在定于变量的源文件内可见经常问14. 引用与指针有什么区别？1) 引用必须被初始化，指针不必。2) 引用初始化以后不能被改变，指针可以改变所指的对象。3) 不存在指向空值的引用，但是存在指向空值的指针。4) 重载操作符使用引用可以完成串试操作经常问15. 全局变量和局部变量在内存中是否有区别？如果有，是什么区别？全局变量储存在全局静态存储区，局部变量在堆栈16. 什么是平衡二叉树？左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于117. 什么函数不能声明为虚函数？constructor13. 冒泡排序算法的时间复杂度是什么？O(n^2)18. 写出float x 与“零值”比较的if语句。 if(x>0.000001&&x<-0.000001) 这个都够古董的, 恐怕是8086以前的事情吧. 汇编早都可以用一条指令比较了. 既然想考精度，就换个不是0的，比如0.00002 ， if(x-0.00002>0.000001&&x-0.0002<-0.000001) 19.用户输入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++; }}20、设有以下说明和定义：typedef union {long i; int k[5]; char c;} DATE; // sizeof(int)*5 = 20struct data { int cat; DATE cow; double dog;} too; //4+20+8 = 32DATE max;则语句 printf("%d",sizeof(struct date)+sizeof(max));的执行结果是：___52____21、用指针的方法，将字符串“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; }22、有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;
