Algorithms for the Main Data Structures Flashcards
1
Q
What is a Stack
A
A Data Strcuture that operates on a first in, last out bias
2
Q
What are the Stack Operations
A
3
Q
What is a Queue
A
A datastructure that opperates on a First in First out Bais
4
Q
What are the Queue Operations
A
5
Q
What is a Linked List
A
- A linked list is composed of nodes, each of which has a pointer to the next item in the list
- If a node is referred to as N, the next node can be accessed using N.next
- The first item in a list is referred to as the head and the last as the tail
6
Q
What are the Two types of Tree Traverses
A
- Depth first (Same as Post Order)
- Breadth first
7
Q
What is a Depth first 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
8
Q
What is a Breadth first Traversal
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
9
Q
Describe the pseudocode for a Queue Enqueue
A
if(isFull() = True then
Print “The queue is full”
Else
rear = (rear+1) % maxSize
arrQueue[rear] = newValue
size = size + 1
Endif
End function
10
Q
Describe the pseudocode for a Queue Dequeue
A
int item
if(isEmpty()) then
Print “The queue is empty”
Else
item = arrQueue[front]
front = (front+1) % maxSize
size = size -1
Endif
End function
