DATA STRUCTURES

B.E. 2/4(IT) 1 Semester (Main) Examination, December 2010

Note: Answer all questions of Part- A. Answer five questions from Part – B.

PART – A (10*2.5=25 Marks)

- What is testing and debugging?
- What do you understand by time and space complexity of algorithms?
- Compare and contrast DFS and BFS.
- State the difference between Stacks and Queues. What are the applications of Queue?
- Define AVL trees and splay trees.
- State the difference between complete binary tree and full binary tree.
- What is a weighted graph? How is it represented?
- What are the advantages of doubly linked lists over singly linked lists?
- Define a leftist tree. What are its advantages?
- What are the various applications of Graphs?

PART –B (5*10=50 Marks)

11. Write an algorithm to insert an element any where in the list implemented using

formula based representation. Determine its time complexity.

12. Write a C++ program to implement a stack with linked representation.

- a) For the following key sequences determine the B-Tree obtained of order three when the keys are inserted one –by-one in the order given into an initially empty tree

2, 7, 1, 8, 4, 5, 9, 0, 3, 6

b)The preorder traversal of binary tree is ABCDEFG and its converse inorder is GDFEABC construct the tree.

- a) Explain AVL Rotations in detail with examples.

b) Explain insertion and removal of items in leftist tree.

15. Write C++ program to insert into and removal of items from a linear list using

array representation and linked representation. Compare their time complexities.

16. a) Explain Kruskal’s Algorithm with an example.

b) Explain how to insert an element into a max heap.

17. Write short notes on the following:

a) Algorithm Analysis

b) Priority Queues

c) Tree Traversals.

DATA STRUCTURES

B.E. 2/4(IT) 1 Semester (Suppl.) Examination, July 2010

Note: Answer all questions of Part- A. Answer five questions from Part – B.

PART – A 25

- What is the functionality of operator ‘delete’? 2
- Explain how to represent binary trees as arrays. 2
- Define a priority queue. 2
- Define a Stack. List down applications of stacks. 3
- What is the best, worst, average time complexity of sequential search? 3
- State the difference between full binary tree and complete binary tree. Give one example for each kind. 3
- Define theta notation. Express the function f(x) = 100x²+4x+2 in Ɵ – notation and find values of c and no. 3
- What are the advantages of double linked list over single linked list. 2
- Convert the postfix expression to infix and prefix form. 2

ab-de/* - Define a Red-Black Tree with an example. 3

PART – B (5*10=50)

11. a) Write a C++ program for Merge sort. 4

b) Explain the following: (4+2)

i) Asymptotic Notations.

ii) Testing and Debugging.

- Write an algorithm for conversion of an infix expression to postfix expression and trace the algorithm for the expression a+(b*c)-d and get the resultant postfix expression. 10
- Define an AVL Tree. Write an algorithm for insertion an AVL tree along with an example. 10
- a) Differentiate between linear lists and linked lists. 5

b) Write procedure for insertion and deletion of an element from a double linked list with an example. 5 - a) Discuss with examples various graphs search methods. 5

b) How to insert an element into max heap? Describe the procedure with an example. 5 - a) Explain Radix sort with an example. 5

b) Explain how insertion can be done in a max Height-Biased leftist trees with an example. 5 - Write short notes on the following:

a) Binary Tree Traversals. 5

b) Applications of circular queues. 3

c) Multiple lists in a single array. 2

DATA STRUCTURES

B.E. 2/4(IT) 1 Semester (Main) Examination, Nov./Dec., 2009

Note: Answer all questions of Part- A. Answer five questions from Part – B.

PART – A Marks:25

- What is debugging? 2
- Derive the time complexity for the selection sort. 3
- What is the best data structure to check whether an arithmetic expression has balanced parenthesis and how it is solved? 2
- Describe about ‘Linked Queue’. 3
- Describe how to represent binary tress as linked representation. 2
- Define: ‘Red-black tree’. Give an example. 3
- What is data object? Give an example. 2
- Give the “Class definition for linked list”. 3
- What are the properties of Graphs? 2
- Define ‘Leftist tree’. 3

PART – B Marks: 50 - a)What are different Asymptotic Notations? Give examples. 4

b)Write a brief description about the following: 3+3

i) Exceptions ii) Dynamic Memory allocation - a) Write an algorithm to evaluate the postfix expression. Discuss clearly the data structures that are needed for it. 3

b) Evaluate the following postfix expression:

5 6 2 + * 12 4 / - 2

c) Compare the sequential and linked representation of stacks. 5 - a) Describe how to do insertion and deletion operations in AVL trees. 5

b) Give the abstract data type binary tree and write the procedure to determine the height of a binary tree. 5 - a)Write a method to return the index of first occurrence of the given element in a linear list with linked representation. 5

b) Write a procedure to insert the element whose value is same as index using array list. 5 - a) Write the pseudo code for breadth-first search and give example. 5

b) Write a procedure to delete the max element from the max heap. 5 - a) Convert the following infix expression into postfix expression

AhB*C-D+E/F/(G+H) 5

b)write about binary search trees. 5 - a) Define M-way search tree. How to insert and delete an element into M-way search tree? Describe with examples. 5

b) Explain any one application of Graphs. 5

DATA STRUCTURES

B.E. 2/4(IT) 1 Semester (Suppl.) Examination, May/June 2009

Note: Answer all questions of Part- A. Answer five questions from Part – B.

PART – A

- Define Splay tree. 2
- What is the Best, Worst and Average time complexity for sequential search? Give proper reasoning? 3
- What are the applications of Queues? 2
- Describe about ‘linked Stack’. 3
- What are the properties of Binary trees? 2
- Define ‘AVL tree’. Give an example? 3
- What are the advantages of doubly linked list over singly list? 2
- Give the class definition for ‘Array list’. 3
- Give the representations of unweighted graphs. 2
- Define prior queue? Give abstract data type specifications of a max priortiy queue. 2

PART – B - a) Write a C++ program for selection sort. 4

b) Write a brief description about the following: 3+3

i) Recursion.

ii) Own data type. - a) Describe the procedure for converting infix to postfix expression. 5

b) Compare the sequential and linked representation of Queue. 3

c) What is the difference between linear and circular queue implementation? 2 - a) Describe how “insertion” and “deletion” operations are carried in B trees. 5

b) What are the data members and visit methods of a linked binary tree. 5 - a) Write a procedure to insert the element as index the element using chain list. 5

b) How to represent Multiple lists in a single array. 5 - a) Discuss with examples various graphs search methods. 5

b) How to insert an element into max heap? Describe the procedure. 5 - a) Explain how to solve the problem “Towers of Hanoi” using stacks 5

b) Write a procedure to insert an element into a Binary search tree. 5 - Write short notes on the following:

a) AVL tree rotations 4

b) Leftist trees 3

c) Testing & debugging. 3

DATA STRUCTURES

B.E. 2/4(IT) 1 Semester (Main) Examination, Nov./Dec., 2008

Note: Answer all questions of Part- A. Answer five questions from Part – B.

PART – A (Marks: 10*2.5=25)

1. How do you create dynamic memory for one dimensional array?

2. What do you understand by asymptotic notation?

3. What are the applications of Stacks and Queues?

4. Display the objects of a stack after each of the following operations on it.

a) push(88) b)push(11) c)pop()

d)push(55) e)pop() f)push(99)

5. What is an indexed binary search tree?

6. Define Red-Black trees? What are its advantages?

7. What are the advantages of circular lists over singly linked lists?

8. What is minimum cost spanning tree? How is it useful?

9. Define a heap. What are its advantages?

10. What are the different representations of a graph?

PART – B (Marks: 5*10=50)

11. Use repeated substitution to solve the following recurrence: 10

t(n) = 2 if n=0

2+t(n-1) if n>0

12. Write a C++ program to implement a Queue with linked representation. 10

13. a) For the following key sequences determine the Binary Search Tree obtained when the keys are inserted one-by-one in the order given into an initially empty tree 2, 7, 1, 8, 4, 5, 9, 0, 3, 6. 5

b) The preorder transversal of a binary tree is ABCDEFG and its converse inorder is GDFEABC. Construct the tree. 5

14. Explain insertion into and removal of items from a B-tree, with an example. 10

15. Write C++ program to insert into and removal of items from a doubly linked list.10

16. a) Explain how to delete an element from min heap. 5

b) What is leftist tree? Explain. 5

17. Write short notes on the following:

a) Testing and Debugging 3

b) Algorithm Analysis 3

c) AVL tree rotations. 4

DATA STRUCTURES

B.E. 2/4(IT) 1 Semester (Suppl.) Examination, May/June 2008

Note: Answer all questions of Part- A. Answer five questions from Part – B.

PART – A Marks:25

1. What is the functionality of the operator ‘new’? 2

2. Briefly explain about ‘Space Complexity’. 3

3. Describe about ‘The abstract data type-stack’. 2

4. Explain about ‘Circular Queues’. 3

5. In a binary tree of height ‘h’, h>=0, what is the minimum and maximum number of elements. 2

6. Define ‘Red-black Tree’. Give an example. 3

7. What are the various operations applicable in linear list. 2

8. Give the ‘Struct definition for a chain node’. 3

9. Differentiate between ‘max tree’ and ‘max heap’. 2

10. Define ‘Spanning Tree’. Give an example. 3

PART – B Marks:50

11. a) Explain the following: 6

i) Exception Handling

ii) Operator Overloading

b) Differentiate between ‘Big Oh Notation (O)’ and ‘Little Oh Notation (0)’.

4

12. a) Explain how to solve the problem ‘Towers of Hanoi’ using Stacks. 5

b) Write a C++ program for doubling the length of array Queue. 5

13. a) Describe about Linked Representation of a Binary Tree. 5

b) Ex1plain how to delete a node from a B-Tree. 5

14. a) In a circular shift operation, the elements of a linear list are rotated clockwise

by a given amount. For example, when the elements of x = [0, 1, 2, 3, 4]

are shifted circularly by 2, the result is x = [2, 3, 4, 0, 1]. 6

Describe how one can perform a circular shift using three reversal operations.

Each reversal may reverse a portion of the list or reverse the entire list.

b) Write a method to return the index of the first occurrence of the given

element in a linear list with linked representation. 4

15. a) Explain how to meld two max Height-Based Leftist Trees. Give an example

6

b) Differentiate between ‘Linked adjacency lists’ and ‘Array adjacency lists’.

4

16. a) Explain about ‘Recursive C++ Functions’. 4

b) Explain how to insert an element into a Max Heap. 3

c) Explain how to do Breadth-First Search in a graph. 3

17. Explain about any two of the following: 5+5

a) AVL Trees

b) Binary Tree Traversal

c) Huffman Codes