Góc học tập
02/05/2019 07:58:31 PM

Data Structure Interview Questions (cont.)

26) What is doubly linked list?

The doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. In a doubly linked list, a node consists of three parts:

  • node data
  • pointer to the next node in sequence (next pointer)
  • pointer to the previous node (previous pointer).

27) Write the C program to insert a node in circular singly list at the beginning.

 
  1. #include  
  2. #include  
  3. void beg_insert(int);  
  4. struct node  
  5. {  
  6.     int data;  
  7.     struct node *next;  
  8. };  
  9. struct node *head;  
  10. void main ()  
  11. {  
  12.     int choice,item;  
  13.     do   
  14.     {  
  15.         printf("\nEnter the item which you want to insert?\n");  
  16.         scanf("%d",&item);  
  17.         beg_insert(item);  
  18.         printf("\nPress 0 to insert more ?\n");  
  19.         scanf("%d",&choice);  
  20.     }while(choice == 0);  
  21. }  
  22. void beg_insert(int item)    
  23. {    
  24.         
  25.     struct node *ptr = (struct node *)malloc(sizeof(struct node));    
  26.     struct node *temp;  
  27.     if(ptr == NULL)    
  28.     {    
  29.         printf("\nOVERFLOW");    
  30.     }    
  31.     else     
  32.     {    
  33.         ptr -> data = item;    
  34.         if(head == NULL)    
  35.         {    
  36.             head = ptr;    
  37.             ptr -> next = head;    
  38.         }    
  39.         else     
  40.         {       
  41.             temp = head;    
  42.             while(temp->next != head)    
  43.                 temp = temp->next;    
  44.             ptr->next = head;     
  45.             temp -> next = ptr;     
  46.             head = ptr;    
  47.         }     
  48.     printf("\nNode Inserted\n");  
  49.     }    
  50.                 
  51. }    
  52.       

28) Define the queue data structure.

A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.

29) List some applications of queue data structure.

The Applications of the queue is given as follows:

  • Queues are widely used as waiting lists for a single shared resource like a printer, disk, CPU.
  • Queues are used in the asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.
  • Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
  • Queues are used to maintain the playlist in media players to add and remove the songs from the play-list.
  • Queues are used in operating systems for handling interrupts.

30) What are the drawbacks of array implementation of Queue?

  • Memory Wastage: The space of the array, which is used to store queue elements, can never be reused to store the elements of that queue because the elements can only be inserted at front end and the value of front might be so high so that, all the space before that, can never be filled.
  • Array Size: There might be situations in which, we may need to extend the queue to insert more elements if we use an array to implement queue, It will almost be impossible to extend the array size, therefore deciding the correct array size is always a problem in array implementation of queue.

Sưu tầm: Nguyễn Thị Bảo Trang

» Các tin khác: