搜索
20091-5：BCDBC6-10：BADBA41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为A→D→C。42.（1）算法的基本设计思想：定义两个指针变量p和q，初始时均指向头结点的下一个结点。P指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。（2）算法的详细实现步骤：①count=0,p和q指向链表表头结点的下一个结点；②若p为空，转⑤；③若count等于k,则q指向下一个结点;否则,count=count+1;④p指向下一个结点，转步骤②；⑤若count等于k,则查找成功,输出该结点的data域的值,返回1;返回；查找失败,返回0;⑥算法结束。（3）算法实现：typedefstructLNode{intdata;structLNode*link;}*LinkList;intSearchN(LinkListlist,intk){LinkListp,q;intcount=0;/*计数器赋初值*/p=q=list-link;/*p和q指向链表表头结点的下一个结点*/while(p!=NULL){if(countk)count++;/*计数器+1*/elseq=q-link;/*q移到下一个结点*/p=p-link;/*p移到下一个结点*/}if(countk)return(0);/*如果链表的长度小于k,查找失败*/else{printf(%d,q-data);/*查找成功*/return(1);}//else}//SearchN20101-5：DCDCB6-11：ACBBDA41.（1）构造的散列表如下下标0123456789关键字71481130189（2）查找成功的平均查找长度:ASL成功=12/7。查找不成功的平均查找长度:ASL不成功=18/7。42.（1）给出算法的基本设计思想：先将n个数据x0x1…xp…xn-1原地逆置，得到xn-1…xpxp-1…x0,然后再将前n-p个和后p个元素分别原地逆置，得到最终结果:xpxp+1…xn-1x0x1…xp-1。（2）算法实现：voidreverse(intr[],intleft,intright){intk=left,j=right,temp;//k等于左边界left,j等于右边界rightwhile(kj){//交换r[k]和r[j]temp=r[k];r[k]=r[j];r[j]=temp;k++;//k右移一个位置j--;//j左移一个位置}}voidleftShift(intr[],intn,intp){if(p0&&pn){reverse(r,0,n-1);//将全部数据逆置reverse(r,0,n-p-1);//将前n-p个元素逆置reverse(r,n-p,n-1);//将后p个元素逆置}}（3）说明算法复杂性：上述算法的时间复杂度为O(n),空间复杂度为O(1)。20111-5：ABBCC6-10：DACBA41.高分笔记图最后一题42.(1)算法的基本设计思想：(5分)1)比较笨的方法：将两升序序列归并排序，然后求其中位数，时间复杂度是O(n)，空间复杂度O(n)。2)高效的方法：分别求两个升序序列A和B的中位数，设为a和b。如果a=b，则a或者b即为所求的中位数。原因：如果将两序列归并排序，则最终序列中，排在子序列ab前边的元素为先前两序列中排在a和b前边的元素;排在子序列ab后边的元素为先前两序列a和b后边的元素。所以子序列ab一定位于最终序列的中间，有因为a=b，显然a就是中位数。如果a≠b(假设ap原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如…a…b…的序列出现，中位数必然出现在(a，b)范围内。因此可以做如下处理：舍弃a所在序列A之中比较小的一半，同时舍弃b所在序列B之中比较大的一半。在保留的两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列只含一个元素为止，则较小者即为所求中位数。(2)算法实现(高效方法)：(8分)intSearch(intA[],intB[],intn){ints1,e1,mid1,s2,e2,mid2;s1=0;e1=n-1;s2=1;e2=n-1;while(s1!=e1||s2!=e2){mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(A[mid1]==B[mid2])returnA[mid1];if(A[mid1]p){//分别考虑奇数和偶数，保持两个子数组元素个数相等if((s1+e1)%2==0){//若元素个数为奇数s1=mid1;//舍弃A中间点以前部分且保留中间点e2=mid2;//舍弃B中间点以后部分且保留中间点}//ifelse{//若元素个数为偶数s1=mid1+1;//舍弃A中间点以前部分且保留中间点e2=mid2;//舍弃B中间点以后部分且保留中间点}//else}//ifelse{if((s1+e1)%2==0){//若元素个数为奇数个e1=mid1;//舍弃A中间点以后部分且保留中间点s2=mid2;//舍弃B中间点以前部分且保留中间点}//ifelse{//若元素个数为偶数个e1=mid1+1;//舍弃A中间点以后部分且保留中间点s2=mid2;//舍弃B中间点以前部分且保留中间点}//else}//else}//whilereturn(A[s1])}//search(3)上述所给算法的时间、空间复杂度分别是O(log2n)和O(1)。(2分)因为每次总的元素个数变为原来的一半，所以有：第一次：元素个数为n/2=n/(21)第二次：元素个数为n/4=n/(22)…………第k次：元素个数为n/(2k)最后元素个数为2则有n/(2k)=2解得k=log2n–1因此：时间复杂度为O(log2n)，而空间复杂度从上述程序中可看出为O(1)。20121-5：BAABC6-11：CCADAD41.高分笔记排序最后一题42.（1）算法思想：顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路：①遍历两个链表求的它们的长度L1，L2；②比较L1，L2，找出较长的链表，并求L=|L1-L2|；③先遍历长链表的L各结点；④同步遍历两个链表，直至找到相同结点或链表结束。（2）算法的C语言代码描述LinkListSearch_First_Common(LinkListL1,LinkListL2){//本算法实现线性时间内找到两个单链表的第一个公共结点intlen1=Length(L1),len2=Length(L2);LinkListlongList,shortlist;//分别指向较长和较短的链表if(len1len2){longList=L1-next;shortlist=L2-next;L=len1-len2;//表长之差}//ifelse{longList=L2-next;shortlist=L1-next;L=len2-len1;//表长之差}//elseWhile(L--)longList=longList-next;while(longList!=NULL){if(longList==shortList)//同步寻找共同结点returnlongList;else{longList=longList-next;shortlist=shortlist-next;}//else}//whilereturnNULL;}//Search_First_Common（3）算法的时间复杂度为O(len1+len2)，空间复杂度为O(1)。20131-5：DCDBA6-10：CCDCA41.（1）给出算法的基本设计思想：（4分）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。算法可分为以下两步：①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中记录Num的出现次数为1；若遇到的下一个整数仍等于Num则计数加一，否则计数减一；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。②判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。（2）算法实现：（7分）intMajority(intA[],intn){inti,c,count=1;//c用来保存候选主元素，count用来计数c=A[0];//设置A[0]为候选主元素for(i=1;in;i++){//查找候选主元素if(A[i]==c)count++;//对A中的候选主元素计数elseif(count0)count--;//处理不是候选主元素的情况else{//更换候选主元素，重新计数c=A[i];count=1;}//else}//forif(count0)for(i=count=0;in;i++)//统计候选主元素的实际出现次数if(A[i]==c)count++;if(countn/2)returnc;//确认候选主元素elsereturn-1;//不存在主元素}//Majority42.（1）采用顺序存储结构，数据元素按其查找概率降序排列。（2分）采用顺序查找方法。（1分）查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。（2分）（2）【答案一】采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。（2分）采用顺序查找方法。（1分）查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。（2分）【答案二】采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。（2分）20141-5：CBADC6-11：DDDDBC41．解答：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。1）算法的基本设计思想：①基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积；若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一；最后返回计算出的wpl即可。②基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计wpl；当遍历到非叶子结点时对该结点的把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增1；队列空时遍历结束，返回wpl2)二叉树结点的数据类型定义如下：typedefstructBiTNode{intweight;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;3)算法代码如下：①基于先序遍历的算法：intWPL(BiTreeroot){returnwpl_PreOrder(root,0);}//intintwpl_PreOrder(BiTreeroot,intdeep){staticintwpl=0;//定义一个static变量存储wplif(root-lchild==NULL&&root-lchild==NULL)//若为叶子结点，累积wplwpl+=deep*root-weight