Data Structures Algorithms Final

Front 1

What is Polymorphism?

Back 1

Permits parent class to dynamically take behaviour of descendent class

Front 2

What does Operator Overload do?

Back 2

Allows for classes of methods (i.e. a Fraction class) to be added/multiplied

public static Fraction operator+ (Fraction a, Fraction b)

Front 3

What does the virtual keyword mean?

Back 3

virtual allows the method to be overwritten by a descendant class

Front 4

What does the static keyword mean?

Back 4

static means that the method or class belongs to the TYPE and not the INSTANCE of a class. A static member cannot be referenced through an instance. Instead it is referenced through the type name

Front 5

What does the override keyword mean?

Back 5

The override modifier is required to extend or modify the abstract or virtual implementation of an inherited method property

Front 6

What is an Interface?

Back 6

An interface contains only the signatures of methods properties

Front 7

a class can only have...

Back 7

one parent class

Front 8

a child class exhibits AT LEAST...

Back 8

the same behaviour as the parent class

Front 9

A class can implement multiple...

Back 9

interfaces

Front 10

A class MUST implement all methods defined in the

Back 10

interface

Front 11

A class may defer implementing the body of an abstract method in the parent class

Back 11

Therefore, the descendant class is also abstract

Front 12

What is the difference between deep and shallow copying?

Back 12

Shallow copying only copies the reference to an object. Deep copying copies the object and operates on it.

With shallow copying, if the original object changes, that is reflected in the reference. Not so for deep copies.

Front 13

Common interface for all linear data structures

Back 13

IContainer

Front 14

What is Stack topIndex when the stack is empty?

Back 14

-1

Front 15

What are the two groups of types in C#

Back 15

Value types and Reference types

Front 16

Of the two groups of types in C#, which does the Object belongs to?

Back 16

Objects belong to Reference types

Front 17

What group of types does the Array class belong to?

Back 17

the Reference type

Front 18

How does the Stack work? What are its main methods?

Back 18

LIFO: last in, first out

OR

FILO: first in, last out

Methods:

void Push(T item): adds item to top of stack

void Pop(): grabs item from top of stack

T Top: returns top item of stack

Front 19

How can a Stack be used to implement a postfix notation of calculator

Back 19

Given: "3 5 8 * +"

When you meet the first operator: "*"

Take the two prior numbers and apply operator to them: "5 * 8"

Then continue..

Front 20

How does a Queue work? What are its main methods?

Back 20

FIFO: first in, first out

OR

LILO: last in, last out

Methods:

void Add(T item): add item to back of queue

void Remove(): remove item from front of queue

T Front: returns item from front of queue

Front 21

Hash Table Public Methods

Back 21

Full

Empty

Deleted

Front 22

What is a Hash Table

Back 22

Data structure that maps keys to values

Front 23

How does the hashing of a Hash Table work?

Back 23

Distributes key/value pairs across an array of buckets

hash = hashfunc(key)

index = hash % array_size

`hash` is independent of array size, and is reduced to an index (number between 0 and array_size - 1) using modulo operator

Front 24

An example of Hash Table indexing

Back 24

The hashfunc returns a value for a given key:

hashfunc('b') = 9

hashfunc('deaf') = 108

hashfunc('bed') = 44

Given an array of 7 buckets, we calculate the index with:

hashfunc('b') % 7 = 2

hashfunc('deaf') % 7 = 3

hashfunc('bed') % 7 = 2

Then, these items are inserted at the index given from the modulo operator.

Front 25

Hash Table Linear Probing / Collisions:

Back 25

Given:

hashfunc('b') % 7 = 2

hashfunc('deaf') % 7 = 3

hashfunc('bed') % 7 = 2

We insert 'b' at index 2 and 'deaf' at index 3. When we attempt to insert 'bed' at index 2 have a collision, the hash table detects this and then checks index 3, another collision, then it checks index 4 and finds an empty spot, inserting 'bed' at index 4.

Final order:

[][]['b']['deaf']['bed'][][][]

'bed' has 2 collisions.

Front 26

Main problem with Linear Collision Resolution

Back 26

Primary clustering, this will result in many keys being stored in close proximity (clustered).

Front 27

Describe Quadratic Probing

Back 27

Must ensure table size is a PRIME NUMBER

Table must be less than or equal to 50% full

Given a table size of 7, once we reach 3 items. We must resize the array to the next prime number, 17 and rehash everything to new indices.

When a value detects a collision, a new index is found using the following method:

1^2, 2^2, 3^2, 4^2...n^2

This prevents clustering found in linear probing

Front 28

Why is does the hash table use modulo with prime numbers?

Back 28

when you're repeating over a set space, you're going to provide an even distribution across your hash space.

Front 29

What is the difference between abstract and virtual classes

Back 29

Abstract classes have no method body

Virtual classes can be defined and overridden in a descendant class

Front 30

list the methods for IContainer

Back 30

//Resets to Empty

void MakeEmpty();

//Returns if empty

bool Empty();

//Returns size

int Size();

Front 31

What is a binary heap?

Back 31

A tree-based data structure where each row is filled out from left to right. The goal is to fully saturate all rows.

Front 32

What are the two types of binary heaps?

Back 32

Max Heap: value of each node is less than or equal to its parent (largest value at root)

Min Heap: value of each node is greater than or equal to its parent (smallest value at root)

Front 33

Given a binary heap stored in an array and an element at position n, how do you find its parent?

Back 33

n / 2

Front 34

Given a binary heap stored in an array and an element at position n, how do you find its left child?

Back 34

2 * n

Front 35

Given a binary heap stored in an array and an element at position n, how do you find its right child?

Back 35

2 * n + 1

Front 36

All methods of a _____ are implicitly virtual, public and abstract

Back 36

interface

Front 37

True or false: A class with no constructor cannot be instantiated

Back 37

False

Front 38

First 10 prime numbers (for hash tables)

Back 38

2, 3, 5, 7, 11, 13, 17, 19, 23 and 29

Front 39

How to calculate modulo with a calculator

Back 39

Given to numbers (A and B) use this formula:

1. divide A by B,

2. subtract the remaining whole number

3. multiply the remaining decimal by B

7 mod 2:

7 / 2 = 3.5

3.5 - 3 = 0.5

0.5 * 2 = 1

Front 40

What is the IComparable interface?

Back 40

Defines a generalized comparison method for classes

Front 41

How should you implement the IComparable interface?

Back 41

Generally, return an integer (1, 0, -1) to show the sorted order of two instances of the same class

-1 = this.object precedes object being compared to

0 = equal

1 = this.object is greater than object being compared to

public int CompareTo(Item other)

{

if (this.Number < other.Number)

return -1;

else if (this.Number == other.Number)

return 0;

else if (this.Number > other.Number)

return 1;

}

Front 42

How does Binary Heaps Insert/Percolate Up work?

Back 42

(This is down assuming a min heap implementation)

1. Add item to bottom of heap, in right-most location

2. Compare item with parent, swap if it has higher priority (i.e. less than its parent)

3. Continue until it does not have higher priority than its parent

Front 43

How does Binary Heap array implementation work

Back 43

Front 44

How does Binary Heaps Delete/Percolate Down work?

Back 44

(assuming max heap)

1. Delete root node

2. Take element at bottom, right-most position and place it at root

3. Compare new root with children, swap if out of order

4. Continue until correct order

Front 45

How does a Fix Heap/Heap Sort work with the Binary Heap?

Back 45

It is a recursive Delete and Percolate down operation to return a sorted array.

1. Delete root and place in array

2. Perform Percolate Down to find next root in correct order

3. Continue steps 1 and 2 until heap is empty

4. Return the sorted array

Front 46

What is a binary tree

Back 46

Simple tree data structure that is either:

a) empty

b) a node with a left and right binary tree

Front 47

How does pre-order traversal work?

Back 47

1. Root

2. Descend left subtree

3. Descend right subtree

Front 48

How does post-order traversal work?

Back 48

1. Ascend left subtree

2. Ascend right subtree

3. Root

Front 49

How does in-order traversal work?

Back 49

1. Descend left subtree

2. Root

3. Descend right subtree

Front 50

What is the definition of a Binary Search Tree?

Back 50

All values in the left subtree are less than the root value

All values in the right subtree are greater than the root value

Front 51

How to perform insert in a Binary Search Tree?

Back 51

1. Start at root

2. If new node smaller than current node, go left. Otherwise go right

3. If we reach a node with no children (a leaf node), insert new node to the left if smaller, insert new node to the right if larger

Front 52

What are the three cases for Deletion in a Binary Search Tree?

Back 52

1. If the node has no children, remove it

2. If the node has 1 child, remove the node and replace it with its child

3. If the node has 2 children, find the smallest node in the right subtree and replace deleted node with this node.

Front 53

What are the properties of a Red Black Tree?

Back 53

It is a self-balancing Binary Search Tree

1. Every node is Red or Black

2. Root node is Black

3. All leaf (nil) nodes are Black

4. If a node is Red, both of its children are Black

5. The path from any node to a descendant nil node MUST have the same number of black nodes (this is called the Black Height)

All operations (Insert, Delete etc) are performed like it is a Binary Search Tree, after operation is complete, you then rebalance the tree to satisfy the properties above.

Front 54

Red Black Tree Balancing: What is Case 1?

Back 54

Case: Uncle of the new node is Red

Solution: Recolor!

-Grandparent becomes Red

-Parent and Uncle become Black

Front 55

Red Black Tree Balancing: What is Case 2?

Back 55

Case: Uncle is Black, Parent is a Right Child

Solution: Left rotate around parent of new node

This then leads to Case 3 for more rebalancing

Front 56

Red Black Tree Balancing: What is Case 3?

Back 56

Case: Uncle is Black, New Node is a Right Child

Solution:

-Parent and Grandparent of new node become Black

-Right rotate around Grandparent

Front 57

What are the properties of a Splay Tree?

Back 57

Its a Binary Search Tree with the additional property that recently added nodes are moved to the root.

Front 58

Concerning splay trees, what is a zig step?

Back 58

When the parent is root (last step), rotate tree around parent to have targeted node at root.

Front 59

Concerning splay trees, what is a zig-zig step?

Back 59

When parent is not root and both the parent and the parent and the targeted node are both left or right children.

Rotate around grandparent to bring targeted node to root.

Front 60

Concerning splay trees, what is a zig-zag step?

Back 60

When parent is not root. The targeted node is a right child and parent is a left child or vice versa.

Rotate around the grandparent to bring targeted node to the root.

Front 61

How do you Insert a node into a Splay Tree?

Back 61

Binary Search Tree insertion and then splay the newly added node to the root.

Front 62

How do you Delete a node from a Splay Tree?

Back 62

Rotate the node to be deleted to root and then remove it.

Front 63

Concerning an Adjacency Matrix, what is the maximum number of edges?

Back 63

n^2 where n is the number of vertices.

Front 64

Concerning the Adjacency Matrix, what is the notation for an edge.

Back 64

Edge[i, j]

i = row

j = column

Front 65

Advantages and Disadvantages of Adjacency Matrix

Back 65

Advantages: easy to tell if an edge exists between two nodes

Disadvantages: Consumes a lot of memory

Front 66

In general, what are the steps for Binary Search?

Back 66

*assume array is ordered lowest to highest

1. Given a target, X

2. Find the midpoint of the array with equation: (low + high) / 2

3. If X == midpoint, return true

4. If X < midpoint, recursive call to binary search on the subarray of the midpoint to the last element

5. If X > midpoint, recursive call to binary search on the subarray of the first element to the midpoint

Front 67

What is the difference between Depth First and Breadth First search?

Back 67

Depth First Search will start at Root and traverse along one edge (typically the left edge) until it reaches a leaf node

Breadth First Search will descend a tree-like graph each level at a time.

Front 68

Breadth First Search Example (number is order explored)

Back 68

Front 69

Depth First Search Example (number is order explored)

Back 69

Front 70

Depth First Search Pseudocode

Back 70

func DFS(Graph, vertex):

vertex = discovered

for all edges adjacent to vertex:

if adj vertex is not discovered:

DFS(Graph, adj)

Front 71

Breadth First Search Pseudocode

Back 71

func BFS(Graph, vertex):

create queue Q

mark vertex as visited

store vertex in Q

while Q is not empty:

remove head w from Q

mark and enqueue all unvisited neighbours of w