我来说说华为机试

1、受乔哥的启发，决定写一个关于华为机试的简介，首先声明本人并非大牛，也无权拿到华为的内部资料，以下内容大部分源自网络，还有一部分是自己的感悟，本文以整理和疏导为主。由于我不会JAVA，在这也就不写JAVA的东西了吧，下面的内容以C/C+为主。分为几个部分：第一部分是华为机试流程、题型等相关介绍，第二部分是一些经典题目的剖些，第三部分是一些提示和建议。一、华为机试介绍1.大致介绍时间：120分钟环境：Visual Studio(去年是vs2005)、Visual C+、Eclipse(Java)题量：共3题 初级题60分3组测试数据 中级题100分5组测试数据 高级题160分8组测试数据注：初级题

2、和中级题为必答题，高级题为附加题。提交次数：每题最多5次评判方式：按通过测试数据组数给分，每通过一组得20分2.考试说明这里有一个老版的机试考试说明，供大家参考： C/C+，JAVA机试流程：打开IE浏览器，输入机试系统IP地址（以当天告知的地址为准）；输入姓名、手机，选择“C/C+”或“JAVA”，登录；登录后显示题目，阅读题目并点击页面最下方“下载框架文件”，将文件解压到D盘；用VC6.0或Eclipse打开工程工程；补充函数体、调试；将工程压缩打包；返回IE浏览器中的试题页面，点击最下方的“提交”按钮，完成提交。3. 注意事项华为的机试阅卷为电脑自动阅卷，大致流程是输入测试数据，判断结果

3、是否正确，所以，在编写好程序后，一定要多测试几组数据，至少要保证题目中测试数据输入后，结果符合题目要求。二、经典题目剖析1.在分析具体题目之前，有几个注意事项说一下：1） 同学们平时写代码的编译环境不太一样，大致有GCC/G+，VC，VS，在这几种之中又细分了好多个版本，但是既然是准备华为机试，那么就装个最简单的VS2005吧，只要代码在这个版本上通过，相信机试的时候也不会出问题。2） 现在很多新旧编程标准交织，这几年还有很实用的C+11，但是为了机试，这些还是先别秀吧，你问为什么有这么好的东西却不让用？因为VS2005不支持呗，类似的还有atoi(), itoa() 这些局限于编译环境的函数

4、也最好别用。2.机试的时候分为3类题：3） 初级题多为简单字符串处理或数字操作4） 中级题在考察编程语言能力的基础上加入一定简单的算法和数据结构。5） 高级题更多的算法和数据结构要求，代码量明显增大，栈、图、树、查找、搜索都在考察范围内。3. 具体题目（以下所有代码本人均在VS2005环境上编译测试通过）1) 排序方法总结题1:排序是编程语言里最基本的方法，目前典型的排序方法有：冒泡排序、快速排序、选择排序、简单插入排序、二分插入排序、希尔排序、归并排序等。既然是基础，那么就必然要了然于心。代码见：1.cpp（打开：Ctrl + 鼠标左键点击）排序算法这么多，比较麻烦，但是思想一定要了然于心，

5、说不定面试的时候就会让你写个排序算法看看呢？但是如果我们只是在程序中用到一个排序的功能，大可不必话费很长的时间去写这些排序算法，C+中给出了一个sort函数，非常方便，大家可以去了解一下，因为使用起来非常简单，并且在接下来的题目中会用到，在这就不多讲了。题2:输入10个数字，按各个位上的和从小到大排序，如果相同，则按数字从小到大排序。 输入描述: 10个正整数，保证都在int范围内，用空格隔开 输出描述: 10个数字，其从大到小的值，用空格隔开，最后一个数字后不加空格 输入样例 11 3 2 4 5 9 8 7 10 6 输出样例 10 2 11 3 4 5 6 7 8 9代码见：2.cpp题

6、3:操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级 < 50，用户任务的优先级 >= 50且 <= 255。优先级大于255的为非法任务，应予以剔除。现有一任务队列task，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler实现如下功能，将task 中的任务按照系统任务、用户任务依次存放到 system_task 数组和 user_task 数组中（数组中元素的值是任务在task 数组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。 例如：task = 0, 30, 155, 1,

7、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个身高），比较身高差，选出身高差最小的两个身高；若身高差相同，选平均身高高的那两个身高；从小到大输出；如：输入 170 181 173 186 190 输出 170 173代码见：4.cpp2） 求最大、最小数题5: 输入整型数组求数组的最小数和最大数之和，例如输入1,2,3,4则输出为5，当输入只有一个数的时候，

8、则最小数和最大数都是该数，例如只输入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分别表示）围坐在一张圆

9、桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，这题既可以使用循环列表又可以使用数组在程序中两种方法都罗列了。题8：出一个链表和一个数k，比如链表123456，k=2，则翻转后214365，若k=3,翻转后321654，若k=4，翻转后432156，用程序实现。代码见：8.cpp如果这题能够轻松地写出，那么单项列表的知识就算是基本掌握了。4） 大数、高精度数运算。题9:求两个长长整型的数据的和并输出。代码见：9.cpp题10:在计算机中，由于处理器位宽限制，只能处理有限精度的十进制整数加减法，比如

10、在32位宽处理器计算机中，参与运算的操作数和结果必须在-231231-1之间。如果需要进行更大范围的十进制整数加法，需要使用特殊的方式实现，比如使用字符串保存操作数和结果，采取逐位运算的方式。如下：9876543210 + 1234567890 = ?让字符串 num1="9876543210"，字符串 num2="1234567890"，结果保存在字符串 result = "11111111100"。-9876543210 + (-1234567890) = ?让字符串 num1="-9876543210"，字符

11、串 num2="-1234567890"，结果保存在字符串 result = "-11111111100"。要求编程实现上述高精度的十进制加法。代码见：10.cpp上面两题，分别实现了正大数的加运算，大数的加运算，相信完全吃透后再编写大数运算的程序就不是问题了。题11:输入两行字符串正整数，第一行是被减数，第二行是减数，输出第一行减去第二行的结果。代码见：11.cpp5） 字符串常见操作题12:通过键盘输入一串小写字母(az)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。比如字符串“abacacde”过滤

12、结果为“abcde”。代码见：12.cpp题13:通过键盘输入一串小写字母(az)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。压缩规则：1. 仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc".2. 压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"代码见：13.cpp题14:删除子串，只要是原串中有相同的子串就删掉，不管有多少个都删除

13、，返回子串个数。输入字符串为：123abc12de234fg1hi34j123k，子串为：123则输出为：abc12de234fg1hi34jk 2代码见：14.cpp题15:将输入的字符串（字符串仅包含小写字母a到z），按照如下规则，循环转换后输出：a->b,b->c,y->z,z->a；若输入的字符串连续出现两个字母相同时，后一个字母需要连续转换2次。例如：aa 转换为 bc，zz 转换为 ab；当连续相同字母超过两个时，第三个出现的字母按第一次出现算。代码见：15.cpp题16：在给定字符串中找出单词（“单词”由大写字母和小写字母字符构成，其他非字母字符视为单词的

14、间隔，如空格、问号、数字等等；另外单个字母不算单词）；找到单词后，按照长度进行降序排序，（排序时如果长度相同，则按出现的顺序进行排列），然后输出到一个新的字符串中；如果某个单词重复出现多次，则只输出一次；如果整个输入的字符串中没有找到单词，请输出空串。输出的单词之间使用一个“空格”隔开，最后一个单词后不加空格。代码见：16.cpp题17:字符串单词首字母转换成大写举例：输入：this is a book返回：This Is A Book代码见：17.cpp题18:通过键盘输入任意一个字符串序列，字符串可能包含多个子串，子串以空格分隔。请编写一个程序，自动分离出各个子串，并使用,将其分隔，并且在

15、最后也补充一个,并将子串存储。  如果输入“abc def gh i        d”，结果将是abc,def,gh,i,d。代码见：18.cpp题19:输入一个字符串，删除其中所有的数字，所有大写字母改成小写，其他不变，并输出。代码见：19.cpp题20：编写一个字符串替换函数，如：“ABCDEFGHIJKLMNOPQRSTUVWXYZ”这个字符串，把其中的“RST”替换为“ggg”这个字符串，结果就变成了：ABCDEFGHIJKLMNOPQgggUVWXYZ代码见：20.cpp题21:写一个程序实现功能：将两个字符串合并为一个字

16、符串并且输出，用指针实现。代码见：21.cpp题22:给定一个字符串,实现一个函数,按下述方式输出字符串： 如果此字符的下一个字符和此字符不一样，原样输出此字符， 否则先输出此字符，再输出此字符连续出现的次数（次数不大于9）。 例如,字符串ABBCCCDEDFFF，输出的结果为AB2C3DEDF3。 不用考虑溢出问题，不能使用任何I/O函数。代码见：22.cpp题23:字符串匹配问题，给定两个字符串，求字符串2，在字符串1中的最先匹配结果。字符串2中可以存在'*'符号，且该符号可以代表任意字符，即字符串2中存在通配符。e.g. 输入：abcdefghabef, a*f 输出：a

17、bcdef代码见：23.cpp题24:输入m个字符串 和一个整数n, 把字符串M化成以N为单位的段，不足的位数用0补齐。如 n=8 m=9 ，123456789划分为：12345678 90000000123 化为 ：12300000代码见：24.cpp题25:统计字符串中数字出现的次数，最大次数的统计出来举例：输入：323324423343输出：3,6代码见：25.cpp题26:输入一段英文文本，用程序统计出现频率最高和最低的两个单词;英文文本中仅出现这四类字符：空格( )、英文逗号(,)、英文句号(.)、英文大小写字母（a-z、A

18、-Z）单词之间的分隔符仅考虑这三种：空格( )、英文逗号(,)、英文句号(.);仅大小写不同的单词算同一个单词；如果两个单词出现次数相同，则在文本中首次出现的单词优先返回。返回的单词统一用小写字母返回例如：输入字符串“Hello world, i said hello world to the world”，返回“world”,“i”代码见：26.cpp题27:将整数倒序输出，剔除重复数据输入一个整数，如12336544，或1750，然后从最后一位开始倒过来输出，最后如果是0，则不输出，输出的数字是不带重复数字的，所以上面的输出是456321和571。如果是负数，比如输入-175，输出-571

19、。代码见：27.cpp以上题目基本可以概括字符串的基本考察点：找单词、替换字符、排序、分割、删除、统计字符或单词出现次数等。题28：名字的漂亮度=26*字母个数最多的+25*字母个数其次的+24*字母个数再其次的(忽略大小写)+.+1*出现次数最小的。输入：整数N，N个字符串输出：N个字符串漂亮度例如：输入1 a 输出 26代码见：28.cpp6） 数组操作题29:判断是否为回文数组（无论从左到右还是从右到左读出来都一样的）。代码见：29.cpp题30:比较两个数组，要求从数组最后一个元素开始逐个元素向前比较，如果2个数组长度不等，则只比较较短长度数组个数元素。请编程实现上述比较，并返回比较中

20、发现的不相等元素的个数比如：数组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;&

21、#160;            input = 3, 6, 1, 9, 7, 8    output = 1, 6, 8, 9, 7, 3代码见：31.cpp题32:算分数，去掉一个最高分一个最低分，求平均分。代码见：32.cpp题33:找出一个数组中满足2N的元素。例如：输入1,2,3,5,7,8,16，则输出：符合条件的有：1 2 8 16 共4个代码见：33.cpp题34:求一个二维数组每列的最小值和二维数组的最小值。代码见：34.cpp

22、题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的矩阵，请编程实现以逆时针旋转方式打印出它的每个元素，例如输入矩阵1 8 72 9 63 4 5则输出为1 2 3 4 5 6 7 8 9。代码见：37.cpp通过上述几题，包含的知识点有数组排序、转置、求特殊集合、按特定顺序输出、多维数组的使用

23、和操作等。7） 四则运算题38:通过键盘输入100以内正整数的加、减运算式，请编写一个程序输出运算结果字符串。输入字符串的格式为：“操作数1 运算符 操作数2”，“操作数”与“运算符”之间以一个空格隔开。代码见：38.cpp题39:输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值注： 1、表达式只含 +, -, *, /, (, ), 四则运算符2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况3、要考虑加减乘除按通常四则运算规定的计算优先级4、除法用整数除法，即仅保留除法运算结果的整数部分。比如8/3=2。输

24、入表达式保证无0作为除数情况发生5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况代码见：39.cpp题40:两个任意长度的正数相减，这两个正数可以带小数点，也可以是整数，请输出结果。 输入的字符串中，不会出现除了数字与小数点以外的其它字符，不会出现多个小数点以及小数点在第一个字符的位置等非法情况，所以考生的程序中无须考虑输入的数值字符串非法的情况。详细要求以及约束：1.输入均为正数，但输出可能为负数；2.输入输出均为字符串形式；3.如果输出是正数则不需要带符号，如果为负数，则输出的结果字符串需要带负号例如：2.2-1.

25、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

26、:求一个正整数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：任意输入两个整数，求他们的最大

27、公约数和最小公倍数。代码见：44.cpp求最大公约数的方法：求差判定法和辗转相除法。着重介绍辗转相除法，其原理是： 以小数除大数，如果能整除，那么小数就是所求的最大公约数。否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。求最小公倍数的方法：首先求得最大公约数，最小公倍数=两数之积/最大公约数。题45:自守数是指一个数的平方的尾数等于该数自身的自然数。例如：252= 625，762= 5776，93762= 87909376。请求出n以内的自守数的个数。代码见：45.cpp题46:任何一个自然数m的立方

28、均可写成m个连续奇数之和。/ 13=1/ 23=3+5/ 33=7+9+11/ 43=13+15+17+19/编程实现：输入一自然数n，求组成n3的n个连续奇数。代码见：46.cpp这里还少一个素数的计算，请大家自己去写一下。9） 匹配问题题47:10个学生考完期末考试评卷完成后，A老师需要划出及格线，要求如下：(1) 及格线是10的倍数；(2) 保证至少有60%的学生及格；(3) 如果所有的学生都高于60分，则及格线为60分输入：输入10个整数，取值0100输出：输出及格线，10的倍数代码见：47.cpp题48:输入一串字符串，其中有普通的字符与括号组成（包括（、）、,''）

29、,要求验证括号是否匹配，如果匹配则输出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输入：OneT

30、woDoubleTwo输出：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)&&a

31、mp;(b=1)输出：RIGTH 3 3输入：if(a=1)&&(b=1)输出：WRONG 3 4代码见：51.cpp题52:输入包括多个行数，首先给出整数N（1<N<10000），接着给出N行文字，每一行文字至少包括一个字符，至多100个字符。如果给定文字中“t”（或“T”）的出现次数比“s”（或“S”）多，则可能为英文，否则可能为德文。输出包括一行，如果输入文字可能为英文，则输出English，否则输出Deutsch。代码见：52.cpp题53：自从有了智能手机，时刻都要关心手机的电量。你的任务很简单，用程序打印符号来表示当前手机的电量。用10行和10列来表示电

32、池的电量，同时在外围加上边框，每一行表示10%的电量。假设还有60%的电量，则显示如下：+-+|-|-|-|-|+|+|+|+|+|+|+-+运行时间限制: 无限制 内存限制: 无限制 输入: 多组测试数据，第一行为测试数据组数N（N<10），紧接着是N行，每行一个数，表示电量，这个数值可能是0，10，20 ，30，40，50，60，70，80，90，100输出: 每组数据输出一个电池的电量，每组数据之间用15个“=”隔开代码见：53.cpp题54：在中国，形容夫妻恩爱的词汇中，大家用的比较多的就是“夫妻相”。所谓“夫妻相”，就是两个人看上去比较般配，长相、身材等某些方面有一定的相似度。

33、本题则另辟蹊径，从人的姓名维度，以字母重复个数来寻找最具“夫妻相”的人。题目中预先给定一组女士的姓名拼音。输入男士的姓名拼音（拼音中间可以有空格,字母全部小写），依预先给定姓名拼音的先后遍历所有姓名，输出字母重复数最多的女士姓名。规则：如果字母重复数最多的女士有多位相同，则以最先匹配的女士做为最具“夫妻相”的人选。规则：人名中的相同字母，按重复一次处理。例如：li ling 与li lei 重复的字符个数为2,而不是4。预置女士名单(先后循序必须保证):"wang fei","zhang man yu","zhang zhi yi",

34、"li li","li xiao man","li yu cun","yang ni","xiao tong","li lei","zhang san"运行时间限制: 无限制内存限制: 无限制输入: 输入一个男士姓名，字符串输出: 输出最具“夫妻相”的女士姓名代码见：54.cpp题55：一副牌中发五张扑克牌给你：让你判断数字的组成： 有以下几种情况： 1：四条：即四张一样数值的牌（牌均不论花色）2：三条带 一对 3：三条带两张不相同数值的牌 4：两对 5：

35、顺子 包括 10，J，Q，K，A 6：什么都不是 7：只有一对.打牌游戏:代码见：55.cpp题56:规则：出牌牌型有5种 牌只有1到9，手里拿着已经排好序的牌a，对方出牌b，用程序判断手中牌是否能够压过对方出牌。 1一张 如4 则5.9可压过 2两张 如44 则55，66，77，.，99可压过 3三张 如444 规则如2 4四张 如4444 规则如2 5五张 牌型只有12345 23456 34567 45678 56789五个，后面的比前面的均大。输入: 输入有多组数据。每组输入两个字符串(字符输出: 压过输出YES 否则NO。串大小不超过100)a，b。a字符串代表手中牌，b字符串代表处

36、的牌。样例输入: 1223344556667733123344556667799888样例输出: YESNO代码见：56.cpp题57：在路由器中，一般来说转发模块采用最大前缀匹配原则进行目的端口查找，具体如下：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，则该

37、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地址同子网地址

38、匹配的基础上，二进制位从左到右完全匹配的位数尽量多（从左到右子网地址最长）。比如：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。示例 输入：ip_addr = "192.168.1.100"net_ad

39、dr_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代码见：57.cpp题58:有一种技巧可以对数据进行加密，它使用一个单词作为它的密匙。下面是它的工作原理：首先，选择一个单词作为密匙，如TRAILBLAZERS。如果单词中包含有重复的字母，只保留第1个，其余几个丢弃。现在，修改过的那个单词死

40、于字母表的下面，如下所示：A B C D E F G H I J K L M N O P Q R S T U V W X Y ZT R A I L B Z E S C D F G H J K M N O P Q U V W X Y上面其他用字母表中剩余的字母填充完整。在对信息进行加密时，信息中的每个字母被固定于顶上那行，并用下面那行的对应字母一一取代原文的字母(字母字符的大小写状态应该保留)。因此，使用这个密匙，Attack AT DAWN(黎明时攻击)就会被加密为Tpptad TP ITVH。请实现下述接口，通过指定的密匙和明文得到密文。详细描述：接口说明：输入:先输入key和要加密的字符串

41、 输出:返回加密后的字符串 样例输入: nihaoni 样例输出: le代码见：58.cpp题59:我国大陆运营商的手机号码标准格式为：国家码+手机号码，例如：8613912345678。特点如下：1、 长度13位；2、 以86的国家码打头；3、 手机号码的每一位都是数字。请实现手机号码合法性判断的函数要求：1） 如果手机号码合法，返回0；2） 如果手机号码长度不合法，返回13） 如果手机号码中包含非数字的字符，返回2；4） 如果手机号码不是以86打头的，返回3；【注】除成功的情况外，以上其他合法性判断的优先级依次降低。也就是说，如果判断出长度不合法，直接返回1即可，不需要再做其他合法性判断。

42、ll示例输入： inMsisdn = “869123456789“输出： 1输入： inMsisdn = “88139123456789“输出： 3输入： inMsisdn = “86139123456789“输出： 0代码见：59.cpp这一类问题的综合性就比较高，题目冗长，但是一定要仔细、耐心地看完题目，看懂题目内在的考点，就好做了。10） 进制转换题60:统计一个数二进制表达中0的个数（首位1之前0不计）。代码见：60.cpp题61:镜像反转二进制表达式，并输出十进制值。代码见：61.cpp题62:输入一个数字，转换为时间，按DDD：HH：MM：SS的格式输出例如：输入100000 显示

43、001:03:46:40代码见：62.cpp在进制转换问题上，除了要熟悉上述已考过的题型外，还要非常清楚如何在2、8、10、16进制间相互转换。11） 二叉树的相关知识点题63:建立一个二叉树，求其高度，首先前、中、后序遍历，求叶子数，求数的深度并且判断是否为平衡二叉树。代码见：63.cpp二叉树是一个典型的数据结构，华为往年的试题中也有考到这个知识点的。下面介绍几个树的重要性质：性质1 二叉树第i层上的结点数目最多为2i-1(i1)。性质2 深度为k的二叉树至多有2k-1个结点(k1)。性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则

44、no=n2+1。二叉树的遍历：前序遍历、中序遍历、后序遍历。（如何遍历、程序如何实现应该知道）12） 背包问题题64：01背包给定一个数，比如20然后 再给定几个数字 1 3 5 7 8则输出：0  0  1  1  1 因为5+7+8=20代码见：64.cpp题65:你有一个容量为100的箩筐，给你30个物品，每个物品的体积已知问：最多能装多少个物品进箩筐 输入描述 一行30个正整数，用空格隔开，表示每个物品的体积 输出描述 一个数字，为最多能

45、装下的物品数 输入样例（此处用3个物品作为样例，实际读入为30个） 5 59 100 输出样例 2 代码见：65.cpp13） 规划问题题66:渡口问题(原题我记不得了，大概如下)：一个渡口有N辆客车和货车需要乘船，规定如下：同类车辆先来的先上；客车优先于货车；客车上了4辆后货车才可以上；客车若不足4辆则货车可以补充；若无货车则客车可以全上。其中客车的优先级为0，货车的优先级为1。例如，输入：5 0 0 1 0 1输出：0 1 3 2 4注意：1、输出的是原车辆在序列中的序号，且从0算起，因而前后交换时要保持相对顺序不变； 2、要考虑客车不足4辆，或者货车数量和客车数量有一者或两者为0的情况。

46、代码见：66.cpp题67:公司设备管理系统，某公司有许多员工和设备，每个员工有一个8位数字组成的ID，每台设备有个小于等于20位由数字和字母组成的设备号。每个员工可以拥有多台设备，但是每台设备只能分配给一个员工使用。输入四个数a,b,c,da:给这个系统添加多少台设备b:从这个系统中删除多少台设备c:添加设备和员工的对应关系d:删除设备和员工的对应关系之后是由这4个参数控制的输入序列a行设备编号，若添加失败则输出"add computers error:"+设备号；成功不输出b行删除设备的编号，若删除失败则输出"remove computers error:&q

47、uot;+设备号；成功不输出c行要分配给员工的设备，若添加失败则输出“assign computer error:”+设备号+“_”+员工号；成功不输出d行要删除分配给员工的设备，若删除失败则输出"remover computer from worker error:"+设备号+“_”+员工号；成功不输出最后要求输出总共的设备数目和排序输出员工和设备的对应关系(员工号+"_"+设备号)（先按照员工号进行排序，若员工有多台设备，则再按照设备号进行排序）。如输入3 2 2 1SN001SN002SN003SN003SN004SN002 12345678SN0

48、01 12345678SN001 12345678输出：remove computers error:SN004112345678_SN002代码见：67.cpp题68:N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK， 则他们的身高满足T1<.<Ti>Ti+1>>TK(1<=i<=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 输入格式 Input Fo

49、rmat 输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 输出格式 Output Format 输出包括得到的最优队列的同学个数 以及最终同学的身高排列。代码见：68.cpp题69:精灵王子爱好冒险，在一次探险历程中，他进入了一个神秘的山洞。在洞穴深处，精灵王子不小心触动了洞穴内暗藏的机关，整个洞穴将很快塌陷，精灵王子必须尽快逃离洞穴。精灵王子的跑步速度为m/s，以这样的速度可能是无法逃出洞穴的。庆幸的是精灵王子拥有闪烁法术，可在s内移动m，不过每次使用

50、闪烁法术都会消耗魔法值点。精灵王子的魔法值恢复的速度为点/s，只有处在原地休息状态时才能恢复。现在已知精灵王子的魔法初值M，他所在洞穴中的位置与洞穴出口之间的距离S，距离洞穴塌陷的时间T。你的任务是写一个程序帮助精灵王子计算如何在最短的时间内逃离洞穴。若能逃出，输出"Yes"，并输出逃出所用的最短时间；若不能逃出，则输出"No"，同时输出精灵王子在剩下的时间内能走的最远距离。注意字母大小写。注意:精灵王子跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。注：M、S、T均是大于等于的整数。由输入保证取值合法性，考生

51、不用检查。提醒：如果输入的S为，则说明本身已经在出口，输出应为：Yes 0如果输入的T为（且S不为），则说明已经没有时间了，输出应为：No 0输入: 输入格式:MST输出: 输出格式：Yes 逃出洞穴所用的最短时间或No 在洞穴塌陷前能逃跑的最远距离 样例输入: 10 50 5 样例输出: Yes 1 代码见：69.cpp题70:M个相同苹果放到N个相同篮子里有多少种放法,允许有篮子不放。1<=M<=10，1<=N<=10例如5个苹果三个篮子，3，1，1 和 1,1,3是同一种放法输入 7 3输出 8代码见：70.cpp14） 最短路径题71:设有n个城市，编号为0n-

52、1，m条单向航线的起点和终点由输入提供，寻找一条换乘次数最少的线路方案。输入 第一行为三个整数n、m、v，表示城市数、单向航线数和起点城市。以下m行每行两个整数，表示一条边的起点、终点，保证不重复、不失败。2n20，1m190输出 共n-1行，分别是从起点城市v到其他n-1个城市最少换乘次数，按照终点城市序号从小到大顺序输出，不能抵达时输出-1。样例输入3 2 00 11 2样例输出12代码见：71.cpp题72:N个城市（N<=10）,从0到9编号，城市间要么有路，要么没路，计算城市A到B之间到底有多少条路。输入：N A B（1<N<=10,0<=A,B<=9）

53、A为出发城市，B为目的城市。然后n行表示行编号的城市到其他城市有没有路，0表示没有，1表示有路。输出：A到B有多少条路输入：3 0 2 1 1 1 1 1 1 1 1 1输出：2代码见：72.cpp15）图连通问题题73:给定一个无向图，一共n个点，请编写一个程序实现两种操作：D x y 从原图中删除连接x，y节点的边。Q x y 询问x，y节点是否连通输入第一行两个数n,m（5<=n<=40000,1<=m<=100000）接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。接下来一行一个整数 q（q<=10000

54、0）以下q行每行一种操作，保证不会有非法删除。输出按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D样例输入3 31 21 32 35Q 1 2D 1 2Q 1 2D 3 2Q 1 2样例输出CDD代码见：73.cpp题74:森林里的苯苯熊要乔迁新喜，上次他已经将物品打包完成，并约了朋友来帮忙。接下来他要选定一个搬家的时间，想了很久，就决定在国庆节进行，因为国庆放假朋友们都有时间啦。但是在森林里，从他现在房子到新豪宅，所经之地有山有水，路途曲折，甚至有些道路是不通的。请你和他一起查看指定的地图，看看从笨笨熊现在的房子到新宅之间，道路是否是畅通的呢？地图是R行、C列的矩阵，矩阵的每一个

55、格子刚好是一天的行程。矩阵由“B”、“-”、“#”、“H”四种字符成员组成，其中： B：代表苯苯熊现在的房子； H：代表笨笨熊新的豪宅； -：代表可以通行的道路； #：代表无法通过的障碍(高山、大河等)；此外，森林里也有交通规则地：在任务位置，只能向“上、下、左、右”四个方向中的其中一个方向行走。 输入: 4 / R的数值4 / C的数值，下面是地图。-#-B-H#-#-输出: Y /代表道路可达或N /代表道路不通样例输入: 15-B-H# 样例输出: Y 代码见：74.cpp图连通的考点也有考过，可以准备一下这个知识点。16） 对数字进行判断题75:中国有句俗语叫“三天打鱼两天晒网”，给定

56、起始日期为1990年1月1号，输入终止日期，计算终止日期是在打渔还是晒网，打渔输出Fishing，晒网输出Netting。输入：1990 01 04输出：Netting代码见：75.cpp题76:两个整数相除，将结果用字符串返回。如果是循环小数，将循环的位用括号括起来。输入：3输出：0.(3)输入 1 7输出 0.(142857)代码见：76.cpp题77:变形的杨辉三角形 1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 1 4 10 16 19 16 10 4 1每个数是上行，左右3个数之和，不存在为0，求第n行第一个偶数出现的位置，没有输出-1代码见：77.cpp17） 实际应用题78:选秀节目打分分为专家评委和大众评委，score 数组里面存储每个评委打的分数，judge_type 里存储与 score 数组对应的评委类别，judge_typei = 1，表示专家评委，judge_typei = 2，表示大众评委，n表示评委总数。打分规则如下：专家评委和大众评委的分数先分别取一个平均分（平均分取整），然后，总分 = 专家评委平均分*0.6 + 大众评委 * 0.4，总分取整。如果没有大众评委，则 总分 = 专家评委平均分，总分取整。函数最终返回选手得分。代码见：78.cpp题79:在掷骰子游戏中，会根据所掷数字在