IMPS OF DS (3130702)

Importants of Data Structure - 3130702

Module - 1 : Introduction to Data Structure


1. Define Data Structure and differentiate between linear and nonlinear data structures.
2. Performance Analysis and Measurement (Time and space analysis of algorithms-Average).

Module - 2 : Linear Data Structure


1. Differentiate between 1) Stack and Queue. (2) Array and Link list.
2. List the advantages of a doubly linked list over singly linked list.
3. A two dimensional array is stored row by row, then what is the address of matrix element A[i,j] for n row and m column matrix? How array representation of polynomial 2x2+5xy+y2 can be done?
4. Which data structure is used in a time sharing single central processing unit and one main memory computer system where many users share the system simultaneously? How users are added for use of the system?
5. What is the problem with sign and magnitude representation if addition of +7 with -6 is performed? Evaluate 7+7 using 2’s complement representation and modulo 16 arithmetic.
6. Write an algorithm for (1) calculating the square of the number for all the prime numbers ranging between 1 to n. Perform time and space analysis. (2) convert an infix expression to a postfix expression. Show the working of the algorithm for the following expression. A+BC/D$E-(FG). (3) swap two nodes, n and n+1, in a singly linked list (4) to count the number of nodes in a singly circular linked list. (5) for Push and Pop operations on a stack. (6) to convert Infix Expression(without parenthesis) into Postfix Expression. (7) Insert and Delete operation in Circular Queue. (8) INSERT, DELETE and DISPLAY function of Circular Queue. (9) inserting an element in a circular queue and deleting a node from a singly linked list. (10) insertion and deletion of a node in Doubly Linked List. (11) insertion of nodes at last position in Linear Linked List.
7. Given a linked list whose typical node consists of an INFO and LINK field. Formulate an algorithm which will count the number of nodes in the list.
8. What is the need of a doubly linked list? Consider a problem of inserting a node into a doubly linked linear list to the left of a specified node whose address is given by variable M. Give details of algorithm.
9. ESolve the Given: (i) In which case insertion and deletion cannot be performed in stack? (ii) How stack can be used to recognize strings acm, bcb, abcba, bacab, abbcbba? Show the trace of contents of stack for recognizing the string abcba. (iii) Convert a+bc-d/eh to postfix. (iv) Convert ((a+b^c^d)*(e+f/d)) to postfix. (v)Which stack operations are needed for performing conversion from infix to postfix? Write the algorithm.
10. What is the difference between serial and sequential processing? How can a record be deleted in a sequential file?
11. Convert Infix Expression A ^ B * C - D + E / F / (G + H) into Postfix expression using stack OR Evaluate the following postfix expression using a stack. Show the steps. 2 $ 3 + 5 * 2 $ 2 – 12 $ 6. OR Evaluate the Postfix Expression 6 2 3 + - 3 8 2 / + * 2 $ 3 + using Stack.
12. Consider the stack S of characters, where S is allocated 8 memory cells. S: A,C,D, F, K, _, _, _ Describe the stack as the following operations take place. Pop(), Pop() ,Push(L), Push(P), Pop(), Push(R), Push (S), Pop() .
13. Write a program to implement 1) queue and check for boundary conditions 2) a circularly linked list
14. List the advantages of a doubly linked list over singly linked list.
15. What is Recursion? Write a pseudocode in ‘C’ language to find the multiplication of two natural numbers.
16. Write a pseudocode for PUSH and POP operations of stack.
17. Illustrate the working of priority queue with suitable examples.
18. Write a recursive algorithm to compute the factorial of a given number. Which data structure can be used to implement this algorithm? OR Write a recursive function to compute the factorial of a number. Show usage of STACK in recursion for this function.
19. Explain the working of the Prim’s algorithm with suitable examples.
20. Write a C program to reverse a string using stack.
21. Discuss various types of data structures with examples.
22. What is time and space analysis? State and explain time analysis for linear search and binary search method.
23. State disadvantages of simple queue. How to overcome it?
24. State at least one efficient representation of a sparse matrix.

Module - 3 : Nonlinear Data Structure


1. Discuss Threaded Binary Tree. OR Explain Threaded binary trees with suitable examples.
2. Discuss different representations of a graph.
3. What is a Binary Search Tree? Construct a binary search tree for the following elements 11,6,14,8,12,15,16,7,9,23. OR Create a Binary Search Tree for the following data and do Inorder, Preorder and Postorder traversal of the tree. 45, 70,30, 60, 15,75,35,55,20,85,80 OR Draw a Binary expression tree for the following and perform preorder traversal: a * ( b + c ) + ( d * e ) / f + g * h.
4. Apply Djkstra’s algorithm on the following graph with Node A as the starting node. OR Apply Djkstra’s algorithm for the following graph with Node S as the starting node.
5. The Preorder traversal of the tree is: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 The inorder traversal of the tree is : 01,2,3,4,5,6,7,8,9,10 What is the postorder traversal? How can a general tree be converted to a binary tree?
6. A communications network is represented by a graph. Each node represents a communication line and each edge indicates the presence of interconnection between the lines. Which traversal technique can be used to find breakdown in line? Explain.
7. Write a recursive algorithm for computing factorials. Which data structure can be used to implement this algorithm?
8. Perform inorder, postorder and preorder traversals for the following binary tree.
9. Explain the working of the Kruskal’s algorithm.
10. Define the following terms with respect to a graph: i) M-ary tree ii) Out Degree iii) Leaf iv) Node, v) Edge, vi) Path vii) Cyclic Graph viii) Siblings ix) Strictly Binary Tree.
11. Discuss 1) different representations of a graph 2) height balanced trees. 3) Minimal Spanning Tree. 4) algorithm of Breadth First Search (BFS) traversal for a Graph. Explain with an example.
12. Write an algorithm for (1) deletion of nodes in Linear Linked List (2) INSERT operation to insert a node at a given position in a Link list. (3) to find the length of a simple link list. (4) to insert a node in a Circular Link List at the FIRST position. (5) DELETE operation in a Binary search tree. (6) a non recursive (Iterative) pre order traversal of Binary search tree.
13. Explain spanning tree with example.
14. List out graph traversal techniques & explain any one using suitable examples.
15. Explain Sequential search method with suitable example.
16. Explain insert and delete operations in AVL trees with suitable examples.
17. Create an AVL tree for the following sequence of numbers. Also mention the name of action taken. 200, 400, 800, 900, 850, 700, 950, 100, 150

Module - 4 : Hashing & File Structuree


1. Explain indexing structure for index files.
2. Explain Sequential Files and Indexed Sequential Files Structures. OR Explain Sequential file organizations and list its advantages and disadvantages.
3. How do the following hash functions work? (i) The mid square method (ii) Digit analysis.
4. How primitive data type floating points are stored in computers?
5. What is the difference between serial and sequential processing? How can a record be deleted in sequential file?
6. How access of record is performed in a multi key file organization?
7. Hash function maps several keys into the same address called collision. How collision resolution techniques work?
8. What is hashing? Explain hash collision and any one collision resolution technique.
9. List the qualities of a good hash function.
10. Explain two hash functions OR What is hashing? Explain Different Hashing techniques in brief. OR What is hashing? Explain hash clash and its resolving techniques.
11. Explain different types of File Organizations and discuss the advantages and disadvantages of each of them.
12. Explain collision in the context of hashing? Discuss collision resolution techniques.
13. What is a hash function used for? Give one example of a hash function.
14. State and explain collision resolution techniques in hashing.

Module - 5 : Sorting & Searching


1. Write the algorithm for binary search. OR What is a binary search tree? Create a binary search tree for the following data. 14, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 23 Explain deleting node 20 in the resultant binary search tree.
2. “If no interchanges occurred, then the table must be sorted and no further passes are required."Which sorting method works on this principal? Apply above sorting technique on the following data 5 1 4 2 8.
3. How binary search techniques can be applied to search for a particular item with a certain key?
4. Apply quick sort on following data: 42 23 74 11 65 58 94 36 99 87.
5. Write the algorithm for (1) binary search and find its complexity. (2) for Bubble sort (3) Selection sort (4) Sequential Search (5) for insertion sort. (6) Merge sort method.
6. Insert the following letters into an empty B-tree of order 5: C N G A H E K Q M F W L T Z D P R X Y S.
7. What is the complexity of the quick sort algorithm on sorted data? Justify your answer.
8. Explain the difference between insertion sort and selection sort with an example. What is the time complexity of these algorithms? How?
9. Apply a merge sort algorithm for the following data and show the steps. 66, 33, 40, 22, 55, 88, 11, 80, 20, 50, 44, 77, 30.
10. Explain average case timing analysis for Search Algorithms.
11. Explain different types of File Organizations and discuss the advantages and disadvantages of each of them.
12. Sort the following numbers in ascending order by applying a quick sort. 29 15 11 82 22 17 53 57 4 8.
13. “If no interchanges occurred, then all the elements must be sorted and no further passes are required.” Which sorting technique works on this principal? Apply the same sorting technique on the following data to sort them in ascending order. 11, 15, 13, 14, 2, 8, 10.