SYBCS : Data structures and algorithms 2 : Semester Exam

Chapter 1 : Tree

Q. Define Heap.

- Heap is a data structure which uses tree based data structure where the is complete binary tree.

Q. Define complete binary tree.

- A complete binary tree is a tree where all the levels of tree have maximum number of possible nodes except the last level. 

Q. Define degree of the tree.

- Degree of the tree is maximum degree of any node in a tree. 

Q. List tree traversal methods.

- There are three tree traversal methods:

1. Preorder

2. Postorder

3. Inorder

Q. Define node of the tree.

- Each data element of tree is called as the node of tree.

Q. What is height balance tree?

- Height balance tree is a tree where the height of left subtree is equal to height of right subtree.

Q. How many nodes in a tree have no ancestors?

- There is only one node in tree without ancestors, root.

Chapter 2: Efficient Search Trees

Q. Define balance factor.

- It is a numerical value associated with each node in the tree, indicating the difference in height between the node's left and right subtrees.

Q. Define spanning tree.

- Spanning tree is a graph which is connected with minimum number of possible edges.

2 mark

Q. Define the following terms:

1. Height to tree.

- It the the maximum number of edges from root to leaves. 

2. Forest

- A group of trees form a forest.

3. Siblings of tree.

- Nodes with common parents are siblings of tree.

Q. What is skewed binary tree.

- Binary tree which is either left subtree or right subtree is called a skewed binary tree.

Chapter 3: Graph

1 mark

---Q. Define critical path.

- a critical path can be defined as the longest path in a directed acyclic graph (DAG) that represents dependencies between tasks.

Q. Define acyclic graph.

- It is a type of graph which does not contain any cycle or loops.

Q. Define Multigraph.

- It is a type of graph which allows multiple edges betwen same pair of vertices.

Q. List any methods of representing graphs.

- Methods of representing graphs re:

1) Adjacency Matrix

2) Adjacency List

3) Inverse Adjacency List

4) Adjacency multi-list representation

-Q. Define complete graph.

- It is a type of graph in which every vertex in a graph is adjacent to every other vertex.

Q. What is weighted graph.

- It is a type of graph in which each edge is assigned a numerical value or weight.

 Q. Define in-degree & out-degree of vertex.

- In-Degree: It represents number of incoming edges to that vertex. 

Out-Degree: It represents number of outgoing edges from that vertex.

Q. Define Degree of the vertex.

- It refers to the number of edges that are connected or incident to that vertex.

Q. State any two applications of graph.

- Applications of graph are:

1) They are used to model and analyze social networks.

2) They can solve path finding and optimization problems.

Chapter 4: Hash Table

1 mark

Q. Define Bucket.

- Bucket is a unit of storage. In hash table data structure, it refers to a specific slot in hash table's array where data can be stored.

Q. What do you mean by rehashing.

- It is a process in which all the keys in the original hash table are rehashed to a new hash table of larger size. It's default size if twice that of original hash table.

2 mark

Q. Write any two properties of hash function

- Properties of hash function are:

1) Easy to understand and simple to computer.

2) Number of collisions should be less.

3) It uniformly distributes data across entire set of possible hash values.