Sample Data Structures Questions
Chapter 1
Program Specification, Design, and Analysis

Data Structures and Other Objects Using Java (Third Edition)
by Michael Main
ISBN 0-321-37525-4

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 9 short answer questions and 19 multiple choice questions in this file.

Short Answers

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

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

  3. It's recommended that the precondition be checked at the start of a method. What's a good exception to throw if a method discovers that it was called with arguments that violate the precondition?

  4. What is the purpose of a final variable?

  5. Which tool can provide nicely formatted documentation about how a method works?

  6. Write the first few lines of this method so that it throws an exception when the precondition is violated:
        public static 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
    3 times log (base 2) of n.
    2n² + 10n.

Multiple Choice

    Multiple Choice
    Section 1.1
    Specification, Design, Implementation
  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. When a method is called, who is responsible for ensuring that the precondition is valid?
    • A. The person who is using the program.
    • B. The programmer who called the method.
    • C. The programmer who wrote the method.
    • D. The programmer who implemented the Java Runtime System.

  3. What will happen if a method is executed and the precondition for the method is not met?
    • A. An exception will be thrown.
    • 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 method must be written by the person writing the code for the method.
    • 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 method.
    • TRUE.
    • FALSE.

  6. If the precondition fails, it is a good idea to throw an exception that will generally halt the program. Why is the program halted?
    • A. The Java Runtime System forbid continuation.
    • B. The method is no longer guaranteed to make the postcondition true.
    • C. The method's memory requires have become exponential (or worse).
    • D. The method's running time has become exponential (or worse).

  7. What information do you need to see in order to make effective use of the printNumber method in Section 1.1?
    • A. Just the method's implementation.
    • B. Just the method's specification.
    • C. Both the implementation and specification.

  8. Which of these function calls will cause an exception to be thrown when x is 42. (x is an int variable).
    • A.
         if (0 < x)
            throw new IllegalArgumentExcpetion("Bad x");
    • B.
         if (0 == x)
            throw new IllegalArgumentExcpetion("Bad x");
    • C.
         if (0 > x)
            throw new IllegalArgumentExcpetion("Bad x");
    • D. None of the above will cause an exception when x is 42.

    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
    • D. Quadratic

  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 method 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.

  19. Which software tool will best help you determine whether your test cases are fully exercising your code?
    • A. Compiler
    • B. Debugger
    • C. Make
    • D. Pine
    • E. Profiler

Michael Main (