严蔚敏版数据结构课后习题答案-.docx

《严蔚敏版数据结构课后习题答案-.docx》由会员分享，可在线阅读，更多相关《严蔚敏版数据结构课后习题答案-.docx（178页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章绪论简述下列术语：数据，数据元素、数据对象、数据结构、存储结 构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入 到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集 合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总 称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操 作。是对一般数据类型的扩展。1.1 试描述数据结构和抽象数据

2、类型的概念与程序设计语言中数据 类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据 类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提 供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据1.12设有以下三个函数:f(n) = 21 / + / + 1Ogg , g() = 15/ + 500 / , h(n) = 500n35 + log 请判断以下断言正确与否:(1)仪11)是0(11) 11(11)是0任(11) 8(。)是001(!1)(4) h(n0(n/(5) h(n)是 O(nlogn)解：对错错对错1.13试设定若干n值，比较两函数/和5

3、060g2的增长趋势，并确 定n在什么范围内，函数/的值大于50bg2的值。解:小的增长趋势快。但在n较小的时候，50Mog2几的值较大。当 n438 时,n2 50wlog2 n14判断下列各对函数/和g()，当 -00时，哪个函数增长更快?(1) /() = IO*+M!+10 ), g(/i) = 24+ + 7(2) /(rt) = (ln(!)+ 5)2, g() = 13n2 5(3) f(ri) = n21 + J/ +1 , g() = (ln(!)2 + n(4) /() = 2屈 +(2 丫，g()=)+5.解：g(n)快 g(n)快 f(n)快(4) f(n)快1. 15

4、试用数学归纳法证明:(1) Z/ = ( +1)(2 +1)/6 (n 0) i=ch0=c2;chl=，0,;x2=atoi(ch);switch(op) case +:x=xl+x2;break;case -:x=xl-x2;break;case * :x=xl*x2;break;case / :x=xl/x2;break;default:break;itoa(x, ch, 10);return chO;3. 23如题3. 21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。解：#include ttinclude #include

5、ttinclude d:VC99DSConstant. htypedef char ARRAY30;typedef ARRAY ElemType;typedef struct NodeTypeElemType data;NodeType *next;NodeType, *LinkType;typedef structLinkType top;int size;Stack;void InitStack(Stack &s);Status Push (Stack &s, ElemType e);Status Pop (Stack ElemType e);Status IsOperator(char

6、c);Status StackEmpty(Stack s);Status InvToFroPoland(char a);int main ()(char a30;couta;if(InvToFroPoland(a) coutaendl;else cout=，0* & ainext=s. top;s.top=p;strcpy (p-data, e);s.size+;return OK;Status Pop (Stack ElemType e)(LinkType p;if (s. top) strcpy (e,s. top-data);p=s. top;s.top=p-next;delete p;

7、s. size;return OK;Status StackEmpty(Stack s)if (s. size=O) return TRUE;else return FALSE;Status IsOperator(char c)while (*p)if (*p=c)return TRUE;p+；return FALSE;3. 24试编写如下定义的递归函数的递归算法，并根据算法画出求 g(5, 2)时栈的变化过程。g(m,n =0 m = 0.nQg(m l,2n)+n m 0,/? 0解:int g (int m, int n);int main ()(int m, n;cout请输入m和n的

8、值：；cinmn;if (n=0) coutg (m, n) endl;else cout0)return(g(m-l, 2*n)+n);else return 0;假设主函数的返回地址为0,递归函数3条语句的地址分别为1、2、300 643 1 323 2 163 3 83 4 40 5 23. 25试写出求递归函数F(n)的递归算法，并消除递归:n+n=0n0解：ttinclude ttdefine N 20int main()int i;int aN;int n;coutn;for (i=0;in+l;i+) if (il) ai=l;else ai=i*ai/2;coutanendl;

9、return 0;3. 26求解平方根VI的迭代函数定义如下:pp2 - A e V pj J其中，P是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。解：ftinclude double Sqrt (double A,double p,double e);int main()(double A, p, e;coutApe;coutSqrt(A, p, e)-e & (p*p-A)1)i=(4) - 1)=7?(1)i=1. 16试写一算法，自大至小依次输出顺序读入的三个整数X, Y和Z 的值解:int max3 (int x, int y, int z)if (xy)if

10、(xz) return x;else return z;elseif (yz) return y;else return z;1.17已知k阶斐波那契序列的定义为，fk-2 。9 fk- 1 ；力=/_1+/一2 +/-%， =左次 + 1,试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以 值调用的形式在函数参数表中出现。解：k0为阶数，n为数列的第n项3. 27已知Ackerman函数的定义如下：n + m = 0ak小n, ) = aki小n -1,1)z w 0, = 0akrrm -1, akirm, n-1) 相 w 0, w 0(1)写出递归算法；(2)写出非递归算法；(3

11、)根据非递归算法，画出求akm(2,1)时栈的变化过程。解：unsigned int akm(unsigned int m, unsigned int n)(unsigned int g;if (m-0)return n+1;elseif (n=0) return akm(m-l, 1);else g=akm (m, n-1);return akm (m-1, g);非递归算法：int akml(int m, int n)Stack s;InitStack(s);ElemType e,el,d;e. mval=m;e.nval=n;Push (s, e);do (while (e. mval)

12、 while(e. nval) e. nval一一;Push(s, e);e. mval一一;e.nval=l;)if(StackLength(s) 1) el. nval=e. nval;Pop(s, e);e. mval一一;e. nval=el. nval+1;e. mval !=0);while (StackLength (s)!=10, akm(2, 1)021l,akm(2,0)6202, akm(l, 1)411akm(l,0)6103, akm(0, 1)401g=akm(2, 0)akm=akni (m-1, 1) =akm(l, 1)g=akm (m, n-1) =akm

13、(1, 0)akm=akm (m-1, l)=akm(0, 1)akm=n+l=2 退栈0, akm(2, 1)021l,akm(2,0)6202, akm(l, 1)411akm(l,0)6100, akm(2, 1)021l,akm(2,0)6202, akm(l, 1)411g=akm(2, 0)akm=akm (m-1, 1) =akm(l, 1)g=akm(m, n-l)=akm(l, 0)akm=akm(m-l, l)=akm(0, 1)=2 退栈g=akm(2, 0)akm=akm (m-1, 1) =akm(l, 1)g=akm(m, n-l) =akm(1, 0) =2;ak

14、m=akm (m-1, g) =akm(0, 2);3, akm(0, 2)7 0 2akm=n+l=3 退栈0, akm(2, 1)0 2 1g=akm(2, 0)l,akm(2,0)6 2 0akm=akm (m-1, 1) =akm(l, 1)2, akm(l, 1)g=akm(m, n-1) =akm(1, 0)=2;akm=akm (m-1, g) =akm(O, 2)=3;退栈0, akm(2, 1)g=akm(2, 0)1, akm(2, 0)akm=akm(m-1, l)=akm(l, 1) =3 退栈0, akm(2, 1)g=akm(2, 0)=3; akm=akm(1,

15、3)1, akm (1, 3)g=akm(l, 2) ; akm(m-1, g)2, akm (1, 2)g=akm(l, 1) ; akm(m-l, g)3, akm(l, 1)g=akm(l, 0) ; akm(m-1, g)4, akm (1, 0)akm=akni(0, 1)5, akm(0, 1)akm(0, 1)=2 退栈0, akm (2, 1)g=akm(2, 0)=3; akm=akm(1, 3)1, akm(l, 3)g=akm(l, 2) ; akm(m-1, g)2, akm (1, 2)g=akm(l, 1) ; akm(m-l, g)3, akm(l, 1)g=ak

16、m(l, 0) ; akm(m-1, g)4, akm (1, 0)akm=akm(0, 1)=2 退栈0, akm (2, 1)1, akm (1, 3)2, akm(l, 2)g=akm(1, 1); akm(m-1, g)g=akm(2, 0)=3; akm=akm (1, 3) g=akm(l, 2) ; akm(m-1, g)3, akm(l, 1)g=akm (1, 0)=2; akm (m-1, g) =akm(0, 2)4, akm(O, 2)akm=n+l=3 退栈0, akm(2, 1)0 2 1g=akm(2, 0)=3; akm=akm (1, 3)l,akm(l,3)

17、613akm(l,2)6122, akm(l, 1)611退栈g=akm(l, 2) ; akm(m-1, g)g=akm(l, 1) ; akm(m-1, g)g=akm(l, 0)=2; akm(m-1, g) =akm(0, 2)=30, akm (2, 1)021l,akm(l,3)6132, akm(l,2)612g=akm(2, 0) =3; akm=akm (1, 3)g=akm(l, 2) ; akm(m-1, g)g=akm(l, 1)=3; akm(m-1, g) =akm(0, 3)3, akm(0, 3)7 0 3akm=n+l=4 退栈0, akm (2, 1)021

18、l,akm(l,3)6132, akm(l,2)612退栈g=akm(2, 0)=3; akm=akm(1, 3)g=akm(l, 2) ; akm(m-1, g)g=akm(l, 1)=3; akm(m-1, g) =akm(0, 3)=40, akm (2, 1)0 2 1l,akm(l,3)6 1 3g=akm(2, 0)=3; akm=akm (1, 3)g=akm(l, 2)=4; akm (m-1, g) =akm(0, 4)2, akm(0, 4)akm=n+l=5 退栈0, akm(2, 1)1, akm (1, 3)退栈0, akm (2, 1)0 2 1g=akm(2, 0

19、)=3; akm=akm (1, 3)g=akm(l, 2)=4; akm(m-1, g) =akm(0, 4) =5 g=akm (2, 0) =3; akm=akm (1, 3)=5 退栈akm (2, 1) =5;3. 28假设以带头结点的循环链表表示队列，并且只设一个指针指向 队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队 列何处队列的算法。解:typedef int ElemType;typedef struct NodeTypeElemType data;NodeType *next;QNode, *QPtr;typedef structQPtr rear;int s

20、ize;Queue;Status InitQueue(Queue& q)q.rear=NULL;q.size=O;return OK;Status EnQueue (Queue& q, ElemType e)QPtr p;p=new QNode;if(!p) return FALSE;p-data=e;if (!q. rear) q. rear=p;p-next=q. rear;)else p-next=q. rear-next;q.rear-next=p;q.rear=p;q. size+;return OK;Status DeQueue (Queue& q,ElemType& e)QPtr

21、 p;if (q.size=O)return FALSE;if (q. size=l) p=q. rear;e=p-data;q.rear=NULL;delete p;else(p=q.rear-next;e=p-data;q.rear-next=p一next;delete p;q. size-；return OK; _3.29如果希望循环队列中的元素都能得到利肋则需设置一个标志 域tag,并以tag的值为0和1来区分，尾指针和头指针值相同时的 队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队 列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的 使用范围（如当循环队列容量

22、较小而队列中每个元素占的空间较多 时，哪一种方法较好）。解：#define MaxQSize 4typedef int ElemType;typedef struct ElemType *base;int front;int rear;Status tag; Queue;Status InitQueue(Queue& q)(q. base=new ElemTypeMaxQSize;if(!q. base) return FALSE;q. front=0;q. rear=0;q. tag=0;return OK;Status EnQueue(Queue& q, ElemType e)if (q.

23、 frontq. rear&q. tag) return FALSE; else q. base q. rear二e;q. rear=(q. rear+l)%MaxQSize;if (q. rear-q. front) q. tag= 1 ；)return OK;Status DeQueue(Queue& q, ElemType& e)if (q. front=q. rear&!q. tag)return FALSE;else e=q. basetq. front;q. front=(q. front+1)%MaxQSize;q. tag=0;return OK;设标志节省存储空间，但运行时间

24、较长。不设标志则正好相反。3. 30假设将循环队列定义为：以域变量ear和length分别指示循环队列中队尾int Fibonacci(int k,int n)if (kl) exit (OVERFLOW);int *p, x;p=new intk+1;if (!p) exit (OVERFLOW);int i, j;for (i=0;ik+l;i+) if(ik-l) pi=0;else pi=l;for (i=k+l;in+l;i+) x=p0;for(j=0; jk; j+) pj=pj+l;pk=2*pk-l-x;return pk;1. 18假设有A, B, C, D, E五个高等院

25、校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为项目名 称性别校名成绩得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分, 条件，并写出相应的入队列和出队列的算法(在出队列的算法中要返 回队头元素)。解：#define MaxQSize 4typedef int ElemType;typedef structElemType *base;int rear;int length;Queue;Status InitQueue(Queue& q)(q. base=new ElemTypeMaxQSize;if(!q. base) return FALSE

26、;q. rear=O;q. length=O;return OK;Status EnQueue(Queue& q, ElemType e)if(q. rear+l)%MaxQSize=(q. rear+MaxQSize-q. length)%MaxQS ize)return FALSE;else q. baseq. rear=e;q. rear=(q. rear+1)%MaxQSize;q. length+;return OK;Status DeQueue(Queue& q, ElemType& e)(if (q. rear+MaxQSize-q. length)%MaxQSize=q. re

27、ar) return FALSE;else e=q. base(q. rear+MaxQSize-q. length)%MaxQSize; q.length-;return OK;3.31假设称正读和反读都相同的字符序列为“回文”，例如，abba，和，abcba，是回文，abcde，和，ababab，则不是回文。试写一个算法判别读入的一个以十为结束符的字符序列是否是“回文”。解:Status SymmetryString(char* p)Queue q;if(UnitQueue(q) return 0;Stack s;InitStack(s);ElemType el,e2;while(*p)

28、Push(s, *p)；EnQueue (q, *p)； p+；while (IStackEmpty(s)Pop(s, el);DeQueue (q, e2);if (el!=e2) return FALSE;return OK;3. 32试利用循环队列编写求k阶菲波那契序列中前n+1项的算法，在循环队要求满足：小皿而加3,其中3为某个约定的常数。（注意:本题所用循环队列的容量仅为k，则在算法执行结束时，列中的元素应是所求k阶菲波那契序列中的最后k项）解：int Fibonacci(int k, int n)(if (kl) exit (OVERFLOW);Queue q;InitQueue(

29、q, k);ElemType x, e;int i=0;while(i=n) if(i=k) /队列求和x=sum(q);DeQueue (q,e);EnQueue(q,x);i+；)return q. base(q. rear+q. MaxSize-l)%q. MaxSize;3. 33在顺序存储结构上实现输出受限的双端循环队列的入列和出列 (只允许队头出列)算法。设每个元素表示一个待处理的作业，元素 值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个 新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插 入在队头，否则插入在队尾。解：/ Filename:Queue, h

30、typedef structElemType *base;int front;int rear;Status tag;int MaxSize;DQueue;Status InitDQueue (DQueue& q, int size)(q. MaxSize=size;q. base=new ElemTypeq. MaxSize;if (!q. base) return FALSE;q.front=0;q.rear=O;q. tag=O;return OK;Status EnDQueue (DQueue& q, ElemType e)(if (q. front=q. rear&q. tag) r

31、eturn FALSE;if (q. front=q. rear&!q. tag) / 空队列q. baseq. rear=e;q. rear=(q. rear+l)%q. MaxSize;if (q. rear=q. front) q. tag=l;)else /非空非满if (e (q. base q. front+q. base (q. rear+q. MaxSize-1) %q. MaxS ize)/2) /从队头入队q. front=(q. front+q. MaxSize-l)%q. MaxSize;q. base q. front =e;if (q. rear=q. front)

32、 q. tag=l;else /从队尾入队q. base q. rear=e;q. rear= (q. rear+l)%q. MaxSize;if (q. rear=q. front) q. tag=l;return OK;)Status DeDQueue (DQueue& q, ElemType& e)(if (q.front=q. rear&!q. tag)return FALSE;else /非空队列e=q. base q. front;q. front= (q. front+l)%q. MaxSize;q. tag=0;)return OK;/ Filename:XT333. cpp

33、主程序文件ttinclude ttinclude typedef int ElemType;ttinclude D:VC99Queue. hint main()int tl, t2, t3, t4;ElemType e;cout请输入作业al、a2、a3、a4的执行时间：;cintlt2t3t4;DQueue dq;InitDQueue (dq, 5);EnDQueue(dq, tl);EnDQueue(dq, t2);EnDQueue(dq, t3);EnDQueue(dq, t4);while (dq. front!=dq. rear| |dq. tag)DeDQueue (dq, e);

34、coutech;int i=0;while(chi) if (chi PJ) coutchi;if (chi=，) EnDQueue (dq, chi, 0) ;/ 从队头入队if (chi=，H) EnDQueue(dq, chi, 1) ;/ 从队尾入队i+；while(dq. front!=dq. rear| |dq. tag)DeDQueue (dq, e);coute;)cout串比较(StrCompare) 求串长 (StrLength) 串连接(Concat)、求子串(SubString)这五种基本操作 构成串类型的最小操作子集。4.6 解：si二SubString(s, 3,

35、1)s2=SubString(s, 6, 1)Replace(s, si, s2)Concat (s3, s, si)Concat (t, SubString (s3, 1, 5), SubString (s3, 7, 2)算法设计题：/ Filename: String.httinclude ttinclude #define MaxSize 128class Stringchar *ch;int curlen;public:String (const String& ob);String (const char* init);String ();String ();void StrAssi

36、gn(String t);int StrCompare(String t);int StrLength();void Concat(String t);String SubString (int start, int len);void show(););String:String(const String& ob)(ch=new charMaxSize+1;if(!ch) exit (1);curlen=ob. curlen;strcpy (ch, ob. ch);String:String(const char* init)(ch=new charMaxSize+1;if (!ch) ex

37、it ;curlen=strlen (init);strcpy(ch, init);String:String()ch=new charMaxSize+1;if(!ch) exit (1);curlen=O;chO” 0,;String: /String()delete ch;curlen=O;)void String:StrAssign(String t)strcpy (ch, t. ch);curlen=t. curlen;int String:StrCompare(String t)return strcmp (ch, t. ch);int String:StrLength()return curlen;void String:Concat(String t)(strcat (ch, t. ch);curlen=curlen+t. curlen;String String:SubString(int start, int len)(String temp;int i, j;if(start=0 & start+len0) temp. curlen=len;for(i=0,j=start;ilen;i+, j+)temp. chi