Python Data Structures Exam Guide
Uploaded by
Farhan KaziPython Data Structures Exam Guide
Uploaded by
Farhan KaziCommon questions
Powered by AIThe Greedy method makes locally optimal choices at each stage with the hope of finding a global optimum, often used in problems like the shortest path and minimum spanning tree. Big-O notation describes the upper bound of an algorithm’s runtime, focusing on the largest growth rate term as input size increases, and is crucial for evaluating worst-case scenarios of algorithm performance. It helps compare the efficiency of different algorithms .
OOP is important because it allows for the structuring of software in a manner that is both scalable and maintainable. It facilitates modularity and reusability. The 'Class' is a blueprint for creating objects, providing initial values for state (attributes) and implementations of behavior (methods). 'Abstraction' involves hiding the complex reality while exposing only the necessary parts of an object. 'Encapsulation' is the bundling of data with the methods that operate on that data, restricting access to some components and protecting the integrity of the object’s data .
For separate chaining with h(X) = X (mod 10), bucket 1 gets [4371], bucket 3 gets [1323, 6173, 9679, 1989], and bucket 4 gets [4199, 4344]. In open addressing with linear probing, 4371 goes to slot 1, 1323 to 3, 6173 follows after 6173 at slot 4 due to linear probing, and similarly for other clashes. For quadratic probing, positions are calculated using (i^2), e.g., 1323 at 3, 6173 at first clash tries (3+1^2)=4, at next (3+2^2)=7 until a slot is found free .
Evaluating a postfix expression using a stack involves scanning the expression from left to right and using a stack to keep operands. Operands are pushed onto the stack, while operators pop two operands for evaluation. For '4 + 9 3 - *': start with empty stack, push 4, push 9, find '-' then pop 9 and 3, compute 9-3 = 6, push result. Push '*', pop 6 and 4, compute 4*6 = 24, push result. The final result on the stack is 24 .
Exception handling in Python is done using try-except blocks, where the try block contains code that may cause an exception, and the except block lets you handle the error. Multiple errors can be handled using a single except statement by specifying a tuple of exceptions. For example, 'except (TypeError, ValueError) as e:' will catch both TypeError and ValueError exceptions. This allows for concise code when the exception handling logic is the same for different types of errors .
The 'len()' function returns the number of items in an object, where the syntax is len(object). For example, 'len("hello")' returns 5. The 'max()' function returns the largest item in an iterable, using the syntax max(iterable). For instance, 'max("hello")' returns 'o'. The 'min()' function returns the smallest item in an iterable with 'min(iterable)' as syntax, like 'min("hello")' which returns 'e'. The 'isdigit()' method checks if all characters in a string are digits with the syntax string.isdigit(), such as '"123".isdigit()' which returns True .
Binary tree traversals are methods of visiting every node in a tree exactly once. Inorder traversal visits left subtree, root, then right subtree. The algorithm is: 1) Traverse the left subtree, 2) Visit the node, 3) Traverse the right subtree. Preorder traversal visits nodes in order: root, left subtree, right subtree. The algorithm is: 1) Visit the node, 2) Traverse the left subtree, 3) Traverse the right subtree. Postorder traversal visits nodes in order: left subtree, right subtree, root. The algorithm is: 1) Traverse the left subtree, 2) Traverse the right subtree, 3) Visit the node .
A Queue is a linear data structure that follows the First In First Out (FIFO) principle. It can be implemented using a Python list by using the append() method to enqueue elements at the end and the pop(0) method to dequeue elements from the front. For example, using 'queue = []', 'queue.append(1)' enqueues 1, and 'queue.pop(0)' dequeues the first element. This implementation is simple but may be inefficient for large data since the pop(0) operation is O(n).
A linked list is a linear data structure consisting of nodes; each node contains data and a reference to the next node in the sequence. Polynomial addition using a linked list involves traversing two polynomial linked lists simultaneously, adding coefficients of terms with the same degree, and creating a new node for each resulting term in the sum linked list. For P(x) = 12x^4 + 2x^2 + 10 and Q(x) = 9x^3 + 8x^2 + x, traverse both lists: 12x^4 remains unchanged, 9x^3 is added directly since it has no pair, and 2x^2 + 8x^2 becomes 10x^2. Therefore, the resulting polynomial will be 12x^4 + 9x^3 + 10x^2 + x + 10 .
Linear search checks each element sequentially and is O(n) in complexity. For x = 35, it requires 5 comparisons, and for x = 28, 4 comparisons. Binary search requires the list to be sorted and is O(log n) in complexity. For x = 35, binary search involves comparing with the middle element and then the right subset (35 is found in 3 comparisons). For x = 28, after comparing with the middle element, the search continues in the left subset (found in 2 comparisons). Binary search is more efficient than linear search for sorted data .