Data Structures and Applications - IAT 2 Question Bank
Sub Code: BCS304 Branch: ISE Sem/Sec: III / A,B,C
Module -3
1. What is Linked List? Explain Different types of Linked List with neat diagram.
2. Define sparse matrix. For the given sparse matrix, give the linked list representation:
3. Write C functions for the following
i) Search an element in the singly linked list.
ii) Concatenation of two singly linked list
iii) Inverting a Singly Linked List
4. Write C Functions for the following Doubly Linked list
i) Inserting a node at the beginning of a DLL.
ii) Deleting a node at the end of a DLL.
5. Define Binary Tree. Explain the Types of Binary Tree with a neat diagram.
6. Write recursive C functions for in-order, pre-order and post-order traversals of a binary
tree. Also, find all the traversals for the given tree.
7. Define the Threaded binary tree. Construct Threaded binary for the following Tree:
Module -4
8. Define Binary Search tree. Construct a binary search tree (BST) for the following elements:
100, 85, 45, 55, 120, 20, 70, 90, 115, 65, 130, 145. Traverse using in-order, pre-order, and
post-order traversal techniques. Write recursive C functions for the same.
9. Define selection tree. Construct min winner tree for the runs of a game given below. Each
run consists of values of players. Find the first 5 winners.
10. Define Forest. Transform the given forest into a Binary tree and traverse using inorder,
preorder and postorder traversal.
11. Define the Disjoint set. Consider the tree created by the weighted union function on
the sequence of unions: union(0,1), union(2,3), union(4,5), union(6,7), union(0,2),
union(4,6), and union(0,4). Process the simple find and collapsing find on eight finds
and compare which find is efficient.
12. Construct a binary tree from the Post-order and In-order sequence given below In-order:
GDHBAEICF Post-order: GHDBIEFCA.
13. Convert Below Tree into Binary Tree
14. Define Graph. Explain the adjacency matrix and adjacency list representation for a below
Graph.
15. Explain in detail Elementary Graph operations. Implement Graph Traversal with
suitable example.
16. Design an algorithm to traverse a graph using Depth First Search (DFS). Apply DFS for
the graph given below.
Module -5
17. Define hashing. Explain different hashing functions with examples.
18. Explain Static Hashing and Dynamic Hashing in detail.
19. What is collision? What are the methods to resolve collision? Explain linear probing with
an example.
20. What is chained hashing? Discuss its pros and cons. Construct the hash table to insert the
keys: 7, 24, 18, 52, 36, 54, 11, 23 in a chained hash table of 9 memory locations. Use h(k) =
k mod m.
21. What is dynamic hashing? Explain the following techniques with examples: i) Dynamic
hashing using directories ii) Directory less dynamic hashing
22. Define the leftist tree. Give its declaration in C. Check whether the given binary tree is a
leftist tree or not. Explain your answer.
23. Explain Priority Queue With a help of an Example
24. Define min Leftist tree. Meld the given min leftist trees.
25. Write a Short Note on i) Leftist Tree ii)Optimal Binary Search Tree
26. Difference between Height Based and Weight based Leftist tree.