DSA chapter wise year Question

4th semester
BIM Notes

Uni-1 Complexity analysis

  1. What is Big Oh(o) notation? 2007. 2009
  2. When is approximation algorithm used as problem solving approach? 2011
  3. Arrange the following expressions by their growth rate from slowest to fastest.  Logn,logn2,n!,n5 2014
  1. What is data structure?
  2. What is average case complexity of algorithm?

Unit-2 Linked List

  1.  What do you mean by linked list?  2002 , 2007,2011
  2.  Write benefits of linked list over array .2002,2007,2012
  3. What must be done before inserting an element at the beginning of array? 2011
  4. What is circular linked list? . 2009
  5. Write the variations of linked list. .  2012
  6. How many start pointers are required in doubly linked list? 2011
  7. What is doubly linked list? Write an algorithm or C-function to insert a node at end of doubly linked list.
  1. How doubly linked list differs from singly linked list?

 

  1. write a function for inserting node in to the list and deleting node from the list node . 2002
  2. Write function to implement to insert a node at beginning of double Link list. . 2009
  3. Write a function to count the total number of nodes in a linear linked list. 2002
  4. Write   function to print all the elements of the linked list. 2011
  5.  Write java function to delete first node of doubly linked list. .  2012
  6. Write java function to delete a node from the end of singly linked list. 2007

Unit-3  Stack & Queues

  1. Define stack . 2009 , 2012
  2. What do you mean by linked list of stack ?  2004
  3. Write down the main features of Stack. 2007
  4. List any three applications of stack. 2011
  5. Describe linked implementation of stack with suitable example? And write down its java  function. 2003
  6. What do you mean by Queue?  2002,2003
  7. How is circular queue more efficient than linear queue? 2004,2007, 2011, 2012,2014
  8. Define priority queue. . 2009
  9. What do you mean by Abstract Data Type? Define queue as an Abstract Data Type. 2003, 2007
  10. Write the application of priority queue. 2012
  11. What do you mean by absurd situation in a queue? 2011
  12. How circular queue is better than linear queue?  .
  13. Define infix and post-fix Expression. 2003
  1. Write the relationship between the stack and recursion. 2014
  2. Differentiate between stack and queue.
  3. What is skip list?

 

  1. What is postfix expression? Evaluate the given expression 2007

6  2  3  +  –  3  8  2  /  +  *  2  $  3  +

  1. Write the algorithm to evaluate postfix expression. Trace the algorithm for the following input: .  2012

ABCD- E/F*+; where A=3, B=5, C=1, D=6, E=4 and F=3.

  1. Use stack to convert the expression into postfix expression and evaluate the value of postfix expression where assume A = 1, B = 2, C = 3, D = 4, E = 5, F =6
    A+(B + C) * D$(E * F)

 

  1. write a function to implement linked list of stack . 2004
  2. .Write a program to implement the basic operations on stack. 2011
  3. Write function for joining two queue of size each 5 into stack. 2003
  4. Write a function to insert element in the queue. 2002,2003
  5. write a function to insert an element into a circular queue . 2004,2007
  6. Write function to perform insertion and deletion operations in a circular queue. 2011
  7. Write  function implement queue with insert, remove and display functions. 2009
  8. Write function to perform deletion operation in linear queue. .  2012
  9. Write a function for evaluating a postfix expression. 2003,2009
  10. Write function for joining two queue of size each 5 into stack. 2003
  11. Write a Java class to implement stack with push and pop functions.

 
Unit-4  Recursion

  1. Define recursive function. Write recursive function to generate Fibonacci resides. 2004
  2. Is it possible to convert all the recursions into iteration? 2011
  3. Differentiate between direct and indirect recursion. Write the recursive function to find the product of two numbers.  .  2012
  4. What is tail recursion?

Unit-6 Binary trees

  1. Write properties of binary tree.2009
  2. Define expression Tree. 2003 , 2007 , 2012
  3. Define binary tree.2002,2004, 2009
  4. What is the required condition to implement binary search? 2002
  5. Define binary tree, strictly binary tree. What are the methods of a traversing binary tree? Write a recursive function for one of the traversals. 2002
  6. Define Min heap and Max heap. 2011
  7. Define complete binary tree with examples. 2007
  8. What do you mean by AVL tree? 2007
  9. What is searching?2007
  10. What do you mean by height balance tree? . 2009
  11. Why binary search is better than sequential search? . 2009
  12. How AVL tree is constructed?  .  2012
  13. Distinguish between tree and forest. 2011
  14. What is Tree Traversal? 2011
  15.  Compare binary search and sequential search with respect to their time complexity.  2014
  16.  Differentiate between complete binary tree and almost complete binary tree. 2014
  17. What is heap tree? 2014,2015 Model
  18. What will be the result if we perform the post order traversal of an expression tree? 2014
  19. What do you mean by Minimum Spanning Tree (MST)? Write Kruskal’s algorithm to construct MST with suitable example. 2014
  20. What is splaying?
  1. What are the advantages of B tree? Explain procedure to insert element in a B tree.
  2. Make expression tree to the expression: AB-C+DEF-+$. Then write the post order traversal for above tree. 2003
  3. write a function to construct a binary tree and construct a binary tree from the following given node { 12,8,14, 7 ,19, 4, 28, 2 , 30}  2004
  4. Use binary search algorithm for finding position of 67 in the given  list    34   44   56   77   78   89    91   92   93  94   95 2004
  5. construct a binary tree the following given node { 10,8,12,7,9,11,18} and also write perorder , in order and post order traversal. 2004
  6. Create an expression tree of given infix notation.   ((A*B) + C – D/E + (f*G))$H 2007
  7. Write an  function to delete a node from Binary tree. 2007
  8. Create binary search tree for following list of elements 45, 30, 29, 88, 1, 1, 12, 7, 2, 6, 10 and display the In order traversal of that tree. . 2009
  9. Function to create binary search tree and binary tree traversal in postorder. . 2009
  10. Construct expression tree of given expression A * B – C. Evaluate post fixed expression using stack (AB / C +) where A = 10, B = 5 and C = 2. . 2009
  11. Convert the given expression to postfix (A+B*C)$(A+B)*C).
  12. Construct a Max heap from the following data given in order: 1, 5, 3, 10, 2, 6, 9, 11. 2011
  13. Write an algorithm to search an item using binary search technique. Search item 16 in the following data set using binary search algorithm: 111, 13, 14, 15, 17, 18, 19, 23, 29. 2011
  14. Define forest. Write C function or algorithm to insert new node in binary tree. .  2012
  15. Write an algorithm of list traversal. 2007 Write binary search algorithm. Search an element 15 from the given list of data using binary search algorithm. 10,15,28,31,33,35,44,45,80,84,96,100 2007
  16. Write an function for inorder and preorder  traversal of Binary Tree. 2011
  17. What is the advantage of AVL tree over binary search tree? Construct an AVL tree from the given set of data: 3, 3, 1, 4, 5, 6, 7, 16, 15, 9,14  2014
  18. Write a function in Java to insert a node in Binary Search tree.

 
Unit -7 Graphs

  1. Discuss the Breadth first traversal in Graph. Also write an algorithm for the traversal. 2002
  2. Discuss the graph traversal method with example. Write C function or algorithm to find shortest path from A to B.  .  2012
  3. What do you mean by nesting depth and parenthesis count? 2007
  4. Differentiate between graph and tree.  2012
  5. Define  graph as an Abstract Data Types.
  6. What is adjacency matrix of graph?
  7. Write Depth first traversal for graph.
  9. Unit-8  Sorting
  1. What do you mean by sorting?  2002 , 2003
  2. What is the difference Insertion sort and Selection sort? In which situation insertion sort will perform better than selection sort. 2004, 2007
  3. Compare Selection and Bubble sort according to their complexities. 2012
  4. Differentiate between Sorting and Searching. 2007, 2012
  5. What is the Big Oh notation of quick sort? 2011
  6. Why is internal sorting faster than external sorting? 2011
  7. What is the difference between Quick sort and Merge sort? 2007
  8. Write an algorithm for implementing selection sort. Why selection sort is efficient then insertion sort in case of larger list of element. 2002
  9. What is merging? 2011
  10. Explain quick sorting with an example.

 

  1. Write function for insertion-sort. 2003,2015 Model
  2. Write function to implement a selection sort .
  3. Trace selection sort algorithm for following data .{66, 29, 32, 59, 12}  2004
  4. Trace bubble sort algorithm for the following data: 32 51 27 85 66 23 13 57 99 11   2003
  5. Sort following list of elements using merge sort: 11, 22, 33, 4, 5, 6, 8, 99, 9, 15. Show the tracing of algorithm. . 2009
  6. Sort the following data using Quick sort algorithm. 48, 37,  57,  92,  86, 2007
  7. Write function for quick sort.
  8. Write an algorithm for merge sort and sort the following data using merge sort algorithm: 11, 22, 33, 4, 5, 6, 8, 99, 9, 15. 2011
  9. Trace Quick sort algorithm for the data: 10, 71, 89, 37, 67, 29, 54, 24 2012

Unit-9 Hashing

  1. What do you mean by bucket Addressing?
  1. Write a function in Java to delete element from a hash table.

 
Other Question

  1. When is collision resolution technique used?
  2. Write a C function or algorithm to solve the TOH problem for n disks.
  3. How do you decide to choose using specific algorithm from various available algorithms to do same thing?
  4. What is linear probing?
  5. Compare available searching techniques.
  6. What is greedy approach?
  7. Why do we need the concept of collision resolution?
  8. Write algorithm to solve problem of Tower of Hanoi.