华为机试题目教学内容.doc

《华为机试题目教学内容.doc》由会员分享，可在线阅读，更多相关《华为机试题目教学内容.doc（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Good is good, but better carries it.精益求精，善益求善。华为机试题目-1、 链表逆序1:CList*converseList(CList*head)2:3:CList*conHead=head;4:CList*before=NULL;5:CList*after=NULL;6:7:while(conHead-next!=NULL)8:9:after=conHead-next;10:conHead-next=before;11:before=conHead;12:conHead=after;13:14:15:return*conHead;16:LinkList.

2、hviewplaincopytoclipboardprint?1. #ifndefLINKLIST_H2. #defineLINKLIST_H3. typedefintElemType;4. typedefstructLNode5. 6. ElemType*data;7. structLNode*next;8. intlength;9. LNode,*LinkList;10. LinkListinitList();11. voidinsertList(LinkListl,ElemType*data,intsizeOfData);12. intlength(LinkListl);13. void

3、reverse(LinkListl);14. #endifLinkList.cviewplaincopytoclipboardprint?1. #includeLinkList.h2. #include3. #include4. /*5. /Method:initList6. /FullName:initList7. /Access:public8. /Returns:LinkList9. /Qualifier:10. /*11. LinkListinitList()12. 13. LinkListl=0;14. l=(LinkList)malloc(sizeof(LNode);15. if(

4、l=NULL)16. returnNULL;17. l-data=0;18. l-next=NULL;19. l-length=0;20. returnl;21. 22. /*23. /Method:insertList24. /FullName:insertList25. /Access:public26. /Returns:void27. /Qualifier:28. /Parameter:LinkListl29. /Parameter:ElemType*data30. /Parameter:intsizeOfData31. /*32. voidinsertList(LinkListl,E

5、lemType*data,intsizeOfData)33. 34. LNode*n=0;35. if(l=NULL|data=NULL)36. return;37. n=(LNode*)malloc(sizeof(LNode);38. if(n=NULL)39. return;40. n-data=(ElemType*)malloc(sizeof(ElemType);41. if(n-data=NULL)42. 43. free(n-data);44. free(n);45. return;46. 47. memcpy(n-data,data,sizeOfData);48. n-next=l

6、-next;49. l-next=n;50. l-length+;51. 52. /*53. /Method:length54. /FullName:length55. /Access:public56. /Returns:int57. /Qualifier:58. /Parameter:LinkListl59. /*60. intlength(LinkListl)61. 62. if(l=NULL)63. return0;64. returnl-length;65. 66. /*67. /Method:reverse68. /FullName:reverse69. /Access:publi

7、c70. /Returns:void71. /Qualifier:72. /Parameter:LinkListl73. /*74. voidreverse(LinkListl)75. 76. LinkListp,q,r;77. if(l=NULL)78. return;79. p=l-next;80. q=p-next;/q为p下一个节点81. while(q)82. 83. r=q-next;/r为q下一个节点84. q-next=p;/指针回指85. p=q;86. q=r;/p,q后移*关键是对指针间赋值的理解*87. 88. l-next=p;89. main.cviewplainc

8、opytoclipboardprint?1. #includeLinkList.h2. #include3. intmain()4. 5. ElemTypenum1=1,num2=2,num3=3;6. LinkListl=initList();7. LinkListl2=initList();8. insertList(l,&num1,sizeof(ElemType);9. insertList(l,&num2,sizeof(ElemType);10. insertList(l,&num3,sizeof(ElemType);11. reverse(l);12. return0;#includ

9、e#include#includestruct_Nodeintdata;struct_Node*next;typedefstruct_NodeNode;/交换两个结点的数据voidSwapNodeData(Node*p1,Node*p2)inttemp=p1-data;p1-data=p2-data;p2-data=temp;/冒泡排序对链表进行排序voidBubbleSort(Node*head)Node*pTemp;intmaxIdx,idx;/计算链表长度maxIdx=0;for(pTemp=head;pTemp!=NULL;pTemp=pTemp-next)+maxIdx;idx=0;

10、while(idxmaxIdx-1)for(pTemp=head;idxnext,+idx)if(pTemp-datapTemp-next-data)SwapNodeData(pTemp,pTemp-next);idx=0;-maxIdx;intmain(void)Node*head=NULL,*temp=NULL,*p=NULL;inti;srand(unsignedint)time(NULL);/产生随机数链表head=(Node*)malloc(sizeof(Node);head-data=rand()%40;p=head;for(i=1;idata=rand()%40;p-next=t

11、emp;p=p-next;p-next=NULL;/输出随机数链表for(p=head;p!=NULL;p=p-next)printf(%d,p-data);printf(n);/对链表排序BubbleSort(head);/输出以排序的链表for(p=head;p!=NULL;p=p-next)printf(%d,p-data);printf(n);/释放资源for(p=head-next;p!=NULL;p=p-next)free(head);head=p;free(head);head=NULL;getchar();return0;2、 判断是否是回文数intlOver=0;intlQu

12、otient=0;lQuotient=lNum;while(1)lOver=lOver*10+lQuotient%10;lQuotient=lQuotient/10;if(lQuotient=0)break;/printf(lNum=n,lNum);/printf(lNum=n,lOver);if(lNum=lOver)/判断反序之后的数与原来的数是否相等result=1;elseresult=0;return0;intmain(void)intnum;intresult=0;while(1)printf(Enteranumber:);scanf(%d,&num);PrintNum(num,r

13、esult);if(result)printf(%disapalinfronnumber.n,num);elseprintf(%disnotapalinfronnumber.n,num);3、 识别字符串中的整数并转换为数字形式voidtake_num(constchar*strIn,int*n,unsignedint*outArray)【输入】strIn：输入的字符串【输出】n：统计识别出来的整数个数outArray：识别出来的整数值，其中outArray0是输入字符串中从左到右第一个整数，outArray1是第二个整数，以此类推。数组地址已经分配，可以直接使用【返回】无注：I、不考虑字符串

14、中出现的正负号(+,-)，即所有转换结果为非负整数（包括0和正整数）II、不考虑转换后整数超出范围情况，即测试用例中可能出现的最大整数不会超过unsignedint可处理的范围III、需要考虑0开始的数字字符串情况，比如00035，应转换为整数35；000应转换为整数0；00.0035应转换为整数0和35（忽略小数点：mmm.nnn当成两个数mmm和nnn来识别）IV、输入字符串不会超过100Bytes，请不用考虑超长字符串的情况。示例输入：strIn=ab00cd+123fght456-253.005fgh输出：n=6outArray=0,123,456,25,3,5IP地址匹配（60分）问

15、题描述：在路由器中，一般来说转发模块采用最大前缀匹配原则进行目的端口查找，具体如下：IP地址和子网地址匹配：IP地址和子网地址所带掩码做AND运算后，得到的值与子网地址相同，则该IP地址与该子网匹配。比如：IP地址：192.168.1.100子网：192.168.1.0/255.255.255.0，其中192.168.1.0是子网地址，255.255.255.0是子网掩码。192.168.1.100&255.255.255.0=192.168.1.0，则该IP和子网192.168.1.0匹配IP地址：192.168.1.100子网：192.168.1.128/255.255.255.19219

16、2.168.1.100&255.255.255.192=192.168.1.64，则该IP和子网192.168.1.128不匹配最大前缀匹配：任何一个IPv4地址都可以看作一个32bit的二进制数，比如192.168.1.100可以表示为：11000000.10101000.00000001.01100100，192.168.1.0可以表示为11000000.10101000.00000001.00000000最大前缀匹配要求IP地址同子网地址匹配的基础上，二进制位从左到右完全匹配的位数尽量多（从左到右子网地址最长）。比如：IP地址192.168.1.100，同时匹配子网192.168.1.0

17、/255.255.255.0和子网192.168.1.64/255.255.255.192，但对于子网192.168.1.64/255.255.255.192，匹配位数达到26位，多于子网192.168.1.0/255.255.255.0的24位，因此192.168.1.100最大前缀匹配子网是192.168.1.64/255.255.255.192。请编程实现上述最大前缀匹配算法。要求实现函数：voidmax_prefix_match(constchar*ip_addr,constchar*net_addr_array,int*n)【输入】ip_addr：IP地址字符串，严格保证是合法IPv

18、4地址形式的字符串net_addr_array：子网地址列表，每一个字符串代表一个子网，包括子网地址和掩码，表现形式如上述，子网地址和子网掩码用/分开，严格保证是合法形式的字符串；如果读到空字符串，表示子网地址列表结束【输出】n：最大前缀匹配子网在*net_addr_array数组中对应的下标值。如果没有匹配返回-1示例输入：ip_addr=192.168.1.100net_addr_array=192.168.1.128/255.255.255.192,192.168.1.0/255.255.255.0,192.168.1.64/255.255.255.192,0.0.0.0/0.0.0.0

19、,输出：n=2#include#includevoidtake_num(constchar*strIn,int*n,unsignedint*outArray)constchar*p=strIn;intnext=0;*n=0;outArray0=0;assert(p&n&outArray);for(p=strIn;*p;p+)if(0=*p)&(*p=9)outArray*n=(outArray*n*10)+(*p)-0);next=1;/*后面还有*/elseif(next=1)(*n)+;next=0;voidmax_prefix_match(constchar*ip_addr,constc

20、har*net_addr_array,int*n)intip,tar_net,tar_mask;/*ip地址*/intip_it4,net_it4,mask_it4;char*p;intindex,max_index,cur_bits,max_bits=0,bit;*n=-1;sscanf(ip_addr,%d.%d.%d.%d,&ip_it0,&ip_it1,&ip_it2,&ip_it3);ip=(ip_it024)+(ip_it116)+(ip_it28)+ip_it3);for(index=0;net_addr_arrayindex0!=0;index+)/*获取网络号和掩码*/p=n

21、et_addr_arrayindex;sscanf(p,%d.%d.%d.%d/%d.%d.%d.%d,&net_it0,&net_it1,&net_it2,&net_it3,&mask_it0,&mask_it1,&mask_it2,&mask_it3);tar_mask=(mask_it024)+(mask_it116)+(mask_it28)+mask_it3);tar_net=(net_it024)+(net_it116)+(net_it28)+net_it3);if(tar_mask)&(ip)=(tar_net)cur_bits=0;/*计算1的个数*/for(bit=0;bit=

22、1;if(cur_bitsmax_bits)max_bits=cur_bits;max_index=index;if(max_bits!=0)*n=max_index;intmain()inti,n,arrayOut100=0;char*strIn=ab00cd+123fght456-253.005fgh;char*ip_addr=192.168.1.100;char*net_addr_array1024=192.168.1.128/255.255.255.192,192.168.1.0/255.255.255.0,192.168.1.64/255.255.255.192,0.0.0.0/0.

23、0.0.0,;take_num(strIn,&n,arrayOut);printf(:input:%snoutput:%dn,strIn,n);for(i=0;in;i+)printf(%dn,arrayOuti);max_prefix_match(ip_addr,net_addr_array,&n);if(n!=-1)printf(max:%d%s,n,net_addr_arrayn);return0;4、 数组比较（20分）问题描述：比较两个数组，要求从数组最后一个元素开始逐个元素向前比较，如果2个数组长度不等，则只比较较短长度数组个数元素。请编程实现上述比较，并返回比较中发现的不相等元素

24、的个数比如：数组1,3,5和数组77,21,1,3,5按题述1.数组比较（20分）问题描述：比较两个数组，要求从数组最后一个元素开始逐个元素向前比较，如果2个数组长度不等，则只比较较短长度数组个数元素。请编程实现上述比较，并返回比较中发现的不相等元素的个数比如：数组1,3,5和数组77,21,1,3,5按题述要求比较，不相等元素个数为0数组1,3,5和数组77,21,1,3,5,7按题述要求比较，不相等元素个数为3要求实现函数：intarray_compare(intlen1,intarray1,intlen2,intarray2)【输入】intlen1：输入被比较数组1的元素个数；intar

25、ray1：输入被比较数组1；intlen2：输入被比较数组2的元素个数；intarray2：输入被比较数组2；【输出】无【返回】不相等元素的个数，类型为int示例:1）输入：intarray1=1,3,5，intlen1=3，intarray2=77,21,1,3,5，intlen2=5函数返回：02）输入：intarray1=1,3,5，intlen1=3，intarray2=77,21,1,3,5,7，intlen2=6函数返回：35、 约瑟夫问题问题描述：输入一个由随机数组成的数列（数列中每个数均是大于0的整数，长度已知），和初始计数值m。从数列首位置开始计数，计数到m后，将数列该位置数

26、值替换计数值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，计数过程完成。输出数值出列顺

27、序为：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,46、 简单四则运算问题描述：输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值注：3.1、表达式只含+,-,*,/四则运算符，

28、不含括号3.2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况3.3、要考虑加减乘除按通常四则运算规定的计算优先级3.4、除法用整数除法，即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生3.5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况要求实现函数：intcalculate(intlen,char*expStr)【输入】intlen:字符串长度；char*expStr:表达式字符串；【输出】无【返回】计算结果示例:1）输入：char*expStr=“1+4*5-8/3

29、”函数返回：192）输入：char*expStr=“8/3*3”函数返回：67、 过滤输入字符串中的重复字符./*请按照要求实现下列函数*/*过滤输入字符串中的重复字符,假设输入google,输出应为gole*/voidchangeStr(constchar*pIn,char*pOut)/统计目前为止不重复字符,初始值为1/初始时,输入串第一个字符加入输出串intcount=1;/统计目前为止不重复字符/*扫描输入串,查看输入串中字符是否存在于输出串若存在,则继续扫描若当前输入串字符与所有输出串中字符比较过后,未有相同的字符则加入到输出串中.*/for(inti=1;istrlen(pIn);

30、i+)for(intj=0;jcount;j+)if(pIni=pOutj)break;elseif(j=count-1)pOutcount+=pIni;/输出串中保存的非重复字符后一个字符置为0/以结束字符串pOutcount=0;8、 给定一个数组input，如果数组长度n为奇数，则将数组中最大的元素放到output数组最中间的位置，如果数组长度n为偶数，则将数组中最大的元素放到output数组中间两个位置偏右的那个位置上，然后再按从大到小的顺序，依次在第一个位置的两边，按照一左一右的顺序，依次存放剩下的数。例如：input=3,6,1,9,7output=3,7,9,6,1;input=

31、3,6,1,9,7,8output=1,6,8,9,7,31#include2#include3usingnamespacestd;4#defineSIGN(x)(x)=0)?(1):(-1)5#defineN56intInputN=3,6,1,9,7;7intOutputN;89voidformatIO(int*input,int*output,intn)1011intm=(N1);12intslid=-1;13if(N&0x01=0)1415m+=1;1617outputm=InputN-1;18for(inti=N-2;i=0;i-)1920outputm+slid=inputi;21if(slid0)slid=-(slid+1);22elseslid=-(slid);23242526intmain()2728sort(Input,Input+N);/从小到大排序29formatIO(Input,Output,N);30for(inti=0;iN;i+)3132coutOutputi,;3334cout=2的相同子串，如果包含，返回1，不包含，返回0；例如：输入12312，包含两个“12”子串，返回1.输入1223122，包含两个“122”子串，返回1.-