数据结构习题答案

第一章绪论1．（第18页，第（5）题）确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。(1)i=1;k=0;do{k=k+10*i;i++;}while(i=n-1)划线语句的执行次数为n-1。(2）i=1;x=0;do{x++;i=2*i;}while（in）;划线语句的执行次数为log2n。(3)for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x++;划线语句的执行次数为n(n+1)(n+2)/6。(4）x=n;y=0;while(x=(y+1)*(y+1))y++;划线语句的执行次数为n。第二章线性表1．第37页习题(2).2在类LinearList中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现。templateclassTvoidSeqListT::Invert(){Te;for(inti=1;i=length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}2．第37页习题(5)在类SingleList中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。templateclassTvoidSingleListT::invert(){NodeT*p=first,*q;first=NULL;while(p){q=p-link;p-link=first;first=p;p=q;}}3．（第37页，第7题）单链表中结点按元素值递增链接，在类SingleList中增加一个成员函数，直接实现删除结点值在a至b之间的结点(ab)。templateclassTvoidSingleListT::DeleteAb(Ta,Tb)//第37页，习题（7）{NodeT*p=first,*q=first;while(p&&p-datab){if(p-data=a){q=p;p=p-link;}elseif(q==first){q=p-link;deletep;p=first=q;}else{q-link=p-link;deletep;p=q-link;}}}4.（第37页，第8题）在类CircularList中增加一个成员函数，在不增加新结点的情况下，直接实现两个链表合并为一个链表的算法，并分析其时间复杂度。templateclassTvoidMerge(CircularListT&a,CircularListT&b){NodeT*p=b.first;while(p-link!=b.first)p=p-link;p-link=a.first-link;a.first-link=b.first-link;b.first-link=b.first;b.length=0;}templateclassTvoidMerge1(CircularListT&a,CircularListT&b){NodeT*p=b.first-link;b.first-data=b.first-link-data;b.first-link=a.first-link;a.first-link=p-link;p-link=p;b.first=p;}第三章栈与队列1．第50页习题(1）设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。1）A,B,C,D,E2)A,C,E,B,D3)C,A,B,D,E4)E,D,C,B,A答：2）和3）不能。对2）中的E，B，D而言，E最先出栈，则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3）。2.第50页习题（9）利用栈可以检查表达式中括号是否配对，试编写算法实现之。boolmatch(chara[],intn){inttop=-1;for(inti=0;in;i++)if(a[i]=='(')top++;elseif(a[i]==')')if(top-1)top--;elsereturntrue;if(top-1)returntrue;returnfalse;}3.第50页习题(10)声明并实现链式队列类LinkedQueue。templateclassTclassLinkedStack:publicStackT{public:LinkedStack();~LinkedStack();virtualboolIsEmpty()const;virtualboolIsFull()const;virtualboolGetTop(T&x);virtualboolPush(constTx);virtualboolPop();virtualvoidSetNull();private:NodeT*top;};templateclassTLinkedStackT::LinkedStack(){top=NULL;}templateclassTLinkedStackT::~LinkedStack(){NodeT*q;while(top){q=top-link;deletetop;top=q;}}templateclassTboolLinkedStackT::IsEmpty()const{return!top;}templateclassTboolLinkedStackT::IsFull()const{returnfalse;}templateclassTboolLinkedStackT::GetTop(T&x){if(IsEmpty()){coutEmptystackendl;returnfalse;}x=top-data;returntrue;}templateclassTboolLinkedStackT::Push(constTx){NodeT*q=newNodeT;q-data=x;q-link=top;top=q;returntrue;}templateclassTboolLinkedStackT::Pop(){NodeT*q=top;if(IsEmpty()){coutEmptystackendl;returnfalse;}top=top-link;deleteq;returntrue;}templateclassTvoidLinkedStackT::SetNull(){NodeT*q;while(top){q=top-link;deletetop;top=q;}}第四章数组与字符串1.给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。答：设有三维数组声明为A[n1][n2][n3]，每个元素占k个存储单元，则loc(A[i][j][k])=loc(A[0][0][0])+k*(i*n2*n3+j*n3+k)2．（第68页，第5题）给出下列稀疏矩阵的顺序三元组的行优先和列优先表示。答：3．（第68页，第6题）对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。答：4．（第69页，第15题（2））在顺序串类String中增加一个成员函数，实现统计该串中出现的字符、字符个数和每个字符出现的次数。voidString::count(charch[],int&n,intnum[]){n=0;for(inti=0;ilength;i++){intj=0;while(jn&&str[i]!=ch[j])j++;if(j==n){ch[j]=str[i];num[j]=1;n++;}elsenum[j]++;}}第五章递归1．设计一个递归算法，实现对一个有序表的顺序搜索。templateclassTintSeqListT::Search4(constT&x)const{elements[length]=1000;returnSch4(x,0);}templateclassTintSeqListT::Sch4(constT&x,inti)const{if(xelements[i])return0;elseif(x==elements[i])return++i;elsereturnSch4(x,i+1);}补充题：（2）求顺序搜索有序表失败时的平均搜索长度。设有序表为（a1,a2,…,an），通常可以假定待查元素位于a1之前，a1与a2之间，a2与a3之间,…,an-1与an之间以及an之后的共n+1个位置处的概率是相等的。答：第六章树1．第107页，第（2）题对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？答：（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵2、（1）k的i－1次方（2）（i＋k－2）/k取整（3）（i－1）k＋m＋1（4）（i－1）%k不等于02．第107页，第（4）题设对一棵二叉树进行中序遍历和后序遍历的结果分别为：（1）中序遍历BDCEAFHG（2）后序遍历DECBHGFA画出该二叉树。答：3.第107页，第（6）题的第6小题设计算法，交换一棵二叉树中每个结点的左、右子树。templateclassTvoidBTreeT::Exch(BTNodeT*p){if(p){BTNodeT*q=p-lchild;p-lchild=p-rchild;p-rchild=q;Exch(p-lchild);Exch(p-rchild);}}4.第107页，第10题将图题6-24中的树转换成二叉树，并将图6-23中的二叉树转换成森林。5.第107页，第11题给出对图6-24中的树的先序遍历和后序遍历的结果。答：先序：A，D，E，F，J，G，M，B，L，H，C，K后序：J，G，F，E，D，M，H，L，K，C，B，A6.第107页，第12题分别以下列数据为输入，构造最小堆。(1)10，20，30，40，50，60，70，80(2)80，70，60，50，40，30，20，10(3)80，10，70，20，60，30，50，40（1）（2）（3）7.第107页，第13题分别以上题的数据为输入，从空的优先权队列开始，依此插入这些元素，求结果优先权队列的状态。8.第108页，第14题第（1）、（2）小题设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W为各字符的频率。（1)画出哈夫曼树（2）计算带权路径长度（2）计算带权路径长度