Algorithms for the main data structures

Question 1

Are stacks FIFO or FILO?

Answer 1

FILO

Question 2

Which function adds an item to a stack?

Answer 2

Push

Question 3

Which function removes an element from a stack?

Answer 3

Pop

Question 4

What is the significance of the back pointer in the array representation of a queue?

Answer 4

Holds the location of the next available space in the queue

Question 5

Which function returns an item at the front of a queue without removing it?

Answer 5

Peek

Question 6

What is the purpose of the front pointer in the array representation of a queue?

Answer 6

Points to the space containing the first item in the queue

Question 7

What value is the top pointer initialised to in the array representation of a stack?

Answer 7

-1

Question 8

Give pseudocode for the two functions which add new elements to stacks and queues

Answer 8

Stacks:
push(element)
top += 1
A[top] = element

Queues:
enqueue(element)
A[back] = element
back += 1

Question 9

Which function returns the item at the top of a stack without removing it?

Answer 9

Peek

Question 10

What is a linked list?

Answer 10

• Composed of nodes, each of which has a pointer to the next item in the list
• First item in a list is referred to as the head and the last as the tail

Question 11

What is a tree?

Answer 11

• Formed from nodes and edges
• Cannot contain cycles and aren’t directed
• Useful as a data structure because they can be traversed

Question 12

What is meant by depth first (post-order) traversal?

Answer 12

• Depth first search goes as far down into the tree as possible before backtracking
• The algorithm uses a stack and goes to the left child node of the current node when it can
• If there is no left child then the algorithm goes to the right child.
• If there are no child nodes, the algorithm visits the current node, outputting the value of the node before backtracking to the next node on the stack and moving right

Question 13

What is meany by breadth-first?

Answer 13

• Starting from the left, breadth-first visits all children of the start node
• The algorithm then visits all nodes directly connected to each of those nodes in turn, continuing until every node has been visited (uses a queue)
• E.g. 5,3,8,2,4

Question 14

What is meant by pre/post/in-order?

Answer 14

• Post-order: line passes to the right of the nodes
• Pre-order: line passes to the left of the nodes
• In-order: line passes under the nodes