Algorithms for the Main Data Structures

Question 1

What is a Stack

Answer 1

A Data Strcuture that operates on a first in, last out bias

Question 2

What are the Stack Operations

Answer 2

Question 3

What is a Queue

Answer 3

A datastructure that opperates on a First in First out Bais

Question 4

What are the Queue Operations

Answer 4

Question 5

What is a Linked List

Answer 5

• 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

Question 6

What are the Two types of Tree Traverses

Answer 6

• Depth first (Same as Post Order)
• Breadth first

Question 7

What is a Depth first Traversal

Answer 7

• 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

Question 8

What is a Breadth first Traversal

Answer 8

• 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

Question 9

Describe the pseudocode for a Queue Enqueue

Answer 9

if(isFull() = True then

Print “The queue is full”

Else

rear = (rear+1) % maxSize

arrQueue[rear] = newValue

size = size + 1

Endif

End function

Question 10

Describe the pseudocode for a Queue Dequeue

Answer 10

int item

if(isEmpty()) then

Print “The queue is empty”

Else

item = arrQueue[front]

front = (front+1) % maxSize

size = size -1

Endif

End function