Answers to Selected Exercises Chapter 1
Download 0.49 Mb.
|
- Navigate this page:
- Chapter 8
Chapter 71. (a) The base case is a nonrecursive exit from the recursive routine. (b) The general (or recursive) case is a path that includes a recursive call to the routine, to solve a smaller version of the original problem. (c) The run-time stack is a structure that keeps track of the activation records at run time, in order to preserve the values of parameters, return addresses, registers, and so on. (d) Binding time refers to the point in the compile/execution cycle when variable names are associated with addresses in memory. (e) Tail recursion occurs when the recursive call is the last statement executed in a recursive function. 4. Answering yes to Question 1 provides us with a base case that works correctly. In answering Question 3, we make an assumption that the function works for some artibary case. We can then show that applying the function to the next value results in the correct answer in the general case. 7. (a) The base cases are return -1 and return 1. (b) The general case is return base*Puzzle(base+1, limit). 10. (a) int Power(int base, int exponent) // Returns the base raised to the exponent { if (exponent == 0) return 1; // base case else
return base * Power(base, exponent-1); // general case } (b) int Factorial(int number) // Returns the factorial of number (number!) { if (num > 0) return num * Factorial(num - 1); // general case else
if (num == 0) return 1; // base case } (c)
void Sort(int values[], int fromIndex, int toIndex) // Sorts values from values[fromIndex] .. values[toIndex]. // The maximum value left in the unsorted portion is put into its // proper place on each call. { int maxIndex; if (fromIndex != toIndex) { // general case maxIndex = MaxPosition(values, fromIndex, toIndex); Swap(values[maxIndex], values[toIndex]); Sort(values, fromIndex, toIndex - 1); } // base case is when fromIndex equals toIndex: do nothing } 13. (a)
int Fibonacci(int number) { if (number <= 1) return number; else
return Fibonacci(number - 2) + Fibonacci(number - 1); } (b) int Fibonacci(int number) { int current; int previous; int temp; if (number <= 1) return 1; else {
current = 1; for (int count = 2; count <= number; count++) { temp = previous; previous = current; current = temp + previous; } return current; } } (c) #include int Fibonacci(int number); int main() { using namespace std; int number; cout << "Input the fibonacci number you wish." << endl; << "Input a negative number to quit." << endl; cin >> number; while (number >= 0) { cout << "number: " << number << endl; << "Fibonacci number: " << Fibonacci(number) << endl; cout << "Input the fibonacci number you wish." << endl; << "Input a negative number to quit." << endl; cin >> number; } return 0; } // Put the function version you are testing here. (d) The recursive solution is inefficient because some of the intermediate values are calculated more than once. (e) The following version, which uses an auxiliary recursive function, is more efficient. Note that the recursive parameters are used to keep track of the current and previous numbers, rather than recalculating them. int Fibonacci(int number) { return Fib(number, 1, 1); } int Fib(int number, int previous, int current) { if (number == 0) return previous; else
return Fib(number - 1, current, current + previous) } 16. (a) // corrected version int NumPaths(int row, int col, int n) { if (row == n || col == n) return 1 else
return NumPaths(row + 1, col, n) + NumPaths(row, col + 1, n); }. (b) The algorithm is inefficient because it calculates some of the intermediate values of NumPaths more than once. (c) const int MAX = 10; int table[MAX][MAX]; . . . int NumPaths2(int row, int col, int n) { if (row == n || col == n) table[row][col] = 1; else if (table[row][col] == 0) table[row][col] = NumPaths2(row+1, col, n) + NumPaths2(row, col+1, n) return table[row][col]; } (d) // initialize table for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX, j++) table[i][j] = 0; // solve problem answer = NumPaths2(l, l, MAX); (e) The second version is more efficent in terms of execution time, but requires additional space for an N x N array of integers.
22. (a) False. Recursive solutions are often less efficient in terms of computing time. (b) True (c) False. Recursive solutions generally require more space in the run-time stack. (d) True. (Don't you want a good grade in this course?)
5. (a) 30 (5 different shapes with 6 different combinations of values for each) (b) 5 (5 different shapes with one legal combinations of values for each) 10. Show what order the nodes in the tree are processed by (a) BDJKMNPQRTWY (b) BJDNPMKRWYTQ (c) QKDBJMPNTRYW 13. (a) The path would go through the nodes containing 56, 69, 59, 62, and 61. (b) The path would go through the nodes containing 56, 47, 22, 29, and 23, before determining that 28 is not in the tree. 14. (a) 11 22 23 29 30 47 49 56 59 61 62 64 69 (b) 11 23 30 29 22 49 47 61 64 62 59 69 56 (c) 56 47 22 11 29 23 30 49 69 59 62 61 64 17. (a) False (b) False (c) True (d) False 19. (a) Elements inserted in random order: Linked list: O(N) Binary search tree: O(log2N) (b) Elements inserted in order: Linked list: O(N) Binary search tree: O(N) 22 template void DeleteNode(TreeNode // Deletes the node pointed to by tree. // Post: The user's data in the node pointed to by tree is no // longer in the tree. If tree is a leaf node or has one NULL // child pointer // the node pointed to by tree is deleted; otherwise, the // user's data is replaced by its logical successor and the // successor's node is deleted. { TreeNode ItemType data; tempPtr = tree; if (tree->left == NULL) tree = tree->right; else if (tree->right == NULL) tree = tree->left; else
{ tempPtr = PtrToSuccessor(tree); tree->info = tempPtr->data; } delete tempPtr; } 24. 1. The Base-Case Question: Yes. The base case occurs when the node to be deleted has been found, when item equals tree->info. In this case we call the DeleteNode function; no further recursive calls are made. 2. The Smaller-Caller Question: Yes. In each of the two general cases, a recursive call is made to delete the element from a subtree, left or right, of the current tree. Deleting from a subtree is a smaller version of the problem. 3. The General Case Question: Yes. If item is less than tree->info, then we know that the node to be deleted is in tree's left subtree. Assuming that the recursive call successfully deletes from the left subtree, the problem is solved correctly. Otherwise, if item is greater than tree->info, we know that the node to be deleted is in tree's right subtree. Again, assuming that the recursive call successfully deletes from the right subtree, the problem is solved correctly. 27.
template void PrintAncestors(TreeNode // prototype template void TreeType // Calls recursive function PrintAncestors to print the ancestors. { PrintAncestors(root, value); } template void PrintAncestors(TreeNode { if (tree->info != value) { std::cout << tree->info << endl; if (tree->info < value) PrintAncestors(tree->right, value); else PrintAncestors(tree->left, value); } } 30. int LeafCount(); // prototype // Post: Function value = number of leaf nodes in the tree. template int Count(TreeNode template int TreeType // Calls recursive function Count to count the number // of leaf nodes. { return Count(root); } template int Count(TreeNode { if (tree == NULL) return 0; else if (tree->left == NULL) && (tree->right == NULL) return 1; else
return Count(tree->left) + Count(tree->right); } 33. (a) bool SimilarTrees(TreeType // Post: True is returned if self and otherTree are similar; false // is returned otherwise. template bool Similar(TreeType // prototype // Recursive function to determine if two trees are similar. (b)
template bool TreeType { return Similar(root, otherTree.root); } template bool Similar(TreeNode { if (tree1 == NULL && tree2 == NULL) return true; else if (tree1 == NULL && tree2 != NULL) || (tree1 != NULL && tree2 == NULL) return false; else return Similar(tree1->left, tree2->left) && Similar(tree2->right, tree2->right); } 35. template void MakeTree(TreeType // Creates a binary tree from a sorted array. { tree.MakeEmpty(); AddElements(tree, info, 0, length-1); }
void AddElements(TreeType int fromIndex, int toIndex) { int midIndex; if (fromIndex <= toIndex) { midIndex = (fromIndex + toIndex) / 2; tree.InsertItem(info[midIndex]); AddElements(tree, info, fromIndex, midIndex - 1); // Complete the left subtree. AddElements(tree, info, midIndex+1, toIndex); // Complete the right subtree. } } 38. Either the value in node 5 or the value in node 6. 40. Preorder 43. (a) Any negative number can be used as a dummy value. (b) Assume that the dummy value is -1.0. tree
Directory: samples samples -> Running head: capstone project samples -> Memorandum of understanding long beach city college- long beach unified school district samples -> Cell Phone Antennas: a look at the history and design of vhf antennas samples -> Affinity program guidelines samples -> Chapter 2: Setting Up Your Android Development Environment Multiple Choice Questions samples -> High School Musical samples -> Finance crisis Introduction samples -> Android Application Development: Working with the Emulator samples -> - Download 0.49 Mb. Share with your friends:
|