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

第1章绪论简述下列术语：数据，数据元素、数据对象、数据结构、存储结 构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入 到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集 合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总 称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操 作。是对一般数据类型的扩展。1.1 试描述数据结构和抽象数据类型的概念与程序设计语言中数据 类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据 类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提 供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据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值，比较两函数/和5060g2的增长趋势，并确 定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试用数学归纳法证明:(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 <iostream. h>ttinclude <stdlib. h>#include <string. h>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 c);Status StackEmpty(Stack s);Status InvToFroPoland(char a);int main ()(char a30;cout<请输入逆波兰算术表达式字符序列：；cin>>a;if(InvToFroPoland(a) cout<<a<<endl;else cout<输入逆波兰算术表达式字符序列错误! ;return 0;Status InvToFroPoland(char a)Stack s;InitStack(s);int i=0;ElemType ch;ElemType cl;ElemType c2;while(ai !='#')if(!IsOperator (ai) if (ai>=，0* && ai<=，91) ch0=ai; chl=，0，; Push (s, ch);)else return FALSE;)else (ch0=ai;chl=，0J ;if(!StackEmpty (s) Pop (s, c2);if(!StackEmpty(s) Pop(s, cl);strcat (ch, cl);strcat (ch,c2);Push (s, ch);else return FALSE;else return FALSE;i+；)if(IStackEmpty (s) Pop(s, cl);strcpy (a, cl);else return FALSE;if(!StackEmpty(s) return FALSE; return OK;void InitStack(Stack &s)(s. top=NULL;s. size=0;Status Push(Stack &s, ElemType e)LinkType p;p=new NodeType;if (!p) exit (OVERFLOW);p->next=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;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.n>Qg(m l,2n)+n m > 0,/? > 0解:int g (int m, int n);int main ()(int m, n;cout请输入m和n的值：；cin>>m>>n;if (n>=0) cout<<g (m, n) «endl;else cout<<，No Solution!;return 0;int g(int m, int n)if(m>0)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=0n>0解：ttinclude <iostream. h>ttdefine N 20int main()int i;int aN;int n;cout<请输入 n: ；cin>>n;for (i=0;i<n+l;i+) if (i<l) ai=l;else ai=i*ai/2;cout<<an<<endl;return 0;3. 26求解平方根VI的迭代函数定义如下:pp2 - A <e圾片(4p,e) = (a) )2 人、sqrt A, p + ,e p - A>e V pj J其中，P是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。解：ftinclude <iostream. h>double Sqrt (double A,double p,double e);int main()(double A, p, e;cout<请输入 A p e:；cin>>A>>p>>e;cout<<Sqrt(A, p, e)<<endl;return 0;double Sqrt (double A, double p,double e)(if(p*p-A)>-e && (p*p-A)<e)return p;elsereturn Sqrt (A, (p+A/p) /2, e);(2) Z X = (xs - l)/(x -1) (x w 1, 2 0) z=0(3)E2 =2 1(Z2>1)i=(4) £- 1)=7?(«>1)i=1. 16试写一算法，自大至小依次输出顺序读入的三个整数X, Y和Z 的值解:int max3 (int x, int y, int z)if (x>y)if(x>z) return x;else return z;elseif (y>z) 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)根据非递归算法，画出求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) 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 (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;akm=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, 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=akm(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)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)021l,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)=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 size;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 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来区分，尾指针和头指针值相同时的 队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队 列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的 使用范围（如当循环队列容量较小而队列中每个元素占的空间较多 时，哪一种方法较好）。解：#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. 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;设标志节省存储空间，但运行时间较长。不设标志则正好相反。3. 30假设将循环队列定义为：以域变量ear和length分别指示循环队列中队尾int Fibonacci(int k,int n)if (k<l) exit (OVERFLOW);int *p, x;p=new intk+1;if (!p) exit (OVERFLOW);int i, j;for (i=0;i<k+l;i+) if(i<k-l) pi=0;else pi=l;for (i=k+l;i<n+l;i+) x=p0;for(j=0; j<k; j+) pj=pj+l;pk=2*pk-l-x;return pk;1. 18假设有A, B, C, D, E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为项目名 称性别校名成绩得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分, 条件，并写出相应的入队列和出队列的算法(在出队列的算法中要返 回队头元素)。解：#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;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. rear) 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) 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 (k<l) exit (OVERFLOW);Queue q;InitQueue(q, k);ElemType x, e;int i=0;while(i<=n) if(i<k-l) if(!EnQueue(q, 0) exit(OVERFLOW);if(i=k-l) if(!EnQueue(q,1) exit(OVERFLOW);)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, htypedef 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) return 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) 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 主程序文件ttinclude <iostream. h>ttinclude <stdlib. h>typedef int ElemType;ttinclude D:VC99Queue. hint main()int tl, t2, t3, t4;ElemType e;cout<<请输入作业al、a2、a3、a4的执行时间：;cin»tl»t2»t3»t4;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);cout<<e<<endl;)return 0;3. 34假设在如教科书3. 4.1节中图3. 9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧(分别以P,H和S表示)等待调度， 要求这三种车厢在输出端铁道上的排列次序为:硬座在前,软卧在中, 硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写 算法输出调度的操作序列：分别以字符缈和D表示对双端队列的头 端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行 入队列的操作。解：int main()(ElemType e;DQueue dq;InitDQueue(dq, 20);char ch 20;cout«请输入待调度的车厢字符序列(仅限PHS):;cin>>ch;int i=0;while(chi) if (chi> PJ) cout«chi;if (chi=，) EnDQueue (dq, chi, 0) ;/ 从队头入队if (chi=，H') EnDQueue(dq, chi, 1) ;/ 从队尾入队i+；while(dq. front!=dq. rear| |dq. tag)DeDQueue (dq, e);cout<<e;)cout<<endl;return 0;并输出。解：typedef enumA, B, C, D, E SchoolName;typedef enumFemale, Male SexType;typedef structchar event 3; 项目SexType sex;SchoolName school;int score; Component;typedef struct int MaleSum; 男团总分int FemaleSum; 女团总分int TotalSum; 团体总分 Sum;Sum SumScore(SchoolName sn, Component a, int n) Sum temp;temp. MaleSum=0;temp. FemaleSum=O;temp. TotalSum=0;第4章串4. 1解：空格串是指一个或多个空格字符(ASCH码为20H)组成的串, 而空串中没有任何字符。4. 2解：串赋 值(StrAssign) >串比较(StrCompare) >求串长 (StrLength) >串连接(Concat)、求子串(SubString)这五种基本操作 构成串类型的最小操作子集。4.6 解：si二SubString(s, 3, 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 <stdlib. h>ttinclude <string. h>#define MaxSize 128class Stringchar *ch;int curlen;public:String (const String& ob);String (const char* init);String ();"String ();void StrAssign(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) exit ;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+len<=curlen && len>0) temp. curlen=len;for(i=0,j=start;i<len;i+, j+)temp. chi