资源描述:
《《数据结构》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(x7、+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