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

《全面试题数据结构和算法题5道附解题思路.docx》由会员分享，可在线阅读，更多相关《全面试题数据结构和算法题5道附解题思路.docx（7页珍藏版）》请在第一文库网上搜索。

1、数据结构和算法题5道（附解题思路）题目1自然数n,请求出分解自然数之和最小的一个题目：一个自然数可以分解为若干个自然数相乘，对于指定自然数n,请求出每种分解自然数之和最小的一个（不考虑1,若是素数，则是它本身）（6分钟）考察点：问题分析及算法的考虑，可以只实现伪代码。另外可以从题目引申考察该实现的测试及异常处理参考答案：分解为若干个素数之积，则和最小。实现如下unsignedintMinSum（unsignedintnumber）（inti=2;intsum=O;intnewnum=number;whi1e(newnum!=1)if(newnum%i=O)sum=sum+i;newnum=ne

2、wnum/i;i=2;）e1sei+；）returnsum;）题目2:返回不超过x的最大2的整数次冥给定一个正整数x（4字节无符号整数）,返回不超过X的最大2的整数次冥如，左边是输入，右边是输出。如果不允许用判断语句（if,whi1e,switch,?:运算符等），如何实现？哪个快？为什么？22324454647488511256512512513512答案移位：intget_max(unsignedintx)unsignedintt=1;x1;whi1e(x)x=1;t=1;)returnt;)不要判断intget_max(unsignedintx)(return1int(1og2(x);)

3、查表unsignedbuf1256=1;unsignedbuf2256=0z12,214,4,4f4,8,8,8f8,8,8f8,8,16,16z.128z128z128t.)；unsignedbuf32222=3z3,3,3,3,3,3z3,亿2,2,2111I1O1O);unsignedshift4=O,8z16z24;intget_max(intx)(unsignedchar*a=(unsignedChar*)&x;pos=buf3buf1a3buf1a2buf1a1buf1a0;returnbuf2aposshiftpos;)查表最快，1og计算比移位慢，循环比直接运算慢题目3（本题答

4、案不全）：设计1个可以有序输出的hash表在常用的集合数据结构中，hash表和二叉树各有优点，Hash表速度快，但是不能有序输出，二叉树能有序输出元素，但是在速度上比不上hash表问题：如何设计一个数据结构，既可以保持像二叉树的有序，又能够有hash表的处理速度？解题思路：考虑hash算法的时候如果能够保持桶间是有序的桶内又是有序的，则可以满足要求；在某些情况下，如果输入是有序的，而中间又需要hash表来暂时保存数据，同时，必须保证输出有序的情况下，例如，需要使用某种条件去除输入的某些内容，可以考虑使用一个前后指针来链接节点，这样在输出的时候能保存有序，而维护列表也非常容易。题目4（本题答案不

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