DATA STRUCTURE EXAM
QUESTIONS AND ANSWERS
Algorithm Definition - Answer- A set of steps to accomplish a task...
Algorithm according to Meriam-Webster Dictionary: a procedure for solving a
mathematical problem (as of finding the greatest common divisor) in a finite number
of steps that frequently involves repetition of an operation; broadly : a step-by-step
procedure for solving a problem or accomplishing some end especially by a
computer.
What makes a good algorithm? - Answer- 1. correctness (solves a problem)
2. efficiency
Asymptotic Analysis - Answer- Tells us that some algorithms are more efficient than
others
Merge Sort Big-O notation - Answer- (n log n)
n = # of items
log n= number of splits for that number of items
ex. log2 8=3
8-#of items
3=number of splits for that amount of items
Linear Search Big-O notation - Answer- O(n)
because we must look at all n items from a[0] to a[...] wherever it ends
Binary Search Description - Answer- It works by repeatedly dividing in half the
portion of the list that could contain the item, until you've narrowed down the possible
locations to just one.
32 teams qualified for the 2014 World Cup. If the names of the teams were arranged
in sorted order (an array), how many items in the array would binary search have to
examine to find the location of a particular team in the array, in the worst case?
Choose 1 answer:
Choose 1 answer:
A
At most, 32.
B
At most, 6.
C
At most, 16.
D
, At most, 1. - Answer- B. at most 6
What is
lg(32)
lg(32), the base-2 logarithm of 32?
Choose 1 answer:
Choose 1 answer:
A
5
B
16
C
32
D
1 - Answer- A. 5
You have an array containing the prime numbers from 2 to 311 in sorted order: [2, 3,
5, 7, 11, 13, ..., 307, 311]. There are 64 items in the array. About how many items of
the array would binary search have to examine before concluding that 52 is not in
the array, and therefore not prime?
Choose 1 answer:
Choose 1 answer:
11
7
32
1
64
128
22 - Answer- 7
In 2013, there were 193 member states in the United Nations. If the names of these
states were sorted alphabetically in an array, about how many names would binary
search examine to locate a particular name in the array, in the worst case?
Choose 1 answer:
Choose 1 answer:
A
No more than 9.
QUESTIONS AND ANSWERS
Algorithm Definition - Answer- A set of steps to accomplish a task...
Algorithm according to Meriam-Webster Dictionary: a procedure for solving a
mathematical problem (as of finding the greatest common divisor) in a finite number
of steps that frequently involves repetition of an operation; broadly : a step-by-step
procedure for solving a problem or accomplishing some end especially by a
computer.
What makes a good algorithm? - Answer- 1. correctness (solves a problem)
2. efficiency
Asymptotic Analysis - Answer- Tells us that some algorithms are more efficient than
others
Merge Sort Big-O notation - Answer- (n log n)
n = # of items
log n= number of splits for that number of items
ex. log2 8=3
8-#of items
3=number of splits for that amount of items
Linear Search Big-O notation - Answer- O(n)
because we must look at all n items from a[0] to a[...] wherever it ends
Binary Search Description - Answer- It works by repeatedly dividing in half the
portion of the list that could contain the item, until you've narrowed down the possible
locations to just one.
32 teams qualified for the 2014 World Cup. If the names of the teams were arranged
in sorted order (an array), how many items in the array would binary search have to
examine to find the location of a particular team in the array, in the worst case?
Choose 1 answer:
Choose 1 answer:
A
At most, 32.
B
At most, 6.
C
At most, 16.
D
, At most, 1. - Answer- B. at most 6
What is
lg(32)
lg(32), the base-2 logarithm of 32?
Choose 1 answer:
Choose 1 answer:
A
5
B
16
C
32
D
1 - Answer- A. 5
You have an array containing the prime numbers from 2 to 311 in sorted order: [2, 3,
5, 7, 11, 13, ..., 307, 311]. There are 64 items in the array. About how many items of
the array would binary search have to examine before concluding that 52 is not in
the array, and therefore not prime?
Choose 1 answer:
Choose 1 answer:
11
7
32
1
64
128
22 - Answer- 7
In 2013, there were 193 member states in the United Nations. If the names of these
states were sorted alphabetically in an array, about how many names would binary
search examine to locate a particular name in the array, in the worst case?
Choose 1 answer:
Choose 1 answer:
A
No more than 9.
