Exam Flashcards
Definition of Stack?
Stack is a linear list in which insertions and deletions are allowed only at one end, called top
Stack follows a LIFO, true or false
True
Stack operations name and describe all stack operations:
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
Definition of Queues:
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.
Queue follows a First-in-first-out (FIFO), true or false?
True
Name and describe queue operations:
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
What are two types of applications of Queues?
- 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
How is a graph defined?
What is a graph?
A graph is defined as: G=(V,E)
A graph is a set of vertices connected by edges.
Define terms related to graphs:
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
Identify and describe the four types of graphs in data structures:
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.
Describe a spanning tree and a minimum spanning tree:
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.
What is a heap? And identify and describe the two types of heaps.
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.
Define an AVL tree.
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.
An AVL tree is said to be balanced if balance factor of each node is between -1 to 1, true or false?
True
What is the calculation for balance factor?
Balance factor (k) = height (left(k)) - height (right(k))
Identify 5 applications of trees:
- Manipulate hierarchical data
- Make information easy to search
- Manipulate sorted lists of data
- Router algorithms
- Form of a multi-stage decision-making
Identify and describe the four types of tree traversals.
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.
Define a hash function and a hash table.
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.
Identify and describe two ways to handle collisions.
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.
Identify 3 advantages and disadvantages of Separate chaining.
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
Identify 3 ways in which open addressing can be performed and compare them.
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.
What is a Disjoint set.
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.
Identify and describe the 3 disjoint set operations.
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
What is a disjoint set forest?
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.
