1. Define Data Structure.
Differentiate Linear and Non-Linear Data Structures
with Example.
• A Data Structure is a way to organize, manage, and store data in a way that enables
efficient access and modification.
• Linear Data Structures: Elements are arranged sequentially, and each element has a
single successor and predecessor (except the first and last).
o Examples: Arrays, Linked Lists, Stacks, Queues
• Non-Linear Data Structures: Elements are not arranged in a sequential manner; they
can have multiple relationships.
o Examples: Trees, Graphs
2. What is ADT? Explain with Example.
• ADT (Abstract Data Type) is a mathematical model for data types, defining the
behavior (operations) but not implementation details.
• Example: A Stack ADT defines operations like push(), pop(), peek(), but doesn’t
specify if it’s implemented using an array or linked list.
3. Types of Data Structures
1. Primitive Data Structures: int, char, float, etc.
2. Linear Data Structures: Arrays, Linked Lists, Stacks, Queues
3. Non-Linear Data Structures: Trees, Graphs
4. Hashing: Hash Tables
5. File-based Data Structures: File systems
4. Classification of Data Structures
1. Static Data Structures: Fixed size (e.g., Arrays)
2. Dynamic Data Structures: Can grow/shrink at runtime (e.g., Linked Lists)
3. Linear Structures: Arrays, Stacks, Queues
4. Non-Linear Structures: Trees, Graphs
5. Evaluate Postfix Expression
Example: 5 3 + 8 2 - *
Steps:
• Push 5, Push 3, Perform 5+3=8
• Push 8, Push 2, Perform 8-2=6
• Perform 8*6=48
Result: 48
6. Convert Infix to Postfix
Example: (A + B) * C
Steps:
• A B + C *
7. Algorithm for Evaluating Postfix Expression
1. Create an empty stack.
2. Scan the postfix expression from left to right.
3. If the element is an operand, push it onto the stack.
4. If the element is an operator, pop two operands, apply the operator, and
push the result back.
5. Continue till the expression ends. The final value in the stack is the
result.
8. Algorithm for Infix to Postfix Conversion
1. Create an empty stack and output string.
2. Scan the infix expression from left to right.
3. If operand, add to output.
4. If operator, pop from stack based on precedence and push the new operator.
5. If ‘(’, push onto stack.
6. If ‘)’, pop till ‘(’ is found.
7. At the end, pop all remaining operators.
9. C Function for Linear Search
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
10. C Function for Binary Search
int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
11. What is Recursion?
• Recursion is a function calling itself to solve smaller subproblems.
• Example: Factorial Calculation
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
12. Applications of Stack
1. Function Calls (Recursion)
2. Undo/Redo Operations
3. Expression Evaluation
4. Backtracking (Maze, Chess)
13. Infix, Prefix, Postfix Expressions
• Infix: A + B (Operators between operands)
• Prefix: + A B (Operators before operands)
• Postfix: A B + (Operators after operands)
14. Evaluate Postfix Expression: 10 5 + 60 6 / * 8 –
Steps:
1. 10 + 5 = 15
2. 60 / 6 = 10
3. 15 * 10 = 150
4. 150 - 8 = 142
Result: 142
15. Checking Stack Sequences Validity
bool validateStackSequences(int pushed[], int popped[], int n) {
stack<int> s;
int j = 0;
for (int i = 0; i < n; i++) {
s.push(pushed[i]);
while (!s.empty() && s.top() == popped[j]) {
s.pop();
j++;
}
}
return s.empty();
}
✔ True for {1,2,3,4,5} → {4,5,3,2,1}
✖ False for {1,2,3,4,5} → {4,3,5,1,2}
.……………………….Answers Generated By Chat GPT……………………………
