Name  _____________________________

 

CPTR247  Fall '05  (100 points)                                                                                            Exam 2

 

1.        Complete the following table by entering the algorithmic complexity for each method.  (1 point each)

 

Enter one of the following for each:

                     C    for constant time – O(1)

                  log    for logarithmic time – O(log2n)

                      n    for linear time – O(n)

                    n2    for quadratic time – O(n2)

 

Data Type

Implementations

Methods

averageTime(n)

worstTime(n)

vector

dynamically allocated array with pointers start, finish, and end-of-storage

push_back

 

 

insert

 

 

erase

 

 

size

 

 

operator [ ]

 

 

array

unsorted

find

 

 

array

sorted

find

 

 

list

doubly linked list with a dummy header node, node (a pointer to the dummy node), and length

 

push_front

 

 

push_back

 

 

size

 

 

operator =

 

 

deque

dynamically allocated blocks (array-based) with a map array, start, and finish

 

push_back

 

 

operator [ ]

 

 

begin

 

 

end

 

 

push_front

 

 

stack

deque

empty

 

 

size

 

 

push

 

 

top

 

 

pop

 

 

binary search tree

doubly linked tree with dummy header node, pointer to header, node_count

size

 

 

find

 

 

erase

 

 

 


2.        Explain how push_back works for the vector class and why the averageTime(n) and worseTime(n) are as you stated in question 1.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.        Explain how insert works for the vector class and why the averageTime(n) and worseTime(n) are as you stated in question 1.  (4 points)

 


4.        Let’s compare the vector and list classes. 

a.        Explain why the insert method is more efficient in the list class than in the vector class.  (3 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.       What O(1) operation does the vector class have that the list class does not, thereby making it an attractive data structure for some applications?  Why doesn’t the list class have that operation?  (3 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.        What is meant when we say a data structure is LIFO or FIFO?  For each, give an example of a data structure that falls into each category. (4 points)

 

LIFO -

 

 

 

 

 

 

        FIFO -

 

 

 

 


6.        Evaluate the following postfix expressions:  (2 points)

 

12  2  1  +  /    

 

 

12  2  +  1  /    

 

 

 

 

7.        Explain how the insert method of the binary search tree class works.  (4 points) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Explain why the averageTime(n) for the insert method of the binary search tree is O(log n) while the worstTime(n) is linear.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 


8.         Answer the following questions regarding this tree: 

                                        

 

Is this a binary search tree?  (yes or no)  (1 point)

 

 

What is the root? (1 point)

 

 

How many nodes are in the tree? (1 point)

 

 

What is the height of the tree?  (1 point)

 

 

List the leaves in the tree. (2 points)

 

 

 

 

Name the children of node 25: (1 points)

 

 

 

Name the parent of node 16: (1 points)

 

 

 

List the nodes as they would be processed in a breadth-first search: (2 points)

 

 

 

List the nodes as they would be processed in a preorder traversal: (2 points)

 

 

 

List the nodes as they would be processed in an inorder traversal: (2 points)

 

 

 

List the nodes as they would be processed in a postorder traversal: (2 points)


9.        Construct a two-tree that is not complete.  (2 points)

 

 

 

 

 

 

 

 

 

 

 

 

10.     Construct a complete tree that is not a two-tree.  (2 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

11.     Construct a binary tree of height 3 with 8 nodes.  (2 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

12.     What is the largest number of nodes possible in a binary tree of height 3?  (1 point)

 

 

 

 

 

13.     What is the smallest number of nodes possible in a binary tree of height 3? (1 point)