Algorithms for the main data structures Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

Are stacks FIFO or FILO?

A

FILO

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Which function adds an item to a stack?

A

Push

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Which function removes an element from a stack?

A

Pop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

Holds the location of the next available space in the queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

Peek

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

Points to the space containing the first item in the queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Peek

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a linked list?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a tree?

A
  • Formed from nodes and edges
  • Cannot contain cycles and aren’t directed
  • Useful as a data structure because they can be traversed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is meany by breadth-first?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly