Manipal University 2007 B.E Information Technology THIRD SEMESTER (IT) END SEMESTER MAKEUP S – UARY, SUBJECT: DATA STRUCTURES – (ICT-205) - Question Paper

THIRD SEMESTER B.E (IT) END SEMESTER MAKEUP exams – JANUARY, 2007
SUBJECT: DATA STRUCTURES – (ICT-205)

Reg.No

Manipal Institute of Technology

(Constituent Institute of MAHE - Deemed University) Manipal - 576 104

THIRD SEMESTER B.E (IT) END SEMESTER MAKEUP EXAMINATIONS - JANUARY, 2007

SUBJECT: DATA STRUCTURES - (ICT-205)

(REVISED CREDIT SYSTEM)

MAX.MARKS: 50

Instructions to Candidates:

Answer any 5 FULL questions.

All questions carry equal marks.

Missing data may be suitably assumed

IA.    List out different types of queues. Define each.

IB.    Define Big-oh notation of time complexity of an algorithm. Arrange the given time complexities in the decreasing order of time.

O(logn), O(2ⁿ), O(n), O(n²), O(n!), O(nlogn)

IC.    Write a program to convert infix expression to prefix expression. (3+2+5)

2A. What is sparse ADT? Discuss its applications.

2B. Obtain the prefix and postfix expression for following

a.    (A+B^AC^AD)*(E+F/D)

b.    A+B*C-D/E*H

2C. Implement double ended queue using array and provide the following functions

-    Insert an item from front end

-    Insert an item from rear end

-    Delete an item from front end

-    Delete an item from rear end

-    Display queue

Consider data in dequeue as Student record with rollno and name as data members.

3A. Write a program to check whether a given string is a palindrome or not using stack.

3B. What is threaded binary tree? List its advantages and disadvantages.

3C. Separate each digit in long integer and construct a singly linked list of those digits. Provide functions to insert, delete, replace and sort the list.

4A. Write a function for binary search. Find the time complexity.

4B. Trace Insertion sort algorithm for following set of numbers 23, 11, 22, 45, 66, 43, 12,

34, 32, 9

4C. Write a program to multiply two polynomials, where polynomial is represented using circular linked list.

5A. Construct a binary tree whose preorder and postorder traversals give the following sequence of vertices.

a.    Preorder - ABCEIFJDGHKL

b.    Postorder - IEJFCGKLHDBA

5B. Define

Binary tree Strictly binary tree.

Complete binary tree Almost complete binary tree

5C. Write a program to create and manage binary search tree with following functions.

-    Inert a node

-    Delete a node

-    Update a node

6A. Construct an expression tree for the following expression.

(a + b * c ) + ( ( d* e + f ) * g )

6B. For a given big set of unsorted numbers, how insert sort, quick sort and merge sort together can be used, inorder to reduce the total time complexity of sorting N numbers.

6C. Define ascending and descending heap. Trace heap sort algorithm for 20, 33, 12, 22,

11, 34, 56, 30, 40.

(3+2+5 Marks)

Page 2 of 2

Attachment: manipal-university-2007-b-e-information-technology-3446-1.pdf

Earning:   Approval pending.