数据结构实用教程课后习题答案万健C++.doc

第2章作业参考答案1. B2. A，D3. 1，n/2，(n-1)/2，n，0，04. templete void SqList : reverse()ElemType e;for (int i = 0; i len / 2; i+) e = elemi; elemi = elemlen i -1; elemlen i 1 = e;templete void LinkList : reverse()if (!head-next) return;LinkNode *q = head - next, *p = q - next;q - next = NULL;tail = q;while (p) q = p; p = p next; q next = head - next; head - next = q;8.void add(LinkList &pa, LinkList &pb)int pa_len, pb_len, i, j;pa_len = pa.Length();pb_len = pb.Length();i = j = 1;Monomial pa_e, pb_e;pa.GetElem(pa_e, 1);pb.GetElem(pb_e, 1);while (i = pa_len & j = pb_len) if (pa_e.exp pb_e.exp) i+; if (i pb_e.exp) pa.Insert(pb_e, i); i+; pa_len+; j+; if (j = pb_len) pb.GetElem(pb_e, j); else if (pa_e.coef += pb_e.coef) pa.SetElem(pa_e, i); i+; else pa.Delete(pa_e, i); pa_len-; j+; if (i = pa_len) pa.GetElem(pa_e, i); if (j = pb_len) pb.GetElem(pb_e, j); while (j = pb_len) pb.GetElem(pb_e, j+); pa.Append(pb_e); 第3章作业参考答案1. 1,4,3,5,2)能，IOIIIOOIOO；(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3先出栈才能2出栈。*若借助栈由输入序列1,2, , n得到输出序列为p1, p2, , pn，则在输出序列中不可能出现这样的情形：存在着ijk使pjpkpi。2. 借助栈T，删除栈S中元素值为k的元素。4./定义双向栈类template /声明一个类模板class DSqStackpublic: /双向栈类的各成员函数DSqStack(int m = 100); DSqStack(); bool Empty(int i) const; ElemType & Top(int i) const; void Push(const ElemType &e,int i); void Pop(int i);private: /双向栈类的数据成员 ElemType *base; /基地址指针 int top2; /栈顶指针int size; /向量空间大小;/构造函数，分配m个结点的顺序空间，构造一个空的双向栈。template DSqStack :DSqStack(int m)top0 = -1;top1 = m;base = new ElemTypem;size = m;/DSqStack/析构函数，将栈结构销毁。template DSqStack :DSqStack()if (base != NULL) delete base;/SqStack/判栈是否为空，若为空，则返回true，否则返回false。template bool DSqStack :Empty(int i) const/i的取值为0或1if (i = 0)return top0 = -1;elsereturn top1 = size;/Empty/取栈顶元素的值。先决条件是栈不空。template ElemType & DSqStack :Top(int i) const/i的取值为0或1return basetopi;/Top/入栈，若栈满，则先扩展空间。插入e到栈顶。template void DSqStack :Push(const ElemType &e, int i)/i的取值为0或1 if (top0 = top1 - 1)/若栈满，则扩展空间。 ElemType *newbase; newbase = new ElemTypesize + 10; for(int j = 0; j = top1; k-) newbasek + 10 = basek; delete base; base = newbase; size += 10; top1 += 10; if (i = 0) base+top0 = e;elsebase-top1 = e;/Push/出栈，弹出栈顶元素。先决条件是栈非空。template void DSqStack :Pop(int i)/i的取值为0或1if (i = 0)top0-;elsetop1+;/Pop5. (1). A, C, D(2). 从左到右读序列，任何时候累计I的个数都应大于等于O的个数。(3). bool islegal(char *a) int s = 0, n = strlen(s); for (int i = 0; i n; i+) if (ai = “I”) s+; else s-; if (s 0) return false; return true;7. 借助队列q0和q1，将队列Q中的元素重新排列：奇数值元素在前，偶数值元素在后。8.类型定义：typedef struct QNode QElemType data;struct QNode *next; QNode, * QLink;template /声明一个类模板class CycLinkQueuepublic: /循环链表队列的各成员函数CycLinkQueue (); /CycLinkQueue (); /void Clear();/bool Empty() const; /int Length() const; /ElemType & GetHead() const; /ElemType & GetLast() const; void Append(const ElemType &e); void Remove();private: QNode *m_rear; /队尾指针;(1) /构造函数，构造一个空的循环链队列。template CycLinkQueue : CycLinkQueue()m_rear = new QNode ;m_rear-next = m_rear;(2)/入队void CycLinkQueue :Append(const ElemType &e)QNode *p;p = new QNode ; p-data = e; p-next = m_rear-next; m_rear-next = p; m_rear = p;(3)/出队。先决条件是队列不空。template void CycLinkQueue :Remove()QNode *p = m_rear-next-next; m_rear-next-next = p-next; if (p = m_rear)m_rear = m_rear-next; /若出队后队列为空，需修改m_rear。 delete p;9.template class SqQueuepublic: /循环队列的各成员函数SqQueue(int m = 100); /SqQueue(); /void Clear();/bool Empty() const; /int Length() const; /ElemType & GetHead() const; /ElemType & GetLast() const; void Append(const ElemType &e); void Remove();private: /循环队列类的数据成员 ElemType *m_base; /基地址指针 int m_front; /队头指针 int m_length; /队列长度 int m_size; /向量空间大小;/构造函数，分配m个结点的顺序空间，构造一个空的循环队列。template SqQueue :SqQueue(int m)m_front = m_length = 0;m_base = new ElemTypem;m_size = m;/SqQueue/入队，插入e到队尾。template void SqQueue :Append(const ElemType &e)int j, k;if (m_length = m_size) /队满，则扩展空间。ElemType *newbase; newbase = new ElemTypem_size + 10; for(j = m_front, k = 0; k m_length; j = (j + 1) % m_size, k+) newbasek = m_basej; delete m_base; m_base = newbase;m_front = 0;m_size += 10; m_base(m_front + m_length) % m_size = e; m_length+;/Append/出队。先决条件是队列不空。template void SqQueue :Remove()m_front = (m_front + 1) % m_size; m_length-;/Remove10.Length(s)的结果为14sub1的值为”I am a “Index(s,”a”,4)的结果为6s的值为”I am a worker”sub3的值为”goodworker”sub3的值为”good worker”11.(1) 288(2) 1282(3) 1180(4) 123412.(1) k=2i+j-3(2) i=(k+1)/3+1，j=i+(k+1)%3-1 (i用前式代入即可)15.(1) (a, b)(2) ( )(3) (b)(4) b(5) (d)16.（略）4.高度最小的树：高度是2，它有n-1个叶结点，1个分支结点。高度最大的树：高度是n，它有1个叶结点，n-1个分支结点。5.n0=1+n2+2n3+(m-1)nm6.树2种：二叉树5种：7.(1) 空树，或二叉树中所有结点的lchild均为空的二叉树(2) 空树，或二叉树中所有结点的rchild均为空的二叉树(3) 空树，或仅有一个结点的二叉树9.(1) 第i层有ki-1个结点(2) (i+k-2)/k (i1)(3) k(i-1)+m+1(4) (i-1)%k0, i+1(5) h=logk(n(k-1)+1)10.11.12.13. 树： 二叉树：14. 森林： 二叉树：16. 赫夫曼树：赫夫曼编码：C1(5): 0110，C2(25):10，C3(3):0010，C4(6):0111，C5(10):000，C6(11):010，C7(36):11，C8(4):0011WPL=(3+4+5+6)*4+(10+11)*3+(25+36)*2=25717.(1)/求二叉树中叶结点的个数 template int BinaryTree:_CountLeaves(BTNode* T) if (!T) return 0;if (!T-lchild)&(!T-rchild) return 1; return _CountLeaves(T-lchild)+ _CountLeaves(T-rchild);(2)/交换二叉树中每个结点的左右孩子template void BinaryTree:_Exchange(BTNode* T)if (T) BTNode *p;p=T-lchild;T-lchild=T-rchild;T-rchild=p; _E xchange(T-lchild); _E xchange(T-rchild); 2. (1). 邻接矩阵 邻接表(2). DFS: V1,V2,V4,V5,V3,V6(3). BFS: V1,V2,V3,V4,V5,V6(4). 深度优先生成树 广度优先生成树3.(1).