C949v4 Study Guide Flashcards
What is the percentage of the assessment that explains algorithms?
29%
What type of search algorithm is linear search?
A basic search algorithm that checks each element sequentially.
What is binary search?
A search algorithm that finds the position of a target value in a sorted array by repeatedly dividing the search interval in half.
Define Big O in the context of time complexity.
A notation used to describe the upper limit of the time complexity of an algorithm.
What is the time complexity of Selection Sort?
O(n^2)
What is the time complexity of Merge Sort?
O(n log n)
What does .pop() do in stacks?
Removes and returns the top element from the stack.
What is a hash table?
A data structure that uses a hash function to map keys to indices of an array for efficient storage and retrieval.
What is the main distinction of a tuple?
Tuples are immutable, meaning their values cannot be changed.
Fill in the blank: A _______ follows the Last-In-First-Out (LIFO) principle.
stack
What is garbage collection?
A process by which a computer’s memory is automatically managed, freeing up memory no longer used.
What are the two possible values of a Boolean data type?
true or false
What is the function of a queue?
A collection of elements that follows the First-In-First-Out (FIFO) principle.
What does a priority queue do?
Dequeues elements based on their priority rather than their insertion order.
What is a binary search tree?
A binary tree where each node has at most two children, with the left child being less than the parent and the right child being greater.
What are the main operations of a deque?
- append()
- appendleft()
- pop()
- popleft()
What is the purpose of the modulo operator in hash tables?
To compute the index for storing the key in the hash table.
What is the average-case time complexity for basic operations in hash tables?
O(1)
What does tree traversal refer to?
The process of visiting each node in a tree in a specific order.
What are the three types of tree traversal?
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
What is the definition of a set?
An unordered collection of unique elements.
What does the term ‘linked allocation’ refer to?
A memory allocation technique where memory is allocated in linked nodes.
What is the difference between assignment and comparison in programming?
Assignment uses = to assign a value, while comparison uses == to check for equality.
What is the definition of a stack?
A linear data structure that follows the Last In First Out (LIFO) principle.
True or False: A dequeue allows adding and removing elements only from one end.
False
What is a linked list?
A data structure consisting of a sequence of nodes, each containing an element and a reference to the next node.
What is the main purpose of a dictionary in programming?
To store key-value pairs where each key maps to a value.
What does ‘peek’ do in a stack?
Returns the top element of the stack without removing it.
What is the underlying data structure of a priority queue?
Heap
What is the syntax to create a list in Python?
[]
What does the ‘append()’ command do in a list?
Adds an element to the end of the list.
What is a dictionary?
A collection of key-value pairs where each key maps to a value.
What does the ‘Get’ operation do in a dictionary?
Returns the value associated with a specified key.
What is the purpose of the ‘Set’ operation in a dictionary?
Sets the value associated with a specified key.
What does the ‘Delete’ operation do in a dictionary?
Removes a key-value pair from the dictionary.
What is a hash table?
A data structure that uses hashing to store and retrieve key-value pairs efficiently.
Define hashing in the context of hash tables.
The process of converting a key into an index that can be used to access a value in the hash table.
What is chaining in hash tables?
A method for handling collisions by storing multiple key-value pairs in the same index.
What is a hash key?
The result of hashing a key to determine its index in the hash table.
What method is commonly used for hashing keys?
Modular Arithmetic.
What is an array?
A data structure that stores a fixed-size sequence of elements of the same type in contiguous memory locations.
How are elements compared in an array?
Elements are compared by their index.
What is the time complexity for inserting an element at the end of an array?
O(1).
What is the time complexity for deleting an element from the end of an array?
O(1).
How are elements accessed in an array?
Using their index.
What is the structure of arrays?
Arrays have a flat structure.
What is a linked list?
A data structure that consists of a sequence of nodes, each containing an element and a reference to the next node.
How are elements compared in a linked list?
Elements are compared by their value.
What is the time complexity for inserting an element at the beginning of a linked list?
O(1).
What is the time complexity for deleting a known node from a linked list?
O(1).
How are elements accessed in a linked list?
By traversing the list from the beginning or end.
What is a doubly linked list?
A data structure that consists of a sequence of nodes, each containing an element and references to the previous and next nodes.
What is the time complexity for inserting an element at the beginning of a doubly linked list?
O(1).
How are elements accessed in a doubly linked list?
By traversing the list from the beginning or end.
What defines a queue data structure?
A structure that follows the First-In-First-Out (FIFO) principle.
What is the time complexity for inserting an element into a queue?
O(1).
What is the time complexity for deleting an element from a queue?
O(1).
What defines a stack data structure?
A structure that follows the Last-In-First-Out (LIFO) principle.
What is the time complexity for inserting an element into a stack?
O(1).
What is the time complexity for deleting an element from a stack?
O(1).
What is a binary tree?
A hierarchical data structure consisting of nodes connected by edges, where each node has at most two children.
How are nodes compared in a binary tree?
Nodes are compared by their value.
What is the method for inserting nodes in a binary tree?
By finding the appropriate location based on their value.
What is a heap?
A specialized tree-based data structure used to maintain the maximum or minimum element in a collection.
What defines a min-heap?
A binary heap where the value of each parent node is less than or equal to its children.
What defines a max-heap?
A binary heap where the value of each parent node is greater than or equal to its children.
How are nodes represented in a binary heap?
As a list, where the root node is at index 1.
What is a graph?
A collection of nodes (vertices) connected by edges.
What is the difference between directed and undirected graphs?
Directed graphs have edges with direction, while undirected graphs have edges with no direction.
What are vertices in a graph?
The nodes in a graph.
What are the methods for inserting elements in a graph?
By adding new vertices or edges.
What is indexing in data structures?
The method used to access individual elements or nodes within a data structure.
How does the hierarchy of a data structure impact indexing?
Linear structures like arrays are often accessed by index, while hierarchical structures like trees may use traversal methods.
