数据结构习题(有答案)

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

2、6, R= <1 , 2>, <2, 3>, <2, 4>, <3, 4>, <3, 5>, <3, 6>, <4, 5>, <4, 6>(1)集合Q)线性表 G；G：-GHdJ。Q<2树(4)图J7p4)1.2设n为正整数，求下列各程序段中的下划线语句的执行次数。(1) i=1; k=0 while(i<=n-1) k+=10*i ; i+;(2) for (int i=1; i<=n; i+) for (int j=1; j<=n; j+) cij=0;for (int

3、k=1; k<=n; k+) cij=cij+aik*bkj解：n-1n n n/3(2)1 ni 1 j 1 k 1 x=0;y=0;for (int i=1; i<=n; i+)for (int j=1; j<=i; j+)for (int k=1; k<=j; k+) x=x+y;n i j 1n i .n i(i1)1 n .2 1 n .1 个n(n1)(2n 1) 1 ?n(n1)1j''- ii ?(3) i 1 j 1 k 1i 1 j 1i 122i 12i12622n(n 1)(n 2) 61.3指出下列个算法的功能，并求其时间复杂度

4、。解：i! , T(n)=O(n)i 1(2) i! , T(n)=O(n2)1 1 int sum1(int n)int p=1,s=0;for (int i=1;i<=n; i+) p*= i; s+=p;return s;(2) int sum2 (int n) int s=0;for ( int i=1; i<=n; i+) int p=1;for (int j=1; j<=i; j+) p*=j; s+=p;return s;1.4算法设计1枚是假的，伪币与真币重量略有不同。如何借用一架有3枚硬币，其中有天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析

5、、算法描述、源程序及运行截图，在线提交。1.设a, b, c为3个整数，求其中位于中间值的整数。第2章线性表1.设计算法：在顺序表中删除值为 e的兀素，删除成功，返回1;否则，返回0。int Sqlist<T>:DeleteElem( T e ) for (i=1; i<=length; i+) 按值顺序查找* i可从0开始if (elemi-1= =e)/ 找到，进行删除操作 for ( j=i; j<length; j+)/ ai 至 an 依次前移Elemj-1 = elemj;length - - ;/ 表长减一return 1 ;删除成功，返回 1return

6、 0 ;/未找到，删除不成功，返回 02.分析顺序表中兀素te位算法int SqList<T>:Locate ( T e )的时间复杂度。解：设表长为n,等概率F,每个兀素被定位的概率为：p=1/n定位成功第i个元素，需比较i次 /、n 1o.1n.1 on(n 1) n 1f (n)?ii ?i 1 nn i 1n223.对于有头结点的单链表，分别写出定位成功时，实现下列定位 语句序列。(1)定位到第i个结点既；p=head; j=0;while ( p && j<i ) p=p->next; j+;(2)定位到第i个结点的前驱a-i;p=head;

7、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.描述一下三个概念的区别：头指针，头结点，首兀结点。并给头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。予图示。头结点：附加在第一， 首兀结点：指链表W头指针头结点个兀素结点么 的个元1产(元j节点a"二前的一个结点，头指针指

8、向头结 置结点。尾(元)结点a 2 .-a n , A点。5 .对于无头结点单链表，给出删除第 i个结点的算法描述。template <calss T>T LinkList<T>:Delete(int i)6 .用教材定义的顺序表的基本操作实现下列操作:template <calss T>int DeleteElem(SqList L, T e)template <calss T>T LinkList<T>:Delete(int i) 在单链表上删除第i个数据元素 if ( head=NULL) throw 表空！”;/ 空表，不能删

9、 else if ( i=1) /删除第1个元素p=Head; x=p->data; /保存被删元素值 Head= p->next ;delete p ;else /元素定位到第 ai-ip=Head; j=1 ; /定位查找起始位置while p->next && j<i-1 p=p->next; j+ ; if ( !p->next | j>i-1 ); 定位失败 throw删除位置不合理”； else /定位成功，进行结点删除 q=p->next;x=p>data;p->next=q->next; dele

10、te q;retrun x; /返回被删除元素值/#include SqList.h "template <calss T>int DeleteElem(SqList L, T e) /i = 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

11、=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=L；while( q->next!=NULL) q=q->next; s->next= q->next ; q->next=s;上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。编程实现：删除单链表中值为 e的兀素。解：325641可以15462

12、3不可以。第3章栈与队列1.铁路进行列车调度时，常把站台设计 成栈式结构的站台，如右图所示。试问： 若进站的六辆列车顺序如上所述，那么是否能够得到325641和154623的出站序 列，如果不能，说明为什么不能；如果能, 说明如彳可得到（即写出"进栈"或"出栈"的 序列）。2.简述以下算法的功能(栈的兀素类型为int )。(1) status algo_1( SqStack S ) int i, n, A 255;n=0;while (!S.StackEmpty() ) n+; An= S.Pop();for ( i=1; i<= n ; i+)

13、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);while (!T.StackEmpty()d=T.Pop();T.Push(d); 解：(1)借助一个数组，将栈中的兀素逆置。(2)借助栈T,将栈S中所有值为e的数据元素删除之。3.编写一个算法，将一个非负的十进制整数 N转换为B进制数， 并输出转换后的结果。 当N=248D, B分别为8和16时，转换后 的结果为多少？#include stack.h"

14、;int NumTrans( int N, int B) /十进制整数 N转换为B进制数 stack<int> S; / 建立一个栈while( N!=0) / N 非零i=N%B ;/从低到高，依次求得各位N=N/B;S.push(i); / 各位入栈while ( !S.StackEmpty() / 栈不空 i= S.pop()；If (i>9) i= 'A'+10-i;cout<< S.pop(); /依次出栈，得到从高到低的输出结果 /#4借且栈，设计算法：假设一个算术表达式中包含“(、” “睛号，对一个合法的数学表达式来说，括号"

15、;(和“)应是相互匹配的。若匹配，返回1;否则，返回0。解：以字符串存储表达式，也可以边输入边判断。顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹 配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹配；否则，括 号/、匹配，多左括号。int blank_match(char *exp) 用子符串存表达式SqStack<char> s;/ 创建一个栈char *p=exp;工作指针p指向表达式首while ( *p!= = ) /不是表达式结束符switch(p) case (: 左括号，入栈s.push(ch); break;case )/ 右括

16、 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|!(E>F)(1) A-B+C-D+(2) AB+D*EFAD*+/

17、+C+(3) AB&&EF ! |7.计算后缀表达式：4 5 * 3 2 + -的值。解：158.将下列递推过程改写为递归过程。void recursion( int n )int i=n;while( i>1) cout<<i; i-; 解：void recurision(int j) if (j>1) cour<<j;recurision(j-l); 9.将下列递归过程改写为非递归过程。void test( int &sum) int x;cin>>x;if (x=0) sum=0;else test(sum); su

18、m+=x; cout<<sum;解：void test (int &sum) stack S; 借助一个栈int x;cin>>x;while (x) S.push(x);cin>>x; sum=0;cout<<sum;while ( x=S.pop() ) sum+=x; cout<<sum; "/10.简述以下算法的功能（栈和队列的兀素类型均为int ）。解：利用栈，将队列中的兀素逆置void algo (Queue &Q)Stack S; 创建一个栈int d;while (!Q.QueueEmpty(

19、)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 ,为队满。template <calss T>void EnQueue(

20、T Se, T e, int m ) / 入队if ( rear+1)%m =fornt ) / 队满，不能插入throw 队满，不能插入！”else rear = (rear+1) % m ; /队尾指针后移serear=e; / 九素入队return ;/#template <calss T>T DnQueue( T Se, int m ) / 出队if ( rear= =fornt )队空，不能出队！throw 队空，不能出队！”elsefront = (front+1)%m ; / 指针后移，指向队首元素 e =sefront; /取队首元素 return e ; /#上机

21、练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.借助栈，实现单链表上的逆置运算。第4章串1 .试问执行以下函数会产生怎样的输出结果?void demonstrate()StrAssign( s, 'THIS IS A BOOK');StrRep ( s, StrSub(s, 3, 7), 'ESE ARE');StrAssign( t, StrConcat ( s, 'S');StrAssign(u, 'XYXYXYXYXYXY');StrAssign(v, StrSub ( u, 6, 3 );StrAssi

22、gn(w, 'W);cout<< " 't=" << t<<endl;cout<< “v= " << v;cout<< “u=" << StrRep(u, v, w); / demonstrate2 .设字符串 S= ' aabaabaabaac' , P= ' aabaac'1)给出S和P的next值和nextval值；2)若S作主串，P作模式串，试给出 KMPB法的匹配过程。解：t= THESE ARE BOOKSv=

23、YXYw= XWXWXW1) S 的 next 与 nextval 值分另为 012123456789 和 002002002009 p的next与nextval值分另为 012123和0020032)利用KMPIT法的匹配过程：第趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配： aabaabaabaac(aa)baac第三趟匹配：aabaabaabaac( 成功)(aa)baac3.算法设计串结构定义如下:struct SStringchar *data；/ 串首址int len;/ 串长int StrSize ; /存放数组的最大长度.；(1)编写一个函数，计算一

24、个子串在一个字符串中出现的次数，如果/、出现，则为0。int str_count (SString S, SString T )解：int str_count (SString S, SString T) int i, 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 + +;return count;(2)编写算法，从串s中删除所有和串t相同的子串。解：int SubString_Delete(SString &s, SString t

25、 )从串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; k<s.len-t.len; k+ )sk=sk+t.len; 左移删除s.len-=t.len ;n+; 被删除次数增1 /forreturn n;Delete SubString解：void maxcomstr( SString *s, SString *t) int index=0

26、,len1=0, i,j,k,len2;(2)编写一个函数，求串 s和串t的一个最长公共子串。void maxcomstr( SString *s, SString *t)i=0;/作为扫描s的指针while ( i <s.len) j = 0;/作为扫描t的指针while ( j < t.len )if (s.datai = = t.dataj ) / 序号为 i,长度为 len2 的子串 len2 =1;/开始计数for ( k=1; s.datai+k=t.dataj+k && s.datai+k!=NULL; k+ )len2+;if ( len2>l

27、en1) / 将较大长度者给 index 和 len1index=i;len1=len2;j + = len2;/ifelse j+;/whilecout<”最长公共子串：”for ( i=0; i<len1; i+;)cout<<s.dataindex+1;/ #1.已知下列字符串a = 'THIS', f = 'A SAMPLE', c = 'GOOD', d ='NE', b ='',s = StrConcat(a,StrConcat(StrSub(f,2,7),StrConcat(b

28、, 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'。试利用下列运算，将s转化 为to联接：StrConcat ( &S,T

29、)求子串：(char *) StrSub( S, i, len )置换：StrRep ( &S, T, R )上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。串结构定义如下：struct SStringchar *data ；/ 串首址int len; / 串长int StrSize ; /存放数组的最大长度.；求：串S所含不同字符的总数和每种字符的个数，不区分英文字母的大小写。第5章数组与压缩矩阵1.假设有二维数组 A6®每个兀素用相邻的6个字节存储，存储器按字节编址。已知 A的起始存储位置(基地址)为1000,计算：数组A的体积(即存储量)；(2)数组

30、A的最舟-个元素 a57的第一个字节的地址；(3)按行存储时，ai4的第一个字节的地址；(4)按列存储时，元素 347的第一个字节的地址。解：(1) 6X8X 6 = 288Byte(2) 1000+288-6=1282;(3) 1000+(1 X 8+4) X 6=1072(4) 1000+(7X6+4)X6=12762.假设按低下标优先存储整数数组A9X3冯4时，A个兀素的字节地址是100,每个整数占四个字节。1 可下列元素的存储地址是什么？ 30000(2) 38247解：(1) 100(2) 100+8 X 3 X 5 X 8+2 >5 X8+4 X8+7=45003. 一个稀疏矩阵如图所示L-1030000020500(1)；A = '0 00000(2)给出带行指针向量的链式存储示意图；9 000014与(3)十字链表存储示意图。M.data口i jeA01234013112013A135112T235309A351事309451AM.mu M.nu M.tu(1)465(2)A.cheadA.rhead卜Amu 4 101 1 3,1八_LA.nu 61 1 35112A.tu 5八一 八|八八-A-r.3 I0 | 931 5 . 1人1 -AA013112135309351013A112235309451A1 1 3|5AA4.算法设计：一个按行