Data Structures Past Paper 2018 PDF

Dr. Babasaheb Ambedkar Technological University, Lonere - 402103 Assignment/Question Bank, 2018 Course: B. Tech in Computer Engineering/Information Technology Sub: Data Structures Sem: III...

Dr. Babasaheb Ambedkar Technological University, Lonere - 402103 Assignment/Question Bank, 2018 Course: B. Tech in Computer Engineering/Information Technology Sub: Data Structures Sem: III √ Q. I Multiple choice questions: Tick ( ) the correct answer. (1 × 10 marks) 1. The OS of a computer may periodically collect all the free memory space to form contiguous block of free space. This is called (A) Concatenation (B) Garbage collection (C) Collision (D) Dynamic Memory Allocation 2. A technique for direct search is (A) Binary Search (B) Linear Search (C) Tree Search (D) Hashing 3. If a node having two children is deleted from a binary tree, it is replaced by its (A) Inorder predecessor (B) Inorder successor (C) Preorder predecessor (D) None of the above 4. A mathematical-model with a collection of operations defined on that model is called (A) Data Structure (B) Abstract Data Type (C) Primitive Data Type (D) Algorithm 5. For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to (A) 2n (B) (2n − 1)/2 (C) 2e (D) e2 /2 6. A full binary tree with 2n+1 nodes contain (A) n leaf nodes (B) n non-leaf nodes (C) n − 1 leaf nodes (D) n − 1 non-leaf nodes 7. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a (A) queue (B) stack (C) tree (D) linked list 8. What is the postfix form of the following prefix expression -A/B*C$DE (A) ABCDE$ ∗ /− (B) A − BCDE$ ∗ /− (C) ABC$ED ∗ /− (D) A − BCDE$ ∗ / 9. A full binary tree with n leaves contains (A) n nodes (B) log2 n nodes (C) 2n − 1 nodes (D) 2n nodes 10. The data structure required for Breadth First Traversal on a graph is (A) queue (B) stack (C) array (D) tree 11. If h is any hashing function and is used to hash n keys in to a table of size m, where n¡=m, the expected number of collisions involving a particular key x is: (A) less than 1 (B) less than n (C) less than m (D) less than n/2 12. Let A be an adjacency matrix of a graph G. The ij th entry in the matrix K A , gives (A) The number of paths of length K from vertex Vi to vertex Vj (B) Shortest path of K edges from vertex Vi to vertex Vj (C) Length of a Eulerian path from vertex Vi to vertex Vj (D) Length of a Hamiltonian cycle from vertex Vi to vertex Vj 13. The OS of a computer may periodically collect all the free memory space to form contiguous block of free space. This is called (A) Concatenation (B) Garbage collection (C) Collision (D) Dynamic Memory Allocation 14. You have to sort a list L consisting of a sorted list followed by a few random elements. Which of the following sorting methods would be especially suitable for such a task? (A) Bubble sort (B) Selection sort (C) Quick sort (D) Insertion sort 15. A technique for direct search is (A) Binary Search (B) Linear Search (C) Tree Search (D) Hashing 16. The searching technique that takes O (1) time to find a data is (A) Linear Search (B) Binary Search (C) Hashing (D) Tree Search 17. The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is (A) 6 (B) 5 (C) 7 (D) 8 18. The postfix form of the expression (A+ B)*(C*D E)*F / G is (A) AB+ CD*E FG /** (B) AB + CD* E F **G / (C) AB + CD* E *F *G / (D) AB + CDE * * F *G / 19. In worst case Quick Sort has order (A) O (n log n) (B) O (n2 /2) (C) O (log n) (D) O (n2 /4) 20. If a node in a BST has two children, then its inorder predecessor has (A) no left child (B) no right child (C) two children (D) no child 21. A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as (A) full binary tree (B) AVL tree (C) threaded tree (D) complete binary tree 22. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a (A) Queue (B) Stack (C) Tree (D) Linked list 23. A sort which relatively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called (A) Insertion sort (B) Selection sort (C) Heap sort (D) Quick sort 24. Which of the following sorting algorithms does not have a worst case running time of O(n2 ) ? (A) Insertion sort (B) Merge sort (C) Quick sort (D) Bubble sort 25. An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components? (A) O(n) (B) O(e) (C) O(e+n) (D) O(e2 ) 26. Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer? (A) O(1) (B) O(log 2 n) (C) O(n) (D) O(n log 2 n) 27. The smallest element of an arrays index is called its (A) Lower bound (B) Upper bound (C) Range (D) Extraction 28. In a circular linked list (A) Components are all linked together in some sequential manner (B) There is no beginning and no end (C) Components are arranged hierarchically (D) Forward and backward traversal within the list is permitted 29. A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are (A) More than n (B) More than n+1 (C) More than (n+1)/2 (D) More than n(n-1)/2 30. The maximum degree of any vertex in a simple graph with n vertices is (A) n1 (B) n+1 (C) 2n1 (D) n 31. The quick sort algorithm exploit ———– design technique (A) Greedy (B) Dynamic programming (C) Divide and Conquer (D) Backtracking 32. The number of different directed trees with 3 nodes are (A) 2 (B) 3 (C) 4 (D) 5 33. One can convert a binary tree into its mirror image by traversing it in (A) Inorder (B) Preorder (C) Postorder (D) Any order 34. The data structure required to evaluate a postfix expression is (A) Queue (B) Stack (C) Array (D) Linked-list 35. The data structure required to check whether an expression contains balanced parenthesis is (A) Stack (B) Queue (C) Tree (D) Array 36. The complexity of searching an element from a set of n elements using Binary search algorithm is (A) O(n) (B) O(log n) (C) O(n2) (D) O(n log n) 37. The number of leaf nodes in a complete binary tree of depth d is (A) 2d (B) 2d1 +1 (C) 2d+1 +1 (D) 2d +1 38. What data structure would you mostly likely see in a nonrecursive implementation of a recursive algorithm? (A) Stack (B) Linked list (C) Queue (D) Trees 39. Which of the following sorting methods would be most suitable for sorting a list which is almost sorted (A) Bubble Sort (B) Insertion Sort (C) Selection Sort (D) Quick Sort 40. The process of accessing data stored in a serial access memory is similar to manipulating data on a (A) Heap (B) Queue (C) Stack (D) Binary tree 41. A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are (A) Greater than n1 (B) Less than n(n1) (C) Greater than n(n1)/2 (D) Less than n2 /2 42. A BST is traversed in the following order recursively: Right, root, left. The output sequence will be in (A) Ascending order (B) Descending order (C) Bitomic sequence (D) No specific order 43. The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum (A) Three nodes (B) Two nodes (C) One node (D) Any number of nodes 44. The postfix form of A*B+C/D is (A) *AB/CD+ (B) AB*CD/+ (C) A*BC+/D (D) ABCD+/* 45. Let the following circular queue can accommodate maximum six elements with the following data front = 2 rear = 4 queue = —–, L, M, N, —–, —– What will happen after ADD O operation takes place? (A) front = 2 rear = 5 queue = L, M, N, O, —-  (B) front = 3 rear = 5 queue = L, M, N, O, —- (C) front = 3 rear = 4 queue = L, M, N, O, —– (D) front = 2 rear = 4 queue = L, M, N, O, —– 46. A binary tree of depth d is an almost complete binary tree if (A) Each leaf in the tree is either at level d or at level d1 (B) For any node n in the tree with a right descendent at level d all the left descendents of n that are leaves, are also at level d (C) Both (A) (B) (D) None of the above 47. A linear collection of data elements where the linear node is given by means of pointer is called (A) Linked list (B) Node list (C) Primitive list (D) None of these 48. Representation of data structure in memory is known as: (A) Recursive (B) Abstract data type (C) Storage structure (D) File structure 49. If the address of A and A are 1000 and 1010 respectively and each element occupies 2 bytes then the array has been stored in ——- order. (A) Row major (B) Column major (C) Matix major (D) None of these 50. An adjacency matrix representation of a graph cannot contain information of: (A) Nodes (B) Edges (C) Direction of edges (D) Parallel edges 51. An ADT is defined to be a mathematical model of a user-defined type along with the collection of all ———— operations on that model. (A) Cardinality (B) Assignment (C) Primitive (D) Structured 52. The goal of hashing is to produce a search that takes (A) O(1) time (B) O(n2 ) time (C) O(log n) time (D) O(n log n) time 53. Which data structure is needed to convert infix notation to postfix notation? (A) Branch (B) Queue (C) Tree (D) Stack 54. The extra key inserted at the end of the array is called a, (A) End key (B) Stop key (C) Sentinel (D) Transposition 55. How many nodes in a tree have no ancestors. (A) 0 (B) 1 (C) 2 (D) n 56. In order to get the contents of a Binary search tree in ascending order, one has to traverse it in (A) Pre-order (B) In-order (C) Post order (D) Not possible 57. The prefix form of an infix expression p + q − r ∗ t is (A) +pq − ∗rt (B) − + pqr ∗ t (C) − + pq ∗ rt (D) − + ∗pqrt 58. Which data structure is used for implementing recursion? (A) Queue (B) Stack (C) Arrays (D) List 59. In binary search, average number of comparison required for searching an element in a list if n numbers is (A) log2 n (B) n / 2 (C) n (D) n 1 60. In order to get the information stored in a Binary Search Tree in the descending order, one should traverse it in which of the following order? (A) left, root, right (B) root, left, right (C) right, root, left (D) right, left, root 61. Ackermans function is defined on the non-negative integers as follows a (m, n) = n+1 if m = 0 = a (m − 1, 1) if m 6= 0, n = 0 = a (m − 1, a(m, n − 1)) if m 6= 0, n 6= 0 The value of a (1, 3) is (A) 4 (B) 5 (C) 6 (D) 7 62. For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is (A) ne (B) 2n (C) 2e (D) en 63. Sorting is not possible by using which of the following methods? (A) Insertion (B) Selection (C) Exchange (D) Deletion 64. A binary tree with n nodes has null branches? (A) n (B) n+1 (C) n/2 (C) n2 65. How many different trees are possible with n nodes? (A) n (B) n+1 (C) 2n − n (C) n2 66. In tree construction which is the suitable efficient data structure? (A) Array (B) Linked list (C) Stack (D) Queue 67. Of the following tree structure, which is, efficient considering space and time complexities? (A) Incomplete Binary Tree (B) Complete Binary Tree (C) Full Binary Tree (D) None of the above 68. Which is the simplest file structure? (A) Sequential (B) Indexed (C) Random (D) None of the above 69. f(n) is of the order of g(n) if there exist positive integers a and b such that (A) f(n) ≤ a * g(n) for all n ≥ b (B) f(n) ≤ a * g(n) for all n ≤ b (C) g(n) ≤ a * f(n) for all n ≥ b (D) None of the above 70. Adjacency matrix for a digraph is (A) Unit matrix (B) Symmetric (C) Asymmetric matrix (D) None of the above 71. Which of the following data structure may give overflow error, even though the current number of elements in it, is less than its size (A) Simple queue (B) Circular queue (C) Stack (D) None of the above 72. Which of the following types of expressions does not require precedence rules for evaluation? (A) Fully parenthesized infix expression (B) Partially parenthesized infix expression (C) Both (A) and (B) (D) Prefix expression 73. Given 2 sorted lists of size m and n respectively. The number of comparisons needed in the worst case by merge sort will be (A) m ∗ n (B) Max(m, n) (C) Min(m, n) (D) m + n − 1 Q. II Write the short answer for the following questions. (2 marks) 1. List out the areas in which data structures are applied extensively? 2. What are the major data structures used in the following areas : RDBMS, Network data model Hierarchical data model. 3. How does an array differ from an ordinary variable? 4. Define the following terms: (i) Abstract data type. (ii) Column major ordering for arrays. (iii) Adjacency multilist. (iv) Game trees. 5. What is stack? Enlist three applications of stack. Also, give three appllications of queue. 6. Why queue is considered to be linear data structures? Justify your answer. 7. Assume that a queue is available for pushing and popping elements. Given an input sequence a, b, c, (c be the first element), give the output sequence of elements if the rightmost element given above is the first to be popped from the queue. 8. Write the postfix form of the expression A + B / C 9. Construct binary search tree for the following items: 17, 10, 7, 65, 19, 18, 2 10. Write and explain procedure for insert an item into stack. 11. What are operations performed on stacks? 12. How is the front of the queue calculated? 13. What is the relationship between a queue and its underlying array? 14. What is a spanning Tree? 15. Classify the Hashing Functions based on the various methods by which the key value is found. 16. What are the types of Collision Resolution Techniques and the methods used in each of the type? 17. What is the data structures used to perform recursion? 18. What is the difference between NULL and VOID pointer? 19. What is the type of the algorithm used in solving the 8 Queens problem? 20. In an AVL tree, at what condition the balancing is to be done? 21. In RDBMS, what is the efficient data structure used in the internal storage representation? 22. Minimum number of queues needed to implement the priority queue? 23. Whether Linked List is linear or Non-linear data structure?  24. For the following COBOL code, draw the Binary tree? 01 STUDENT REC. 02 NAME. 03 FIRST NAME PIC X(10). 03 LAST NAME PIC X(10). 02 YEAR OF STUDY. 03 FIRST SEM PIC XX. 03 SECOND SEM PIC XX. 25. What is header linked list? Use header linked list to store the following polynomial. p(x) = 2x8 − 5x7 + 3x2 + 4 26. If you are using C language to implement the heterogeneous linked list, what pointer type will you use? 27. Write and explain recursive procedure to calculate factorial of a number n. 28. What is singly linked list? Insert the following elements in sequence in an empty linked list. A, D, U, X 29. What are the advantages & disadvantages of a doubly linked list over a singly linked list? 30. Consider P, Q, U, X, Z nodes, construct the binary search tree. 31. What is polish notation? Consider infix expression P: (A+B)/(C-D), translate it into prefix and postfix notation. 32. What is garbage collection? Who will run garbage collection program? When it will be run? 33. List out few of the Application of tree data-structure? 34. List out few of the applications that make use of Multilinked Structures? 35. What values are automatically assigned to those array elements which are not explicitly initialized? 36. What is the difference between a grounded header link list and a circular header link list? 37. How many key comparisons and assignments an insertion sort makes in its worst case? Q. III Write the long answer for the following questions. (5 marks) 1. What is data structure? Enlist the five areas in which data structure is used. 2. What is an Abstract Data type (ADT)? Explain, why array is called ADT? 3. What is sparse matrix? Convert the following matrix into non-sparse matrix.   2 0 0 0   0 0 0 0   0 0 1 0     0 2 0 0 4. What is linked list? Create linked list to maintain five students record such as student name and roll no. 5. Suppose multidimensional arrays A and B are declared using A(-1:2, 2:10) and B(1:8, -3:3, -4:5). Find the length of each dimension and the number of elements in A and B.  6. Suppose a 10 element array A contains the values a1 , a2 ,.....a10. To find the values in A after each of the loop. Repeat for K = 1 to 9 Set A[k+1] = A [k] 7. Let LIST be a linked list in memory. Write a separate procedure for each of the following which: (a) Finds the how many times a given ITEM occurs in LIST. (b) Finds the how many of nonzero elements in LIST. (c) Adds a given value K to each element in List. 8. Consider the multidimensional arrays: X(-5:5, 3:33) and Y(3:10, 1:15, 10:20) (a) Find the length of each dimension and the number of elements in X and Y. (b) Suppose Base(Y)=400 and there are w=4 words per memory location. Find the effective indices E1, E2, E3 and the address of Y[5, 10, 15] assuming (i) Y is stored in row major order and (ii)Y is stored in column major order. 9. What is data, data types, data structures. Why stack is called as abstract data type (ADT)? 10. Explain the row major and column major storage of two dimensional arrays in memory. 11. Suppose the data in LIST are sorted. Write algorithm to find the location of the ITEM in the linked list. 12. A single array A[1...Maxsize] is used to implement two stacks. Two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) points to the location of the topmost element in each of the stack. Insert the elements: A, B, C in stack 1 and insert X, Y, Z in the stack 2 and show each of the stack content. Also, if the space is to be used efficiently, what is condition for stack full. 13. Write an algorithm to evaluate a postfix expression. Execute your algorithm using the fol- lowing postfix expression as your input: ab + cd + ∗f ↑ 14. If a circular linked list is used to represent a queue. Discuss, how enqueue and dequeue operations can be performed by using single variable. 15. Consider the stack, where stack is allocated N=6 memory cells. Suppose initially stack contains A, D, E F G(Top of stack). Then the following operations called in order. Show the stack top and any other situation raised while doing each of the operation. Push(stack, K) Pop(stack, Item) Push(stack, L) Push(stack, S) Pop(stack, Item) Push(stack, T) 16. Consider insertion of characters in empty linked list A, B, C, D, E, F. Assume these elements are stored using 10 memory locations. Find the sequence of characters in the list. Suppose F and then C are deleted and then G is inserted at the beginning of list. Find the final structure. 17. Let J and K be integers and suppose Q(J, K) is recursively defined by ( 5, if J < K; (1) Q(J, K) = Q(J − K, K + 2) + J, if J≥ K. (2) Find the values of Q (2, 7), Q (5, 3) and Q (15, 2). 18. Consider the binary tree T in Figure. 1 Find preorder, inorder and postorder traversal of the tree. A B C D E G H J K F L Figure 1: 19. The following numbers are inserted into an empty binary search tree in the given order. 10, 2, 4, 6, 14, 11, 15 Construct binary search tree. Also, what is the height of the tree? 20. What is m-way search trees? Construct 2-way search tree from an empty search tree with the following keys in the order: 20, 35, 40, 10, 15, 25. 21. What is best data structure to check whether an arithematic expression has balanced paren- theses? Illustrate your answer with a small parenthesized arithematic expression. 22. Define the following terminology with suitable example. Depth of the tree Header linked list Graph Level of node In-degree of node 23. Consider the simple undirected graph given in Figure 2. Describe G formally in terms of its set V of nodes and its set E of edges. Also find the degree of each node. Figure 2: 24. What is graph traversal? Suppose xyz airways has nine daily flights, as follows: 103 Aurangabad to Hyderabad, 203 Bombay to Delhi, 305 Chennai to Manglore, 106 Hy- derabad to Aurangabad, 204 Delhi to Bombay, 308 Manglore to Bombay, 201 Bombay to Chennai, 301 Delhi to Raipur, 402 Raipur to Chennai. Give linked list representation using two lists (node, edge). 25. What is insertion sort? Sort the following elements using insertion sort. Also, show that complexity of insertion sort is O(n2 ). 77, 31, 45,11, 88, 22, 666, 55 26. Insert the following data into a hash table implemented using linear open addressing. 11, 21, 1, 3, 33, 4, 15, 6, 7, 18, 9, 99 Assume the buckets to have 3 slots each. Make use of the hash function h(X)=X%10. (6 marks) 27. What is an AVL search tree? Construct an AVL search tree using the following data. Perform the appropriate rotation to re-balance the tree. OS, LINUX, DOS, UNIX, XENIX. 28. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X. For a node stored at X[i], the left child is stored in X[2i] and the right child is stored in X[2i+1]. Give the array representation of the tree given in Figure 3. Also, in worst case to store any binary tree of n number of vertices, how many places need in the array? 12 10 20 8 14 13 Figure 3: 29. Consider an array B[0:15, 0:5], the base address is 1003 and one element occupy 4 bytes of memory. Answer the following sub-questions. (i) The number of elements in B (ii) The total memory occupied by B (iii) The address of B[7, 2] element 30. What is a circular header list? Write and explain algorithm for traversing circular header list. 31. Enlist and explain advantages of circularly linked lists over singly linked list. Also, give disadvantages of circularly linked list. 32. What is circular queue? Write down routines for inserting and deleting elements from a circular queue using arrays. 33. Give an array representation of priority queue. 34. What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers: 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48. Traverse the tree in Preorder, Inorder and postorder 35. How do you rotate a Binary Tree? Explain right and left rotations with the help of an example. 36. Taking a suitable example explains how a general tree can be represented as a Binary Tree. 37. Prove the hypothesis that A tree having m nodes has exactly (m1) edges or branches. 38. What are the different ways of representing graph in memory? Represent the following graph in figure 4 using those ways.  Figure 4: 39. Reverse the order of elements on a stack S using two additional stacks. using one additional queue. 40. Draw the expression tree of the following infix expression. Convert it in to Prefix and Postfix expressions. ((a + b) + c ∗ (d + e) + f ) ∗ (g + h) 41. Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time. 42. Write the non-recursive algorithm to traverse a tree in preorder. 43. What is quick sort? Sort the following array using quick sort method. 24 56 47 35 10 90 82 31 44. Create a heap with following list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3, 12 45. Compare and contrast various sorting techniques with respect to memory space and comput- ing time. 46. The following values are to be stored in a hash table 25, 42, 96, 101, 102, 162, 197 Describe how the values are hashed by using division method of hashing with a table size of 7. Use chaining as the method of collision resolution. 47. What do you mean by hashing? Explain any five popular hash functions. 48. Which are the two standard ways of traversing a graph? Explain them with an example of each. 49. Consider the following specification of a graph G V(G) = 1, 2, 3, 4 E(G) = (1, 2), (1, 3), (3, 3), (3, 4), (4, 1) (i) Draw an undirected graph. (ii) Draw its adjacency matrix. 50. Why do we use a symptotic notation in the study of algorithm? Describe commonly used asymptotic notations and give their significance. 51. Illustrate the steps for converting an infix expression into a postfix expression for the following expression (a + b) ∗ (c + d)/(e + f ) ↑ g. 52. Construct a binary tree whose nodes in inorder and preorder are given as follows: Inorder : 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50 Preorder: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50 53. Execute your algorithm to convert an infix expression to a post fix expression with the fol- lowing infix expression on your input: (m + n) ∗ (k + p)/(g/b) ↑ (a ↑ b/c) 54. A double ended queue is a linear list where additions and deletions can be performed at either end. Represent a double ended queue using an array to store elements and write modules for additions and deletions. 55. Explain Dijkstras algorithm for finding the shortest path in a given graph. 56. Find the shortest path from A to Z using Dijkstras Algorithm Figure 5: 57. Write a complete programme in C to create a single linked list. Write functions to do the following operations (i) Insert a new node at the end (ii) Delete the first node 58. Define a sparse metrics. Explain the representation of a 4X4 matrix using linked list. 59. Given the following inorder and preorder traversal reconstruct a binary tree Inorder sequence: D, G, B, H, E, A, F, I, C Preorder sequence: A, B, D, G, E, H, C, F, I 60. Write a procedure to reverse a singly linked list. 61. Define a method for keeping two stacks within a single linear array S in such a way that neither stack overflows until entire array is used and an entire stack is never shifted to a different location within the array. Write routines for pushing and poping elements in two stacks. 62. Suppose a queue is housed in an array in circular fashion. It is desired to add new items to the queue. Write down a procedure ENQ to achieve this also checking whether the queue is full. Write another procedure DQ to delete an element after checking queue empty status. 63. What is a height balanced tree? Explain how the height is balanced after addition/deletion of nodes in it? End of question bank