1 Define data structure. Enlist and explain types of data structure
Ans : A Data Structure is a particular way of organizing, managing, and storing data in a
computer so that it can be accessed and modified efficiently. It's essentially a scheme for
organizing data and defining the relationships between the data elements. The choice of an
appropriate data structure is crucial for designing efficient algorithms.
• Primitive Data Structures:
o These are the basic, fundamental data types that are directly operated upon
by machine-level instructions. They form the building blocks for more
complex data structures.
o Example: Integer, Float, Character, Boolean, Pointer.
• Non-Primitive Data Structures:
o These are derived from primitive data structures. They are used to store a
collection of data values (either primitive or non-primitive) in a specific
arrangement.
o Example: Arrays, Lists, Files, Stacks, Queues, Trees, Graphs.
o Non-Primitive Data Structures are further sub-classified as:
▪ Linear Data Structures:
• Elements are arranged in a sequential or linear fashion, where
each element has a unique predecessor and successor (except
the first and last).
• This structure is easy to implement.
▪ Non-Linear Data Structures:
• Elements are not arranged sequentially.
• An element can be connected to two or more other elements,
representing complex relationships.
• This structure is more difficult to implement but more effective
in representing real-world hierarchical data.
,2 Differentiate primitive and non-primitive data structures.
Feature Primitive Data Structures Non-Primitive Data Structures
Basis Basic, fundamental data types Derived from primitive data
provided by the language. structures.
Storage Store a single value Store a collection of values (data
items).
Focus Focus on the representation of data Focus on grouping data and defining
values. relationships between data elements.
Size Typically fixed size (e.g., an int is 4 Can be fixed (static, like arrays) or
bytes). variable (dynamic, like linked lists).
Nature Simple and machine-level; directly More complex and abstract; require
manipulated by CPU instructions. specific functions for manipulation.
Examples Integer, Float, Character, Boolean. Array, Stack, Queue, Linked List, Tree,
Graph.
3 Convert infix expression into postfix: (A-B)/C*D^(E/F)^(G+H).
Rules of Precedence (High to Low):
1. Parentheses ()
2. Exponentiation ^ (Right-to-Left Associativity)
3. Multiplication * and Division / (Left-to-Left Associativity)
4. Addition + and Subtraction - (Left-to-Left Associativity)
Conversion Steps
Output (Postfix Stack
Token Notes
Expression) (Operators)
( ( Push opening parenthesis.
A A ( Operand: Output it.
- A (- Push operator.
B AB (- Operand: Output it.
) AB- ( Pop operators until '(', output '-', then pop '('.
/ AB- / Push operator.
C AB-C / Operand: Output it.
, Output (Postfix Stack
Token Notes
Expression) (Operators)
Pop / (same precedence, L-to-R), output it, then push
* AB-C/ *
*.
D AB-C/D * Operand: Output it.
^ AB-C/D *^ Push ^ (higher precedence than *).
( AB-C/D *^( Push opening parenthesis.
E AB-C/DE *^( Operand: Output it.
/ AB-C/DE *^(/ Push operator.
F AB-C/DEF *^(/ Operand: Output it.
) AB-C/DEF/ *^ Pop operators until '(', output '/', then pop '('.
Push ^. (Right Associativity: $\text{Op}_1 = \text{\^}$,
$\text{Op}_2 = \text{\^}$. Pop Op1 only if Op1 has
^ AB-C/DEF/ *^^
strictly lower precedence than Op2. Since they're
equal, we push. A∧B∧C=A(B∧C))
( AB-C/DEF/ *^^( Push opening parenthesis.
AB-C/DEF/
G *^^( Operand: Output it.
G
AB-C/DEF/
+ *^^(+ Push operator.
G
AB-C/DEF/
H *^^(+ Operand: Output it.
GH
AB-C/DEF/
) *^^ Pop operators until '(', output '+', then pop '('.
GH+
AB-C/DEF/
End Pop remaining operators: ^, ^, *.
GH+^^*
The final Postfix Expression is:
AB−C/DEF/GH+∗
Ans : A Data Structure is a particular way of organizing, managing, and storing data in a
computer so that it can be accessed and modified efficiently. It's essentially a scheme for
organizing data and defining the relationships between the data elements. The choice of an
appropriate data structure is crucial for designing efficient algorithms.
• Primitive Data Structures:
o These are the basic, fundamental data types that are directly operated upon
by machine-level instructions. They form the building blocks for more
complex data structures.
o Example: Integer, Float, Character, Boolean, Pointer.
• Non-Primitive Data Structures:
o These are derived from primitive data structures. They are used to store a
collection of data values (either primitive or non-primitive) in a specific
arrangement.
o Example: Arrays, Lists, Files, Stacks, Queues, Trees, Graphs.
o Non-Primitive Data Structures are further sub-classified as:
▪ Linear Data Structures:
• Elements are arranged in a sequential or linear fashion, where
each element has a unique predecessor and successor (except
the first and last).
• This structure is easy to implement.
▪ Non-Linear Data Structures:
• Elements are not arranged sequentially.
• An element can be connected to two or more other elements,
representing complex relationships.
• This structure is more difficult to implement but more effective
in representing real-world hierarchical data.
,2 Differentiate primitive and non-primitive data structures.
Feature Primitive Data Structures Non-Primitive Data Structures
Basis Basic, fundamental data types Derived from primitive data
provided by the language. structures.
Storage Store a single value Store a collection of values (data
items).
Focus Focus on the representation of data Focus on grouping data and defining
values. relationships between data elements.
Size Typically fixed size (e.g., an int is 4 Can be fixed (static, like arrays) or
bytes). variable (dynamic, like linked lists).
Nature Simple and machine-level; directly More complex and abstract; require
manipulated by CPU instructions. specific functions for manipulation.
Examples Integer, Float, Character, Boolean. Array, Stack, Queue, Linked List, Tree,
Graph.
3 Convert infix expression into postfix: (A-B)/C*D^(E/F)^(G+H).
Rules of Precedence (High to Low):
1. Parentheses ()
2. Exponentiation ^ (Right-to-Left Associativity)
3. Multiplication * and Division / (Left-to-Left Associativity)
4. Addition + and Subtraction - (Left-to-Left Associativity)
Conversion Steps
Output (Postfix Stack
Token Notes
Expression) (Operators)
( ( Push opening parenthesis.
A A ( Operand: Output it.
- A (- Push operator.
B AB (- Operand: Output it.
) AB- ( Pop operators until '(', output '-', then pop '('.
/ AB- / Push operator.
C AB-C / Operand: Output it.
, Output (Postfix Stack
Token Notes
Expression) (Operators)
Pop / (same precedence, L-to-R), output it, then push
* AB-C/ *
*.
D AB-C/D * Operand: Output it.
^ AB-C/D *^ Push ^ (higher precedence than *).
( AB-C/D *^( Push opening parenthesis.
E AB-C/DE *^( Operand: Output it.
/ AB-C/DE *^(/ Push operator.
F AB-C/DEF *^(/ Operand: Output it.
) AB-C/DEF/ *^ Pop operators until '(', output '/', then pop '('.
Push ^. (Right Associativity: $\text{Op}_1 = \text{\^}$,
$\text{Op}_2 = \text{\^}$. Pop Op1 only if Op1 has
^ AB-C/DEF/ *^^
strictly lower precedence than Op2. Since they're
equal, we push. A∧B∧C=A(B∧C))
( AB-C/DEF/ *^^( Push opening parenthesis.
AB-C/DEF/
G *^^( Operand: Output it.
G
AB-C/DEF/
+ *^^(+ Push operator.
G
AB-C/DEF/
H *^^(+ Operand: Output it.
GH
AB-C/DEF/
) *^^ Pop operators until '(', output '+', then pop '('.
GH+
AB-C/DEF/
End Pop remaining operators: ^, ^, *.
GH+^^*
The final Postfix Expression is:
AB−C/DEF/GH+∗
