《数据结构》ds习题答案a

《《数据结构》ds习题答案a》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章绪论1.(第18页，第(5)题)确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。(1)i=l；k=0;do{k二k+10*i;i++;}while(i<=n~l)划线语句的执行次数为n-l。(2)i=l;x=0;do{x++;i=2*i;}while(i=(y+1)*

2、(y+1))y++;划线语句的执行次数为L6Jo第二章线性表1.第37页习题(2).2在类LinearList中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现°templatevoidSeqList::Invert0{Te;for(inti=l;i<=length/2;i++){e二elements[iT];e1ements[i-l]=elements[1ength-i];elements[length-i]=e;}}2.第37页习题(5)在类SingleList中增加一个

3、成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。tcmplatcvoidSingleList::invert(){Node*p=first,*q;first二NULL;while(p){q二p->link;p->link二first;first二p;p二q;qp第三章栈与队列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,

4、C,B,A答：2)和3)不能。对2)中的E,B,D而言，E最先出栈，则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3)。2.第50页习题(9)利用栈可以检查表达式中括号是否配对，试编写算法实现之。boolmatch(chara[],intn){inttop二T;for(inti二0;i-l)top-一；elsereturntrue;if(top>-l)returntrue;roturnfalse;}第四章数组与字符串1.给出三维数组元素A

5、[i][j][k]的存储地址loc(A[i][j][k])0答：设有三维数组声明为AEn.JM[n3],每个元素占k个存储单元，贝IJloc(A[i][j][k])=loc(A[0][0][0])+k*(i*n2*n：j+j*n3+k)2.(第68页，第5题)给出下列稀疏矩阵的006-30000000-8100题图4-5顺序三元组的行优先和列优先表示。答：z、0026010-3110-310262147232-8332-83331043310414754495449丿6）行三元组（b）列三元组1.（第68页，第6题）对题图4-5的稀疏矩阵执行矩阵转置时

6、数组num□和k[]的值。答：colo134num[col]10212k[col]01134第五章递归1.设计一个递归算法，实现对一个有序表的顺序搜索。templateintSeqList::Search4(constT&x)constjielements[length]=1000;returnSch4(x,0);}templateintSeqList::Sch4(constT&x,inti)const{if(x

7、+i;elsereturnSch4(x,i+1);第六章树1.第107页，第(2)题对于三个结点A,B和C,可分別组成多少不同的无序树、有序树和二叉树?答：(1)无序树：9棵(2)有序树：12棵(3)二叉树：30棵2.第107页，第(4)题设对一棵二叉树进行中序遍历和后序遍历的结果分别为：(1)中序遍历BDCEAF11G(2)后序遍历DECBHGFA画出该二叉树。答：1.第107页，第(6)题的第6小题设计算法，交换一棵二叉树中每个结点的左、右子树。templatevoidBTree::Exch(BTNode*p){if(p)

8、{BTNode*q=p->lchild;p->lchild=p->rchi