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

数据结构和算法题道（附解题思5路）题目1自然数n,请求出分解自然数之和最小的一个题目一个自然数可以分解为若干个自然数相乘，对于指定自然数n.请求出每种分解自然数之和最小的一个（不考虑1,若是素数，则是它本（身）6分钟）考察点问题分析及算法的考虑，可以只实现伪代码另外可以从题目引申考察该实现的测试及异常处理参考答案分解为若干个素数之积，则和最小实现如下unsigned intMinSum unsignedint numberint i=2;int sum=O;int newnum=number;whilenewnum!=lifnewnum%i==O{sum=sum+i;newnum=newnum/i;i=2;；else i++return sum;给定一个正整数x（4字节无符号整数），返不超过x的最大2的整数题目2:返回不超过x的最大2的整数次冥（如，左边是输入，右边是输出如果不允许用判断语句if,while,次冥switch:运算符等），如何实现？哪个快？为什么f324454647488511256512512513512答案移位int get_maxunsigned intxunsigned intt=l;1；Xwhile x{=1；X；t=lreturn t;不要判断int get_maxunsigned intxreturn lintlog2x;查表；unsigned bufl

[256]={1}unsigned buf2

[256]={0,1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,....128,128,128,...；unsigned buf3

[2]

[2]

[2]

[2]={{3,3,3,3},{3,3,3,3},亿2,2,2},{1,1,0,0};unsigned shift

[4]={0,8,16,24;int get_maxint xunsigned char*a=unsignedchar*x;pos=buf3[bufl[a

[3]]][bufl[a

[2]]][bufl[a[l]]][bufl[a

[0]]];return buf2[a[pos]]shift[pos];查表最快Jog计算比移位慢，循环比直接运算慢题目3（本题答案不全）设计1个可以有序输出的hash表在常用的集合数据结构中，hash表和二叉树各有优点，Hash表速度快，但是不能有序输出，二叉树能有序输出元素，但是在速度上比不上hash表问题如何设计一个数据结构，既可以保持像二叉树的有序，又能够有hash表的处理速度？解题思路:考虑hash算法的时候如果能够保持桶间是有序的桶内又是有序的,则可以满足要求；在某些情况下，如果输入是有序的，而中间又需要hash表来暂时保存数据，同时，必须保证输出有序的情况下，例如，需要使用某种条件去除输入的某些内容，可以考虑使用一个前后指针来链接节点，这样在输出的时候能保存有序，而维护列表也非常容易题目4（本题答案不全）给出单词出现文件中的文件名问题:mini-search背景有N个文件，文件名l.txt

2.txt...n.txt,每个文件中有若干英文单词（数量不定，空格分隔）要求用户输入一个英文单词，系统计算给出该英文单词曾出现在那些文件中，给出文件名；参考答案:基本方法根据用户输入的英文单字在各个文件中进行匹配查找；给出更优的匹配算法可加分；较优方法:对文件中的英文单词进行预处理，使用树结构（二十六叉树）;更优方法对文件中的英文单词进行预处理，使用哈希算法；考察点数据结构+算法设计题目5（本题答案不全）多路归并）linux32位系统下有10个无序文件，各文件大小不一（均小于2g,现需要将此10个文件归并为一个有序文件，请选择你最熟悉的语言实现之；说明，文件的每一行为最长不超过128位的阿拉伯数字组合；参考答案可以先把十个文件有序化后再采用多路归并算法进行归并,此外需要注意由于数字长度不确定，只能自己书写数字的比对函数；考察点针对测试开发人员，难。