2.3.1 - Algorithms (Data Structures)

Question 1

What would be output using a breadth-first traversal on the following tree?

Answer 1

Italy, France, Spain, Austria, Germany, Norway

Outputs the root node first

Question 2

What would be output using a depth-first traversal on the following tree?

Answer 2

Austria, Germany, France, Norway, Spain, Italy

Root node is always last in depth-first (post-order)

Question 3

Describe the steps involved in a breadth-first traversal + state the data structure used

Answer 3

Uses a queue data structure to perform the traversal

1. Visit root node
2. Visit all direct children
3. Visit all children of first child
4. Repeat three points for each child visited

Question 4

Describe the steps involved in a depth-first traversal + state the data structure used

Answer 4

Uses a stack data structure to perform the traversal

1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the root node
4. Repeat three points for each child visited

Question 5

In what situation would a depth-first traversal be chosen over a breadth-first traversal?

Answer 5

Depth

• Requires less memory than breadth first search.
• Quicker than breadth if you are looking at deep parts of tree

Breadth

• Is more efficient when the data searched for is closer to the root.

Question 6

Keywords to describe a binary (search) tree

Answer 6

• Ordered Data Structure
• Child Node
• Parent Node
• Root Node
• Leaf Node
• Sub Tree
• Edge / Branch

Question 7

Draw this Binary Search Tree

Answer 7

Question 8

What is the purpose of the root and free pointers in a binary search tree?

Answer 8

Root Pointer - Points to where the tree starts (root node)

Free Pointer - Points to where the next piece of data would be added in the array

Question 9

Key words to describe a tree (multi-branch)

Answer 9

• No restriction on the number of child nodes per parent
• Un-Ordered Data Structure
• Child Node
• Parent Node
• Leaf Node
• Sub Tree
• Edge / Branch

Question 10

Write the pseudocode to push an item to a stack

Answer 10

Question 11

Write the pseudocode to pop an item to a stack

Answer 11

Question 12

Keywords to describe a queue

Answer 12

• Dynamic Data Structure
• Enqueue
• Dequeue
• First in First Out (FIFO)
• Peek
• Front Pointer
• Rear Pointer
• Circular / Non-Circular

Question 13

Write the pseudocode to dequeue an item to a queue

Answer 13

Question 14

Write the pseudocode to enqueue an item to a queue

Answer 14

Question 15

Describe the purpose of pointers in this queue

Answer 15

headPointer - Where the data will be removed from (dequeued)

tailPointer - Where the data will be added to (enqueued)

Question 16

Give examples of where stacks and queues are used in computers

Answer 16

Queues - Used in print queues – New print jobs are added to the end of the queue. Jobs are processed from the front of the queue

Stack - Internet History – When you visit a site the last site is pushed to the stack. When you click back the last item is popped from the stack, and then loaded.

Question 17

Keywords to describe a linked list

Answer 17

• Dynamic Data Structure
• Node (made up of a pointer and a piece of data)
• Non-Contiguous
• Start Pointer
• Null

Question 18

What are the pros and cons of a linked list?

Answer 18

(+) You can store multiple pointers without reordering the linked list

(+) Using pointers means that the linked list does not need to be store contiguously in memory

(-) Inefficient for searching as you must go through each node one at a time following the pointers (WHILE loop until ‘null’ is reached).

Question 19

What would the pointers be to output this linked list in alphabetical order?

Answer 19

Start Pointer = 2

Question 20

What types of edges can be used in a graph?

Answer 20

• Directed
• Undirected
• Weighted
• Unweighted

Edges in a directed graph only go in one direction. Undirected edges can go in both directions.

Question 21

How do you differentiate between a tree and a graph?

Answer 21

• Trees cannot have cycles - graphs can have cycles
• Trees have a root node - graphs do not have a root node
• Trees have a hierarchy - graphs have no hierarchy
• Trees are always undirected - graphs can be directed
• Trees are always connected - graphs can be connected or disconnected

Question 22

Keywords to describe a stack

Answer 22

• Dynamic Data Structure
• Pop
• Push
• First in Last Out (LIFO)
• Peek
• Top Pointer