(全)面试题数据结构和算法题5道（附解题思路）.docx

数据结构和算法题5道（附解题思路）题目1自然数n,请求出分解自然数之和最小的一个题目：一个自然数可以分解为若干个自然数相乘，对于指定自然数n,请求出每种分解自然数之和最小的一个（不考虑1,若是素数，则是它本身）（6分钟）考察点：问题分析及算法的考虑，可以只实现伪代码。另外可以从题目引申考察该实现的测试及异常处理参考答案：分解为若干个素数之积，则和最小。实现如下unsignedintMinSum（unsignedintnumber）（inti=2;intsum=O;intnewnum=number;while(newnum!=l)if(newnum%i=O)sum=sum+i;newnum=newnum/i;i=2;）elsei+；）returnsum;）题目2:返回不超过x的最大2的整数次冥给定一个正整数x（4字节无符号整数）,返回不超过X的最大2的整数次冥如，左边是输入，右边是输出。如果不允许用判断语句（if,while,switch,?:运算符等），如何实现？哪个快？为什么？22324454647488511256512512513512答案移位：intget_max(unsignedintx)unsignedintt=l;x>>l;while(x)x>>=l;t<<=l;)returnt;)不要判断intget_max(unsignedintx)(returnl<<int(log2(x);)查表unsignedbufl256=1;unsignedbuf2256=0zL2,2l4,4,4f4,8,8,8f8,8,8f8,8,16,16z.128z128z128t.)；unsignedbuf32222=3z3,3,3,3,3,3z3,亿2,2,2lllI1O1O);unsignedshift4=O,8z16z24;intget_max(intx)(unsignedchar*a=(unsignedChar*)&x;pos=buf3bufla3bufla2buflalbufla0;returnbuf2apos<<shiftpos;)查表最快，log计算比移位慢，循环比直接运算慢题目3（本题答案不全）：设计1个可以有序输出的hash表在常用的集合数据结构中，hash表和二叉树各有优点，Hash表速度快，但是不能有序输出，二叉树能有序输出元素，但是在速度上比不上hash表问题：如何设计一个数据结构，既可以保持像二叉树的有序，又能够有hash表的处理速度？解题思路：考虑hash算法的时候如果能够保持桶间是有序的桶内又是有序的，则可以满足要求；在某些情况下，如果输入是有序的，而中间又需要hash表来暂时保存数据，同时，必须保证输出有序的情况下，例如，需要使用某种条件去除输入的某些内容，可以考虑使用一个前后指针来链接节点，这样在输出的时候能保存有序，而维护列表也非常容易。题目4（本题答案不全）：给出单词出现文件中的文件名问题:mini-search背景：有N个文件，文件名l.txt2.txt.n.txt,每个文件中有若干英文单词（数量不定，空格分隔）要求：用户输入一个英文单词，系统计算给出该英文单词曾出现在那些文件中，给出文件名；参考答案:基本方法：根据用户输入的英文单字在各个文件中进行匹配查找；给出更优的匹配算法可加分；较优方法:对文件中的英文单词进行预处理,使用树结构（二十六叉树）;更优方法：对文件中的英文单词进行预处理，使用哈希算法;考察点：数据结构+算法设计题目5（本题答案不全）：多路归并Iinux32位系统下有10个无序文件，各文件大小不一（均小于2g）,现需要将此10个文件归并为一个有序文件，请选择你最熟悉的语言实现之；说明，文件的每一行为最长不超过128位的阿拉伯数字组合；参考答案：可以先把十个文件有序化后再采用多路归并算法进行归并，此外需要注意由于数字长度不确定，只能自己书写数字的比对函数；考察点：针对测试开发人员，难