2013年9月华为机试题目

这一次的机试题目比以前的稍微难了一点点，这次整理的题目不一定很难，但是也是很基础的操作，我不可能知道机试的题目，就我的个人经验而言，机试的题目可能有一定的难度，但是不外乎一些基本的操作，这一次的改变就是二叉树、栈等其它数据结构类型的比例比以前增加了许多。

ps:下面的程序比5月份的版本更加可靠，也均在vs2005环境上面编译通过，为什么选择vs2005环境，一个是vs2005环境比6.0的编译规则更加规范，二个是华为机试的验证是在vs2005上面验证的。

1.最大回文数

#include <stdio.h> #include <stdlib.h> void GetMaxNumber(char *s) { char *p = s; char *q = s; int length = 0,max = 0,id = 0; while (*q++) length++; int index = 0,mx = 0; char *snew = (char*)malloc(sizeof(char)*(2*length-1)); for (;index<(length*2-2);index++) { if(index%2 == 0) snew[index] = p[mx++]; else snew[index] = '#'; } for (index=0,mx=0;snew[index];index++,mx=0) { for (;snew[index+mx] == snew[index -mx] && (index+mx)<(2*length-1) && (index-mx)>=0;mx++) if(mx > max) { max = mx; id = index; } } for (index=id-max+1;index<id+max;index++) { if(snew[index] == '#') continue; else printf("%c",snew[index]); } printf("\n"); } void main() { char c[] = "adcdabaabbaabbba,hello,suize!ezius,ollehasd"; GetMaxNumber(c); }

2.子串替换

#include <stdio.h> #include <stdlib.h> #include <string> //获得字符串长度 int GetStringLength(char *s) { char *p = s; int length = 0; while (*p++) length++; return length; } //字串替换 void StrReplace(char* strSrc, char* strFind, char* strReplace) { char *snew = (char*)malloc(sizeof(char)*100);//用来保存新的字符串 if (NULL == snew)//判断是否分配成功 snew = NULL; else memset(snew,0,100*sizeof(char));//全部赋值为0 char *ps = strSrc,*pf = strFind,*pr = strReplace; int lens = GetStringLength(ps); int lenf = GetStringLength(pf); int lenr = GetStringLength(pr); char *temp = (char*)malloc(sizeof(char)*lenf);//用来保存要匹配的字符串 if(NULL == temp) exit(1); else memset(temp,0,lenf*sizeof(char)); char *psnew = snew;//用来保存新字符串的起点 int index = 0; while (*ps) { int i = 0; for(i=0;i<lenf;i++)//复制 { *(temp+i) = *(ps+i); } for (i=0;i<lenf;i++)//匹配 { if(*(temp+i) != *(pf+i)) break; } if (i == lenf)//匹配成功 { for (int j=0;j<lenr;j++)//保存要替代的字符串 { *snew++ = *(pr+j); } ps += lenf;//后移lenf个位置 } else { *snew++ = *ps++;//后移一个位置 } } printf("\'%s\' - \'%s\' + \'%s\' = \n\'%s\'\nReplace Successfully!\n",strSrc,strFind,strReplace,psnew); } void main() { char strSrc[] = "hello,world!"; char strFind[] = "world"; char strReplace[] = "suize"; StrReplace(strSrc,strFind,strReplace); }

3.字符串过滤

#include <stdio.h> #include <stdlib.h> void main() { char c[100] = "abcdeabdask"; char outc[100] = {0}; int cc[26] = {0}; for (int i=0,j=0;i<sizeof(c)/sizeof(c[0]);i++) { if(cc[c[i]-'a'] == 0) { outc[j++] = c[i]; cc[c[i]-'a'] = 1; } } printf("%s\n",outc); }

4.约瑟夫环（没有bug的版本）

#include <stdio.h> #include <stdlib.h> #include <string> struct Person { int num; int code; Person *next; }; Person *person = NULL;//设置全局变量 void CreateCircus(); void main() { person = (Person*)malloc(sizeof(Person)*7); if (person == NULL) { exit(1); } else memset(person,NULL,7); CreateCircus(); int m = 6; Person *currentPerson = NULL; Person *prePerson = NULL; currentPerson = &person[0]; prePerson = &person[6]; while (currentPerson != prePerson) { for (int j = 1;j<m;j++) { prePerson = currentPerson; currentPerson = currentPerson->next; } m = currentPerson->code; printf("%d ",currentPerson->num); prePerson->next = currentPerson->next; currentPerson = prePerson->next; } } void CreateCircus() { for (int i=0;i<7;i++) { person[i].num = i+1; person[i].next = &person[i+1]; } person[6].next = &person[0]; person[0].code=3; person[1].code=1; person[2].code=7; person[3].code=2; person[4].code=4; person[5].code=8; person[6].code=4; }

5.手机号码匹配

#include <stdio.h> #include <stdlib.h> int GetStringLength(char *s) { char *p = s; int length = 0; while(*p++) length++; return length; } int CheckMobileNumber(char *mobile) { char *p = mobile; if (13 == GetStringLength(p)) { if('8' == *p && '6' == *(p+1)) { for(int i=0;i<13;i++) if (*p >= '0' && *p <= '9') p++; else return 2; } else return 3; return 0; } else return 1; } void main() { char *mobile = "8615850511953"; int check = CheckMobileNumber(mobile); switch (check) { case 0:printf("手机号码合法!\n");break; case 1:printf("手机号码长度不合法!\n");break; case 2:printf("手机号码中包含非数字的字符!\n");break; case 3:printf("手机号码不是以86打头的!\n");break; } }

6.括号匹配(2个)

1)

/************************************************************************/ /*输入一个字符串表达式，判断括号匹配 例如：｛｝｛｝｛｝【】【】（）｛【】｝ 匹配 ｛【｛】｝｝ 不匹配 使用堆栈实现，源码如下： */ /************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <windows.h> //typedef char* PCHAR; #define STACK_SIZE 100 int top = -1; void inistack(PCHAR& s) { // char* s; s=(char*)malloc(STACK_SIZE); memset(s,'/0',STACK_SIZE); // return s; } void destorystack(PCHAR& s) { free(s); } void push(char* s,char e) { //top++; if (top == STACK_SIZE-1) { s = (char*)realloc(s,STACK_SIZE*2); } top++; s[top] = e; } char pop(char* s) { char c=s[top]; top--; return c; } BOOL isEmpty() { return top == -1; } int scaleMah(const char* a) { int sizes = strlen(a); int i=0; char c='d'; char* s=&c; inistack(s); char zhan[100] = {0}; int j=0; for (i=0;i<sizes;i++) { switch (a[i]) { case '(': case '[': case '{': { push(s,a[i]); break; } case ')': { if(isEmpty()) return 0; if(pop(s) != '(') return 0; break; } case ']': { if(isEmpty()) return 0; if(pop(s) != '[') return 0; break; } case '}': { if(isEmpty()) return 0; if(pop(s) != '{') return 0; printf("/n"); break; } } } destorystack(s); if(!isEmpty()) return 0; else return 1; } int main() { printf("please input /n/n"); char a[100] = {0}; scanf("%s",a); int r = scaleMah(a); if (r == 0) { printf("not mach/n"); } else printf("mached!/n"); return 0; } 2）

#include "stdio.h" #include "string.h" #include "stdlib.h" #define StackSize 100 //假定预分配的栈空间最多为100个元素 #define MaxLength 100 //最大的字符串长度 typedef int DataType; //假定栈元素的数据类型为整数 typedef struct { DataType data[StackSize]; int top; }SeqStack; void Initial(SeqStack *S); int IsEmpty(SeqStack *S); int IsFull(SeqStack *S); void Push(SeqStack *S, DataType x); DataType Pop(SeqStack *S); DataType Top(SeqStack *S); void PrintMatchedPairs(char *expr); void main(void) { char expr[MaxLength]; printf("请输入符号个数小于%d的表达式：\n",MaxLength); gets(expr); printf("括号对是：\n"); PrintMatchedPairs(expr); return; } //置栈空 void Initial(SeqStack *S) { S -> top = -1; } //判断栈是否空 int IsEmpty(SeqStack *S) { return S -> top == -1; } //判断栈是否满 int IsFull(SeqStack *S) { return S -> top == StackSize -1; } //进栈 void Push(SeqStack *S, DataType x) { if(IsFull(S)) { printf("栈上溢!"); exit(1); } S -> data[++ S -> top] = x; return; } //出栈 DataType Pop(SeqStack *S) { if(IsEmpty(S)) { printf("栈为空！"); return -1; } return S -> data[S -> top--]; //栈顶指针加1后将x入栈 } //取栈顶元素 DataType Top(SeqStack *S) { if(IsEmpty(S)) { printf("栈为空！"); exit(1); } return S -> data[S -> top]; } //括号匹配 void PrintMatchedPairs(char *expr) { SeqStack S; int i , j , length = strlen(expr); Initial(&S); for(i = 1 ; i <= length ; i++) { if(expr[i - 1] == '(') { Push(&S,i); } else if(expr[i - 1] == ')') { j = Pop(&S); if(j == -1) { printf("没有对应第%d个右括号的左括号\n", i); } else { printf("%d %d\n",i,j); } } } while(!IsEmpty(&S)) { j = Pop(&S); printf("没有对应第%d个左括号的右括号\n", j); } } 7.交换左右子数

#include<stdio.h> #include<stdlib.h> typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef struct QNode{ BiTree t; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue; void InitQueue(LinkQueue &Q) { //构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//头结点 if(!Q.front) exit(0); Q.front->next=NULL; } bool Empty(LinkQueue Q) { if(Q.front==Q.rear) return true; else return false; } void EnQueue(LinkQueue &Q, BiTree t) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(0); p->t=t; p->next=NULL; Q.rear->next=p; Q.rear=p;//插入的t为Q的新的队尾元素 } void DeQueue(LinkQueue &Q,BiTree &t) { QueuePtr p; if(Q.front==Q.rear) { printf("队列为空！"); exit(0); } p=Q.front->next; t=p->t; Q.front->next=p->next; if(Q.rear==p)//只有一个元素的情况下，出去一个元素就变成空队列 Q.rear=Q.front; free(p); } void change_Q(BiTree &T)//非递归 { LinkQueue q; InitQueue(q); BiTree t,temp; EnQueue(q,T);//根结点入队列 while(!Empty(q)) { DeQueue(q,t); temp=t->lchild; t->lchild=t->rchild; t->rchild=temp; if(t->lchild!=NULL) EnQueue(q,t->lchild);//体会这里的妙处，原来交换过来了，想象入队列的情况 if(t->rchild!=NULL) EnQueue(q,t->rchild); } } void change(BiTree &T)//递归 { if(T) { BiTNode *temp; temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; change(T->lchild); change(T->rchild); } } void CreateBiTree(BiTree &T) { char ch; //scanf("%c",&ch); if((ch=getchar())=='\n') T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(0); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void PreOrderTraverse(BiTree T) { if(T) { printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void main() { BiTree T; CreateBiTree(T); PreOrderTraverse(T); printf("\n"); change_Q(T); PreOrderTraverse(T); }

8.简单四则运算

#include <stdio.h> #include <stdlib.h> #include <string> int GetStringLength(char *s) { char *p = s; int length = 0; while (*p++) length++; return length; } int calculate(int len,char *expStr) { char *temp = (char*)malloc(sizeof(char)*len); if (NULL == temp) exit(1); else memset(temp,0,len*sizeof(char)); char *p = expStr; char *temp2 = temp; int result = 0; for (int i=0;i<len;i++) { if ((*(p+i) != '*') && (*(p+i) != '/')) { *temp++ = *(p+i); } else { if (*(p+i) == '*') { *temp = (*--temp-48) * (*(p+i+1)-48)+48; temp++; i += 1; } else if(*(p+i) == '/') { *temp = (*--temp-48) / (*(p+i+1)-48)+48; temp++; i += 1; } } } for (int i=0;i<GetStringLength(temp2);i++) { if (*(temp2+i)<='9' && * (temp2+i)>='0' ) { result += *(temp2+i) - 48; } else { if (*(temp2+i) == '-') { result -= *(temp2+i+1) - 48; i += 1;//指针指向减法子表达式之后的一个运算符号 } else { result += *(temp2+i+1) - 48; i += 1;//指针指向加法子表达式之后的一个运算符号 } } } return result; } void main() { char *expStr = "1+4*5-8/3+3"; printf("%s = -\n",expStr,calculate(GetStringLength(expStr),expStr)); }

9.二叉树基本操作

#include<stdio.h> #include<stdlib.h> int count = 0;//保存叶子节点的数目 int nodenumber = 0;//保存总节点的数目 typedef struct node /*结构类型定义*/ { char data; struct node *left; struct node *right; }BiTNode; BiTNode *CreateBiTree(BiTNode *bt) {/*按先序次序输入二叉树中结点的值(可为字符型或整型)*/ char ch; ch = getchar(); if(ch=='?') bt=NULL; else { bt=(BiTNode*)malloc(sizeof(BiTNode));/*生成根结点*/ if(!bt) exit(0); bt->data=ch; bt->left=CreateBiTree(bt->left);/*构造左子树*/ bt->right=CreateBiTree(bt->right);/*构造右子树*/ } return bt; } void DLRSequence(BiTNode *bt) { if (bt) { printf("%c",bt->data); DLRSequence(bt->left); DLRSequence(bt->right); } } void LDRSequence(BiTNode *bt) { if (bt) { LDRSequence(bt->left); printf("%c",bt->data); LDRSequence(bt->right); } } void LRDSequence(BiTNode *bt) { if (bt) { LRDSequence(bt->left); LRDSequence(bt->right); printf("%c",bt->data); } } void ChangeChild(BiTNode *bt) //递归交换左右子数 { if(bt) { BiTNode *temp = bt->left; bt->left = bt->right; bt->right = temp; ChangeChild(bt->left); ChangeChild(bt->right); } } void LeafNumber(BiTNode *bt) { if (bt) { if (bt->left==NULL && bt->right==NULL) count++; LeafNumber(bt->left); LeafNumber(bt->right); } } void NodeNumber(BiTNode *bt) { if(bt) { if (bt) nodenumber++; NodeNumber(bt->left); NodeNumber(bt->right); } } //按层次遍历 //1.每一个数组元素是一个子数 //2.tail和head通过(XXX+1) 来自加 //3.tail跑的快，head跑的慢；tail负责将每一层的指针付给数组，head负责一次输出每一个元素。 //4.判断条件和节点数目无关，虽然二叉树节点为空，但是循环依然进行 void LevelTree(BiTNode *bt) { BiTNode *p; BiTNode *q[20]; int tail = 0,head = 0; if (bt) { tail = (tail+1) ; q[tail] = bt; } while (head != tail) { head = (head+1) ; p = q[head]; printf("%c",p->data); if (p->left!=NULL) { tail = (tail+1) ; q[tail] = p->left; } if (p->right!=NULL) { tail = (tail+1) ; q[tail] = p->right; } } } void main() { BiTNode* bt = NULL; printf("请先序输入二叉树(构建一个完全二叉树，空位置用?代替):\n"); bt=CreateBiTree(bt); printf("构造成功!\n"); printf("先序遍历结果是："); DLRSequence(bt); printf("\n"); printf("中序遍历结果是："); LDRSequence(bt); printf("\n"); printf("后序遍历结果是："); LRDSequence(bt); printf("\n"); printf("层序遍历结果是："); LevelTree(bt); printf("\n"); ChangeChild(bt); printf("交换左右子数的先序遍历结果是："); DLRSequence(bt); printf("\n"); LeafNumber(bt); NodeNumber(bt); printf("叶子节点数目为：%d\n",count); printf("总节点数目为：%d\n",nodenumber); //printf("数的层数是:%d\n",TreeHigh(bt)); } 10.字符串翻转

#include <stdio.h> #include <stdlib.h> //字符串翻转 void main() { char c[] = "!U-EVOI-I"; char *p = c; char *q = c; int len = 0; while(*q++) len++; //q -= 2; //correct q = c+len-1;//correct char *temp = (char *)malloc(sizeof(char)); if(temp == NULL) exit(1); for(int i=0;i<len/2;i++) { *temp = *q; *q = *p; *p = *temp; p++; q--; } printf("%s\n",c); }

11.合并字符串

#include <stdio.h> #include <stdlib.h> //获得字符串长度 int GetStringLength(char *s) { char *p = s; int length = 0; while(*p++) length++; return length; } //字符串合并 void MergeString(char *s1,char *s2) { int len1 = GetStringLength(s1); int len2 = GetStringLength(s2); char *p = (char*)malloc(sizeof(char)*(len1+len2+1)); if(p == NULL) exit(1); char *sum = p; for (int i=0;i<len1;i++) { *p = *s1; p++; s1++; } for (i=0;i<len2;i++) { *p = *s2; p++; s2++; } *p = '\0'; printf("%s\n",sum); p = sum; free(p); p = NULL; } //主函数 void main() { char s1[] = "hello,"; char s2[] = "suize!"; MergeString(s1,s2); } 12.单词倒置

#include <stdio.h> #include <stdlib.h> #include <string> void DivideString(const char *pInputStr, long lInputLen, char *pOutputStr) { int cnt = 0; char temp; for (int i=0;i<lInputLen;i++) { if (pInputStr[i] != ' ') { pOutputStr[i] = pInputStr[i]; cnt++; } else { for (int j = 0;j<cnt/2;j++)//倒置每一个单词 { temp = pOutputStr[i-cnt+j]; pOutputStr[i-cnt+j] = pOutputStr[i-1-j]; pOutputStr[i-1-j] = temp; } cnt =0; pOutputStr[i] = ','; } printf("%c",pOutputStr[i]); } printf("\n"); } void main() { char str[1000]; char *ch = NULL; gets(str); long lInputLen = strlen(str); ch = (char*)malloc(sizeof(char)*lInputLen); if (ch == NULL) { exit(0); } else memset(ch,0,lInputLen); DivideString(str,lInputLen,ch); printf("%s\n",ch); printf("%d\n",strlen(str)); } 13.删除子字符串 #include <stdio.h> #include <stdlib.h> int GetStringlength(char *s) { int length = 0; char *p = s; while (*p++) length++; return length; } //删除子字符串 void DeleteSubString(char *s,char *subs) { char *ps = s; char *psubs = subs; int lensub = GetStringlength(subs); char *temp = (char*)malloc(sizeof(char)*(lensub)); if(temp == NULL) exit(1); while (*ps) { for (int i = 0;i<lensub;i++)//复制，应该可以不用temp { *temp = *ps; temp++; ps++; } ps -= lensub;//还原 temp -= lensub; int j=0; for (j=0;j<lensub;j++)//比较 { if(*temp != *psubs) break; temp++; psubs++; } temp -= j;//还原 psubs -= j; if(j == lensub) ps += lensub; else { printf("%c",*ps);//打印输出 ps++; } } printf("\n"); free(temp); temp = NULL; } void main() { char s[] = "hello,suize!"; char subs[] = ",suize"; DeleteSubString(s,subs); }