operating system interview questions -3

1. What are rings in Windows NT?

Windows NT uses protection mechanism called rings provides by the process to
implement separation between the user mode and kernel mode.

2. What is Executive in Windows NT?

In Windows NT, executive refers to the operating system code that runs in kernel
mode.

3. What are the sub-components of I/O manager in Windows NT?

> Network redirector/ Server
> Cache manager.
> File systems
> Network driver
> Device driver

4. What are DDks? Name an operating system that includes this feature.

DDks are device driver kits, which are equivalent to SDKs for writing device
drivers. Windows NT includes DDks.

5. What level of security does Windows NT meets?

C2 level security.

6. How are devices represented in UNIX?

All devices are represented by files called special files that are located in/dev directory. Thus, device files and other files are named and accessed in the same way. A 'regular file' is just an ordinary data file in the disk. A
'block special file' represents a device with characteristics similar to a disk (data transfer in terms of blocks). A 'character special file' represents a device with characteristics similar to a keyboard (data transfer is by stream of
bits in sequential order).

7. What is 'inode'?

All UNIX files have its description stored in a structure called 'inode'. The inode contains info about the file-size, its location, time of last access, time of last modification, permission and so on. Directories are also represented as files and have an associated inode. In addition to descriptions about the file, the inode contains pointers to the data blocks of the file. If the file is large, inode has indirect pointer to a block of pointers to additional data
blocks (this further aggregates for larger files). A block is typically 8k.
Inode consists of the following fields:
> File owner identifier
> File type
> File access permissions
> File access times
> Number of links
> File size
> Location of the file data

8. Brief about the directory representation in UNIX

A Unix directory is a file containing a correspondence between filenames and inodes. A directory is a special file that the kernel maintains. Only kernel modifies directories, but processes can read directories. The contents of a
directory are a list of filename and inode number pairs. When new directories are created, kernel makes two entries named '.' (refers to the directory itself) and '..' (refers to parent directory). System call for creating directory is mkdir (pathname, mode).

9. What are the Unix system calls for I/O?

> open(pathname,flag,mode) - open file
> creat(pathname,mode) - create file
> close(filedes) - close an open file
> read(filedes,buffer,bytes) - read data from an open file
> write(filedes,buffer,bytes) - write data to an open file
> lseek(filedes,offset,from) - position an open file
> dup(filedes) - duplicate an existing file descriptor
> dup2(oldfd,newfd) - duplicate to a desired file descriptor
> fcntl(filedes,cmd,arg) - change properties of an open file
> ioctl(filedes,request,arg) - change the behaviour of an open file
The difference between fcntl anf ioctl is that the former is intended for any open file, while the latter is for device-specific operations.

10. How do you change File Access Permissions?
Every file has following attributes:
> owner's user ID ( 16 bit integer )
> owner's group ID ( 16 bit integer )
> File access mode word
'r w x -r w x- r w x'
(user permission-group permission-others permission)
r-read, w-write, x-execute
To change the access mode, we use chmod(filename,mode).
Example 1:
To change mode of myfile to 'rw-rw-r--' (ie. read, write permission for user -
read,write permission for group - only read permission for others) we give the
args as:
chmod(myfile,0664) .
Each operation is represented by discrete values
'r' is 4
'w' is 2
'x' is 1
Therefore, for 'rw' the value is 6(4+2).
Example 2:
To change mode of myfile to 'rwxr--r--' we give the args as:
chmod(myfile,0744).

11. What are links and symbolic links in UNIX file system?
A link is a second name (not a file) for a file. Links can be used to assign more than one name to a file, but cannot be used to assign a directory more than one name or link filenames on different computers. Symbolic link 'is' a file that only contains the name of another file.Operation on the symbolic link is directed to the file pointed by the it.Both the limitations of links are eliminated in symbolic links.Commands for linking files are:
Link ln filename1 filename2
Symbolic link ln -s filename1 filename2

12. What is a FIFO?

FIFO are otherwise called as 'named pipes'. FIFO (first-in-first-out) is a special file which is said to be data transient. Once data is read from named pipe, it cannot be read again. Also, data can be read only in the order written. It is used in interprocess communication where a process writes to one end of the pipe (producer) and the other reads from the other end (consumer).

13. How do you create special files like named pipes and device files?

The system call mknod creates special files in the following sequence.
1. kernel assigns new inode,
2. sets the file type to indicate that the file is a pipe, directory or special file,
3. If it is a device file, it makes the other entries like major, minor device numbers.
For example:
If the device is a disk, major device number refers to the disk controller and minor device number is the disk.

14. Discuss the mount and unmount system calls

The privileged mount system call is used to attach a file system to a directory of another file system; the unmount system call detaches a file system. When you mount another file system on to your directory, you are essentially splicing one directory tree onto a branch in another directory tree. The first argument to mount call is the mount point, that is , a directory in the current file naming system. The second argument is the file system to mount to that point. When you insert a cdrom to your unix system's drive, the file system in the cdrom automatically mounts to /dev/cdrom in your system.

15. How does the inode map to data block of a file?

Inode has 13 block addresses. The first 10 are direct block addresses of the first 10 data blocks in the file. The 11th address points to a one-level index block. The 12th address points to a two-level (double in-direction) index block.The 13th address points to a three-level(triple in-direction)index block. This provides a very large maximum file size with efficient access to large files,but also small files are accessed directly in one disk read.

16. What is a shell?

A shell is an interactive user interface to an operating system services that allows an user to enter commands as character strings or through a graphical user interface. The shell converts them to system calls to the OS or forks off a process to execute the command. System call results and other information from the OS are presented to the user through an interactive interface. Commonly used shells are sh,csh,ks etc.

Read more »

operating system interview questions -2

1. Explain the popular multiprocessor thread-scheduling strategies.

> Load Sharing: Processes are not assigned to a particular processor. A global
queue of threads is maintained. Each processor, when idle, selects a thread from
this queue. Note that load balancing refers to a scheme where work is allocated
to processors on a more permanent basis.
> Gang Scheduling: A set of related threads is scheduled to run on a set of
processors at the same time, on a 1-to-1 basis. Closely related threads /
processes may be scheduled this way to reduce synchronization blocking, and
minimize process switching. Group scheduling predated this strategy.
> Dedicated processor assignment: Provides implicit scheduling defined by
assignment of threads to processors. For the duration of program execution, each
program is allocated a set of processors equal in number to the number of
threads in the program. Processors are chosen from the available pool.
> Dynamic scheduling: The number of thread in a program can be altered during
the course of execution.

2. When does the condition 'rendezvous' arise?

In message passing, it is the condition in which, both, the sender and receiver
are blocked until the message is delivered.

3. What is a trap and trapdoor?

Trapdoor is a secret undocumented entry point into a program used to grant
access without normal methods of access authentication. A trap is a software
interrupt, usually the result of an error condition.

4. What are local and global page replacements?

Local replacement means that an incoming page is brought in only to the relevant
process' address space. Global replacement policy allows any page frame from any
process to be replaced. The latter is applicable to variable partitions model
only.

5. Define latency, transfer and seek time with respect to disk I/O.

Seek time is the time required to move the disk arm to the required track.
Rotational delay or latency is the time it takes for the beginning of the
required sector to reach the head. Sum of seek time (if any) and latency is the
access time. Time taken to actually transfer a span of data is transfer time.

6. Describe the Buddy system of memory allocation.

Free memory is maintained in linked lists, each of equal sized blocks. Any such
block is of size 2^k. When some memory is required by a process, the block size
of next higher order is chosen, and broken into two. Note that the two such
pieces differ in address only in their kth bit. Such pieces are called buddies.
When any used block is freed, the OS checks to see if its buddy is also free. If
so, it is rejoined, and put into the original free-block linked-list.

7. What is time-stamping?

It is a technique proposed by Lamport, used to order events in a distributed system without the use of clocks. This scheme is intended to order events consisting of the transmission of messages. Each system 'i' in the network maintains a counter Ci. Every time a system transmits a message, it increments its counter by 1 and attaches the time-stamp Ti to the message. When a message
is received, the receiving system 'j' sets its counter Cj to 1 more than the maximum of its current value and the incoming time-stamp Ti. At each site, the ordering of messages is determined by the following rules: For messages x from site i and y from site j, x precedes y if one of the following conditions holds....(a) if Ti Increased speed and memory capacity of microprocessors together with the support fir virtual memory and
> Growth of client server computing .

8. What are the four layers that Windows NT have in order to achieve independence?

> Hardware abstraction layer
> Kernel
> Subsystems

> System Services.

9. What is SMP?

To achieve maximum efficiency and reliability a mode of operation known as
symmetric multiprocessing is used. In essence, with SMP any process or threads
can be assigned to any processor.

10. What are the key object oriented concepts used by Windows NT?
> Encapsulation
> Object class and instance

11. Is Windows NT a full blown object oriented operating system? Give reasons.

No Windows NT is not so, because its not implemented in object oriented language
and the data structures reside within one executive component and are not
represented as objects and it does not support object oriented capabilities .

12. What is a drawback of MVT?

It does not have the features like
> ability to support multiple processors
> virtual storage
> source level debugging

13. What is process spawning?

When the OS at the explicit request of another process creates a process, this
action is called process spawning.

14. How many jobs can be run concurrently on MVT?

15 jobs

15. List out some reasons for process termination.

> Normal completion
> Time limit exceeded
> Memory unavailable
> Bounds violation
> Protection error
> Arithmetic error
> Time overrun
> I/O failure
> Invalid instruction
> Privileged instruction
> Data misuse
> Operator or OS intervention
> Parent termination.

16. What are the reasons for process suspension?

> swapping
> interactive user request
> timing
> parent process request

17. What is process migration?

It is the transfer of sufficient amount of the state of process from one machine
to the target machine

18. What is mutant?

In Windows NT a mutant provides kernel mode or user mode mutual exclusion with
the notion of ownership.

19. What is an idle thread?
The special thread a dispatcher will execute when no ready thread is found.

20. What is FtDisk?

It is a fault tolerance disk driver for Windows NT.

21. What are the possible threads a thread can have?

> Ready
> Standby
> Running
> Waiting
> Transition
> Terminated.

Read more »

operating system interview questions -1

1. When is a system in safe state?

The set of dispatchable processes is in a safe state if there exists at least one temporal order in which all processes can be run to completion without resulting in a deadlock.

2. What is cycle stealing?

We encounter cycle stealing in the context of Direct Memory Access (DMA). Either the DMA controller can use the data bus when the CPU does not need it, or it may force the CPU to temporarily suspend operation. The latter technique is called cycle stealing. Note that cycle stealing can be done only at specific break points in an instruction cycle.

3. What is meant by arm-stickiness?

If one or a few processes have a high access rate to data on one track of a storage disk, then they may monopolize the device by repeated requests to that track. This generally happens with most common device scheduling algorithms (LIFO, SSTF, C-SCAN, etc). High-density multisurface disks are more likely to be affected by this than low density ones.

4. What are the stipulations of C2 level security?

C2 level security provides for:
> Discretionary Access Control
> Identification and Authentication
> Auditing
> Resource reuse

5. What is busy waiting?

The repeated execution of a loop of code while waiting for an event to occur is called busy-waiting. The CPU is not engaged in any real productive activity during this period, and the process does not progress toward completion.

6. What are short-, long- and medium-term scheduling?

Long term scheduler determines which programs are admitted to the system for processing. It controls the degree of multiprogramming. Once admitted, a job becomes a process.
Medium term scheduling is part of the swapping function. This relates to processes that are in a blocked or suspended state. They are swapped out of real-memory until they are ready to execute. The swapping-in decision is based on memory-management criteria.Short term scheduler, also know as a dispatcher executes most frequently, and makes the finest-grained decision of which process should execute next. This scheduler is invoked whenever an event occurs. It may lead to interruption of one process by preemption.

7. What are turnaround time and response time?

Turnaround time is the interval between the submission of a job and its completion. Response time is the interval between submission of a request, and the first response to that request.

8. What are the typical elements of a process image?

> User data: Modifiable part of user space. May include program data, user stack area, and programs that may be modified. > User program: The instructions to be executed.
> System Stack: Each process has one or more LIFO stacks associated with it. Used to store parameters and calling addresses for procedure and system calls.
> Process control Block (PCB): Info needed by the OS to control processes.

9. What is the Translation Lookaside Buffer (TLB)?

In a cached system, the base addresses of the last few referenced pages is maintained in registers called the TLB that aids in faster lookup. TLB contains those page-table entries that have been most recently used. Normally, each virtual memory reference causes 2 physical memory accesses-- one to fetch appropriate page-table entry, and one to fetch the desired data. Using TLB in-between, this is reduced to just one physical memory access in cases of
TLB-hit.

10. What is the resident set and working set of a process?

Resident set is that portion of the process image that is actually in real-memory at a particular instant. Working set is that subset of resident set that is actually needed for execution. (Relate this to the variable-window size method for swapping techniques.)

11. Explain the concept of Reentrancy.

It is a useful, memory-saving technique for multiprogrammed timesharing systems. A Reentrant Procedure is one in which multiple users can share a single copy of a program during the same period. Reentrancy has 2 key aspects: The program code cannot modify itself, and the local data for each user process must be stored separately. Thus, the permanent part is the code, and the temporary part is the pointer back to the calling program and local variables used by that program.
Each execution instance is called activation. It executes the code in the permanent part, but has its own copy of local variables/parameters. The temporary part associated with each activation is the activation record.Generally, the activation record is kept on the stack.

Note: A reentrant procedure can be interrupted and called by an interrupting program, and still execute correctly on returning to the procedure.

12. Explain Belady's Anomaly ?

Also called FIFO anomaly. Usually, on increasing the number of frames allocated to a process' virtual memory, the process execution is faster, because fewer page faults occur. Sometimes, the reverse happens, i.e., the execution time increases even when more frames are allocated to the process. This is Belady's Anomaly. This is true for certain page reference patterns.

13. What is a binary semaphore? What is its use?

A binary semaphore is one, which takes only 0 and 1 as values. They are used to implement mutual exclusion and synchronize concurrent processes.

14. What is thrashing?

It is a phenomenon in virtual memory schemes when the processor spends most of its time swapping pages, rather than executing instructions. This is due to an inordinate number of page faults.

15. List the Coffman's conditions that lead to a deadlock.

> Mutual Exclusion: Only one process may use a critical resource at a time.
> Hold & Wait: A process may be allocated some resources while waiting for others.
> No Pre-emption: No resource can be forcible removed from a process holding it.
> Circular Wait: A closed chain of processes exist such that each process holds at least one resource needed by another process in the chain.

Read more »

queue programs in c -5

Question 5.Write program that implements a priority queue using an array ?

Ans :

#include 
#include 

#define MAX 5

struct data
{
 char job[MAX] ;
 int prno ;
 int ord ;
} ;

struct pque
{
 struct data d[MAX] ;
 int front ;
 int rear ;
} ;

void initpque ( struct pque * ) ;
void add ( struct pque *, struct data ) ;
struct data delete ( struct pque * ) ;

void main( )
{
 struct pque q ;
 struct data dt, temp ;
 int i, j = 0 ;

 clrscr( ) ;

 initpque ( &q ) ;

 printf ( "Enter Job description (max 4 chars) and its priority\n" ) ;
 printf ( "Lower the priority number, higher the priority\n" ) ;
 printf ( "Job     Priority\n" ) ;

 for ( i = 0 ; i < MAX ; i++ )  {   scanf ( "%s %d", &dt.job, &dt.prno ) ;   dt.ord = j++ ;   add ( &q, dt ) ;  }  printf ( "\n" ) ;   printf ( "Process jobs prioritywise\n" ) ;  printf ( "Job\tPriority\n" ) ;   for ( i = 0 ; i < MAX ; i++ )  {   temp  = delete ( &q ) ;   printf ( "%s\t%d\n", temp.job, temp.prno ) ;  }  printf ( "\n" ) ;   getch( ) ; }  /* initialises data members */ void initpque ( struct pque *pq ) {  int i ;   pq -> front = pq -> rear = -1 ;
 for ( i = 0 ; i < MAX ; i++ )  {   strcpy ( pq -> d[i].job, '\0' ) ;
  pq -> d[i].prno = pq -> d[i].ord = 0 ;
 }
}

/* adds item to the priority queue */
void add ( struct pque *pq, struct data dt )
{
 struct data temp ;
 int i, j ;

 if ( pq -> rear == MAX - 1 )
 {
  printf ( "\nQueue is full." ) ;
  return ;
 }

 pq -> rear++ ;
 pq -> d[pq -> rear] = dt ;

 if ( pq -> front == -1 )
  pq -> front = 0 ;

 for ( i = pq -> front ; i <= pq -> rear ; i++ )
 {
  for ( j = i + 1 ; j <= pq -> rear ; j++ )
  {
   if ( pq -> d[i].prno > pq -> d[j].prno )
   {
    temp = pq -> d[i] ;
    pq -> d[i] = pq -> d[j] ;
    pq -> d[j] = temp ;
   }
   else
   {
    if ( pq -> d[i].prno == pq -> d[j].prno )
    {
     if ( pq -> d[i].ord > pq -> d[j].ord )
     {
      temp = pq -> d[i] ;
      pq -> d[i] = pq -> d[j] ;
      pq -> d[j] = temp ;
     }
    }
   }
  }
 }
}

/* removes item from priority queue */
struct data  delete ( struct pque *pq )
{
 struct data  t ;
 strcpy ( t.job, "" ) ;
 t.prno = 0 ;
 t.ord = 0 ;

 if ( pq -> front == -1 )
 {
  printf ( "\nQueue is Empty.\n" ) ;
  return t ;
 }

 t = pq -> d[pq -> front] ;
 pq -> d[pq -> front] = t ;
 if ( pq -> front == pq -> rear )
   pq -> front = pq -> rear = -1 ;
 else
   pq -> front++ ;

 return  t ;
}

Read more »

queue programs in c -4

Question 4.Write program that implements deque using an array ?
Ans :

#include 

#include 



#define MAX 10



void addqatbeg ( int *, int, int *, int * ) ;

void addqatend ( int *, int, int *, int * ) ;

int delqatbeg ( int *, int *, int * ) ;

int delqatend ( int *, int *, int * ) ;

void display ( int * ) ;

int count ( int * ) ;



void main( )

{

	int arr[MAX] ;

	int front, rear, i, n ;



	clrscr( ) ;



	/* initialises data members */

	front = rear = -1 ;

	for ( i = 0 ; i < MAX ; i++ )

		arr[i] = 0 ;



	addqatend ( arr, 17, &front, &rear ) ;

	addqatbeg ( arr, 10, &front, &rear ) ;

	addqatend ( arr, 8, &front, &rear ) ;

	addqatbeg ( arr, -9, &front, &rear ) ;

	addqatend ( arr, 13, &front, &rear ) ;

	addqatbeg ( arr, 28, &front, &rear ) ;

	addqatend ( arr, 14, &front, &rear ) ;

	addqatbeg ( arr, 5, &front, &rear ) ;

	addqatend ( arr, 25, &front, &rear ) ;

	addqatbeg ( arr, 6, &front, &rear ) ;

	addqatend ( arr, 21, &front, &rear ) ;

	addqatbeg ( arr, 11, &front, &rear ) ;



	printf ( "\nElements in a deque: " ) ;

	display ( arr ) ;



	n = count ( arr ) ;

	printf ( "\nTotal number of elements in deque: %d", n ) ;



	i = delqatbeg ( arr, &front, &rear ) ;

	printf ( "\nItem extracted: %d", i ) ;



	i = delqatbeg ( arr, &front, &rear ) ;

	printf ( "\nItem extracted:%d", i ) ;



	i = delqatbeg ( arr, &front, &rear ) ;

	printf ( "\nItem extracted:%d", i ) ;



	i = delqatbeg ( arr, &front, &rear ) ;

	printf ( "\nItem extracted: %d", i ) ;



	printf ( "\nElements in a deque after deletion: " ) ;

	display ( arr ) ;



	addqatend ( arr, 16, &front, &rear ) ;

	addqatend ( arr, 7, &front, &rear ) ;



	printf ( "\nElements in a deque after addition: " ) ;

	display ( arr ) ;



	i = delqatend ( arr, &front, &rear ) ;

	printf ( "\nItem extracted: %d", i ) ;



	i = delqatend ( arr, &front, &rear ) ;

	printf ( "\nItem extracted: %d", i ) ;



	printf ( "\nElements in a deque after deletion: " ) ;

	display ( arr ) ;



	n = count ( arr ) ;

	printf ( "\nTotal number of elements in deque: %d", n ) ;



	getch( ) ;

}



/* adds an element at the beginning of a deque */

void addqatbeg ( int *arr, int item, int *pfront, int *prear )

{

	int i, k, c ;



	if ( *pfront == 0 && *prear == MAX - 1 )

	{

		printf ( "\nDeque is full.\n" ) ;

		return ;

	}



	if ( *pfront == -1 )

	{

		*pfront = *prear = 0 ;

		arr[*pfront] = item ;

		return ;

	}



	if ( *prear != MAX - 1 )

	{

		c = count ( arr ) ;

		k = *prear + 1 ;

		for ( i = 1 ; i <= c ; i++ )

		{

			arr[k] = arr[k - 1] ;

			k-- ;

		}

		arr[k] = item ;

		*pfront = k ;

		( *prear )++ ;

	}

	else

	{

		( *pfront )-- ;

		arr[*pfront] = item ;

	}

}



/* adds an element at the end of a deque */

void addqatend ( int *arr, int item, int *pfront, int *prear )

{

	int i, k ;



	if ( *pfront == 0 && *prear == MAX - 1 )

	{

		printf ( "\nDeque is full.\n" ) ;

		return ;

	}



	if ( *pfront == -1 )

	{

		*prear = *pfront = 0 ;

		arr[*prear] = item ;

		return ;

	}



	if ( *prear == MAX - 1 )

	{

		k = *pfront - 1 ;

		for ( i = *pfront - 1 ; i < *prear ; i++ )

		{

			k = i ;

			if ( k == MAX - 1 )

				arr[k] = 0 ;

			else

				arr[k] = arr[i + 1] ;

		}

		( *prear )-- ;

		( *pfront )-- ;

	}

	( *prear )++ ;

	arr[*prear] = item ;

}



/* removes an element from the *pfront end of deque */

int delqatbeg ( int *arr, int *pfront, int *prear )

{

	int item ;



	if ( *pfront == -1 )

	{

		printf ( "\nDeque is empty.\n" ) ;

		return 0 ;

	}



	item = arr[*pfront] ;

	arr[*pfront] = 0 ;



	if ( *pfront == *prear )

		*pfront = *prear = -1 ;

	else

		( *pfront )++ ;



	return item ;

}



/* removes an element from the *prear end of the deque */

int delqatend ( int *arr, int *pfront, int *prear )

{

	int item ;



	if ( *pfront == -1 )

	{

		printf ( "\nDeque is empty.\n" ) ;

		return 0 ;

	}



	item = arr[*prear] ;

	arr[*prear] = 0 ;

	( *prear )-- ;

	if ( *prear == -1 )

		*pfront = -1 ;

	return item ;

}



/* displays elements of a deque */

void display ( int *arr )

{

	int i ;



	printf ( "\n front->" ) ;

	for ( i = 0 ; i < MAX ; i++ )

		printf ( "\t%d", arr[i] ) ;

	printf ( " <-rear" ) ;

}



/* counts the total number of elements in deque */

int count ( int *arr )

{

	int c = 0, i ;



	for ( i = 0 ; i < MAX ; i++ )

	{

		if ( arr[i] != 0 )

			c++ ;

	}

	return c ;

}

Read more »

queue programs in c - 3

Question .Write program that implements circular queue as an array ?

Ans :

#include 

#include 



#define MAX 10



void addq ( int *, int, int *, int * ) ;

int delq ( int *, int *, int * ) ;

void display ( int * ) ;



void main( )

{

	int arr[MAX] ;

	int i, front, rear ;



	clrscr( ) ;



	/* initialise data member */

	front = rear = -1 ;

	for ( i = 0 ; i < MAX ; i++ )

		arr[i] = 0 ;



	addq ( arr, 14, &front, &rear ) ;

	addq ( arr, 22, &front, &rear ) ;

	addq ( arr, 13, &front, &rear ) ;

	addq ( arr, -6, &front, &rear ) ;

	addq ( arr, 25, &front, &rear ) ;



	printf ( "\nElements in the circular queue: " ) ;

	display ( arr ) ;



	i = delq ( arr, &front, &rear ) ;

	printf ( "Item deleted: %d", i ) ;



	i = delq ( arr, &front, &rear ) ;

	printf ( "\nItem deleted: %d", i ) ;



	printf ( "\nElements in the circular queue after deletion: " ) ;

	display ( arr ) ;



	addq ( arr, 21, &front, &rear ) ;

	addq ( arr, 17, &front, &rear ) ;

	addq ( arr, 18, &front, &rear ) ;

	addq ( arr, 9, &front, &rear ) ;

	addq ( arr, 20, &front, &rear ) ;



	printf ( "Elements in the circular queue after addition: " ) ;

	display ( arr ) ;



	addq ( arr, 32, &front, &rear ) ;



	printf ( "Elements in the circular queue after addition: " ) ;

	display ( arr ) ;



	getch( ) ;

}



/* adds an element to the queue */

void addq ( int *arr, int item, int *pfront, int *prear )

{

	if ( ( *prear == MAX - 1 && *pfront == 0 ) || (  *prear + 1 == *pfront ) )

	{

		printf ( "\nQueue is full." ) ;

		return ;

	}



	if ( *prear == MAX - 1 )

		*prear = 0 ;

	else

		( *prear )++ ;



	arr[*prear] = item ;



	if ( *pfront == -1 )

		*pfront = 0 ;

}



/* removes an element from the queue */

int delq ( int *arr, int *pfront, int *prear )

{

	int data ;



	if ( *pfront == -1 )

	{

		printf ( "\nQueue is empty." ) ;

		return NULL ;

	}



	data = arr[*pfront] ;

	arr[*pfront] = 0 ;



	if ( *pfront == *prear )

	{

		*pfront = -1 ;

		*prear = -1 ;

	}

	else

	{

		if ( *pfront == MAX - 1 )

			*pfront = 0 ;

		else

			( *pfront )++ ;

	}

	return data ;

}



/* displays element in a queue */

void display ( int * arr )

{

	int i ;

	printf ( "\n" ) ;

	for ( i = 0 ; i < MAX ; i++ )

		printf ( "%d\t", arr[i] ) ;

	printf ( "\n" ) ;

}

Read more »

queue programs in c -2

Question 2.Write program that implements queue as a linked list

Ans :

#include 

#include 



struct node

{

	int data ;

	struct node *link ;

} ;



struct queue

{

	struct node *front ;

	struct node *rear ;

} ;



void initqueue ( struct queue * ) ;

void addq ( struct queue *, int ) ;

int delq ( struct queue * ) ;

void delqueue ( struct queue * ) ;



void main( )

{

	struct queue a ;

	int i ;



	clrscr( ) ;



	initqueue ( &a ) ;



	addq ( &a, 11 ) ;

	addq ( &a, -8 ) ;

	addq ( &a, 23 ) ;

	addq ( &a, 19 ) ;

	addq ( &a, 15 ) ;

	addq ( &a, 16 ) ;

	addq ( &a, 28 ) ;



	i = delq ( &a ) ;

	printf ( "\nItem extracted: %d", i ) ;



	i = delq ( &a ) ;

	printf ( "\nItem extracted: %d", i ) ;



	i = delq ( &a ) ;

	printf ( "\nItem extracted: %d", i ) ;



	delqueue ( &a ) ;



	getch( ) ;

}



/* initialises data member */

void initqueue ( struct queue *q )

{

	q -> front = q -> rear = NULL ;

}



/* adds an element to the queue */

void addq ( struct queue *q, int item )

{

	struct node *temp ;



	temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

	if ( temp == NULL )

		printf ( "\nQueue is full." ) ;



	temp -> data = item ;

	temp -> link = NULL ;



	if ( q -> front == NULL )

	{

		q -> rear = q -> front = temp ;

		return ;

	}



	q -> rear -> link = temp ;

	q -> rear = q -> rear -> link ;

}



/* removes an element from the queue */

int delq ( struct queue * q )

{

	struct node *temp ;

	int item ;



	if ( q -> front == NULL )

	{

		printf ( "\nQueue is empty." ) ;

		return NULL ;

	}



	item = q -> front  -> data ;

	temp = q -> front ;

	q -> front = q -> front -> link ;

	free ( temp ) ;

	return item ;

}



/* deallocates memory */

void delqueue ( struct queue *q )

{

	struct node *temp ;



	if ( q -> front == NULL )

		return ;



	while ( q -> front != NULL )

	{

		temp = q -> front ;

		q -> front = q -> front -> link ;

		free ( temp ) ;

	}

}

Read more »

queue programs in c -1

Question 1.Write program that implements queue as an array ?

Ans :

#include 

#include 



#define MAX 10



void addq ( int *, int, int *, int * ) ;

int delq ( int *, int *, int * ) ;



void main( )

{

	int arr[MAX] ;

	int front = -1, rear = -1, i ;



	clrscr( ) ;



	addq ( arr, 23, &front, &rear ) ;

	addq ( arr, 9, &front, &rear ) ;

	addq ( arr, 11, &front, &rear ) ;

	addq ( arr, -10, &front, &rear ) ;

	addq ( arr, 25, &front, &rear ) ;

	addq ( arr, 16, &front, &rear ) ;

	addq ( arr, 17, &front, &rear ) ;

	addq ( arr, 22, &front, &rear ) ;

	addq ( arr, 19, &front, &rear ) ;

	addq ( arr, 30, &front, &rear ) ;

	addq ( arr, 32, &front, &rear ) ;



	i = delq ( arr, &front, &rear ) ;

	printf ( "\nItem deleted: %d", i ) ;



	i = delq ( arr, &front, &rear ) ;

	printf ( "\nItem deleted: %d", i ) ;



	i = delq ( arr, &front, &rear ) ;

	printf ( "\nItem deleted: %d", i ) ;



	getch( ) ;

}



/* adds an element to the queue */

void addq ( int *arr, int item, int *pfront, int *prear  )

{

	if ( *prear == MAX - 1 )

	{

		printf ( "\nQueue is full." ) ;

		return ;

	}



	( *prear )++ ;

	arr[*prear] = item ;



	if ( *pfront == -1 )

		*pfront = 0 ;

}



/* removes an element from the queue */

int delq ( int *arr, int *pfront, int *prear )

{

	int data ;



	if ( *pfront == -1 )

	{

		printf ( "\nQueue is Empty." ) ;

		return NULL ;

	}



	data = arr[*pfront] ;

	arr[*pfront] = 0 ;

	if ( *pfront == *prear )

		 *pfront = *prear = -1 ;

	else

		 ( *pfront )++ ;



	return  data ;

}

Read more »

stack programs in c -7

Question 7.Write program to evaluate an epression entered in postfix form ?

Ans :

#include 

#include 

#include 

#include 

#include 



#define MAX 50



struct postfix

{

	int stack[MAX] ;

	int top, nn ;

	char *s ;

} ;



void initpostfix ( struct postfix * ) ;

void setexpr ( struct postfix *, char * ) ;

void push ( struct postfix *, int ) ;

int pop ( struct postfix * ) ;

void calculate ( struct postfix * ) ;

void show ( struct postfix ) ;



void main( )

{

	struct postfix q ;

	char expr[MAX] ;



	clrscr( ) ;



	initpostfix ( &q ) ;





	printf ( "\nEnter postfix expression to be evaluated: " ) ;

	gets ( expr ) ;



	setexpr ( &q, expr ) ;

	calculate ( &q ) ;

	show ( q ) ;



	getch( ) ;

}



/* initializes data members */

void initpostfix ( struct postfix *p )

{

	p -> top = -1 ;

}



/* sets s to point to the given expr. */

void setexpr ( struct postfix *p, char *str )

{

	p -> s = str ;

}



/* adds digit to the stack */

void push ( struct postfix *p, int item )

{

	if ( p -> top == MAX - 1 )

		printf ( "\nStack is full." ) ;

	else

	{

		p -> top++ ;

		p -> stack[p -> top] = item ;

	}

}



/* pops digit from the stack */

int pop ( struct postfix *p )

{

	int data ;



	if ( p -> top == -1 )

	{

		printf ( "\nStack is empty." ) ;

			return NULL ;

	}



	data = p -> stack[p -> top] ;

	p -> top-- ;



	return data ;

}



/* evaluates the postfix expression */

void calculate( struct postfix *p )

{

	int n1, n2, n3 ;

	while ( *( p -> s ) )

	{

		/* skip whitespace, if any */

		if ( *( p -> s ) == ' ' || *( p -> s ) == '\t' )

		{

			p -> s++ ;

			continue ;

		}



		/* if digit is encountered */

		if ( isdigit ( *( p -> s ) ) )

		{

			p -> nn = *( p -> s ) - '0' ;

			push ( p, p -> nn ) ;

		}

		else

		{

			/* if operator is encountered */

			n1 = pop ( p ) ;

			n2 = pop ( p ) ;

			switch ( *( p -> s ) )

			{

				case '+' :

					  n3 = n2 + n1 ;

					  break ;



				case '-' :

					  n3 = n2 - n1 ;

					  break ;



				case '/' :

					  n3 = n2 / n1 ;

					  break ;



				case '*' :

					  n3 = n2 * n1 ;

					  break ;



				case '%' :

					  n3 = n2 % n1 ;

					  break ;



				case '$' :

					  n3 = pow ( n2 , n1 ) ;

					  break ;



				default :

					  printf ( "Unknown operator" ) ;

					  exit ( 1 ) ;

			}



			push ( p, n3 ) ;

		}

		p -> s++ ;

	}

}



/* displays the result */

void show ( struct postfix p )

{

	p.nn = pop ( &p ) ;

	printf ( "Result is: %d", p.nn ) ;

}

Read more »

stack programs in c -6

Question 6.Write Program to convert an expression in postfix form to an infix form ?

Ans :

#include 

#include 

#include 



#define MAX 50



struct postfix

{

	char stack[MAX][MAX], target[MAX] ;

	char temp1[2], temp2[2] ;

	char str1[MAX], str2[MAX], str3[MAX] ;

	int i, top ;

} ;



void initpostfix ( struct postfix * ) ;

void setexpr ( struct postfix *, char * ) ;

void push ( struct postfix *, char * ) ;

void pop ( struct postfix *, char * ) ;

void convert ( struct postfix * ) ;

void show ( struct postfix ) ;



void main( )

{

	struct postfix q ;

	char expr[MAX] ;



	clrscr( ) ;



	initpostfix ( &q ) ;



	printf ( "\nEnter an expression in postfix form: " ) ;

	gets ( expr ) ;



	setexpr ( &q, expr ) ;

	convert ( &q ) ;



	printf ( "\nThe infix expression is: " ) ;

	show ( q ) ;



	getch( ) ;

}



/* initializes data member */

void initpostfix ( struct postfix *p )

{

	p -> i = 0 ;

	p -> top = -1 ;

	strcpy ( p -> target, "" ) ;

}



/* copies given expression to target string */

void setexpr ( struct postfix *p, char *c )

{

	strcpy ( p -> target, c ) ;

}



/* adds an expr. to the stack */

void push ( struct postfix *p, char *str )

{

	if ( p -> top == MAX - 1 )

		printf ( "\nStack is full." ) ;

	else

	{

		p -> top++ ;

		strcpy ( p -> stack[p -> top], str ) ;

	}

}



/* pops an expr. from the stack */

void pop ( struct postfix *p, char *a )

{

	if ( p -> top == -1 )

		printf ( "\nStack  is empty." ) ;

	else

	{

		strcpy ( a, p -> stack[p -> top] ) ;

		p -> top-- ;

	}

}



/* converts given expr. to infix form */

void convert ( struct postfix *p )

{

	while ( p -> target[p -> i] )

	{

		/* skip whitespace, if any */

		if( p -> target[p -> i] == ' ' )

			p -> i++ ;

		if ( p -> target[p -> i] == '%' || p -> target[p -> i] == '*' ||

			 p -> target[p -> i] == '-' || p -> target[p -> i] == '+' ||

			 p -> target[p -> i] == '/' || p -> target[p -> i] == '$' )

		{

			pop ( p, p -> str2 ) ;

			pop ( p, p -> str3 ) ;

			p -> temp1[0] = p -> target[p -> i] ;

			p -> temp1[1] = '\0' ;

			strcpy ( p -> str1, p -> str3 ) ;

			strcat ( p -> str1, p -> temp1 ) ;

			strcat ( p -> str1, p -> str2 ) ;

			push ( p, p -> str1 ) ;

		}

		else

		{

			p -> temp1[0] = p -> target[p -> i] ;

			p -> temp1[1] = '\0' ;

			strcpy ( p -> temp2, p -> temp1 ) ;

			push ( p, p -> temp2 ) ;

		}

		p -> i++ ;

	}

}



/* displays the expression */

void show ( struct postfix p )

{

	char *t ;

	t = p.stack[0] ;

	while ( *t )

	{

		printf ( "%c ", *t ) ;

		t++ ;

	}

}

Read more »

stack programs in c -5

Question 5.Write program to convert expression in postfix form to prefix form ?

Ans :

#include 

#include 

#include 



#define MAX 50



struct postfix

{

	char stack[MAX][MAX], target[MAX] ;

	char temp1[2], temp2[2] ;

	char str1[MAX], str2[MAX], str3[MAX] ;

	int i, top ;

} ;



void initpostfix ( struct postfix * ) ;

void setexpr ( struct postfix *, char * ) ;

void push ( struct postfix *, char * ) ;

void pop ( struct postfix *, char * ) ;

void convert ( struct postfix * ) ;

void show ( struct postfix ) ;



void main( )

{

	struct postfix q ;

	char expr[MAX] ;



	clrscr( ) ;



	initpostfix ( &q ) ;



	printf ( "\nEnter an expression in postfix form: " ) ;

	gets ( expr ) ;



	setexpr ( &q, expr ) ;

	convert ( &q ) ;



	printf ( "\nThe Prefix expression is: " ) ;

	show ( q ) ;



	getch( ) ;

}



/* initializes the elements of the structure */

void initpostfix ( struct postfix *p )

{

	p -> i = 0 ;

	p -> top = -1 ;

	strcpy ( p -> target, "" ) ;

}



/* copies given expr. to target string */

void setexpr ( struct postfix *p, char *c )

{

	strcpy ( p -> target, c ) ;

}



/* adds an operator to the stack */

void push ( struct postfix *p, char *str )

{

	if ( p -> top == MAX - 1 )

		printf ( "\nStack is full." ) ;

	else

	{

		p -> top++ ;

		strcpy ( p -> stack[p -> top], str ) ;

	}

}



/* pops an element from the stack */

void pop ( struct postfix *p, char *a )

{

	if ( p -> top == -1 )

		printf ( "\nStack  is empty." ) ;

	else

	{

		strcpy ( a, p -> stack[p -> top] ) ;

		p -> top-- ;

	}

}



/* converts given expr. to prefix form */

void convert ( struct postfix *p )

{

	while ( p -> target[p -> i] != '\0' )

	{

		/* skip whitespace, if any */

		if ( p -> target[p -> i] == ' ')

			p -> i++ ;

		if( p -> target[p -> i] == '%' || p -> target[p -> i] == '*' ||

			p -> target[p -> i] == '-' || p -> target[p -> i] == '+' ||

			p -> target[p -> i] == '/' || p -> target[p -> i] == '$' )

		{

			pop ( p, p -> str2 ) ;

			pop ( p, p -> str3 ) ;

			p -> temp1[0] = p -> target[ p -> i] ;

			p -> temp1[1] = '\0' ;

			strcpy ( p -> str1, p -> temp1 ) ;

			strcat ( p -> str1, p -> str3 ) ;

			strcat ( p -> str1, p -> str2 ) ;

			push ( p, p -> str1 ) ;

		}

		else

		{

			p -> temp1[0] = p -> target[p -> i] ;

			p -> temp1[1] = '\0' ;

			strcpy ( p -> temp2, p -> temp1 ) ;

			push ( p, p -> temp2 ) ;

		}

		p -> i++ ;

	}

}



/* displays the prefix form of expr. */

void show ( struct postfix p )

{

	char *temp = p.stack[0] ;

	while ( *temp )

	{

		printf ( "%c ", *temp ) ;

		temp++ ;

	}



}

Read more »

stack programs in c -4

Question 4.Write program to convert an Infix form to Postfix form ?

Ans :

#include 

#include 

#include 

#include 



#define MAX 50



struct infix

{

	char target[MAX] ;

	char stack[MAX] ;

	char *s, *t ;

	int top ;

} ;



void initinfix ( struct infix * ) ;

void setexpr ( struct infix *, char * ) ;

void push ( struct infix *, char ) ;

char pop ( struct infix * ) ;

void convert ( struct infix * ) ;

int priority ( char ) ;

void show ( struct infix ) ;



void main( )

{

    struct infix p ;

	char expr[MAX] ;



    initinfix ( &p ) ;



    clrscr( ) ;



    printf ( "\nEnter an expression in infix form: " ) ;

	gets ( expr ) ;



	setexpr ( &p, expr ) ;

	convert ( &p ) ;



	printf ( "\nThe postfix expression is: " ) ;

	show ( p ) ;



    getch( ) ;

}



/* initializes structure elements */

void initinfix ( struct infix *p )

{

	p -> top = -1 ;

	strcpy ( p -> target, "" ) ;

	strcpy ( p -> stack, "" ) ;

	p -> t = p -> target ;

	p -> s = ""  ;

}



/* sets s to point to given expr. */

void setexpr ( struct infix *p, char *str )

{

	p -> s = str ;

}



/* adds an operator to the stack */

void push ( struct infix *p, char c )

{

	if ( p -> top == MAX )

		printf ( "\nStack is full.\n" ) ;

	else

	{

		p -> top++ ;

		p -> stack[p -> top] = c ;

	}

}



/* pops an operator from the stack */

char pop ( struct infix *p )

{

	if ( p -> top == -1 )

	{

		printf ( "\nStack is empty.\n" ) ;

		return -1 ;

	}

	else

	{

		char item = p -> stack[p -> top] ;

		p -> top-- ;

		return item ;

	}

}



/* converts the given expr. from infix to postfix form */

void convert ( struct infix *p )

{

    char opr ;



	while ( *( p -> s ) )

	{

		if ( *( p -> s ) == ' ' || *( p -> s ) == '\t' )

		{

			p -> s++ ;

			continue ;

		}

		if ( isdigit ( *( p -> s ) ) || isalpha ( *( p -> s ) ) )

		{

			while ( isdigit ( *( p -> s ) ) || isalpha ( *( p -> s ) ) )

			{

				*( p -> t ) = *( p -> s ) ;

				p -> s++ ;

				p -> t++ ;

			}

		}

		if ( *( p -> s ) == '(' )

		{

			push ( p, *( p -> s ) ) ;

			p -> s++ ;

		}



		if ( *( p -> s ) == '*' || *( p -> s ) == '+' || *( p -> s ) == '/' || *( p -> s ) == '%' || *( p -> s ) == '-' || *( p -> s ) == '$' )

		{

			if ( p -> top != -1 )

			{

				opr = pop ( p ) ;

				while ( priority ( opr ) >= priority ( *( p -> s ) ) )

				{

					*( p -> t ) = opr ;

					p -> t++ ;

					opr = pop ( p ) ;

				}

				push ( p, opr ) ;

				push ( p, *( p -> s ) ) ;

			}

			else

				push ( p, *( p -> s ) ) ;

			p -> s++ ;

		}



		if ( *( p -> s ) == ')' )

		{

			opr = pop ( p ) ;

			while ( ( opr ) != '(' )

			{

				*( p -> t ) = opr ;

				p -> t++ ;

				opr =  pop ( p ) ;

			}

			p -> s++ ;

		}

	}



	while ( p -> top != -1 )

	{

		char opr = pop ( p ) ;

		*( p -> t ) = opr ;

		p -> t++ ;

	}



	*( p -> t ) = '\0' ;

}



/* returns the priority of an operator */

int priority ( char c )

{

	if ( c == '$' )

		return 3 ;

	if ( c == '*' || c == '/' || c == '%' )

		return 2 ;

	else

	{

		if ( c == '+' || c == '-' )

			return 1 ;

		else

			return 0 ;

	}

}



/* displays the postfix form of given expr. */

void show ( struct infix p )

{

    printf ( " %s", p.target ) ;

}

Read more »

stack programs in c -3

Question 3.Write program to convert an Infix expression to Prefix form ?

Ans :

#include 

#include 

#include 

#include 



#define MAX 50



struct infix

{

	char target[MAX] ;

	char stack[MAX] ;

	char *s, *t ;

	int top, l ;

} ;



void initinfix ( struct infix * ) ;

void setexpr ( struct infix *, char * ) ;

void push ( struct infix *, char ) ;

char pop ( struct infix * ) ;

void convert ( struct infix * ) ;

int priority ( char c ) ;

void show ( struct infix ) ;



void main( )

{

    struct infix q ;

	char expr[MAX] ;



	clrscr( ) ;



    initinfix ( &q ) ;



	printf ( "\nEnter an expression in infix form: " ) ;

	gets ( expr ) ;



	setexpr ( &q, expr ) ;

	convert ( &q ) ;



	printf ( "The Prefix expression is: " ) ;

	show ( q ) ;



	getch( ) ;

}



/* initializes elements of structure variable */

void initinfix ( struct infix *pq )

{

	pq -> top = -1 ;

	strcpy ( pq -> target, "" ) ;

	strcpy ( pq -> stack, "" ) ;

	pq -> l = 0 ;

}



/* reverses the given expression */

void setexpr ( struct infix *pq, char *str )

{

	pq -> s = str ;

	strrev ( pq -> s ) ;

	pq -> l = strlen ( pq -> s ) ;

	*( pq -> target + pq -> l ) = '\0' ;

	pq -> t = pq -> target + ( pq -> l - 1 ) ;

}



/* adds operator to the stack */

void push ( struct infix *pq, char c )

{

	if ( pq -> top == MAX - 1 )

		printf ( "\nStack is full.\n" ) ;

	else

	{

		pq -> top++ ;

		pq -> stack[pq -> top] = c ;

	}

}



/* pops an operator from the stack */

char pop ( struct infix *pq )

{

	if ( pq -> top == -1 )

	{

		printf ( "Stack is empty\n" ) ;

			return -1 ;

	}

	else

	{

		char item = pq -> stack[pq -> top] ;

		pq -> top-- ;

		return item ;

	}

}



/* converts the infix expr. to prefix form */

void convert ( struct infix *pq )

{

	char opr ;



	while ( *( pq -> s )  )

	{

		if ( *( pq -> s )  == ' ' || *( pq -> s )  == '\t' )

		{

			pq -> s++    ;

			continue ;

		}



		if ( isdigit ( *( pq -> s )  ) || isalpha ( *( pq -> s )  ) )

		{

			while ( isdigit ( *( pq -> s )  ) || isalpha ( *( pq -> s )  ) )

			{

				*( pq -> t ) = *( pq -> s )  ;

				pq -> s++   ;

				pq -> t-- ;

			}

		}



		if ( *( pq -> s )  == ')' )

		{

			push ( pq, *( pq -> s ) ) ;

			pq -> s++    ;

		}



		if ( *( pq -> s )  == '*' || *( pq -> s )  == '+' || *( pq -> s )  == '/' ||

			 *( pq -> s )  == '%' || *( pq -> s )  == '-' || *( pq -> s )  == '$' )

		{

			if ( pq -> top != -1 )

			{

				opr = pop ( pq ) ;



				while ( priority ( opr ) > priority ( *( pq -> s )  ) )

				{

					*( pq -> t ) = opr ;

					pq -> t-- ;

					opr = pop ( pq ) ;

				}

				push ( pq, opr ) ;

				push ( pq, *( pq -> s )  ) ;

			}

			else

				push ( pq, *( pq -> s ) ) ;

			pq -> s++    ;

		}



		if ( *( pq -> s )  == '(' )

		{

			opr = pop ( pq ) ;

			while ( opr != ')' )

			{

				*( pq -> t ) = opr ;

				pq -> t-- ;

				opr =  pop ( pq ) ;

			}

			pq -> s++    ;

		}

	}



	while ( pq -> top != -1 )

	{

		opr = pop ( pq ) ;

		*( pq -> t ) = opr ;

		pq -> t-- ;

	}

	pq -> t++ ;

}



/* returns the priotity of the operator */

int priority ( char c )

{

	if ( c == '$' )

		return 3 ;

	if ( c == '*' || c == '/' || c == '%' )

		return 2 ;

	else

	{

		if ( c == '+' || c == '-' )

			return 1 ;

		else

			return 0 ;

	}

}



/* displays the prefix form of given expr. */

void show ( struct infix pq )

{

	while ( *( pq.t ) )

	{

		printf ( " %c", *( pq.t ) ) ;

		pq.t++ ;

	}

}

Read more »