USN
1 / P / E / I / S
/ PESIT Bangalore South Campus
Hosur road, 1km before Electronic City, Bengaluru -100
Department of Information Science and Engineering

INTERNAL ASSESSMENT TEST - 1

Subject & Code : Data Structures & Applications (15CS33)

PART 1
1 / Define pointers. With the help of C code segment, show the usage of & and * operators. OR / 8
Ans. / A Pointer type holds address of some memory location. It is a user defined data type which creates special types of variables which can hold the address of primitive data type like char, int, float, double or user defined data type like function, pointer etc. or derived data type like array, structure, union, enum.
Every variable keeps two type of value.
1. Contain of variable or value of variable.
2. Address of variable where it has stored in the memory.
There are two operators used in pointers :- & the address operator and * the dereferencing operator.
* is also known as indirection operator which gives content of any variable.
& is also known as reference operator which gives address where variable has stored in memory. * and & operators always cancel to each other i.e. *&p=p
Ex. float i, *pi;
pi = &i; // stores address of i at pi
*pi = 10; // stores value 10
printf(“Number %f is stored at %p”, *pi, pi);
printf(“Number %f is stored at %p ”, i, &i);
2 / What do you understand by dynamic memory allocation? Explain any three functions that support dynamic allocation with suitable examples?
Ans. In dynamic memory allocation, required memory is allocated to variable(s) during run time. Here memory allocation is postponed to run time which helps efficient usage of memory. The user of any system can take correct decision on amount of memory to be used for his/her application only during run time. Dynamic memory allocation helps here.
C supports 3 functions - malloc( ), calloc( ) and realloc( ).
The C syntax of these functions –
i.  void *malloc(size_t size);
malloc allocates a block of memory of size bytes, and return a pointer to the block while successful allocation or returns NULL if unable to allocate block.
Ex. float f, *pf;
pf = (float *) malloc(5* sizeof(float));
here function malloc allocates (5* sizeof(float)) bytes block.
ii.  void *calloc(size_t elements, size_t element_size);
Allocate element block of (elements * element_size ) bytes, initialize to zero, return pointer to the block for successful allocation or returns NULL if unable to allocate block.
Ex. float f, *pf;
pf = (float *) calloc(5, sizeof(float));
here function calloc allocates memory for 5 consecutive blocks of size sizeof(float) bytes each.
iii.  void *realloc(void *ptr, size_t new_size);
A previously allocated block starting at ptr and change the block size to new_size.
}  For successful allocation, it returns pointer to resized block. If block size is increased, contents of old block may be copied to a completely different region. In this case, the pointer returned will be different from the ptr argument, and ptr will no longer point to a valid memory region.
}  If ptr is NULL, realloc is identical to malloc
Ex.
float f, *pf, *newpf;
pf = (float *) malloc(5*sizeof(float));
…
newpf = (float *) realloc(pf, 10* sizeof(float));
here, realloc increases the previously allocated memory (pointed by pf) size from 5*sizeof(float) to 10* sizeof(float). The newly allocated is pointed by pointer newpf. / 8
PART 2
3 / What is union? How is it different from structure? With suitable example show how union is declared and used in C?
Ans. A collection of one or more variables, typically of different types, grouped together under a single name for convenient handling; only one of its members is stored at a time.
·  a single variable may hold different types at different times
·  Storage is enough to hold largest member
·  Members are overlaid on top of each other
Union
{
int ival;
float fval;
char *sval;
} u;
//Show with a code snippet the usage of the union
Differences:
1.  For one structure variable , memory allocated is sum of the memory needed by each member; whereas in union, memory allocated is enough to hold the largest member.
2.  In union all it’s members share memory whereas in structure, memory is allocated for each member.
OR / 8
4 / What is structure? How is it different from arrays? With an example show how a structure can be used within another structure.
Ans. A structured type is a data type that is built from other types. It is a way of aggregating a collection of “things” of different types. They are comprising a number of members (or fields) of possibly different types, normally identified by a member name.
Differences from Arrays –
·  Arrays are structured type comprising a number of elements of the same type. Whereas structures are structured type comprising a number of members of possibly different types.
·  Arrays are identified by an array subscript or index. Whereas structures are identified by a member name.
Nested structure example:
struct date {
unsigned day;
unsigned month;
unsigned year;
};
struct Employee {
int ident;
char name[30];
double pay_rate;
struct date start_date; // date was defined earlier char *dept_name;
};
//Show how to access the members of this structure / 8
PART 3
5 / Name various operations that can be performed on data structure. Write a C function to Search a number in a list of numbers using binary search.
Ans. Operations on DS: Creating
•  Insertion
•  Deletion
•  Searching
•  Sorting
•  Merging
•  Traversing
Write 1 line for each.
//write the binary search function / 8
OR
6 / Discuss polynomial addition problem using array.
Ans. Refer class note / 8
PART 4
7 / Define stack. Write C functions to implement stack using array.
Ans. Stack is an ordered list where insertions and deletions are made at one end called top also known as LIFO structure. Eg. plate stacker, piling of CD’s etc.
Two methods -
–  Push: add item to the top of the stack
–  Pop: remove an item from the top of the stack
Write the functions for push and pop.
OR / 8
8 / a / Show the stack after each operation of the following sequence that starts with the empty stack: push(a), push(b), pop, push(c), push(d), pop.
Top = 0, Stack[top] = a
Top =1, stack[top]= b, stack[0]=a
Popped b, top = 0, stack[top]=a
Top = 1, stack[top]=c, stack[0]=a
Top = 2, stack[top]=d, stack[1]=c, stack[0]=a
Popped d, top = 1, stack[top]=c, stack[0]=a / 3
b / Write the postfix form of the following infix expression i) ((A + B) * C - (D-E)) ^(F+G) show the stack content.
Ans. Show steps in tabular form. Final result is: AB+C*DE- - FG+^
Evaluate the resultant postfix expression for A=D=5, B=3,C=2, E=7, F=1, G=2.
Show the stack in tabular form. Final result is : 5832. / 5
PART 5
9 / List applications of stacks. Using stack write an algorithm to determine if a given string is palindrome and print suitable message as output.
Ans. There are various applications of stacks. Few are –
Convert an arithmetic expression from infix to postfix/prefix.
Evaluate a postfix expression
Check whether a string is palindrome
Reverse a string, etc.
Algorithm to check a string is palindrome or not-
1.  Set top = -1 and flag=1
2.  Read a string of n characters and Push the characters in a stack, S
For i=0 to n-1 do
Read string[i];
Push(S, string[i]);
3.  Compare the characters of the string with the popped item of the stack
For i=0 to (n/2)-1 do
If(string[i]=pop( ))
Continue;
Else
flag = 0;
break;
4.  If flag=1 write ”string is palindrome”
Else write “string is not a palindrome”
OR / 8
10 / Write a C program to check whether a given expression is a valid postfix expression or not. / 8
Ans.
void main( )
{
int i = 0; char postfix[100];
while(postfix[i] != ‘\0’)
{
if(isalnum(postfix[i]) ) push(opstk, postfix[i]);
else
{
op2 = pop(opstk);
op1 = pop(opstk);
switch(postfix[i])
{
Case ‘+’ :
Case ‘-’ :
Case ‘*’ :
Case ‘/’ :
Case ‘^’ :
Case ‘%’ : push(opstk,’t’) //where t is an arbitrary character.
default: break;
}
i++;
}
}
pop(opstk);
if(top= = -1) printf(“\nExpression is valid”);
else printf(“\nExpression is invalid”);
}
Write push and pop function.

B.E 3rd Semester