CSCI
203 Spring 2016 Exam #1
Instructions: This exam is closed book, closed notes,
closed technology (cell phones, tablets, computers, calculators, etc), closed neighbor—but open mind. Write your answers in the space
provided. If you need more space, use
the back of one of the exam pages and indicate where I can find your
answer. Read through the entire test
before starting to answer any questions, in order to find the easy ones to
answer first—thus maximizing your score.
There are 20 questions, not counting the bonus question(s), and each is worth
5 points. Good luck and have fun!
1.
We
talked about how to store a polynomial efficiently when there were many terms
missing. Draw a diagram showing how to
store the polynomial -7x15+4x3-2 efficiently and briefly
explain your technique.
2.
We
talked about how to store a large dimensional tri-diagonal matrix (one with the
nonzero values on, or just above or below the diagonal) efficiently. Draw a diagram showing how to store a matrix
like this efficiently and briefly explain your technique.
3.
You
have two matrix multiplication algorithms you are considering using for large
matrices. The first is O(100n7)
and the second is O(10000n5).
Which would you choose to use and why?
4.
For
problem 3 above, what value of n is the break even
point where it makes sense to switch algorithms?
5.
What
is the “big Oh” of a linear search through a list to find an element if the
list is unordered?
6.
What
is an algorithm that can find an element faster than a linear search if the
list is stored in a sorted array?
7.
What
are two different ways to implement a list data structure internally?
8.
What
is the “big Oh” of inserting an element at the back of a linear, singly linked
list that just has a head pointer?
9.
What
is the “big Oh” of inserting an element at the back of a doubly linked,
circular linked list with a header node that points to the head and the tail?
10.
What
is the “big Oh” of the bubble sort?
11.
Given
the array of 9 numbers shown below, show the resulting array at the end of each
pass of the bubble sort.
|
Index |
Value |
Pass 1 |
Pass 2 |
Pass 3 |
Pass 4 |
Pass 5 |
Pass 6 |
Pass 7 |
Pass 8 |
Pass 9 |
|
0 |
8 |
|
|
|
|
|
|
|
|
|
|
1 |
4 |
|
|
|
|
|
|
|
|
|
|
2 |
3 |
|
|
|
|
|
|
|
|
|
|
3 |
7 |
|
|
|
|
|
|
|
|
|
|
4 |
5 |
|
|
|
|
|
|
|
|
|
|
5 |
2 |
|
|
|
|
|
|
|
|
|
|
6 |
6 |
|
|
|
|
|
|
|
|
|
|
7 |
1 |
|
|
|
|
|
|
|
|
|
12.
Give
the sequence of numbers compared when searching an ordered array of numbers
from 1 through 100 when using a binary search to find the number 37.
13.
Give
the code to remove the last element from a circular, doubly linked list with a
header node named head, with data, next, and prev
fields.
14.
Why
would we use a singly linked list with a head pointer instead of an array to
store a list of values?
15.
What
is a real world example of a stack?
16.
What
is a real world example of a queue?
17.
In
computer science, what is one place we use a stack?
18.
Write
code to show how to implement a stack push function using two queues.
19.
Why
should we check the isEmpty() or isFull() functions before
removing an element from a stack?
20.
Write
the isEmpty() function for a circular, doubly linked list with a header
node.
BONUS: Sudoku…each row, column, and highlighted 3x3
square should have each of the digits 1 through 9 occurring in it exactly
once. Fill in the blanks to make it so.
|
|
|
|
|
|
1 |
7 |
5 |
|
|
9 |
|
|
|
8 |
|
|
|
2 |
|
|
|
1 |
2 |
|
5 |
9 |
|
6 |
|
5 |
|
8 |
|
1 |
|
6 |
|
3 |
|
|
2 |
|
|
|
|
|
7 |
|
|
7 |
|
3 |
|
2 |
|
4 |
|
5 |
|
1 |
|
2 |
7 |
|
9 |
3 |
|
|
|
4 |
|
|
|
3 |
|
|
|
9 |
|
|
9 |
5 |
4 |
|
|
|
|
|