面试题数据结构和算法题5道（附解题思路）

数据结构和算法题5道（附解题思路）题目1自然数n,请求出分解自然数之和最小的一个题目：一个自然数可以分解为若干个自然数相乘，对于指定自然数n,请求出每种分解自然数之和最小的一个（不考虑1，若是素数，则是它本身）（6分钟）考察点：问题分析及算法的考虑，可以只实现伪代码。另外可以从题目引申考察该实现的测试及异常处理参考答案：分解为若干个素数之积，则和最小。实现如下unsignedintMinSum(unsignedintnumber){inti=2;intsum=0;intnewnum=number;while(newnum!=1){if(newnum%i==0){sum=sum+i;newnum=newnum/i;i=2;}elsei++;}returnsum;}题目2：返回不超过x的最大2的整数次冥给定一个正整数x(4字节无符号整数)，返回不超过x的最大2的整数次冥如，左边是输入，右边是输出。

如果不允许用判断语句(if,while,switch,?:

运算符等)，如何实现？哪个快？为什么？1122324454647488...511256512512513512答案移位：intget_max(unsignedintx){unsignedintt=1;x>>1;while(x){x>>=1;t<<=1;}returnt;}不要判断intget_max(unsignedintx){return1<<int(log2(x));}查表unsignedbuf1[256]={1};unsignedbuf2[256]={0,1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,....128,128,128,...};unsignedbuf3[2][2][2][2]={{3,3,3,3},{3,3,3,3},{2,2,2,2},{1,1,0,0}};unsignedshift[4]={0,8,16,24};intget_max(intx){unsignedchar*a=(unsignedchar*)&x;pos=buf3[buf1[a[3]]][buf1[a[2]]][buf1[a[1]]][buf1[a[0]]];returnbuf2[a[pos]]<<shift[pos];}查表最快，log计算比移位慢，循环比直接运算慢题目3(本题答案不全)：设计1个可以有序输出的hash表在常用的集合数据结构中，hash表

和

二叉树各有优点，Hash表速度快，但是不能有序输出，二叉树能有序输出元素，但是在速度上比不上hash表问题：如何设计一个数据结构，既可以保持像二叉树的有序，又能够有hash表的处理速度？解题思路：考虑hash算法的时候，如果能够保持桶间是有序的，桶内又是有序的，则可以满足要求；在某些情况下，如果输入是有序的，而中间又需要hash表来暂时保存数据，同时，必须保证输出有序的情况下，例如，需要使用某种条件去除输入的某些内容，可以考虑使用一个前后指针来链接节点，这样在输出的时候能保存有序，而维护列表也非常容易。题目4(本题答案不全)：给出单词出现文件中的文件名问题：mini-search背景：有N个文件，文件名1.txt2.txt…n.txt，每个文件中有若干英文单词（数量不定，空格分隔）要求：用户输入一个英文单词，系统计算给出该英文单词曾出现在那些文件中，给出文件名；参考答案：基本方法：根据用户输入的英文单字在各个文件中进行匹配查找；给出更优的匹配算法可加分；较优方法：对文件中的英文单词进行预处理，使用树结构（二十六叉树）；更优方法：对文件中的英文单词进行预处理，使用哈希算法；考察点：数据结构+算法设计题目5(本题答案不全)：多路归并linux32位系统下有10个无序文件，各文件大小不一（均小于2g），现需要将此10个文件归并为一个有序文件，请选择你最熟悉的语言实现之；说明，文件的每一行为最长