SIZEOF CONST 预处理题目:
1. sizeof相关系列问题
b. 对于 int a[200]; sizeof(a) = 200* sizeof(int) = 800; 对整个数组大小评测
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中 结果:3
d. 对于空的类进行评测 class A {}; sizeof(A) = 1;默认空类是有一个占位符的
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
f. 使用malloc或者new 分配内存，void *pp = malloc(10); sizeof(p) = 4；跟指针一样,sizeof 只能测出静态数组的长度，无法检测动态分配的或外部数组大小
h. 下面函数输出结果：对于char str[100]或者char str[] 参数都退化为char* str,这样的函数即使传入char s[10] 也是可以的
{
printf("%d\n", sizeof(str));
}
char s[10]; //函数对数组长度并没有检验
Func(s);
结果:sizeof(char*)=4
{
printf("%d\n", sizeof(str));
}
char s[100];
Func(s); //这里必须给定100位长度char数组
结果：100*sizeof(char) = 100
2. CONST 常见题目:
3. 写一个标准宏MIN，这个宏输入两个参数并返回较小的一个
(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;
}
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所指的值为123456789
int 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;
}
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;
}
}
}
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) 在使用引用之前不需要测试它是否为空，相反指针应该总被测试防止其为空。
6. 全局变量和局部变量在内存中是否有区别？如果有，是什么区别？
全局变量储存在全局静态存储区，局部变量在堆栈
static变量和static 函数各有什么特点？
答:static变量：在程序运行期内一直有效，如果定义在函数外，则在编译单元内可见，如果在函数内，在在定义的block内可见；static函数：在编译单元内可见；
static全局变量与普通的全局变量有什么区别？
static全局变量只能在本模块中调用，不能在其他文件单元中被引用.而全局变量可以使用extern在任何地方引用
static函数与普通函数有什么区别：
static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝
程序的局部变量存在于（堆栈）中，全局变量存在于（静态区 ）中，动态申请数据存在于（ 堆）中。
16. 什么是平衡二叉树？
左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于1
7. 什么构造函数不能声明为虚函数？
答案: 虚函数采用一种虚调用的办法。虚调用是一种可以在只有部分信息的情况下工作的机制,特别允许我们调用一个只知道接口而不知道其准确对象类型的函数。但如果要创建一个对象势必要知道其准确类型因此构造函数不能为虚。
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默认为private
12.纯虚函数如何定义？使用时应注意什么？
virtual void f()=0;
是接口，子类必须要实现
13.数组和链表的区别
数组：数据顺序存储，固定大小
连表：数据可以随机存储，大小可动态改变
进程是死的，只是一些资源的集合，真正的程序执行都是线程来完成的，程序启动的时候操作系统就帮你创建了一个主线程。
DLL中有没有独立的堆栈，这个问题不好回答，或者说这个问题本身是否有问题。因为DLL中的代码是被某些线程所执行，只有线程拥有堆栈，如果DLL中的代码是EXE中的线程所调用，那么这个时候是不是说这个DLL没有自己独立的堆栈？如果DLL中的代码是由DLL自 己创建的线程所执行，那么是不是说DLL有独立的堆栈？
以上讲的是堆栈，如果对于堆来说，每个DLL有自己的堆，所以如果是从DLL中动态分配的内存，最好是从DLL中删除，如果你从DLL中分配内存，然后在EXE中，或者另外一个DLL中删除，很有可能导致程序崩溃
int i = 512;
cout << boolalpha << ((i & (i - 1)) ? false : true) << endl;
计算结果题目：
1
class 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是虚函数.
答:A
2 输出下面程序结果。
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＋15
9×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 而且还是基础题。
方法一:
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=5
5=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 3
8 9 4
7 6 5
N = 4，打印：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
解答：
1 #define N 15
int 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;
}
}
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" -->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). 编程实现：把十进制数(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)
{
{
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;//尾部要加\0
printf("%s\n",dest);
free(dest);// 使用完，应当释放空间，以免造成内存汇泄露
return 0;
}
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;
把循环语句内外换一下, 造成大量的内存页失效
评论