Data Structures

 Important Questions

Subject Code - 3130702

1.      Differentiate between linear and nonlinear data structures.  OR Briefly explain various linear and non-linear data structures along with their applications.

2.      What is an ordered tree? What is forest?

      3.      Explain the structure of indexed sequential file.

      4.      How open addressing can be used for collision resolution?

      5.      Explain structure of sequential file. Explain processing in sequential file.

      6.      Give definitions:    (1)   Graph     (2)  Adjacent nodes

      7.      What is priority queue? Explain the array representation of priority queue.

      8.      Explain outdegree and indegree.

      9.      Explain Depth First Search operation Breadth First Search Operation.  

            OR

Explain Depth First Search and Breadth First Search in graphs with an example. 

OR

List advantages and disadvantages of Breadth First Search and Depth First Search. 

OR

Explain BFS and DFS in detail.

      10.  Write and explain application of queu

11.  Discuss the variations of a queue.

      12.  Write a program to implement queue and check for boundary conditions.

      13.  Write a program to implement a circularly linked list.

      14.  List the advantages of a doubly linked list over singly linked list.

      15.  What is a header node? Explain its importance.

      16.  Write an algorithm to count the number of nodes in a singly circularly linked list.

      17.  Explain the working of the Kruskal’s algorithm.

      18.  Write the algorithm for binary search and find its complexity.

      19.  Define the following terms with respect to a graph: Node, Edge, Path.

      20.  Discuss different representations of a graph.

      21.  What is the complexity of the quick sort algorithm on sorted data? Justify your answer.

      22.  Explain the difference between insertion sort and selection sort with an example. What is the                  time complexity of these algorithms? How?

      23.  Explain hash functions. OR    List the qualities of a good hash function. OR

What is hashing? What are the qualities of a good hash function? Explain any two hash functions in detail.

      24.  How directed tree can be represented?

      25.  How following hash functions work?  (1) The midsquare method   (2) Digit analysis

     26.  How primitive data type floating point is stored in computer?

      27.  How many null branches a binary tree possesses?

      28.  What is the difference between serial and sequential processing? How a record can be deleted in             sequential file?

      29.  What is the advantage of circular queue? OR Explain the concept of circular queue. Compare                  circular queue with simple queue.

      30.  Explain indexing structure for index files.

      31.  Write recursive algorithm for computing factorial. Which data structure can be used to                              implement this algorithm?

      32.  How does priority queue work?

      33.  How binary search technique can be applied to search for a particular item with a certain key?

      34.  How access of record is performed in multi key file organization?

      35.  Write an algorithm to reverse a string using stack.

      36.  Write an algorithm for simple queue with ENQUEUE operations.

      37.  Write a program to implement stack using linked list.

      38.  Write a program to implement circular queue using array.

      39.  Explain insert and delete operations in AVL trees with suitable examples.

      40.  Explain double ended queue.

      41.  Write ‘C’ functions to implement DELETE_FIRST_NODE and TRAVERSE operations in                      doubly linked list.

      42.  With a suitable example, explain steps for conversion of a general tree into a binary tree.

      43.  Explain Sequential search method and Binary Search Method.

      44.  Explain Threaded binary trees with suitable examples. OR Explain the structure of threaded                     binary tree.

      45.  Explain Depth First Search and Breadth First Search in graphs with an example.

      46.  Write an algorithm for Insertion sort method. Explain each step with an example.

      47.  Explain various Hash collision resolution techniques with examples. OR

Discuss various rehashing techniques. OR

List out different hash methods and explain any three. OR

Describe various collision resolution techniques in hashing.  OR

Discuss various methods to resolve hash collision with suitable examples. OR

Hash function map several keys into same address called collision. How collision resolution techniques work? OR What is hashing? Explain hash collision and any one collision resolution technique

      48.  Explain Sequential file organizations and list its advantages and disadvantages.

      49.  Write Prim’s algorithm for minimum spanning tree with an example.

      50.  What is prefix notation?   OR What is postfix notation? What are its advantages?

      51.  Write a pseudo-code for PUSH and POP operations of stack.

      52.  Write an algorithm to perform various operations (insert, delete and display) for simple queue.

      53.  Write differences between simple queue and circular queue. Write an algorithm for insert and                  delete operations for circular queue.

      54.  Write a ‘C’ program to implement stack using linked list.

     55.  Enlist and briefly explain various applications of stack.

      56.  Write an algorithm for Binary search method.

      57.  Write a ‘C’ program for Bubble sort.

      58.  Write a ‘C’ program for Selection sort.  OR Write an algorithm for Selection sort method.                        Explain each step with an example.

      59.  Write a ‘C’ program for Merge sort.

      60.  Write a ‘C’ program for Quick sort.

      61.  Write a ‘C’ functions for Insertion sort.  OR Write a ‘C’ program for insertion sort and discuss               its efficiency.

      62.  Write ‘C’ functions for: inserting a node, postorder traversal and counting total number of                         nodes for binary search tree.

      63.  Write an algorithm to check if an expression has balanced parenthesis using stack.

      64.  Write a C program to implement a stack with all necessary overflow and underflow checks                      using array.

      65.  Write a C program to implement a circular queue using array with all necessary overflow and                  underflow checks.

      66.  Write a program to insert and delete an element after a given node in a singly linked list.

      67.  Explain various applications of queue.

      68.  Differentiate between arrays and linked list.

      69.  Define complete binary tree and almost complete binary tree.

      70.  What is binary tree traversal? What are the various traversal methods? Explain any two with                 suitable example.

      71.  Mention the properties of a B-Tree.

      72.  What is a minimum spanning tree? Explain Kruskal’s algorithm for finding a minimum                         spanning tree.

OR    Write Kruskal’s algorithm for minimum spanning tree with an example.

OR    Write Kruskal’s algorithm for minimum spanning tree and explain with an example.

      73.  Write an algorithm to reverse a string of characters using stack.

      74.  Write ‘C’ functions to: (1) insert a node at the end (2) delete a node from the beginning of a                     doubly linked list.   OR Create a doubly circularly linked list and write a function to traverse it.

75.  Compare: (1) Linked-list and Array (2) Circular queue and Simple Queue

     76.  Write an algorithm to implement insert and delete operations in a simple queue.

     77.  Describe: (1) Recursion (2) Priority Queue (3) Tower of Hanoi

     78.  Write a ‘C’ functions to: (1) insert a node at beginning in singly linked list (2) insert an element             in circular queue.

     79.  With figure, explain the following terms: (1) Depth of a tree (2) Sibling nodes (3) Strictly binary             tree (4) Ancestor nodes (5) Graph (6) Minimum spanning tree (7) Degree of a vertex

     80.  Explain Right-in-threaded, left-in-threaded and full-in-threaded binary trees.

     81.  Write an algorithm for binary search method and discuss its efficiency.

     82.  Explain Sequential, Indexed Sequential and Random file organizations.

     83.  Write recursive ‘C’ functions for (1) in-order (2) pre-order and (3) post-order traversals of binary             search tree.

     84.  What is Stack? List out different operation of it and write algorithm for any two operations.

     85.  Write a 'C' program or an algorithm to convert infix expression without parenthesis to postfix                 expression.

     86.  Write user defined C function for inserting an element into circular queue.

     87.  What is a Queue? Write down drawback of simple queue. Also write an algorithm for deleting                 an element from circular queue.

     88.  Write down advantages of linked list over array and explain it in detail.

     89.  Write an algorithm to delete a node from doubly linked list.

     90.  Define the following terms. 1) Graph 2) Tree 3) Multi graph 4) Weighted graph 5) Elementary                path 6) Complete Binary tree 7) Descendent node

     91.  List out different traversal way of tree and demonstrate any two with example.

     92.  Write an algorithm to delete a node from tree.

     93.  Explain AVL tree with example. OR Explain AVL trees. OR Explain deletion in an AVL tree                 with a suitable example.

     94.  Write down precondition and algorithm of binary search method.

     95.  Explain file in terms of fields, records and database.