《数据结构与算法分析》(C++第二版)【美】Clifford-A.Shaffer著-课后习题答案-二(共28页).doc

《《数据结构与算法分析》(C++第二版)【美】Clifford-A.Shaffer著-课后习题答案-二(共28页).doc》由会员分享，可在线阅读，更多相关《《数据结构与算法分析》(C++第二版)【美】Clifford-A.Shaffer著-课后习题答案-二(共28页).doc（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构与算法分析（C+第二版）【美】Clifford A.Shaffer著 课后习题答案 二5Binary Trees5.1 Consider a non-full binary tree. By definition, this tree must have some internalnode X with only one non-empty child. If we modify the tree to removeX, replacing it with its child, the modified tree will have a higher frac

2、tion ofnon-empty nodes since one non-empty node and one empty node have beenremoved.5.2 Use as the base case the tree of one leaf node. The number of degree-2 nodesis 0, and the number of leaves is 1. Thus, the theorem holds.For the induction hypothesis, assume the theorem is true for any tree withn

3、 1 nodes.For the induction step, consider a tree T with n nodes. Remove from the treeany leaf node, and call the resulting tree T. By the induction hypothesis, Thas one more leaf node than it has nodes of degree 2.Now, restore the leaf node that was removed to form T. There are twopossible cases.(1)

4、 If this leaf node is the only child of its parent in T, then the number ofnodes of degree 2 has not changed, nor has the number of leaf nodes. Thus,the theorem holds.(2) If this leaf node is the child of a node in T with degree 2, then that nodehas degree 1 in T. Thus, by restoring the leaf node we

5、 are adding one newleaf node and one new node of degree 2. Thus, the theorem holds.By mathematical induction, the theorem is correct.32335.3 Base Case: For the tree of one leaf node, I = 0, E = 0, n = 0, so thetheorem holds.Induction Hypothesis: The theorem holds for the full binary tree containingn

6、 internal nodes.Induction Step: Take an arbitrary tree (call it T) of n internal nodes. Selectsome internal node x from T that has two leaves, and remove those twoleaves. Call the resulting tree T. Tree T is full and has n1 internal nodes,so by the Induction Hypothesis E = I + 2(n 1).Call the depth

7、of node x as d. Restore the two children of x, each at leveld+1. We have nowadded d to I since x is now once again an internal node.We have now added 2(d + 1) d = d + 2 to E since we added the two leafnodes, but lost the contribution of x to E. Thus, if before the addition we hadE = I + 2(n 1) (by t

8、he induction hypothesis), then after the addition wehave E + d = I + d + 2 + 2(n 1) or E = I + 2n which is correct. Thus,by the principle of mathematical induction, the theorem is correct.5.4 (a) template void inorder(BinNode* subroot) if (subroot = NULL) return; / Empty, do nothingpreorder(subroot-

9、left();visit(subroot); / Perform desired actionpreorder(subroot-right();(b) template void postorder(BinNode* subroot) if (subroot = NULL) return; / Empty, do nothingpreorder(subroot-left();preorder(subroot-right();visit(subroot); / Perform desired action5.5 The key is to search both subtrees, as nec

10、essary.template bool search(BinNode* subroot, Key K);if (subroot = NULL) return false;if (subroot-value() = K) return true;if (search(subroot-right() return true;return search(subroot-left();34 Chap. 5 Binary Trees5.6 The key is to use a queue to store subtrees to be processed.template void level(Bi

11、nNode* subroot) AQueueBinNode* Q;Q.enqueue(subroot);while(!Q.isEmpty() BinNode* temp;Q.dequeue(temp);if(temp != NULL) Print(temp);Q.enqueue(temp-left();Q.enqueue(temp-right();5.7 template int height(BinNode* subroot) if (subroot = NULL) return 0; / Empty subtreereturn 1 + max(height(subroot-left(),h

12、eight(subroot-right();5.8 template int count(BinNode* subroot) if (subroot = NULL) return 0; / Empty subtreeif (subroot-isLeaf() return 1; / A leafreturn 1 + count(subroot-left() +count(subroot-right();5.9 (a) Since every node stores 4 bytes of data and 12 bytes of pointers, theoverhead fraction is

13、12/16 = 75%.(b) Since every node stores 16 bytes of data and 8 bytes of pointers, theoverhead fraction is 8/24 33%.(c) Leaf nodes store 8 bytes of data and 4 bytes of pointers; internal nodesstore 8 bytes of data and 12 bytes of pointers. Since the nodes havedifferent sizes, the total space needed f

14、or internal nodes is not the sameas for leaf nodes. Students must be careful to do the calculation correctly,taking the weighting into account. The correct formula looks asfollows, given that there are x internal nodes and x leaf nodes.4x + 12x12x + 20x= 16/32 = 50%.(d) Leaf nodes store 4 bytes of d

15、ata; internal nodes store 4 bytes of pointers.The formula looks as follows, given that there are x internal nodes and35x leaf nodes:4x4x + 4x= 4/8 = 50%.5.10 If equal valued nodes were allowed to appear in either subtree, then during asearch for all nodes of a given value, whenever we encounter a no

16、de of thatvalue the search would be required to search in both directions.5.11 This tree is identical to the tree of Figure 5.20(a), except that a node withvalue 5 will be added as the right child of the node with value 2.5.12 This tree is identical to the tree of Figure 5.20(b), except that the val

17、ue 24replaces the value 7, and the leaf node that originally contained 24 is removedfrom the tree.5.13 template int smallcount(BinNode* root, Key K);if (root = NULL) return 0;if (KEComp.gt(root-value(), K)return smallcount(root-leftchild(), K);elsereturn smallcount(root-leftchild(), K) +smallcount(r

18、oot-rightchild(), K) + 1;5.14 template void printRange(BinNode* root, int low,int high) if (root = NULL) return;if (KEComp.lt(high, root-val() / all to leftprintRange(root-left(), low, high);else if (KEComp.gt(low, root-val() / all to rightprintRange(root-right(), low, high);else / Must process both

19、 childrenprintRange(root-left(), low, high);PRINT(root-value();printRange(root-right(), low, high);5.15 The minimum number of elements is contained in the heap with a single nodeat depth h 1, for a total of 2h1 nodes.The maximum number of elements is contained in the heap that has completelyfilled u

20、p level h 1, for a total of 2h 1 nodes.5.16 The largest element could be at any leaf node.5.17 The corresponding array will be in the following order (equivalent to levelorder for the heap):12 9 10 5 4 1 8 7 3 236 Chap. 5 Binary Trees5.18 (a) The array will take on the following order:6 5 3 4 2 1The

21、 value 7 will be at the end of the array.(b) The array will take on the following order:7 4 6 3 2 1The value 5 will be at the end of the array.5.19 / Min-heap classtemplate class minheap private:Elem* Heap; / Pointer to the heap arrayint size; / Maximum size of the heapint n; / # of elements now in

22、the heapvoid siftdown(int); / Put element in correct placepublic:minheap(Elem* h, int num, int max) / Constructor Heap = h; n = num; size = max; buildHeap(); int heapsize() const / Return current size return n; bool isLeaf(int pos) const / TRUE if pos a leaf return (pos = n/2) & (pos =0; i-) siftdow

23、n(i); ;template void minheap:siftdown(int pos) while (!isLeaf(pos) / Stop if pos is a leafint j = leftchild(pos); int rc = rightchild(pos);if (rc n) & Comp:gt(Heapj, Heaprc)j = rc; / Set j to lesser childs valueif (!Comp:gt(Heappos, Heapj) return; / Done37swap(Heap, pos, j);pos = j; / Move downtempl

24、ate bool minheap:insert(const Elem& val) if (n = size) return false; / Heap is fullint curr = n+;Heapcurr = val; / Start at end of heap/ Now sift up until currs parent currwhile (curr!=0) &(Comp:lt(Heapcurr, Heapparent(curr) swap(Heap, curr, parent(curr);curr = parent(curr);return true;template bool

25、 minheap:removemin(Elem& it) if (n = 0) return false; / Heap is emptyswap(Heap, 0, -n); / Swap max with last valueif (n != 0) siftdown(0); / Siftdown new root valit = Heapn; / Return deleted valuereturn true;38 Chap. 5 Binary Trees/ Remove value at specified positiontemplate bool minheap:remove(int

26、pos, Elem& it) if (pos = n) return false; / Bad posswap(Heap, pos, -n); / Swap with last valuewhile (pos != 0) &(Comp:lt(Heappos, Heapparent(pos)swap(Heap, pos, parent(pos); / Push up if largesiftdown(pos); / Push down if small keyit = Heapn;return true;5.20 Note that this summation is similar to Eq

27、uation 2.5. To solve the summationrequires the shifting technique from Chapter 14, so this problem may be tooadvanced for many students at this time. Note that 2f(n) f(n) = f(n),but also that:2f(n) f(n) = n(24+48+616+ +2(log n 1)n) n(14+28+316+ +log n 1n)= n(logn1i=112i log n 1n)= n(1 1n log n 1n)=

28、n log n.5.21 Here are the final codes, rather than a picture.l 00h 010i 011e 1000f 1001j 101d 11000a b c g 1101k 11139The average code length is 3.234455.22 The set of sixteen characters with equal weight will create a Huffman codingtree that is complete with 16 leaf nodes all at depth 4. Thus, the

29、average codelength will be 4 bits. This is identical to the fixed length code. Thus, in thissituation, the Huffman coding tree saves no space (and costs no space).5.23 (a) By the prefix property, there can be no character with codes 0, 00, or001x where “x” stands for any binary string.(b) There must

30、 be at least one code with each form 1x, 01x, 000x where“x” could be any binary string (including the empty string).5.24 (a) Q and Z are at level 5, so any string of length n containing only Qs andZs requires 5n bits.(b) O and E are at level 2, so any string of length n containing only Os andEs requ

31、ires 2n bits.(c) The weighted average is5 5 + 10 4 + 35 3 + 50 2100= 2.7bits per character5.25 This is a straightforward modification./ Build a Huffman tree from minheap h1template HuffTree*buildHuff(minheapHuffTree*,HHCompare * hl) HuffTree *temp1, *temp2, *temp3;while(h1-heapsize() 1) / While at l

32、east 2 itemshl-removemin(temp1); / Pull first two treeshl-removemin(temp2); / off the heaptemp3 = new HuffTree(temp1, temp2);hl-insert(temp3); / Put the new tree back on listdelete temp1; / Must delete the remnantsdelete temp2; / of the trees we createdreturn temp3;6General Trees6.1 The following al

33、gorithm is linear on the size of the two trees./ Return TRUE iff t1 and t2 are roots of identical/ general treestemplate bool Compare(GTNode* t1, GTNode* t2) GTNode *c1, *c2;if (t1 = NULL) & (t2 != NULL) |(t2 = NULL) & (t1 != NULL)return false;if (t1 = NULL) & (t2 = NULL) return true;if (t1-val() !=

34、 t2-val() return false;c1 = t1-leftmost_child();c2 = t2-leftmost_child();while(!(c1 = NULL) & (c2 = NULL) if (!Compare(c1, c2) return false;if (c1 != NULL) c1 = c1-right_sibling();if (c2 != NULL) c2 = c2-right_sibling();6.2 The following algorithm is (n2)./ Return true iff t1 and t2 are roots of ide

35、ntical/ binary treestemplate bool Compare2(BinNode* t1, BinNodeElem* t2) BinNode *c1, *c2;if (t1 = NULL) & (t2 != NULL) |(t2 = NULL) & (t1 != NULL)return false;if (t1 = NULL) & (t2 = NULL) return true;4041if (t1-val() != t2-val() return false;if (Compare2(t1-leftchild(), t2-leftchild()if (Compare2(t

36、1-rightchild(), t2-rightchild()return true;if (Compare2(t1-leftchild(), t2-rightchild()if (Compare2(t1-rightchild(), t2-leftchild)return true;return false;6.3 template / Print, postorder traversalvoid postprint(GTNode* subroot) for (GTNode* temp = subroot-leftmost_child();temp != NULL; temp = temp-r

37、ight_sibling()postprint(temp);if (subroot-isLeaf() cout Leaf: ;else cout Internal: ;cout value() n;6.4 template / Count the number of nodesint gencount(GTNode* subroot) if (subroot = NULL) return 0int count = 1;GTNode* temp = rt-leftmost_child();while (temp != NULL) count += gencount(temp);temp = te

38、mp-right_sibling();return count;6.5 The Weighted Union Rule requires that when two parent-pointer trees aremerged, the smaller ones root becomes a child of the larger ones root. Thus,we need to keep track of the number of nodes in a tree. To do so, modify thenode array to store an integer value with

39、 each node. Initially, each node isin its own tree, so the weights for each node begin as 1. Whenever we wishto merge two trees, check the weights of the roots to determine which hasmore nodes. Then, add to the weight of the final root the weight of the newsubtree.6.60 1 2 3 4 5 6 7 8 9 10 11 12 13

40、14 15-1 0 0 0 0 0 0 6 0 0 0 9 0 0 12 06.7 The resulting tree should have the following structure:42 Chap. 6 General TreesNode 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Parent 4 4 4 4 -1 4 4 0 0 4 9 9 9 12 9 -16.8 For eight nodes labeled 0 through 7, use the following series of equivalences:(0, 1) (2, 3)

41、(4, 5) (6, 7) (4 6) (0, 2) (4 0)This requires checking fourteen parent pointers (two for each equivalence),but none are actually followed since these are all roots. It is possible todouble the number of parent pointers checked by choosing direct children ofroots in each case.6.9 For the “lists of Ch

42、ildren” representation, every node stores a data value and apointer to its list of children. Further, every child (every node except the root)has a record associated with it containing an index and a pointer. Indicatingthe size of the data value as D, the size of a pointer as P and the size of anind

43、ex as I, the overhead fraction is3P + ID + 3P + I.For the “Left Child/Right Sibling” representation, every node stores threepointers and a data value, for an overhead fraction of3PD + 3P.The first linked representation of Section 6.3.3 stores with each node a datavalue and a size field (denoted by S). Each child (every node except the root)also has a pointer pointing to it. The overhead fraction is thusS + PD + S + Pmaking it quite efficient.The second linked representation of Section 6.3.3 stores with each node adata value and a pointer to the list of children. Each chi