《数据结构》期末考试试题及答案

第三趟:[12 18 25 53] 18Р第四趟:[12 18 18 25 53] (4分)Р O(n2)(1分)。Р5、7分Р(1)4分РAР B 1 C Р 3 2Р 5 D 4 Р E FР(2)4分Р6、(1) 3分Р Р Р Р E FР Р A B C DР Р Р(2)WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分)Р(3)A:010 B:011 C:110 D:111 E:00 F;10 (3分)Р12、A-B:(A、B) 1分РA-C:(A、D、C) 2分РA-D:(A、D) 1分Р A-E:(A、D、E) 2分Р 三,设计题(20分)Р1、(10分)РStatus ListDelete(Sqlist &L,ElemType x)Р{Р int i,j;Р for(i=0;i<L->length;i++)Рif(L->elem[i]==x) break;Р if(i=L->length) return ERROR;Р for(j=i;j<L->lengthi-1;j++)Р L->elem[j]=L->elem[j+1];Р L->length--;Р} (8分)Р平均时间复杂度:(2分)Р设元素个数记为n,则平均时间复杂度为:Р2(10分)Рvoid pop(Stack &S,Elemtype &e)Р{Р if(S.top==S.base) return ERROR;Р S.top--;Р e=*s.top;Р}Р2、(10分)РvoidCountLeaves(BinTree T,int &n)Р{Рif(T)Р{Рif((!(T->lchild)&&!( T->rchild)) n++;Р CountLeaves (T->lchild,n);Р CountLeaves (T->rchild,n);Р}Р}