2011年华为校园招聘上机试题及答案1. 数组比较（20分）问题描述：比较两个数组，要求从数组最后一个元素开始逐个元素向前比较，如果2个数组长度不等，则只比较较短长度数组个数元素。

请编程实现上述比较，并返回比较中发现的不相等元素的个数比如：数组{1,3,5}和数组{77,21,1,3,5}按题述要求比较，不相等元素个数为0数组{1,3,5}和数组{77,21,1,3,5,7}按题述要求比较，不相等元素个数为3要求实现函数：int array_compare(int len1, int array1[], int len2, int array2[])【输入】int len1：输入被比较数组1的元素个数；int array1[]：输入被比较数组1；int len2：输入被比较数组2的元素个数；int array2[]：输入被比较数组2；【输出】无【返回】不相等元素的个数，类型为int示例1）输入：int array1[] = {1,3,5}，int len1 = 3，int array2[] = {77,21,1,3,5}，int len2 = 5函数返回：02）输入：int array1[] = {1,3,5}，int len1 = 3，int array2[] = {77,21,1,3,5,7}，int len2 = 6函数返回：３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。

•要求实现函数：void array_iterate(int len, int input_array[], int m, int output_array[])【输入】int len：输入数列的长度；int intput_array[]：输入的初始数列int m：初始计数值【输出】int output_array[]：输出的数值出列顺序【返回】无•示例输入：int input_array[] = {3,1,2,4}，int len = 4，m=7输出：output_array[] = {2,3,1,4}3. 简单四则运算•问题描述：输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值注：1、表达式只含+, -, *, / 四则运算符，不含括号2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况3、要考虑加减乘除按通常四则运算规定的计算优先级4、除法用整数除法，即仅保留除法运算结果的整数部分。

比如8/3=2。

输入表达式保证无0作为除数情况发生5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况•要求实现函数：int calculate(int len,char *)【输入】int len: 字符串长度；char *: 表达式字符串；【输出】无【返回】计算结果•示例1）输入：char * = “1+4*5-8/3”函数返回：192）输入：char *= “8/3*3”函数返回：61. #include <stdio.h>2.3. /*4. * author by wanww5. * time: 2011-09-076. */7. u sing namespace std;8.9. i nt array_compare(int len1, int array1[], int len2, int array2[])10. {11. if(len1 == len2) {12. int count = 0;13. for (int i=0;i<len1;i++)14. {15. if(array1[i]!=array2[i]) count++;16. }17. return count;18. } else if(len1<len2) {19. return array_compare(len1, array1,len1,array2+len2-len1);20.21. } else {22. return array_compare(len2,array1+len1-len2,len2,array2);23. }24. }25.26. void array_iterate(int len, int input_array[], int m,int output_array[])27. {28. int * flag = new int[len];29. memset(flag,0,len*4);30. int hasout=0; //已经出列的数字个数31. int start = 0; //开始的下标号32. int j=0; //当前以报到的数字33.34. while(true)35. {36. if(flag[start] == 0) //当前元素还没出列37. {38. j++;39. if(j==m) //已经计数到m,当前start下标的元素出列40. {41. output_array[hasout] = input_array[start];42. flag[start] = 1; //标记当前元素已经出列43.44. hasout ++;45. if(hasout == len) break; //所有的元素都已经出列，结束程序46.47. //初始化下一轮的数字48. j = 0;49. m = input_array[start];50. }51.52. }53.54. start ++;55. if(start==len) start = 0;56.57. }58.59. delete [] flag;60.61. }62.63. int calculate(int len,char *expStr)64. {65. struct {66. char opdata[200];67. int top;68. }opstack;69. //定义操作符栈70.71. opstack.top = -1;72.73. int i=0;//遍历字符串的下标74. int t=0;//当前后缀表达式的长度75.76. char ch = expStr[i];77.78. while (ch!='\0')79. {80. switch (ch)81. {82. case '+':83. case '-':84. while (opstack.top != -1)85. {86. expStr[t] = opstack.opdata[opstack.top];87. opstack.top--;88. t++;89. }90. opstack.top++;91. opstack.opdata[opstack.top] = ch;92. break;93. case '*':94. case '/':95. while (opstack.top != -1 && (opstack.opdata[opstack.top] =='*' || opstack.opdata[opstack.top] =='/') )96. {97. expStr[t] = opstack.opdata[opstack.top];98. opstack.top--;99. t++;100. }101. opstack.top++;102. opstack.opdata[opstack.top] = ch;103. break;104. default:105. expStr[t] = ch;106. t++;107. break;108. }109. i++;110. ch = expStr[i];111. }112.113. while (opstack.top != -1)//将栈中所有的剩余的运算符出栈114. {115. expStr[t] = opstack.opdata[opstack.top];116. opstack.top--;117. t++;118. }119.120. expStr[t]='\0';121.122.123. struct {124. int numeric[200];125. int top;126. }data;127.128. data.top = -1;129.130. i=0;131. ch = expStr[i];132.133.134. while (ch!='\0')135. {136. if (ch>='0' && ch <= '9' )137. {138. data.top++;139. data.numeric[data.top] = ch-'0';140. }141. else if('+' == ch)142. {143. int tmp = data.numeric[data.top-1] + data.numeric[data.top]; 144. data.top--;145. data.numeric[data.top] = tmp;146. }147. else if('-' == ch)148. {149. int tmp = data.numeric[data.top-1] - data.numeric[data.top]; 150. data.top--;151. data.numeric[data.top] = tmp;152. }153. else if('*' == ch)154. {155. int tmp = data.numeric[data.top-1] * data.numeric[data.top]; 156. data.top--;157. data.numeric[data.top] = tmp;158. }159. else if('/' == ch)160. {161. if(data.numeric[data.top] == 0)162. {163. printf("cannot be zero of the divide\n");164. exit(1);165. }166. int tmp = data.numeric[data.top-1] / data.numeric[data.top];167. data.top--;168. data.numeric[data.top] = tmp;169. }170. i++;171. ch = expStr[i];172. }173.174. return data.numeric[data.top];175. }176.177.178.179.180. void main()181. {182.183. int array1[] = {1,3,5};184. int len1 = 3;185. int array2[] = {77,21,1,3,5,7};186. int len2 = 6;187. int count = array_compare(sizeof(array1)/sizeof(int),array1,sizeof(array2 )/sizeof(int),array2);188. printf("%d\n",count);189.190. printf("*****************************************************\n");191.192. int input_array[] = {3,1,2,4};193. int len = 4;194. int m=7;195.196. int * output_array = new int[sizeof(input_array)/sizeof(int)];197.198. array_iterate(4,input_array,7,output_array);199.200. for (int i=0;i<sizeof(input_array)/sizeof(int);i++)201. {202. printf("%d ",output_array[i]);203. }204.205.206. delete [] output_array;207.208. printf("\n*****************************************************\n"); 209.210. char expStr[] = "8/3*3";211.212.213. int result = calculate(strlen(expStr),expStr);214.215. printf("%s\n",expStr);216. printf("%d\n",result);217.218.219.220. }。