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

希望对你有帮助。。。。

答案与试题是配套的   选择题没有解析  有不懂得可以在文库上@我

2009  1-5：BCDBC        6-10：BADBA

41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从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）算法实现：

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        else q=q->link;/*q移到下一个结点*/

           p=p->link; /*p移到下一个结点*/

    }

    if(count   else    { printf("%d",q->data); /*查找成功*/

          return (1);}//else}//SearchN 

2010   1-5：DCDCB       6-11：ACBBDA

41.（1）构造的散列表如下

 查找不成功的平均查找长度: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）算法实现：

 void reverse(int r[],int left,int right){

     int k=left,j=right,temp; //k等于左边界left,j等于右边界right

     while(k         temp=r[k];

         r[k]=r[j];

         r[j]=temp;

         k++;//k右移一个位置

         j--;//j左移一个位置

     }

 }

void leftShift(int r[],int n,int p){

if(p>0&&p        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就是中位数。

如果a≠b(假设a< p>

原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如…a…b…的序列出现，中位数必然出现在(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(A[mid1]==B[mid2])   return A[mid1];

　　if(A[mid1]< p){//分别考虑奇数和偶数，保持两个子数组元素个数相等

　　  if((s1+e1)%2==0){//若元素个数为奇数

　　   s1=mid1;//舍弃A中间点以前部分且保留中间点

　　   e2=mid2; //舍弃B中间点以后部分且保留中间点

　　  }//if

　　  else{//若元素个数为偶数

　　   s1=mid1+1;//舍弃A中间点以前部分且保留中间点

　　   e2=mid2; //舍弃B中间点以后部分且保留中间点

　　  }//else

　　}//if

　　else{

　　 if((s1+e1)%2==0){//若元素个数为奇数个

　　  e1=mid1;//舍弃A中间点以后部分且保留中间点

　　  s2=mid2;//舍弃B中间点以前部分且保留中间点

　　 }//if

　　 else {//若元素个数为偶数个

　　  e1=mid1+1;//舍弃A中间点以后部分且保留中间点

　　  s2=mid2;//舍弃B中间点以前部分且保留中间点

　　 }//else

　}//else

 }//while

 return (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)。

2012   1-5：BAABC       6-11：CCADAD

41.高分笔记 排序 最后一题

42.（1）算法思想：顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路： 

①遍历两个链表求的它们的长度L1，L2； 

②比较L1，L2，找出较长的链表，并求L=|L1-L2|；

③先遍历长链表的L各结点；

④同步遍历两个链表，直至找到相同结点或链表结束。

（2）算法的C语言代码描述 

LinkList Search_First_Common(LinkList L1,LinkList L2){

//本算法实现线性时间内找到两个单链表的第一个公共结点 

  int len1=Length(L1),len2=Length(L2); 

  LinkList longList,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)//同步寻找共同结点 

      return longList; 

    else{ 

      longList=longList->next; 

      shortlist=shortlist->next; 

    } //else

  }//while 

  return NULL; 

}//Search_First_Common 

（3）算法的时间复杂度为O(len1+len2)，空间复杂度为 O(1)。

2013   1-5：DCDBA       6-10：CCDCA

 （1）给出算法的基本设计思想：（4分）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。算法可分为以下两步：①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中记录Num的出现次数为1；若遇 到 的下一个 整  数 仍  等 于Num

则计数加一，否则计数减一；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。②判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。

（2）算法实现：（7分） 

int Majority ( int A[ ], int n ) { 

  int i, c, count=1; / / c用来保存候选主元素，count用来计数 

   c = A[0];  / / 设置A[0]为候选主元素 

  for ( i=1; i     if ( A[i] = = c )    count++; / / 对A中的候选主元素计数

    else

       if ( count > 0)   count--;/ / 处理不是候选主元素的情况

       else { / / 更换候选主元素，重新计数

            c = A[i];

          count = 1;

      }//else

  }//for 

  if ( count>0 ) 

  for ( i=count=0; i     if ( A[i] = = c ) 

      count++; 

  if ( count> n/2 ) return c; / / 确认候选主元素 

  else return -1; / / 不存在主元素

}//Majority

42.（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分）

2014   1-5：CBADC       6-11：DDDDBC

41．解答：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。

1）算法的基本设计思想：

①基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积；若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一；最后返回计算出的wpl即可。

②基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计wpl；当遍历到非叶子结点时对该结点的把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增1；队列空时遍历结束，返回wpl

2)二叉树结点的数据类型定义如下：

typedef struct BiTNode{

  int weight;

   struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

3)算法代码如下：

①基于先序遍历的算法：

intWPL(BiTreeroot){

  return  wpl_PreOrder(root,0);

}//int

intwpl_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  q[MaxSize];    //声明队列，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初始化为空

   q[end2++]=root;  //根节点入队

   while(end1!=end2){  //层次遍历，若队列不空则循环

       BiTree t=q[end1++]; //拿出队列中的头一个元素

     if(t->lchild==NULL&&t->lchild==NULL)

             wpl+=deep*t->weight;  //若为叶子结点，统计wpl

     if(t->lchild!=NULL){  //若非叶子结点把左结点入队

        q[end2++]=t->lchild;

        newlastNode=t->lchild;

     }  //并设下一层的最后一个结点为该结点的左结点

     if(t->rchild!=NULL){   //处理叶节点

        q[end2++]=t->rchild;

        newlastNode=t->rchild;

    }//if

     if(t==lastNode){//若该结点为本层最后一个结点，更新lastNode

       lastNode=newlastNode;

        deep+=1;   //层数加1

    }//if

}//while

return 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_PreOrder

C/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：AACBBA

41.(1) 算法思想： 定义一个大小为N的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。

(2) 节点的数据结构定义如下： 

typedef struct Node { 

  Int data; 

  Struct Node * next; 

}Node; 

(3) int a[n];    // 全局数组标志节点的绝对值的值是否出现过 

void DeleteABSEqualNode(Node * head) { 

   memset(a,0,n); // 初始化为0 

   if (head == NULL)  { return NULL; } 

   Node * p = head;  

   Node * r = head

   while (p != NULL) { 

     if (a[abs(p->data)] == 1){

          //如果此绝对值已经在节点值的绝对值中出现过则   删除当前节点 

        r->next = p->next;  delete p;   p = r->next; 

     } //if

     else { //否则，将数组中对应的元素置1，并将指针指向下一个元素

       a[abs(p->data)] = 1;   r = p;   p = p->next; 

     }//else 

  } //while 

  return head; }//DeleteABSEqualNode

(4) 只遍历一次链表，所以时间复杂度为O(n)， 因为申请大小为n的数组，所以空间复杂度为O(n)，（n为节点绝对值的最大值）。

42.(1)邻接矩阵为：

（2）0行3列的元素的含义是顶点0到顶点3的最短距离为2.

（3）Bm中非零元素的含义是：假设此顶点位于i行j列，如果i==j，则表示i顶点到自己的距离为0；如果i≠j，则表示顶点i到达不了顶点j。

（资料素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）