[最新答案V0.4版]微软等数据结构+算法面试100题[第41-60题答案]

1微软等公司微软等公司微软等公司微软等公司数据结构数据结构数据结构数据结构++++算法面试算法面试算法面试算法面试100100100100题题题题之之之之第第第第41-6041-6041-6041-60题答案题答案题答案题答案------------答案答案答案答案V0.4V0.4V0.4V0.4版版版版---------1.此答案系列，仅仅，只能作为你的思路参考（我无法保证90%以上精准，更不用说100%）。2.关于本微软等100题系列，所有任何资料或资源，归我个人July和个别网友所有，任何人不得私自据为己有。3.版权所有，本资料暂且，仅供学习交流之用，任何人不得抄袭、擅自用于其它用途。若有如此，必定不遗余力，必究。4.永远、继续欢迎，各位，提供针对此100道题任何一道，自己认为好的思路、或算法。5.此份答案，每一题，都有所啰嗦之处，主要是为了照顾初学者。若是只写思路，这100题的答案，只要花一到俩页纸，就够了。So，怕篇幅过大，此次只一次性整理20题的答案。最后，欢迎，各位，任何人，针对以下任何一题的但或思路，提出批评指正，或分享思路。------------------------------------------------------------------MyBlog：微软等100题系列，整理资源下载地址：题目系列：1.[最新整理公布][汇总II]微软等数据结构+算法面试100题[第1-80题][第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题][第二部分]精选微软等公司结构+算法面试100题[前41-60题]：答案系列：4.[最新答案V0.3版]微软等数据结构+算法面试100题[第21-40题答案][答案V0.2版]精选微软数据结构+算法面试100题[前20题]--修正其它，答案、思路，正在整理中。更多资源，下载地址：谢谢。网友思路回复地址：作者声明:本人July对以上所有任何内容和资料享有版权，转载请注明出处。向你的厚道致敬。谢谢。2010年12月1日。241.求固晶机的晶元查找程序晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，若匹配不过，照相机则按测好的晶元间距移到下一个位置。求遍历晶元盘的算法求思路。关于第41题，请看以下网友的回复：xiuxianshen感觉很简单啊，你对应你的元件个数新建两个相同维数的一维数组，一组保存检测的匹配情况，一组保存该元件的距离，二维数组也可以，遍历前先考虑数据参数就可以了。kicming难就难在元件的分布情况是未知的对机器来说它是不知道边界的它自己不知道换行所以很难规定换行的条件比如从左向右找找到某个地方发现没有元件了那是换行还是不换行呢换行的话，右边可能还有元件，不换行，可能当前已经到晶元盘边界了再往右找就是地板了..所以想求一个“盲目”遍历算法。42.请修改append函数，利用这个函数实现：两个非降序链表的并集，1-2-3和2-3-5并为1-2-3-5另外只能输出结果，不能修改两个链表的数据。此题，合并链表，要求将俩个非有序排列的链表，有顺序的合并。如下：//引自一网友。#includestdio.h#includemalloc.htypedefstructlnode{intdata;structlnode*next;}lnode,*linklist;linklistcreatlist(intm)//创建链表{linklistp,l,s;inti;3p=l=(linklist)malloc(sizeof(lnode));p-next=NULL;printf(请输入链表中的一个数字：);scanf(%d,&p-data);for(i=2;i=m;i++){s=(linklist)malloc(sizeof(lnode));s-next=NULL;printf(请输入第%d个数字,i);scanf(%d,&s-data);p-next=s;p=p-next;}printf(\n);returnl;}voidprint(linklisth)//打印链表{linklistp=h-next;intt=1;printf(打印各个数字：\n);do{printf(请输出第%d个数:,t);printf(%d\n,p-data);p=p-next;t++;}while(p);}linklistmergelist(void)//两个链表合并{inte,n;linklistpa,pb,pc,head;printf(请输入第一个链表的长度：);scanf(%d,&e);pa=creatlist(e);printf(请输入第二个链表的长度：);scanf(%d,&n);pb=creatlist(n);head=pc=(linklist)malloc(sizeof(lnode));pc-next=NULL;while(pa&&pb){if(pa-data=pb-data)4{pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;returnhead;}voidmain(){linklisthead;head=mergelist();print(head);}///////////////////////////////////请输入第一个链表的长度：5请输入链表中的一个数字：3请输入第2个数字2请输入第3个数字1请输入第4个数字7请输入第5个数字9请输入第二个链表的长度：5请输入链表中的一个数字：6请输入第2个数字4请输入第3个数字5请输入第4个数字8请输入第5个数字7打印各个数字：请输出第1个数:3请输出第2个数:2请输出第3个数:1请输出第4个数:6请输出第5个数:4请输出第6个数:55请输出第7个数:7请输出第8个数:8请输出第9个数:7请输出第10个数:9Pressanykeytocontinue//引用yangsen600。#includestdio.h#includestdlib.h#includemalloc.hstructNode{intnum;Node*next;};Node*createTail(){intx;Node*head=NULL,*p=NULL,*tail=NULL;puts(\npleaseentersomedigits(endof'.'):);while(1==scanf(%d,&x)){p=(Node*)malloc(sizeof(Node));p-num=x;p-next=NULL;if(NULL==head){tail=p;head=tail;}else{tail-next=p;tail=p;}}getchar();returnhead;}Node*CombinationNode(Node*head1,Node*head2)6{Node*head,*tail,*p=head1,*q=head2,*s;if(NULL==p)returnq;if(NULL==q)returnp;tail=p;if(p-numq-num)tail=q;head=tail;while(NULL!=p&&NULL!=q){if(p-num=q-num)//如果p所指元素q所指元素，那么把p所指元素，率先拉入合并后的链表中，//p赋给s，并从p的下一个元素p-next查找。//直到发现p所指不再q，而是pq了即转至下述代码的else部分。{s=p;p=p-next;}else{s=q;q=q-next;}tail-next=s;tail=s;}if(NULL==p)p=q;s=p;tail-next=s;returnhead;}voidprintHead(Node*head){if(NULL==head)return;7printf(List:);while(head){printf(%d-,head-num);head=head-next;}puts(NUL);}voidmain(void){Node*head1,*head2,*head;head1=createTail();printHead(head1);head2=createTail();printHead(head2);head=CombinationNode(head1,head2);printHead(head);}//////////////////////////////////////////pleaseentersomedigits(endof'.'):32179.List:3-2-1-7-9-NULpleaseentersomedigits(endof'.'):64587.List:6-4-5-8-7-NULList:3-2-1-6-4-5-7-8-7-9-NULPressanykeytocontinue//与上述那段，输出结果一致。已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。//非递归实现链表合并排序：Node*Merge(Node*head1,Node*head2){if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;Node*head=NULL;Node*p1=NULL;8Node*p2=NULL;if(head1-datahead2-data){head=head1;p1=head1-next;p2=head2;}else{head=head2;p2=head2-next;p1=head1;}Node*pcurrent=head;while(p1!=NULL&&p2!=NULL){if(p1-data=p2-data){pcurrent-next=p1;pcurrent=p1;p1=p1-next;}else{pcurrent-next=p2;pcurrent=p2;p2=p2-next;}}if(p1!=NULL)pcurrent-next=p1;if(p2!=NULL)pcurrent-next=p2;returnhead;}//递归实现，Node*MergeRecursive(Node*head1,Node*head2){if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;9Node*head=NULL;if(head1-datahead2-data){head=head1;head-next=MergeRecursive(head1-next,head2);}else{head=head2;head-next=MergeRecursive(head1,head2-next);}returnhead;}不放比较一下，这俩段核心代码，注意其区别：Node*Combination