数据结构习题(有答案)

1、.专业.专注.word可编辑第1章绪1.1后卜列儿种二兀组表上的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1) A= ( D , R ),其中，D = a i, a2, a 3, a，, 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

2、 = 1 , 2,3, 4, 5, 6,R= , , , , , , , 1.2设n为正整数，求卜列各程序段中的下划线语句的执行次数。(1) i=1; k=0(2) for (int i=1; i=n; i+)while(i=n-1)for (int j=1; j=n; j+)(1)集合(；：$一展(金(3(2)线性表 j j u 7 72/占)p5(3)树f (4)图%?解：(1) n-1k+=10*i ;i+； ci j=0；for (int k=1; k=n; k+)ci j=cij+aik*bkjn n n(2) Z Z Z 1 = n3ijV k x=0;y=0;for (int i

3、=1; i=n; i+)for (int j=1; j=i; j+)for (int k=1; k=j; k+) x=x+y;上31Hz j=i2i J .n(n+1)(2n+-(3) j止k壬jm im 22 T2 廿 2622_n(n+1)(n+2)61.3指出下列个算法的功能，并求其时间复杂度。 int sum1(int n)(2) int sum2 (int n) int s=0;解：int p=1,s=0;for (int i=1;i=n; i+) p*= i; s+=p;return s;for ( int i=1; i=n; i+) int p=1;for (int j=1; j

4、=i; j+) p*=j;s+=p;return s; Z i! , T(n)=O(n)i(2)工 i! , T(n)=O(n 2)i1.4算法设计有3枚硬币，其中后1枚是假的，伪币与真币重量略有小何。如何借用一架 天平，找出伪币？以流程图表示算法。开始:1日是 A=B ?:一C是伪币工是:A=C ?Bze伪币否A是伪币L尸结束上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.设a, b, c为3个整数，求其中位于中间值的整数。第2章线性表1.设计算法：在顺序表中删除值为e的元素，删除成功，返回1;否则，返回0。int Sqlist:DeleteElem( T e ) f

5、or (i=1; i=length; i+) 按值顺序查找* i可从0开始if (elemi-1= =e)/ 找到，进行删除操作 for ( j=i; jlength; j+)/ ai 至 an 依次前移Elemj-1 = elem j;length - - ;/ 表长减一return 1 ;/删除成功，返回1return 0 ;/未找到，删除不成功，返回02.分析顺序表中兀素te位算法int SqList:Locate ( Te )的时间复杂度。解：设表长为n,等概举下，每个元素被定位的概率为：p=1/n定位成功第i个元素,需比较i次，1 .1J .1 n(n + 1) n + 1f (n)

6、- *i =一工 i = =y nn y n223.对于有头结点的单链表，分别写出定位成功时，实现卜列定位 语句序列。(1)定位到第i个结点ai；p=head; j=0;while ( p & jnext; j+;(2)定位到第i个结点的前驱am ;p=head; j=0;while ( p & jnext; j+;(3)定位到尾结点；p=head;while ( p -next )p=p-next;(4)定位到尾结点的前驱。p=head;while ( p-next-next )p=p-next;4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存

7、储的是链表中首结点的地址，并以此来标识一个链表头结点：附加在第一个元素结点之前的一个结点,头指针指向头结点首元结点：指链表中的第一个元素结点头指针头结点首（元）结点.a5.对于无头结点单链表，给出删除第i个结点的算法描述。template T LinkList:Delete(int i)template T LinkList:Delete(int i)if ( head=NULL) throwelse if ( i=1) /在单链表上删除第i个数据元素表空！”; 空表，不能删删除第1个元素p=Head; x=p-data;/保存被删元素值Head= p-next ;delete p ;else

8、 / 元素定位到第ai-ip=Head; j=1 ; /定位查找起始位置while p-next & jnext; j+ ; if ( !p-next | ji-1 ); /throw删除位置不合理”；else /定位成功，进行结点删除q=p-next;x=pdata;p-next=q-next;delete q;retrun x; /返回被删除元素值/#6.用教材定义的顺序表的基本操作实现下列操作#include SqList.h template template int DeleteElem(SqList L, T e)int DeleteElem(SqList L, T e) /i =

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

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

11、 SqStack S ) int i, n, A 255;n=0;while (!S.StackEmpty() ) n+; An= S.Pop(); for ( i=1; i= n ; i+) S.Push(Ai);(2) status algo_2(SqStack S, int e) SqStack T;int d;while (!S.tackEmpty() d = S.Pop();if (d!=e ) T.Push(d); 解：(1)借助一个数组，将栈中的元素逆置。(2)借助栈T,将栈S中所有值为e的数据元素删除之。while (!T.StackEmpty() d=T.Pop();T.Pu

12、sh(d); 3.编写一个算法，将一个非负的十进制整数 N转换为B进制数，并输出转换后的结果。当N=248D , B分别为8和16时，转换后的结果为多少？#include Stack.hint NumTrans( int N, int B)/十进制整数 N转换为B进制数stack S; / 建立一个栈while( N!=0) / N 非零i=N%B ;/从低到高，依次求得各位N=N/B;S.push(i); / 各位入栈while ( !S.StackEmpty() 栈不空 i= S.pop()；If (i9) i= A+10-i;cout S.pop(); /依次出栈，得到从高到低的输出结果

13、/#4借且栈，设计算法：假设一个算术表达式中包含解：以字符串存储表达式，也可以边输入边判断号，对一个合法的数学表达式来说，括号（和“应是相互匹配的。若匹配，返回1;否则，返回0。顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹配；否则，括号不匹配，多左括号。int blank_match(char *exp)用子符串存表达式SqStack s;/ 创建一个栈char *p=exp; /工作指针p指向表达式首while ( *p!= =) /不是表达式结束符switch(p) case (: /左括号,入栈s.p

14、ush(ch); break;case ) / 右括 pif (s.StackEmpty() return 0;/ 栈空,不匹配,多右括号else s.Pop(); break; 左括号出栈switchp+; 取表达式下一个字符/ whileif (!s.StackEmpty()/表达式结束,栈不空return 0 ; /小匹配，多左括号elsereturn 1 ; / 匹配/#5.简述栈和队列的逻辑特点，各举一个应用实例。6.写出下列中缀表达式的后缀表达式。-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3) A&B|!(EF)(1) A-B+C-D+(2) AB+D*EFAD

15、*+/+C+(3) AB&EF ! |7.计算后缀表送式：4 5 * 3 2 + - 的值。解：158.将下列递推过程改写为递归过程。void recursion( int n )int i=n;while( i1) cout1) courx;if (x=0) sum=0;else test(sum); sum+=x; 解:void test (int &sum) stack S; 借助一个栈int x;cinx;while (x) S.push(x);cinx; coutsum;sum=0;coutsum;while ( x=S.pop() ) sum+=x; coutsum; /10.简述

16、以下算法的功能（栈和队列的元素类型均为int)。解：利用栈,将队列中的元素逆置void algo (Queue & Q)Stack S; 创建一个栈 int d;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 。与 出这样设计的循环队列入队、出队的算法。解：采用教材队

17、空与队满判别方法。为了区分队空与队满条件，牺牲一个元素空间。即：rear=front , 为队空；rear=(front+1)%m ,为队满。template void EnQueue( T Se, T e, int m ) 入队if ( rear+1)%m =fornt )队满，不能插入throw 队满，不能才1入！”else rear = (rear+1) % m ; /队尾指针后移serear=e; /九素入队return ;/#template T DnQueue( T Se口，int m )/ 出队if ( rear= =fornt )/ 队空，不能出队！throw 队空，不能出队！

18、”else front = (front+1)%m ;/指针后移，指向队首元素e =sefront; 取队return e ;/#上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.借助栈，实现单链表上的逆置运算 。第4章串1.试问执行以下函数会产生怎样的输出结果解：t= THESE ARE BOOKSvoid demonstrate()v= YXYw= XWXWXWStrAssign( s, THIS IS A BOOK);StrRep ( s, StrSub(s, 3, 7), ESE ARE);StrAssign( t, StrConcat ( s, S);StrAs

19、sign(u, XYXYXYXYXYXY);StrAssign(v, StrSub ( u, 6, 3 );StrAssign(w, W);cout t= tendl;cout v= v;cout u= StrRep(u, v, w); / demonstrate2.设字符串 S= aabaabaabaac , P= aabaac1）给出S和P的next值和nextval值；2）若S作主串，P作模式串，试给出KMP算法的匹配过程。1) S 的 next 与 nextval 值分另为 012123456789 和 002002002009 ,p的next与nextval值分另为 012123和0

20、020032)利用KMP算法的匹配过程：趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaac(aa)baac第三趟匹配 ：aabaabaabaac(成功)(aa)baac3.算法设计串结构定义如下：struct SStringchar *data ；/ 串首址int len; / 串长int StrSize ; /存放数组的最大长度；如果不出现，则为0。(1)编写一个函数，计算一个子串在一个字符串中出现的次数， 解：int str_count (SString S, SString T) for ( i=0; S.datai; i+)int i,

21、j,k, count=0;int str_count (SString S, SString T )for ( j=i, k=0; (S.dataj=T.datak; j+,k+) if ( k= =T.len-1)count + +;return count;(2)编写算法，从串s中删除所有和串t相同的子串。解：int SubString_Delete(SString &s, SString t )从串s中删除所有与t相同的子串，并返回删除次数for ( n=0, i=0; i=s.len-t.len; i+ )for ( j=0; j t.len) 找到了与t匹配的子串for ( k =

22、i; ks.len-t.len; k+ )sk=sk+t.len; /左移删除5.1 en-=t.len ;n+; 被删除次数增1 /forreturn n;Delete_SubString(2)编写一个函数，求串s和串t的一个最长公共子串解：void maxcomstr( SString *s, SString *t) void maxcomstr( SString *s, SString *t)int index=0,len1=0, i,j,k,len2;i=0;/作为扫描s的指针while ( i s.len) j = 0;/作为扫描t的指针while ( j len1) 将较大长度者给

23、 index和lenlindex=i;len1=len2;j + = len2;/if else j+;/whilecout ”最长公共子串for ( i=0; ilen1; i+;)couts.dataindex+1;/ #1.已知下列字符串a = THIS, f = A SAMPLE, c = GOOD, d =NE, 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

24、= 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。试利用下列运算,将s转化 为t。联接：StrConcat ( &S,T )求: (char *) StrSub( S, i, len )置换：StrRep ( &S, T, R )上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。串结构定义如下：struct SStringchar *da

25、ta ;串首址int len;/ 串长int StrSize ; /存放数组的最大长度.;求：串S所含不同字符的总数和每种字符的个数，/、区分英文字母的大小写。第5章数组与压缩矩阵1.假设有二维数组A6X8,每个元素用相邻的 6个字节存储，存储器按解：（1） 6X8X6 = 288Byte字节编址。已知A的起始存储位置（基地址）为1000,计算：数组A的体积（即存储量）（2）数组A的最后一个元素a57的第一个字节的地址（3）按行存储时，元素a14的第一个字节的地址（4）按列存储时，元素a47的第一个字节的地址(2) 1000+288-6=1282(3) 1000+(1 X8+4) X6=1072(4) 1000+(7 X6+4) X6=12762.假设按低下标优先存储整数数组A9 X 3X5 X时，第一个元素的字节地址解：（1）100是100,每个整数占四个字节。问下列元素的存储地址是什么 a 0000(2) a 8247(