西安电子科技大学《数据结构》2009答案.pdfVIP

数据结构试题参考答案 一．C A BAD  C C B BA  B C C D C  二 1．012341  2．O(nLogn)  3. q­next=s­next;s­next p;  2  4. O(n),O(n )  5. (rear+m­front)%m  6. n  7.4  8. 20 15 12 30 35 83 47 76  9. 15 28 36 97 24 47 52 78 13 86  10. 499  三．  1． 先序：G H I J  后序：H J I G  2．  0  ^  1  ^  2  ^  3  25  36  ^  4  48  70  ^  5  ^  6  94  ^  7  18  ^  8  63  ^  9  75  ^  10  32  ^  查找成功：ASL  =(1*7+2*2)/9=11/9  成功 查找失败：ASL  =(2*2+5*1)/11=9/11  失败 3.  (1)  0:A B  1:B 2:C E A B  3:D E A B C  4: E A B  (2)算法f的功能是输出有向图从任意一个顶点开始进行 1次深度遍历所能访问到的顶点序列  4．  (1) 21  8  7  29  41  63  43  58  (2) 8  7  21  43  58  63  29  41  (3)  不是堆，调整为小顶堆后如图所示  7  8  21  41  58  63  29  43  四.  (1)  void f(LinkList head){  LinkNode *p new node();  if(head NULL){  head=p;  p­next p;  }  else{  p­next head;  LinkList t=head;  while(t­next!=NULL)t=t­next;  t­next=p;  head=p;  }  }  算法时间复杂度为 O(n)  (2)  void f(BiThrTreet,int a,int b){  p=t­lchild;  //p 指向根节点  while(p!=t){  //空树或遍历结束  while(p­ltag Link)p=p­lchild;  if(p­data.key b)break;  else if(p­data.keya)  coutp­data.key;  while(p­rtag Threadp­rchild!=tp­data.keyb){  if(p­data.keya) coutp­data;  p=p­rchild;  }  p=p­rchild;  }  }  该算法建立在遍历中序线索二叉树的基础上，算法复杂度为 O(n)。