# Thapar University 2006 B.E Computer Science Data Structure - Question Paper

Thapar Institute of Engineering & Technology

B.Tech CS (2nd Year)

Final Term exam

CS001 (Data Structur

**e)**

Vi

Computer Science and Engineering Department CS-001 Data Structures December 2006 B.E Computer Science & Engg. 3^{rd} Sem

Time : 3hrs Max Marks: 36

Note : Attempt any five questions

Q1 a) Define data structure and categorize them into various types based on their organization and representation, with suitable examples.

b) Define an algorithm with suitable examples. What are the various attributes of an algorithm explain? (4+3)

Q2. a) What are the merits and demerits of a linear queue over circular queue? Explain an Application of circular queue data structure.

b) Explain the relative merits and demerits of linked data structures over sequential data structures with suitable example. (4+3)

Q3.Write a function search(p, x) that accepts a pointer p to a, singly linked, list of integers and an integer x and returns a pointer to node containing x, if it exists and NULL otherwise. Write a function searchjnsert (p, x), that adds x to list(pointcd lo by p) if it is not found and returns a pointer to node containing x. (7)

Q4 a) Draw the binary expression tree for the expression given below and write the prefix and postfix form of the expression.

((A+B-C)*D-(E-(F-G))) / (U+V) b) Define balance factor and specify the directions of rotation for balance factors outside -1 - 0 - + 1 range for an A V L Tree. (4+3)

Q5 a) Define Binary Search tree and write an algorithm to delete a node from a BST. b) Explain the Merge Sort algorithm for sorting the data and apply the algorithm to the following data and show all the passes in sorting

25 57 48 37 12 92 86 33 99 3 (4+3)

Q6 a) Explain the binary search algorithm and apply the binary search technique to the following data to find out if the element 184 exists in the data set, if it exists return the index of the element, show all the steps

30 47 86 95 115 130 138 159 166 184 206 212 219 224 237 258

b) Explain threaded binary tree with suitable examples. (4+4)

Attachment: |

Earning: Approval pending. |