SOLUTION

In linear search, each element of array is compared with the given Item to be searched for, one by one. This method, which traverses the array sequentially to locate the given Item, is called linear search or sequential search.

SOLUTION

Simple data structures can be combined in various ways to form more complex structures called compound structures. Compound data structures are classified into following two types: Linear data structures and Non - linear data structures.

SOLUTION

In the given array, the UB (upper bound) is 15 and LB (lower bound) is -2. The array length can be calculated by the formula :
Array size (length) = UB - LB + 1
                              = 15 - (-2) +1
                              = 18

SOLUTION

In the given array, the UB (upper bound) is 10 and LB (lower bound) is -4. We can also calculate the array length by the formula :
Array size (length) = UB - LB + 1.

SOLUTION

Simple data structures are normally built from primitive data types like integers, reals, characters, boolean. For example, a) array b) structure.

SOLUTION

Primitive data types are those data types, which are not composed of other data types. C++ names primitive data types as standard or fundamental data types. Primitive data types are Integer, Real and Character data types.

SOLUTION

The base address of an array is the address of the first element in the array and always appears in the lowest memory location. The second array element directly follows the first in memory, the third element follows the second etc.

SOLUTION

In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value.

SOLUTION

In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value.

SOLUTION

The array size (length) = UB - LB + 1. Here, the upper bound is 6 and lower bound is -12. Therefore, 6-(-12) = 6 + 12 = 19. Thus, length of an array will be 19 as the declaration is from -12 to 6.

SOLUTION

A singly-linked list is the most basic of all the linked data structures. It is simply a sequence of dynamically allocated objects, each of which refers to its successor in the list.

SOLUTION

In computer science, a stack is a "last in, first out(LIFO)" abstract data type and data structure. A stack can have any abstract data type as an element, but is characterised by only two fundamental operations, the push and the pop.

SOLUTION

In a FIFO data structure, the first element added to the queue will be the first one to be removed.

SOLUTION

Topmost node is called the root of the tree and the bottommost nodes are called leaves of the tree.

SOLUTION

Primitive data types are those data types which are not composed of other data types. In C++, primitive data types are known as standard or fundamental data types. Primitive data types are Integer, Real and Character data types.

SOLUTION

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.

SOLUTION

An array is a systematic arrangement of objects, usually in rows and columns. Operations on arrays include: Creation, Traversal, Deletion, Searching, Sorting.

SOLUTION

Binary search searches for the given ITEM in a sorted array. The search segment reduces to half at every successive stage. To search for ITEM in a sorted array, the ITEM is compared with the middle element of the segment.

SOLUTION

In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value. It operates by checking every element of a list one at a time in sequence until a match is found.

SOLUTION

The array should be sorted for Binary Search to work.  Also, the upper and lower bounds for the array should be known, as mid point is calculated.     

SOLUTION

Length  = UB – LB + 1

where UB  (or  Upper Bound)  = 4

          LB  (or Lower Bound)   =  -3

         Size = 4  - ( -3) +1

SOLUTION

An array is a collection of elements of the same data type.  Each array element is referenced using the index or subscript.  A structure has members of different data types.  The members in the structure are accessed using the dot  ‘.’ operator.     

SOLUTION

Address of A[ i ] [ j ]  =  B + W( nr( j – LB_C) + ( i – LB_R))
Here,   B = 1000         nr = 16

           W = 1                 LB_R = -10

           i = -5                  LB_C = 5

           j = 8

Address of A[-5, 8] = 1000 + 1( 16(8 - 5)  +  ( -5 – (-10)  )

SOLUTION

Address of X[ i ] [ j ]  =  B + W( nc(i – LB_R) + (j – LB_C))
Here,  B = 2000          nc = 8

          W = 2                 LB_R = -2

           i = 2                   LB_C = -3

           j = 3

Address of A[i , j]     = 2000 + 2( 8( 2 - (-2) ) + (3 - (-3)  )

SOLUTION

An array is allocated contiguous storage in memory. For this, the 2D array is linearized. This can be  done in two ways – Row Major or Column Major. 
In Row Major form, the first row is stored followed by the second row and so on. In Column Major, the first column is stored followed by the second column and so on. The computer keeps track of the starting address of the array (base address) and accesses the element by calculating its address.  

SOLUTION

After I -          12    24    26    28    11    13    25    27

After II -         12    24    26    28    11    13    25    27

After III -        12    24    26    28   11     13    25    27

After IV -        11    12    24    26    28    13    25    27

After V -         11    12    13    24    26    28    25    27

After VI -        11    12    13    24    25    26    28    27

SOLUTION

After I-     2          4         16          11           3          25          27          28
After II -   2          4         11           3          16          25          27          28

After III -  2          4          3          11          16          25          27          28

After IV -  2          3          4          11          16          25          27          28

After V -   2          3          4          11          16          25          27          28

After VI -  2          3          4          11          16          25          27          28

After VII - 2          3          4          11          16          25          27          28

After VIII -2          3          4          11          16          25          27          28   

SOLUTION

After I -          1             4            6          8        2           3        5            7
After II -         1             2            6          8        4           3        5            7

After III -        1             2            3          8        4           6        5            7

After IV -        1             2            3          4        8           6        5            7

After V -         1             2            3          4        5           6        8            7

After VI -        1             2            3          4        5           6        8            7

After VII -       1             2            3          4        5           6        7            8        

SOLUTION

They are both searching techniques.  Linear Search can be used on sorted or unsorted arrays. It involves comparing each array element with the given value.

Algorithm for Linear Search
1.  SET ctr = 0                                            // 0 is the Lower Bound of the array

2.  REPEAT STEPS 3   to  4 UNTIL ctr > UB      // check each element of the array

3.  IF A[ctr] = Val  THEN                            // compare value and array element

         {  

              PRINT   Val,  “located  at “, ctr
              GO TO 6
          }
4.  ctr = ctr + 1                                                  // increment counter

5.IF  ctr > UB THEN

             PRINT    Val,  “Not in array”
6.  END

Binary Search can be used only on sorted arrays. It is considered more efficient than Linear Search as the number of comparisons are much less.   It first compares the value and the middle element of the array.  As it is a sorted array, if the value is less than the middle element, the elements in the left half should be checked otherwise if the value is greater than the middle element, the right half of the array should be checked.  This process is done repeatedly till the element is located or declared ‘not found’.

Algorithm for Binary Search with array sorted in ascending order

1.  SET low = LB, up = UB               // UB and LB are upper and lower bounds

2.  REPEAT STEPS 3   to  6 UNTIL low > up //  repeat until low  goes beyond up

3.  m = INT( low + up) / 2                               // find mid point of array

4.  IF A[ m ] = Val  THEN          // compare value and array element

         {   PRINT   Val,  “located  at “, m + 1

             GO TO 7

       }
5.  IF A [ m ] < Val THEN 

           low = m + 1

6.  IF A[ m ] > Val THEN 

           up = m - 1

7.  END               

SOLUTION

An array is a collection of finite elements of the same data type, placed contiguously in memory. Each array element can be referenced using index or subscript numbers.

Arrays can be one-dimensional or multi-dimensional.

A one–dimensional array is declared with one size specification. Each element is accessed using the array name and index number which refers to its location.  In array  A[10], the elements can be accessed as A[0], A[1] and so on.  

A two–dimensional array can be regarded as an array of arrays. It requires 2 size specifiers. It is a kind of multi-dimensional array. To declare an integer array named AX with 4 rows and 8 columns, give

    int  AX[4][8];

SOLUTION

Address of ARR[i] =  B + W(i – LB)

where  B is Base Address,  W is element size and LB is Lower Bound of the array.

B = 4500                           W = 2

i = 2                                 LB = -5

Address of ARR[ i ] = 4500 + 2( 2 – (-5))

                             =  4514

B = 4500                           W = 2

i = -1                                LB = -5

Address of ARR[ i ] = 4500 + 2( -1 – (-5))

                              = 4508

SOLUTION

int binary(int A[ ], int n)
                 int pos, l, u, m;

pos=-1;

l=0;

u=9;

while(l <= u){

    m=(u + l)/2;

    if(A[m]==n){

         pos=m+1;

         break;

    }

    if(A[m]>n)

         u=m-1;

    else

       if(A[m] < n)

           l=m+1;

}

return pos;

SOLUTION

int linear(int A [ ],  int n){
      int i, pos = -1;
      for(i=0; i < 10 ; i++)
         if(A[ i ] == n){
            pos = i+1;
            break;
         }
     return pos; 
}    

SOLUTION

LIFO is an acronym, which stands for last in, first out. It refers to the organization of data elements in memory in LIFO manner.

SOLUTION

We can convert infix expression to the postfix by using stack and we can also evaluate the postfix expression using the stack.

SOLUTION

"List" is the collection of elements stored in a sequential order.

SOLUTION

Traversal refers to the process of visiting each node in a data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.

SOLUTION

A node is an abstract basic unit used to build linked data structures such as trees, linked lists, and computer-based representations of graphs. Each node contains some data and possibly links to other nodes. Pointers or references often used to implement links between nodes.

SOLUTION

In computer science, garbage collection (GC) is a form of automatic memory management. The garbage collector attempts to reclaim garbage, or memory used by objects that will never be accessed or mutated again by the application.

SOLUTION

If the memory is not utilized, then it is stored in a separate area known as free pool. It is also known as AVAIL list.

SOLUTION

Infix notation is the common arithmetic and logical formula notation, in which operators are placed in between the operands. For Example: a + b

SOLUTION

Deque(double-ended queues) are the refined queues in which elements can be added or removed at either end but not in the middle.

SOLUTION

A queue implemented within an array, where the first element of the array logically follows the last element is known as circular queue.

SOLUTION

When there is no element left in the stack and deletion operation is performed on it,then it is the case of underflow.

SOLUTION

The push operation adds an element to the list. Pushing an element in the stack involves adding of data item at the top of the list.

SOLUTION

Merging is an operation performed on data structure in which elements of two similar data structure are combined to form a new data structure of the same type.

SOLUTION

There is a situation in an array when we try to insert or add an element into a full array. It leads to an overflow condition.

SOLUTION

A queue is FIFO structure where insertions take place at the "rear" end and deletions at the "front" end.

SOLUTION

In stack the items are stored sequentially, thus forming linear data structure.

SOLUTION

It will be evaluated as (20+(8/4)) = 20 + 2 = 22.

SOLUTION

An expression is in postfix form if the operators appear after the operands.

SOLUTION

The organized collection of data is called data structure. So, a data structure is combination of organized data(having datatypes) and allowed operations.

SOLUTION

Element size is the space that the element needs for the storage purpose.

SOLUTION

The pop operation removes or deletes an item from the list. It removes the element from the top most position.

SOLUTION

A stack is a linear structure where insertions and deletions take place only at one end, i.e., LIFO structure.

SOLUTION

Element size is the memory space that the element needs for the storage purpose.

SOLUTION

The organized collection of data is called data structure. So, a data structure is a combination of organized data and allowed operations.

SOLUTION

A linear data structure is one in which elements are stored sequencially. For Example- Linked List, Array.

SOLUTION

Merging is an operation performed on data structure in which elements of two similar data structure are combined to form a new data structure of the same type.

SOLUTION

In computer science, a tree is a widely used data structure that emulates a hierarchical tree structure with a set of linked nodes.

SOLUTION

The index of first element in the queue is stored in front. If front =0 it means there is zero element in the queue.

SOLUTION

It will result in an overflow, if we try to add an element to a queue, which is already full.

SOLUTION

Front stores the index of first element in the queue. Rear stores the index of last element in the queue.

SOLUTION

Number of elements in a queue can be calculated using the given formula - queue = front-rear + 1 .

SOLUTION

A stack is implemented in Last In First Out manner where, insertion and deletion is restricted to only one end-stack’s top.

SOLUTION

Push is to insert an element in the stack, whereas Pop is to delete an element from the stack.

SOLUTION

As stacks are LIFO implemented data structures, so it can be used for string reversal.

SOLUTION

It is a linked list, which is a linear collection of data elements, called nodes. Linked lists are dynamic structures.

SOLUTION

In arrays, the memory is reserved before processing. That is why they are called dense lists or static data structures.

SOLUTION

If we try to use pop operation on an empty stack, it causes underflow as there is no element in the stack.

SOLUTION

Circular queues are implemented in circular forms rather than in straight lines and are able to utilise the space that is not utilised linear queues.  

SOLUTION

Prefix is when operator is placed before operands, postfix is when operator is placed after its operands, and in infix the operator is placed between its operands.

SOLUTION

Dequeue is a double ended queue where elements can be added or removed at either end but not in the middle.

SOLUTION

The basic operations performed on arrays are –
Traversing  - visiting each element for some processing.

Searching – traversing the array to see if a certain given value exists in it or not.  Two commonly used methods are – Linear Search and Binary Search.  Linear search can be used on unsorted arrays.    Binary Search is done only on sorted arrays.  

Insertion – This can be done if there is space available in the array.  In an unsorted array, the new element can be placed at the end.  If the array is sorted, the element is given its proper position in the sorted sequence, by shifting other elements. 

Deletion -  If the element to be deleted exists in the array, then the element should be removed and the elements that follow shifted so that the rest of the sequence remains undisturbed.  

Sorting -  Array elements may be arranged in ascending or descending order.  Some sorting techniques are bubble sort, selection sort, insertion sort, shell sort, heap sort, quick sort. 

SOLUTION

The fundamental data types (char, int, float, double,void) can be grouped together and treated as a unit.  This grouped unit is a data structure.  
Data structures have been classified into two categories -

Simple Data Structure – these are built using the fundamental data types i.e.  char, int, float and double.  Examples - arrays and structures 

Compound Data Structure – these  are built using simple data structures.  These are further divided into – linear and non-linear.

Linear data structures are those whose elements form a sequence.  Examples – Stacks, Queues and Linked Lists.

SOLUTION

 // To replace elements below left diagonal with 0s
#include < iostream.h> 
#include < conio.h>
void main()
{ 
  clrscr();
  int i, j, X[4][4];
  cout<<"nEnter integers for the array";
  for(i=0; i < 4; i++)                                  // accept 16 elements into array
  for(j=0; j < 4; j++)
       cin>>X[ i ] [ j ];
  for(i=0; i < 4; i++)                                // assign 0 if below diagonal
  for(j=0; j < 4; j++)
  {
       if ( i > j )
       {  
         X[ i ] [ j ] = 0;
         cout<< "n Final Array n";
        }
  }  
  for(i=0; i < 4; i++)
  {                                                      // display final array
  for(j=0; j < 4; j++)
  {    
    cout << X[ i ] [ j ]<< "  ";
    cout<<"n";
   }
  }
}                          

SOLUTION

// to shift even nos before odd
               #include < iostream.h>

#include < conio.h>

void main(){

  clrscr();

  int i, j, A[10], B[10];

  cout<<"nEnter integers for the array";

  for(i=0; i<10; i++)                                   // accept 10 elements into array A

     cin>>A[ i ];

  j=0;

  for(i=0; i<10; i++){                                 // place even nos. in array B

    if(A[ i ]%2==0){

       B[ j ] = A[ i ];

       ++j;

    }

  }

  for(i=0; i < 10; i++){                                // place odd nos. in array B

    if(A[ i ]%2==1){

       B[ j ] = A[ i ];

       ++j;

    }

  }

  for( i=0; i<10; i++)                                  // copy array B to array A

    A[ i ] = B[ i ];

  for(i=0;i<10;i++)                                     // display array A

    cout<< A[ i ]<< ' ';

SOLUTION

// To display sum of both diagonals separately 
#include < iostream.h>
#include < conio.h>
void main()
{
   clrscr();
   int i, j, X[4][4], sl = 0, sr = 0;
   cout<<"nEnter integers for the array";
   for(i=0; i < 4; i++)                                  // accept 16 nos. into array X
   for(j=0; j < 4; j++)
   {
       cin>>X[ i ] [ j ];
       cout<<"n Sum of left diagonal = ";
   }
   for(i=0; i < 4; i++)                               // add left diagonal
   {
        sl = sl + X[ i ] [ i ];
        cout<< sl;
        cout<<"n Sum of right diagonal = ";
   }
   for(i=0; i < 4; i++)                               // add right diagonal
   for(j=0; j < 4; j++)
   {
        if( i +j == 3)
        sr = sr + X[ i ] [ j ];
        cout<< sr;
   } 
}                         

SOLUTION

// to delete all occurrences from sorted array and shift right

#include < iostream.h>

#include < conio.h>

void main(){

  clrscr( );

  int i, j, k, n, pos, A[20];

  cout<<"nEnter integers for the array, in ascending order";

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

     cin>>A[ i ];

  cout<<"nEnter integer to delete : ";

  cin>>n;

  k = 0;

  pos = -1;

  for(i=0; i < 20; i++){

     if (A[ i ] == n){                  // if found, shift all in front, back

       pos = i;

       for(j=pos; j > 0; j--)

          A[ j ] = A[ j - 1 ];

       A[ k ] = 0;

       ++k;

     }

  }

  if (pos==-1)

    cout<<"n Not found in array n";

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

    cout<< A[ i ]<< ' ';

  getch();

SOLUTION

Insertion of another value can be done if there is space available in the array.  If the array is unsorted i.e. elements are not placed in any particular sequence, the new element can be made the last element.  If the array is sorted, the element must be given its proper position in the sorted sequence. 

Algorithm for Insertion in a Sorted Array – Ascending order
1.  SET i = 0
2.  REPEAT STEP 3  AS LONG AS  A[ i ] < Val
3.  IF A[ i ] < Val THEN

        i = i + 1;
4.  SET  pos = i;
5.  SET i = UB
6.  REPEAT STEP 7 UNTIL i = pos
7.   { A[ i ] = A[ i-1 ];

           i = i – 1

    }
8.   A[ pos ] = Val;
9.  END                           

SOLUTION

Merge – sort is when two sorted arrays are merged to create the third array which is also sorted.   
In this technique,  the current values of the two arrays are compared and the one smaller is put into the new array.  The marker in the array used moves ahead one element.  Again the current elements of the two arrays are compared and the smaller value put into the new array.  This process continues till one of the arrays ends and then the remaining elements of the other array are placed in the new array.  

 //Merge sort ascending- with component arrays in descending order

#include < iostream.h>

void main(){

  int ia, ib, ic, A[6], B[6], C[12];

  cout<<"nEnter 6 integers, in desc order ";                           //first array

  for(ia=0; ia < 6; ia++)

     cin>>A[ ia ];

  cout<<"nEnter 6 more integers, in desc order ";                   // second array

  for(ia=0; ia < 6; ia++)

     cin>>B[ia];

  for(ia=5,ib=5,ic=0; ia>=0 && ib>=0; )                                 // creation of third array

  {

    if(A[ia] > B[ib]){

       C[ic] = B[ib];

       ++ic;

       --ib;

    }

    else{

       C[ic] = A[ia];

       ++ic;

       --ia;

    }

   }                                                           // end of for loop

  if(ia < 0)

     while(ib>=0){

     C[ic] = B[ib];

     ++ic;

     --ib;

  }

  if(ib < 0)

     while(ia >= 0){

     C[ic] = A[ia];

     ++ic;

     --ia;

  }

   cout<<"n Merged Array n";

   for(ic=0; ic<12; ic++)

      cout<< C[ic]<< ' ';

SOLUTION

In tree data structure the elements are not stored in a sequence, therefore it is a non-linear data structure.

SOLUTION

Data structures like trees, binary trees, graphs and heaps are non-linear data structures as the elements doesn't stored in an order.

SOLUTION

A linear data structure is one in which elements are stored sequentially. For Example - Liked List, Array.

SOLUTION

The data structure which contains different type of data is known as non-homogeneous or heterogeneous data structure.

SOLUTION

When the items or entities in a group are similar, then they are said to be homogeneous. Similarly, when the elements of the data structure are of same type, then it is a homogeneous data structure.

SOLUTION

A sorting is a process of arranging items in some sequence and/or in different sets/order.

SOLUTION

Searching is the operation that performed on data structure to search for a specified data element.

SOLUTION

In computer science, a tree is a widely used data structure that emulates a hierarchical tree structure with a set of linked nodes.

SOLUTION

A postfix expression itself determines the precedence of operators. Therefore, for the machine it is easier to carry out a postfix expression than other expressions.

SOLUTION

The pop operation removes (deletes) an item from the stack, and returns this item value to the calling program.

SOLUTION

The push operation adds(stores) elements to the Stack.

SOLUTION

FIFO is an acronym for First In, First Out, an abstraction in ways of organizing and manipulation of data relative to time and prioritization.

SOLUTION

Arrays refer to a named list of a finite number n of similar data elements. The array itself is given a name and its elements are referred to by their subscripts. In C++, an array is denoted as follows:
Arrayname[size]
where size specifies the number of elements in the array and the subscript (also called index) value ranges from 0 to size-1.  

SOLUTION

In C++, the lower bound is always 0 and the upper bound is size -1.

SOLUTION

In C++, the lower bound is always 0 and the upper bound is size -1.

SOLUTION

Trees are multilevel data structures having a hierarchical relationship among its elements called nodes. Topmost node is called the root of the tree and the bottommost nodes are called leaves of the tree.

SOLUTION

In bubble sort, we compare two adjoining values and exchange them if they are not in proper order. In this case, in first pass, when we compare the values, there will be no change i.e. it will remain 13, 24, 5, 19, 2, 17, 4. But in second pass the values 24 and 5 will be swapped. Therefore, in every pass, the heaviest element settles at its appropriate position in the bottom.

SOLUTION

The basic idea of selection sort is to repeatedly select the smallest key in the reamining unsorted array.
For the given array : 15 , 6, 13, 22, 3, 52 , 2
Step 1: Choose the smallest element from unsorted array which is 2; put this smallest element in sorted part at 1st position.
Step 2. The second pass identifies 3 as the smallest element in remaining unsorted array. Add 3 also in sorted part at 2nd position.
Step 3: In third pass, 6 is chosen as smallest and put at position 3.
Step 4: This time 13 is moved to sorted part at 4th position.
Step 5: Fifth pass adds 15 to sorted part at the next position.
Step 6: Sixth pass adds 22 and seventh pass adds 52 to sorted list.  

SOLUTION

Linked lists are special lists of some data elements linked to one another. The logical ordering is represented by having each element pointing to the next element. Each element is called a node, which has two parts. The INFO part which stores the information and the POINTER part, which points to the next element.