Thursday, September 15, 2016
Data structure 1st annual 2014 iub past paper bsc solved
Data structure (1st annual 2014)
Q.No 1: what is data structure ? Define the basic data
structures with suitable examples.
Ans: In computer
science, a data structure is a way of storing data in a computer so that it can
be used efficiently. Or anything that can store data can be called as data
structure.
Basic data structures:
Anything that can store data can be called as data structured.
Examples: Integer,
float, Boolean, char etc, all are basic data structures.
Q.No.1(b): Describe different data structure operations
briefly.
Ans:
OPERATIONS
ON DATA STRUCTURE:
A data structure is created to define and process complex data. The data
in a data structure is processed using certain operations
·
Insertion: Adding new
data items into a data structure is called insertion.
·
Deletion: Removing data items from a data
structure is called deletion.
·
Searching: Finding specific data item in
data structure is called searching.
·
Traversing: Accessing
each record or item in a data structure exactly one for processing is called
traversing. It is also called visiting.
·
Sorting:Arranging data items in a data
structure into a specific order is called sorting.
· Merging: Combining two lists of data items into a single list is called merging.
Q.No.2(a): Convert the following infix expression into postfix notations:
Infix expression: A*(B+C)+X/Y
|
||
Char scanned
|
Stack
|
Postfix Expression
|
A
|
A
|
|
*
|
*
|
A
|
(
|
*(
|
A
|
B
|
*(
|
A B
|
+
|
*(+
|
A B
|
C
|
*(+
|
A B C
|
)
|
*
|
A B C +
|
+
|
+
|
A B C + *
|
X
|
+
|
A B C + * X
|
/
|
+/
|
A B C + * X
|
Y
|
+/
|
A B C + * X Y
|
+
|
A B C + * X Y /
|
|
Empty
|
A B C + * X Y / +
|
|
Q.No.2(b): Evaluate the following postfix expression using stack.
Postfix expression: 15,6,2,+,*,4,/
|
|
Char scanned
|
Stack
|
15
|
15
|
6
|
15,6
|
2
|
15,6,2
|
+
|
15,8
|
*
|
120
|
4
|
120,4
|
/
|
30
|
Q.No.3: Each node of linked list contains INFO and LINK fields. Write code or algorithm to perform the following operations.
(a) To append an element at the end
of linked list
(b) Count number of items in the
linked list
Solution(a):
Code to add element at the end of linked list:
Algorithm to add element
at the end of linked list:
1.
Input data to be inserted
2.
[Create a
new node] R=new node
3.
Rèdata=data
4.
Rèlink=NULL
5.
If (p==NULL)
(a) P=R
6.
Else
(a) Temp=p
(b) While(Tempèlink!=NULL)
(i)
Temp=Tempèlink
7.
Tempèlink=R
8.
Exit
|
Function
p=NULL;
append(int num)
{
node *temp, *r;
if(p
= = NULL)
{
temp = new node;
temp→data
= num;
temp→link = NULL;
}
else
{ temp=p;
while(temp→link!=NULL)
temp= temp→link;
r =
new node;
r→data
= num;
r→link = NULL;
temp→link
= r;
}
}
Solution(b):
Algorithm Function
Algorithm to count total
elements in linked list:
1.
Set temp=p and c=0
2.
While(temp!=NULL)
(i)
Temp=tempèlink;
(ii)
C++;
3.
return c;
4.
exit
|
count()
{
node *temp = p;
int c = 0;
while(temp != NULL)
{
temp = temp→link;
c ++;
}
return c;
}
Q.No.4(a): Describe the benefits of double linked list over single linked.
Ans: Benefits of double linked list over single linked list:
· A doubly linked list can be traversed in both directions
(forward and backward). A singly linked list can only be traversed
in one direction
·
A node on a doubly linked list may be deleted with little
trouble, since we have pointers to the previous and next nodes. A node on a
singly linked list cannot be removed unless we have the pointer to its predecessor
·
If we are at a node, the we can go at any node. But in
linked list, it is not possible to reach the previous node.
Insertion algorithm of circular Queue:
Solution(b):
1. If
((rear ==MAX -1&& front == 0) || (rear + 1 =front)) Then
2. Print “Queue is full”
3. If
(rear = MAX -1) Then [Check If REAR reaches end if QUEUE]
(i) Set rear = 0
Else
(a)
rear++; [Increment
REAR by 1]
(b)
arr[rear]
= item [End
of Step 3 if ]
4. If (front == -1) [Check if
QUEUE is empty]
Set front
= 0
5. Exit
Q.No.5(a): Explain the technique of insertion sort also
write algorithm
Insertion sort Algoritm
Description: Here A is an unsorted array having N elements.
1. Repeat For J = 2 to N
2. Set TEMP = A[J]
3. Set K = J - 1
4. Repeat While (K >= 1) and
(A[K] > TEMP)
5. Set A[K+1] = A[K]
6. Set K = K - 1
[End of While
Loop]
6. Set A[K+1] = TEMP
[End of For
Loop]
8.
Exit
Q.No.6(a): Describe the technique of binary search. what are
its limitation?
Suppose DATA is an array which is sorted in increasing numerical
order or,
Equivalently alphabetically.
Then there is extremely efficient algorithm called binary
Search which can be used to find the location LOC of a given
ITEM of information in
DATA. We indicate the general idea of this algorithm by means of
an idealized version
of a familiar everyday example.
Suppose one wants to find the location of some name in telephone
directory.
Obviously one does not perform a linear search. Rather one opens
the directory in the
middle to determine which half contains the name being sought.
Then one opens that half
in the middle to determine which quarter of the directory
contains the name. Then one
opens that quarter in the middle to determine which eighth of
the directory contains the
name. And so on. Eventually one finds the location of the name
since one is reducing the
number of possible locations for it in the directory.
The binary search algorithm applied to our array DATA works as
follows. During
each stage of our algorithm, our search for ITEM is reduced to
segments of elements of
DATA.
Limitations of binary search:
·
Binary search
algorithm can work only with the sorted array (either ascending or descending
order).
·
If the element which
we are trying to find is not available in the array, then it will start its
process all the way and finally only the output shows that the element is not
present in the list. This will be time consuming and waste of memory
allocation.
·
If the element to be
identified occurs more than once, then it will show the occurrence of the first
one.
Solution(b):
Description: Here A
is an array having N elements. X is the
value to be searched.
1. Repeat For J = 1 to N
2. If
(X == A[J]) Then
3. Print:
ITEM found at location J
4. Return
[End
of If]
[End
of For Loop]
5. If (J > N) Then
6. Print: ITEM doesn’t exist
[End of If]
7. Exit
Q.No.7(a): Discuss different
methodologies to design efficient algorithm:
Ans: Methodologies to design efficient algorithm:
1. Brute Force Algorithm(Trying all possible solutions):
Brute force Is a straightforward approach
to solving a problem, usually directly based on The problem’s statement and
definitions of the concepts involved.
Some examples of brute force
algorithms are:
·
Computing an (a > 0, n a nonnegative integer) by multiplying a*a*…*a
·
Computing n!
·
Selection sort
·
Bubble sort
·
Sequential search
·
Exhaustive search: Traveling
Salesman Problem, Knapsack problem.
2. Greedy
Algorithms "take what you can get now" strategy
It is based on trying best current (local) choice. Greedy
algorithms can run significantly faster than brute force ones. Unfortunately,
it is not always the case that a greedy strategy leads to the correct solution.
Examples:
·
Minimal spanning tree
·
Shortest distance in graphs
·
Greedy algorithm for the Knapsack problem
·
The coin exchange problem
·
Huffman trees for optimal encoding
3. Divide and Conquer:
It is based on dividing problems into sub
problems.
Divide-and-conquer algorithms are naturally implemented as recursive
procedures. The partial sub-problems leading to the one currently being solved
are automatically stored in the procedure call stack.
Examples of divide-and-conquer algorithms:
·
Computing
an (a > 0, n a nonnegative integer) by recursion
·
Binary
search in a sorted array (recursion)
·
Merge
sort algorithm, Quick sort algorithm
(recursion)
·
The
algorithm for solving the fake coin problem (recursion)
4. Dynamic Programming Algorithm:
It is
based on Remembering past results. The dynamic programming algorithm is
suitable for the observe the dependency of the sub problem. It is only used for Only for overlapping
sub problems
Examples:
·
Fibonacci
numbers
·
Warshall’s algorithm implemented by
iterations
Conclusion:
Comparison of the various algorithm design strategy are done on
the basis of various factors like complexity, memory required, stability etc .Usually a given problem can be solved using various approaches
however it is not wise to settle for the first that comes to mind. More often
than not, some approaches result in much more efficient solutions than
others. Consider again the Fibonacci
numbers computed recursively using the decrease-and-conquer approach, and
computed by iterations using dynamic programming. In the first case the
complexity is O(2n), while in the second case the complexity is O(n). On the
other hand, consider sorting based on decrease-and-conquer (insertion sort) and
brute force sorting. For almost sorted files insertion sort will give almost
linear complexity, while brute force sorting algorithms have quadratic
complexity.
Q.No.7(b): Reverse the element of stack using Queue.
#include<stdio.h>
#include<conio.h>
void
pushstack(int);
void popstack();
void
printstack();
void
pushqueue(int);
void popqueue();
void
reversestack();
int front, rear,
top, n, i, temp, stack[10], queue[10];
void main()
{
clrscr();
front = top =
rear = -1;
printf("Enter
the number of elements to be added in stack==");
scanf("%d",
&n);
if(n>10)
printf("The
number should be between 1 and 10");
else
{
for(i=0;
i<noe; i++) {
printf("Enter
the element==");
scanf("%d",
&temp);
pushstack(temp);
}
printstack();
reversestack();
}
getch();
}
/*-------------------------------------------------------------------------------*/
void
pushstack(int item)
{
top++;
stack[top] =
item;
}
/*--------------------------------------------------------------------------------*/
void popstack()
{
temp = stack[top];
top--;
pushqueue(temp);
}
/*--------------------------------------------------------------------------------*/
void
printstack()
{
for(i=top;
i>=0; i--)
printf("\n
Element %d of stack is %d", i, stack[i]);
}
/*--------------------------------------------------------------------------------*/
void
reversestack()
{
for(i = top;
i>= 0; i--)
popstack();
for(i=0; i<=
rear; i++)
popqueue();
printf("\n");
printstack();
}
/*---------------------------------------------------------------------------------*/
void
pushqueue(int item)
{
rear++;
queue[rear] =
item;
if(front == -1)
front = 0;
}
/*---------------------------------------------------------------------------------*/
void popqueue()
{
temp =
queue[front];
if(front ==
rear)
front = rear =
-1;
else
front++;
pushstack(temp);
}
Subscribe to:
Post Comments
(
Atom
)
itss soo good
ReplyDeleteThanks
Delete