CSCI 203 Fall 2012 Exam #1
Directions: This test is closed book, closed notes,
closed cell phones, closed neighbor, but open mind (hopefully). Write all your answers in the space
provided. If you need more room, use the
back of one of the other sheets, but indicate where I can find your
answer. Write legibly—if I can’t read
it, I have to assume it is wrong. Read
through all the questions before answering any of them in order to find the
easy ones, answer them first, and maximize your score. Each question is 20 points while the bonus is
5. You have 50 minutes…good luck and
have fun!
1.
Describe
a way to store polynomials in an array that can store polynomials of any degree
in a minimal amount of space. Show a
sample polynomial stored in an array using your technique.
2.
You
are to choose between two different algorithms.
One has a “big Oh” of n7 while the other has a “big Oh” of
1000n6+10000n5+1000000n4. Which would you choose if you needed to solve
problems involving large data sets?
3.
You
have a doubly linked circular linked list of integers with a header node of
type node, pointed to by the pointer variable head which points to a node. Write code to insert a new integer x at the
front of the list. Be sure to allocate a
new node to hold the integer.
4.
Given
two queues with the usual insert and remove routines, we are implementing a
stack. Write code for the push and pop
routines.
5.
If
you need a list data structure, when would you use an array, and when would you
use a linked list? Discuss insert,
delete, and search times.
BONUS:
Sudoku…you
know the routine. Each row, column, and
marked 3x3 square contains the digits 1-9 exactly once. Fill in the missing numbers to continue to
make this true.
|
|
|
3 |
|
6 |
9 |
|
|
|
|
|
6 |
4 |
|
|
|
|
9 |
|
|
7 |
|
|
4 |
8 |
|
1 |
|
|
|
|
|
|
|
|
|
9 |
3 |
|
|
|
|
|
1 |
|
2 |
|
|
|
|
|
9 |
5 |
|
|
|
|
|
|
|
|
|
2 |
|
3 |
4 |
|
|
7 |
|
|
3 |
|
|
|
|
8 |
6 |
|
|
|
|
|
7 |
1 |
|
3 |
|
|