Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

Important Instructions to examiners:
1) The answers should be examined by key words and not as word-to-word as given in
The model answer scheme
...

3) The language errors such as grammatical, spelling errors should not be given more
Importance (Not applicable for subject English and Communication Skills)
...
The figures drawn by candidate and model answer may vary
...

5) Credits may be given step wise for numerical problems
...

6) In case of some questions credit may be given by judgment on part of examiner of
relevant answer based on candidate’s understanding
...

1
...

(Each type definition carries- 1Mark)
Ans:

PRIMITIVE DATASTRUCTURE
the primitive data structures are the basic data types that are available in most of the
programming languages
...

Example: Integer, character, string, Boolean

Page 1 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

NON-PRIMITIVE DATASTRUCTURE
The data structure that are derived from primary data structure is known as non-Primitive
data structure
...

Example: Arrays, Structure, Union, linked list, Stacks, Queue etc
...

(2 operation carries- 1 Mark)
Ans:
1
...
Searching
3
...
Insertion
5
...
Merging
...

(Sorting definition -1Mark, Types-1Mark)
Ans:

Sorting is the operation of arranging data or elements in some given order, numerically or
alphabetically
...

1
...

2
...
Because the large data may be in secondary storage
...

d) Give the principal of bubble sort
...

1
...
If necessary , swap (exchange) them
Sorting begins with 0th elements & it compares with 1st element in list
...
Like this all elements are compared with
next element & interchanged if required
...
In 2nd pass again comparisons starts with 0th element & 2nd largest element is
placed at second last position
...

Page 2 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

e) Define stack
...


f) List operations on trees
...

(Definition-2Marks)
Ans:

A graph is a weighted graph if a number (weight) is assigned to each edge
...


Page 3 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

B) Attempt any two:
a) Explain different approaches to design an algorithm
...
Top-Down Approach: A top-down approach starts with identifying major components
of system or program decomposing them into their lower level components & iterating
until desired level of module complexity is achieved
...

2
...
Starting from very
bottom, operations that provide layer of abstraction are implemented
b) Explain the linear search algorithm
...

(Algorithm-1 Mark, Explanation-2 Marks, Limitation-1Mark; any related algorithm can
be considered)
Ans: Linear search is the easiest search technique in which each element is scanned in a
sequential manner to locate the desire element
...
Linear search
is also called as „sequential search‟
...

2
...

4
...


21
1

11
2

91
3

19
4

We are searching for element 91
...
Until we find the target value or reach to the end of array
...

Algorithm:
Start
Accept n values from user i
...
array elements
...
e
...

Set i=0,flag=0
Compare A[i] with target
If(A[i] is a target)
Page 4 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

Set flag=1 go to step 7
Else
Move to next data element
i= i+1;
6
...
If(flag=1) then
Return i as position of target located
Else
Report as target not found
...
Stop
...

(Definition-1Mark, Explanation-3Marks)
Ans:

A queue, in which the last node is connected back to the first node to form a cycle, is
called as circular queue
...

Circular queues overcome the problem of unutilized space in linear queue implemented as
an array
...
e
...

After rear reaches the last position, i
...
MAX-1 in order to reuse the vacant positions, we
can bring rear back to the 0th position, if it is empty, and continue incrementing rear in
same manner as earlier
...
For deletion,
front will also have to be incremented circularly
...

If ((rear == MAX-1) and (front !=0)
Rear =0;
Else
Rear= rear +1;
Now we insert an element F at the beginning by bringing rear to the first position in the
queue
...


Page 5 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

In the above example, if another element, G is added to the queue, i
...
rear and front
coincide
...
Thus rear and
front cannot be used for both i
...
to check for empty queue as well as the condition for a
full queue
...
Thus to check for queue full condition there are
three methods
...
Use a counter to keep track of the number of elements in the queue
...

2
...
After add operation if rear = front
then will say that queue is full
...
By checking (rear + 1) % MAX== front
...


Subject Name: Data Structure Using 'C'

Attempt any four:

MARKS 16

a) Sort the given no
...

Numbers: 348, 14, 614, 5381, 47
(Each pass- 1 Mark)
Ans: 348, 14,614,5381,47
Pass 1: Numbers are sorted on least significant digit
...

P: 5, 6, 2, +, *, 12, 4, /, also evaluate P for final value
...


Step 2: Operators are moved between the two operands of the group
5*(6+2)-12/4
1
2
3
4
5
6
7
8
9
10

Input
5,6,2,+,*,12,4,/,6,2,+,*,12,4,/,2,+,*,12,4,/,+,*,12,4,/,*,12,4,/,12,4,/,4,/,/,End

Stack
Empty
5
5,6
5,6,2
5,8
40
40,12
40,12,4
40,3
37

Operation

6+2=8
5*8=40

12/4=3
40-3=37

c) Define the term:
i)
Node
ii)
Address
iii)
Null pointer
iv)
Next pointer for linked list
...

d) Explain the terms with the help of diagram:
i)
Siblings
ii)
Leaf Node
(Definition-1Mark, Example-1 Mark)
Ans:
i) Siblings: Any nodes that have the same parent
...
It does not have any child
...

(4 points each -1 Mark)
Ans:
Stack

Queue

In Stack insertion and deletion In Queue insertion and deletion
operations are performed at operations are performed at
same end
different end
In stack the element which is In Queue the element which is
inserted last is first to delete so inserted first is first to delete so it
it is called Last In first Out
is called first In first Out
In stack only one pointer is used In Queue two pointer is used
called Top
called front, rear
In Stack Memory is not wasted

In Queue memory can be wasted/
unusable in case of linear queue
...

(Program-2 Mark, Logic -2Mark, any relevant logic shall be considered)
Ans:

#include ...


Attempt any four:

MARKS 16

a) Define recursion
...

(Definition -1Mark, Logic of program- 3Marks)
Ans:

Definition: - Process of calling function itself is known as recursion in C programming
...
h>
int multiply(int,int);
int main(){
int a,b,product;
printf("Enter any two integers: ");
scanf("%d%d",&a,&b);
product = multiply(a,b);
printf("Multiplication of two integers is %d",product);
return 0;
}
Page 12 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

int multiply(int a,int b){
static int product=0,i=0;
if(i < a){
product = product + b;
i++;
multiply(a,b);
}
return product;
}
b) Describe priority queue and list its advantages
...

2) Two elements with the same priority are processed according to the order in which
they are added to the queue
...

 Keep the list sorted in increasing order
...

(Explanation -2Marks, example/diagram- 2Marks)
Ans:
Algorithm
Step-1: Initialize the Current pointer with the beginning of the List
...

Step-3: Move the Current pointer to point to the next node in the list and go to step-2, till
the list is not over or else quit
...

(Explanation of each traversal -1Marks, example with all traversal -1Marks)
Ans:
1
...

Procedure:Step 1:
Visit root node
Step 2:
Visit left sub tree in preorder
Step 3:
Visit right sub tree in preorder
2
...

Procedure:Step 1:
Visit left sub tree in inorder
Step 2:
Visit root node
Step 3:
Visit right sub tree in inorder
3
...

Procedure:Step 1:
Visit left sub tree in postorder
Step 2:
Visit right sub tree in postorder
Step 3:
Visit root node

Page 14 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

Example:Preorder: A, B, C
Inorder: B, A, C
Postorder: B, C, A

A

B

C

e) Draw the tree structure for the following expressions:
i)
(2a +5b) 3 (x-7y) 4
ii)
(a-3b) (2x-y) 3
(Each equation tree- 2Marks)
Ans:

f) What is Hashing? Give its significance
...

Significance of Hashing:1
...

2
...

3
...


Page 15 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330
4
...

(Explanation with example each complexity - 2Marks)
Ans:

Time complexity:Time complexity of a program/algorithm is the amount of computer time that it needs to
run to completion
...

Frequency count for algorithm B is n as a=a+1 is key statement executes n time as the loop
runs n times
...

Space complexity:Space complexity of a program/algorithm is the amount of memory that it needs to run to
completion
...


Variable space requirements: - It consists of space needed by structured variables
whose size depends on particular instance of variables
...


Page 16 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

b) Explain stack as an abstract data type
...

We use eltype to denote type of stack element & parameterize stack type with eltype
abstract typedef <> stack (eltype)
...

Formally stack may be defined as follows:
typedef struct stack
{
int data [size];
int top;
}stack;
size is constant, maximum number of elements that can be stored

c) Write a procedure to insert an element into a queue and to delete an element from a
queue
...

(Description- 2Marks, Node structure- 2Marks)
Ans:

Description:Doubly linked list is also called as two way linked list
...

Each node contains 3 fields:• Info field is used to store data
...

• A pointer field previous which contains pointer to previous node
Node structure:Previous
Link

N

1

N

Next
Link

Info
struct node
{
int info;
struct node * node;
struct node * prev;
} *start;
Page 18 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

e) Explain insertion of new node at start and at end in singly linked list
...
Create New Node
2
...
Make it‟s “Pointer” or “Next Field” as NULL
4
...
Make new node as Starting node

Inserting node at last in the SLL (Steps):
1
...
Fill Data into “Data Field“
3
...
Node is to be inserted at Last Position so we need to traverse SLL up to Last Node
...
Make link between last node and new node

Page 19 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

f) Consider the following tree
...

(Inorder -1 Mark; Pre order- 1 Marks; Postorder- 2 Marks)

Ans:

Inorder-D G B A H E I C F
Preorder:- A B D G C E H I F
Postorder:- G D B H I E F C A

5
...

(Solution-4 Marks Program-4 Marks)
Ans:

A= {11, 5, 21, 3, 29, 17, 2, 43}
Pre-condition for Binary search is array elements must be sorted in ascending order
...
Applying Bubble sort we sort the elements
of array
...
Low=0 high=7 k=29
Mid= (0+7)/2 = 3
Page 20 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

A[mid] =a [3] =11
29>11
k>a [mid]
ii
...
Low=mid+1
Mid= (6+7)/2=6
A[mid] =a [6] =29
A[mid] =k
Therefore key element is found at 6th position, no
...
Search is
successful
‘C’ program for Binary Search
...
h>
#include ...

(Correct Postfix Expression -8 Marks; Stepwise solution shall be consider)
Ans:

Resultant Postfix Expression is- ab↑c*d-ef/gh+/+

Page 23 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

c) Explain DFs with suitable example
...

Stack is used in the implementation of the depth first search
...
Mark it as waiting
...
Push all its adjacent nodes into
the stack &mark them as waiting
...
Repeat step 4 until stack is empty
...
The steps for the DFS will be as follows:

Page 24 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

a) Initially, push J onto stack as follows:
stack: J
b) Pop and print the top element J , and then push onto the stack all the neighbors of J as
follows:
Print J STACK D, K
c) Pop and print the top element K, and then push onto the stack all the unvisited
neighbors of k
Print KSTACK D, E, G
d) Pop and print the top element G, and then push onto the stack all the neighbors of G
...

e) Pop and print the top element C and then push onto the stack all the neighbors of C
Print C STACK D, E, F
f) Pop and print the top element F
Print F STACK D, E
Note that only neighbor D of F is not pushed onto the stack, since D has already been
pushed onto the stack
...
Accordingly,
the nodes which were printed,
J, K, G, C, F, E, D
These are the nodes reachable from J
...


Subject Name: Data Structure Using 'C'

Attempt any two:

MARKS 16

a) Explain push and POP operation on stack with algorithm and example
...

PUSH
A

PUSH B

2

2

1

1

B

0

A

A

0

Stack top

Stack top

Initially stack top is set to -1
...
e stack is empty
...

Algorithm
1
...
TOP = TOP + 1
3
...
Exit
POP: Pop operation is used to remove an element from stack
...

Algorithm:1
...
Else remove the Top most elements
3
...
TOP = TOP – 1
5
...

b) What is tree? Define any four terminologies related to tree and draw the tree
structure for following expression
(11a2 +7b3+5c) 4 + (3a3+4b2+8c) 3
...

(Any four terminology)
Root: It is special node in tree structure & the entire tree is referred through it
...

Child: All immediate successors of node are its children
...

Degree of node: The degree of node is number children of a node
...

Level: The level of node in binary tree is the root of tree has level 0
...

Depth: The depth of binary tree is the maximum level of any node in the tree expression
tree for
(11a2 +7b3+5c) 4 + (3a3+4b2+8c) 3

Page 27 of 30

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION
(Autonomous)
(ISO/IEC - 27001 - 2005 Certified)
SUMMER-15 EXAMINATION

Model Answer
Subject Code: 17330

Subject Name: Data Structure Using 'C'

c) Consider the graph ‘G’ in fig
...

Find indeg (Y) and outdeg (Y)
...

Find the path P of G using powers of the adjacency matrix A

---

Title: Data Structure Using C
Description: Hey folks it is a solved question paper which will help you to clear all your queries. Thank you

Buy These NotesPreview