Part A: Multiple Choice Questions (MCQs)
1. Which of the following best defines a data structure?
a. A method of communication
b. A way to store and organize data in memory
c. A system for internet access
d. A graphical interface design
Answer: b. A way to store and organize data in memory
Explanation: A data structure is a specialized format for organizing, processing, retrieving, and storing data in a computer's memory so that it can be accessed and used efficiently.
2. Which data structure allows dynamic memory allocation and easy insertion/deletion?
a. Array
b. Stack
c. Linked List
d. Queue
Answer: c. Linked List
Explanation: A linked list consists of nodes that are dynamically allocated. Insertion and deletion are efficient because they only require changing pointers, unlike arrays which have a fixed size.
3. In a singly linked list, each node contains:
a. Data and address of previous node
b. Only data
c. Data and address of next node
d. Index value and data
Answer: c. Data and address of next node
Explanation: A node in a singly linked list contains the data and a pointer (reference) to the next node in the sequence. It does not have a pointer to the previous node (that's a doubly linked list).
4. The main advantage of a doubly linked list over a singly linked list is:
a. Random access
b. Uses less memory
c. Allows traversal in both directions
d. Faster arithmetic operations
Answer: c. Allows traversal in both directions
Explanation: A doubly linked list has pointers to both the next and previous nodes, allowing traversal in both forward and backward directions. The trade-off is increased memory usage.
5. What type of linked list connects the last node back to the first?
a. Doubly linked list
b. Circular linked list
c. Singly linked list
d. Linear linked list
Answer: b. Circular linked list
Explanation: In a circular linked list, the last node's pointer points back to the first node, forming a circle. This is useful for applications that require continuous cycling.
6. Which operation removes the top element from a stack?
a. Enqueue
b. Dequeue
c. Pop
d. Top
Answer: c. Pop
Explanation: The pop operation removes and returns the top element of a stack. Push adds an element. Enqueue and Dequeue are queue operations.
7. Which node in a tree does not have any children?
a. Root node
b. Leaf node
c. Sibling node
d. Parent node
Answer: b. Leaf node
Explanation: A leaf node is a node that has no children. The root node is the topmost node, siblings share the same parent, and a parent node has children.
8. Which data structure operates on a Last-In, First-Out (LIFO) principle?
a. Array
b. Stack
c. Queue
d. Tree
Answer: b. Stack
Explanation: A stack follows the LIFO principle, where the last element added is the first one to be removed. A queue follows FIFO (First-In, First-Out).
9. Which algorithm is used for sorting data?
a. Quick Sort
b. Binary Search
c. Depth-First Search
d. Euclidean Algorithm
Answer: a. Quick Sort
Explanation: Quick Sort is a sorting algorithm. Binary Search is for searching. Depth-First Search is for traversing graphs/trees. Euclidean Algorithm is for finding GCD.
10. Which algorithm is an example of a Greedy Algorithm?
a. Bubble Sort
b. Huffman Coding
c. Depth-First Search
d. Binary Search
Answer: b. Huffman Coding
Explanation: Huffman Coding is a greedy algorithm used for lossless data compression. It makes the locally optimal choice at each
step to build the optimal prefix code.
11. What is the space complexity of the Binary Search Algorithm?
a. O(1)
b. O(n)
c. O(log n)
d. O(n^2)
Answer: a. O(1)
Explanation: The iterative version of Binary Search has a space complexity of O(1) because it uses a constant amount of extra space. The recursive version has O(log n) space complexity due to the call stack.
12. Which data structure allows random access to elements by index?
a. Stack
b. Queue
c. Array
d. Tree
Answer: c. Array
Explanation: Arrays store elements in contiguous memory locations, allowing direct access to any element using its index in constant time O(1). Stacks, queues, and trees do not allow random access.
13. A school wants to automate the process of generating student report cards based on input marks. Which step of computational thinking would most likely involve identifying how to separate marks by subject, calculate averages, and assign grades?
a. Decomposition
b. Pattern Recognition
c. Abstraction
d. Algorithm Design
Answer: a. Decomposition
Explanation: Decomposition is the process of breaking down a complex problem into smaller, more manageable sub-problems. Separating the task into "calculate averages," "assign grades," etc., is a clear example of decomposition.
14. What is the time complexity of Linear Search?
a. O(1)
b. O(log n)
c. O(n)
d. O(n^2)
Answer: c. O(n)
Explanation: Linear search examines each element in the list one by one until the target is found or the list ends. In the worst case, it examines all 'n' elements, giving a time complexity of O(n).
15. During an inter-school tech competition, students were asked to develop a solution for managing traffic signals based on traffic density. Which approach best shows their use of computational thinking?
a. They memorized how traffic lights work in real life.
b. They created a flowchart outlining how traffic signal timing changes with vehicle count.
c. They guessed a solution based on their intuition.
d. They programmed a random timer for each signal.
Answer: b. They created a flowchart outlining how traffic signal timing changes with vehicle count.
Explanation: Creating a flowchart to model the logic of the system (traffic signal timing based on vehicle count) demonstrates the computational thinking skills of algorithm design and modeling a solution.
Part B: Short Answer Questions
Problem 1: Finding the Sum of Digits Problem Statement: Given an integer, calculate the sum of its digits.
Solution: Digit Extraction and Summation Give answer of the following:
a) Algorithm
Answer:
1. Start.
2. Initialize sum = 0.
3. Read input integer n.
4. While n > 0 :
Extract the last digit: digit = n % 10.
Add digit to sum: sum = sum + digit.
Remove the last digit: n = n / 10 (integer division).
5. Print sum.
6. End.
b) Efficiency (Time Complexity and Space Complexity)
Answer:
Time Complexity: O(log n) or O(d), where d is the number of digits in the number. The number of iterations is proportional to the number of digits. Space Complexity: O(1). Only a constant amount of extra space is used for variables like sum and digit.
c) Clarity
Answer: The algorithm is simple and clear. The steps of extracting the last digit using modulo and removing it using integer division are standard and easy to understand.
d) Correctness
Answer: The algorithm is correct because it systematically processes each digit of the number until no digits remain, accumulating the sum accurately. It handles positive integers. (For negative numbers, one would need to take the absolute value first.)
Problem 2: Finding the Factorial of a Number Problem Statement: Compute the factorial of a non-negative integer n (i.e., n!).
Solution: Iterative Approach Give answer of the following:
a) Algorithm
Answer:
1. Start.
2. Initialize factorial = 1.
3. Read input integer n.
4. If n < 0, print "Factorial not defined for negative numbers" and stop.
5. For i from 1 to n :
factorial = factorial * i.
6. Print factorial.
7. End.
b) Efficiency (Time Complexity and Space Complexity)
Answer:
Time Complexity: O(n). The loop runs 'n' times. Space Complexity: O(1). Only a constant amount of extra space is used for variables factorial and i.
c) Clarity
Answer: The iterative approach is very clear and easy to follow. The logic is straightforward: multiply numbers from 1 to n.
d) Correctness
Answer: The algorithm is correct. It computes the product of all integers from 1 to n. The base case for n=0 is handled correctly (0! = 1). It also handles negative input gracefully.
Problem 3: Finding the Largest Number in a List Problem Statement: Given a list of integers, find the largest number in the list.
Solution: Linear Scan Give answer of the following:
a) Algorithm
Answer:
1. Start.
2. Read the list of numbers L.
3. If L is empty, print "List is empty" and stop.
4. Initialize max = L[0] (assume first element is the largest).
5. For each element x in L (starting from the second element):
If x > max, then max = x.
6. Print max.
7. End.
b) Efficiency (Time Complexity and Space Complexity)
Answer:
Time Complexity: O(n). The algorithm must examine each element in the list once to determine the maximum. Space Complexity: O(1). Only a constant amount of extra space is used for the max variable.
c) Clarity
Answer: The algorithm is very clear and intuitive. It uses a simple linear scan to find the maximum.
d) Correctness
Answer: The algorithm is correct. It correctly initializes the maximum with the first element and then updates it whenever a larger element is found. It handles lists of any size (assuming non-empty).
Problem 4: Checking for Prime Numbers Problem Statement: Determine if a given integer n is a prime number (i.e., it has no divisors other than 1 and itself).
Solution: Simple Divisibility Test Give answer of the following:
a) Algorithm
Answer:
1. Start.
2. Read input integer n.
3. If n <= 1, print "Not Prime" and stop.
4. For i from 2 to sqrt(n) :
If n % i == 0, print "Not Prime" and stop.
5. Print "Prime".
6. End.
b) Efficiency (Time Complexity and Space Complexity)
Answer:
Time Complexity: O([source symbol unavailable]n). The loop runs up to the square root of n. Space Complexity: O(1). Only a constant amount of extra space is used.
c) Clarity
Answer: The algorithm is clear and efficient. The use of sqrt(n) as the upper bound is a standard optimization.
d) Correctness
Answer: The algorithm is correct. If a number n has a divisor greater than its square root, it must also have a divisor smaller than its square root. Therefore, checking up to [source symbol unavailable]n is sufficient.
Problem 5: Finding the Average of a List Problem Statement: Calculate the average value of a list of numbers.
Solution: Summation and Division Give answer of the following:
a) Algorithm
Answer:
1. Start.
2. Read the list of numbers L.
3. If L is empty, print "List is empty" and stop.
4. Initialize sum = 0.
5. For each element x in L :
sum = sum + x.
6. Calculate average = sum / length(L).
7. Print average.
8. End.
b) Efficiency (Time Complexity and Space Complexity)
Answer:
Time Complexity: O(n). The algorithm must iterate through the list once to calculate the sum. Space Complexity: O(1). Only a constant amount of extra space is used for sum and average.
c) Clarity
Answer: The algorithm is simple and straightforward.
d) Correctness
Answer: The algorithm is correct. It correctly calculates the sum of all elements and divides by the number of elements to find the average. It handles the empty list case.
6. How can abstraction help a student create a simple timetable app for school?
Answer: Abstraction helps a student create a timetable app by allowing them to focus on the essential features and hide unnecessary details. The student can abstract the complex scheduling logic into simple components: a "Class" object with properties like subject, teacher, and time; a "Day" object containing a list of classes; and a "Timetable" object containing a list of days. They can ignore the underlying complexities of how the data is stored or how the UI renders, focusing instead on the logic of adding, removing, and displaying classes. This simplifies the design and implementation process.
7. A shopkeeper wants to use a program to quickly find a product in a long list. Which type of algorithm should they use and why?
Answer: The shopkeeper should use a search algorithm. Specifically, if the list is sorted (e.g., alphabetically by product name or by product ID), they should use Binary Search. Binary search is highly efficient with a time complexity of O(log n), meaning it can find an item in a large list very quickly by repeatedly dividing the search interval in half. If the list is unsorted, they would need to use Linear Search (O(n)), but it would be much slower for a long list. Therefore, sorting the list and using Binary Search is the best approach.
Part C: Long Answer Questions
1. Compare and evaluate the efficiency of Bubble Sort and Merge Sort in sorting a list of 1,000 student names. Discuss in terms of time complexity and clarity. Which is more suitable and why?
Answer: Bubble Sort:
Time Complexity: O(n²) in the worst and average cases. For 1,000 names, this means approximately 1,000,000 comparisons. It is very slow for large datasets. Clarity: Bubble Sort is very easy to understand and implement. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Merge Sort:
Time Complexity: O(n log n) in all cases. For 1,000 names, this is approximately 1,000 × 10 = 10,000 operations. It is much faster and more efficient for large datasets. Clarity: Merge Sort is more complex to understand and implement. It uses a divide-and-conquer approach, recursively dividing the list into smaller sublists, sorting them, and then merging them back together.
Comparison and Evaluation: For a list of 1,000 student names, Merge Sort is far more suitable due to its superior time complexity. Bubble Sort would take
significantly longer to sort the list. While Bubble Sort is easier to code, the performance gain of Merge Sort is crucial for larger datasets. In a real-world application, efficiency is paramount. Therefore, despite its complexity, Merge Sort is the better choice.
2. Describe the difference between Stack and Queue. How does their operation affect algorithm design? Provide one real-life example for each data structure.
Answer: Stack:
Principle: Last-In, First-Out (LIFO). Operations: push (add to top), pop (remove from top), peek (view top). Algorithm Design: Stacks are used in algorithms that require reversing order, backtracking, or managing function calls (recursion). For example, in depth-first search (DFS), a stack is used to keep track of the path. Real-life Example: A stack of plates in a cafeteria. The last plate placed on top is the first one to be taken.
Queue:
Principle: First-In, First-Out (FIFO). Operations: enqueue (add to rear), dequeue (remove from front), peek (view front). Algorithm Design: Queues are used in algorithms that require processing items in the order they arrive, such as breadth- first search (BFS), task scheduling, and buffer management. Real-life Example: A line of people waiting to buy tickets. The first person in line is the first to be served.
Conclusion: The choice between a stack and a queue depends on the order in which data needs to be processed. Stacks are for LIFO, and queues are for FIFO.
3. Explain the importance of tree traversal techniques. Compare in-order, pre-order, and post-order traversal with examples and their use cases.
Answer: Importance of Tree Traversal: Tree traversal is the process of visiting each node in a tree exactly once. It is essential for searching, inserting, deleting, and displaying data in a tree structure.
Types of Traversal:
In-order Traversal (Left, Root, Right): Visits the left subtree, then the root, then the right subtree. For a Binary Search Tree (BST), in-order traversal yields nodes in ascending order.
Example: For a BST with nodes 2, 1, 3, in-order gives 1, 2, 3. Use Case: Sorting data in a BST.
Pre-order Traversal (Root, Left, Right): Visits the root, then the left subtree, then the right subtree.
Example: For the same BST, pre-order gives 2, 1, 3. Use Case: Creating a copy of a tree, or generating a prefix expression from an expression tree.
Post-order Traversal (Left, Right, Root): Visits the left subtree, then the right subtree, then the root.
Example: For the same BST, post-order gives 1, 3, 2. Use Case: Deleting a tree, or generating a postfix expression from an expression tree.
Conclusion: Each traversal method has specific use cases. In-order is for sorted output, pre-order for copying, and post-order for deletion.
4. How does abstraction help in computational thinking? Explain with an example.
Answer: Abstraction is a key component of computational thinking. It involves filtering out unnecessary details and focusing on the essential
features of a problem. This simplifies complex problems, making them easier to solve.
How it Helps:
Simplification: By hiding irrelevant details, abstraction reduces complexity. Generalization: It allows us to create general solutions that can be applied to similar problems. Focus: It helps in focusing on the core logic rather than implementation details.
Example: Consider designing a GPS navigation app. Instead of worrying about the internal combustion engine of the car, the type of tires, or the color of the car, we abstract these away. We focus on the essential elements: the current location, the destination, the road network, and the traffic conditions. We model the problem as finding the shortest path in a graph, where nodes are locations and edges are roads. This abstraction allows us to design a routing algorithm (like Dijkstra's) without needing to know the mechanical details of the vehicle. The user interacts with a simple interface showing a map and directions, hiding the complex computations and data structures used to calculate the route.
5. A hospital wants to design a system to manage patient records. Which data structure(s) would be best for storing and retrieving patient information quickly? Justify your choice.
Answer: For a hospital patient record system, the best data structure would be a combination of a Hash Table (or Dictionary) and a Database (like a Relational Database or NoSQL Database).
Hash Table / Dictionary:
Use: For quick lookup of patient records by a unique identifier (e.g., Patient ID, Social Security Number). Justification: A hash table allows for O(1) average time complexity for insertion, deletion, and retrieval. This is ideal for fast access to individual patient records.
Database (Relational or NoSQL):
Use: For persistent storage, complex queries (e.g., finding all patients with a specific condition), and maintaining relationships between data (e.g., patient, doctor, appointments). Justification: A database provides data integrity, security, and the ability to handle large volumes of data. It also supports ACID (Atomicity, Consistency, Isolation, Durability) properties, which are critical for medical records.
Conclusion: A hybrid approach, where the database is the primary storage and a hash table (or cache) is used for fast in-memory access to frequently accessed records, would be the most efficient design. A simple array or linked list would not be suitable due to slow search times for large datasets. A tree structure (like a B-tree) could be used for indexing within the database.
6. How can algorithm design be used to solve a real-world problem? Provide an example.
Answer: Algorithm design is the process of defining a step-by-step procedure to solve a specific problem. It is fundamental to solving real- world problems efficiently.
Example: Route Planning in a Delivery Service
Problem: A delivery company needs to find the most efficient route for its delivery trucks to visit multiple locations and return to the depot. Algorithm Design: This is a classic example of the Traveling Salesperson Problem (TSP). We can design an algorithm (e.g., a greedy algorithm or a heuristic like nearest neighbor) to find a near-optimal route. Steps:
A. Model the locations as nodes in a graph.
B. Model the roads as edges with weights representing distance or time.
C. Design an algorithm to find the shortest Hamiltonian cycle (a path that visits each node exactly once and returns to the start).
Solution: The algorithm outputs the order in which to visit the locations, minimizing total travel time and fuel
consumption.
Conclusion: Algorithm design provides a systematic approach to solving complex real-world problems, leading to efficient and effective solutions.