Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science > Data Structures > Flashcards

Data Structures Flashcards

(70 cards)

Start Studying
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

Fill in the blank: A _______ is a linear data structure that allows insertion and deletion of elements from both ends.

A

deque

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

What is a queue?

A

A queue is a linear 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
5
Q

What type of data structure is a binary tree?

A

A hierarchical data structure.

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

Multiple Choice: Which of the following is NOT a type of tree data structure? A) Binary Tree B) AVL Tree C) Hash Table D) B-Tree

A

C) Hash Table

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

What is the purpose of a hash table?

A

A hash table is used to implement an associative array, mapping keys to values for efficient data retrieval.

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

True or False: In a binary search tree, the left child is always less than the parent node.

A

True

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

Fill in the blank: In a graph, a _______ is a collection of nodes and edges.

A

vertex

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

What is the difference between a directed and an undirected graph?

A

In a directed graph, edges have a direction, while in an undirected graph, edges do not have a direction.

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

Multiple Choice: What is the time complexity of searching in a balanced binary search tree? A) O(log n) B) O(n) C) O(n log n) D) O(1)

A

A) O(log n)

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

What is a vector in computer science?

A

A vector is a dynamic array that can grow in size and is used to store a sequence of elements.

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

True or False: A stack can be implemented using an array or a linked list.

A

True

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

Fill in the blank: The _______ operation in a stack removes the top element.

A

pop

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

What traversal methods are commonly used for trees? [3]

A

In-order, pre-order, and post-order traversals.

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

Multiple Choice: Which of the following is a characteristic of a hash function? A) It is reversible B) It produces a fixed-size output C) It can have collisions D) Both B and C

A

D) Both B and C

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

What is the primary use of a priority queue?

A

A priority queue is used to manage a collection of elements where each element has a priority, allowing for the retrieval of the highest (or lowest) priority element.

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

True or False: In a binary tree, each node can have at most two children.

A

True

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

Fill in the blank: The _______ of a graph is a way to visit all the vertices.

A

traversal

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

What is the difference between depth-first search (DFS) and breadth-first search (BFS)?

A

DFS explores as far down a branch as possible before backtracking, while BFS explores all neighbors at the present depth before moving on.

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

Multiple Choice: Which data structure is best for implementing a recursion? A) Stack B) Queue C) Linked List D) Array

A

A) Stack

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

True or False: A hash table can achieve average case time complexity of O(1) for search operations.

A

True

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

Fill in the blank: The _______ data structure allows for fast random access to elements.

A

array

[because their memory location is fixed]

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

What is a balanced tree? change

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What is an array?
A data type that stores a set of related data items under a single identifier [can have multiple dimensions]
26
What is a hash table?
A hash table is a data structure that implements an associative array, a structure that can map keys to values.
27
What is a collision in a hash table?
A collision occurs when two different keys hash to the same index in the hash table. [needs a mechanism to cope with collisions as they occur; you should also have atleast the number of indices as you have items to store]
28
What is two methods to handle collisions?
1.Chaining 2. Re-hashing
29
What are dictionaries in programming?
Dictionaries are collections of key-value pairs that allow for efficient data retrieval based on keys.
30
What is clustering?
When a hashing algorithm produces indices that are not randomly distributed
31
What is index?
The location where items will be stored ; calculated from the key
32
What is load factor?
The ratio of how many indices are available to how many items there are
33
What are 2 uses of using hashing algorithms?
1. Databases- used to create indices(which need to be unique) for databases enabling quick storage and retrieval of data 2. Memory addressing- Used to generate memory addresses where data will be stored.
34
What is cache memory?
A memory location where data is placed temporarily so users have faster access to programs and data stored in the cache eg when going on website and you're already logged in, or when you enable certain preferences on websites
35
What are traversals?
The process of visiting each node in a data structure, exactly once. Such traversals are classified by the order in which nodes are visited (pre-order , in-order, post-order)
36
How does re-hashing work?
If a collision occurs the same algorithm is run again or an alternative algorithm is run until a unique key is created. This normally uses a technique called probing, which means that the algorithm probes, or searches for an empty slot; one way of doing this is simply looking for the next available slot where there was a clash
37
How does chaining work?
When 2 or more keys are assigned to an index, a list is formed and key/value pairs are CHAINED together ; collision occur , then list created, key/value pairs are now elements in the list, if more collisions occur the process is repeated
38
What happens if a (static) stack needs more memory than allocated and the CPU tries to push more items into it?
A stack overflow occurs
39
How does memory work in static queues and stacks?
There's a pointer that points to the item that is about to be dealt with, once it's been dealt with the pointer moves to the next item which leaves the previous slot 'empty', but it's not actually empty because the data is still there , but we represent it as empty to show that it's been dealt with. - Therefore, there's no way to add more data in an 'empty' slot
40
What is an abstract data type (ADT)?
An ADT is a theoretical model of how data can be stored and the operations that can be carried out on the data [Therefore, the data structure is the implementation of this in a programming language]
41
What is the difference between a stack and a queue?
A stack follows Last In First Out (LIFO) order, while a queue follows First In First Out (FIFO) order.
42
What is the primary operation of a stack?
The primary operation of a stack is 'push' to add an item and 'pop' to remove the top item.
43
Fill in the blank: In a queue, the operation to add an item is called __________.
enqueue
44
True or False: Hash tables can store data in any order.
True
45
What happens when the load factor exceeds a certain threshold?
When the load factor exceeds a certain threshold, the hash table may be resized to maintain efficient operations. Add to this card
46
What does it mean for a data structure to be mutable?
A mutable data structure can be changed after it is created, such as adding or removing elements.
47
Fill in the blank: In a hash table, the __________ is used to determine the index for a key.
hash function
48
What is the purpose of resizing a vector?
Resizing a vector allows it to accommodate more elements when it reaches its capacity. (Applies to anything really)
49
True or False: You can access elements in a vector using an index.
True
50
What is the space complexity of a hash table in the worst case?
O(n) where n is the number of keys stored.
51
What are the advantages of using a hash table?
Advantages include fast access times, efficient storage, and quick lookups.
52
What is the primary disadvantage of hash tables?
The primary disadvantage is that they can suffer from collisions, which can degrade performance.
53
What are advantages to using a hash table? [2]
1. Space-efficient 2.They're more efficient than search trees or other data structures
54
What are text files?
A file that contains human-readable characters
55
What are the two main actions you want to carry out when working with text files?
1. To write data from the program into a text file 2. To read data into the program from a text file
56
What is a record?
One line of a file
57
What is a field?
An item of data in text files or binary?? ; that can be recorded for each record?
58
What is a binary file?
A type of file that stores data as sequences of 0s and 1s
59
What are the advantages of using binary files?
1. Can be used in a wide range of applications 2. Takes less memory than other image formats
60
What is a heap?
A pool of unused memory that is allocated to a dynamic data structure
61
How does a heap work?
Memory is taken from the heap when data needs to be stored and conversely, when data isn't needed/has been dealt with data is returned/added to the heap [for dynamic data structures]
62
What are the advantages of using static data structure? [2]
1. Fast access to each element of data as the memory location is fixed 2. Structures are a fixed size , making them more predictable to work with
63
What are the disadvantages of using static data structures?
1. Inefficient as memory is allocated that may not be needed 2. Cannot add any more items
64
What is the advantage of using dynamic data structures?
1. Efficient as the amount of memory varies as needed
65
What are the disadvantages of using dynamic data structures? [2]
1. Structures vary in size so there needs to be a mechanism for knowing the size of the current structure 2. Memory addresses are fragmented so slower to access
66
What are objects in graphs called?
Vertices or nodes
67
What are connections in graphs called?
Edge
68
What is the term used for a graph, that have no value?
Unweighted
69
What is the term used for a graph, that has a value?
Weighted
70

Computer Science (5 decks)

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