2.3.1 Algorithms for the Main Data Structure Flashcards

1
Q

What is a stack?

A
  • First in, last out data structure
  • Implemented as array and use single pointer
  • Points to element at top of stack
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the stack operations?

A
  • size() - check size
  • isEpty() - check if empty
  • peek()- return top element
  • push(element)- add to stack
  • pop() - remove and return top element
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are queues?

A
  • First in first out data structure
  • Represented as array
  • Two pointers
  • One holds position of first element, the other the next available space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the queue operations?

A
  • size()- check size
  • isEmpty()- check if empty
  • peek()- return front element
  • enqueue(element) - add to the queue
  • dequeue - remove and return front element
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are linked lists?

A
  • Abstract, dynamic data structure to hold ordered data from different locations
  • Composed of nodes each of which has a pointer to the next item in the list
  • First item in the head
  • Last item is the tail
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How do you insert an item into a linked list?

A
  • Add item to next free space
  • Follow pointers from start until you find a node greater than the item
  • Change pointer of previous node to point to item
  • Change the pointer of the item to point to the next node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are trees?

A
  • Formed from nodes and edges
  • Cannot contain cycles
  • Undirected
  • Useful dta structure as can be traveresed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the types of tree traversal?

A
  • Depth first (post-order) traversal
  • Breadth first
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How do you perform post-order traversal?

A
  • Draw line starting to left of root
  • Draw a bubble aroyund the tree
  • Output as the line passes to the right of a node
  • Implemented using a stack
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How do you perform breadth first traversal?

A
  • Visits all children of the start node
  • VIsits all nodes directly connected to each of those nodes in turn
  • Implemented using a queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly