## Sample Data Structures Questions Chapter 1 The Phases of Software Development

### Data Structures and Other Objects Using C++ Fourth Edition by Michael Main and Walter Savitch ISBN 0132129485

#### The Purpose of These Questions

These are typical exam questions from Chapter 1 of the textbook. These exact questions might not be on your exam, but if you research and find the right answers to these questions, that should be good preparation for a real exam. (It's also possible that some of this material was not covered in your class.) At the moment there are 11 short answer questions and 19 multiple choice questions in this file.

 Short Answers Section 1.1 Specification and Design
1. Describe one good method for precisely specifying what a function must do, without indicating how the function accomplishes its work. Provide an example, using a small function.

2. What is a precondition? What is a postcondition?

3. It's recommended that the precondition be checked at the start of a function. What's a good approach if a function discovers that its precondition is not true?

4. Is it always possible for a function to check that its precondition is true?

5. Suppose that you accidently call a correctly implemented function, but the precondition is false. Is the function guaranteed to halt with a nice message? Is the function allowed to erase everything on your hard drive?

6. Write the first few lines of this function so that it uses the assert facility to check its precondition:
```    void exam(int i)
// Precondition: i is not equal to 42.
...
```

 Short Answers Section 1.2 Running Time Analysis

7. Give a concise formula that gives the approximate number of digits in a positive integer. The integer is written in base 10.

8. Why is the order of an algorithm generally more important than the speed of the processor?

9. Convert each time formula to the best possible big-O notation. Do not include any spurious constants in your big-O answer.

Time FormulaBig-O
10n.
2n².
3 times log (base 2) of n.
2n² + 10n.

10. Write the simplest big-O expression to describe the number of operations required for the following algorithm:
```    for (i = 1; i < N; ++i)
{
...statements that require exactly i operations...
}
```

 Short Answers Section 1.3 Testing and Debugging

11. You are at a computer science cocktail party and you meet a student who has just started working with a debugger. With about three or four sentences, explain the basic features of your debugger and how they help you find bugs.

#### Multiple Choice

 Multiple Choice Section 1.1 Specification and Design
1. Why is writing easily modifiable code important?
• A. Easily modifiable code generally has a quicker run time.
• B. Most real world programs require change at some time.
• C. Most text editors make it easy to modify code.
• D. Several people may be writing the same function at the same time.

2. Which phase of the software life-cycle is usually the most expensive?
• A. Analysis and specification of the task
• B. Design
• C. Implementation
• D. Maintenance and evolution

3. What will happen if a function is executed and the precondition for the function is not met?
• A. An error message will be printed.
• B. The program will loop indefinitely.
• C. The system will crash.
• D. Any of the above results could happen.

4. Answer true or false for this statement: When programming in teams, the specification of a function should be written by the person writing the code for the function.
• TRUE.
• FALSE.

5. Answer true or false for this statement: When programming individually (not in a team), there is no need to write a specification for a function
• TRUE.
• FALSE.

6. If the precondition fails, it is a good idea to write a useful error message and then halt the program. Why is the program halted?
• A. Most operating systems forbid continuation.
• B. The function is no longer guaranteed to make the postcondition true.
• C. The function's memory requires have become exponential (or worse).
• D. The function's running time has become exponential (or worse).

7. Which of these is used to stop the program execution when a precondition is not met.
• A. assert();
• B. exit();
• C. return();
• D. void();

8. Which of these statements will always cause a program to halt? (x is an int variable).
• A. assert(10 > 0);
• B. assert(10 < 0);
• C. assert(x < 0);
• D. None of the above will always cause a program to halt.

 Multiple Choice Section 1.2 Running Time Analysis

9. What does a run-time analysis usually count?
• A. The number of arithmetic and other operations required for the program to run
• B. The number of megabytes required for the program to run
• C. The number of seconds required for the program to run
• D. The number of seconds plus the number of megabytes
• E. The number of seconds times the number of megabytes

10. Which of these is the correct big-O expression for 1+2+3+...+n?
• A. O(log n)
• B. O(n)
• C. O(n log n)
• D. O(n²)

11. Which of the following formulas in big-O notation best represent the expression n²+35n+6?
• A. O(n³)
• B. O(n²)
• C. O(n)
• D. O(42)

12. Answer true or false for this statement: For all possible inputs, a linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem.
• TRUE.
• FALSE.

13. Answer true or false for this statement: True or false: An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.
• TRUE.
• FALSE.

14. What term is used to describe an O(n) algorithm.
• A. Constant
• B. Linear
• C. Logarithmic

15. Here is some code for an integer variable n:
```    while (n > 0)
{
n = n/10; // Use integer division
}
```
What is the worst-case time analysis for the above loop?
• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n²)

16. Express the formula (n - 2)*(n - 4) using big-O notation:
• A. O(1)
• B. O(8)
• C. O(log n)
• D. O(n)
• E. None of the above

 Multiple Choice Section 1.3 Testing and Debugging

17. Why is it important to test boundary values when testing programs?
• A. Calculating by hand, it's easy to find the right answers for boundary values.
• B. Debuggers are easier to use when testing boundary values.
• C. In practice, a large proportion of errors arise from boundary values.
• D. The correct execution of a function on all boundary values proves a function is correct.

18. How may boundary values for a function be found?
• A. Pick values that are one step away from different behavior.
• B. Pick values that make the precondition equal to the postcondition.
• C. Pick values where the precondition is false.
• D. Pick values where the postcondition is false.