数据结构习题有答案

1、第1章绪1.1 后卜列儿种二兀组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1) A=(D,R),其中，D=ai,a2,a3,包,R=(2) B=(D,R),其中，D=a,b,c,d,e,R=(a,b),(b,c),(c,d),(d,e)(3) C=(D,R)，其中，D=a,b,c,d,e,f,g,R=(d,b),(d,g),(b,a),(b,c),(g,e),(e,f)(4) K=(D,R),其中，D=1,2,3,4,5,6,R=<1,2>,<2,3>,<2,4>,<3,4>,<3,5>,<3,

2、6>,<4,5>,<4,6>1.2设n为正整数，求下列各程序段中的下划线语句的执行次数。(1)i=1;k=0while(i<=n-1)k+=10*i;i+;(2)for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)cij=0;for(intk=1;k<=n;k+)cij=cij+aik*bkjx=0;y=0;for(inti=1;i<=n;i+)for(intj=1;j<=i;j+)for(intk=1;k<=j;k+)x=x+y;(1)集合(2)线性表77777)(2(3)树,''

3、(4)图4)解：1 n-1nnn2 ZZZ1=n3i=1j=1k=1ZZZ1=f£j更生i2+1fi，血±典。+nn±D(2) i±j±k壬i=tj=ti=t22t22622_n(n+1)(n+2)一61.3指出下列个算法的功能，并求其时间复杂度。解：Zi!,T(n)=O(n)y(2)vi!,T(n)=O(n2)iWintsum1(intn)(intp=1,s=0;for(inti=1;i<=n;i+)p*=i；s+=p;returns;intsum2(intn)ints=0;for(inti=1;i<=n;i+)intp=1;fo

4、r(intj=1;j<=i;j+)p*=j;s+=p;结束returns;1.4算法设计1枚是假的，伪币与真币重量略有不同。如何借用一架有3枚硬币，其中有天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.设a,b,c为3个整数，求其中位于中间值的整数。1.设计算法：在顺序表中删除值为e的兀素,否则，返回0。删除成功，返回1;intSqlist<T>:DeleteElem(Te)for(i=1;i<=length;i+)/按值顺序查找*i可从0开始if(elemi-1=e)/找到，进行删除操作for(j=i;j<

5、;length;j+)/ai至an依次前移Elemj-1=elemj;length-;/表长减一return1;删除成功，返回1)return0;/未找到，删除不成功，返回0)>:Locate(Te)解：设表长为n,等概率F,每个兀素被定位的概率为：p=1/n2.分析顺序表中兀素te位算法intSqList<!的时间复杂度。定位成功第i个兀素，需比较i次'1.1",1n(n+1)n+1f(n)*iZi-ynn曰n223.对于有头结点的单链表，分别写出定位成功时，实现卜列定位语句序列。(1)定位到第i个结点ai；p=head;j=0;while(p&&

6、;j<i)p=p->next;j+;(2)定位到第i个结点的前驱a-i；p=head;j=0;while(p&&j<i-1)p=p->next;j+;(3)定位到尾结点；p=head;while(p->next)p=p->next;(4)定位到尾结点的前驱。p=head;while(p->next->next)p=p->next;4.描述一下三个概念的区别：头指针，头结点，首兀结点。并给头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。予图示。头结点：附加在第一个兀素结点之前的一个结点，头指针指向

7、头结点。首兀结点：指链表中的个兀素结点。头指针头结点首(元)结点尾(兀)结点ai|_+1a2.n1a|.对于无头结点单链表，给出删除第i个结点的算法描述。template<calssT>TLinkList<T>:Delete(inti).用教材定义的顺序表的基本操作实现下列操作:template<calssT>intDeleteElem(SqListL,Te)template<calssT>TLinkList<T>:Delete(inti)在单链表上删除第i个数据元素if(head=NULL)throw表空！”;/空表，不能删else

8、if(i=1)/删除第1个元素p=Head;x=p->data;/保存被删元素值Head=p->next;deletep;)else/元素定位到第ai-ip=Head;j=1;/定位查找起始位置whilep->next&&j<i-1p=p->next;j+;if(!p->next|j>i-1);定位失败throw删除位置不合理”；else/定位成功，进行结点删除q=p->next;x=p>data;p->next=q->next;deleteq;retrunx;/返回被删除元素值/#includeSqList.h

9、"template<calssT>intDeleteElem(SqListL,Te)/i=L.LocateElem(e);按值查找if(!i)/未找到return0;else/找到delete(i);/删除被找到的儿素7.已知L是有表头结点的单链表，且P结点既不是首兀结点，也不是尾结点，试写出实现卜列功能的语句序列。(1)在P结点后插入S结点；(2)在P结点前插入S结点；(3)在表首插入S结点；(4)在表尾插入S结点.【解】s->next=p->next;p->next=s;q=L;while(q->next!=p)q=q->next;s-&

10、gt;next=p或q->next;q->next=s;s->next=L->next;L->next=s;q=L;while(q->next!=NULL)q=q->next;s->next=q->next;q->next=s;上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。编程实现：删除单链表中值为e的兀素。解：325641可以154623不可以。第3章栈与队列1.铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问：若进站的六辆列车顺序如上所述，那么是否能够得到325641和154623的出站序列

11、，如果不能，说明为什么不能；如果能,说明如彳5得到（即写出"进栈"或"出栈"的序列）。2.简述以下算法的功能(栈的兀素类型为int)。statusalgo_1(SqStackS)inti,n,A255;n=0;while(!S.StackEmpty()n+;An=S.Pop();for(i=1;i<=n;i+)S.Push(Ai);statusalgo_2(SqStackS,inte)SqStackT;intd;while(!S.tackEmpty()d=S.Pop();if(d!=e)T.Push(d);while(!T.StackEmpty()

12、d=T.Pop();T.Push(d);解：(1)借助一个数组，将栈中的兀素逆置。(2)借助栈T,将栈S中所有值为e的数据元素删除之。3.编写一个算法，将一个非负的十进制整数N转换为B进制数，并输出转换后的结果。当N=248D,B分别为8和16时，转换后的结果为多少？#includeStack.h"intNumTrans(intN,intB)/十进制整数N转换为B进制数stack<int>S;/建立一个栈while(N!=0)/N非零i=N%B;/从低到高，依次求得各位N=N/B;S.push(i);/各位入栈while(!S.StackEmpty()/栈不空i=S.po

13、p();If(i>9)i='A'+10-i;cout<<S.pop();/依次出栈，得到从高到低的输出结果/#4借且栈，设计算法：假设一个算术表达式中包含（、”“后号,解：以字符串存储表达式，也可以边输入边判断。对一个合法的数学表达式来说，括号"（和“）应是相互匹配的。若匹配，返回1;否则，返回0。顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹配；否则，括号不匹配，多左括号。intblank_match(char*exp)用字符串存表达式SqStack<cha

14、r>s;/创建一个栈char*p=exp;工作指针p指向表达式首while(*p!='=')/不是表达式结束符switch(p)case'(':左括号，入栈s.push(ch);break;case')'/右括号if(s.StackEmpty()return0;/栈空，不匹配，多右括号elses.Pop();break;/左括号出栈/switchp+;/取表达式下一个字符/whileif(!s.StackEmpty()/表达式结束，栈不空return0;/小匹配，多左括号elsereturn1;/匹配/#5.简述栈和队列的逻辑特点，各举一个

15、应用实例。6.写出下列中缀表达式的后缀表达式。(1)-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3)A&&B|!(E>F)A-B+C-D+AB+D*EFAD*+/+C+AB&&EF!|7.计算后缀表达式：45*32+-的值。解：158.将下列递推过程改写为递归过程。voidrecursion(intn)inti=n;while(i>1)cout<<i;i-;解：voidrecurision(intj)if(j>1)cour<<j;recurision(j-1);9.将下列递归过程改写为非递归过程。voi

16、dtest(int&sum)intx;cin>>x;if(x=0)sum=0;elsetest(sum);sum+=x;cout<<sum;解：voidtest(int&sum)stackS;借助一个栈intx;cin>>x;while(x)S.push(x);cin>>x;sum=0;cout<<sum;while(x=S.pop()sum+=x;cout<<sum;"/10.简述以下算法的功能（栈和队列的兀素类型均为int）。解：利用栈，将队列中的兀素逆置voidalgo(Queue&

17、Q)(StackS;/创建一个栈intd;while(!Q.QueueEmpty()d=DeQueue(Q);S.Push(d);while(!S.StackEmpty()d=S.Pop();Q.EnQueue(d);12.假设以数组sem存放循环队列的兀素，同时设变量rear和front分别作为队首、队尾指针，且队首指针指向队首前一个位置，队尾指针指向队尾儿素处，初始时，rear=fornt=-1。与出这样设计的循环队列入队、出队的算法。解：米用教材队空与队满判别方法。为了区分队空与队满条件，牺牲一个兀素空间。即：rear=front,为队空；rear=(front+1)%m,为队满。tem

18、plate<calssT>voidEnQueue(TSe,Te,intm)/入队if(rear+1)%m=fornt)/队满，不能插入throw队满，不能插入！”elserear=(rear+1)%m;/队尾指针后移serear=e;/九素入队return;/#template<calssT>TDnQueue(TSe,intm)/出队if(rear=fornt)队空，不能出队！throw队空，不能出队！”elsefront=(front+1)%m;/指针后移，指向队首元素e=sefront;/取队首元素returne;/#上机练习题要求：给出问题分析、算法描述、源程序及

19、运行截图，在线提交。1.借助栈，实现单链表上的逆置运算。第4章串.试问执行以下函数会产生怎样的输出结果?voiddemonstrate()(StrAssign(s,'THISISABOOK');StrRep(s,StrSub(s,3,7),'ESEARE');StrAssign(t,StrConcat(s,'S');StrAssign(u,'XYXYXYXYXYXY');StrAssign(v,StrSub(u,6,3);StrAssign(w,'W);cout<<"'t="<

20、<t<<endl;cout<<“v="<<v;cout<<“u="<<StrRep(u,v,w);/demonstrate.设字符串S='aabaabaabaac',P='aabaac'1)给出S和P的next值和nextval值；2)若S作主串，P作模式串，试给出KMPB法的匹配过程。解：t=THESEAREBOOKSv=YXYw=XWXWXW1)S的next与nextval值分另为012123456789和002002002009,p的next与nextval值分另U为01

21、2123和0020032)利用KMPIT法的匹配过程：第趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaac(aa)baac第三趟匹配：aabaabaabaac(成功)(aa)baac3.算法设计串结构定义如下:structSString(char*data;/串首址intlen;/串长intStrSize;/存放数组的最大长度.)；(1)编写一个函数，计算一个子串在一个字符串中出现的次数，如果/、出现，则为0。intstr_count(SStringS,SStringT)解：intstr_count(SStringS,SStringT)inti,

22、j,k,count=0;for(i=0;S.datai;i+)for(j=i,k=0;(S.dataj=T.datak;j+,k+)if(k=T.len-1)count+;)returncount;)(2)编写算法，从串s中删除所有和串t相同的子串。解：intSubString_Delete(SString&s,SStringt)从串s中删除所有与t相同的子串，并返回删除次数for(n=0,i=0;i<=s.len-t.len;i+)for(j=0;j<t.len&&si+j=ti;j+);if(j>t.len)找至ij了与t匹配的子串for(k=i;

23、k<s.len-t.len;k+)sk=sk+t.len;/左移删除s.len-=t.len;n+;被删除次数增1/forreturnn;/Delete_SubString(2)编写一个函数，求串s和串t的一个最长公共子串。voidmaxcomstr(SString*s,SString*t)解：voidmaxcomstr(SString*s,SString*t)intindex=0,len1=0,i,j,k,len2;i=0;/作为扫描s的指针while(i<s.len)j=0;/作为扫描t的指针while(j<t.len)if(s.datai=t.dataj)/序号为i,长

24、度为len2的子串len2=1;/开始计数for(k=1;s.datai+k=t.dataj+k&&s.datai+k!=NULL;k+)len2+;if(len2>len1)/将较大长度者给index和len1index=i;len1=len2;j+=len2;/ifelsej+;/whilecout<<”最长公共子串：for(i=0;i<len1;i+;)cout<<s.dataindex+1;/#1.已知下列字符串a='THIS',f='ASAMPLE',c='GOOD',d='N

25、E',b='',s=StrConcat(a,StrConcat(StrSub(f,2,7),StrConcat(b,StrSub(a,3,2),t=StrRep(f,StrSub(f,3,6),c),u=StrConcat(StrSub(c,3,1),d),g='IS',v=StrConcat(s,StrConcat(b,StrConcat(t,StrConcat(b,u),试问：s,t,v,StrLength(s),StrIndex(v,g),StrIndex(u,g)各是什么？已知：s='(XYZ)+*',t='(X+Z)*Y

26、'。试利用下列运算，将s转化为t。联接：StrConcat(&S,T)求子串：(char*)StrSub(S,i,len)置换：StrRep(&S,T,R)上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。串结构定义如下：structSStringchar*data;/串首址intlen;/串长intStrSize;/存放数组的最大长度.;求：串S所含不同字符的总数和每种字符的个数，不区分英文字母的大小写。1.假设有二维数组A6如每个兀素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为1000,计算：数组A的体积(即存储量);(

27、2)数组A的最舟-个元素357的第一个字节的地址；(3)按行存储时，元素ai4的第一个字节的地址；(4)按列存储时，元素347的第一个字节的地址。解：(1)6X8X6=288Byte1000+288-6=1282;1000+(1X8+4)X6=10721000+(7X6+4)X6=12762.假设按低下标优先存储整数数组A9X3冯4时，A个兀素的字节地址是100,每个整数占四个字节。1可下列元素的存储地址是什么？(1)30000(2)38247解：(1)100(2)100+8X3X5X8+2>5X8+4X8+7=45003.一个稀疏矩阵如图所示_030000020500(1)给出三元组存储示意图；A=000000(2)给出带行指针向量的链式存储示意图；90000144(3)十字链表存储示意图。M.dataijeA01234013112-h013A135112235A309A351309451AM.muM.nuM.tu465(2)A.cheadA.rheadI卜Amu4r131A.nu61112I1135A.tu5AAA八(3)3I|9_31A卜-第5章数组与压缩矩阵013112135309351013A112309