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
Short Answers Section 1.1 Specification and Design


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.

What is a precondition? What is a postcondition?

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?

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

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?

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


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

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

Convert each time formula to the best possible bigO notation.
Do not include any spurious constants in your bigO answer.
Time Formula  BigO 
10n  .

2n²  .

3 times log (base 2) of n  .

2n² + 10n  .


Write the simplest bigO 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


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


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.

Which phase of the software lifecycle is usually the most expensive?
 A.
Analysis and specification of the task
 B.
Design
 C.
Implementation
 D.
Maintenance and evolution

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.

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.

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

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

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

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


What does a runtime 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

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

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

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.

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.

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

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

Express the formula (n  2)*(n  4) using bigO 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


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.

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.

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
Data Structures and Other Objects Using C++
Michael Main
(main@colorado.edu)
and
Walter Savitch
(wsavitch@ucsd.edu)
Thank you for visiting
http://www.cs.colorado.edu/~main/questions/chap01q.html
Copyright © 2000
AddisonWesley Computer and Engineering Publishing Group