我来说说华为机试.docx

我来说说华为机试.docx

《我来说说华为机试.docx》由会员分享，可在线阅读，更多相关《我来说说华为机试.docx（42页珍藏版）》请在冰点文库上搜索。

我来说说华为机试

受乔哥的启发，决定写一个关于华为机试的简介，首先声明本人并非大牛，也无权拿到华为的内部资料，以下内容大部分源自网络，还有一部分是自己的感悟，本文以整理和疏导为主。

由于我不会JAVA，在这也就不写JAVA的东西了吧，下面的内容以C/C++为主。

分为几个部分：

第一部分是华为机试流程、题型等相关介绍，第二部分是一些经典题目的剖些，第三部分是一些提示和建议。

一、华为机试介绍

1.大致介绍

时间：

120分钟

环境：

VisualStudio（去年是vs2005）、VisualC++、Eclipse（Java）

题量：

共3题

初级题——60分——3组测试数据

中级题——100分——5组测试数据

高级题——160分——8组测试数据

注：

初级题和中级题为必答题，高级题为附加题。

提交次数：

每题最多5次

评判方式：

按通过测试数据组数给分，每通过一组得20分

2.考试说明

这里有一个老版的机试考试说明，供大家参考：

C/C++，JAVA机试流程：

①打开IE浏览器，输入机试系统IP地址（以当天告知的地址为准）；

②输入姓名、手机，选择“C/C++”或“JAVA”，登录；

③登录后显示题目，阅读题目并点击页面最下方“下载框架文件”，将文件解压到D盘；

④用VC6.0或Eclipse打开工程工程；

⑤补充函数体、调试；

⑥将工程压缩打包；

⑦返回IE浏览器中的试题页面，点击最下方的“提交”按钮，完成提交。

3.注意事项

华为的机试阅卷为电脑自动阅卷，大致流程是输入测试数据，判断结果是否正确，所以，在编写好程序后，一定要多测试几组数据，至少要保证题目中测试数据输入后，结果符合题目要求。

二、经典题目剖析

1.在分析具体题目之前，有几个注意事项说一下：

1）同学们平时写代码的编译环境不太一样，大致有GCC/G++，VC，VS，在这几种之中又细分了好多个版本，但是既然是准备华为机试，那么就装个最简单的VS2005吧，只要代码在这个版本上通过，相信机试的时候也不会出问题。

2）现在很多新旧编程标准交织，这几年还有很实用的C++11，但是为了机试，这些还是先别秀吧，你问为什么有这么好的东西却不让用？

因为VS2005不支持呗，类似的还有atoi（）,itoa（）这些局限于编译环境的函数也最好别用。

2.机试的时候分为3类题：

3）初级题——多为简单字符串处理或数字操作

4）中级题——在考察编程语言能力的基础上加入一定简单的算法和数据结构。

5）高级题——更多的算法和数据结构要求，代码量明显增大，栈、图、树、查找、搜索都在考察范围内。

3.具体题目（以下所有代码本人均在VS2005环境上编译测试通过）

1）排序方法总结

题1:

排序是编程语言里最基本的方法，目前典型的排序方法有：

冒泡排序、快速排序、选择排序、简单插入排序、二分插入排序、希尔排序、归并排序等。

既然是基础，那么就必然要了然于心。

代码见：

1.cpp（打开：

Ctrl+鼠标左键点击）

排序算法这么多，比较麻烦，但是思想一定要了然于心，说不定面试的时候就会让你写个排序算法看看呢？

但是如果我们只是在程序中用到一个排序的功能，大可不必话费很长的时间去写这些排序算法，C++中给出了一个sort函数，非常方便，大家可以去了解一下，因为使用起来非常简单，并且在接下来的题目中会用到，在这就不多讲了。

题2:

输入10个数字，按各个位上的和从小到大排序，如果相同，则按数字从小到大排序。

输入描述:

10个正整数，保证都在int范围内，用空格隔开

输出描述:

10个数字，其从大到小的值，用空格隔开，最后一个数字后不加空格

输入样例113245987106

输出样例102113456789

代码见：

2.cpp

题3:

操作系统任务调度问题。

操作系统任务分为系统任务和用户任务两种。

其中，系统任务的优先级<50，用户任务的优先级>=50且<=255。

优先级大于255的为非法任务，应予以剔除。

现有一任务队列task[]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。

函数scheduler实现如下功能，将task[]中的任务按照系统任务、用户任务依次存放到system_task[]数组和user_task[]数组中（数组中元素的值是任务在task[]数组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。

例如：

task[]={0,30,155,1,80,300,170,40,99}   system_task[]={0,3,1,7,-1}   user_task[]={4,8,2,6,-1}

代码见：

3.cpp

题4:

输入一组身高在170到190之间（5个身高），比较身高差，选出身高差最小的两个身高；若身高差相同，选平均身高高的那两个身高；从小到大输出；

如：

输入170181173186190输出170173

代码见：

4.cpp

2）求最大、最小数

题5:

输入整型数组求数组的最小数和最大数之和，例如输入1,2,3,4则输出为5，当输入只有一个数的时候，则最小数和最大数都是该数，例如只输入1，则输出为2；数组的长度不超过50。

代码见：

5.cpp

题6:

输入一串字符，只包含“0-10”和“，”找出其中最小的数字和最大的数字（可能不止一个），输出最后剩余数字个数。

代码见：

6.cpp

相信通过题2、题3，在找最大、最小数时，不论是数组还是字符类型都可以轻松应对了。

3）链表

题7：

一组人（7个），围成一圈，从某人开始数到第3个的人出列，再接着从下一个人开始数，依次输出出列的人。

（报数：

共n个人从1编号，设从第s个人报号，报到m出队，依次输出出队的人。

）

代码见：

7.cpp

约瑟夫环是一个数学的应用问题：

已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。

从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，这题既可以使用循环列表又可以使用数组在程序中两种方法都罗列了。

题8：

出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现。

代码见：

8.cpp

如果这题能够轻松地写出，那么单项列表的知识就算是基本掌握了。

4）大数、高精度数运算。

题9:

求两个长长整型的数据的和并输出。

代码见：

9.cpp

题10:

在计算机中，由于处理器位宽限制，只能处理有限精度的十进制整数加减法，比如在32位宽处理器计算机中，参与运算的操作数和结果必须在-231~231-1之间。

如果需要进行更大范围的十进制整数加法，需要使用特殊的方式实现，比如使用字符串保存操作数和结果，采取逐位运算的方式。

如下：

9876543210+1234567890=?

让字符串num1="9876543210"，字符串num2="1234567890"，结果保存在字符串result="11111111100"。

-9876543210+（-1234567890）=?

让字符串num1="-9876543210"，字符串num2="-1234567890"，结果保存在字符串result="-11111111100"。

要求编程实现上述高精度的十进制加法。

代码见：

10.cpp

上面两题，分别实现了正大数的加运算，大数的加运算，相信完全吃透后再编写大数运算的程序就不是问题了。

题11:

输入两行字符串正整数，第一行是被减数，第二行是减数，输出第一行减去第二行的结果。

代码见：

11.cpp

5）字符串常见操作

题12:

通过键盘输入一串小写字母（a~z）组成的字符串。

请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。

比如字符串“abacacde”过滤结果为“abcde”。

代码见：

12.cpp

题13:

通过键盘输入一串小写字母（a~z）组成的字符串。

请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。

压缩规则：

1.仅压缩连续重复出现的字符。

比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc".

2.压缩字段的格式为"字符重复的次数+字符"。

例如：

字符串"xxxyyyyyyz"压缩后就成为"3x6yz"

代码见：

13.cpp

题14:

删除子串，只要是原串中有相同的子串就删掉，不管有多少个都删除，返回子串个数。

输入字符串为：

123abc12de234fg1hi34j123k，子串为：

123

则输出为：

abc12de234fg1hi34jk2

代码见：

14.cpp

题15:

将输入的字符串（字符串仅包含小写字母‘a’到‘z’），按照如下规则，循环转换后输出：

a->b,b->c,…,y->z,z->a；若输入的字符串连续出现两个字母相同时，后一个字母需要连续转换2次。

例如：

aa转换为bc，zz转换为ab；当连续相同字母超过两个时，第三个出现的字母按第一次出现算。

代码见：

15.cpp

题16：

在给定字符串中找出单词（“单词”由大写字母和小写字母字符构成，其他非字母字符视为单词的间隔，如空格、问号、数字等等；另外单个字母不算单词）；找到单词后，按照长度进行降序排序，（排序时如果长度相同，则按出现的顺序进行排列），然后输出到一个新的字符串中；如果某个单词重复出现多次，则只输出一次；如果整个输入的字符串中没有找到单词，请输出空串。

输出的单词之间使用一个“空格”隔开，最后一个单词后不加空格。

代码见：

16.cpp

题17:

字符串单词首字母转换成大写

举例：

输入：

thisisabook

返回：

ThisIsABook

代码见：

17.cpp

题18:

通过键盘输入任意一个字符串序列，字符串可能包含多个子串，子串以空格分隔。

请编写一个程序，自动分离出各个子串，并使用’,’将其分隔，并且在最后也补充一个’,’并将子串存储。

  如果输入“abcdefghi    d”，结果将是abc,def,gh,i,d。

代码见：

18.cpp

题19:

输入一个字符串，删除其中所有的数字，所有大写字母改成小写，其他不变，并输出。

代码见：

19.cpp

题20：

编写一个字符串替换函数，如：

“ABCDEFGHIJKLMNOPQRSTUVWXYZ”这个字符串，把其中的“RST”替换为“ggg”这个字符串，结果就变成了：

ABCDEFGHIJKLMNOPQgggUVWXYZ

代码见：

20.cpp

题21:

写一个程序实现功能：

将两个字符串合并为一个字符串并且输出，用指针实现。

代码见：

21.cpp

题22:

给定一个字符串,实现一个函数,按下述方式输出字符串：

如果此字符的下一个字符和此字符不一样，原样输出此字符，否则先输出此字符，再输出此字符连续出现的次数（次数不大于9）。

例如,字符串ABBCCCDEDFFF，输出的结果为AB2C3DEDF3。

不用考虑溢出问题，不能使用任何I/O函数。

代码见：

22.cpp

题23:

字符串匹配问题，给定两个字符串，求字符串2，在字符串1中的最先匹配结果。

字符串2中可以存在'*'符号，且该符号可以代表任意字符，即字符串2中存在通配符。

e.g.输入：

abcdefghabef,a*f输出：

abcdef

代码见：

23.cpp

题24:

输入m个字符串 和一个整数n, 把字符串M化成以N为单位的段，不足的位数用0补齐。

如 n=8 m=9 ，

123456789划分为：

1234567890000000

123化为 ：

12300000

代码见：

24.cpp

题25:

统计字符串中数字出现的次数，最大次数的统计出来

举例：

输入：

323324423343输出：

3,6

代码见：

25.cpp

题26:

输入一段英文文本，用程序统计出现频率最高和最低的两个单词;

英文文本中仅出现这四类字符：

空格（）、英文逗号（,）、英文句号（.）、英文大小写字母（a-z、A-Z）

单词之间的分隔符仅考虑这三种：

空格（）、英文逗号（,）、英文句号（.）;

仅大小写不同的单词算同一个单词；

如果两个单词出现次数相同，则在文本中首次出现的单词优先返回。

返回的单词统一用小写字母返回

例如：

输入字符串“Helloworld,isaidhelloworldtotheworld”，返回“world”,“i”

代码见：

26.cpp

题27:

将整数倒序输出，剔除重复数据

输入一个整数，如12336544，或1750，然后从最后一位开始倒过来输出，最后如果是0，则不输出，输出的数字是不带重复数字的，所以上面的输出是456321和571。

如果是负数，比如输入-175，输出-571。

代码见：

27.cpp

以上题目基本可以概括字符串的基本考察点：

找单词、替换字符、排序、分割、删除、统计字符或单词出现次数等。

题28：

名字的漂亮度=26*字母个数最多的+25*字母个数其次的+24*字母个数再其次的（忽略大小写）+....+1*出现次数最小的。

输入：

整数N，N个字符串

输出：

N个字符串漂亮度

例如：

输入1a输出26

代码见：

28.cpp

6）数组操作

题29:

判断是否为回文数组（无论从左到右还是从右到左读出来都一样的）。

代码见：

29.cpp

题30:

比较两个数组，要求从数组最后一个元素开始逐个元素向前比较，如果2个数组长度不等，则只比较较短长度数组个数元素。

请编程实现上述比较，并返回比较中发现的不相等元素的个数

比如：

数组{1,3,5}和数组{77,21,1,3,5}按题述要求比较，不相等元素个数为0

数组{1,3,5}和数组{77,21,1,3,5,7}按题述要求比较，不相等元素个数为3

代码见：

30.cpp

题31:

如果数组长度n为奇数，则将数组中最大的元素放到output[]数组最中间的位置，如果数组长度n为偶数，则将数组中最大的元素放到output[]数组中间两个位置偏右的那个位置上，然后再按从大到小的顺序，依次在第一个位置的两边，按照一左一右的顺序，依次存放剩下的数。

例如：

input[]={3,6,1,9,7}  output[]={3,7,9,6,1};            

input[]={3,6,1,9,7,8}   output[]= {1,6,8,9,7,3}

代码见：

31.cpp

题32:

算分数，去掉一个最高分一个最低分，求平均分。

代码见：

32.cpp

题33:

找出一个数组中满足2^N的元素。

例如：

输入1,2,3,5,7,8,16，则输出：

符合条件的有：

12816共4个

代码见：

33.cpp

题34:

求一个二维数组每列的最小值和二维数组的最小值。

代码见：

34.cpp

题35:

对一个数组，将数组中偶数从大到小排序，奇数从小到大排序,奇数和偶数交叉着放且输出数组第一位放奇数 若奇数和偶数不等长，则把剩下的直接放到数组中。

代码见：

35.cpp

题36:

求两个整型数组的异集，即A+B-（A与B的交集）。

例如a[]={1,2,3,4,5},b[]={2,3}，则a,b的异集为{1,4,5}。

代码见：

36.cpp

题37:

给定一个n*m的矩阵，请编程实现以逆时针旋转方式打印出它的每个元素，例如输入矩阵

187

296

345

则输出为123456789。

代码见：

37.cpp

通过上述几题，包含的知识点有数组排序、转置、求特殊集合、按特定顺序输出、多维数组的使用和操作等。

7）四则运算

题38:

通过键盘输入100以内正整数的加、减运算式，请编写一个程序输出运算结果字符串。

输入字符串的格式为：

“操作数1运算符操作数2”，“操作数”与“运算符”之间以一个空格隔开。

代码见：

38.cpp

题39:

输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值

注：

1、表达式只含 +, -, *, /,（,）, 四则运算符

2、表达式数值只包含个位整数（0-9），且不会出现0作为除数的情况

3、要考虑加减乘除按通常四则运算规定的计算优先级

4、除法用整数除法，即仅保留除法运算结果的整数部分。

比如8/3=2。

输入表达式保证无0作为除数情况发生

5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况

代码见：

39.cpp

题40:

两个任意长度的正数相减，这两个正数可以带小数点，也可以是整数，请输出结果。

输入的字符串中，不会出现除了数字与小数点以外的其它字符，不会出现多个小数点以及小数点在第一个字符的位置等非法情况，所以考生的程序中无须考虑输入的数值字符串非法的情况。

详细要求以及约束：

1.输入均为正数，但输出可能为负数；

2.输入输出均为字符串形式；

3.如果输出是正数则不需要带符号，如果为负数，则输出的结果字符串需要带负号

例如：

2.2-1.1直接输出为“1.1”，1.1-2.2则需要输出为“-1.1”

4.输出的结果字符串需要过滤掉整数位前以及小数位后无效的0，小数位为全0的，直接输出整数位

例如：

相减结果为11.345，此数值前后均不可以带0，“011.345”或者“0011.34500”等等前后带无效0的均视为错误输出。

例如1.1-1.1结果为0.0，则直接输出0。

代码见：

40.cpp

四则运算看似非常简单，但是如果将其与字符串、小数、整数、正数、负数混合，很可能是我们忽略掉一些特殊的情况而使程序出现BUG，所以要多加练习，并且写代码之前最好在纸上将可能出现的情况列出，这样可以使程序的条理更加清晰。

8）数的各种附属数

题41:

求一个正整数X的平方根Y，立方根Z。

代码见：

41.cpp

求平方根和立方根我们一般用牛顿迭代法，下面是对应的公式。

平方根迭代公式a（n+1）=（a（n）+Y/a（n））/2，其中Y为待求平方根。

立方根迭代公式a（n+1）={2a（n）+Z/{[a（n）]^2}}/3，其中Z为待求平方根。

题42:

我们把只包含因子2，3，5的数称为丑数，把1当作第一个丑数，求从小到大的第n个丑数（还有质素）

输入：

n输出：

第n个丑数。

代码见：

42.cpp

题43:

相关数：

判断比整数N小的数里，有多少个与7相关的数（比如7、14、17、27）。

只需要给出总的个数，不需要输出。

代码见：

43.cpp

题44：

任意输入两个整数，求他们的最大公约数和最小公倍数。

代码见：

44.cpp

求最大公约数的方法：

求差判定法和辗转相除法。

着重介绍辗转相除法，其原理是：

 以小数除大数，如果能整除，那么小数就是所求的最大公约数。

否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数。

依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。

求最小公倍数的方法：

首先求得最大公约数，最小公倍数=两数之积/最大公约数。

题45:

自守数是指一个数的平方的尾数等于该数自身的自然数。

例如：

252=625，762=5776，93762=87909376。

请求出n以内的自守数的个数。

代码见：

45.cpp

题46:

任何一个自然数m的立方均可写成m个连续奇数之和。

//　1^3=1

//　2^3=3+5

//　3^3=7+9+11

//　4^3=13+15+17+19

//编程实现：

输入一自然数n，求组成n^3的n个连续奇数。

代码见：

46.cpp

这里还少一个素数的计算，请大家自己去写一下。

9）匹配问题

题47:

10个学生考完期末考试评卷完成后，A老师需要划出及格线，要求如下：

（1）及格线是10的倍数；

（2）保证至少有60%的学生及格；

（3）如果所有的学生都高于60分，则及格线为60分

输入：

输入10个整数，取值0~100

输出：

输出及格线，10的倍数

代码见：

47.cpp

题48:

输入一串字符串，其中有普通的字符与括号组成（包括‘（’、‘）’、‘[’,']'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1.

代码见：

48.cpp

题49:

将第一行中含有第二行数的数输出并升序排序。

例如：

输入一行数字：

123 423 5645 875 186523

再输入第二行：

23

将第一行中含有第二行中“23”的数输出并排序

结果即：

123 423 186523

代码见：

49.cpp

题50:

将 电话号码 one two...nine zero翻译成1  2...9 0

中间会有double

例如输入：

OneTwoThree

输出：

123

输入：

OneTwoDoubleTwo

输出：

1222

输入：

1Two2输出：

ERROR

输入：

DoubleDoubleTwo输出：

ERROR

有空格，非法字符，两个Double相连，Double位于最后一个单词，都错误，输出：

ERROR

代码见：

50.cpp

题51:

编程的时候，if条件里面的“（”、“）”括号经常出现不匹配的情况导致编译不过，请编写程序检测输入一行if语句中的圆括号是否匹配正确。

同时输出语句中出现的左括号和右括号数量，如if（（a==1）&&（b==1））是正确的，而if（（a==1））&&（b==1））是错误的。

注意if语句的最外面至少有一对括号。

输入：

if（（a==1）&&（b==1））

输出：

RIGTH33

输入：

if（（a==1））&&（b==1））

输出：

WRONG34

代码见：

51.cpp

题52:

输入包括多个行数，首先给出整数N（1

如果给定文字中“t”（或“T”）的出现次数比“s”（或“S”）多，则可能为英文，否则可能为德文。

输出包括一行，如果输入文字可能为英文，则输出English，否则输出Deutsch。

代码见：

52.cpp

题53：

自从有了智能手机，时刻都要关心手机的电量。

你的任务很简单，用程序打印符号来表示当前手机的电量。

用10行和10列来表示电池的电量，同时在外围加上边框，每一行表示10%的电量。

假设还有60%的电量，则显示如下：

+----------+

|----------|

|----------|

|----------|

|----------|

|++++++++++|

|++++++++++|

|++++++++++|

|++++++++++|

|++++++++++|

|++++++++++|

+----------+

运行时间限制:

无限制

内存限制:

无限制

输入:

多组测试数据，第一行为测试数据组数N（N<10），紧接着是N行，每行一个数，表示电量，这个数值可能是0，10，20，30，40，50，60，70，80，90，100

输出:

每组数据输出一个电池的电量，每组数据之间用15个“=”隔开

代码见：

53.cpp