Code: DC08 Subject: DATA STRUCTURES
Time: 3 Hours Max. Marks: 100
NOTE: There are 9 Questions in all.
· Question 1 is compulsory and carries 20 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.
· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.
· Any required data not explicitly given, may be suitably assumed and stated.
Q.1 Choose the correct or best alternative in the following: (2x10)
a. 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
b. An algorithm is made up of two independent time complexities f (n) and g (n). Then the complexities of the algorithm is in the order of
(A) f(n) x g(n) (B) Max ( f(n),g(n))
(C) Min (f(n),g(n)) (D) f(n) + g(n)
c. 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
d. The best average behavior is shown by
(A) Quick Sort (B) Merge Sort
(C) Insertion Sort (D) Heap Sort
e. What is the postfix form of the following prefix *+ab–cd
(A) ab+cd–* (B) abc+*–
(C) ab+*cd– (D) ab+*cd–
f. Time complexities of three algorithms are given. Which should execute the slowest for large values of N?
(A) 
(B) 
(C) 
(D) None
of these
g. 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
h. 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
i. The quick sort algorithm exploit _________ design technique
(A) Greedy (B) Dynamic programming
(C) Divide and Conquer (D) Backtracking
j. The maximum degree of any vertex in a simple graph with n vertices is
(A) n–1 (B) n+1
(C) 2n–1 (D) n
Answer any FIVE Questions out of EIGHT Questions.
Each question carries 16 marks.
Q.2 a. The system allocates memory for any multidimensional array from a large single dimensional array. Describe two mapping schemes that helps us to store a two dimensional metrics in a one-dimensional array. (8)
b. Define a sparse metrics. Explain the representation of a 4X4 matrix using linked list. (8)
Q.3 a. Write an algorithm for insert/delete operations of a Circular Queue that uses an array based implementation. (9)
b. Convert the following Infix expression to Postfix form using a stack:
x + y * z + (p * q + r ) * s, Follow usual precedence rule and assume that the expression is legal. (7)
Q.4 a. What is the best case complexity of quick sort and outline why it is so. How could its worst case behavior arise? (6)
b. Define a linked list with a loop as a linked list in which the tail element points to one of the list’s elements and not to NULL. Assume that you are given a linked list L, and two pointers P1, P2 to the head. Write an algorithm that decides whether the list has a loop without modifying the original list. The algorithm should run in time O(n) and additional memory O(1), where n is the number of elements in the list. (10)
Q.5 a. Write an algorithm for evaluating a postfix expression. (8)
b. Write down the algorithm of quick sort. Sort the following array of elements using quick sort {3 1 4 1 5 9 2 6 5 3 5 8} (8)
Q.6 a. 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 (8)
b. Which sorting algorithm is easily adaptable to singly linked lists? Write the algorithm for that sorting algorithm. (8)
Q.7 a. What is Hashing? Explain any two hashing methods. List various methods to resolve hashing. (10)
b. Define Binary Tree. Explain the representation of binary tree using pointers. (6)
Q.8 a. Given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to output the three traversal orders. Write an algorithm for checking validity of the input, i.e., the program must know if the input is disjoint, duplicated and has a loop. (10)
b. How do you find the complexity of an algorithm? What is the relation between the time and space complexities of an algorithm? Justify your answer with an example. (6)
Q.9 a. Write an algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neither find a shortest path tree from some node? Why? (8)
b. Explain the representations of graph. Represent the given graph using any two methods (8)
