Exam

Question 1

Definition of Stack?

Answer 1

Stack is a linear list in which insertions and deletions are allowed only at one end, called top

Question 2

Stack follows a LIFO, true or false

Answer 2

True

Question 3

Stack operations name and describe all stack operations:

Answer 3

stack() - creates a new empty stack
push(item) - adds a new item to top of stack
pop() - removes an item from top of stack
peek() - returns the top item from the stack but does not remove it
isEmpty() - checks to see if stack is empty or not
size() - returns number of items in stack

Question 4

Definition of Queues:

Answer 4

Queue is a linear list in which elements can be inserted only at one end called rear and deleted only at the other end called front.

Question 5

Queue follows a First-in-first-out (FIFO), true or false?

Answer 5

True

Question 6

Name and describe queue operations:

Answer 6

queue() - creates a new empty queue
enqueue() - adds a new item to the rear of the queue
dequeue() - removes the front item from the queue
isEmpty() - checks whether queue is empty
size() - returns number of items in queue

Question 7

What are two types of applications of Queues?

Answer 7

• Queues are widely used as waiting lists for a single shared resource like a printer
• Queues are used as a buffer in MP3 media players

Question 8

How is a graph defined?

What is a graph?

Answer 8

A graph is defined as: G=(V,E)

A graph is a set of vertices connected by edges.

Question 9

Define terms related to graphs:

Answer 9

Vertices - collections of data items (nodes)
Edges - Lines that connect one vertex to another
Adjacent - When two vertices are connected by an edge
Path - The structure of vertices
Connected graph - When there is a path between a pair of vertices

Question 10

Identify and describe the four types of graphs in data structures:

Answer 10

Directed graphs - A directed graph is when edges have direction from one vertex to another.

Undirected graphs - An directed graph is when edges have no direction from one vertex to another.

Weighted graphs - A weighted graph shows the length of the edges.

Unweighted graphs - An unweighted graph does not show the length of the edges.

Question 11

Describe a spanning tree and a minimum spanning tree:

Answer 11

Spanning tree - A spanning tree is an undirected graph where all edges are connected to vertices.

Minimum spanning tree - A minimum spanning tree is an undirected weighted graph that has a weight related to each edge to find a spanning tree that has a minimum total weight.

Question 12

What is a heap? And identify and describe the two types of heaps.

Answer 12

A heap is a special tree-based data structure in which the tree is a complete binary tree.

Max heap - In a max-heap the key present at the root node must be greatest amongst all of its children.

Min heap - In a min-heap the key present at the root node must be smaller than all of its children.

Question 13

Define an AVL tree.

Answer 13

An AVL tree can be defined as a height balanced binary search tree in which each node is associated with a balance factor which is calculated by subtracting the height of the left sub-tree by the height of the right sub-tree.

Question 14

An AVL tree is said to be balanced if balance factor of each node is between -1 to 1, true or false?

Answer 14

True

Question 15

What is the calculation for balance factor?

Answer 15

Balance factor (k) = height (left(k)) - height (right(k))

Question 16

Identify 5 applications of trees:

Answer 16

• Manipulate hierarchical data
• Make information easy to search
• Manipulate sorted lists of data
• Router algorithms
• Form of a multi-stage decision-making

Question 17

Identify and describe the four types of tree traversals.

Answer 17

Inorder (Left,Root,Right) - Inorder traversal will cause all nodes to be visited in ascending order.

Preorder (Root, Left Right) - Preorder traversal will visit the node sub tree first before going on to the left sub tree and the right sub-tree respectively.

Postorder (Left, Right, Root) - Postorder traversal firstly visits the left sub tree, then the right sub tree and lastly the root.

Breadth First or Level Order - A tree has different levels.

Question 18

Define a hash function and a hash table.

Answer 18

A hash function is a function that converts a given big phone number to a small practical integer value.

A hash table is an array that stores pointers to records corresponding to a given phone number.

Question 19

Identify and describe two ways to handle collisions.

Answer 19

Separate chaining - The idea is to make each cell of the hash table point to a linked lit of records that have the same has function value.

Open addressing - In open addressing all the elements are stored in the hash table itself, each table entry contains either a record or NIL.

Question 20

Identify 3 advantages and disadvantages of Separate chaining.

Answer 20

Advantages:

• Simple to implement
• Hash table never fills up
• Less sensitive to the hash function or load factors

Disadvantages:

• Cache performance of chaining is not good
• Wastage of space
• Uses extra space of links

Question 21

Identify 3 ways in which open addressing can be performed and compare them.

Answer 21

Linear probing - has the best cache performance but suffers from clustering. Yet it is easy to compute.

Quadratic probing - lies between the two terms of cache performance and clustering.

Double hashing - has poor cache performance but no clustering. Also requires more computation time.

Question 22

What is a Disjoint set.

Answer 22

A disjoint set is a collection of distinct dynamic sets {S1, S2…SK}. Each set is identified by a member of the set, called a representative.

Question 23

Identify and describe the 3 disjoint set operations.

Answer 23

MakeSet (x) - creates a new set where x is its only element and is therefore a representative of that set.

Union (x, y) - combines the two sets containing x and y into one new set.

Find (x) - returns the representative of the set containing x

Question 24

What is a disjoint set forest?

Answer 24

A disjoint set forest is a collection of trees. Each element points to its parent and the root of each tree is the representative of the set.

Question 25

What is union by rank?

Answer 25

Union by rank is when each node is associated with a rank. The rank is the approximate depth of the tree.

Question 26

What is path compression?

Answer 26

Path compression means that when we find x, we make all nodes encountered point directly to the representative element for x. Initially all elements have Rank 0.