C Programming and Data Structures

May/June 2008

SET- 4

1. (a) Define an Algorithm.

Ans: In solving a problem or to develop a program we should have two criteria.
1. algorithm
2. flow chart
Algorithm: An algorithm is a method of representing the step-by-step procedure for solving
a problem. An algorithm is very useful for finding the right answer to problem or to a difficult
problem by breaking the problem into simple cases.
Algorithm for in-order traversal (recursive):
Step 1: check if tree is empty by verifying root pointer R. Print tree empty if
R=NULL
Step 2: if leftptr(R)!=NULL then call in-order (leftptr(R))
Step 3: print data(R).
Step 4: if rightptr(R)!= NULL then call in-order(rightptr(R))
Step 5: return.
(b) What is the use of flow chart?
Ans: Flow chart is a diagrammatic representation of an algorithm. It is built using different types of
boxes and symbols. The operation to be performed is written in the box. All symbols are inter-
connected and processed to indicate the flow of information and processing.
Uses of flow chart:
1. Flow chart helps us to understand the program easily.
2. As different boxes are used to specify the type of operation performed, it helps in easy
understanding of complex programs.
(c) What are the different steps followed in program development ?
Ans: A ‘C ’ program has to pass through many phases for its successful execution and to achieve
desired output.
 Solved Question Papers C.63

The various steps involved in program development are as follows

1. Editing phase
2. Compilation phase
3. Linking phase
4. Execution phase

Editing Phase

In the editing phase, a C program is entered into a file through a text editor. Unix operating system
provides a text editor which can be accessed through the Command ‘Vi’ Modern, compiler vendors
provide Integrated Development Environment IDEs. The file is saved on the disk with an extension of
‘C’. Corrections in the program at later stages are done through these editors. Once the program has
been written, it requires to be translated into machine language.

Compilation Phase

This phase is carried out by a program called as compiler. Compiler translates the source code into
the object code. The compilation phase cannot be proceeded successfully until and unless the source
code is error-free. The compiler generates messages if it encounters syntactic errors in the source
code. The error-free source code is translated into object code and stored in a separate file with an
extension ‘.obj’.

Linking Phase

In this phase, the linker links all the files and functions with the object code under execution. For
example, if a user uses a ‘printf ’ function in his\ her program, the linker links the user program’s
apostrophe object code with the object code of the printf function. Now the object code is ready for
next phase.

Execution Phase

In this phase, the executable object code is loaded into the memory and the program execution begins.
We may encounter errors during the execution phase even though compilation phase is successful.
The errors may be run-time errors and logical errors.
2. Write a program to find the sum of a given series by using function with argument and
return value e= 2+3/1!-6/2!+9/3!-12/4!.....!
Ans:
Program:
#include<stdio.h>
#include<math.h>
long fact(int);
C.64 Solved Question Papers

void main()
{
int x,i,n;
float s=0,c;
clrscr();
printf("\n enter the value of x\t");
scanf("%d",&x);
/*perform the looping operation*/
for(i=0,n=0;i<=n;i=i+2,n++)
s=s+(pow(-1,n)*pow(x,i)/fact(i));
printf("\n the result is %f",s);
getch();
}
/* calling sub program*/
long fact(int x)
{
long int y=1;
while(x!=0)
{
y=y*x;
x--;
}
return y;

3. Write a program and explain the working of malloc() and calloc() functions.
Ans: Memory space is required by the variable in a program to calculate, and assign during execu-
tion. The process of allocating memory out runtime is known as dynamic memory allocation.
There are some memory management functions in C that can be used for allocating and freeing
memory during program execution.
Some memory allocation functions are
Malloc() Allocates required size of bytes and returns a pointer to the first byte of
allocated space.
Calloc() Allocates space for an array of elements, initializes them to zero and then
returns a pointer to the memory.
Free() Free previously allocated space.
Realloc Modifies the size of previously allocated space.
Memory allocation using malloc() function:
Block of memory may be allocated using malloc() function. Malloc() function reserves a block
of memory of specified size and returns a pointer of typed void.
 Solved Question Papers C.65

Syntax:-
Ptr=(cast-type#)malloc(byte size);
Ptr- pointer of cast type.
Malloc returns a pointer (of cast type) to an area of memory with the size of given bytes.
Example:- y=(int*)malloc(100*size of(int));
Malloc allocates a block of contiguous bytes. The allocation can fail if the space in the heap is
not sufficient. If it fails, it returns null.
Example program that uses a table of integers whose size will be specified interactively at
run time.
#include<stdio.h>
#define null 0
Main()
{
int *p,*table;
int size;
printf("enter size of table");
scanf("%d",&size);
printf("\n");
if(table=(int*)malloc(size*sizel of(int)==null)
{
printf("no space available");
exit(1);
printf("address of first byte is %u",table);
printf("input table values");
for(p=table;p<table+size;p++)
scanf("%d",&p);
for(p=table+size-1;p>=table;p--)
Printf("%d is stored address %u",*p,p);
}

Memory allocation using calloc() function:-

Calloc() is another memory allocation function that is normally used for requesting memory
space at run time for storing derived data types such as arrays and structures. Malloc allocates
a single block of storage, each of them, being of the same size, and then sets all bytes to zero.
The general form of calloc() is
Ptr=(cast_type*)calloc(n, elem_size);
The above statement allocates contiguous space for n blocks, each of size elem_size bytes. All
bytes are initialized to zero and a pointer to first byte of the allocated region is returned. If there
is not enough space a null pointer is returned. Calloc() allocates blocks of memory.
C.66 Solved Question Papers

Calloc takes two arguments which are number of elements to allocated memory and size in
bytes of a single variable.
Calloc initializes the allocated memory to zero.
#include<stdio.h>
include<stdio.h>
#define null 0
Main()
{
Char *buffer;
If(buffer=(char*)malloc(10))==null)
{
printf("malloc faile");
exit(1);
}
Printf("buffer of size %deated \n",msize(buffer));
Strcpy(buffer,"hyderabad");
Printf("buffer contains%s",buffer);
If(buffer=(char*)realloc(buffer,15)=!null)
{
Printf("reallocation failed");
Exit(1);
}
Printf("buffer size modified");
Printf("buffer still contains %s \n",buffer);
Strcpy("buffer", "secunderabad");
Printf("\n buffer now contains %s \n",buffer);
Free(buffer);
}

4 . Define structure and write the general format for declaring and accessing members.
Ans. Structure can store data items in consequent memory locations. The advantage of structures is
that the data items may be of different data types.
Declaring structures:
Struct student
{
Char name[20];
Int stno; (1)
};
 Solved Question Papers C.67

Memory allocation is as follows:

Struct tagname
{
Data type n1;
Data type n2;
};
With (1) no memory allocation is not done only the structure is defined for allocating.
Struct bokkbank
{
Char title[20];
Char author[15];
Int pages;
Float price;
};
Struct bokbankk bookk1,book2,bok3;
Tag name is optional.
Giving values to members:
The link between a member and a variable is established by using 'dot operator' or 'period
operator'.
Book1.pages=250;
Book1.price=28.50;
Also initialized using scanf( ) statement
Scanf("%s",book1.title);
Scanf("%d",bok1.pages);
Structure initialization:
Main ()
{
Static struct
{
Int weight;
Float height;
}
Student={60,180,75};
-----------------
-----------------
}
Also can be initialized as
Main ()
C.68 Solved Question Papers

{
Struct st_record
{
Int weight;
Float height;
};
Static struct st_record st1={60,180,75};
Static struct st_record st2={53,170,60};
-------------
-------------
}
(OR)

Struct st_recrd
{
Int weight;
Float height;
} st1={60,180,75};
Main (0
{
Static struct st_recrd st2={53,170,60};
---------------
----------------
}
Accessing members of structure:
Structure members can be accessed by writing variable name.member
Dot( . ) operator links structure variable to the data member. It is the highest precedence
operator and associatively is left to right.
Assigning values to structure:
One way is to assign values at the time of declaring structure variables.
Struct person p1={"ravi", "21", "male", "student"}
Another way is to assign values to each member separately as shown below.
Strcpy(p1.name, "ravi");
P1.age=21;
Strcpy(p1.gender, "male");
Strcpy(p1.occupation, "student");
Here is an example demonstrating the structure with initialized values.
/* structure with initialized values */
#include<stdio.h>
#include<conio.h>
Void main ( )
{
 Solved Question Papers C.69

Struct organization
{
bb Char name[20];
Char designation[20];
Int sal;
};
Struct organization emp1={"ramu", "secretary", "8000"};
Struct organization emp2={"raju", "manager", "18000"};
Printf("details of employee one =%c%c%d",emp1.name ,emp1.designation, emp1.sal);
Printf("details of employee one =%c%c%d",emp2.name ,emp2.designation, emp2.sal);
}

5. Describe various types of files with an example for each.

Ans: File: A file is a collection of records. Each record provides an information to the user. These
files are arranged on the disk and can be accessed through file handling information provided
by the standard 'C' library.
Basic operations on files
The files consists of large amount of data which can be read or modified depending upon the
requirement. The basic operations that are performed on files are
1. Opening a file
2. Reading or writing a file
3. Closing a file
These operations are carried out with the help of a structure FILE (stdio.h file) and a file pointer.
There are two types of files. They are
1. Sequential file
2. Random access file
1. Sequential file:
In a sequential file system, records are stored in a serial order and retrieved in the same order.
If a read operation is to be performed on the last record, then all the records before the last
record need to be read because of which a lot of time is wasted.
2. Random access file:
In sequential access of file, data is read from or written sequentially i.e., from beginning of the
file to end of the file in order. It is achieved using functions fprintf( ), fscanf( ), getc( ), putc( )
etc. In random access of a file, a particular part of a file can be accessed irrespective of other
parts.
Random access of files is achieved with the help of functions fseek( ), ftell( )
and rewind ( ) which are available in I/O library. The functionality of each of these functions
are given below.
C.70 Solved Question Papers
(a) ftell( ):
n= ftell(fp);
Here ‘n’ gives the current position of the pointer from beginning. It gives the information
regarding number of bytes to be read or written already.
(b) rewind( )
This function takes file pointer to the starting of the file, and resets it.
Syntax:
Rewind(fp);
This statement rewinds the file pointer fp to the beginning of the file.
(c) fseek( ):
fseek( ) is a file function that is used to move the file pointer to a desired location in the file. It
is generally used when a particular part of the file is to be accessed. The main purpose of the file
fseek( ) is to position the file pointer to any location on the stream.
Syntax:
Fseek(fileptr, offset, position);
‘fileptr’ is a file pointer
Offset:
It specifies the number or variable of type long to reposition the pointer forward and negative
integer is used to move the pointer backward.
Position:
It specifies the current position.
The values that can be assigned to position are
Value position
0 beginning of file
1 current position
2 end of file (EOF)
The fseek( ) returns zero, if all the operations are performed successful and returns -1 if an error
occurs such as EOF is marked.

Example:

Program:
#include<stdio.h>
#include<conio.h>
Main ( )
{
FILE *fp;
Long int n;
 Solved Question Papers C.71

Char c, fname[25];
Printf("enter the file name:\n");
Getc(fname);
Fp=fopen(fname,'w');
While(c=getchar( )!=EOF)
Putc(c,fp);
Fclose(fp);
Fp=fopen(fname,"r");
N=0;
While(!feof(fp))
{
Fseek(fp,n,0);
Printf("position of %c is %d\n",
getc(fp),ftell(fp));
Fclose(fp);
}

6. Write a program to explain selection sort. Which type of technique does it belong to?
Ans: Selection sort: In sorting technique, sorting is done by selecting the largest element in the
unsorted list and placing it at the appropriate position (by swapping).
In each pass, the largest element in the list is placed at an appropriate position. If there are ‘n’
elements in the list.
Æ in the first pass, all the elements are compared and largest element is placed at the last
position.
Æ in second pass, first n–1 elements are compared and process continues for a list of n–z
elements, then for n–3 elements and so on until first element.
If there are ‘n’ elements, we require n-1 passes.

Example:
Consider a list of elements 12, 21, 50, 14, 2, 20.
12 21 50 14 2 20
Pass 1: 12 21 20 14 2 50
Pass 2: 12 2 20 14 21 50
Pass 3: 12 2 14 20 21 50
Pass 4: 12 2 14 20 21 50
Pass 5: 2 12 14 20 21 50
In pass 1, the largest element is obtained by comparing from first element onwards. Here the
largest element is 50. So, the positions of 50 and nth element are interchanged as shown.
In pass 2, the first n-1 elements are compared and the largest element is obtained which is 21.
So, the position of 21 and (n–1)th element are interchanged.
C.72 Solved Question Papers

The process is repeated until all the elements are sorted.

Algorithm for selection sort:

Step 1: start.
Step 2: repeat through step 5 for i=n-1 to '0' do.
Step 3: [initializing]
Large=a[0]
Index=0
Step 4: repeat through step for j=1 to I do.
Step 5: [obtain the largest element in a pass]
If a[j] > large
Large=a[j]
Index=j;
Step 6: [placing the largest element in its proper position]
a[index] = a[i]
a[i] = large
end
C program for selection sort
Let us assume that an array named elements[] will hold the array to be sorted and maxsize is the
number of elements to be sorted. We will also assume that the sorting order is ascending in
nature.
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 500
void selection(int elements[], int maxsize);
int elements[MAXSIZE],maxsize;
int main()
{
int i;
printf("\nHow many elements you want to sort:");
scanf("%d",&maxsize);
printf("\nEnter the values one by one: ");
for (i = 0; i < maxsize; i++)
{
printf ("\nEnter element %i :",i);
scanf("%d",&elements[i]);
}
 Solved Question Papers C.73

printf("\nArray before sorting:\n");

for (i = 0; i < maxsize; i++)
printf("[%i], ",elements[i]);
printf ("\n");
selection(elements, maxsize);
printf("\nArray after sorting:\n");
for (i = 0; i < maxsize; i++)
printf("[%i], ", elements[i]);
}
void selection(int elements[], int array_size)
{
int i, j, k;
_________ ________ __ _
int min, temp;
for (i = 0; i < maxsize-1; i++)
{
min = i;
for (j = i+1; j < maxsize; j++)
{
if (elements[j] < elements[min])
min = j;
}
temp = elements[i];
elements[i] = elements[min];
elements[min] = temp;
}
}
Let us now analyze the efficiency of the selection sort. You can easily understand from the
algorithm that the first pass of the program does (maxsize - 1) comparisons. The next pass does
(maxsize - 2) comparisons and so on. Thus, the total number of comparisons at the end of the
sort would be :
(maxsize - 1) + (maxsize - 2) + + 1 = maxsize * (maxsize - 1) / 2 = O(maxsize2).
7. What is the difference between a queue and a circular queue? Explain circular
queue operations?
Queues are data structures that, like the stack, have restructions on where you can add and
remove elements.
Ans: Circular queue is a queue in which elements are stored in circular manner. Circular queue is
implemented using arrays.
Let us consider an array CQ that contains ‘k’ elements in which CQ[1] comes after CQ[k] in
C.74 Solved Question Papers

the array. A linear queue can be transformed to the circular queue when last room comes just
before the first room.
In circular queue, if an element is inserted when rear=k, then this element is assigned CQ[1] i.e.
instead of incrementing the rear value to k+1, rear is reset to 2. If there is only a single element,
the front=rear and if that element is deleted then front=null and rear=null, which indicate that
queue is empty. It is very easy to perform insertion and deletion operation on linear queue. At
the same time there are many drawbacks of implementing simple queues.
1. If one element is deleted, that empty memory location cannot be used again, whereas in circular
queues it can be used.
2. It is not possible to insert an element even at the beginning of the queue if that location is empty.
Because of these limitations, disk space is wasted.
In order to overcome these problem, circular queues are implemented.
The function queue_store and queue_retrieve would change in the case of a circular queue.
Void queue_store(char*p)
{
If((end+1==start)||(end+1-max&&start==0))
{
Printf("queue is full");
Return;
}
Arr[end]=p;
End++;
If(end==max)
End=0;
}
Char*queue_retrieve[void]
{
If(start==max)
Start=0;
If(start==end)
{
Printf("queue is empty");
}
Start++;
Return arr[start-1];
}
8. Explain tree traversal in detail.
Ans:
Tree traversal :
A tree can be traversed in three major ways. They are
a. in-order traversal
 Solved Question Papers C.75

b. pre-order traversal
c. post-order traversal
a. In-order traversal:
In-order traversal is given by following steps:
1. traverse the left sub-tree
2. process the root node
3. traverse the right sub-tree
Algorithm for in-order traversal (recursive):
Step 1: check if tree is empty by verifying root pointer R. Print tree empty if
R=NULL
Step 2: if leftptr(R)!=NULL then call in-order (leftptr(R))
Step 3: print data(R).
Step 4: if rightptr(R)!= NULL then call in-order(rightptr(R))
Step 5: return.
Example:
A

D
B

} E
C G

F
So the in-order of the binary tree in the figure above is C-B-A-E-F-D-G.
Pre-order traversal:
Pre-order traversal is defined as follows:
1. process the root node
2. traverse the left sub tree in pre-order.
3. traverse the right sub tree in pre- order
Algorithm for in-order traversal :
Step 1: check if tree is empty by verifying root pointer R
If R=NULLL, then print "tree empty"
Step 2: print data(R)
Step 3: if leftptr(R)!=NULL then call pre-order(leftptr(R))
Step 4: if rightptr(R)!=NULL call pre-order(rightptr(R))
Step 5: return
C.76 Solved Question Papers

Example:
A

D
B

E G
C

F
Pre-order traversal is A B C D E F G
Post-order traversal:
Post-order traversal is defined as follows:
1. traverse the left sub-tree
2. traverse the right sub-tree
3. process the root node.
Algorithm for post-order traversal :
Step 1: check if tree is empty by verifying root pointer R. Print tree empty if
R=NULL, then print "tree empty"
Step 2: if leftptr(R)!=NULL then call post-order (leftptr(R))
Step 3: Print data(R).
Step 4: if rightptr(R)!= NULL then call post-order(rightptr(R))
Step 5: return.
Example:
A

D
B

C E
G

F
Post-order traversal for the above tree is C-B-F-E-G-D-A