Data Structure Using Python Question Bank - BCA Students

Prepared By: Uday Shah 

Ruparel Education Pvt. Ltd.  - (HOD-IT)

Asst. Prof., 

Faculty of Computer Applications,

Nobile University

UNIT 1: Foundations of Python Programming

Q1. Key Features and Applications of Python

Answer

1. Python is a high-level programming language, which means it is easy for humans to read and write compared to low-level languages.
2. Its syntax is very simple and similar to English, so beginners can learn it quickly without confusion.
3. Python is an interpreted language, so code runs line by line without needing compilation.
4. It is platform independent, meaning the same program can run on Windows, Linux, or Mac without changes.
5. Python supports multiple programming paradigms like object-oriented, functional, and procedural programming.
6. It has a large community support, so students can easily find help and resources online.
7. Python provides many built-in libraries such as NumPy and Pandas, which make programming faster and easier.
8. It is very useful for beginners and students because of its simple structure and readability.
9. Python is widely used in Data Science for data analysis and visualization.
10. It is also used in Artificial Intelligence and Machine Learning for building smart systems.
11. Python is used in Web Development using frameworks like Django and Flask.
12. It is helpful in automation tasks, such as file handling and repetitive work.
13. Python is also used in game development, although less than other languages.
14. It supports database connectivity, so it can store and retrieve data easily.
15. Python allows faster development, as it requires fewer lines of code compared to other languages.

 Q2. Importance of Indentation and Comments

Answer

1. Indentation means giving space at the beginning of a line, which is very important in Python.
2. Python uses indentation instead of brackets {} to define blocks of code.
3. It helps the interpreter understand which code belongs to which block.
4. Proper indentation improves code readability for programmers.
5. It makes the program look clean and well-structured.
6. Incorrect indentation will give an IndentationError in Python.
7. It is mainly used in loops and conditional statements.
8. For example, all statements inside if must be indented.
9. Comments are written using the # symbol in Python.
10. Comments are used to explain the logic of the program.
11. They help other programmers understand the code easily.
12. Comments are ignored by the compiler, so they do not affect execution.
13. They are very useful for debugging and maintenance.
14. Multi-line comments can be written using triple quotes ''' '''.
15. Writing comments is considered a good programming practice.

 Q3. Compare int, float, bool, and string

Answer

1. int is used to store whole numbers like 10, 50, or -5 without decimals.
2. float is used to store decimal numbers like 10.5 or 3.14.
3. bool represents logical values, which are either True or False.
4. string is used to store text data, such as names or sentences.
5. Integers are used in calculations where no decimal value is needed.
6. Floats are used when precision and decimal values are required.
7. Boolean values are mostly used in conditions and decision-making.
8. Strings are used in printing messages and storing text information.
9. int consumes less memory compared to float.
10. float provides more accurate results for scientific calculations.
11. Boolean values are often the result of comparison operations.
12. Strings support operations like concatenation and indexing.
13. Strings are immutable, meaning they cannot be changed after creation.
14. All these are built-in data types provided by Python.
15. Each data type is used depending on the type of data required in the program.

 Q4. Difference between Type Conversion and Type Casting

Answer

1. Type Conversion is an automatic process where Python converts one data type to another.
2. Type Casting is a manual process done by the programmer.
3. Conversion happens implicitly without user involvement.
4. Casting happens explicitly using functions like int(), float(), etc.
5. Example of conversion: adding int and float automatically gives float.
6. Example of casting: converting string to int using int("10").
7. Conversion is usually safe and error-free.
8. Casting can sometimes produce errors if data is invalid.
9. Conversion is handled by Python internally.
10. Casting gives more control to the programmer.
11. Conversion happens during expression evaluation.
12. Casting is used when user wants specific data type.
13. Common casting functions are int(), float(), str().
14. Conversion is not always visible to user.
15. Both are important for handling different data types.

 Q5. Nested Conditions vs Simple if-else

Answer

1. A simple if statement checks only one condition.
2. if-else provides two possible outcomes (true or false).
3. Nested if means one if statement inside another if.
4. Nested conditions are used when multiple conditions need checking.
5. Simple if is easier to understand for beginners.
6. Nested if can become complex if not written properly.
7. Nested conditions allow detailed decision making.
8. Example: checking grades (A, B, C) based on marks.
9. Simple if requires less code.
10. Nested if increases code length and complexity.
11. Proper indentation is very important in nested conditions.
12. Logical thinking is required to write nested conditions correctly.
13. Used in real-world applications like login systems.
14. Helps in solving complex problems step by step.
15. Both are important for controlling program flow.

 Q6. List and Tuple

Answer

1. A list is a collection of multiple values stored in one variable.
2. A tuple is also a collection but with some restrictions.
3. Lists are created using square brackets [].
4. Tuples are created using parentheses ().
5. Lists are mutable, meaning values can be changed.
6. Tuples are immutable, meaning values cannot be changed.
7. Lists allow adding and removing elements.
8. Tuples do not allow modification after creation.
9. Lists are slightly slower than tuples.
10. Tuples are faster because they are fixed.
11. Lists support many functions like append(), remove().
12. Tuples have limited functions.
13. Lists are used when data changes frequently.
14. Tuples are used for fixed data like coordinates.
15. Both are important for storing grouped data.

 Q7. Dictionary and Set

Answer

1. A dictionary stores data in key-value pairs.
2. It is created using curly braces {}.
3. Each key must be unique in a dictionary.
4. Values can be duplicated.
5. Example: {"name":"Uday", "age":20}.
6. A set stores unique values only.
7. Sets are also created using {}.
8. Duplicate values are automatically removed in sets.
9. Sets are unordered, so indexing is not possible.
10. Dictionaries are ordered (in latest Python versions).
11. Dictionary values are accessed using keys.
12. Sets are useful for mathematical operations like union.
13. Dictionaries are useful for mapping data.
14. Sets improve performance for uniqueness checking.
15. Both are important data structures in Python.

 Q8. pass Statement

Answer

1. The pass statement is used when no action is required.
2. It acts as a placeholder in the code.
3. It prevents syntax errors when a block is empty.
4. It is commonly used in loops and conditions.
5. It can be used inside functions and classes.
6. It does not produce any output.
7. It does not affect program execution.
8. Useful during program development stage.
9. Helps in writing code step by step.
10. It improves code structure.
11. It indicates that code will be added later.
12. It is better than leaving block empty.
13. It avoids compilation errors.
14. It is a temporary statement.

 Q9. break vs continue

 Answer

1. The break statement is used to stop the loop completely.
2. The continue statement is used to skip the current iteration.
3. When break is executed, control comes out of loop.
4. Continue moves control to the next iteration.
5. Break is useful when a condition is satisfied.
6. Continue is useful for skipping unwanted values.
7. Break reduces number of loop executions.
8. Continue does not stop loop, it continues running.
9. Break is used in infinite loops to exit.
10. Continue is used in filtering data.
11. Both are used in loops like for and while.
12. Break improves efficiency.
13. Continue improves flexibility.
14. They help in better control of loops.
15. Both are important for logical programming.

 Q10. for loop and while loop

 Answer

1. A for loop is used when the number of iterations is known.
2. A while loop is used when the condition decides execution.
3. For loop uses range() function.
4. While loop depends on condition being true.
5. For loop is easy to use and understand.
6. While loop gives more control over execution.
7. For loop automatically ends after iterations.
8. While loop may run forever if condition is wrong.
9. For loop is commonly used with lists and arrays.
10. While loop is used in logical problems.
11. For loop syntax is simple.
12. While loop requires manual control (increment/decrement).
13. Both loops are used for repetition.
14. Both reduce code length.
15. Both are important for programming logic.

 

UNIT 2: Introduction to Algorithms & Python Data Handling

Q1. What is Data Structure? Explain its Classification

Answer

1. A data structure is a way to store and organize data in a computer, so it can be used efficiently.
2. It helps in performing operations like insertion, deletion, and searching easily.
3. Data structures improve the performance of programs by managing data properly.
4. They are mainly divided into two types: Linear and Non-linear.
5. Linear data structures store data in a sequential manner.
6. Examples of linear structures are array, list, stack, and queue.
7. Non-linear data structures store data in a hierarchical or network form.
8. Examples include tree and graph.
9. Another classification is primitive and non-primitive data structures.
10. Primitive data structures include int, float, char, and boolean.
11. Non-primitive data structures include arrays, linked lists, trees, and graphs.
12. Data structures are used in real-life applications like databases and operating systems.
13. Choosing the correct data structure improves efficiency and speed.
14. They help in better memory utilization.
15. Data structures are a basic concept in computer science and programming.

  Q2. What is a User Defined Function? How to define in Python

 Answer

1. A user-defined function is a function created by the programmer to perform a specific task.
2. It helps in reducing code repetition by reusing the same block of code.
3. Functions make programs more organized and readable.
4. In Python, functions are defined using the def keyword.
5. Syntax starts with def function_name():.
6. Code inside the function must be properly indented.
7. Functions can take parameters (inputs) from the user.
8. They can also return values using the return statement.
9. Example: def add(a, b): return a+b.
10. Functions can be called by using their name with arguments.
11. They help in modular programming, dividing large programs into small parts.
12. Functions improve debugging and maintenance.
13. They allow code reuse in different parts of program.
14. Python supports both built-in and user-defined functions.
15. User-defined functions are important for writing clean and efficient programs.

 Q3. Explain Custom Module with Example

Answer

1. A module is a file that contains Python code like functions and variables.
2. A custom module is a module created by the user.
3. It helps in organizing code into separate files.
4. Modules improve code reuse and maintainability.
5. To create a module, save code in a .py file.
6. Example: create file maths.py with functions.
7. Use import maths to use the module.
8. Functions inside module can be called using module name.
9. Example: maths.add(2,3)
10. Modules reduce code duplication.
11. They make large programs easy to manage.
12. Python provides many built-in modules like math and random.
13. Custom modules are useful for team projects.
14. They help in separating logic into different parts.
15. Modules support structured programming approach.

  Q4. Dynamic Nature of Lists in Python

 Answer

1. Python lists are dynamic, meaning their size can change at runtime.
2. You can add elements using methods like append().
3. You can also remove elements using remove() or pop().
4. Lists do not require fixed size during declaration.
5. They can store different types of data (int, string, etc.).
6. Lists automatically increase or decrease memory when needed.
7. This makes lists very flexible compared to arrays.
8. Lists allow insertion at any position.
9. They support many built-in functions.
10. Lists can be modified anytime (mutable).
11. Dynamic nature reduces memory wastage.
12. Lists are widely used in real applications.
13. They allow easy data manipulation.
14. Useful in handling unknown size data.
15. Makes Python programming simple and powerful.

  Q5. Array Module vs List

 Answer

1. Python array is available using array module.
2. Lists are built-in data structures.
3. Arrays store same type of elements only.
4. Lists can store different data types.
5. Arrays are more memory efficient.
6. Lists are more flexible.
7. Arrays require importing module.
8. Lists do not need any import.
9. Arrays are faster for numerical operations.
10. Lists are easier to use.
11. Arrays are used in scientific applications.
12. Lists are used in general programming.
13. Syntax of arrays is more complex.
14. Lists support more built-in methods.
15. Lists are more commonly used than arrays.

 Q6. Define Data and Information

 Answer

1. Data refers to raw facts and figures.
2. It is unprocessed and has no meaning by itself.
3. Example: numbers like 10, 20, 30 are data.
4. Information is processed and meaningful data.
5. It is useful for decision making.
6. Example: average marks of students is information.
7. Data is input for processing.
8. Information is output after processing.
9. Data can be collected from various sources.
10. Information helps in understanding patterns.
11. Data alone is not useful without processing.
12. Information provides value and meaning.
13. Computers process data into information.
14. Both are important in computing.
15. Information is always more useful than raw data.

 Q7. Primitive vs Non-Primitive Data Structures

 Answer

1. Primitive data structures are basic data types.
2. Examples include int, float, char, boolean.
3. They store single value only.
4. They are directly supported by programming language.
5. Non-primitive data structures are complex data types.
6. Examples include array, list, tree, graph.
7. They store multiple values.
8. They are derived from primitive types.
9. Primitive types are simple and fast.
10. Non-primitive types are flexible and powerful.
11. Primitive data is stored in fixed size memory.
12. Non-primitive data can be dynamic.
13. Primitive types are used for basic operations.
14. Non-primitive types are used for complex problems.
15. Both are essential in programming.

Q8. Static vs Dynamic Memory Allocation

Answer

1. Static memory allocation is done at compile time.
2. Dynamic memory allocation is done at runtime.
3. Static memory size is fixed.
4. Dynamic memory size can be changed.
5. Static allocation is faster.
6. Dynamic allocation is flexible.
7. Static memory cannot be resized.
8. Dynamic memory can grow or shrink.
9. Static memory may waste space.
10. Dynamic memory uses memory efficiently.
11. Static allocation is simple.
12. Dynamic allocation is complex.
13. Example: array (static), list (dynamic).
14. Dynamic memory is used in modern applications.
15. Both methods are important in programming.

Q9. Asymptotic Notation

 Answer

1. Asymptotic notation is used to measure algorithm performance.
2. It shows how time or space grows with input size.
3. It helps compare different algorithms.
4. Big-O notation shows worst-case complexity.
5. Example: O(n), O(n²), O(log n).
6. It ignores constants and focuses on growth rate.
7. Helps in selecting efficient algorithms.
8. Used in computer science for analysis.
9. Big-O is most commonly used notation.
10. Omega shows best case.
11. Theta shows average case.
12. Important for large input data.
13. Helps optimize programs.
14. Improves performance understanding.
15. Essential concept in data structures.

Q10. Input and Output (input() and print())

Answer

1. input() is used to take input from user.
2. It always returns value as string.
3. You can convert input using int(), float().
4. Example: x = input("Enter number").
5. print() is used to display output.
6. It prints data on screen.
7. Example: print("Hello").
8. It supports multiple values.
9. You can format output using f-strings.
10. Input is used for user interaction.
11. Output is used to show results.
12. Both are basic functions in Python.
13. Used in almost every program.
14. Helps in communication between user and program.
15. Essential for learning programming.

 Q11. Analysis of Algorithm

 Answer

1. Analysis of algorithm means evaluating efficiency of an algorithm.
2. It helps to know how much time and space is required.
3. Two types: time complexity and space complexity.
4. Time complexity measures execution time.
5. Space complexity measures memory usage.
6. Helps in comparing algorithms.
7. Important for large data handling.
8. Uses asymptotic notation.
9. Example: O(n), O(log n).
10. Best case, worst case, average case analysis.
11. Helps in optimization.
12. Improves program performance.
13. Used in real-world applications.
14. Important for interviews and exams.
15. Essential topic in data structures.

UNIT 3: Stack, Queue & Linked List

Q1. Define Stack and Explain with Algorithm

 Answer

1. A stack is a linear data structure that follows LIFO (Last In First Out) principle.
2. This means the last element inserted is the first one to be removed.
3. The main operations of stack are push (insert) and pop (delete).
4. Another operation is peek, which shows the top element without removing it.
5. Stack uses a pointer called TOP to track the last inserted element.
6. When stack is full, it is called overflow condition.
7. When stack is empty, it is called underflow condition.
8. Stack can be implemented using array or linked list.
9. Push operation adds an element at the top.
10. Pop operation removes the top element.
11. Algorithm for PUSH: check overflow → increment TOP → insert element.
12. Algorithm for POP: check underflow → return element → decrement TOP.
13. Stack is used in expression evaluation and recursion.
14. It is easy to implement and understand.
15. Stack is widely used in programming and system design.

Q2. Stack Applications (Explain any three)

Answer

1. Stack is used in expression evaluation, such as postfix and prefix expressions.
2. It helps in checking balanced parentheses in expressions like ( ).
3. Stack is used in function calls and recursion, where each call is stored.
4. It is used in undo and redo operations in applications like text editors.
5. Stack is used in backtracking algorithms like maze solving.
6. It is helpful in syntax parsing in compilers.
7. Used in depth-first search (DFS) algorithm.
8. Helps in reversing data like strings.
9. Used in browser history navigation.
10. Supports memory management in programs.
11. Used in arithmetic expression conversion.
12. Helps in managing temporary data.
13. Efficient for last inserted element processing.
14. Widely used in software development.
15. Important for understanding recursion.

Q3. Stack in Recursion

Answer

1. Recursion is a process where a function calls itself repeatedly.
2. Stack is used internally to manage these function calls.
3. Each function call is stored as a stack frame.
4. The stack stores local variables and return address.
5. When a function is called, it is pushed onto the stack.
6. When a function completes, it is popped from the stack.
7. This follows LIFO principle.
8. Recursive calls create multiple stack entries.
9. When base condition is reached, stack starts unwinding.
10. If too many calls occur, it may cause stack overflow.
11. Example: factorial function uses recursion.
12. Stack helps maintain correct execution order.
13. It manages memory during recursion.
14. Without stack, recursion is not possible.
15. Stack is essential for recursive problem solving.

Q4. Prefix and Postfix Conversion

Answer

1. Prefix notation places operator before operands.
2. Example: +AB means A + B.
3. Postfix notation places operator after operands.
4. Example: AB+ means A + B.
5. Infix notation is the normal form (A + B).
6. Conversion is done using stack.
7. Operators have precedence like +, *, ^.
8. Stack stores operators temporarily.
9. Parentheses are handled carefully.
10. Higher precedence operators processed first.
11. Prefix and postfix avoid ambiguity.
12. Used in compilers and calculators.
13. Postfix is easier for evaluation.
14. No need for parentheses in postfix.
15. Conversion improves expression processing.

Q5. What is Queue? Difference from Stack

Answer

1. A queue is a linear data structure that follows FIFO (First In First Out).
2. The first element inserted is the first one to be removed.
3. Queue operations are enqueue (insert) and dequeue (delete).
4. Stack follows LIFO, queue follows FIFO.
5. In queue, insertion happens at rear.
6. Deletion happens from front.
7. Queue uses two pointers: front and rear.
8. Stack uses only one pointer (TOP).
9. Queue is used in scheduling tasks.
10. Stack is used in recursion.
11. Queue maintains order of arrival.
12. Stack reverses order of elements.
13. Queue is used in printers and buffers.
14. Both are linear data structures.
15. Both are important in programming.

Q6. Queue Implementation Algorithm

Answer

1. Queue uses FIFO principle.
2. Two pointers are used: front and rear.
3. Initially, both are set to -1.
4. Enqueue means inserting element at rear.
5. Dequeue means removing element from front.
6. Before inserting, check for overflow.
7. Before deleting, check for underflow.
8. Enqueue algorithm: increment rear → insert element.
9. Dequeue algorithm: return front element → increment front.
10. If queue is empty, front = rear = -1.
11. Queue can be implemented using array.
12. Also implemented using linked list.
13. Efficient for scheduling tasks.
14. Maintains proper order of data.
15. Used in real-time systems.

Q7. Circular Queue

Answer

1. Circular queue connects last position to first.
2. It solves problem of unused space in normal queue.
3. Rear moves in circular manner.
4. When rear reaches end, it goes to beginning.
5. Uses modulo operation for circular movement.
6. Efficient use of memory.
7. Prevents wastage of space.
8. Overflow occurs when queue is full.
9. Underflow occurs when queue is empty.
10. Operations are enqueue and dequeue.
11. Used in CPU scheduling.
12. Also used in buffering systems.
13. Improves performance over linear queue.
14. Requires careful pointer management.
15. Important concept in data structures.

Q8. Linked List and Types

Answer

1. A linked list is a collection of nodes connected by links.
2. Each node contains data and a pointer.
3. It does not require continuous memory.
4. It is a dynamic data structure.
5. Easy insertion and deletion.
6. Types of linked list include singly linked list.
7. Doubly linked list has two pointers.
8. Circular linked list connects last node to first.
9. Linked list is flexible.
10. Used in memory management.
11. Efficient for large data.
12. No fixed size required.
13. Access is sequential, not direct.
14. More memory required than array.
15. Important in dynamic applications.

Q9. Program for Singly Linked List

Answer

1. Singly linked list contains nodes with one pointer.
2. Each node points to next node.
3. First node is called head.
4. Last node points to NULL.
5. Nodes are created dynamically.
6. Insertion can be at beginning, middle, or end.
7. Deletion removes node from list.
8. Traversal means visiting all nodes.
9. Example in Python uses class Node.
10. Each node has data and next field.
11. Linked list grows dynamically.
12. No memory wastage.
13. Useful for dynamic data.
14. Easy insertion compared to array.
15. Important for data structure understanding.

 Q10. Program to Implement Stack

 Answer

1. Stack can be implemented using list in Python.
2. Use append() for push operation.
3. Use pop() for pop operation.
4. Stack follows LIFO principle.
5. Top element is last element of list.
6. Check if stack is empty before pop.
7. Use len() to check size.
8. Stack operations are simple.
9. Efficient for small applications.
10. Python list acts as stack.
11. No need for separate implementation.
12. Used in expression evaluation.
13. Easy to implement.
14. Useful in real-world problems.
15. Helps understand stack concept.

Q11. Insert Node at Specific Position in Linked List

Answer

1. First create a new node.
2. Assign data to the node.
3. Traverse list to desired position.
4. Keep track of previous node.
5. Adjust pointers carefully.
6. New node points to next node.
7. Previous node points to new node.
8. If inserting at beginning, update head.
9. If inserting at end, set next to NULL.
10. Check for invalid position.
11. Maintain list structure.
12. Avoid losing existing nodes.
13. Operation takes O(n) time.
14. Important for dynamic data handling.
15. Used in real applications like memory management.

 

UNIT 4: Sorting, Searching & Hashing

 

Q1. Bubble Sort Algorithm (Step-by-Step)

Answer

1. Bubble Sort is a simple sorting algorithm used to arrange elements in ascending or descending order.
2. It works by repeatedly comparing adjacent elements in the list.
3. If two elements are in the wrong order, they are swapped.
4. After each pass, the largest element moves to the end of the list.
5. This process is repeated until the list is completely sorted.
6. Number of passes required is n-1 for n elements.
7. It is called “bubble” sort because elements bubble up to their correct position.
8. It is easy to understand and implement.
9. Algorithm Step 1: Start from the first element.
10. Step 2: Compare it with the next element.
11. Step 3: Swap if needed.
12. Step 4: Continue till the end of list.
13. Step 5: Repeat passes until no swaps occur.
14. Time complexity is O(n²) in worst case.
15. It is not efficient for large datasets but useful for learning.

 Q2. Quick Sort on Given Data

Answer

1. Quick Sort is a divide and conquer algorithm used for fast sorting.
2. It selects a pivot element from the list.
3. All elements smaller than pivot go to the left side.
4. All elements greater than pivot go to the right side.
5. This process is called partitioning.
6. Then Quick Sort is applied recursively on both sides.
7. It continues until the list is fully sorted.
8. Example list: [100,25,35,85,75,95,12,52,1,3]
9. Choose pivot (e.g., first or last element).
10. Divide list into smaller and larger elements.
11. Recursively apply same process.
12. Combine sorted sublists.
13. Quick sort is faster than bubble sort.
14. Average time complexity is O(n log n).
15. It is widely used in real-world applications.

 Q3. Selection Sort Algorithm

Answer

1. Selection sort is a simple sorting technique.
2. It works by selecting the smallest element from the list.
3. The smallest element is placed at the correct position.
4. This process is repeated for all elements.
5. First pass: smallest element goes to first position.
6. Second pass: second smallest goes to second position.
7. It does not require swapping many times.
8. It performs fewer swaps compared to bubble sort.
9. Algorithm Step 1: Find minimum element.
10. Step 2: Swap with first position.
11. Step 3: Repeat for remaining elements.
12. Time complexity is O(n²).
13. It is easy to understand.
14. Not efficient for large datasets.
15. Useful for small lists.

Q4. Binary Search Program

Answer

1. Binary search is used to find an element in a sorted list.
2. It works by dividing the list into two halves.
3. First, find the middle element.
4. Compare middle element with target value.
5. If equal, element is found.
6. If target is smaller, search left half.
7. If target is larger, search right half.
8. Repeat process until element is found.
9. It reduces search space quickly.
10. Requires sorted data.
11. Much faster than linear search.
12. Time complexity is O(log n).
13. Uses low and high pointers.
14. Efficient for large datasets.
15. Commonly used in searching problems.

 Q5. What is Hashing and Characteristics of Good Hash Function

Answer

1. Hashing is a technique to store and retrieve data quickly.
2. It uses a function called hash function.
3. Hash function converts key into an index.
4. Data is stored at calculated index.
5. It provides fast access to data.
6. Used in hash tables.
7. A good hash function should be fast to compute.
8. It should distribute keys uniformly.
9. It should minimize collisions.
10. It should be deterministic (same input → same output).
11. Should use all parts of key.
12. Avoid clustering of values.
13. Improve search efficiency.
14. Used in databases and caching.
15. Important for fast data access.

 Q6. Collision in Hashing

Answer

1. Collision occurs when two keys map to same index.
2. It is a common problem in hashing.
3. Happens due to limited size of hash table.
4. Different keys may produce same hash value.
5. Collisions reduce efficiency.
6. Needs proper handling.
7. Cannot be completely avoided.
8. Must be minimized using good hash function.
9. Example: keys 10 and 20 giving same index.
10. Causes overwriting if not handled.
11. Leads to incorrect data retrieval.
12. Increases search time.
13. Requires resolution techniques.
14. Important concept in hashing.
15. Must be managed carefully.

 Q7. Collision Resolution Techniques

Answer

1. Collision resolution is used to handle collisions in hashing.
2. One method is chaining.
3. In chaining, each index stores a linked list.
4. Multiple elements can be stored at same index.
5. Another method is open addressing.
6. In open addressing, find next empty slot.
7. Linear probing checks next index sequentially.
8. Quadratic probing uses square increments.
9. Double hashing uses another hash function.
10. Helps maintain efficiency.
11. Prevents data loss.
12. Ensures correct retrieval.
13. Improves performance.
14. Required in hash table design.
15. Important for real applications.

 Q8. Merge Sort Example

Answer

1. Merge sort is a divide and conquer algorithm.
2. It divides list into smaller parts.
3. Each part is sorted individually.
4. Then parts are merged together.
5. Example: [38,27,43,3,9,82,10]
6. Divide into two halves repeatedly.
7. Continue until single elements remain.
8. Merge sorted elements step by step.
9. Maintain order while merging.
10. Produces sorted list at end.
11. Time complexity is O(n log n).
12. Stable sorting algorithm.
13. Requires extra memory.
14. Efficient for large data.
15. Widely used in applications.

 Q9. Linear Search Algorithm

Answer

1. Linear search checks elements one by one.
2. It starts from first element.
3. Compares each element with target.
4. Stops when element is found.
5. If not found, returns failure.
6. Works on unsorted data.
7. Easy to implement.
8. No special requirement.
9. Time complexity is O(n).
10. Not efficient for large data.
11. Suitable for small lists.
12. Used in simple programs.
13. Sequential process.
14. No extra memory needed.
15. Basic searching technique.

 Q10. Bubble Sort Passes on Given Data

Answer

1. Given list: [100,25,35,85,75,95,12,52,1,3]
2. Compare first two elements and swap if needed.
3. Largest element moves to end in first pass.
4. Continue comparing adjacent elements.
5. After first pass, largest element is fixed.
6. Second pass sorts next largest.
7. Continue passes until sorted.
8. Total passes = n-1.
9. Each pass reduces unsorted part.
10. Repeated swapping occurs.
11. Easy but slow method.
12. Time complexity is O(n²).
13. Good for understanding sorting.
14. Not suitable for large data.
15. Demonstrates working of algorithm clearly.

 Q11. Merge Sort Explanation

Answer

1. Merge sort divides list into halves.
2. Uses recursive approach.
3. Each half is sorted separately.
4. Then merged in sorted order.
5. Combines smaller lists into bigger list.
6. Maintains order while merging.
7. Uses extra memory.
8. Time complexity is O(n log n).
9. Efficient for large datasets.
10. Stable sorting algorithm.
11. Works well for linked lists.
12. Suitable for external sorting.
13. Better than bubble sort.
14. Requires divide and conquer strategy.
15. Important sorting algorithm.

 

UNIT 5: Nonlinear Data Structures – Trees & Graphs

 

Q1. Tree Terminologies (Root, Parent, Child, Leaf, Sibling)

Answer

1. A tree is a hierarchical data structure where data is arranged like a tree shape.
2. The topmost node of a tree is called the root node.
3. Root is the starting point of the tree.
4. A parent node is a node that has one or more child nodes.
5. A child node is a node that comes under another node.
6. A node can have multiple children depending on the tree type.
7. A leaf node is a node that has no children.
8. Leaf nodes are always present at the bottom of the tree.
9. Sibling nodes are nodes that share the same parent.
10. Example: children of same parent are siblings.
11. Each node may have a link to its children.
12. Tree structure represents real-life hierarchy like family tree.
13. These terms help understand tree structure clearly.
14. Used in file systems and databases.
15. Important for understanding advanced data structures.

Q2. Binary Tree and Its Types 

Answer

1. A binary tree is a tree where each node has maximum two children.
2. These children are called left child and right child.
3. Binary tree is widely used in computer science.
4. One type is full binary tree, where each node has 0 or 2 children.
5. Another type is complete binary tree, where all levels are filled except last.
6. In complete tree, nodes are filled from left to right.
7. Perfect binary tree has all levels completely filled.
8. Balanced binary tree maintains minimum height.
9. Balanced tree improves search performance.
10. Binary trees are used in searching and sorting.
11. Example: Binary Search Tree (BST).
12. Helps in efficient data storage.
13. Easy to traverse using different methods.
14. Important in expression trees.
15. Used in many real-world applications.

Q3. BST Insertion and Deletion

Answer

1. A Binary Search Tree (BST) follows rule: left < root < right.
2. During insertion, compare value with root.
3. If smaller, go to left subtree.
4. If larger, go to right subtree.
5. Repeat until correct position is found.
6. Insert new node at leaf position.
7. Example: inserting 50, 30, 70 creates BST structure.
8. Deletion has three cases.
9. Case 1: deleting leaf node (simple removal).
10. Case 2: node with one child (replace node with child).
11. Case 3: node with two children (replace with inorder successor).
12. Inorder successor is smallest node in right subtree.
13. After deletion, tree must maintain BST property.
14. BST allows efficient searching.
15. Important for database indexing.

Q4. Tree Traversals (Inorder, Preorder, Postorder)

Answer

1. Tree traversal means visiting all nodes in a specific order.
2. Inorder traversal follows Left → Root → Right.
3. It gives sorted output in BST.
4. Preorder traversal follows Root → Left → Right.
5. Used to create copy of tree.
6. Postorder traversal follows Left → Right → Root.
7. Used in deleting tree.
8. Traversals can be done using recursion.
9. Each traversal has its own use.
10. Inorder is most commonly used.
11. Preorder is useful in expression trees.
12. Postorder is useful in evaluation.
13. Traversal helps in accessing all nodes.
14. Important for tree operations.
15. Basic concept in tree data structure.

Q5. Graph Traversal Technique

Answer

1. Graph traversal means visiting all vertices of a graph.
2. It is used to explore all nodes.
3. Two main techniques are DFS and BFS.
4. Traversal ensures all nodes are visited once.
5. It uses data structures like stack or queue.
6. Helps in searching and path finding.
7. Used in networking and maps.
8. Avoids visiting same node again.
9. Uses visited array or list.
10. Works for both directed and undirected graphs.
11. Important for algorithm design.
12. Helps solve real-world problems.
13. Efficient for large graphs.
14. Used in AI and game development.
15. Basic concept in graph theory.

Q6. Adjacency Matrix vs Adjacency List

Answer

1. Adjacency matrix uses a 2D array to represent graph.
2. Rows and columns represent vertices.
3. Value 1 means edge exists, 0 means no edge.
4. Easy to implement.
5. Requires more memory.
6. Adjacency list uses list of nodes.
7. Each vertex stores list of connected nodes.
8. Uses less memory than matrix.
9. Efficient for sparse graphs.
10. Matrix is good for dense graphs.
11. List is flexible and dynamic.
12. Matrix is faster for edge checking.
13. List is better for traversal.
14. Both represent graph differently.
15. Choice depends on application.

Q7. Depth First Search (DFS)

Answer

1. DFS is a graph traversal technique.
2. It explores as far as possible before backtracking.
3. Uses stack or recursion.
4. Start from a node and go deep.
5. Visit one node at a time.
6. Mark visited nodes.
7. Avoid revisiting nodes.
8. Backtrack when no more nodes available.
9. Works for all graph types.
10. Used in maze solving.
11. Used in cycle detection.
12. Time complexity is O(V+E).
13. Efficient for deep search.
14. Easy to implement recursively.
15. Important graph algorithm.

Q8. Deletion in Binary Search Tree

Answer

1. Deletion in BST must maintain BST property.
2. First find the node to delete.
3. Case 1: node is a leaf → simply remove it.
4. Case 2: node has one child → replace with child.
5. Case 3: node has two children.
6. Find inorder successor or predecessor.
7. Replace node with successor value.
8. Delete successor node.
9. Maintain tree structure.
10. Use recursion for implementation.
11. Ensure tree remains balanced if possible.
12. Important for dynamic data.
13. Efficient operation.
14. Used in databases.
15. Important for tree operations.

:: Best of Luck ::