Note: Attempt any five questions.
1. What are some of the applications for the tree data structure?
Ans: i) Manipulation of the arithmetic expressions.
ii)Symbol table construction.
iii) Syntax analysis.
2. Which data structure is used to perform recursion?
Ans: The answer is Stack. Stack has the LIFO (Last In First Out) property; it remembers it’s ‘caller’. Therefore, it knows to whom it should return when the function has to return. On the other hand, recursion makes use of the system stack for storing the return addresses of the function calls.Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written explicit, stack is to be used.
3. What is linked lists?What are its applications in data structure?
Ans: Linked list is the most basic form of a data structure. A linked list is more or less similar to an array in that it can hold a list of values. But the similarity ceases here. The major difference between a linked list and array is that an array can hold values belonging to the same data type only whereas there is no such restriction on a linked list.
4. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
Ans: Prefix Notation: ^ – * +ABC – DE + FG
Postfix Notation: AB + C * DE – – FG + ^
5. What is data structure?
Ans: A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.
6. List out the areas in which data structures are applied extensively.
Ans: i) Compiler Design
ii) Operating System
iii) Database Management System
iv) Statistical analysis package
v) Numerical Analysis
vii) Artificial Intelligence
7. Explain quick sort algorithm.
Ans: Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.
8. What are Binary trees and why are they used in data structures?
Ans: A binary tree is one in which each node has at most two descendants – a node can have just one but it can’t have more than two.Clearly each node in a binary tree can have a left and/or a right descendant. The importance of a binary tree is that it can create a data structure that mimics a “yes/no” decision making process.