CSCI 200
Basic Data Structures
Part I: Complexity of operations
Express the worst-case running time in Big-O notation for the following data structures. Some have been filled out for you.
Queue Stack
Operation Complexity Operation Complexity
enqueue(x) O(1) push(x)
dequeue() pop()
isEmpty() isEmpty()
(Doubly) Linked-List Array
Operation Complexity Operation Complexity
insert an element before/after O(1) insert element at rank i
remove a given node remove element at rank i
access element at rank i access element at rank i
search for an element search for an element
1. Suppose you have to implement a container in which the user will perform the following operations: n calls to insert
(anywhere), n3 calls to access an element at rank i, and search for an element 5 times. Which data structure listed
above would be most efficient? Why?
1
Part II: Practice with trees
A
B C
D E F G
H I J
1. List the nodes as they are visited along a preorder traversal.
2. List the nodes as they are visited along an inorder traversal.
3. List the nodes as they are visited along a postorder traversal.
4. Which node is the root?
5. Which node(s) are internal nodes?
6. Which node(s) are external nodes (i.e., leaves)?
7. What is the depth of node ”G”?
8. What is the height of the tree?