Data Structure
Previous year question paper with solutions for Data Structure May-2018
Our website provides solved previous year question paper for Data Structure May-2018. Doing preparation from the previous year question paper helps you to get good marks in exams. From our DS question paper bank, students can download solved previous year question paper. The solutions to these previous year question paper are very easy to understand.
These Questions are downloaded from www.brpaper.com You can also download previous years question papers of 10th and 12th (PSEB & CBSE), B-Tech, Diploma, BBA, BCA, MBA, MCA, M-Tech, PGDCA, B-Com, BSc-IT, MSC-IT.
Print this page
Question paper 1
-
(a) Explain the Big-Oh computation for each of the following control structures:
-
Sequencing
-
If-then-else
-
“for” loop
-
“While” loop
Answer:
Explain the Big-on Computation for each of the following control structures.
-
Sequencing => Statement +1: The total time is
Statement +2: found by adding the times for all statement
Statement +K -> Total time
-> time (statement+1) + time (statement +2) +….+ time (statement K)
If each statement is “simple” (only involves basic open)
Then the time for each statement is constant and the total time is also constant: 0(1).
-
If-then-else => if (condition) 2
Sequence of statement 1
In this situation
Eithen sequence else
Will execute ,or Sequence of statement 2
Sequence 2 will
Execute
Therefore , the worse case time is the slowest of the slowest of the
Two possibilities : max ( time ( Sequence ) time (sequence 2) So what if-then-else statement would be O(N).
-
for loop => for (i=o; i<N; l+) sequence of Statement
-> The loop executes N time, So the Sequence d statement also executes N times. Since we the statements are 0(1), the total tin=me for the for loop is N*0(1), Which is 0(N) overall.
White i=0,--------.
White (i<n)—n+1
S+ ;------n
;------n
F(n)=3n+2
Q(n)
-
(b) What is a data structure ? what are the common operation that can be performed on a data structure?
Answer:
Data may be or in many different ways . the mathematical model of a particular Organization of dater is called a dater Structure
=> following are the Different operations performed on a dater Structure
(i) Traversing => Accessing Each exactly once so that items in the record may be processed.
(ii) Searching => Finding the location of the record with a key value , Or finding the locations of all Seconds Which satisfy once or more conditions
(iii)Inserting => Adding a new record to the Structure
(iv)deleting => Removing a record froing the Structure
(v)Sorting => Arron record in some loo cat order E.g - Numerically or other types.
(vi) Merging => Combing the record in two different sorted files into a single sorted file.
2 (a) Write algorithm to evaluate a given postfix expression. Apply the same on the following postfix expression:
7 2 3 * - 4 ^ 8 2 / +
Answer:
Evaluation Rules => 1. White Reading the expression from left to right push the element in the stack if it is
-
Lob the two operands from the stack if the element is an operator and then evaluate it.
-
Push back the resent of the evaluation Repeat it fill the end of the expression.
Expression 1 2 3 * +
1 2 3 * +
Push Push 3 Pop pop
-
2 2
-
1
Push
Left to rig Evaluation -
Step
Input symbol
operation
Stack
Calculation
1.
1
Push
1
2.
2
Push
1,2
3.
3
Push
1,2,3
4.
*
Pop 2 element
1
Evaluate
2 3
5.
Push result=(2)
1,2,6
6.
+
Pop 2 element
Empty
& Evaluate
1+6
7.
Push result (7)
7
8.
No More elements
Empty
7
(pop)
result
=> 7 2 3 *- + ^ 8 2 / +
=> 7 2 *3
=> Scan left to right => 7 – 2 * 3 4
=> if is come => (7 -2) 3 8/2
Put it in the stack => (7-2) 3^4 + (8/2)
=> It are count => (7-2 *3) + (8/2)
Remove two lost oprond from stack and put oprater B/W then
=> Exit
-
(b) What is a stack ? How it is represented in memory? Discuss linked and sequential representations with examples.
Answer:
Stack is a liner data structure which follows a port order in which the are performed the order may be last in first out (HFO) or (Fine) first in las out.
=> These are mainly following these basic are performed in the stock
Push =>Adds an them in stock if two stock is full then It is sold to be an overflow
PoP=> Remove an from the stock.
Peak or Top=> Returns top element of the stack
=> These are two ways to implement of the stack
=> Using Array
=> Using linked list.
200
204
208
212
216
220
204
208
232
236
240
249
11
9
17
89
1
90
19
5
3
23
43
99
0
1
2
3
4
5
6
7
8
9
10
11
33
4900
4800
22
5000
4900
II
5000
Inbox
Linked top 4800
Initial stack paring
There element And
Top have address
4800
3 (a) Define queue Write algorithm how you insert and delete an element from a circular queue Write its applications also.
Answer:
Queue => It is a container of objects that are inserted and removed according to the FIFO Principle two operations are performed =>
En queue means to Insert an item into the back of the queue,
De queue = means removing the front item.
=> Operations on a circular Queue
Front => Get the front item from Queue
Rear => Get the lost item from queue
En queue => steps (1) Check whether queue is full
Check rear = Size 1 front =0II
(rear = front -1)
(2) if it is full thon display Queue is full if queue is not full then, check if (rear =size -1
Insert element.
De queue => Steps => (1) check whether queue is Empty means check (front==-1).
(2) if it is empty then display Queue is empty if queue is not empty then step
(3) Check if (front = = rear) if It is true then set front =rear =-1 else Check if (front = Size-1) if it is true then set front=0 and return the element
=> following are the Applications of Queue->
=> Direct application
=> waiting lists
=> Access to shored resources (E.S printer.
=>Indirect applications => Auxiliary data structure for Also.
=> component of other data structure.
(b) write an algorithm to check for parentheses matching in an expression using stack.
Answer:
parentheses means that Each opening symbol has a Corresponding bring Symbol and the part of parentheses are properly nested.
From by thon ds paste import stack
Def par check ( Symbol string)
S= Stack
Balanced = tone
Index = 0
Balanced [7*(2+4)=3)]
7* 6-3
42-3=39
While index sten (symbol string)
Symbol = Symbol string (index)
If symbol = = “(“.
S Push (symbol)
[7*(2+4)-3)]
[7*(6-3)]
[7*3]=21
If S is Empty ():
Balanced = false
Else
S pop
Index =index +1
If balanced and s is empty ():
Return false
Print (par checker (‘((()))’))
Print par checker (‘(()’))
4 (a) What do you mean by an array ? How it is represented in memory ? Write algorithms to insert and delete an element from an array.
Answer:
Array=> It is a data structure used in many languges in order to store data of a kind like integer string etc.
=>Just as you world expect elements are consecutive is memory with no holes or empty space in between except required for alignment purpose.
=>Insertion (A,N, Element m LOC)
Step 1= set I=N-1
Step 2 = Repeat white > Loc -2
-
Set A (I+s) = A (I)
-
Set I=I-1
Step 3= Set A [Los -1] ELEMENT
Step 4 , Set N=N+1
Step 5 => Exit
Index
Los
0
1
1
1
2
2
2
3
3
3
4
4
4
5
5
=>Detection of an element from Array=>
=> Detection (A.N, Element , Loc )
Step 1=> Set Element A[Loc]
Step 2 => Write set I= Loc
Step 3 => Repeat while I L N
-
Set A [I]=A[I+1]
-
Set I=I+1
Step4 => Set N=N-1
Step5 => Exit
-
(b) What are space matrices ? Explain their types at implementation.
Answer:
What are sparse matrices=>
Sparse matrix or sparse array is a matrix in which most of the elements are Zero. By contrast if most of the elements are nonzero then matrix is considered dense.
=>these are seven available space matrix types:-
. CSC – matrix : compressed column format
.CSR – matrix : Compressed sparse Row matrix.
. coo-matrix: A Sparse matrix in coo format.
.bsr-matrix : Block sparse Row matrix
.dia –matrix : Sparse matrix with Diagonal storage
.dok-matrix : of keys based sparse matrix
-
Matrix: Row based list of lists sparse matrix
=>Implementation => Sparse matrix and gts representations
St 1 (using Arrays and Linked listed ) A matrix is a this-dimensioned data object made of M rows and n colums , therefore baring total m n Value if most of the elements of
The matrix have O value
Then it is called a
Sparse matrix
-
5 (a) Write an algorithm to insert a new node in the existing sorted single linked list. Discuss your algorithm with the help of a suitable example.
Answer:
Following are the steps required for Inseration as first rods in linked list [Insert first start value]
Step 1 =>It AVAIL=Null , then write OVERELONG
Step 2 => set new = AVAIL and
Set AVAIL = Link [AVAIL]
Step 3 => Set INFO [NEW] VALUE
Step 4 => Set Link [NEW] Start and
Set START =NEW
Step 5 => Exit.
This Algorithm inserts first node in for field containing VALUE in a linked list with START starting address.
Start
10
P/20
Q/30
R/X
40 10 20 30
A/10
AVAIL
10
50
60
x
40 50 60
NEW=40 50-AVNIL=50 –VALUE-A
Step 1 : It AVAIL =NULL Then
Write Over Flow return
Step 2 : Set NEW := AVAIL and
Set AVAIL = LINK [AVAIL]
Step 3 : Set INFO [NEW] = VALUE
Step 4 : Set LINK [NEW] LINK [LOC]
And set Link {LOC] NEW
Step 5: Exit
This algorithm will insert a node in a linked list after the node with address LOC with Value .
(b) Explain the advantages and disadvantages of doubly linked list over singly linked list.
Answer:
Following are Advantages of disadvantages of Doubly linked list over singly linked list.
Advantages =>(1) A DLL can be traversed in both for and backward direction.
(2) The delete operation in DLL is more if pointer to the node to be deleted is Given.
(3) We can quickly insert a new node before a Given node.
In DLL we can Get the previous node using previous pointer I singly linked to delete a node pointer to the previous node is needed.
Disadvantages over Singly linked list.
=> the operation in singly linked list require an extra pointer previous to be maintained
E g-> in inseration we need to modify previous points together with next pointers.
e.g-> in following functions for insertions at different positing we need 1 or 2 extra steps to set previous pointer.
(a) write algorithm for merge sort and discuss the same with the help of an example.
(b) Compare liner and binary search with suitable examples.
Answer:
(a) Merge Sort 38,27,43,3,9,82,10
=>Divide the array
Into two parts.
=>Divide the
array Into
Two
parts again
=>Break each element
Into single parts
=>Sort the elements from
Smallest to largest.
=> Merge the divide sorted arrays to
=> They array has been sorted.
(b) Linear binary search win example?
Linear search
Binary search
1.
The element are to Random Order
1.
The Element are Sorted Order.
2.
Worst Case time Complexity O(n)
2.
The Worst case time complexity is (log2n)
3.
Access is slow
3.
Access is faster.
4.
Single and multi dimer Array is sorts Used
4.
Only Single dimensional Array is sorted Used.
Example of Linear searches.
Example of Binary search
=>
Find out 37 from the Given data structural
0 1 2 3 4 5 6
20
35
37
40
45
50
51
Return=2
Calculate middle =(low+ high)/2.
=(0+8)/2=4
0 1 2 3 4 5 6 7 8
20
35
37
40
45
50
51
55
67
First Middle Last
if 37== array [middle]
Return middle
Else if 37 <array [middle]
high = middle -1
Else if 37> array [middle]
low = middle +1
7 (a) Write an algorithm for bubble sort and apply the same the following sequence of elements:
12 6 4 9 14 3 7
Answer:
Bubble sort => something referred to as sinking sort is a simple sorting that repeatedly steps through the list Compares adjacent element and them if they are the words order.
6
5
2
6
12
Example => (1)
5
8
2
6
12
5
2
8
6
12
5
2
6
8
12
5
2
6
8
12
(2)
5
2
6
8
12
2
5
6
8
12
Steps -> Step 1-> start with the 1st element and compare It with the adjacent elements so swap.
Step 2-> Now compare 2nd 3rd element 8>2 So Swap
Step 3-> Next look at the 3rd 4th element 8>6 so swap.
Step 4-> Compare 4th 5th element 8<12 So you need no swap.
Step 5->End the Result after swap is 1.
Step 1->
12
6
4
9
14
3
7
6
12
4
9
14
3
7
6
4
12
9
14
3
7
6
4
9
12
14
3
7
6
4
9
12
14
3
7
6
4
9
12
14
3
7
6
4
9
12
3
14
7
6
4
9
2
3
7
4
Step 2=>
6
4
9
12
3
7
14
4
6
9
12
3
7
14
4
6
9
12
3
7
14
4
6
9
3
12
7
4
4
6
9
3
7
12
14
Step 3=>
4
6
9
3
7
2
14
4
6
3
9
7
12
14
4
6
3
7
9
12
14
Step 4=>
4
6
3
7
9
12
14
4
3
6
7
9
12
14
4
3
6
7
9
12
14
Step 5=>
4
3
6
7
9
12
14
3
4
6
7
9
12
14
(b) Define Binary tree. Compare contiguous and linked memory representation of binary tree.
Answer:
Binary tree=> A binary tree an important class of a tree data structure in which a node can have at most two children.
Linked Representation =>
This is the linked representation of Binary tree.
Contiguous representation of Binary tree=>
Suppose T is a complete binary tree then only single linear array TREE is very as follow->
A
B
C
D
D
D
E
8 (a) What are Binary search tress? How you can insert and delete an element in a binary search tree? Write algorithms and explain with suitable example. Give example.
Answer:
Binary search trees=> It is define as in which the value of all the nodes of the left subtree than the value of the node.
The value of all the nodes of the right subtree of any node are greater than value of the node.
Insertion in Binary search tree=>
We have to follow the B S T properties so we can’t insert any new node any where in a binary search tree.
->To insert an element we first search that element and if the element is not found then we insert it.
->By Using an temporary pointer then go to the place where the node is going to be inserted
Insert (I,n)
Temp= T root
Y = NULL
White temp I =NULL
Y = temp
If n data < temp data
Temp = temp left
Else
Temp = temp right
N parent = Y
If Y= NULL
T root =n
Else if n data <y data
Y left =n
Else
Y right =n
= Deletion in Binary Search tree=> We will a subtree with another one We transplant one subtree n place of anther.
=>DELETE (T,Z)
If Z left == Null
TRANSPLANT (T ,Z, Z. left)
Else
Y= MINIMUM (z. right) minimum element in right subtree.
If y. parent ? =Z “ Z is not direct child.
TRANSPLANT (T, Y, Y right )
y. right =z right
y. right . Parent =y
TRANSPLANT (T, Z, y)
Y= left =z. left
Y left parent=y
(b) Discuss Binary tree traversals with suitable examples.
Answer:
Binary Tree traversal=> It is a processed vising each node in the tree exactly Once visiting each node in a Graph Should be done in a Systematic manner. If search result in a visit to all the vertices It is called a traversal.
Traversal techniques=>
(a)->pre order traversal
(b)->In order Traversal
(c)->Post order traversal.
(a) Pre order traversal To traverse a binary tree in pre order operations ->
1. Visit the road.
2. Traverse the left sub tree of root.
3. Traverse the right sub tree of root.
Example
Pre order traversal
7,1,0,3,2,5,4,6,9,8,10
(b) In order traversal=> TO traverse a binary tree in in order traversal.
Operations=> 1. Traverse the left most tree.
2. Visit the root.
3. Traverse the right most sub tree.
In order traversal=
0,1,2,3,4,5,6,7,8,9,10
(c) Post order traversal=> TO traversal a binary tree in post order tree easel
1. Operations => 1. Traverse the left sub tree
2. Traverse the right sub tree of root
3. Visit the root.
Post order traversal=
0,2,4,6,5,3,1,8,10,9,7.
Q9. (a) Discuss the row major and column major order of storing data in two dimension arrays.
Answer:
Elements of an array can be stores in column major layout or Row major layout -> for an array stored in column major layout
The element of the columns are Contiguous in memory In Row major layout the element of the rows are contiguous.
=>Array layout is also called order format and representation the order in while element are stored Can be important for integration.
(b) Compare array and link list.
Answer:
ARRAY
LINKED LIST
Basic
It is a consistent set of a fixed number of data items
->It is an ordered set comprising a variate no g data items.
Size
Spexified During declaration
->No need to specify ; grow and shrink during execution.
->Element location is allocated during compile time.
->element positions is assigned during run time.
->order of element
->stored
-> Stored Randomly
Access
->Direct Access
Deletion
->Slow relatively as
Shifting requlred
->Easier fast and efficient
->Binary & linear search
->Linear search
Memory
->Less
->More
(c) Briefly explain representation of linked using static and dynamic data structures.
Answer:
Representation of linked using static dynamic data Structures =>
=>Static or sequential array representation =>
->The linked list will be maintained or represented by two para arrays of same sixes one array for the actual data item in called field of the node other array for the address is called the next field of the nodes ->
=>Dynamic array representation
=>A Linked list is dynamic data structure
The Number of nodes in a list are not fixed and can Grow and shrink on demand Linked list Itself is a dynamic data structure.
(d) What is recursion ? Give Example.
Answer:
It is simply an already active method being in by Itself directly or being in rocked by another method indirectly
Example=>List traversal such as in a liner search or computing the factorial Function While stand examples of multiple recussion include tree traversal such as in a first search.
(e) Wrote algorithm for selection sort.
Answer:
Sorting algorithm- It is a place Compo based algorithm List is divided into two parts
Sorted part => At the left end
Unsorted part=> Right rand
Ex Algorithm
I=0
20
12
10
15
2
Min Value at Index 1
I-=1
20
12
10
15
2
Min Value at Index 2
I=2
20
1
10
15
2
Min Value at Index 2
I=3
20
12
10
15
2
Min Value at Index 4
2
12
10
15
20
Swapping