c++面试编程题

常用经典编程例子

一个链表的结点结构

struct Node { int 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 < head2->data ) {

head = head1 ; p1 = head1->next; p2 = head2 ;

} else {

head = head2 ; p2 = head2->next ; p1 = head1 ; }

Node *pcurrent = head ;

while ( p1 != NULL && p2 != NULL) {

if ( p1->data <= p2->data ) {

pcurrent->next = p1 ; pcurrent = p1 ; p1 = p1->next ; } else {

pcurrent->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 < head2->data ) {

head = head1 ;

head->next = MergeRecursive(head1->next,head2); }

else {

head = head2 ;

head->next = MergeRecursive(head1,head2->next); }

return head ;

写一个函数找出一个整数数组中，第二大的数 （microsoft）

答案：

const int MINNUMBER = -32767 ; int find_sec_max( int data[] , int count) {

int maxnumber = data[0] ;

int sec_max = MINNUMBER ; for ( int i = 1 ; i < count ; i++) {

if ( data[i] > maxnumber ) {

sec_max = maxnumber ; maxnumber = data[i] ; } else {

if ( data[i] > sec_max ) sec_max = data[i] ; } }

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 < num) {

q = p; p = p->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; else break; } if(!p)//没有找到要删除的结点 return NULL; else {

if(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 < num) { q = p; p = p->next; } else break; } 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)

cout<<\"have ring\"; else

cout<<\"no ring\";

如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）

struct node { char val; node* next;}

bool check(const node* head) {} //return false : 无环；true: 有环一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）： bool check(const node* head) {

if(head==NULL) return false; node *low=head, *fast=head->next;

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; else { Node *p = head; head = head->next; delete p; } return head; }

String 的具体实现

已知String类定义如下：

class String {

public:

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 char[1] ; m_data[0] = '\\0' ; } else {

m_data = new char[strlen(str) + 1]; strcpy(m_data,str); } }

String::String(const String &another)

{

m_data = new char[strlen(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 char[strlen(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 (0if(bSign==true) { } else { }

return bSign;

printf(\"No!\\n\"); printf(\"Yes!\\n\");

for (int i=0;iif(*p++!=*q--){ bSign=false;break;};

整数转换成字符串itoa函数的实现

    

#include \"stdafx.h\" #include using namespace std;

void itoaTest(int num,char str[] ) {

   

int sign = num,i = 0,j = 0; char temp[11];

if(sign<0)//判断是否是一个负数 {

 num = -num;  };  do  {

 temp[i] = num%10+'0';  num/=10;  i++;  }while(num>0);  if(sign<0)  {

 temp[i++] = '-';  }

 temp[i] = '\\0';  i--;  while(i>=0)  {

 str[j] = temp[i];  j++;  i--;  }

 str[j] = '\\0';  }

编程实现字符串转化为整型，不用atoi

 string str;  int sum = 0;  cin >> str;

 for(int i = 0; i < str.size(); i++)  {

 sum = sum * 10 + str[i] - '0';  }

 cout << sum << endl;

请写出一个函数来模拟c++中的strstr函数：该函数的返回值是主传中字符子串的位置以后的所有字符，请不要使用任何c程序已有的函数

 string LeftSting(const string &Srcstr, const string &Substr)  {

 string Results(\"\");  int i = 0;

 while(i < Srcstr.size())

 {                        }

 return Results;  }

int j = i; int k = 0;

while(k < Substr.size()) { if(Srcstr[j] == Substr[k]) { j++; k++; } else break; }

if(k == Substr.size())//找到了子串 { for(int t = i; t < Srcstr.size(); t++) Results += Srcstr[t]; break; }

else if(k == 0)//此时第一个不是匹配的 i++;

else//此时已经匹配了k个字符 i += k;

字符串输出

35.22．简单应用题

请编写一个函数display()，该函数要求用户先输入一字符串，然后在屏幕上再输出该字符串（假设该字符串长度小于100）。注意：部分源程序已存在文件test35_2.cpp中。

请勿修改主函数main和其他函数中的任何内容，仅在函数display()的花括号中填写若干语句。 如输入abc，输出结果如下： please input string: abc abc

Press any key to continue

文件test35_2.cpp的内容如下：

#include #include void display() { }

void main() {

cout<<\"please input string:\"<} 【答案】

void display() {

char str[100],ch; int i=0;

while ((ch=getche())!='\\r') { str[i]=ch; i++; }

str[i]='\\0';

cout<2.2字符串翻转

16.22．简单应用题

请编写一个函数void fun(char ss[])，该函数将字符串ss翻转，如ss为\"123abc\"则翻转后为\"cba321\"。注意：用数组方式及for循环来实现该函数。

注意：部分源程序已存在文件test16_2.cpp中。

请勿修改主函数main和其他函数中的任何内容，仅在函数fun的花括号中填写若干语句。 文件test16_2.cpp的内容如下： #include #include void fun(char ss[]); void main() {

char s[80];

cout<<\"请输入字符串：\"; cin>>s; fun(s);

cout<<\"逆序后的字符串:\"<void fun(char ss[]) { }

【答案】void fun(char ss[])

{

int n=strlen(ss);

for(int i=0;i<(n/2); i++) { char c=ss[i]; ss[i]=ss[n-1-i]; ss[n-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.h\" void main() {

char instr[50]; char *outstr;

cout << \"Input a string: \" <> instr;

outstr=change(instr);

cout << \"Over graded string: \" << endl; cout << outstr <char *change(char instr[]) { } 【答案】

char *change(char instr[]) {

char *outstr=new char[50];

const char delta = 'A' - 'a'; int i;

for( i = 0 ; instr[i] != '\\0'; i++) { if(instr[i] >= 'a' && instr[i] <= 'z') { outstr[i] = instr[i] + delta; } else { outstr[i] = instr[i]; } }

outstr[i] = '\\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 #include

char *append(char *s1,char *s2) { }

void main() {

char *s,*s1,*s2; s1=\"this is \"; s2=\"a string.\"; s=append(s1,s2); cout<char *append(char *s1,char *s2) {

char *tmp; int length;

length=strlen(s1)+strlen(s2); tmp=new char[length+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 #include

int CalcDigital(char *str); void main() {

char *str;

str=new char[255]; cout<<\"输入字符串：\"; cin>>str;

int num=CalcDigital(str); cout<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;iif(str[i]<='9' && str[i]>='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 #include

char MaxCharacter(char * str); void main() {

char str[100];

strcpy(str,\"Good Morning!\"); char maxc=MaxCharacter(str); cout<cout<<\"Max char:\"<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=str[i]; }

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 #include

void fun(char s[ ], int c) { }

void main() {

static char str[ ]=\"turbo c and borland c++\"; char ch;

cout<<\"原始字符串:\\n\"<>ch;

fun(str,ch);

cout<<\"str=\"<void fun(char s[ ], int c) {

int i=0; char *p; p=s; while(*p)

{if(*p!=c) {s[i]=*p; i++; }

p++; }

s[i]='\\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 s[100],t[100];

cout<<\"Please enter string S: \"<}

【答案】

void fun(char *s,char t[ ]) {

int i,j=0,n;

n=strlen(s); for(i=0;iif(i%2!=0&&s[i]%2!=0) { t[j]=s[i];j++;} t[j]='\\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的内容如下：

#include

int 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<<\"子串起始位置:\"<cout<<\"匹配不成功\"<int pattern_index(char substr[],char str[]) {

int i,j,k;

for(i=0;str[i];i++) for(j=i,k=0;(str[j]==substr[k])||(substr[k]=='?');j++,k++) if(!substr[k+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 s[10];

printf(\"输入7个字符的字符串:\"); gets(s); fun(s,7); cout<int fun(char *s, int num) {char t; int i, j;

for(i=1;i2.11回文数

26.22．简单应用题

请编写函数fun()，该函数的功能是判断字符串是否为回文，若是则函数返回1，主函数中输出YES；否则返回0，主函数中输出NO。回文是指顺读和倒读都一样的字符串。

例如：字符串LEVEL是回文，而字符串123312就不是回文。 注意：部分源程序已存在文件test26_2.cpp中。

请勿修改主函数main和其他函数中的任何内容，仅在函数fun的花括号中填写若干语句。 文件test26_2.cpp的内容如下：

#include #include #define N 80

int fun(char *str) { }

void main() {char s[N];

cout<<\"Enter a string : \"<cout<<\"\\n\\n\"; puts(s); if(fun(s)) cout<<\"YES\\n\"; else

cout<<\"NO\\n\"; } 【答案】

int fun(char *str) {int i,n=0,fg=1; char *p=str; while(*p) {n++; p++;}

for(i=0;iif(str[i]==str[n-1-i]) ; else

{fg=0; break;} return fg; }

数组查找一

19.22．简单应用题

请编写一个函数int SeqSearch(int list[], int start, int n, int key)，该函数从start开始，在大小为n的数组list中查找key值，返回最先找到的key值的位置，如果没有找到则返回-1。请使用for循环实现。

注意：部分源程序已存在文件test19_2.cpp中。

请勿修改主函数main和其他函数中的任何内容，仅在函数SeqSearch的花括号中填写若干语句。 文件test19_2.cpp的内容如下：

#include

int SeqSearch(int list[], int start, int n, int key) { }

void main() {

int A[10];

int key, count=0, pos;

cout<<\"Enter a list of 10 integers: \"; for(pos=0;pos<10;pos++) { cin>>A[pos]; }

cout<<\"Enter a key: \"; cin>>key; pos=0;

while( (pos=SeqSearch(A,pos,10,key))!=-1) { count++; pos++; }

cout<list.\"<}

【答案】

int SeqSearch(int list[], int start, int n, int key) {

for(int i=start;ireturn -1; }

3.6数组查找二

43.22．简单应用题

请编写一个函数 index(int x,int a[],int n)，该函数实现先显示给定长度的一数组中所有元素，然后在其中查找一个数是否存在的功能。注意：使用for循环结构实现该函数的基本功能，根据main函数的调用情况给出正确的返回值。部分源程序已存在文件test43_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数index的花括号中填写若干语句。

源程序文件test43_2.cpp清单如下：

#include

bool index(int x,int a[],int n) { }

void main() {

int a[]={1,2,3,4,5,6,7,8}; int num; num=5;

cout<<\"num=5\\n\";

if (index(num,a,8)) cout<<\"true\"<bool index(int x,int a[],int n) {

for(int i=0;i