CC++面试题（一）

1.求下面函数的返回值(微软) ———统计1的个数

int func(int x) { int countx = 0; while(x) { countx++; x = x&(x-1); } return countx; } 假定x = 9999 10011100001111 答案: 8

思路: 将x转化为2进制，看含有的1的个数。 注: 每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的那个1)变为0。（假设该位为第k位，减1后，该位后面全部变成1，但是由于该位是最右边的1了，所以x的第k位后面全是0，而x-1的第k位是0，从1到k-1位全是1，按位与的结果自然就是第k位和1~k-1位都变成0。） 所以该表达式的用途之一：

１：将最低的为1的位变成0，这个解释理解起来不难。

该表达式的第二个用途为： ２：当x为奇数的时候,x=x&(x-1)它的值相当于x=x-1;一样的效果；当x为2的N次幂时,结果为0，这可以用来快速判断一个数是否为２的ｎ次方。

2.判断一个数(x)是否是2的n次方

int func(int x) { if( (x&(x-1)) == 0 ) { return 1; } else { return 0; } } int main() { int x = 8; printf("%d\n", func(x)); return 0; }

注: (1) 如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位为0，然后利用上面的思路就很容易想通了。

指针与数组对比

字符串逆序

char * reverse(char *str) { if (str == NULL ) { return NULL; } char *end = str; while (*end) { end++; } end--; char *ptr = (char*)malloc(sizeof(char)*(strlen(str)+1)); if (ptr == NULL) { printf("malloc err!\n"); exit(1); } char *begin = ptr; while(str <= end) { *ptr++ = *end--; } *ptr = '\0'; printf("%s\n",begin); return begin; }

3.字符串逆序（不借助额外分配的内存）

void swap(char *ch1,char *ch2) { char tmp = *ch1; *ch1 = *ch2; *ch2 =tmp; } char* Reverse1(char* s) { // p指向字符串头部 char* begin = s; // q指向字符串尾部 char* end = s; while (*end) ++end; end--; #if 0 // 交换并移动指针，直到begin和end交叉 while(begin < end) { char tmp = *begin ; *begin++ = *end; *end-- = tmp ; //swap(begin,end); 用指针操作的时候用char *参数 //begin++; //end--; } #else //不借助临时变量 这种只适合于纯字符的字符串（没有空格符号等） while(begin < end) { *end = *end ^ *begin; *begin = *end ^ *begin; *end = *end-- ^ *begin++; } #endif return s; }

指针与数组的区别

//递归调用 void swap(char &ch1,char &ch2) { char tmp = ch1; ch1 = ch2; ch2 =tmp; } void reverse(char s[], int left, int right) { if (left >= right) { return; } char ch = s[left]; s[left] = s[right]; s[right] = ch; //swap(s[left],s[right]); 用元素的值操作的时候可以用引用 reverse(s, left + 1, right - 1); } //调用方法：reverse(s,0,strlen(s)-1); //非递归调用 void reverse(char s[], int left, int right) { while (left <= right) { char ch; ch = s[right]; s[right--] = s[left]; s[left++] = ch; } }

4按单词逆序

给定一个字符串，按单词将该字符串逆序，比如给定”This is a sentence”，则输出是”sentence a is This”，为了简化问题，字符串中不包含标点符号。

分两步 1 先按单词逆序得到”sihT si a ecnetnes” 2 再整个句子逆序得到”sentence a is This”

对于步骤一，关键是如何确定单词，这里以空格为单词的分界。当找到一个单词后，就可以使用上面讲过的方法将这个单词进行逆序，当所有的单词都逆序以后，将整个句子看做一个整体（即一个大的包含空格的单词）再逆序一次即可，如下图所示，第一行是原始字符换，第二行是按单词逆序后的字符串，最后一行是按整个句子逆序后的字符串。

void reverse_word(char *begin, char *end) { while (begin <= end) { char ch = *begin; *begin++ = *end; *end-- = ch; } } char *reverse_sentence(char *s) { char *begin = s; char *end = s; while (*end != '\0') { if (*end == ' ') { reverse_word(begin, end - 1); end++; begin = end; } else { end++; } } reverse_word(begin, end - 1);//对最后一个单词逆序 reverse_word(s, end - 1);//将整个字符串逆序 return s; }

5.编写一个类string 的构造，析构和赋值函数

class string() { public: string(c6nst char *str= NULL); string(const string &other); string& operator=(const string &other); ~string(void); private: char * m_data; } //有参构造 string::string(const char *str) { if( str == NULL) { //对于NULL字符串只需要一个‘\0’标志 m_data = new char[1]; if(m_data ==NULL) { cout<<"new err!\n"<<endl; exit(1); } m_data[0]='\0'; } else { int length = strlen(str); m_data = new char[length +1]; if(m_data == NULL) { cout<<"new char err!"<<endl; exit(1); } strcpy(m_data,str); } } //拷贝构造 string ::string(const string &other) { cout<<"copy !"<<endl; m_data = new char[strlen(other.m_data) + 1]; if(m_data == NULL) { cout<<"new char err!"<<endl; exit(1); } strcpy(m_data,other.m_data); } //重载= string::string & operator=(const string &other) { //输入参数const 型 if(this == &other)//如果对象与other是同一个对象，this 指向对象的地址&other 也是指向对象的地址 { return *this;//直接返回本身 } delete[] m_data;// 释放原来的内存资源 int length = strlen(other.m_data); m_data = new char[length +1]; if(m_data == NULL) { cout<<"new char err!"<<endl; exit(1); } strcpy(m_data,other.m_data); return *this;//返回对象的引用 } //析构 string::~string() { //如果m_data不为空，则释放内存 if(m_data != NULL) { delete [] m_data; m_data = NULL; } } int main() { string a("hello");//调用有参构造 string b(a);//调用拷贝构造 strng c("world"); c=b;//调用赋值 = string d; system("pause"); return 0; }

6.改错题

只能在原来的基础上增加代码，不能删除代码

void foo(int age,char *b) { b= (char *)malloc(64); sprintf(b,"your age is %d",age); } int main() { char*f; foo(24,f); printf("%s\n",f); return 0; } /*修改为：------------------------------*/ void foo(int age,char **b) { *b= (char **)malloc(64); sprintf(b,"your age is %d",age); } int main() { char *f; foo(24,&f); printf("%s\n",f); return 0; }

7.多态实现,举例分析

class shape { public: virtual double area() = 0; }; class circle:public shape { public: circle(double r) { this->r =r; } virtual double area() { return r*r*3.14; } private: double r; }; class triangle:public shape { public: triangle(double x,double y) { this->x = x; this->y =y; } virtual double area() { return x*y/2; } private: double x,y; }; class rectangle:public shape { public: rectangle(double x,double y) { this->x = x; this->y = y; } virtual double area() { return x*y; } private: double x,y; }; int main() { circle c(0.5); rectangle r(2.5,3.8); triangle t(2.4,4.2); shape *base; base = &c; cout<<base->area()<<endl; base= &r; cout<<base->area()<<endl; base = &c; cout<<base->area()<<endl; system("pause"); return 0; }

8.链表的逆置

typedef int DataType; //类型定义 typedef struct node{ //单链表定义 DataType data; struct node* next; }LinkedNode,*LinkList; void ReverseList(LinkList& ListHead) { cout<<"Begin to Reverse the List"<<endl; if( (NULL==ListHead)||(NULL==ListHead->next) )return ; //边界检测 LinkedNode* pPre=ListHead; //先前指针 LinkedNode* pCur=pPre->next; //当前指针 LinkedNode* pNext=NULL; //后继指针 while(pCur!=NULL) { pNext=pCur->next; pCur->next=pPre; pPre=pCur; pCur=pNext; } ListHead->next=NULL; ListHead=pPre; //记录下新的头结点 }

9.文件操作，从input.txt文件中读入，将每一个英文字母加上数值1，并且每5个英文字母后插入一个字符‘ \0’,输出到第二个文件mem.txt中。

char buf[1024]={0}; char change_ch(char&ch) { if(ch >='a' && ch <'z') { return (ch+1); } else { return ch; } } void read_file() { FILE *fp = NULL; const char *file_name = "C:/Users/Administrator/Desktop/input.txt"; fopen_s(&fp,file_name,"r"); char ch; int count = 0; char *begin = buf; while (!feof(fp)) { ch = fgetc(fp); if(ch == ' ') { *begin = ' '; begin++; continue; } if (count == 5) { *begin = change_ch(ch); begin++; *begin = '\\'; begin++; *begin = '0'; count = 0; begin++; continue; } *begin = change_ch; begin++; count++; } *begin = 0; fclose(fp); } void write_file() { FILE *fp = NULL; const char *path_name = "C:/Users/Administrator/Desktop/mem.txt"; fopen_s(&fp, path_name, "w"); int len = strlen(buf); int i = 0; for (i = 0; i < len ; i++) { fputc(buf[i],fp); } fclose(fp); }