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!='\0')
{
s1 = str;
s2 = s;
while(*s2 == *s1&&(*s2!='\0')&&(*s1!='0'))
{
s2++;
s1++;
}
if(*s2 == '\0')
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 != '\0') 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" -->1234
int 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. 什么是平衡二叉树？
左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于1
17. 什么函数不能声明为虚函数？
constructor
13. 冒泡排序算法的时间复杂度是什么？
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 = 20
struct data { int cat; DATE cow; double dog;} too; //4+20+8 = 32
DATE 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;