Data Structures and Applications Question bank(3rd sem)

 Question bank for 3rd sem CS&E

MODULE 1: Introduction

Classification of Data structures:

SN	QUESTIONS	YEAR	MARKS
1	Define data structures. Classify the data structures.	2017-18	08

Data Structure Operations:

SN	QUESTIONS	YEAR	MARKS
1	Explain the operations of data structures.	2018-19	08
2	What is an array? How array are declarations and implemented in C	2016-17	07
3	What are self-referential structures? Explain with Example.	2017-18	06
4	Differentiate between structures and unions.	2017-18	04
5	Define data structures. List and explain the different operations that can be carried on arrays.	2019-20	10

Array of structure:

SN	QUESTIONS	YEAR	MARKS
1	Explain with Example; a) insertion and b) deletion in an array.	2017-18	08

    

Structures And Function:

SN	QUESTIONS	YEAR	MARKS
1	Difference between structures and function with examples.	2016-17	08

Pointers:

SN	QUESTIONS	YEAR	MARKS
1	Define Pointers. List the advantages of pointers over arrays	2019-20	04
2	What are pointer variables? How to Declare a pointer variable	2014-15	05

Dynamically Allocated Arrays:

SN	QUESTIONS	YEAR	MARKS
1	List and explain any 4 functions supported in C for dynamic memory allocation with examples.	2017-18	08
2	Define dynamic memory allocation. List and write with Explanation the syntax of dynamic memory allocation functions	2019-20	06
3	Explain the dynamic memory allocation function in detail.	2018-19	08

MODULE 2: Stacks

Definition

SN	QUESTIONS	YEAR	MARKS
1	Define stack. Write the procedure for two basic operations associated with stack.	Jan-19, July-19	5
2	Define stack data structure and give the ADT for the stack. Write C functions for push() and pop() operations.	July-19	8

Representation

SN	QUESTIONS	YEAR	MARKS
1
2

Operations

SN	QUESTIONS	YEAR	MARKS
1	Define stack. Implement push and pop operations for stack using arrays.	Dec-15, Jan-14	8
2	Define stack. Give the C implementation of push and pop functions. Include check for empty and full conditions of stack.	Dec-11,Jan-15,July-17,19	8
3	Define stack. List the operations on stack.
4	Write a C program demonstrating the various stack operations, including cases for overflow and underflow of STACKS.	June-18, July-18	8

Stack using Dynamic Arrays

SN	QUESTIONS	YEAR	MARKS
1	Write the algorithm to implement a stack using a dynamic array whose initial capacity is 1 and array doubling is usual to increase the stack’s capacity (that is dynamically reallocated twice the memory) whenever an element is added to a full stack. Implement the operations-push, pop and display.	June-17	8

Infix to Postfix Conversion

SN	QUESTIONS	YEAR	MARKS
1	Convert A*B+C$ postformatm	May-11	4
2	Write postfix form of the rt A*B+C $ postfix form following expression using stack i) A$B*C-D+E/F/(G+H) ii) A-B/(C*D$E)	Dec-15	6
3	Convert the following infix expression into postfix expression using stack: i) a*(b+c)*d ii)(a+b)*d+e/(f+a*d)+c	July-15	8
4	Write postfix form of the following expression i) (a+b)*d+e/(f+a*d)+c ii) ((a/(b-c+d))*(e-a)*c) iii) a/b-c+d*e-a*c	Jan-14 July-17	6 4
5	Write the algorithm to convert infix to postfix expression and apply the same to convert the following expression from infix to postfix: i) (a*b)+c/d ii) (((a/b)-c)+(d*e))-(a*c)	June-12	12
6	Write the postfix form of the following expression: i) ((6+(3-2)*4) ↑ 5+7) ii) A$B$C=D	Jun-18	8
7	Write the postfix from of the following expression: A+((B*C-D/E ↑F)*G)*H	Dec-18	5
8	Convert the given infix expression to postfix and prefix expression: i) (c+b)*d+e/(f+g*h)+i ii) ((a/(b-c+d))*/(e-f)*g)	June-19	6

Evaluation of Postfix Expression

SN	QUESTIONS	YEAR	MARKS
1	Write a C function to evaluate a postfix expression and apply the same to evaluate AB+CDE-*/ A=5, B=6, C=4, D=3, E=7	July-15	7
2	Convert the infix expression a/b-c+d*e-a*c into postfix expression. Write a function to evaluate that postfix expression and trace that for given data a=6, b=3, c=1,d=2, e=4.	Jul-13, 17	6
3	Convert the infix expression	Jul-17, Jun-19	8,6
4	Write an algorithm to evaluate a postfix expression. Evaluate the following postfix expression abc+de/ where a=5, b=6, c=2, d=12, e=4.	Jun-18	6
5	Write a C function to evaluate a postfix expression	Dec-11,Jun-18	8,2
6	Illustrate with examples how to insert a node at the beginning, INSERT a node at intermediate position, DELETE a node with a given value.	June-18	9
7	Write an algorithm for evaluation of postfix expression. Trace the same for the expression abfede*+ac*+ where a=b, b=3, d=2, e=4.	July-19	6

MODULE 2: Recursion

SN	QUESTIONS	YEAR	MARKS
1	Write down the algorithm for the Athckerm function. Evaluate A(1,2) using ACKERMANN function.	June-18	4
2	Write the algorithm to implement a stack using a dynamic array whose initial capacity is 1 and array doubling is used to increase the stack’s capacity (that is dynamically reallocated twice the memory) whenever an element is added to a full stack .Implement the operations-push,, pop and display.	Jan-17	8
3	Write algorithm of the tower of Hanoi.	Jan-17	4
4	Define recursion. Write recursive program for (i) Factorial of a number (ii) Tower of Hanoi	Jan-18	8
5	Define recursion. Write C recursive functions for the following: (i) Tower of Hanoi (ii) Factorial of a given number.	Jan-19, July-19	10
6	Write a note on the Ackerman function.	Jan-19	5

Operations

SN	QUESTIONS	YEAR	MARKS
1	Define queues. Implement Q insert and Q delete function for queues using arrays	Jan-18	8
2	Define queues. Write Q INSERT and Q DELETE procedures for queues using arrays	Jan-19	10

Circular Queue

SN	QUESTIONS	YEAR	MARKS
1	What are the advantages of circular queue over linear queue? Write insert and delete functions for circular implementation of queues.	Dec-14	8, 5
2	List the disadvantages of linear queue and explain how it is solved in circular queue. Give the algorithm to implement a circular queue with suitable examples.	Jan-17	8
3	Write C functions for insert cq() and delete cq() operations on a circular queue	Jul-19	5

Circular Queues using Dynamic Arrays 

SN	QUESTIONS	YEAR	MARKS
1
2

Priority Queue

SN	QUESTIONS	YEAR	MARKS
1	With a neat diagram explain ONE-WAY list representation of a priority queue	June-18	6
2	Write a short note on priority queues	Jan-19	5

Double Ended Queue

SN	QUESTIONS	YEAR	MARKS
1	What is an input restricted double ended queue? Implement the same with the supporting functions.	July-17	8

Applications of Queues

SN	QUESTIONS	YEAR	MARKS
1
2

A Mazing Problem 

SN	QUESTIONS	YEAR	MARKS
1	Describe how you could model a maze where 0 represents open paths and 1 represents barriers. What moves are permitted in the matrix model?/ Provide an example MAZE together with its allowable moves and table of moves.	July-18	8

Multiple Stacks

SN	QUESTIONS	YEAR	MARKS
1	Explain in detail multiple stacks, with relevant functions in C.	July-19	8

MODULE 3: Linked  List

Operations

SN	QUESTION	YEAR	MARKS
1	Mention types of operations in Linked List and Explain ?	Jan-19	10
2	Write the following algorithm for singly Linked List Inserting ITEM as the first node of list VJ Deleting the node with the given ITEM of information	Jan-19	10

Types of Linked List

SN	QUESTION	YEAR	MARKS
1	Mention types of Linked List and Explain	Jan-13	10
2	Explain different types of Linked List with diagram	Jan-15	10
3	What is a Linked List ? Explain the different types of Linked List with diagram	Jan-13	10

Singly Linked List

SN	QUESTION	YEAR	MARKS
1	Mention and Explain Singly linked list with an Example ?	July-17, 18, 19 Jan-17	8
2	Give the node structure to create a singly Linked List of integers and write functions to perform the following : Create a list Assume the list contains 3 nodes with data 10,20,30.Insert a mode with data 40 at the end of the list Insert a node with data 50 between the nodes having data values 10 and 20 .Display the singly Linked List	Jan-17	8
3	Write the functions for a singly linked list with integer data to search an element in the list ?	Jan-17 July-18	8
4	Write a function for singly linked lists with integer data to search an element in the list that is unsorted and a list that is sorted	July-18	8
5	Illustrate with examples how to insert a node at the beginning INSERT a node at intermediate position DELETE a node with a give value	July-18	9
6	Define linked lists .Explain in detail the primitive operations performed on Supply Linked List(SLL).List the different types of linked lists	July-19	12

Doubly Linked List

SN	QUESTIONS	YEAR	MARKS
1	Explain Doubly Linked List operations with Example?	July-13, 14, 18, 19 Dec-11, 15 June-19	8
2	Write C functions for the following operations on Doubly Linked List (DLL) Concatenation of two DLL Search the DLL for the given key element	June-19	8
3	Write a note on doubly linked list.How it is different from singly linked list	Dec-15	5
4	What is the advantage of doubly linked lists over singly linked lists ? Illustrate with an example	July-14 Jan-17	4
5	Write a short note 0n-Doubly Linked List	July-13	3
6	Describe the doubly linked list with advantages and disadvantages. Write a C function to delete a node from a doubly linked list. Ptr is a pointer to the node to be deleted. Assume that there are node on either side of the node to be deleted	Dec-11	8
7	List out the difference between the doubly linked list and singly linked list .Illustrate with example the following operations on a doubly Linked List: Inserting a node at the beginning Inserting at the intermediate position Deletion of a node with a given value Search a key element	July-17, 18 June-18	10 8

Circular Linked List

SN	QUESTION	YEAR	MARKS
1	Write a C function to insert a node at front and rear end in a circular linked list	July-15 Jan-13	10
2	Explain the following with an example program? Creation of circular linked list Display of circular linked list Insertion of circular linked list Deletion of any node Searching a node from circular linked list	July-15 Jan-13	10

Header Linked List

SN	QUESTION	YEAR	MARKS
1	Write a note on the header linked list. Explain the widely used header list with diagram	July-18 Jan-19	5

Linked Implementation Of Stack

SN	QUESTION	YEAR	MARKS
1	Explain implementation of linked list in stack with example	Jun-12 July-19	8
2	Write a C Program to implement the two primitive operations on stack using dynamic memory allocation	June-12	8
3	Write a C program to implement linked stacks	July-19	8

Linked Implementation of Queue

SN	QUESTION	YEAR	MARKS
1	Explain the implementation of linked lists in a queue?	Dec-15 Jan-15 June-12	10
2	Write a C function to implement the insert and delete operations on a queue using linked list	Dec-15	8
3	Define linked list .Write a C program to implement the insert and delete operations on queue using linked list	Jan-15 June-12	10

Polynomial Manipulation

SN	QUESTION	YEAR	MARKS
1	Brief explanation on polynomial manipulation	Dec-15 July-13, 14, 19 June-12, 19 Jan-19	10
2	Write the node structure show would you store the given polynomial a and b in linked list .Write a C function for for adding 2 polynomials using linked list	Dec-15 July-13	8 6
3	Write the node structure for linked representation of polynomial.Explain the algorithm to add two polynomials represented using linked list	July-14 Jan-17,19	8

Sparse Matrix Representation with Multilinked Data Structure

SN	QUESTION	YEAR	MARKS
1	Explain Sparse Matrix representation with Multilinked Data Structure	July-13,19 June-19 Jan-17,18, 19	5
2	For the given sparse matrix write the diagrammatic linked list representation	June-19	5
3	For the given spare matrix write the diagrammatic linked list representation	Jan-17	6
4	Define sparse matrix .Given sparse matrix representation of linked list for given matrix	Jan-18 June-19	8 4
5	Write a note on-linked list of sparse matrix	July-13	3

Programming Examples

SN	QUESTION	YEAR	MARKS
1	Write the example program for the following Length of list Merging of two list	July-14,15,18,19 Jan-19	5
2	Write a C function to concatenate two singly linked list	July-15 July-14 June-18	5 4 8
3	Write the functions to perform the following Inverting a single linked list Concatenating the singly linked list Finding the length of a circular linked list	Dec-18	10
4	Write a C function to reverse the given singly linked list	July-15 July-14	5 4
5	Write C function to perform the following Reversing a singly linked list Concatenating singly linked list Finding the length of the list	July-17 Jan-19	6
6	Write a C program using pointers to Concatenate two strings. Reverse a string.	July-19	6

                                        

MODULE 5: Graphs

Definition

SN	QUESTIONS	YEAR	MARKS
1	Define graphs. Explain in detail about directed graphs.	Jan - 19	10

Terminologies

SN	QUESTIONS	YEAR	MARKS
2	Define the terminologies with examples for graph data structure (i) Graph (ii) Multigraph (iii) Complete graph.	June - 19, july -19	6

Matrix and Adjacency List Representation of Graph

SN	QUESTIONS	YEAR	MARKS
3	What do you mean by adjacency matrix and adjacency list ? Give the adjacency matrix and adjacency list of the following graph :	July - 17	8
4	Give the adjacency matrix and adjacency list representation for the graph shown in following figure	July - 13	5
5	Define graphs. Give an adjacency matrix and adjacency list for the given weighted graph in the following graph.	Jan - 18	8
6	Give the adjacency matrix and adjacency list representation for the weighted graph given in figure below.	June - 19	6
7	What is a graph? Give the matrix and adjacency list representation of graphs.	Jan - 17	8

Elementary Graph Operations

SN	QUESTIONS	YEAR	MARKS

Traversal Methods

SN	QUESTIONS	YEAR	MARKS
8	What are the methods used for traversing a graph? Explain any one with an example.	July - 17, Jan - 18	8
9	Write an algorithm for BFS and DFS graph traversal methods.	Jan - 19, July - 19	10 8

MODULE 5: Sorting and Searching

Insertion Sort

SN	QUESTIONS	YEAR	MARKS
1	Write a C function for insertion sort. Sort the following list using insertion sort : 50, 30, 10, 70, 40, 20, 60.	July - 17	8
2	Write an algorithm for an insertion sort. Also discuss the complexity of insertion sort.	Jan - 19	10

Radix Sort

SN	QUESTIONS	YEAR	MARKS
3	Write an algorithm for Radix sort.	Jan - 18	8

Address Calculation Sort

SN	QUESTIONS	YEAR	MARKS
4	Write an algorithm for bubble sort. Trace the algorithm for the data: 30, 20, 10, 40, 80, 60, 70.	Jan - 17	8

MODULE 5: Hashing 

Hash Table Organization

SN	QUESTIONS	YEAR	MARKS
5	Explain Hashing in detail.	Jan - 18	8

Hash Functions

SN	QUESTIONS	YEAR	MARKS
6	Define Hash function. What do you mean by Perfect Hash Function?	July - 18	8
7	Write a short note on Hashing. Explain any 3 popular HASH functions.	July - 18	8

Static and Dynamic Hashing

SN	QUESTIONS	YEAR	MARKS
8	Explain in detail about Static and Dynamic hashing.	Jan - 19	10

Concept of Collision

SN	QUESTIONS	YEAR	MARKS
9	Explain Hashing and Collision. What are methods used to resolve collisions?	July - 19	8

Collision Resolution Techniques

SN	QUESTIONS	YEAR	MARKS
10	Discuss in brief the linear probing collision resolution technique. What are the disadvantages of this technique? How could it be overcome?	Jan - 17	5
11	Define Hash function. Explain Collision resolution strategies.	Jan - 17	5
12	Explain open addressing and chaining used to handle overflows in hashing.	Jan - 17	5
13	Explain directoryless dynamic hashing.	Jan - 17	5
14	What is Collision? What are the methods to resolve collisions? Explain linear probing with an example.	July - 17	8
15	Explain Hashing and Collision. What are methods used to resolve collisions?	July - 19	8

MODULE 5: File Structures

File Organization

SN	QUESTIONS	YEAR	MARKS
1	Write a short note on Indexed sequential file.	Jan - 17	6
2	Briefly explain basic operations that can be performed on a file, Explain indexed sequential file organization.	Jan - 17	6
3	What do you understand by the term File organization ? Briefly summarize any 3 widely used file organizations techniques.	July - 18	8
4	What are the basic operations that can be performed on a file ? List the methods used for file organization.	July - 19	4

SN	Module 1	REPs	COs
1	Define dynamic memory allocation. List and write the syntax with explanation of dynamic memory allocating functions.	8	CO1
2	Write the Knuth Morris Pratt pattern matching algorithm and apply the same to search the pattern ‘abcdabcy’ in the text:’abcxabcdabxabcdabedabcy’	4	CO2
3	Define data structure . List and explain the different operations that can be carried on arrays.	3	CO1
4	Write a C program to i)                Comparing strings ii)             Concatenate two strings .	3	CO2
5	Explain the classification of data structures. What are the primitive operations performed on them?	3	CO1
6	Define pointers . How to declare and initialize pointers , explain with example.List the advantages of pointers over arrays.	2	CO2
7	What is structure? How it is different from arrays. Explain types of structure declaration with eg.	2	CO2
8	Differentiate between structure and union.	2	CO2
9	Give the ADT for sparse matrices. Express the given sparse matrix the triplet form and find its transpose	2	CO2
10	Consider given two polynomials A(x)= 4x15 +3x4+5  and B(x)=x4+10x2+1 Represent the polynomials using an array of pointers.	2	CO2
11	Define strings. List and explain any 5 operation with example	1	CO2
12	Write a  bubble sort algorithm.	1	CO2
13	Explain with example  i)insertion                                      ii)deletion in an array.	1	CO2
14	Is it possible to store the contents of an array into points? Justify your opinion and with suitable C statements.	1	CO2
15	List and explain in detail, three types of structures used to store the strings .	1	CO2
16	Explain about the representation of  a 2-dimensional array in memory.	1	CO2
17	Write a c program to concatenate Fname and Lname of a person without using a library function.	1	CO2
18	What is an algorithm? Explain the criteria that an algorithm  must satisfy.	1	CO2
19	What do you mean by pattern matching? Let P and T be strings with the lengths R and S respectively and stored as an array with one character per element. Write a pattern matching algorithm that finds index P in T. Also discuss the algorithm.	1	CO2
20	Write a c program with appropriate structure definition and variable declaration to read and display information about 5 employees using nested structure.	1	CO2

SN	Module 2	REPs	COs
1	Define a stack.. Explain the different operations performed on stacks using c functions. Show them using diagrammatic representation.	7	CO3
2	Convert the following infix expression into postfix expression using stacks i)                ((H*((((A+((B+C)*D))*F)*G)*E))+J) ii)             A$B*C-D+E|F|(G+H) iii)           A-B|(C*D$E) iv)   A+(B*C-D/E F)*G)*H v)              (a+b)*d+e/(f+g*h)+i vi)            ((a/(b-c+d))*(c-f)*g) vii)          (a+b)*d+e/(f+a*d)+c viii)   ((a/(b-c+d))*(e-a)*c) ix)            A$B$C*D                                                       (any two)	7	CO3
3	Define recursion. What are the properties of recursive procedure? Write the recursive function for the following i)                Factorial of a number ii)              Tower of Honoi.	5	CO2
4	Write the algorithm to evaluate the postfix expression . apply the same for the given postfix expressions i)                ABC-D*E$F and assume A=6,B=3,C=2,d=5,E=1 and F=7. ii)             ab/c-de*tac*t where a=6,b=3,c=1,d=2,e=4. iii)           Abc+*de/- where a=5,b=6,c=2,d=12,e=4.		CO3
5	Write a note on Ackerman’s function.	3	CO2
6	Write a note on dequeue and priority queue.	3	CO3
7	Write the advantages of circular queue over ordinary queue. Write the program to simulate the working of a circular queue of integers using an array. Provide following operations i)              Insert ii)         Delete iii)   Display	3	CO3
8	Write the QINSERT and QDELETE procedure for queue using arrays.	3	CO3
9	Differentiate between recursion and iteration process	2	CO2
10	Write the algorithm to convert a parenthesized infix to postfix. Apply the algorithm and show the contents of stacks during conversion of expression (A+B*C)*((D+E_F)/J).	1	CO3
11	Explain in detail  multiple stacks, with relevant functions in C.	1	CO3
12	Define queue. List different types of queues. How do you overcome by specifying limitations on the required c statements and diagrammatic representation using an example.	1	CO3
13	Write a c function for i)                Adding n natural odd numbers ii)             Adding n natural even numbers.	1	CO2
14	Evalute the following postfix expression by showing the contents of stacks 5 4 6 + * 4 9 3 / + *	1	CO3
15	Outline the algorithm for infix to prefix expression. Using the same algorithm convert the following infix to prefix  ((H*((((A+((B+C)*D))*F)*G)*E))+J).	1	CO3
16	What is an input restricted in a double ended queue? Implement the same with the supporting functions.	1	CO3
17	Implementation of a circular queue using dynamically allocated arrays.	1	CO3
18	Let A and B be nonnegative integers . suppose a function GCD is recursively defined as follows GCD(A, B)=GCD(B,A) if A<B                =A if B=0                =GCD(B,MOD(A,B)) otherwise Here MOD(A,B) read as A Modulo B. Evaluate GCD(20,28).	1	CO2

SN	Module 3	REPs	COs
1	Write a c function to add two polynomials. Write a node structure linked list representation of polynomials. Show the linked list representation for two polynomials. POLY 1 : 5x2+4x+2 POLY 2: 3x2+2x+5	7	CO3
2	Differentiate between singly linked list and doubly linked list.	4	CO3
3	Write a note on the header linked list . explain the widely used header list with diagrams. Write the c function for i)                Inverting a SLL ii)             Concatenating two SLL iii)           Finding the length of a circular list.	4	CO3
4	Write a C function for the following operations on doubly linked list i)     Insertion at the beginning . ii)      Insertion at the end. iii)     Deletion at the beginning . iv)      Deletion at the end.	3	CO3
5	Write a C statement for addition and deletion of a node on DLL.	2	CO3
6	Write a C function for the following operations on circular linked list i)                Insertion at the beginning . ii)             Insertion at the end. iii)           Deletion at the beginning . iv)     Deletion at the end	2	CO3
7	Write a C function for the following operations on linked list i)                Insertion at the beginning . ii)             Insertion at the end. iii)           Deletion at the beginning . iv)            Deletion at the end.	2	CO3
8	What is a linked list? Explain the types of linked list with a neat diagram and also discuss the operations performed on linked list.	2	CO3
9	Write a c function for i)                Concatenation of 2 DLL ii)             Search an element in DLL	2	CO3
10	Give the node structure to create a linked list of integers and write a C function to perform the following i)            Create a three node list with data 10 ,20 and 30. ii)           Insert a node with data value 15 in between the                               nodes  having data values 10 and 20. iii)           Delete the node whose data is 20. iv)            Display the resulting singly linked list.	2	CO5
11	Write a note on the header linked list . Explain the widely used header linked list with examples.	2	CO3
12	State the advantages of DLL over SLL.	1	CO3
13	Describe the DLL with advantages  and disadvantages. Write a c function to delete a node from circular DLL with header node.	1	CO3
14	Write and explain how you implement the operations of stacks using SLL with the help of c statements.	1	CO3
15	Write a c program to implement limited stacks	1	CO3
16	Write a C statement, explain how you create a node , add and delete on a singly linked list with proper message where each node is containing the details of employee in the form of Empid, Empname, Empaddr and Empsalary as data fields.	1	CO5
17	Write a C function of SLL with integer data to search an element in the list that is unsorted and a list that is sorted.	1	CO3
18	Illustrate with examples how to insert a node at beginning , insert node at an intermediate position, delete node at a given value.	1	CO3

SN	Module 4	REPs	COs
1	Define Binary tree with an example. Write a recursive routine to traverse the given tree using inorder,preorder and postorder.	4	CO3
2	What is a tree? With suitable example,  Define: (i)Binary tree  (ii)Level of the binary tree  (iii)Complete binary tree  (iv)Degree of the tree  (v)Strictly binary tree (vi)Skewed binary tree (vii)Almost complete binary tree	4	CO3
3	Given the following traversal, draw a binary tree (i)Inorder: 4 2 5 1 6 7 3 8   Postorder: 4 5 2 6 7 8 3 1 (ii)Preorder: A B C E I F J D G H K L      Inorder: E I C F J B G D K H L A (iii) Inorder: D J G B H E A F K I C         Postorder: J G D H E B K I F C A (iv) Preorder: B C A E D G H F I        Inorder: A B C D E F G H I  .	4	CO5
4	Write the routines for:  (i) Copying binary trees  (ii) Testing for equality of binary trees	3	CO2
5	Define BST. Write the recursive search and iterative search algorithm for a binary search tree.	3	CO2
6	What are the advantages of the threaded binary tree over a binary tree? Explain the construction of the threaded binary tree for 10,20,30,40 and 50.	2	CO5
7	For the given data, draw a binary search tree and show the array and linked list representation of the same: 100,84,45,55,110,20,70,65	2	CO5
8	Define tree data structure.Represent the below given tree in figure using  (i)Linked list representation  (ii) Left child right sibling representation (iii)Degree-two or Binary tree representation.	2	CO5
9	Write recursive C function for inorder,preorder and postorder traversals of binary tree. Give 3 traversals for the binary tree shown in figure. Also find the depth of the tree.	2	CO3
10	Write a short note on threaded binary trees and state the rules to construct a threaded binary tree.	2	CO3
11	Define Binary Search Tree for the following input : 14 15 4 9 7 18 3 5 16 20 17 9 Give recursive search function to search an element in the tree.	1	CO5
12	Define a threaded binary tree. List its advantages and disadvantages. Draw the one way threading and two way threading of the following binary tree.	1	CO5
13	Write function to insert an element in a binary search tree.	1	CO2
14	Define a binary tree. Explain how you construct and add a NODE to the binary tree using c Statements. Also explain how you represent a binary tree using arrays.	1	CO3
15	Define binary tree traversal method. List and explain the different binary tree traversal methods along with C-functions.	1	CO3
16	Define expression tree. Using a C function, explain how you construct an expression tree. Construct an expression tree for: a+b*c/f^g-h.	1	CO5
17	Find the INORDER,PREORDER and POSTORDER for the following	1	CO5
18	.Write a diagrammatic explanation, explain how you create and construct a BST. Also write a C function for the same.	1	CO2
19	Define expression tree. For a tree given, in below figure traverse the tree using in-order, preorder and postorder traversals.	1	CO5
20	Define Binary Search Tree(BST). Construct BST for the element step-by-step, 100,85,45,55,110,20,70,65,113,145,132,96.	1	CO5
21	Write an algorithm for deleting a key element from BST.	1	CO2
22	List the rules to construct the threads. Write the routines for inorder traversal of a threaded binary tree.	1	CO3
23	Define a complete binary tree. Illustrate with examples.	1	CO3
24	Write a function to insert an item into an ordered binary search tree (duplicate items are not allowed).	1	CO2
25	Draw a binary tree for the following expression 3+4*(7-6)/4+3. Traverse the above generated tree using inorder, preorder and postorder. Also write a function in C for each one.(	1	CO5

SN	Module 5	REPs	COs
1	Write an algorithm for breadth first search and depth first search.	3	CO2
2	What is a collision? What are the methods to resolve collisions? Explain linear probing with an example.	2	CO3
3	What are the methods used for traversing a graph? Explain any one with an example. And write the C function for the same.	2	CO3
4	Write an algorithm for Insertion sort. Apply Insertion sort showing the various passes to sort the array A, where A = [77,33,44,11,88,22,66,55].	2	CO3
5	Explain in detail about Static and dynamic hashing.	2	CO3
6	What are the basic operations that can be performed on a file? List the methods used for file organisation ( any two). Explain indexed sequential file organisation.	2	CO3
7	Define file. List basic file operations. Explain any four operations with Syntax and example.	2	CO3
8	What is a graph? Give the Matrix and adjacent a list representation of graphs.	2	CO3
9	Write an algorithm for bubble sort. Trace the algorithm for the data: 30,20,10,40,80,60,70.	2	CO5
10	Explain open addressing and chaining used to handle overflow in hashing.	1	CO3
11	Explain directory less dynamic hashing	1	CO3
12	Briefly explain basic operations that can be performed on a file. Explain indexed sequential file organisation.	2	CO3
13	Define graphs. Write the difference between graphs and trees. For the given graph show the adjacency matrix and adjacency list representation of the graph.	1	CO5
14	Define graphs. Give adjacency matrix and adjacency linked list for the given weighted graph in the figure	1	CO5
15	Write an algorithm for radix sort.	1	CO2
16	State and explain WARSHALL'S algorithm with an example.	1	CO2
17	Write a short note on hashing. Explain any three popular Hash Function.	2	CO3
18	What do you understand about the term file organisation? Briefly summarise any three widely used file organisation techniques.	1	CO3
19	Write an algorithm for Insertion sort. Also discuss about the complexity of Insertion sort	1	CO2
20	Arrange the following elements in ascending order using RADIX SORT 151,60,875,342,12,477,689,128,15	1	CO5
21	Define the terminologies with examples for graph data structure.  i)Graph  ii) Multigraph iii) Complete graph  iv) Weighted graph  v) Self loop vi) Parallel edge	1	CO3
22	Give the adjacency Matrix and adjacency list representation for the weighted graph given Fig	1	CO5
23	Right address calculation sort algorithm. Sort Z, A, P, B, Q, I, J, K using the address calculation sort algorithm.	1	CO2
24	Give the adjacency matrix, Incidence Matrix and linked list representation of the following undirected graph:	1	CO5
25	Give the adjacency matrix and adjacency list representation for the weighted graph given in fig	1	CO5
26	Find the resultants of the types of graph traversal methods .	1	CO5