CBSE Class 12 Computer Science Arrays Stacks Queues And Linked List Worksheet Set 02

Arrays, Stacks, Queues And Linked List

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. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks.

Simple Data Structure: These data structures are normally built from primitive data types like integers, floats, characters. For example arrays and structure.

Compound Data Structure: simple data structures can be combined in various ways to form more complex structure called compound structures. Linked Lists, Stack, Queues and Trees are examples of compound data structure.

Searching methods in array

Linear Search: In this method each element of the array is compared with the number to be searched in linear order (from first to last). Where the number is matched, the position is displayed.

#include<iostream.h>
#include<conio.h>
void main()
{
int lsearch(int[],int,int);
int a[50],item,n,index;
clrscr();
cout<<"\n Enter size of array";
cin>>n;
cout<<"\n Enter array elements";
for(int i=0;i<n;i++)
cin>>a[i];
cout<<"Enter the item to be searched";
cin>>item;
index=lsearch(a,n,item);
if(index==-1)
cout<<"\n Element not found";
else
cout<<"\n Element found at position "<<index+1;
getch();
}
int lsearch(int a[],int size,int item)
{
for(int i=0;i<size;i++)
{
if(a[i]==item)
return i;
}
return -1;
}

Binary Search Method

Binary search algorithm is applicable for already sorted array only. In this algorithm, to search for the given item from the sorted array (in ascending order), the item is compared with the middle element of the array. If the middle element is equal to the item then index of the middle element is returned. If the item is less than the middle element, it is present in the first half of the array (between 0 and middle-1), so the next iteration continues on the first half only. If the item is larger than the middle element, it is present in the second half of the array (between middle+1 and size-1), so the next iteration continues on the second half only. The same process continues until either the item is found (search successful) or the segment is reduced to a single element and the item is still not found (search unsuccessful).

#include<iostream.h>
#include<conio.h>
void main()
{
int bsearch(int[],int,int);
int a[50],item,n,index;
clrscr();
cout<<"\n Enter total elements";
cin>>n;
cout<<"\n Enter array elements in sorted form:";
for(int i=0;i<n;i++)
cin>>a[i];
cout<<"Enter the item to be searched";
cin>>item;
index=bsearch(a,n,item);
if(index==-1)
cout<<"\n Element not found";
else
cout<<"\n Element found at position "<<index+1;
getch();
}
int bsearch(int a[],int size,int item)
{
int beg,last;
beg=0; last=size-1;
int mid=(last+beg)/2;
while(beg<=last)
{
mid=(beg+last)/2;
if(item==a[mid])
{
return mid;
}
else if(item>a[mid])
beg=mid+1;
else
last=mid-1;
}
return -1;
}

Sorting operation in the array

Sorting means to arrange the array elements in Ascending order or in Descending order. There are various methods to do this but for ease, Bubble sort method is displayed here.

#include<iostream.h>
#include<conio.h>
void bubblesort(int[],int);
void main()
{
int a[50],n;
clrscr();
cout<<"\nHow many elements do you want to create array with? ";
cin>>n;
cout<<"\nEnter array elements\n";
for(int i=0;i<n;i++)
cin>>a[i];
bubblesort(a,n);
cout<<"\n\nThe sorted array is as shown below\n";
for(i=0;i<n;i++)
cout<<a[i]<<"\n";
getch();
}
void bubblesort(int a[],int n)
{
int temp;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}

Some Questions Based on Array (2 marks question)

Question 1. Write a function in C++ which accepts an integer array and its size as arguments/parameters and reverses the array. Example: if the array is 1,2,3,4,5 then rearrange the array as 5,4,3,2,1
Answer: void reverse(int arr[ ], int n)
{
int temp;
for(int i=0,j=n-1; i<=j; i++,j--)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
In simple words: Swap the first element with the last, the second with the second last, and so on, until the middle is reached.

Exam Tip: Use two index variables, one moving forward from the start and one moving backward from the end.

Question 2. Write a function in C++ which accepts an integer array and its size as arguments/parameters and exchanges the elements in the given manner. Example: if the array is 1,2,3,4,5,6,7,8,9,10 then rearrange the array as 2,1,4,3,6,5,8,7,10,9
Answer: void change(int arr[ ], int n)
{
int temp;
for(int i=0; i<n; i=i+2)
{
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
In simple words: Every pair of neighbouring elements is swapped, starting from index 0.

Exam Tip: Step the loop by 2 so that each pair is swapped only once.

Question 3. Write a function in C++ to merge the contents of two sorted arrays A and B into a third array C. Assuming array A is sorted in ascending order, B is sorted in descending order, the resultant array is required to be in ascending order.
Answer: void merge(int A[], int B[], int C[], int m, int n)
{
int i=0, j=n-1, k=0;
while(i<m && j>=0)
{
if(A[i]<=B[j])
C[k++]=A[i++];
else
C[k++]=B[j--];
}
while(i<m)
C[k++]=A[i++];
while(j>=0)
C[k++]=B[j--];
}
In simple words: Pick the smaller of the two current values (reading B from its end gives ascending order) and copy it into C until both arrays are finished.

Exam Tip: Remember that B is descending, so start reading B from its last element.

Question 4. Write a function in C++ which accepts an integer array and its size as arguments and assigns the elements into a two dimensional array of integers in the following format. If the array is 1,2,3,4,5,6 the resultant 2D array is: 1 2 3 4 5 6 / 0 1 2 3 4 5 / 0 0 1 2 3 4 / 0 0 0 1 2 3 / 0 0 0 0 1 2 / 0 0 0 0 0 1. If the array is 1,2,3 the resultant 2D array is: 1 2 3 / 0 1 2 / 0 0 1
Answer: void makeTwoD(int arr[], int n, int A[][10])
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
if(j<i)
A[i][j]=0;
else
A[i][j]=arr[j-i];
}
}
In simple words: Row i starts with i zeros, then the array is copied from position 0 onwards.

Exam Tip: Work out the value of A[i][j] as arr[j-i] when j is at least i, and 0 otherwise.

Questions based on Two Dimensional Array (3 marks question)

Question 1. Write a function in C++ that will accept a 2-D array and its row and column size as arguments and find the sum of rows and columns.
Answer: void rowcolsum(int A[ ][ ],int N, int M)
{
for (int i=0;i<N;i++)
{
int SumR=0;
for (int j=0;j<M;j++)
SumR+=A[i][j];
cout<<SumR<<endl;
}
for (int i=0;i<N;i++)
{
int SumC=0;
for (int j=0;j<M;j++)
SumC+=A[j][i];
cout<<SumC<<endl;
}
}
In simple words: First add each row and print it, then add each column and print it.

Exam Tip: Reset the sum variable inside the outer loop so each row or column starts from zero.

Question 2. Write a function in C++ to find the sum of both left and right diagonal elements from a two dimensional array (matrix).
Answer: void DiagSum(int A[ ][ ], int N)
{
int SumD1=0,SumD2=0;
for (int I=0;I<N;I++)
{
SumD1+=A[I][I];
SumD2+=A[N-I-1][I];
}
cout<<"Sum of Diagonal 1:"<<SumD1<<endl;
cout<<"Sum of Diagonal 2:"<<SumD2<<endl;
}
In simple words: The left diagonal uses A[I][I] and the right diagonal uses A[N-I-1][I], so one loop adds both.

Exam Tip: For the right diagonal, the row index goes down as the column index goes up.

Address Calculation in Two Dimensional Array

A two dimensional array can be arranged in two manners: 1. Row Major Order 2. Column Major Order.

Row Major Order: Address of A[row][column] = B + w*(n*row + column), where B is the base address, w is the word size and n is the total number of columns.

Column Major Order: Address of A[row][column] = B + w*(m*column + row), where B is the base address, w is the word size and m is the total number of rows.

Question 1. An array x[30][10] is stored in memory with each element requiring 4 bytes. If the base address of x is 4500, find the memory location of x[12][8] when the contents are stored along the row.
Answer: Row major order: B=4500, w=4, n=10.
Address = 4500 + 4*(10*12 + 8) = 4500 + 4*128 = 4500 + 512 = 5012
In simple words: Count how many elements come before x[12][8] in row order, then multiply by the element size and add the base address.

Exam Tip: In row major order, use the number of columns in the formula.

Question 2. An array P[20][30] is stored in memory along the column with each element occupying 4 bytes. If the element P[2][20] is stored at memory location 5000, find the base address of the array.
Answer: Column major order: W=4, N=20 (rows), M=30, Loc(P[2][20])=5000.
Loc(P[I][J]) = Base(P) + W*(N*J + I)
5000 = Base(P) + 4*(20*20 + 2) = Base(P) + 1608
Base(P) = 5000 - 1608 = 3392
In simple words: Find the number of elements stored before P[2][20] in column order, multiply by 4, and subtract that from 5000.

Exam Tip: In column major order, use the number of rows in the formula.

Question 3. An array S[40][30] is stored in memory along the row with each element occupying 2 bytes. If the element S[15][5] is stored at memory location 5500, find the memory location of S[20][10].
Answer: Row major order: W=2, M=30 (columns), Loc(S[15][5])=5500.
Loc(S[I][J]) = Base(S) + W*(M*I + J)
5500 = Base(S) + 2*(30*15 + 5) = Base(S) + 910
Base(S) = 4590
Loc(S[20][10]) = 4590 + 2*(30*20 + 10) = 4590 + 1220 = 5810
In simple words: First find the base address from the known element, then use the same formula for the new element.

Exam Tip: Always find the base address first, then calculate the required location.