1999年试题答案: void MergeList L(LinkList &La, LinkList &Lb, LinkList &lc) 已知单链线性表La和Lb的元素按值非递减排列。 归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列 pc=La; ∥用La的头结点作为Lc的头结点 while(pa&&pb) i pc->next=pa; pc=pa pa=pa->next; j else ipc->next=-pb pc=pb pb=pb->next pc->next=pa?pa: pb ∥插入剩余段 free(Lb) ∥释放Lb的头结点 ://MergeList L Void enqueue( Dual Stack Q, Data lype a if(!Q Stack Full(D))Qpush(a, 1); else return("overflow") Data lype dEqueue( DualStack Data lype a fif((Q Stack Empty (l)&&Q Stack Empty(2))) fif(! Q Stack Empty (2))a=- pop(2) else while(!Q Stack Empty(1)Q- push(Q- pop( 1), 2), a=Q-pop(2); else return("Infeasible") void Traverse level( Bitree bt) Enqueue( Q, bt while(! Queue Empty(Q)
1999 年试题答案： 1． void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc) //已知单链线性表 La 和 Lb 的元素按值非递减排列。 //归并 La 和 Lb 得到新的单链线性表 Lc，Lc 的元素也按值非递减排列。 { pa=La->next;pb=Lb->next; Lc=pc=La; //用 La 的头结点作为 Lc 的头结点 while(pa&&pb) { if(pa->datadata) { pc->next=pa; pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放 Lb 的头结点 }//MergeList_L 2． Void enqueue(Dual Stack Q, DataType a ) { if(!Q.StackFull(1)) Q.push(a,1); else return("overflow"); } DataType dlqueue(DualStack Q) DataType a; {if(!(Q.StackEmpty(1)& &Q.StackEmpty(2))) {if(!Q.StackEmpty(2)) a=Q.pop(2); else {while(!Q.StackEmpty(1)) Q.push(Q.pop(1),2); a=Q.pop(2); } return(a); } else return("Infeasible"); } 3． void Traverse_level(Bitree bt) {Initqueue(Q); Enqueue(Q,bt); while (!QueueEmpty(Q))
visit(Q) if(!v->lchild)Enqueue(Q, v->lchild); if(v-rchild)Enqueue( Q, v->rchild) maino Datatype preorder[n inorder[n Struct link *bt 0,n-1), struct link *creatBT(int prestart, int preen, int instart, int inend) i p=(struct link *)malloc(sizeof( struct link)); p->lchild=null; p->rchild=null p->data= prestart f for(iinstart inorder[i==preorder(start); 1++) p->lchild=creatBT(prestart+l, prestart-instart+i, instart, i-1) p->rchild=creatBT(prestart-instart+i+l, preen, i+l, inend); return(p) hashtable del hashtable(hashtable &hash, keytype k) if( hash[t]==null) return("infeasible); else if (hash[t]==K) hash(t]=hash(t]->next else found=0; sh[t] p=hash(t]->next while((I found)&&(po null)) if(! found )ret
{v=Dlqueue(Q); visit(Q); if(!v->lchild)Enqueue(Q,v->lchild); if(!v->rchild)Enqueue(Q,v->rchild); } } 4． main() {Datatype preorder[n],inorder[n]; Struct link *BT; If (n>0) BT=creat(0,n-1,0,n-1); Return(BT); } struct link * creatBT(int prestart, int preend, int instart, int inend) {p=(struct link *)malloc(sizeof(struct link)); p->lchild=null;p->rchild=null; p->data=preorder[prestart]; if (prestartinstart) p->lchild=creatBT(prestart+1,prestart-instart+i,instart,i-1); if (irchild=creatBT(prestart-instart+i+1,preend,i+1,inend); } return(p); } 5． hashtable del_hashtable (hashtable &hash, keytype K) {t=h(k); if ( hash[t]= = null) return (“infeasible”); else if (hash[t]= =K) hash[t]=hash[t]->next; else { found=0; q=hash[t]; p=hash[t]->next; while ((!found)&&(p<> null)) if ( p->key= =K) {found=1; q->next=p->next; } else{q=p; p=p->next;} if(!found) return (“infeasible”);
return(hash); 1)(有多种答案) 2)(有多种答案) 3) 二叉排序树:
} return(hash); } 6． 1）（有多种答案） 2）（有多种答案） 3） 7． 二叉排序树： 12 1 4 3 7 2 8 10
平衡二叉树: 1)12210206184163082 2)621048122830201618 3)301020122416682818 9 不是堆 极小化堆为12243365335648928670 平均时间 最坏情况 辅助存储 堆排序 O(n log n) O(n log n) 快速排序 O(n log n) O(log n) 2812162830 46101820
平衡二叉树： 4 2 8 1 3 7 12 10 8 1) 12 2 10 20 6 18 4 16 30 8 28 2) 6 2 10 4 8 12 28 30 20 16 18 3) 30 10 20 12 2 4 16 6 8 28 18 9. 不是堆, 极小化堆为 12 24 33 65 33 56 48 92 86 70 平均时间 最坏情况 辅助存储 堆排序 O(n log n) O(n log n) O(1) 快速排序 O(n log n) O(n2 ) O(log n) 10. 2 8 12 16 28 30 4 6 10 18 20