计算机考研数据结构统考历年真题答案2009-2015

《计算机考研数据结构统考历年真题答案2009-2015》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目前刚整理了2009-2015的试题过几天2016的也会上传上去希望对你有帮助。。。。。。。答案与试题是配套的选择题没有解析有不懂得可以在文库上@我20091-5：BCDBC6-10：BADBA41.该方法求得的路径不一定是最从a到C的D:路K:为A-B-C.事实上其嚴短路f/J短路径。例如，对于下图所示的带权A^D^C图，如果按照题中的原则，从A到C的最fe路径为A-*B-*C，事实上其最短路径为A-^D-^Co42.(1)算法的基本设计思想：定义两个指针变量p和q，初始时均指向头结点的下一个结点。P

2、指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。(2)算法的详细实现步骤：①count=0，p和q指向链表表头结点的下一个结点；②若p为空，转⑤；③若count等于k，则q指向下一个结点;否则，count=count+l;④p指向下一个结点，转步骤②；⑤若count等于k，则查找成功，输出该结点的data域的值，返回1;返回；查找失败，返In]0;⑥算法结朿。(3)算法实现：typed

3、efstructLNode{intdata;structLNode*link;}*LinkList;intSearchN(LinkListlist,intk){LinkListp，q;intcount=0;/*计数器赋初值*/p=q=list-〉link;/*p和q指向链表表头結点的下一个結点*/while(p!=NULL){if(countlink;/*q移到下一个结点*/p=p->link;/*p移到下一个结点*/}if(count

4、tum(0);/*如果链表的长度小于k，查找失败*/else{printf(’’％d’’，q-〉data);/*查找成功*/return(l);}//else}//SearchN20101-5：DCDCB6-11：ACBBDA41.(1)构造的散列表如下•卜•标0123456789关键字71481130189(2)查找成功的平均査找长度:ASL成功=12/7。查找不成功的平均查找长度:ASL不成功=18/7。42.(1)给出算法的基木设计思想：先将n个数据xOxl…xp…xn-1原地逆置，得到Xn-P"

5、Xpxp小-xO,然后再将前n-p个和后p个元素分别原地逆置，得到最终结果:xpxp+1…xn-1xOx1…xp-1o(2)算法实现：voidreverse(intr[]，intleft，intright){intk=left，j=right，temp;//k等于左边界leftj等于右边界rightwhile(k

6、p){if(p>O&&p

7、序序列A和B的中位数，设为a和b。如果3=13,则a或者b即为所求的中位数。原因：如果将两序列归并排序，则最终序列屮，排在子序列ab前边的元素为先前两序列中排在a和b前边的元素;排在子序列ab后边的元素为先前两序列a和b后边的元素。所以子序列ab—定位于最终序列的中间，有因为a=b，显然a就是中位数。如果av^b(假设a

8、b所在序列B之中比较大的一半。在保留的两个升序序列中求出新的中位数a和b,重复上述过程，直到两个序列只含一个元素为止，则较小者即为所求中位数。(2)算法实现(高效方法)：(8分)intSearch(intA[],intB[],intn){ints1，e1，mid1，s2，e2，mid2;si=0;e1=n-1;s2=l;e2二n-1;while(sl!=el

9、

10、s2!=e2){midl=(sl+e1)/2;mid2=(s2+e2)/2;if