华为机试题目教学内容.doc
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.hviewplaincopytoclipboardprint?1. #ifndef LINKLIST_H 2. #define LINKLIST_H 3. typedef int ElemType; 4. typedef struct LNode 5. 6. ElemType *data; 7. struct LNode *next; 8. int length; 9. LNode, *LinkList; 10. LinkList initList(); 11. void insertList(LinkList l, ElemType *data, int sizeOfData); 12. int length(LinkList l); 13. void reverse(LinkList l); 14. #endif LinkList.cviewplaincopytoclipboardprint?1. #include "LinkList.h" 2. #include <stdlib.h> 3. #include <string.h> 4. /* 5. / Method: initList 6. / FullName: initList 7. / Access: public 8. / Returns: LinkList 9. / Qualifier: 10. /* 11. LinkList initList() 12. 13. LinkList l = 0; 14. l = (LinkList)malloc(sizeof(LNode); 15. if(l = NULL) 16. return NULL; 17. l->data = 0; 18. l->next = NULL; 19. l->length = 0; 20. return l; 21. 22. /* 23. / Method: insertList 24. / FullName: insertList 25. / Access: public 26. / Returns: void 27. / Qualifier: 28. / Parameter: LinkList l 29. / Parameter: ElemType * data 30. / Parameter: int sizeOfData 31. /* 32. void insertList(LinkList l, ElemType *data, int sizeOfData) 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->next; 49. l->next = n; 50. l->length+; 51. 52. /* 53. / Method: length 54. / FullName: length 55. / Access: public 56. / Returns: int 57. / Qualifier: 58. / Parameter: LinkList l 59. /* 60. int length(LinkList l) 61. 62. if(l = NULL) 63. return 0; 64. return l->length; 65. 66. /* 67. / Method: reverse 68. / FullName: reverse 69. / Access: public 70. / Returns: void 71. / Qualifier: 72. / Parameter: LinkList l 73. /* 74. void reverse(LinkList l) 75. 76. LinkList p, 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.cviewplaincopytoclipboardprint?1. #include "LinkList.h" 2. #include <stdio.h> 3. int main() 4. 5. ElemType num1 = 1, num2 = 2, num3 = 3; 6. LinkList l = initList(); 7. LinkList l2 = initList(); 8. insertList(l, &num1, sizeof(ElemType); 9. insertList(l, &num2, sizeof(ElemType); 10. insertList(l, &num3, sizeof(ElemType); 11. reverse(l); 12. return 0; #include<stdio.h>#include<stdlib.h>#include<time.h>struct_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;while(idx<maxIdx-1)for(pTemp=head;idx<maxIdx-1;pTemp=pTemp->next,+idx)if(pTemp->data>pTemp->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;i<20;+i)temp=(Node*)malloc(sizeof(Node);temp->data=rand()%40;p->next=temp;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;intlQuotient=0;lQuotient=lNum;while(1)lOver=lOver*10+lQuotient%10;lQuotient=lQuotient/10;if(lQuotient=0)break;/printf("lNum=<%d>n",lNum);/printf("lNum=<%d>n",lOver);if(lNum=lOver)/判断反序之后的数与原来的数是否相等result=1;elseresult=0;return0;intmain(void)intnum;intresult=0;while(1)printf("Enteranumber:");scanf("%d",&num);PrintNum(num,result);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、不考虑字符串中出现的正负号(+,-)，即所有转换结果为非负整数（包括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分）问题描述：在路由器中，一般来说转发模块采用最大前缀匹配原则进行目的端口查找，具体如下：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.192192.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/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地址字符串，严格保证是合法IPv4地址形式的字符串net_addr_array：子网地址列表，每一个字符串代表一个子网，包括子网地址和掩码，表现形式如上述，子网地址和子网掩码用/分开，严格保证是合法形式的字符串；如果读到空字符串，表示子网地址列表结束【输出】n：最大前缀匹配子网在*net_addr_array数组中对应的下标值。如果没有匹配返回-1示例输入：ip_addr="192.168.1.100"net_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",""输出：n=2#include<stdio.h>#include<assert.h>voidtake_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,constchar*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_it0<<24)+(ip_it1<<16)+(ip_it2<<8)+ip_it3);for(index=0;net_addr_arrayindex0!='0'index+)/*获取网络号和掩码*/p=net_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_it0<<24)+(mask_it1<<16)+(mask_it2<<8)+mask_it3);tar_net=(net_it0<<24)+(net_it1<<16)+(net_it2<<8)+net_it3);if(tar_mask)&(ip)=(tar_net)cur_bits=0;/*计算1的个数*/for(bit=0;bit<sizeof(tar_mask)*8;bit+)cur_bits+=tar_mask&1;tar_mask>>=1;if(cur_bits>max_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.0.0.0",""take_num(strIn,&n,arrayOut);printf("<1>:input:%snoutput:%dn",strIn,n);for(i=0;i<n;i+)printf("%dn",arrayOuti);max_prefix_match(ip_addr,net_addr_array,&n);if(n!=-1)printf("<2>max:%d%s",n,net_addr_arrayn);return0;4、 数组比较（20分）问题描述：比较两个数组，要求从数组最后一个元素开始逐个元素向前比较，如果2个数组长度不等，则只比较较短长度数组个数元素。请编程实现上述比较，并返回比较中发现的不相等元素的个数比如：数组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的元素个数；intarray1：输入被比较数组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后，将数列该位置数值替换计数值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,46、 简单四则运算问题描述：输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值注：3.1、表达式只含+,-,*,/四则运算符，不含括号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”函数返回：192）输入：char*expStr=“8/3*3”函数返回：67、 过滤输入字符串中的重复字符./* 请按照要求实现下列函数 */ /* 过滤输入字符串中的重复字符 , 假设输入 google , 输出应为 gole */ void changeStr(const char *pIn, char *pOut) /统计目前为止不重复字符,初始值为1 /初始时, 输入串第一个字符加入输出串 int count = 1; /统计目前为止不重复字符 /* 扫描输入串, 查看输入串中字符是否存在于输出串 若存在, 则继续扫描 若当前输入串字符与所有输出串中字符比较过后, 未有相同的字符 则加入到输出串中. */ for(int i=1; i<strlen(pIn); i+) for(int j=0; j<count; j+) if(pIni = pOutj) break; else if(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=3,6,1,9,7,8output=1,6,8,9,7,31 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 #define SIGN(x) (x)>=0)?(1):(-1) 5 #define N 5 6 int InputN=3, 6, 1, 9, 7; 7 int OutputN; 8 9 void formatIO(int* input,int* output,int n)10 11 int m=(N>>1);12 int slid=-1;13 if(N&0x01=0)14 15 m+=1;16 17 outputm=InputN-1;18 for(int i=N-2;i>=0;i-)19 20 outputm+slid=inputi;21 if(slid>0)slid=-(slid+1);22 else slid=-(slid);23 24 25 26 int main()27 28 sort(Input,Input+N);/从小到大排序29 formatIO(Input,Output,N);30 for(int i=0;i<N;i+)31 32 cout<<Outputi<<","33 34 cout<<endl;35 return 1;36 10、第二题：输入一个数，把它作为一个串，判断其中是否包含长度>=2的相同子串，如果包含，返回1，不包含，返回0；例如：输入12312，包含两个“12”子串，返回1. 输入1223122，包含两个“122”子串，返回1.-
