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

2009 1-5：BCDBC6-10：BADBA41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为ABC，事实上其最短路径为ADC。 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）算法实现：typedef struct LNode int data; struct LNode * link; * LinkList;int SearchN(LinkList list,int k)LinkList p,q;int count=0; /*计数器赋初值*/p=q=list->link; /*p和q指向链表表头结点的下一个结点*/while(p!=NULL)if(count<k) count+; /*计数器+1*/else q=q->link;/*q移到下一个结点*/ p=p->link; /*p移到下一个结点*/if(count<k)return(0);/*如果链表的长度小于k,查找失败*/ else printf("%d",q->data); /*查找成功*/ return (1);/else/SearchN 2010 1-5：DCDCB 6-11：ACBBDA41.（1）构造的散列表如下下标0123456789关键字71481130189（2）查找成功的平均查找长度:ASL成功=12/7。 查找不成功的平均查找长度:ASL不成功=18/7。42.（1）给出算法的基本设计思想：先将n个数据x0x1xpxn-1原地逆置，得到xn-1xpxp-1x0,然后再将前n-p个和后p个元素分别原地逆置，得到最终结果:xpxp+1xn-1x0x1xp-1。（2）算法实现： void reverse(int r,int left,int right) int k=left,j=right,temp; /k等于左边界left,j等于右边界right while(k<j)/交换rk和rj temp=rk; rk=rj; rj=temp; k+;/k右移一个位置 j-;/j左移一个位置 void leftShift(int r,int n,int p)if(p>0&&p<n)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)。2011 1-5：ABBCC 6-10：DACBA 41.高分笔记 图 最后一题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就是中位数。如果ab(假设a< p>原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如ab的序列出现，中位数必然出现在(a，b)范围内。因此可以做如下处理：舍弃a所在序列A之中比较小的一半，同时舍弃b所在序列B之中比较大的一半。在保留的两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列只含一个元素为止，则较小者即为所求中位数。(2)算法实现(高效方法)：(8分)int Search(int A, int B, int n) int s1,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(Amid1=Bmid2) return Amid1;if(Amid1< p)/分别考虑奇数和偶数，保持两个子数组元素个数相等 if(s1+e1)%2=0)/若元素个数为奇数 s1=mid1;/舍弃A中间点以前部分且保留中间点 e2=mid2; /舍弃B中间点以后部分且保留中间点 /if else/若元素个数为偶数 s1=mid1+1;/舍弃A中间点以前部分且保留中间点 e2=mid2; /舍弃B中间点以后部分且保留中间点 /else/ifelse if(s1+e1)%2=0)/若元素个数为奇数个 e1=mid1;/舍弃A中间点以后部分且保留中间点 s2=mid2;/舍弃B中间点以前部分且保留中间点 /if else /若元素个数为偶数个 e1=mid1+1;/舍弃A中间点以后部分且保留中间点 s2=mid2;/舍弃B中间点以前部分且保留中间点 /else/else /while return (As1) /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)。2012 1-5：BAABC 6-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(len1>len2) longList=L1->next; shortlist=L2->next; L=len1-len2;/表长之差 /if else longList=L2->next; shortlist=L1->next; L=len2-len1;/表长之差 /else While(L-) longList=longList->next; while(longList!=NULL) if(longList=shortList)/同步寻找共同结点 returnlongList; else longList=longList->next; shortlist=shortlist->next; /else /while returnNULL;/Search_First_Common（3）算法的时间复杂度为O(len1+len2)，空间复杂度为O(1)。2013 1-5：DCDBA 6-10：CCDCA 41.（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=A0;/设置A0为候选主元素 for(i=1;i<n;i+)/查找候选主元素 if(Ai=c) count+;/对A中的候选主元素计数 else if(count>0) count-;/处理不是候选主元素的情况 else/更换候选主元素，重新计数 c=Ai; count=1; /else /for if(count>0) for(i=count=0;i<n;i+)/统计候选主元素的实际出现次数 if(Ai=c) count+; if(count>n/2)returnc;/确认候选主元素 elsereturn-1;/不存在主元素/Majority42.（1）采用顺序存储结构，数据元素按其查找概率降序排列。（2分）采用顺序查找方法。（1分）查找成功时的平均查找长度=0.351+0.352+0.153+0.154=2.1。（2分）（2）【答案一】采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。（2分）采用顺序查找方法。（1分）查找成功时的平均查找长度=0.351+0.352+0.153+0.154=2.1。（2分）【答案二】采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。（2分）2014 1-5：CBADC 6-11：DDDDBC41解答：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。1）算法的基本设计思想：基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积；若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一；最后返回计算出的wpl即可。基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计wpl；当遍历到非叶子结点时对该结点的把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增1；队列空时遍历结束，返回wpl2)二叉树结点的数据类型定义如下：typedef struct BiTNode int weight; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;3)算法代码如下：基于先序遍历的算法：intWPL(BiTreeroot) return wpl_PreOrder(root,0);/intintwpl_PreOrder(BiTreeroot,intdeep) static int wpl=0;/定义一个static变量存储wpl if(root->lchild=NULL&&root->lchild=NULL)/若为叶子结点，累积wpl wpl+=deep*root->weight; if(root->lchild!=NULL)/若左子树不空，对左子树递归遍历 wpl_PreOrder(root->lchild,deep+1); if(root->rchild!=NULL)/若右子树不空，对右子树递归遍历 wpl_PreOrder(root->rchild,deep+1); return wpl;/wpl_PreOrder基于层次遍历的算法：#defineMaxSize100 /设置队列的最大容量int wpl_LevelOrder(BiTree root) BiTree qMaxSize; /声明队列，end1为头指针，end2为尾指针 int end1, end2; /队列最多容纳MaxSize-1个元素 end1=end2=0; /头指针指向队头元素，尾指针指向队尾的后一个元素 int wpl=0, deep=0; /初始化wpl和深度 BiTree lastNode; /lastNode用来记录当前层的最后一个结点 BiTree newlastNode; /newlastNode用来记录下一层的最后一个结点 lastNode=root; /lastNode初始化为根节点 newlastNode=NULL; /newlastNode初始化为空 qend2+=root; /根节点入队 while(end1!=end2) /层次遍历，若队列不空则循环 BiTree t=qend1+; /拿出队列中的头一个元素 if(t->lchild=NULL&&t->lchild=NULL) wpl+=deep*t->weight; /若为叶子结点，统计wpl if(t->lchild!=NULL) /若非叶子结点把左结点入队 qend2+=t->lchild; newlastNode=t->lchild; /并设下一层的最后一个结点为该结点的左结点 if(t->rchild!=NULL) /处理叶节点 qend2+=t->rchild; newlastNode=t->rchild; /if if(t=lastNode)/若该结点为本层最后一个结点，更新lastNode lastNode=newlastNode; deep+=1; /层数加1 /if/whilereturn wpl; /返回wpl/wpl_LevelOrder注意：上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，读者应当选取自己最擅长的书写方式。直观看去，先序遍 历 代 码 行 数 少，不用运用其他工具，书写也更容易，希望读者能掌握。在先序遍历的算法中，static是一个静态变量，只在首次调用函数时声明wpl并赋值为0，以后的递归调用并不会使得wpl为0，具体用法请参考相关资料中的static关键字说明，也可以在函数之外预先设置一个全局变量，并初始化。不过考虑到历年真题算法答案通常都直接仅仅由一个函数构成，所以参考答案使用static。若对static不熟悉的同学可以使用以下形式的递归：int wpl_PreOrder(BiTree root,intdeep) int lwpl, rwpl; /用于存储左子树和右子树的产生的wpl lwpl=rwpl=0; if(root->lchild=NULL&&root->lchild=NULL) /若为叶子结点，计算当前叶子结点的wpl return deep*root->weight; if(root->lchild!=NULL) /若左子树不空，对左子树递归遍历 lwpl=wpl_PreOrder(root->lchild,deep+1); if(root->rchild!=NULL) /若右子树不空，对右子树递归遍历 rwpl=wpl_PreOrder(root->rchild,deep+1); return lwpl+rwpl;/wpl_PreOrderC/C+语言基础好的同学可以使用更简便的以下形式：int wpl_PreOrder(BiTree root,int deep) if(root->lchild=NULL&&root->lchild=NULL) /若为叶子结点，累积wpl return deep*root->weight; return(root->lchild!=NULL?wpl_PreOrder(root->lchild,deep+1):0)+ (root->rchild!=NULL?wpl_PreOrder(root->rchild,deep+1):0);/wpl_PreOrder这个形式只是上面方法的简化而已，本质是一样的，而这个形式代码更短，在时间有限的情况下更具优势，能比写层次遍历的考生节约很多时间，所以读者应当在保证代码正确的情况下，尽量写一些较短的算法，为其他题目赢得更多的时间。但是，对于基础不扎实的考生，还是建议使用写对把握更大的方法，否则可能会得不偿失。例如在上面的代码中，考生容易忘记三元式(x?y:z)两端的括号，若不加括号，则答案就会是错误的。2015 1-5：DCCBD 6-11：AACBBA41.(1)算法思想：定义一个大小为N的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。(2)节点的数据结构定义如下：typedefstructNode Intdata; StructNode*next;Node;(3)intan; /全局数组标志节点的绝对值的值是否出现过voidDeleteABSEqualNode(Node*head) memset(a,0,n);/初始化为0 if(head=NULL)returnNULL; Node*p=head; Node*r=head while(p!=NULL) if(aabs(p->data)=1) /如果此绝对值已经在节点值的绝对值中出现过则 删除当前节点 r->next=p->next; deletep; p=r->next; /if else/否则，将数组中对应的元素置1，并将指针指向下一个元素 aabs(p->data)=1; r=p; p=p->next; /else /while returnhead;/DeleteABSEqualNode(4) 只遍历一次链表，所以时间复杂度为O(n)，因为申请大小为n的数组，所以空间复杂度为O(n)，（n为节点绝对值的最大值）。42.(1)邻接矩阵为： （2）0行3列的元素的含义是顶点0到顶点3的最短距离为2.（3）Bm中非零元素的含义是：假设此顶点位于i行j列，如果i=j，则表示i顶点到自己的距离为0；如果ij，则表示顶点i到达不了顶点j。