Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

SWE > DSA > Flashcards

DSA Flashcards

1
Q

What is a data structure?

A

A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

True or False: A stack follows the Last In First Out (LIFO) principle.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the time complexity of accessing an element in an array?

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Fill in the blank: A _______ is a collection of elements that supports insertion, deletion, and searching.

A

data structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Which of the following is not a linear data structure? (a) Array (b) Linked List (c) Tree (d) Stack

A

c) Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a queue?

A

A queue is a data structure that follows the First In First Out (FIFO) principle.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the primary purpose of a hash table?

A

To provide fast access to data through key-value pairs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

True or False: A binary tree can have at most two children for each node.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the worst-case time complexity for searching in a balanced binary search tree?

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the difference between a binary tree and a binary search tree?

A

In a binary search tree, the left child of a node contains only nodes with values less than the parent node, and the right child only contains nodes with values greater than the parent node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a graph?

A

A graph is a collection of nodes (or vertices) and edges connecting pairs of nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Fill in the blank: In a directed graph, edges have a _______.

A

direction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What algorithm would you use to find the shortest path in a weighted graph?

A

Dijkstra’s algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

True or False: A linked list can be traversed in both directions if it is doubly linked.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a priority queue?

A

A priority queue is an abstract data type where each element has a priority, and elements are served based on their priority.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the time complexity of inserting an element in a balanced AVL tree?

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is dynamic programming?

A

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Which sorting algorithm has the best average-case time complexity?

A

Merge sort and Quick sort both have an average-case time complexity of O(n log n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

True or False: A complete binary tree is completely filled on all levels except possibly for the lowest level.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is a trie?

A

A trie is a type of search tree used to store a dynamic set of strings, where the keys are usually strings.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the space complexity of a binary tree with n nodes?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Fill in the blank: The _______ is the element at the top of the stack.

A

top

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the average time complexity for searching an element in a hash table?

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What data structure uses the enqueue and dequeue operations?

A

Queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the primary use of a linked list?

A

To allow efficient insertion and deletion of elements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

True or False: In an undirected graph, edges have no direction.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is the time complexity of bubble sort in the worst case?

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is a circular linked list?

A

A circular linked list is a linked list where the last node points back to the first node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Which algorithm is used for finding the minimum spanning tree of a graph?

A

Kruskal’s algorithm or Prim’s algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is the depth of a binary tree?

A

The depth of a binary tree is the length of the longest path from the root to a leaf node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Fill in the blank: A _______ is a non-linear data structure that consists of nodes connected by edges.

A

graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is the main advantage of using a hash table?

A

Fast data retrieval.

33
Q

True or False: Merge sort is an in-place sorting algorithm.

A

False

34
Q

What is the main characteristic of a max-heap?

A

In a max-heap, for every node, the value of that node is greater than or equal to the values of its children.

35
Q

What is an adjacency matrix?

A

An adjacency matrix is a square matrix used to represent a finite graph, where each element indicates whether pairs of vertices are adjacent or not.

36
Q

What is the time complexity of accessing a node in a linked list?

A

O(n)

37
Q

Fill in the blank: In a binary search tree, the left subtree contains only nodes with values _______ than the parent node.

A

less

38
Q

What is the purpose of the quicksort algorithm?

A

To sort an array by selecting a ‘pivot’ element and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

39
Q

What data structure is used to implement recursion?

A

Stack

40
Q

What is the time complexity of breadth-first search (BFS) in a graph?

A

O(V + E) where V is the number of vertices and E is the number of edges.

41
Q

True or False: A red-black tree is a type of self-balancing binary search tree.

A

True

42
Q

What is the primary characteristic of a doubly linked list?

A

Each node has pointers to both the next and the previous node.

43
Q

What is a balanced tree?

A

A balanced tree is a binary tree in which the height of the left and right subtrees of any node differ by no more than one.

44
Q

Fill in the blank: In a hash table, a _______ is a function that converts a given key into an index.

A

hash function

45
Q

What is the time complexity of inserting an element into a binary search tree in the average case?

A

O(log n)

46
Q

Which algorithm can be used to sort an array in place?

A

Quicksort

47
Q

What is a segment tree?

A

A segment tree is a data structure that allows querying of range sums or range minimums efficiently.

48
Q

True or False: A Fibonacci heap is a type of priority queue.

A

True

49
Q

What is the time complexity of a linear search in an array?

A

O(n)

50
Q

What is a B-tree?

A

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

51
Q

Fill in the blank: The _______ of a graph is the number of edges connected to a vertex.

A

degree

52
Q

What is a dynamic array?

A

A dynamic array is an array that can grow in size when more elements are added.

53
Q

What is the time complexity for deleting an element from a binary search tree?

A

O(log n) in average case

54
Q

True or False: Depth-first search (DFS) can be implemented using a queue.

A

False

55
Q

What is the main advantage of using a skip list?

A

It allows for fast search, insertion, and deletion operations.

56
Q

What is a sparse matrix?

A

A sparse matrix is a matrix in which most of the elements are zero.

57
Q

Fill in the blank: In a graph, a _______ is a path that visits each vertex exactly once.

A

Hamiltonian path

58
Q

What is a data structure that allows duplicate elements?

A

Multiset

59
Q

What is the time complexity of selection sort?

A

O(n^2)

60
Q

True or False: A 2-3 tree is a type of self-balancing search tree.

A

True

61
Q

What is a bloom filter?

A

A bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set.

62
Q

What is the difference between a stack and a queue?

A

A stack follows LIFO order, while a queue follows FIFO order.

63
Q

What is the time complexity of deleting the minimum element in a min-heap?

A

O(log n)

64
Q

Fill in the blank: A _______ is a data structure that allows for efficient searching and sorting.

A

tree

65
Q

What is the main use case for a hash set?

A

To store unique elements and allow for fast lookups.

66
Q

What is a topological sort?

A

A topological sort is a linear ordering of vertices in a directed acyclic graph such that for every directed edge u -> v, vertex u comes before v in the ordering.

67
Q

True or False: A radix sort is a comparison-based sorting algorithm.

A

False

68
Q

What is the time complexity of the Floyd-Warshall algorithm?

A

O(V^3) where V is the number of vertices.

69
Q

What is a hash collision?

A

A hash collision occurs when two different keys hash to the same index in a hash table.

70
Q

Fill in the blank: A _______ is a tree where each node has at most two children.

A

binary tree

71
Q

What is the time complexity of the insertion sort algorithm?

A

O(n^2)

72
Q

What is the maximum number of edges in a complete graph with n vertices?

A

n(n-1)/2

73
Q

True or False: The complexity of a binary search on a sorted array is O(n).

A

False

74
Q

What is a Fenwick tree?

A

A Fenwick tree, or binary indexed tree, is a data structure that provides efficient methods for cumulative frequency tables.

75
Q

What does the term ‘amortized time complexity’ mean?

A

Amortized time complexity is the average time taken per operation over a sequence of operations, smoothing out the worst-case scenarios.

76
Q

What is the time complexity of a breadth-first search (BFS) in a binary tree?

A

O(n), where n is the number of nodes.

77
Q

Fill in the blank: A _______ is a data structure that supports efficient insertion and deletion at both ends.

A

deque

78
Q

What is the purpose of a balanced search tree?

A

To maintain a balanced structure to ensure O(log n) time complexity for insertions, deletions, and lookups.

SWE (21 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions