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

精选优质文档-倾情为你奉上数据结构与算法分析（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 fraction 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 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) 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 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 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 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 the 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 <class Elem>void inorder(BinNode<Elem>* subroot) if (subroot = NULL) return; / Empty, do nothingpreorder(subroot->left();visit(subroot); / Perform desired actionpreorder(subroot->right();(b) template <class Elem>void postorder(BinNode<Elem>* 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 necessary.template <class Key, class Elem, class KEComp>bool search(BinNode<Elem>* 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 <class Elem>void level(BinNode<Elem>* subroot) AQueue<BinNode<Elem>*> Q;Q.enqueue(subroot);while(!Q.isEmpty() BinNode<Elem>* temp;Q.dequeue(temp);if(temp != NULL) Print(temp);Q.enqueue(temp->left();Q.enqueue(temp->right();5.7 template <class Elem>int height(BinNode<Elem>* subroot) if (subroot = NULL) return 0; / Empty subtreereturn 1 + max(height(subroot->left(),height(subroot->right();5.8 template <class Elem>int count(BinNode<Elem>* 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 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 for 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 data; 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 node 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 value 24replaces the value 7, and the leaf node that originally contained 24 is removedfrom the tree.5.13 template <class Key, class Elem, class KEComp>int smallcount(BinNode<Elem>* 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(root->rightchild(), K) + 1;5.14 template <class Key, class Elem, class KEComp>void printRange(BinNode<Elem>* 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 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 up 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 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 Elem, class Comp> class minheap private:Elem* Heap; / Pointer to the heap arrayint size; / Maximum size of the heapint n; / # of elements now in 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 < n); int leftchild(int pos) const return 2*pos + 1; / Return leftchild posint rightchild(int pos) const return 2*pos + 2; / Return rightchild posint parent(int pos) const / Return parent position return (pos-1)/2; bool insert(const Elem&); / Insert value into heapbool removemin(Elem&); / Remove maximum valuebool remove(int, Elem&); / Remove from given posvoid buildHeap() / Heapify contents for (int i=n/2-1; i>=0; i-) siftdown(i); ;template <class Elem, class Comp>void minheap<Elem, Comp>: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 downtemplate <class Elem, class Comp>bool minheap<Elem, Comp>: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 <class Elem, class Comp>bool minheap<Elem, Comp>: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 <class Elem, class Comp>bool minheap<Elem, Comp>:remove(int pos, Elem& it) if (pos < 0) | (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 Equation 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)= 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 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 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 requires 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 <class Elem>HuffTree<Elem>*buildHuff(minheap<HuffTree<Elem>*,HHCompare<Elem> >* hl) HuffTree<Elem> *temp1, *temp2, *temp3;while(h1->heapsize() > 1) / While at least 2 itemshl->removemin(temp1); / Pull first two treeshl->removemin(temp2); / off the heaptemp3 = new HuffTree<Elem>(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 algorithm is linear on the size of the two trees./ Return TRUE iff t1 and t2 are roots of identical/ general treestemplate <class Elem>bool Compare(GTNode<Elem>* t1, GTNode<Elem>* t2) GTNode<Elem> *c1, *c2;if (t1 = NULL) && (t2 != NULL) |(t2 = NULL) && (t1 != NULL)return false;if (t1 = NULL) && (t2 = NULL) return true;if (t1->val() != 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 identical/ binary treestemplate <class Elem>bool Compare2(BinNode<Elem>* t1, BinNode<Elem* t2) BinNode<Elem> *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(t1->rightchild(), t2->rightchild()return true;if (Compare2(t1->leftchild(), t2->rightchild()if (Compare2(t1->rightchild(), t2->leftchild)return true;return false;6.3 template <class Elem> / Print, postorder traversalvoid postprint(GTNode<Elem>* subroot) for (GTNode<Elem>* temp = subroot->leftmost_child();temp != NULL; temp = temp->right_sibling()postprint(temp);if (subroot->isLeaf() cout << "Leaf: "else cout << "Internal: "cout << subroot->value() << "n"6.4 template <class Elem> / Count the number of nodesint gencount(GTNode<Elem>* subroot) if (subroot = NULL) return 0int count = 1;GTNode<Elem>* temp = rt->leftmost_child();while (temp != NULL) count += gencount(temp);temp = temp->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 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 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) (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 Children” 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 anindex 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