DS 57 Exam Terminologies
Studied by 0 people
Learn
Practice Test
Spaced Repetition
Match
Flashcards1/49
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
50 Terms
What does Big O notation describe?
The upper bound of an algorithm's runtime.
What is the time complexity of binary search?
O(log n)
What is the time complexity of accessing an element in an array?
O(1)
What data structure uses contiguous memory for elements of the same type?
Array
What Python structure is mutable and ordered?
List
What Python structure is immutable and ordered?
Tuple
What is a dictionary in Python?
A key-value mapping with fast lookup.
What Python structure allows only unique values and is unordered?
Set
What is recursion?
A function that calls itself to solve smaller subproblems.
Why is a base case important in recursion?
To prevent infinite recursion.
What is the time complexity of linear search?
O(n)
Which algorithm divides the problem into smaller subproblems?
Divide and Conquer
Which algorithm stores results to avoid recalculating?
Dynamic Programming
Which algorithm makes the best decision at each step?
Greedy Algorithm
What is the main benefit of using a linked list?
Efficient insertion and deletion.
What is the drawback of using linked lists compared to arrays?
No direct access to elements.
What type of linked list allows backward and forward traversal?
Doubly linked list
What is a circular linked list?
A linked list where the last node points to the head.
What is the time complexity of inserting an element in a list?
O(n)
What is the space complexity of recursive factorial?
O(n)
What does O(n^2) time complexity usually result from?
Nested loops.
What is a brute-force algorithm?
An algorithm that tries all possible solutions.
What is the time complexity of merge sort?
O(n log n)
What does the in keyword check in Python?
Membership in a collection.
What is the use of len() in Python?
Returns the number of elements.
Which data structure is ideal for storing key-value pairs?
Dictionary
Which Python structure allows duplicates and is ordered?
List
What function returns both index and item during iteration?
enumerate()
Which data structure allows constant-time lookups by key?
Dictionary
Which Python structure cannot change once created?
Tuple
How do you access an element in a 2D array at row i, column j?
array[i][j]
Which type of loop leads to logarithmic time complexity?
Loop that halves the data each iteration.
What type of list is best for constant-time appends?
List
What is the complexity of a loop within a loop over the same data?
O(n^2)
What function removes the last item in a list?
pop()
How is a tuple different from a list?
Tuples are immutable.
Which method adds an item to the end of a list?
append()
How do sets handle duplicate values?
They automatically remove them.
What is the purpose of the hash function in dictionaries?
To map keys to indexes.
What is a randomized algorithm?
An algorithm that uses randomness to decide steps.
What is a singly linked list?
A list where each node points only to the next.
What does max() do in Python?
Returns the largest element.
What is the time complexity of accessing a dictionary value?
O(1)
What structure is preferred for fast membership testing?
Set
What is the overall complexity of merge sort?
O(n log n)
What is the space complexity of a list with n elements?
O(n)
Which operation is faster in a tuple compared to a list?
Iteration.
What is the default time complexity of deleting an item from a list?
O(n)
What type of algorithm guarantees an optimal result in all cases?
None - greedy and others don't guarantee optimality.
Which Python type can be used as dictionary keys?
Tuple