Unit 7 - Data Structures

Question 1

What is the difference between trees and binary trees?

Answer 1

• Trees are a graph which contain a root node at the top which branches into other nodes
• Binary trees are trees where each node has a maximum of two child nodes

Question 2

What are the ways to traverse a tree?

Answer 2

• Pre-order traversal: start from root node, then left subtree, then right subtree.
• In-order traversal: start from the left subtree, then root node, then right subtree.
• Post-order traversal: start from bottom of left subtree, then bottom of right subtree, then root node.
• Breadth-first traversal: start from root node, then all nodes directly beneath root node (left to right), then all nodes directly beneath each of these nodes (left to right), and repeat until all nodes are traversed.
• Breadth-first traversal: node-based method of finding the shortest path through the graph. Uses the queue data structure to store nodes one at a time before moving on to adjacent nodes.
• Depth-first traversal:

Question 3

What are abstract data types (ADTs)?

Answer 3

A logical description of how data is viewed and the operations that can be performed on it

Question 4

What are the differences between dynamic and static data structures? (Both are ADTs)

Answer 4

• Dynamic data structures are able to grow or shrink in size using a heap (a portion of memory from which space is allocated or de-allocated as needed); static data structures are fixed in size and do not use a heap
• Dynamic data structures use more memory and may cause an overflow error if it exceeds the maximum memory limit (which crashes the program); static data structures cannot grow, therefore they cannot require more memory than what is allocated in advance by the programmer

Question 5

What is a queue? (includes the common queue operations)

Answer 5

• A First In First Out (FIFO) data structure
• where new elements can only be added to the rear
• and elements can only be retrieved from the front
• includes a front and rear pointer which holds the indexes of the front and back of the queue

Common queue operations:
enQueue(item): add item to the back of the queue
deQueue(): return the item at the front of the queue
isEmpty(): check if the queue is empty
isFull(): check if the queue is full

Question 6

Explain the three types of queues.

Answer 6

Linear: jussa regular ol queue

Circular: when the queue is full, the rear pointer points to the front of the queue

Priority: a queue where higher priority items are at the front and lower priority items are at the back

Question 7

What is a stack?

Answer 7

• A Last In First Out data structure
• where data is added/removed from the top
• includes a pointer which holds the index of the top item of the stack