2012最全华为上机试题及部分答案.doc

2011年华为软件校园招聘编程测验1、请上机编写程序，按题目要求提交文件。详见考试说明，点击进入考试说明3、评卷通过在给定用例输入下，严格按照试题要求比较考生实现函数的输出与预设输出。两者相同则得分，不同则不得分。4、评卷人保证测试用例输入参数的合法性，考生不用考虑输入参数非法或异常的情况5、评卷人保证测试用例输入在被测函数正常合法情况下使用不会导致程序错误6、如果考生函数异常导致程序崩溃或死循环，则自动评卷可能会被人为终止，剩余用例不被执行，无法得分7、基于上述阅卷规则，请考生严格按照题目要求功能实现程序，尽量保证实现函数的稳健性，同时建议完成一道题并调试保证正确性后，再考虑并实现下一题目1，判断电话号码是否合法：/要注意情况包含，有可能会同时出现几种不好的情况，要按照顺序输出错误。不能同时输出好几种错误，应该是这样包含：先判断长度是否符合，再判断是否以86打头，再判断有无其他字符int fun(char num)char *p=num;int n=strlen(num);if(n=13)if(*p=8&*(p+1)=6)while(*p!=0)if(*p=0&*p=9)p+;else return 2;if(*p=0)return 0;else return 3;elsereturn 1;int main()char num=87139a3887671;int k=fun(num);coutk=0&j=0;i-,j-)if(arry1i!=arry2j)k+;return k;int main()int num1=1,3,5;int num2=77,21,1,3,5;int k=f(3,num1,5,num2);coutkendl;return 0;2.约瑟夫问题 问题描述：输入一个由随机数组成的数列（数列中每个数均是大于0的整数，长度已知），和初始计数值m。从数列首位置开始计数，计数到m后，将数列该位置数值替换计数值m，并将数列该位置数值出列，然后从下一位置从新开始计数，直到数列所有数值出列为止。如果计数到达数列尾段，则返回数列首位置继续计数。请编程实现上述计数过程，同时输出数值出列的顺比如： 输入的随机数列为：3,1,2,4，初始计数值m=7，从数列首位置开始计数（数值3所在位置）第一轮计数出列数字为2，计数值更新m=2，出列后数列为3,1,4，从数值4所在位置从新开始计数第二轮计数出列数字为3，计数值更新m=3，出列后数列为1,4，从数值1所在位置开始计数第三轮计数出列数字为1，计数值更新m=1，出列后数列为4，从数值4所在位置开始计数最后一轮计数出列数字为4，计数过程完成。输出数值出列顺序为：2,3,1,4。 要求实现函数：voidarray_iterate(intlen,intinput_array,intm,intoutput_array)【输入】 intlen：输入数列的长度；intintput_array：输入的初始数列intm：初始计数值【输出】 intoutput_array：输出的数值出列顺序 示例输入：intinput_array=3,1,2,4，intlen=4，m=7输出：output_array=2,3,1,4函数如下：void fun(int len,int a1,int len2,int a2)int n=0,i=-1,k=1,m=len2;while(1)for(int j=0;jm;)i=(i+1)%len; /注意这个是%，不要写成/if(a1i!=0)j+; m=a1i;a2n+=a1i;a1i=0; if(k=len)break; k+;3.简单四则运算 问题描述：输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值注： 1、表达式只含+,-,*,/四则运算符，不含括号2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况3、要考虑加减乘除按通常四则运算规定的计算优先级4、除法用整数除法，即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况 要求实现函数：intcalculate(intlen,char*expStr)【输入】 intlen:字符串长度；char*expStr:表达式字符串；【输出】 无【返回】 计算结果 示例1） 输入：char*expStr=“1+4*5-8/3” 函数返回：192） 输入：char*expStr=“8/3*3” 函数返回：6 简化版的四则运算：没有括号，只有加减乘除四种运算int fun(char a,int len) /字符数组和字符数组的长度int num20;char str20;int k1=0,k2=0;int data=0;for(int i=0;i=0&ai=9) numk1+=ai-0;if(ai=-|ai=+)strk2+=ai;if(ai=*) numk1-1=numk1-1*(ai+1-0);i+;/遇见*，就运算，结果保存在数组中if(ai=/) numk1-1=numk1-1/(ai+1-0);i+;int temp=num0;int j=0; /两个数组只剩下数组和加减运算符while(jk2) /顺序运算if(strj=-)temp=temp-numj+1;else if(strj=+)temp=temp+numj+1;j+;return temp;int main() har a=3*3+7+4/3;int k=fun(a,9);coutkendl;return 0;函数实现2：中序表达式转换为后序表达式，使用算法实现int isp(char c) int p;switch(c)case *:case /:p=1;break;case +:case -: p=0;break;return p;char* transf(int len,char a,char b)int k=0;stack s1;for(int i=0;i=0&ai=9)bk+=ai; else if(s1.empty()s1.push(ai); else while(isp(ai)=isp(s1.top() bk+=s1.top();s1.pop();s1.push(ai);while(s1.empty()bk+=s1.top();s1.pop();bk=0;return b;void fun(char c,stack s2) char p1,p2;if(!s2.empty()p1=s2.top();s2.pop();else pos=false;coutkongzhanendl;if(!s2.empty()p2=s2.top();s2.top();else pos=false;coutkongzhanendl;if(pos=true)switch(c)case +:s2.push(p1+p2);break;case -:s2.push(p2-p1);break;case *:s2.push(p1*p2);break;case /:s2.push(p2/p1);break;void eval(char a) stack s2;for(int i=len;ilen;i+)switch(ai)case +:case -:case *:case /:fun(ai,&s2);break;default:s2.push(ai-0);break;int main() char a=1+4*5-8/3;int len=strlen(a);char b20;char *q=transf(9,a,b);coutqendl;return 0;第五题：一副牌中发五张扑克牌给你：让你判断数字的组成：有以下几种情况：1：四条：即四张一样数值的牌（牌均不论花色） 2：三条带一对3：三条带两张不相同数值的牌 4：两对 5：顺子包括10，J，Q，K，A6：什么都不是 7：只有一对 思路：将数组排序，统计相同的数字的个数，再分情况讨论void sort(int a)int temp;for(int i=0;i5;i+) for(int j=0;jaj)temp=ai;ai=aj;aj=temp;void test(int a)int *b=new int5;int k=1;for(int i=0;i5;i+) bi=ai;for(int j=0;j4;j+)if(aj=aj+1)k+;if(k=4)if(b1=b3)cout四条endl;elsecout三条带一对endl;if(k=3)if(b1!=b2|b2!=b3)cout三条带两个不同的牌endl;elsecout两对endl;if(k=2)cout一对endl;if(k=1)if(b4-b0=4&b4-b1=3&b4-b2=2&b4-b3=1)cout顺子endl;elsecout什么都不是endl; int main() int a=1,2,4,4,4;test(a);return 0;第二题：求两个数组的和差就是去掉两个数组中相同的元素然后将两个数组中的元素存放在一个新的数组中，按大小顺序排序思路：将数组A和数组B分别进行排序，然后将A与B进行比较，重复的跳过去，不重复的赋给数组C，依次输出。 while(i la & j lb) if(aai bbj) csub = bbj; +sub; +j; else if(aai = bbj) +i; +j; for(; i la; +i) csub = aai; +sub; for(; j next;while(p2)p3=p2-next;p2-next=p1;p1=p2;p2=p3;head-next=NULL;head=p1;return head;2. 将一个字符串的元音字母复制到另一个字符串，并排序（30分）问题描述：有一字符串，里面可能包含英文字母（大写、小写）、数字、特殊字符，现在需要实现一函数，将此字符串中的元音字母挑选出来，存入另一个字符串中，并对字符串中的字母进行从小到大的排序（小写的元音字母在前，大写的元音字母在后，依次有序）。说明：1、 元音字母是a,e,i,o,u,A,E,I,O,U。 2、 筛选出来的元音字母，不需要剔重；最终输出的字符串，小写元音字母排在前面，大写元音字母排在后面，依次有序。要求实现函数：void sortVowel (char* input, char* output);using namespace std;void fun(char a,char s) /提取元音字母，放入数组int i=0,n=0;while(ai!=0)if(ai=a|ai=e|ai=i|ai=o|ai=u)sn+=ai;else if(ai=A|ai=E|ai=I|ai=O|ai=U)sn+=ai;i+;char temp; /将数组排序for(int i=0;in-1;i+)for(int j=0;jsj+1)temp=sj;sj=sj+1;sj+1=temp;int k=0; /定位大写字母的最后位置while(sk=A&sk=Z)k+; for(int j=0;jn;j+) /输出原字符串 coutsj ; coutendl;char *p=new char20; /将字符串变换位置，输出。char *q=p; for(int i=k;in;i+)*p=si;p+;for(int j=0;jk;j+)*p=sj;p+;*p=0;coutqendl;int main() char str=HaJsdStOoAOeINaPQaWEiAIiO;char s20;fun(str,s);return 0;3. 身份证号码合法性判断我国公民的身份证号码特点如下：1、 长度为18位；2、 第117位只能为数字；3、 第18位可以是数字或者小写英文字母x。4、 身份证号码的第714位表示持有人生日的年、月、日信息。例如：511002 19880808 0111或511002 19880808011x。请实现身份证号码合法性判断的函数。除满足以上要求外，需要对持有人生日的年、月、日信息进行校验。年份大于等于1900年，小于等于2100年。需要考虑闰年、大小月的情况。所谓闰年，能被4整除且不能被100整除 或 能被400整除的年份，闰年的2月份为29天，非闰年的2月份为28天。其他情况的合法性校验，考生不用考虑。函数返回值：1） 如果身份证号合法，返回0；2） 如果身份证号长度不合法，返回1；3） 如果身份证号第117位含有非数字的字符，返回2；4） 如果身份证号第18位既不是数字也不是英文小写字母x，返回3；5） 如果身份证号的年信息非法，返回4；6） 如果身份证号的月信息非法，返回5；7） 如果身份证号的日信息非法，返回6（请注意闰年的情况）；要求实现函数：int verifyIDCard(char* input)示例1） 输入：”511002 111222”，函数返回值：1；2） 输入：”511002 abc123456789”，函数返回值：2；3） 输入：”511002 19880808123a”，函数返回值：3；4） 输入：”511002 188808081234”，函数返回值：4；5） 输入：”511002 198813081234”，函数返回值：5；6） 输入：”511002 198808321234”，函数返回值：6；7） 输入：”511002 1989 0229 1234”，函数返回值：7；8） 输入：”511002 198808081234”，函数返回值：0；int fun(char *str)int year=0,month=0,day=0;if(strlen(str)-1)18) /1 for(int i=0;i=0&stri=0&str17=9)/3for(int i=6;i1900&year2100)/4 for(int i=10;i0&month=12)/5 for(int i=12;i14;i+) day=day*10+stri-0; if(day=31)/6 if(year%4!=0&month=2&day=28)return 0;else if(year%4=0&month=2&day29) return 0;else if(year%4!=4&month!=2&day31)return 0;else return 6; else return 6; elsereturn 5;else return 4; else return 3; else return 1;int main()char a=340621198608377817;int k=fun(a);coutkendl;return 0;第二题：比较一个数组的元素 是否为回文数组判断是否是回文数组：bool fun(char a)int n=strlen(a);int i=0,j=n-1;while(ij)if(ai!=aj)return false;i+;j-;return true;第三题：求两个数组的和差：就是去掉两个数组中相同的元素 然后将两个数组中的元素存放在一个新的数组中 且数组A中元素要在B数组元素之前思路：利用循环比较，将相同的数字的标记为0，再赋给数组Cint main() int a=1,3,5,7,9,12,13;int s=1,3,5,6,7,8,9;int len1=sizeof(a)/sizeof(int);int len2=sizeof(s)/sizeof(int);for(int i=0;ilen1;i+)for(int j=0;jlen2;j+)if(ai=sj)ai=0;sj=0;int t30;int k=0,i=0,j=0;while(ilen1)if(ai!=0)tk+=ai;i+;while(jlen2)if(sj!=0)tk+=sj;j+;for(int i=0;ik;i+)coutti ;return 0;字符串计算1、选秀节目打分，分为专家评委和大众评委，score数组里面存储每个评委打的分数，judge_type里存储与score数组对应的评委类别，judge_type=1，表示专家评委，judge_type=2，表示大众评委，n表示评委总数。打分规则如下：专家评委和大众评委的分数先分别取一个平均分（平均分取整），然后，总分=专家评委平均分*0.6+大众评委*0.4，总分取整。如果没有大众评委，则总分=专家评委平均分，总分取整。函数最终返回选手得分。int cal_score(int score, int judge_type, int n)int sum1=0,sum2=0,avg1=0,avg2=0;int m=0,k=0;for(int i=0;in;i+)if(judge_typei=1)sum1=sum1+scorei;m+;if(judge_typei=2)sum2=sum2+scorei;k+;avg1=sum1/m;avg2=sum2/k;return (int)(avg1*0.6+avg2*0.4);int main() int input=3,6,1,9,7,8;int output=1,1,2,1,2,2;int n=sizeof(input)/sizeof(int);int p=cal_score(input,output,n);coutpendl;return 0;2、给定一个数组input，如果数组长度n为奇数，则将数组中最大的元素放到output数组最中间的位置，如果数组长度n为偶数，则将数组中最大的元素放到output数组中间两个位置偏右的那个位置上，然后再按从大到小的顺序，依次在第一个位置的两边，按照一左一右的顺序，依次存放剩下的数。例如：input=3,6,1,9,7output=3,7,9,6,1;input=3,6,1,9,7,8output=1,6,8,9,7,3函数接口voidsort(intinput,intn,intoutput)using namespace std;void sort(int input,int n,int output)int i=0,j=n-1;int temp;for(int i=0;in-1;i+)for(int j=0;jinputj+1)temp=inputj;inputj=inputj+1;inputj+1=temp;int k=0;i=0;j=n-1;while(ij)outputi+=inputk+;outputj-=inputk+;coutoutput3endl;int main() int input=3,6,1,9,7,8;int output20;sort(input,6,output);return 0;3、操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级=50且=255。优先级大于255的为非法任务，应予以剔除。现有一任务队列task，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler实现如下功能，将task中的任务按照系统任务、用户任务依次存放到system_task数组和user_task数组中（数组中元素的值是任务在task数组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。task=0,30,155,1,80,300,170,40,99system_task=0,3,1,7,-1user_task=4,8,2,6,-1函数接口：void scheduler(int task, int n,int system_task, int user_task) int *p = new intn; int i,j,temp; int k1=0,k2=0; for(i = 0;in;i+) pi = i;for(i = 0;in-1 ;i+) for(j=0;j*(task+pj+1) temp = pj;pj = pj+1;pj+1 = temp; /此处是排下标 for(j=0;jn;j+) if(*(task+pj)=50 & *(task+pj)k) /创建单链表s=new node1;s-data=k;p-next=s;p=s;head=head-next; /开始的的时候head是表头节点，现在是第一个节点p-next=NULL;return head;node *reverse(node *head)node *p1,*p2,*p3;p1=head;p2=head-next;while(p2)p3=p2-next;p2-next=p1;p1=p2;p2=p3;head-next=NULL;head=p1;return head;node *del(node *head,int num)node *p,*s;p=head;while(p-data!=num&p-next!=NULL)s=p;p=p-next;if(p-data=num)if(p=head)head=p-next;delete p;elses-next=p-next;delete p;elsecout未找到要删除的节点data=num;while(p-datanext!=NULL)s=p;p=p-next;if(numdata)if(p=head)t-next=p;head=s;else t-next=p;s-next=t;else /把插入点定位在了链尾p-next=t;t-next=NULL;return head; node *sort(node* head) node *p; int temp; int n=sizeof(head)/sizeof(node); if(head=NULL&head-next=NULL)return head; p=head; for(int i=0;in;i+) p=head;for(int j=0;jdatap-next-data) temp=p-data;p-data=p-next-data;p-next-data=temp; return head; 栈的基本操作：struct listint data;struct node *next;*node;void initstack(node &top)top=NULL;void push(node &top,int num)node *p;p=new node;p-data=num;p-next=top;top=p;void pop(node &top)node *p=top;int n=top-data;top=top-next;coutni;j-) if(sjsj-1) b=1; temp=sj; sj=sj-1; sj-1=temp; for(j=i;jsj+1) b=1;temp=sj;sj=sj+1;sj+1=temp; i+;扫描数组，求出最大的增量长度：int main() int a=7,2,3,4,5,6,8;int n=7;int max=1,len=1;for(int i=1;i=ai-1) len+; continue; /跳出本次循环，继续以下的部分if(maxlen)max=len;len=1;coutmaxendl;return 0;扫描整数序列，求出最大长度子序列：思路：定义两个游标i j分别在数组的左右，从两边收缩，计算i j之间数组的总和，然后比较，求出最大的记录，并将此时的i j 记录下来。int main() int s=1,20,-3,49,59,10,30,20,-41,90,-2,-30,60.-29;int n=sizeof(s)/sizeof(int);int i,k,j,a,b,num,max=0;for( i=0;i=i;j-) num=0;for( k=i;k=j;k+)num=num+sk; if(maxnum) max=num; a=i; b=j; for(int m=a;m=b;m+)coutsm ;return 0; 直接插入排序：void insertsort(int a,int n)int x,j;for(int i=1;i=0&xaj;j-)aj+1=aj; aj+1=x;提取字符串中的数字：在字符串ab00cd+123fght456-253.005fgh中提取的字符是0,123,456,253，5。void fun( char str, int outArray)char *p=str;int count=0,value=0;while(*p!=0)if(*p=9)value=0; while(*p=9) value=value*10+(*p-0); p+； outArraycount+=value;p+;数字转换成字符串：int main()char str20,temp20;int i=0,j=0;int num=1234567;while(num0)stri=num%10+0;num=num/10;i+;i-;while(i=0)tempj+=stri-;tempj=0;couttempN; /定义输入的行数 getchar(); /输入的N行字符 for(int i=0;iN;i+) while(1) /记住控制方法 ch=getchar(); /这是单个字符 if(ch=a)num+; if(ch=n)break; coutnum=0&j=0) resultn+=(pi-0)+(qj-0)+k)%10+0; k=(pi-0)+(qj-0)/10; i-;j-; while(i=0) resultn+=(pi-0)+k)%10+0; k=(pi-0)+k)/10; i-; while(j0) resultn+=(qj-0)+k)%10+0; k=(qj-0)+k)/10; i-; if(k=1) resultn+=1; /如果是两个负数相加 ，加上resultn+=-; resultn=0; 求字符串中最大的回文长度：void fun(char a)int len=strlen(a);int i=0,j=len-1,len2=0; /len2是回文的一半长度char *p,*q;int max=0,pos1=0,pos2=0;for(i=0;ii;j-) p=&ai;q=&aj;while(pq) if(*p=*q)len2+;p+;q-;Else /上式中，如若不成立，保留下来的len的值可能很大，要将其变成0，以便继续使用。 len=0,break;