数据结构习题(有答案).doc

1、第1章 绪1.1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1) A= ( D，R )，其中，D = a1，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，6， R= ，(1) 集合(2) 线性表 (3) 树 (4) 图 1.2 设n为

2、正整数，求下列各程序段中的下划线语句的执行次数。(1) i=1; k=0while(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 k=1; k=n; k+) cij=cij+aik*bkj解：(1) n-1 (2) (3) 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;(3) 1.3 指出下列个算法的功能，并求其时间复杂度。(1) int sum1(int n

3、)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) , T(n)=O(n)(2) , T(n)=O(n2)1.4 算法设计有3枚硬币，其中有1枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1. 设 a, b, c为3个整

4、数，求其中位于中间值的整数。第2章 线性表1. 设计算法：在顺序表中删除值为e的元素，删除成功，返回1；否则，返回0。int Sqlist:DeleteElem( T e ) for (i=1; i=length; i+) / 按值顺序查找 * i可从0开始 if (elemi-1= =e) / 找到，进行删除操作 for ( j=i; jlength; j+) / ai至an依次前移 Elemj-1 = elemj; length - - ; / 表长减一 return 1 ; /删除成功，返回 1 return 0 ; / 未找到，删除不成功，返回 02. 分析顺序表中元素定位算法 int

5、 SqList:Locate ( T e ) 的时间复杂度。解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n定位成功第i个元素，需比较i次3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。 (1) 定位到第i个结点ai；p=head; j=0;while ( p & jnext; j+;(2) 定位到第i个结点的前驱ai-1；p=head; j=0;while ( p & jnext; j+;(3) 定位到尾结点；p=head; while ( p -next ) p=p-next; (4) 定位到尾结点的前驱。p=head; while ( p-next-nex

6、t ) p=p-next;4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。首元结点：指链表中的第一个元素结点。5. 对于无头结点单链表，给出删除第i个结点的算法描述。 template T LinkList:Delete(int i)template T LinkList:Delete(int i) / 在单链表上删除第i个数据元素 if ( head=NULL) throw “表空!”; / 空表，不能删 else if ( i=1)

7、/ 删除第1个元素 p=Head; x=p-data; / 保存被删元素值Head= p-next ; delete p ; else / 元素定位到第ai-1 p=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. 用教材定义的顺序表的基本操作实现下列操作： template

8、int DeleteElem(SqList L, T e)#include “SqList.h“template 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=p-nex

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

10、4623的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。解：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+) S.Push(Ai);(2) status algo_2(SqStack S, int e) SqStack T; int d;while (!S.tackEmpty()

11、 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”int NumTrans( int N, int B) /十进制整数N转换为B进制数stack S; / 建立一个栈while( N!=0) / N非零 i=N%B ; /

12、 从低到高，依次求得各位 N=N/B; S.push(i); / 各位入栈 while ( !S.StackEmpty() / 栈不空 i= S.pop(); If (i9) i=A+10-i; cout S.pop(); / 依次出栈，得到从高到低的输出结果/#4 借且栈，设计算法：假设一个算术表达式中包含“(”、“)”括号，对一个合法的数学表达式来说，括号“(”和“)”应是相互匹配的。若匹配，返回1；否则，返回0。解：以字符串存储表达式，也可以边输入边判断。 顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹

13、配；否则，括号不匹配，多左括号。int blank_match(char *exp) 用字符串存表达式 SqStack s; / 创建一个栈 char *p=exp; / 工作指针p指向表达式首 while ( *p!=) / 不是表达式结束符 switch(p) case (: /左括号，入栈 s.push(ch); break; case ) / 右括号 if (s.StackEmpty() return 0; / 栈空，不匹配，多右括号 else s.Pop(); break; / 左括号出栈 /switch p+; / 取表达式下一个字符 / while if (!s.StackEmp

14、ty() / 表达式结束，栈不空 return 0 ; /不匹配，多左括号 else return 1 ; / 匹配 /#5. 简述栈和队列的逻辑特点，各举一个应用实例。6. 写出下列中缀表达式的后缀表达式。(1)-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*+/+C+(3) AB&EF ! |7.计算后缀表达式：4 5 * 3 2 + - 的值。解：158.将下列递推过程改写为递归过程。void recursion( int n ) int i=n; while( i1) cout1) courx;i

15、f (x=0) sum=0;else test(sum); sum+=x; coutx;while (x) S.push(x); cinx; sum=0; coutsum;while ( x=S.pop() ) sum+=x; coutsum; /10. 简述以下算法的功能（栈和队列的元素类型均为 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); 解：利用栈，将队

16、列中的元素逆置12. 假设以数组sem存放循环队列的元素，同时设变量rear和front分别作为队首、队尾指针，且队首指针指向队首前一个位置，队尾指针指向队尾元素处，初始时，rear=fornt=-1。写出这样设计的循环队列入队、出队的算法。解：采用教材队空与队满判别方法。为了区分队空与队满条件，牺牲一个元素空间。即：rear=front， 为队空；rear=(front+1)%m，为队满。template void EnQueue( T Se, T e, int m ) /入队 if ( rear+1)%m=fornt ) /队满，不能插入throw “队满，不能插入!” else rear

17、 = (rear+1) % m; / 队尾指针后移 serear=e; / 元素入队 return ;/#template T DnQueue( T Se, int m ) / 出队 if ( rear=fornt ) /队空，不能出队!throw “队空，不能出队!” else front = (front+1)%m; / 指针后移，指向队首元素 e =sefront; / 取队首元素 return e ; /#上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.借助栈，实现单链表上的逆置运算。第4章 串1. 试问执行以下函数会产生怎样的输出结果?void demonst

18、rate( ) 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 ) );StrAssign(w, W);cout“t=” tendl;cout“v=” v;cout“u=” StrRep(u, v, w); / demonstrate解：t= THESE ARE BOOKSv= YXYw= XWXWXW2.设字符串S=aa

19、baabaabaac，P=aabaac1）给出S和P的next值和nextval值；2）若S作主串，P作模式串，试给出KMP算法的匹配过程。1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和0020032）利用KMP算法的匹配过程： 第一趟匹配：aabaabaabaac aabaac(i=6,j=6) 第二趟匹配：aabaabaabaac (aa)baac 第三趟匹配：aabaabaabaac (成功) (aa)baac3. 算法设计串结构定义如下：struct SString char *data；

20、/ 串首址 int len; / 串长 int StrSize； / 存放数组的最大长度. ;(1) 编写一个函数，计算一个子串在一个字符串中出现的次数，如果不出现，则为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) 编写算法，

21、从串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 = i; ks.len-t.len; k+ ) sk=sk+t.len; /左移删除s.len-=t.len ;n+; / 被删除次数增1/forreturn n;/Delete_SubString(2) 编写一个函数，求串s和串t 的一个最长公共子串。void maxcoms

22、tr( 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) / 将较大长度者给index和len1 index=i; len1=len2; j + = len2; /if else j+; /while cout”最长公共子串：” for ( i=0; ilen1; i+; ) couts.dataindex+1; / #

23、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 = IS,v = StrConcat(s,StrConcat(b,StrConcat(t,StrConcat(b,u),试问: s, t, v, StrLength(s), StrIndex(v,g), StrInde

24、x(u,g) 各是什么 ?已知：s=(XYZ)+* ，t=(X+Z)*Y。试利用下列运算，将 s 转化为 t。联接：StrConcat ( &S,T )求子串：(char *) StrSub( S, i, len ) 置换：StrRep ( &S, T, R )上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。串结构定义如下：struct SString char *data； / 串首址 int len; / 串长 int StrSize； / 存放数组的最大长度. ;求：串S所含不同字符的总数和每种字符的个数，不区分英文字母的大小写。第5章 数组与压缩矩阵1. 假设有二维

25、数组 A68，每个元素用相邻的 6 个字节存储，存储器按字节编址。已知 A 的起始存储位置(基地址)为 1000，计算：(1) 数组 A 的体积（即存储量）;(2) 数组 A 的最后一个元素 a57 的第一个字节的地址;(3) 按行存储时，元素 a14 的第一个字节的地址;(4) 按列存储时，元素 a47 的第一个字节的地址。 解：(1）686 = 288Byte(2）1000+288-6=1282；(3）1000+(18+4)6=1072(4）1000+(76+4)6=12762. 假设按低下标优先存储整数数组A9358时，第一个元素的字节地址是 100，每个整数占四个字节。问下列元素的存储地址是什么