Algorithms for the Main Data Structures

Question 1

Examples of data structures.

Answer 1

-Stacks -Queues
-Linked Lists -Trees

Question 2

What are the traversal types of trees?

Answer 2

Depth First (post-order)
Breadth first

Question 3

What data structure is a stack an example of?

Answer 3

First in, Last out (FILO)

Question 4

What is the single pointer that keeps track of the top of the stack called?

Answer 4

Top pointer

Question 5

What are top pointers initialized at?

Answer 5

-1

Question 6

What is the 1st position in the stack

Answer 6

0

Question 7

PsuedoCode to check size of stack

Answer 7

size()

Question 8

PsuedoCode to check if the stack is empty?

Answer 8

isEmpty()

Question 9

PsuedoCode to return the top element in the stack (but not remove it)

Answer 9

peek()

Question 10

PsuedoCode to add to stack

Answer 10

push(element)

Question 11

PsuedoCode to remove the top element from the stack and return the removed element

Answer 11

pop()

Question 12

Example of PsuedoCode size() in a stack

Answer 12

size()
return top +1

Question 13

Example of PsuedoCode isEmpty() in a stack

Answer 13

isEmpty()
If top < 0:
return True
else:
return False
endif

Question 14

Example of PsuedoCode peek() in a stack

Answer 14

peek()
if isEmpty():
return error
else:
return A[top]
endif

Question 15

Example of PsuedoCode push(element) in a stack

Answer 15

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

Question 16

Example of PsuedoCode pop() in a stack

Answer 16

pop()
if isEmpty():
return error
else:
toRemove = A[top]
A[top] = “”
top -= 1
return toReturn
endif

Question 17

What type of data structure are queues

Answer 17

First in, First out (FIFO)

Question 18

What are stacks and queues represented as?

Answer 18

Arrays

Question 19

What are the pointers called in a queue?

Answer 19

Front and back pointer

Question 20

What does the front pointer hold?

Answer 20

The position of the first element

Question 21

What does the back pointer store?

Answer 21

The next available space

Question 22

PsuedoCode to check size of a queue

Answer 22

size()

Question 23

PsuedoCode to check if a queue is empty

Answer 23

isEmpty()

Question 24

PsuedoCode to check the front element of a queue (but not remove)

Answer 24

peek()

Question 25

PsuedoCode to add to the queue

Answer 25

enqueue(element)

Question 26

PsuedoCode to remove front element from the queue and return removed elements

Answer 26

dequeue()

Question 27

Example of PsuedoCode size() in a queue

Answer 27

size() return back - front

Question 28

Example of PsuedoCode isEmpty() in a queue

Answer 28

isEmpty() if front == back : return True else : return False endif

Question 29

Example of PsuedoCode peek() in a queue

Answer 29

peek() return A[front]

Question 30

Example of PsuedoCode enqueue(element) in a queue

Answer 30

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

Question 31

Example of PsuedoCode dequeue() in a queue

Answer 31

dequeue() if isEmpty() : return error else : toDequeue = A[Front] A[front] = "" front += 1 return toDequeue

Question 32

What are linked lists composed of?

Answer 32

Nodes

Question 33

What does each node have in a linked list?

Answer 33

A pointer node to the next item in the list

Question 34

What is the first and last item in a linked list referred to as?

Answer 34

Head and tail

Question 35

Searching a linked list is performed with what type of search?

Answer 35

Linear

Question 36

How does a linear search, search

Answer 36

It checks each item in a lost one by one from the start until the target value is found or the end of the list is found

Question 37

What are trees formed from

Answer 37

Nodes and edges

Question 38

State 2 facts about trees

Answer 38

- Trees do not have cycles - Trees are not directed

Question 39

Why are trees a useful data structure?

Answer 39

Because they can be traversed

Question 40

What are the 2 traversal types in a tree?

Answer 40

- Depth First (post order) - Breadth first

Question 41

Explain depth first, and what abstract data structure is used to store the data in order.

Answer 41

Search goes as far down into the tree as possible, before backtracking. A stack.

Question 42

Explain breadth first, and what abstract data structure is used to store the data in order.

Answer 42

Starting from the left and visiting everything on the same row then back to the right and down