1. Define elementary data organizations with examples.
Elementary data organizations refer to the simplest ways data can be stored and organized in a
program. Common types include:
Arrays: A collection of elements stored in contiguous memory locations.
Example: int arr[5] = {1, 2, 3, 4, 5};
Structures: Group different types of data under one name.
Example:
c
Copy code
struct Student {
int id;
char name[50];
};
Pointers: Variables that store memory addresses.
Example: int *p = &x;
2. What are data structure operations? Explain with examples.
Data structure operations are actions performed on data structures to manage data efficiently.
Common operations include:
Insertion – Adding an element.
E.g., Add a node to a linked list.
Deletion – Removing an element.
E.g., Remove an element from a queue.
Traversal – Visiting each element.
E.g., Printing all elements in an array.
Searching – Finding an element.
E.g., Binary search in a sorted array.
Sorting – Arranging elements in order.
E.g., Bubble sort on an array.
3. Explain insertion operation in a data structure with an example.
Insertion adds a new element to a data structure.
Example (Array):
Insert 25 at index 2 in array [10, 20, 30, 40].
Steps:
Shift elements from index 2 rightwards.
Insert 25 at index 2.
Result: [10, 20, 25, 30, 40]
4. Explain deletion operation in a data structure with an example.
Deletion removes an element from a data structure.
Example (Array):
Delete element at index 1 from [10, 20, 30, 40].
Steps:
Shift elements after index 1 to the left.
Result: [10, 30, 40]
5. What is traversal? Describe different types of traversals.
Traversal is the process of visiting each element of a data structure to access or modify it.
Types:
Array/List Traversal: Linear, left to right.
Tree Traversals:
o Inorder (Left, Root, Right)
o Preorder (Root, Left, Right)
o Postorder (Left, Right, Root)
o Level Order (Breadth-first)
6. Define algorithm analysis. Why is it important?
Algorithm analysis evaluates the efficiency of an algorithm in terms of time and space usage.
Importance:
Helps choose the most efficient algorithm.
Optimizes performance.
Predicts scalability with large inputs.
7. What are asymptotic notations? Name the commonly used ones.
Asymptotic notations describe the performance of algorithms as input size approaches infinity.
Common notations:
Big-O (O): Worst-case scenario.
Omega (Ω): Best-case scenario.
Theta (Θ): Average or tight bound.
8. Explain Big-O notation with an example.
Big-O (O) describes the upper bound or worst-case time complexity.
Example:
Linear Search in an array:
At worst, you search the entire array → O(n)
9. Explain Omega (Ω) notation with an example.
Omega (Ω) represents the lower bound or best-case time complexity.
Example:
Linear Search in an array:
If the element is at the first index → Best case = Ω(1)
10. Explain Theta (Θ) notation with an example.
Theta (Θ) gives the tight bound – both upper and lower limits.
Example:
An algorithm that always runs in exactly n steps → Θ(n)
This means:
Best case = Ω(n)
Worst case = O(n)
11. What do you mean by time complexity of an algorithm?
Time complexity is the amount of time an algorithm takes to run as a function of input size n.
Example:
Binary Search → Time Complexity = O(log n)
12. What do you mean by space complexity of an algorithm?
Space complexity is the total memory (RAM) used by an algorithm, including input, auxiliary
variables, and recursion stack.
Example:
Merge Sort → Space Complexity = O(n) due to extra array used during merging.
13. Explain the concept of time-space trade-off with an example.
Time-space trade-off refers to the compromise between time and memory:
Use more memory to achieve faster execution.
Or use less memory, which might take more time.
Example:
Using a lookup table to store results of expensive calculations (memoization):
Speeds up future computations (less time).
Uses extra memory (more space).