c++面试编程题

常用经典编程例子一个链表的结点结构struct Nodeint data ;Node *next ;typedef struct Node Node ;(1)已知链表的头结点head,写一个函数把这个链表逆序 ( Intel)Node * ReverseList(Node *head) /链表逆序if ( head = NULL | head-next = NULL )return head;Node *p1 = head ;Node *p2 = p1-next ;Node *p3 = p2-next ;p1-next = NULL ;while ( p3 != NULL )p2-next = p1 ;p1 = p2 ;p2 = p3 ;p3 = p3-next ;p2-next = p1 ;head = p2 ;return head ;(2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小相同）Node * Merge(Node *head1 , Node *head2)if ( head1 = NULL)return head2 ;if ( head2 = NULL)return head1 ;Node *head = NULL ;Node *p1 = NULL;Node *p2 = NULL;if ( head1-data data )head = head1 ;p1 = head1-next;p2 = head2 ;elsehead = head2 ;p2 = head2-next ;p1 = head1 ;Node *pcurrent = head ;while ( p1 != NULL & p2 != NULL)if ( p1-data data )pcurrent-next = p1 ;pcurrent = p1 ;p1 = p1-next ;elsepcurrent-next = p2 ;pcurrent = p2 ;p2 = p2-next ;if ( p1 != NULL )pcurrent-next = p1 ;if ( p2 != NULL )pcurrent-next = p2 ;return head ;(3)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。 (Autodesk)答案：Node * MergeRecursive(Node *head1 , Node *head2)if ( head1 = NULL )return head2 ;if ( head2 = NULL)return head1 ;Node *head = NULL ;if ( head1-data data )head = head1 ;head-next = MergeRecursive(head1-next,head2);elsehead = head2 ;head-next = MergeRecursive(head1,head2-next);return head ;写一个函数找出一个整数数组中，第二大的数 （microsoft）答案：const int MINNUMBER = -32767 ;int find_sec_max( int data , int count)int maxnumber = data0 ;int sec_max = MINNUMBER ;for ( int i = 1 ; i maxnumber )sec_max = maxnumber ;maxnumber = datai ;elseif ( datai sec_max )sec_max = datai ;return sec_max ;编程实现单链表的插入Node* InsertNode(Node *Head, int num) Node *newNode = new Node;newNode-data = num;if(!Head)/此时为空链表newNode-next = NULL;return newNode;Node *p = Head;Node *q = NULL;/q指向p结点之前的结点while(p)/此时寻找位置if(p-data next;else/此时找到了位置break;if(p = Head)/插入到头结点之前newNode-next = Head;Head = newNode;else if(!p)/插入到尾结点之后,此时q指向尾结点q-next = newNode;newNode-next = NULL;else/插入到p结点和q结点之间newNode-next = q-next;q-next = newNode;return Head;编程实现双链表删除结点（注意它和单链表删除结点的情况有所不同）Node* DoubleLink_DelNode(Node *Head, int num)Node *p = Head;if(!p)return NULL;while(p)if(num != p-data) p = p-next;elsebreak;if(!p)/没有找到要删除的结点return NULL;elseif(p = Head)/此时删除的是头结点Head = Head-next; delete p;else if(p-next)/此时删除的是中间结点p-prev-next = p-next;p-next-prev = p-prev;delete p;else/删除的是尾结点p-prev-next = NULL;delete p; return Head;编程实现双链表的插入Node* DoubleLink_InsertNode(Node *Head, int num)Node *newNode = new Node;/初始化产生一个新结点newNode-data = num;newNode-prev = NULL;newNode-next = NULL;Node *p = Head;Node *q = NULL;while(p)if(p-data next;elsebreak;if(p = Head)/此时是在头结点之前进行插入newNode-next = p;p-prev = newNode;Head = newNode;else if(!p)/在尾结点之后进行插入q-next = newNode;newNode-prev = q;else/在中间进行插入p-prev-next = newNode;newNode-prev = p-prev;newNode-next = p;p-prev = newNode; return Head;如何证明一个表是循环链表link * p,*q; p=head; q=p-next; while(q&q-next&p!=q)/q or q-next =NULL时无环， q=q时有环 p=p-next; q=q-next-next; if(p=q) couthave ring; else coutnext; while(fast!=NULL & fast-next!=NULL) low=low-next; fast=fast-next-next; if(low=fast) return true; return false;实现队列的出队与入队/数据入队列Node *EnQueue(Node *head, Node *tail, int data)/创建一个新结点Node *p = new Node;p-data = data;p-next = NULL;if(head = NULL)/此时为空队列 head = p;*tail = p;else(*tail)-next = p;*tail = p;return head;/删除头结点Node* DeQueue(Node *head) if(!head)/头结点为空return NULL;elseNode *p = head;head = head-next;delete p;return head;String 的具体实现 已知String类定义如下：class Stringpublic:String(const char *str = NULL); / 通用构造函数String(const String &another); / 拷贝构造函数 String(); / 析构函数String & operater =(const String &rhs); / 赋值函数private:char *m_data; / 用于保存字符串;尝试写出类的成员函数实现。答案：String:String(const char *str)if ( str = NULL ) /strlen在参数为NULL时会抛异常才会有这步判断m_data = new char1 ;m_data0 = 0 ;elsem_data = new charstrlen(str) + 1;strcpy(m_data,str); String:String(const String &another)m_data = new charstrlen(another.m_data) + 1;strcpy(m_data,other.m_data);String& String:operator =(const String &rhs)if ( this = &rhs)return *this ;delete m_data; /删除原来的数据，新开一块内存m_data = new charstrlen(rhs.m_data) + 1;strcpy(m_data,rhs.m_data);return *this ;String:String()delete m_data ;判断字符串是否为回文bool IsSymmetry(const char* p)assert(p!=NULL);const char* q=p;int len=0;while(*q+!=0)len+;bool bSign=true;q=p+len-1;if (0len)for (int i=0;ilen/2;i+)if(*p+!=*q-) bSign=false;break;if(bSign=true)printf(Yes!n);elseprintf(No!n);return bSign;整数转换成字符串itoa函数的实现 1 #include stdafx.h 2 #include 3 using namespace std; 4 void itoaTest(int num,char str ) 5 6 int sign = num,i = 0,j = 0; 7 char temp11; 8 if(sign0); 18 if(sign=0) 25 26 strj = tempi; 27 j+; 28 i-; 29 30 strj = 0; 31 编程实现字符串转化为整型，不用atoi32 string str;33 int sum = 0;34 cin str;35 for(int i = 0; i str.size(); i+)36 37 sum = sum * 10 + stri - 0;38 39 cout sum endl;请写出一个函数来模拟c+中的strstr函数：该函数的返回值是主传中字符子串的位置以后的所有字符，请不要使用任何c程序已有的函数40 string LeftSting(const string &Srcstr, const string &Substr)41 42 string Results();43 int i = 0;44 while(i Srcstr.size()45 46 int j = i;47 int k = 0;48 while(k Substr.size()49 50 if(Srcstrj = Substrk)51 52 j+;53 k+;54 55 else56 break;57 58 if(k = Substr.size()/找到了子串59 60 for(int t = i; t Srcstr.size(); t+)61 Results += Srcstrt;62 break;63 64 else if(k = 0)/此时第一个不是匹配的65 i+;66 else/此时已经匹配了k个字符67 i += k;68 69 return Results;70 字符串输出35.22简单应用题请编写一个函数display()，该函数要求用户先输入一字符串，然后在屏幕上再输出该字符串（假设该字符串长度小于100）。注意：部分源程序已存在文件test35_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数display()的花括号中填写若干语句。如输入abc，输出结果如下：please input string:abcabcPress any key to continue文件test35_2.cpp的内容如下：#include #include void display()void main()coutplease input string:endl;display();【答案】void display()char str100,ch;int i=0;while (ch=getche()!=r)stri=ch;i+;stri=0;coutendlstrendl;2.2字符串翻转16.22简单应用题请编写一个函数void fun(char ss)，该函数将字符串ss翻转，如ss为123abc则翻转后为cba321。注意：用数组方式及for循环来实现该函数。注意：部分源程序已存在文件test16_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数fun的花括号中填写若干语句。文件test16_2.cpp的内容如下：#include#includevoid fun(char ss);void main()char s80; couts;fun(s);cout逆序后的字符串:sendl;void fun(char ss)【答案】void fun(char ss)int n=strlen(ss);for(int i=0;i(n/2); i+)char c=ssi;ssi=ssn-1-i;ssn-1-i=c;2.3字符串大小写转换21.22简单应用题请编写一个函数char *change(char instr)，将输入字符串中的所有小写字母转换为大写字母输出。要求使用for循环实现。如输入jinfeiteng，则输出结果是JINFEITENG。注意：部分源程序已存在文件test21_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数change的花括号中填写若干语句。文件test21_2.cpp的内容如下：char *change(char instr);#include iostream.hvoid main()char instr50;char *outstr;cout Input a string: instr;outstr=change(instr);cout Over graded string: endl;cout outstr = a & instri = z)outstri = instri + delta;elseoutstri = instri;outstri = 0;return outstr;2.4字符串连接4.22简单应用题常用字符串函数strcat(s1,s2)可将字符串s2添加到字符串s1的末端，但其使用必须保证字符串s1足够大，以便保存它自己的内容和字符串s2中的内容。请编写一个函数char *append(char *s1,char *s2)，其可将字符串s2添加到字符串s1的末端，而且不受s1空间大小的限制。请利用常用字符串函数实现。常用字符串函数说明：strcpy(to,form)：将form字符串复制到to字符串；strcat(s1,s2)：将字符串s2添加到字符串s1的末端,但必须保证字符串s1足够大；strlen(s)：返回字符串s的长度；注意：部分源程序已存在文件test4_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数append的花括号中填写若干语句。输出结果如下： this is a string.文件test4_2.cpp的内容如下：#include#includechar *append(char *s1,char *s2)void main()char *s,*s1,*s2;s1=this is ;s2=a string.;s=append(s1,s2);coutsendl;【答案】char *append(char *s1,char *s2)char *tmp;int length;length=strlen(s1)+strlen(s2);tmp=new charlength+1;strcpy(tmp,s1);strcat(tmp,s2);return tmp;字符串中的数字9.22简单应用题请编写一个函数int CalcDigital(char *str)，该函数可返回字符串str中数字字符（即0-9这10个数字）的个数，如字符串olympic2008中数字字符的个数为4。请用if条件判断语句与for循环语句来实现该函数。注意：部分源程序已存在文件test9_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数find的花括号中填写若干语句。文件test9_2.cpp的内容如下：#include#includeint CalcDigital(char *str);void main()char *str;str=new char255;coutstr;int num=CalcDigital(str);coutstr:numendl;int CalcDigital(char *str)【答案】int CalcDigital(char *str)if(str=NULL) return 0; int num_of_digital=0;int len=strlen(str); for(int i=0;ilen;i+)if(stri=0)num_of_digital+;return num_of_digital;2.6字符串中最大的字符15.22简单应用题请编写一个函数char MaxCharacter(char * str)，该函数返回参数str所指向的字符串中具有最大ASCII码的那个字符（如字符串world中字符w具有最大的ASCII码）。当str所指向的字符串为空时，则返回空字符0x0或0。输出结果如下：Good Morning!Max char：r注意：部分源程序已存在文件test15_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数MaxCharacter的花括号中填写若干语句。文件test15_2.cpp的内容如下：#include#includechar MaxCharacter(char * str);void main()char str100;strcpy(str,Good Morning!);char maxc=MaxCharacter(str);coutstrendl;coutMax char:maxcendl;char MaxCharacter (char *str)【答案】char MaxCharacter (char *str)if(str=NULL)return 0x0;char maxChar=0x0;int len=strlen(str);for(int i=0;imaxChar)maxChar=stri;return maxChar;2.7字符串删除一18.22简单应用题编写函数fun()，该函数的功能是从字符串中删除指定的字符，同一字母的大、小写按不同字符处理。例如：程序执行时输入字符串为turbo c and borland c+，从键盘上输入字符n，则输出后变为turbo c ad borlad c+。如果输入的字符在字符串中不存在，则字符串照原样输出。注意：部分源程序已存在文件test18_2.cpp中。请勿改动主函数main和其他函数中的任何内容，仅在函数fun的花括号中填入所编写的若干语句。文件test18_2.cpp的内容如下：#include#include#includevoid fun(char s , int c) void main()static char str =turbo c and borland c+;char ch;cout原始字符串:nstrendl;coutch;fun(str,ch);coutstr=strendl;【答案】void fun(char s , int c) int i=0;char *p;p=s; while(*p) if(*p!=c) si=*p; i+; p+; si=0; 2.8字符串删除二27.22简单应用题请编写函数fun()，其功能是将s所指字符串中除了下标为奇数、同时ASCII值也为奇数的字符之外，其余的所有字符都删除。字符串中剩余的字符所形成的一个新的字符串放在t所指的数组中。例如：s所指字符串中的内容为ABCDEFG12345，其中字符A的ASCII码值虽为奇数，但元素所在的下标为偶数，因此必需删除；字符1的ASCII码值为奇数，所在数组中的下标也为奇数，不删除，最后t所指的数组中的内容应是135。请勿修改主函数main和其他函数中的任何内容，仅在函数su的花括号中填写若干语句。文件test27_2.cpp的内容如下：#include #include #include #include void fun(char *s,char t ) void main()char s100,t100;coutPlease enter string S: endl; gets(s);fun(s, t);puts(t);【答案】void fun(char *s,char t ) int i,j=0,n;n=strlen(s); for(i=0;in;i+) if(i%2!=0&si%2!=0) tj=si;j+;tj=0; 2.9字符串查找20.22简单应用题请编写一个函数int pattern_index(char substr,char str)，该函数执行含通配符?的字符串的查找时，该通配符可以与任一个字符匹配成功。当子串substr在str中匹配查找成功时，返回子串substr在str中的位置，否则返回值为0。要求使用for循环实现。输出结果如下：子串起始位置：5注意：部分源程序已存在文件test20_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数pattern_index的花括号中填写若干语句。文件test20_2.cpp的内容如下：#includeint pattern_index(char substr,char str)void main()char *substring,*string;int same;substring=?gram;string=this program return index of substring;same=pattern_index(substring,string);if(same)cout子串起始位置:sameendl;elsecout匹配不成功endl;【答案】int pattern_index(char substr,char str)int i,j,k; for(i=0;stri;i+)for(j=i,k=0;(strj=substrk)|(substrk=?);j+,k+)if(!substrk+1)return(i);return(0);2.10字符串排序22.22简单应用题请编写函数fun()，对长度为7个字符的字符串，除首、尾字符外，将其余5个字符按ASCII值码降序排列。例如：原来的字符串为CEAedca，则排序后输出为CedcEAa。注意：部分源程序已存在文件test22_2.cpp中。请勿改动主函数main和其他函数中的任何内容，仅在函数fun的花括号中填入所编写的若干语句。文件test22_2.cpp的内容如下：#include #include #include #include void int fun(char *s, int num) void main()char s10;printf(输入7个字符的字符串:);gets(s);fun(s,7);couts;【答案】int fun(char *s, int num)char t; int i, j; for(i=1;inum-2;i+) for(j=i+1;jnum-1;j+) if(sisj) t=si; si=sj; sj=t; 2.11回文数26.22简单应用题请编写函数fun()，该函数的功能是判断字符串是否为回文，若是则函数返回1，主函数中输出YES；否则返回0，主函数中输出NO。回文是指顺读和倒读都一样的字符串。例如：字符串LEVEL是回文，而字符串123312就不是回文。注意：部分源程序已存在文件test26_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数fun的花括号中填写若干语句。文件test26_2.cpp的内容如下：#include#include#define N 80int fun(char *str)void main()char sN;coutEnter a string : endl; gets(s);coutnn; puts(s);if(fun(s) coutYESn;else coutNOn;【答案】int fun(char *str)int i,n