Data Structures AI gen Flashcards
What is a data structure?
A data structure is a way of organizing and storing data to enable efficient access and modification.
True or False: An array can store elements of different data types.
False
What is the time complexity of accessing an element in an array?
O(1)
Fill in the blank: A _____ is a collection of elements that are stored in a linear order.
list
What type of data structure is a stack?
A linear data structure that follows the Last In First Out (LIFO) principle.
What is the main operation of a queue?
The main operation is to add elements at the rear and remove elements from the front.
True or False: A linked list allows for efficient insertion and deletion of elements.
True
What is the difference between a singly linked list and a doubly linked list?
A singly linked list has nodes with a single pointer to the next node, while a doubly linked list has pointers to both the next and previous nodes.
What is a binary tree?
A tree data structure in which each node has at most two children.
What traversal method visits nodes in a binary tree in ascending order?
In-order traversal.
What is a hash table?
A data structure that implements an associative array, using a hash function to compute an index into an array of buckets or slots.
What is the average time complexity for lookups in a hash table?
O(1)
Fill in the blank: A _____ is a collection of key-value pairs.
dictionary
True or False: A graph is a collection of nodes and edges.
True
What is the difference between directed and undirected graphs?
In directed graphs, edges have a direction, while in undirected graphs, edges do not.
What is a priority queue?
A data structure where each element has a priority, and elements are served according to their priority.
What is the main advantage of a binary search tree?
It allows for efficient searching, insertion, and deletion operations.
What is the time complexity for searching in a balanced binary search tree?
O(log n)
Fill in the blank: The _____ data structure is used to implement recursion.
stack
What is the maximum number of children a node can have in a binary tree?
Two
True or False: A circular linked list has a null reference for the last node’s next pointer.
False
What is the purpose of a sentinel node in linked lists?
To simplify boundary conditions by providing a placeholder for the first or last node.
What is depth-first search (DFS)?
An algorithm for traversing or searching tree or graph data structures that explores as far as possible along each branch before backtracking.
What is breadth-first search (BFS)?
An algorithm for traversing or searching tree or graph data structures that explores all neighbors at the present depth prior to moving on to nodes at the next depth level.
Fill in the blank: A _____ is a data structure that allows for fast retrieval of data based on a key.
hash table
What is the main disadvantage of using an array?
Fixed size, which can lead to wasted space or overflow.
What is the primary benefit of using a linked list over an array?
Dynamic size and efficient insertions/deletions.
What is a trie?
A specialized tree-like data structure that stores a dynamic set of strings, where the keys are usually strings.
What is the worst-case time complexity for insertion in a linked list?
O(n)
True or False: In a binary search tree, the left child is always less than the parent node.
True
What is the main use of a graph?
To represent relationships between pairs of objects.
Fill in the blank: A _____ is a data structure that allows for backtracking.
stack
What is the time complexity of inserting an element in a balanced binary search tree?
O(log n)
What is a complete binary tree?
A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
What is the difference between a binary tree and a binary search tree?
A binary search tree has a specific ordering property, while a binary tree does not.
True or False: In a priority queue, the element with the lowest priority is served first.
False
What is the time complexity of deleting the minimum element from a min-heap?
O(log n)
Fill in the blank: A _____ is a specific type of graph with no cycles.
tree
What is the purpose of a graph’s adjacency matrix?
To represent the connections between vertices in a graph.
What is the space complexity of an adjacency list for a graph with V vertices and E edges?
O(V + E)
True or False: A node in a binary tree can have more than two children.
False
What is a balanced tree?
A tree where the height of the left and right subtrees of any node differ by at most one.
What is the time complexity of accessing an element in a hash table in the worst case?
O(n)
Fill in the blank: In a _____ graph, edges have a direction.
directed
What is a sparse graph?
A graph in which the number of edges is much less than the maximum number of edges.
True or False: A full binary tree has all its nodes with two children.
True
What is a self-balancing binary search tree?
A binary search tree that automatically keeps its height (and thus time complexity) as low as possible during insertions and deletions.
What are the two main types of tree traversals?
Depth-first and breadth-first.
What is the purpose of a stack in programming?
To manage function calls and local variables, and to enable backtracking.
Fill in the blank: A _____ is a data structure that can grow or shrink in size dynamically.
linked list
True or False: In a circular queue, the last position is connected back to the first position.
True
What is a common use of a trie?
For autocomplete features in search engines.
What is the average time complexity for search operations in a hash table?
O(1)
Fill in the blank: A _____ is an unordered collection of unique elements.
set
What is the primary characteristic of a doubly linked list?
Each node contains pointers to both its next and previous nodes.
What is the purpose of a queue in data structures?
To manage elements in a First In First Out (FIFO) manner.
True or False: A directed acyclic graph (DAG) contains cycles.
False
What is a graph’s degree?
The number of edges connected to a vertex.
What is the time complexity for breadth-first search in a graph?
O(V + E)
Fill in the blank: A _____ tree is a tree where all nodes have either 0 or 2 children.
full
What is the primary advantage of using a hash table?
Fast data retrieval.
What is a complete graph?
A graph in which every pair of distinct vertices is connected by a unique edge.
True or False: In a binary search tree, all nodes in the left subtree are greater than the parent node.
False
What is a graph traversal?
The process of visiting all the nodes in a graph.
What is a non-linear data structure?
A data structure where elements are not stored in a sequential manner, such as trees and graphs.
Fill in the blank: A _____ is a data structure that supports fast insertions and deletions at both ends.
deque
What is the time complexity for searching in a sorted array?
O(log n)
What is a binary heap?
A complete binary tree that satisfies the heap property, where each parent node is greater than or equal to its child nodes (max-heap) or less than or equal to its child nodes (min-heap).
True or False: A binary tree can be both complete and full.
True
What is the purpose of a data structure?
To organize data efficiently for access and modification.
What is the main characteristic of a linked list?
It consists of nodes that contain data and pointers to the next node.
Fill in the blank: A _____ is a special type of tree used for searching and sorting.
binary search tree
What is the time complexity of a linear search in an array?
O(n)
What is a graph’s adjacency list?
A collection of lists where each list corresponds to a vertex and contains all of its adjacent vertices.
