数据结构2007试题(a)-答案

图2构造平衡二叉树过程评分标准:除第一步外,每插入一个元素占1分,每次调整占2分。4.答:不能。因为在这里,二分查找只减少了关键字间的比较次数,而记录的移动次数不变,时间的复杂度仍为O(n2)。评分标准:答对“不能”占3分,说明理由占5分。5.答:生成初始归并段(或顺串),采用多路平衡归并方法进行归并。四、算法设计题(共30分)1.设计一个在带头结点的单链表L中删除一个最小值结点的算法。解:用p从头至尾扫描单链表,pre指向*p结点的前驱,用minp保存值最小的结点指针,minpre指向*minp结点的前驱。一面扫描,一面比较,将最小值的结点放到*minp中。算法如下:voiddelminnode(LinkList*&L){LinkList*pre=L,*p=pre->next,*minp=p,*minpre=pre;while(p!=NULL)//查找最小值结点*minp及其前驱结点*minpre{if(p->data<minp->data){minp=p;数据结构期末考试试题(共3页)5minpre=pre;}pre=p;p=p->next;}minpre->next=minp->next;//删除*minp结点free(minp);}评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。2.假设二叉树采用二叉链存储结构存储,设计一个算法,由二叉树b复制成另一棵二叉树t。(15分)解:递归算法如下:voidcopy(BTNode*b,BTNode*&t){BTNode*l,*r;if(b==NULL)t=NULL;else{t=(BTNode*)malloc(sizeof(BTNode));copy(b->lchild,l);copy(b->rchild,r);t->lchild=l;t->rchild=r;}}评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。