Computational Structures
A curated list of fundamental questions and answers for Unit 04.
1. Explain how the ‘extend()’ function works in python lists. Provide an example.
The extend() function in Python is used to add all the elements from an iterable (like a list, tuple, or string) to the end of the current list. Unlike append() which adds the entire iterable as a single element, extend() adds each item individually.
For example, if you have a list a = [1, 2, 3] and you call a.extend([4, 5]), the list a becomes [1, 2, 3, 4, 5]. The function modifies the original list in place.
2. Explain the potential issues which could arise when two variables reference the same list in a program? Provide an example.
If two variables point to the same list, any change made through one variable will affect the other, because both refer to the exact same object in memory. This can lead to unintended side effects.
Example:
a = [1, 2, 3]
b = a # 'b' now references the same list as 'a'
b.append(4)
print(a) # Output: [1, 2, 3, 4]To avoid this, you can create a separate copy of the list using the copy() method: b = a.copy().
3. Define a stack and explain the Last-In, First-Out (LIFO) principle.
A stack is a data structure where elements are added and removed from the same end, called the “top.” It operates on the Last-In, First-Out (LIFO) principle, meaning the last item added is the first one to be removed.
4. How does the stack help in balancing parentheses in an expression? Describe the process.
A stack is used to ensure every opening parenthesis has a matching closing parenthesis. The process is:
- Scan the expression. When an opening parenthesis `(` is found, push it onto the stack.
- When a closing parenthesis `)` is found, try to pop an element from the stack.
- If the stack is empty after scanning the whole expression, the parentheses are balanced.
- If you try to pop from an empty stack, or if the stack is not empty at the end, the parentheses are unbalanced.
5. Differentiate between the Enqueue and Dequeue operations of a queue.
Enqueue: Adds an item to the back (end) of the queue.
Dequeue: Removes an item from the front of the queue.
6. Explain how the concept of a queue is applied in a computer job scheduling system.
In job scheduling, jobs are placed in a queue in the order they arrive. The system processes them based on the First-In, First-Out (FIFO) principle, so the first job added is the first one to be executed. A print queue is a common example.
7. How can lists be utilized to implement other data structures?
Python lists are versatile and can implement other data structures like stacks (using `append()` for push and `pop()` for pop) and queues (using `append()` for enqueue and `pop(0)` for dequeue). They can also represent 2D arrays (matrices) using nested lists.
8. Differentiate between the Depth-First Search (DFS) and Breadth-First Search (BFS).
| Feature | DFS | BFS |
|---|---|---|
| Search Type | Goes deep into each path first | Explores level by level |
| Data Structure | Stack (or recursion) | Queue |
| Memory Usage | Less (usually) | More |
| Best For | Solving puzzles, maze-like problems | Finding shortest paths |