Scribd
Upload
10 views2 pages

Data Structures: Trees, Graphs, and Hashing

The document outlines an assignment for a Data Structures and Applications course, focusing on various concepts such as binary trees, graph operations, and hashing techniques. It includes questions on tree types, traversal methods, and the importance of data structures like queues and stacks in algorithms. Additionally, it covers performance considerations in large-scale systems and the mechanics of different hashing methods.

Uploaded by

vishaks2722
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
10 views2 pages

Data Structures: Trees, Graphs, and Hashing

The document outlines an assignment for a Data Structures and Applications course, focusing on various concepts such as binary trees, graph operations, and hashing techniques. It includes questions on tree types, traversal methods, and the importance of data structures like queues and stacks in algorithms. Additionally, it covers performance considerations in large-scale systems and the mechanics of different hashing methods.

Uploaded by

vishaks2722
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Assignment-2

Subject: Data Structures and Applications

Semester: 3rd

1. What are the key differences between Full, Complete, and Perfect binary trees?

2. How do you implement an iterative in-order traversal without using recursion?

3. Why is a queue data structure necessary for Level-order (BFS) traversal?

4. Define the differences between Single-threaded and Double-threaded binary trees.

5. What is the role of a "tag bit" (boolean variable) in the node structure of a threaded
binary tree?

6. Why are insertion and deletion operations significantly more complex in a TBT compared
to a standard binary tree?

7. Compare a standard Binary Search Tree (BST) with a Threaded Binary Tree in terms of
search efficiency and traversal complexity

8. Why is maintaining a balanced tree (like an AVL or Red-Black tree) critical for performance
in large-scale systems?

9. How do you calculate the Diameter of a binary tree or find the Lowest Common Ancestor
(LCA) of two specific nodes?

10. List the typical operations of a Graph ADT. How do addVertex, addEdge, and
removeVertex maintain the integrity of the graph?

11. Explain the role of the exist(u, v) operation. What does it return for weighted vs.
unweighted graphs?

12. Define the degree(u), inDegree(u), and outDegree(u) operations. In what type of graph is
inDegree distinct from outDegree?

13. What primary data structure is used to implement BFS, and why is it essential for
exploring levels?

14. Explain how BFS can be used to find the shortest path in an unweighted graph.

15. Describe the use of a Stack (or recursion) in DFS. How does it differ from BFS in its
exploration path?

16. Explain the concepts of Back Edges and Forward Edges discovered during a DFS traversal.

17. Explain the core logic of hashing. How does a hash function map a search key to a
specific data bucket?
18. Describe the difference between Linear Probing, Quadratic Probing, and Double Hashing.
Which one suffers most from primary clustering?

19. Explain how Extendible Hashing uses a directory of pointers and "global/local depth" to
manage growing data.

20. How does Linear Hashing handle bucket overflows without requiring an additional level
of indirection (directory)?

You might also like