Skip to content
Textbook Guides

Data Structures and Other Objects Using C++ 4th Edition Solution Manual

Need to ace your assignments? Use Data Structures and Other Objects Using C++ 4th Edition Solution Manual for detailed, easy-to-understand solutions to textbook questions.

Preview 8 of 26 pages

See the first 8 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Chapter 1: Solutions to Sample Exam Questions Short Answer Questions 1.1. Use a precondition/postcondition contract. For example: double new_balance(double balance, double interest_rate); // Precondition: The parameter interest_rate is the annual bank // account interest rate, for example 5.0 for 5%. The parameter // balance is an account balance before interest is posted. // Postcondition: The value returned by the function is the new // account balance after posting one year of simple interest at // the rate given by interest_rate. 1.2. A precondition is a statement giving the condition that is supposed to be true when a function is called. A postcondition is a statement describing what will be true when a function call is completed. 1.3. If the precondition fails, the function can print an error message and halt the program. 1.4. Preconditions cannot always be checked. 1.5. If you call a function and the precondition is false, then there is no telling what might happen. Anything could happen, including erasing the entire hard drive. Of course, the functions that we write try to avoid such unpleasant behavior, but there is no guarantee. 1.6. void exam(int i) // Precondition: i is not equal to 42. // Library facilities used: assert.h { assert(i != 42); ... 1.7. log n is the approximate number of digits in n (using base 10 logs). (The exact formula is floor(log n) + 1, using base 10 logs and the floor function which rounds a real number down to the next lowest integer.) 1.8. Even a slow processor will beat a fast processor if the slower processor uses a faster algorithm and the input size is large enough. 1.9. The first formula is O(n). The second and fourth formulas are O(n^2) (using ^ for exponentiation). The third formula is O(log n). 1.10. See the Method 2 analysis on page 17 of the text. 1.11. My debugger lets me run a program and stop it at a specified point to examine the current values of variables. After this, I can step through the program one line at a time, continuing to keep a watch on variable values. Or I can continue execution in a normal way, specifying a later point to stop the program. Multiple Choice Questions:

  2. Page 2
  3. Page 3
    Read page 3 as text

    1.1 B 1.6 B 1.11 B 1.16 E 1.2 D 1.7 A 1.12 False 1.17 C 1.3 D 1.8 B 1.13 False 1.18 A 1.4 False 1.9 A 1.14 B 1.19 E 1.5 False 1.10 D 1.15 B Chapter 2: Solutions to Sample Exam Questions Short Answer Questions 2.1. Assuming that we are using the namespace main_savitch_2A: throttle quiz; quiz.shut_off( ); cout << quiz.flow( ); 2.2. class throttle { public: throttle( ); // C throttle(int size); // C void shut_off( ); void shift(int amount); double flow( ) const; // X bool is_on( ) const; // X ... 2.3. If you write a class with no constructors, then the compiler automatically creates a simple default constructor called the "automatic default constructor". The automatic default constructor doesn't do much work -- it just calls the default constructors for the member variables that are objects of some other class. 2.4. An inline member function has it's entire implementation given right in the class definition. For example, the throttle's shut_off member function shown here: class throttle { public: throttle( ); throttle(int size); void shut_off( ) { position = 0; } ... 2.5. A macro guard consists of three # compiler directives to avoid the accidental duplicate inclusion of some defintions. For example: #ifndef throttle_H #define throttle_H ... #endif 2.6. #include "throttle.h" using namespace main_savitch_2A; or using namespace main_savitch_2A::throttle;

  4. Page 4
    Read page 4 as text

    2.7. A const reference parameter guarantees that a function's implementation does not change the value of the parameter. It may be used whenever the function's implementation does not even try to change a parameter (and usually when the parameter might be a large data type rather than something small like an int). For example: double length(const Point& p) // Postcondition: The return value is the distance of p from the origin. { return sqrt(p.get_x( )*p.get_x( ) + p.get_y( )*p.get_y( )); } 2.8. x should be a value parameter if you do not want the changes to change the actual argument. x should be a reference parameter if you do want the changes to change the actual argument. x could never be a const reference parameter in this example (since the body of the function is changing x). 2.9. Use a const reference parameter when the function's implementation does not even attempt to change the value of the parameter. 2.10. Use a reference parameter when the function's implementation does change the value of a parameter and you want the change to alter the actual argument. 2.11. This is a bit of a trick question, and I'm not sure that I would ask it on an exam. The trick is to realize that even the const member function can alter x.size (although it cannot alter the size member variable of the object that activates the const function). x = y; Legal in all three places. x.size = y.size; Not legal in main program, but legal in a member function or a friend function. x.size = 3; Not legal in main program, but legal in a member function or a friend function. x.h(42); Legal in all three places. 2.12. foo foo::operator +(const foo& f1, const foo& f2); The argument names f1 and f2 are unimportant. Usually f1 and f2 are const reference parameters, but there may be situations where that is not true. The function may also need to be a friend function (if it needs access to the foo private members). 2.13. The operator + must be a friend of the class. 2.14. You are implementing a class and you want to write a non - member function that needs access to the class's private members. Multiple Choice Questions: 2.1 D 2.6 C 2.11 D 2.2 D 2.7 A 2.3 D 2.8 D 2.4 C 2.9 C

  5. Page 5
    Read page 5 as text

    2.5 B 2.10 D Chapter 3: Solutions to Sample Exam Questions Short Answer Questions 3.1. The value_type is defined at the top of the bag class definition: class bag { typedef int value_type; ... It is better to use the value_type typedef (rather than just using an int) because it makes it write a new bag class with a different kind of item in the bags. 3.2. You need a variable to keep track of how much of the partially - filled array is currently being used. 3.3. There is only one copy of the static member constant for the entire class. This is different than ordinary member variables where each object has it's own copy of the member variables. 3.4. The size_t variable i can never hold a negative value, so an error occurs when -- i is executed with i equal to zero. A typical error is that i will actually be set to the biggest unsigned int. 3.5. Note that the correct loop must run i backward: for (i = 99; i >= 51; -- i) data[i] = data[i - 1]; data[50] = 42; 3.6. Note that the correct loop must run i forward: for (i = 51; i <= 99; ++i) data[i - 1] = data[i]; Multiple Choice Questions: 3.1 B 3.6 B 3.11 D 3.2 A 3.7 C 3.12 D 3.3 A 3.8 D 3.13 D 3.4 B 3.9 E 3.14 A 3.5 B 3.10 B 3.15 D Chapter 4: Solutions to Sample Exam Questions Short Answer Questions 4.1. int i; p = new int[100]; for (i = 0; i < 100; i++) p[i] = i; delete [ ] p; 4.2. A bad_alloc exception is thrown.

  6. Page 6
    Read page 6 as text

    Note: In older versions of C++, a function called the new_handler was called. Normally, the new_handler then prints an error message and halts the program. 4.3. p1 points to i (containing 42) and p2 points to k (containing 80). ---- ---- i| 42 | k| 80 | ---- ---- ^ ^ | | -- | -- -- | -- p1| . | p2| . | ----- ----- 4.4. The pointers still point to the same variables, but both variables now contain 80. ---- ---- i| 80 | k| 80 | ---- ---- ^ ^ | | -- | -- -- | -- p1| . | p2| . | ----- ----- 4.5. Both p1 and p2 now point to k: ---- ---- i| 42 | k| 80 | ---- ---- ^ ^ ____________| | / | --- / - --- | - p1| . | p2| . | ----- ----- 4.6. The parameter is an array of double numbers. The function's implementation does not change any values in the array. 4.7. The parameter p is a constant pointer. Within foo, the integer *p cannot be changed. However, p itself can be changed (making it point to another integer). 4.8. For two bags x and y and the statement x=y, the automatic assignment operator will simply copy the member variables from y to x. So we will end up with both x.data and y.data pointing to the same dynamic array. 4.9. The approach works correctly, but it is slow if we add many items after the initial capacity is reached. The slowness comes from the fact that each time we add a new item, a new (slightly larger) dynamic

  7. Page 7
    Read page 7 as text

    array is allocated, the items are copied from the old array to the new array, and the old array is returned to the heap. A better solution might increase the size by at least 50%, as shown here: resize(used*1.5 + 1); 4.10. void bag::triple_capacity( ) { Item *new_array = new Item[capacity * 3]; size_t i; for (i = 0; i < used; i++) new_array[i] = data[i]; delete [ ] data; data = new_array; capacity = capacity * 3; } 4.11 operator * 4.12 void printem(const polynomial&amp; p) { int i; for (i = 1; i &lt;= 10; ++i) cout &lt;&lt; p.eval( double(i) ); } void zapbig(polynomial&amp; p) { p.assign_coef(0.0, p.degree( )); } 4.13 The [0] element has the value 3.0. The [2] element has the value 2.1. The [4] element has the value 4.1. The other elements are zero, and the current degree is 4. 4.14 There are several possible answers, but the simplest is: p.assign_coef(0.09, 4); 4.15 double slope(const polynomial&amp; p, double x) { return p.derivative( ).eval(x); } Multiple Choice Questions: 4.1 D 4.6 C 4.11 B 4.16 C 4.21 D 4.2 D 4.7 C 4.12 A 4.17 C 4.22 C 4.3 A 4.8 A 4.13 D 4.18 D 4.4 D 4.9 A 4.14 B 4.19 A 4.5 C 4.10 Yes 4.15 B 4.20 C Chapter 5: Solutions to Sample Exam Questions Short Answer Questions 5.1. head_ptr = new node(entry, head_ptr);

  8. Page 8
    Read page 8 as text

    5.2. Declare a node* variable called temp and make it equal to p - &gt;link( ); Change p - &gt;link( ) to point to the next node (temp - >link( )). Then delete temp. 5.3. node *cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor - &gt;link( )) cout &lt;&lt; cursor - &gt;data( ) &lt;&lt; endl; 5.4. locate_ptr = locate_ptr - &gt;link( ); 5.5. size_t count_42s(const node* head_ptr) { size_t answer = 0; const node * cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor - &gt;link( )) if (cursor - &gt;data( ) == 42) answer++; return answer; } 5.6. bool has_42(const node* head_ptr) { const node * cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor - &gt;link( )) if (cursor - &gt;data( ) == 42) return true; return false; } 5.7. bool all_42s(const node* head_ptr) { const node* cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor - &gt;link( )) if (cursor - &gt;data( ) != 42) return false; return true; } 5.8. int sum(const node* head_ptr) { const node* cursor; int answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor - &gt;link( )) answer += cursor - &gt;data( ); return answer; } 5.9. int product(const node* head_ptr) { const node* cursor; int answer = 1;

18 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.