《数据结构实用教程课后习题答案万健C++》由会员分享，可在线阅读，更多相关《数据结构实用教程课后习题答案万健C++（16页珍藏版）》请在金锄头文库上搜索。
1、第 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 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
2、 add(LinkList 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 pb_e.exp)pa.Insert(pb_e, i);i+;pa_len+;j+;if (j /声明一个类模板 class DSqStack public: /双向栈类的各成员函数 DSqStack(int m = 100); DSqStack(); bool Empty(int i) const;ElemType
3、void Push(const ElemType 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 !=
4、 NULL) delete base;/SqStack/判栈是否为空，若为空，则返回 true，否则返回 false。 template bool DSqStack :Empty(int i) const/i 的取值为 0 或 1 if (i = 0) return top0 = -1; else return top1 = size; /Empty/取栈顶元素的值。先决条件是栈不空。 template ElemType /Top/入栈，若栈满，则先扩展空间。插入 e 到栈顶。 template void DSqStack :Push(const ElemType newbase = new
5、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; else base-top1 = e; /Push/出栈，弹出栈顶元素。先决条件是栈非空。 template void DSqStack :Pop(int i)/i 的取值为 0 或 1 if (i = 0) top0-; else top1+; /Pop5. (1). A, C, D(2). 从左到右读序列，
6、任何时候累计 I 的个数都应大于等于 O 的个数。 (3). bool islegal(char *a) int s = 0, n = strlen(s);for (int i = 0; i /声明一个类模板 class CycLinkQueue public: /循环链表队列的各成员函数 CycLinkQueue (); /CycLinkQueue (); /void Clear(); /bool Empty() const;/int Length() const;/ElemType /ElemType void Append(const ElemType void Remove(); pr
7、ivate:QNode *m_rear; /队尾指针 ;(1) /构造函数，构造一个空的循环链队列。 template CycLinkQueue : CycLinkQueue() m_rear = new QNode ; m_rear-next = m_rear; (2)/入队 void CycLinkQueue :Append(const ElemType p = new QNode ;p-data = e;p-next = m_rear-next;m_rear-next = p;m_rear = p; (3)/出队。先决条件是队列不空。 template void CycLinkQueue
8、 :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 SqQueue public: /循环队列的各成员函数SqQueue(int m = 100); /SqQueue(); /void Clear(); /bool Empty() const;/int Length() const;/ElemType /ElemType void Append(c
9、onst ElemType 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 :Appe
10、nd(const ElemType if (m_length = m_size) /队满，则扩展空间。 ElemType *newbase;newbase = new ElemTypem_size + 10;for(j = m_front, k = 0; k void SqQueue :Remove() m_front = (m_front + 1) % m_size;m_length-; /Remove10.Length(s)的结果为 14 sub1 的值为”I am a “ Index(s,”a”,4)的结果为 6 s 的值为”I am a worker” sub3 的值为”goodwor
11、ker” 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) 空树，或二叉树中所有结点的 lc
12、hild 均为空的二叉树 (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.GHFBDAECJI11.JHIBEACKFGD12.FICBHADEGJ13.树： 二叉树：HCBFIGDKJEAJCBKEFDIHAG14.森林： 二叉树：JDHLKCBAGDFEJIHBGACEKDFL16.赫夫曼树：3 C34 C811 C65 C16 C425 C236
13、C710 C5赫夫曼编码：C1(5): 0110，C2(25):10，C3(3):0010，C4(6):0111，C5(10):000，C6(11): 010，C7(36):11，C8(4):0011 WPL=(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)return _CountLeaves(T-lchild)+ _CountLeaves(T-rchild); (2)/交换
14、二叉树中每个结点的左右孩子 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). 邻接矩阵 邻接表01234012340111011100010000110010110500011000110501234v3v1v2v4v500025v6133514534342(2). DFS: V1,V2,V4,V5,V3,V6(3). BFS: V1,V2,V3,V4,V5,V6(4). 深度优先生成树 广度优先生成树V2V1V3V4V5V6V6V1V2V4V5V33.(1). 012340123431316362325 5565565v3v1v4v5v6v231532(2).v3v1v4v5v6v23135201234v3v1v2v4v5032613135541331642555v60122253556464.(1). 顶点 v1 v2 v3 v4 v5 v6入度 0
