CBSE Class 12 Computer Science Data Structures Concepts

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. For example, Stacks are used in function call during execution of a program, while B-trees are particularly well-suited for implementation of databases. The data structure can be classified into following two types: 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.

Data Structure Arrays

Data structure array is defined as linear sequence of finite number of objects of same type with following set of operation:

¶ Creating : defining an array of required size

¶ Insertion: addition of a new data element in the in the array

¶ Deletion: removal of a data element from the array

¶ Searching: searching for the specified data from the array

¶ Traversing: processing all the data elements of the array

¶ Sorting : arranging data elements of the array in increasing or decreasing order

¶ Merging : combining elements of two similar types of arrays to form a new array of same type

In C++ an array can be defined as

Datatype arrayname[size];

2,3 & 4 Marks Practice Questions

Question 1. Convert the following infix expressions to postfix expressions using stack
1. A + (B * C) ^ D - (E / F - G)
Answer:

Final Postfix Expression: \(ABC^*D^{\wedge}+EF/G--\)
In simple words: Operators are placed after their operands following operator precedence rules using a stack.

Exam Tip: Remember operator precedence: Exponentiation (\(\wedge\)) > Multiplication/Division (*, /) > Addition/Subtraction (+, -).

Question 1 (continued). 2. A * B / C * D ^ E * G / H
Answer:
Evaluating strictly from left to right with equal precedence operators associating from left to right:
\(A * B \rightarrow AB*\)
\(/ C \rightarrow AB*C/\)
\(* D \rightarrow AB*C/D*\)
\(^ E \rightarrow AB*C/DE^*\)
\(* G \rightarrow AB*C/DE^*G*\)
\(/ H \rightarrow AB*C/DE^*G*H/\)
Final Postfix Expression: \(AB*C/DE^*G*H/\)
In simple words: Operators with the same precedence are evaluated from left to right.

Exam Tip: For chain multiplication and division, strictly proceed from left to left-associative order.

Question 1 (continued). 3. ((A*B)-((C-D)*E/F)*G (Note: Source OCR shows C_D and missing parenthesis, standard form parsed as given)
Answer:
Applying standard stack-based infix-to-postfix conversion yields: \(AB*CD-EF/*G*-\)
In simple words: Resolve innermost parentheses first before applying operator precedence to outer levels.

Exam Tip: Balance parentheses carefully before starting your conversion table.

Question 2. Evaluate the following postfix expression E given below; show the contents of the stack during the evaluation
1. E = 5, 9, +, 2, /, 4, 1, 1, 3, -, *, +
Answer:
Step-by-step evaluation:
- Push 5, 9 → Stack: [5, 9]
- Operator + → \(5 + 9 = 14\) → Stack: [14]
- Push 2 → Stack: [14, 2]
- Operator / → \(14 / 2 = 7\) → Stack: [7]
- Push 4, 1, 1, 3 → Stack: [7, 4, 1, 1, 3]
- Operator - (on 1 and 3) → \(1 - 3 = -2\) → Stack: [7, 4, 1, -2]
- Operator * (on 1 and -2) → \(1 \times (-2) = -2\) → Stack: [7, 4, -2]
- Operator * (on 4 and -2) → \(4 \times (-2) = -8\) → Stack: [7, -8]
- Operator + (on 7 and -8) → \(7 + (-8) = -1\)
Final Result = -1
In simple words: Pop operands when an operator is encountered, perform the calculation, and push the result back.

Exam Tip: Always pop Operand2 first, then Operand1, for non-commutative operations like subtraction and division: \(\text{Op1} - \text{Op2}\).

Question 2 (continued). 2. E = 80, 35, 20, -, 25, 5, +, -, *
Answer:
- Push 80, 35, 20
- 35 - 20 = 15 → Stack: [80, 15]
- Push 25, 5
- 25 + 5 = 30 → Stack: [80, 15, 30]
- 15 - 30 = -15 → Stack: [80, -15]
- 80 * (-15) = -1200
Final Result = -1200
In simple words: Systematic popping and evaluation lead straight to the final arithmetic value.

Question 2 (continued). 3. E = 30, 5, 2, ^, 12, 6, /, +, -
Answer:
- Push 30, 5, 2
- 5 ^ 2 = 25 → Stack: [30, 25]
- Push 12, 6
- 12 / 6 = 2 → Stack: [30, 25, 2]
- 25 + 2 = 27 → Stack: [30, 27]
- 30 - 27 = 3
Final Result = 3
In simple words: Exponentiation is evaluated first among the operands present.

Exam Tip: Verify exponentiation rules carefully (\(5^2 = 25\), not 10).

Question 2 (continued). 4. E = 15, 3, 2, +, /, 7, +, 2, *
Answer:
- Push 15, 3, 2
- 3 + 2 = 5 → Stack: [15, 5]
- 15 / 5 = 3 → Stack: [3]
- Push 7 → Stack: [3, 7]
- 3 + 7 = 10 → Stack: [10]
- Push 2 → Stack: [10, 2]
- 10 * 2 = 20
Final Result = 20
In simple words: Follow the strict sequence of incoming tokens from left to right.

Exam Tip: Double check division order: 15 / (3 + 2) = 15 / 5 = 3.

Question 3. An array A[40][10] is stored in the memory along the column with each element occupying 4 bytes. Find out the address of the location A[3][6] if the location A[30][10] is stored at the address 9000.
Answer:
For a column-major two-dimensional array \(A[M][N]\):
Address of \(A[I][J] = \text{base address} + (J \times M + I) \times \text{sizeof(type)}\)
Here, \(M = 40, N = 10, \text{sizeof(type)} = 4\) bytes.
Given address of \(A[30][10] = 9000\). Note: Row index goes from 0 to 39, column index from 0 to 9. Wait, the question specifies \(A[30][10]\), let us compute using indices \(I = 30, J = 9\) or as given \(I = 30, J = 10\). Assuming standard indexing where column is 9, let's use the exact formula with given coordinates:
\(\text{Address}(A[30][10]) = \text{base address} + (10 \times 40 + 30) \times 4 = 9000\)
\(9000 = \text{base address} + (400 + 30) \times 4\)
\(9000 = \text{base address} + 430 \times 4\)
\(9000 = \text{base address} + 1720\)
Base Address = \(9000 - 1720 = 7280\)
Now, find address of \(A[3][6]\) where \(I = 3, J = 6\):
\(\text{Address}(A[3][6]) = 7280 + (6 \times 40 + 3) \times 4\)
\(= 7280 + (240 + 3) \times 4\)
\(= 7280 + 243 \times 4\)
\(= 7280 + 972 = 8252\)
Final Address = 8252
In simple words: First find the base address using the given location, then apply the column-major formula to find the target address.

Exam Tip: In column-major order, the column index multiplies the total number of rows (\(J \times M + I\)).

Question 4. Define functions in C++ to perform a PUSH and POP operation in a dynamically allocated stack considering the following:
struct Node
{ int X,Y;
Node *Link; };
class STACK
{ Node * Top;
public:
STACK( ) { TOP=NULL;}
void PUSH( );
void POP( );
~STACK( );
};
Answer:
void STACK::PUSH()
{
Node *p = new Node;
cout << "Enter X and Y: ";
cin >> p->X >> p->Y;
p->Link = TOP;
TOP = p;
}

void STACK::POP()
{
if(TOP == NULL)
{
cout << "Stack Underflow \n";
}
else
{
Node *t = TOP;
TOP = TOP->Link;
cout << "Deleted: " << t->X << ", " << t->Y << endl;
delete t;
}
}
In simple words: PUSH creates a new node at the top, while POP removes the topmost node and frees memory.

Exam Tip: Always check for overflow (new returning NULL) and underflow (TOP == NULL) in dynamic structures.

Question 5. Write a function in C++ to perform a Add and Delete operation in a dynamically allocated Queue considering the following:
struct node
{ int empno; char name[20]; float sal;
Node *Link;
};
Answer:
class Queue {
Node *front, *rear;
public:
Queue() { front = rear = NULL; }
void Add();
void Delete();
};

void Queue::Add()
{
Node *p = new Node;
cout << "Enter empno, name, sal: ";
cin >> p->empno >> p->name >> p->sal;
p->Link = NULL;
if(rear == NULL)
{
front = rear = p;
}
else
{
rear->Link = p;
rear = p;
}
}

void Queue::Delete()
{
if(front == NULL)
{
cout << "Queue Underflow\n";
}
else
{
Node *t = front;
front = front->Link;
if(front == NULL) rear = NULL;
cout << "Deleted Employee Number: " << t->empno << endl;
delete t;
}
}
In simple words: Elements are added at the rear and deleted from the front in a linked queue.

Exam Tip: Handle the edge case when the queue becomes completely empty (setting both front and rear to NULL).