Brainscape's Knowledge GenomeTM

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


See full index

Comsci > Data Structures > Flashcards

Data Structures Flashcards

1
Q

What is a primitive data type?

A

A data type that can’t be broken down further.

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

What is an abstract data type?

A

A conceptual model of how data is to be organised and the operations we might perform on the data.

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

What is a data structure?

A

Implementation of ADTs. Can combine multiple data under a single identifier.

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

What are the key ADTs?

A
  • Stacks
  • Queues
  • Graphs
  • Trees
  • Hash Tables
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are arrays?

A

Static data structures that stored data of the same type arranged as a contiguous block in memory with a fixed length

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

How does indexing work in arrays?

A

The index acts as an offset to the data from the start off the structure in memory. For this reason the dimensions and data type of the array must be known.

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

What is a multidimensional array?

A

An n-dimensional array is a set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements.

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

What are the uses of arrays?

A
  • Can store multiple homogenous values
  • Can represent vectors
  • Can store tabular data in a matrix
  • 2D arrays are common in machine learning applications that consist of large related data sets
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the advantages of static data structures?

A
  • Do not require pointers so take up less space
  • Can randomly access any element in constant time because data is stored continuously in memory
  • Faster than dynamic data structures
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the disadvantages of static data structures?

A
  • Cannot grow to accommodate more data being declared
  • Cannot shrink to free up memory
  • Inefficient if more space is allocated than required
  • Can lead to errors if not enough space is allocated
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

On what kind of basis is date retrieved from a stack?

A

Last-In-First-Out

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

On what kind of basis is data retrieved from a queue?

A

First-In-First-Out

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

What are the key operations of a stack?

A
  • Push
  • Pop
  • Peek
  • Test for empty stack
  • Test for full stack
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the key operations of a queue?

A
  • Add and item
  • Remove an item
  • Test for an empty queue
  • Test for a full queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a stack overflow?

A

An attempt is made to push more data onto the stack that it can store

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

What is a stack underflow?

A

Occurs when a pop is attempted on an empty stack.

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

What are stacks comprised of?

A
  • A sequence of items
  • A stack pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are queues comprised of?

A
  • Sequence of items
  • Rear pointer
  • Front pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the uses of stacks?

A
  • Reversing sequences of items
  • Maintaining “undo” lists in applications
  • Maintaining a web-browser history
  • Storing processor state (register values) when handling an interrupt
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are the uses of queues?

A
  • Maintaining a queue of print jobs
  • Managing an input buffer
  • Handling multiple file downloads
  • Maintaining a playlist of media
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Test if a stack is empty?

A

Check if the stack pointer is equal to -1

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

Test if a stack is full?

A

Compare the stack pointer to the maximum size of the array (-1)

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

Push an item onto a stack?

A
  1. Check if the state is full if not…
  2. Increment the stack pointer by 1
  3. Assign the pushed item to the element within item indexed by the stack pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Peeking a stack?

A
  1. Check if the stack is empty, if not…
  2. Return the item at the stack pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Popping a stack?

A
  1. Check if the stack is empty, if not…
  2. Decrement the stack pointer
  3. Return the item at the stack pointer + 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is a linear queue?

A

A simple static and array based implementation of a queue

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

What are the advantages and disadvantages of linear queues?

A

+Simple to program
-Can lead to wasted capacity as memory is never used up
-Process of shuffling data to solve this issue is inefficient

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

What is a circular queue?

A

A static array based implementation of a queue with “wrapping” front and rear pointers

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

What are the advantages and disadvantages of a circular queue?

A

+It avoids wasted space with no need of shuffling
- more complex to implement
(-Can still run out of storage space)

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

What are the different types of queues?

A
  • Linear
  • Circular
  • Priority
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

How do you test if a linear queue is empty?

A

Check if the front pointer is greater than rear pointer

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

How do you test of a linear queue is full?

A

Check if the rear pointer points to the last element

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

How do you enqueue items in a linear queue?

A
  1. Check if full
  2. Increment rear pointer
  3. Assign item to index indicated by rear pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

How do you dequeue items in a linear queue?

A
  1. Check if empty
  2. Return value at the front pointer
  3. Increment front pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

How do you peek a linear queue?

A
  1. Check if empty
  2. Return value at front pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

How do you enqueue items in a circular queue?

A
  1. Check if queue is full
  2. Increment rear pointer and modulus it with the maximum size of the array
  3. Add items at index indicated by rear pointer
  4. Increment queue size
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

How do you dequeue items from a circular queue?

A
  1. Check if empty
  2. Store removed item
  3. Increment front pointer and modulus with maximum size of the array
  4. Decrement the queue size and return item
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What area the differences between a circular and linear queue? (Structure only)

A
  • Circular more efficient but also more complex
  • Can wrap around memory locations
  • No space is wasted after dequeueing
  • Linear queues shuffle but this is inefficient
  • Circular queues don’t need to do this
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What is a priority queue?

A

A type of queue where each item in the queue has a priority.

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

How do priority queues work?

A
  • Items are stored within the queue based on priority with highest priority at the front.
  • When enqueueing we search for an item that has less priority and insert the item in front of it by shuffling everything after it
  • This preserves FIFO within priority levels
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

What are the advantages of a dynamic data structure?

A
  • Can change size at run-time by dynamically allocating memory
  • More flexible, with no wasted space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

What are the disadvantages of a dynamic data structure?

A
  • Do not store items in continuous memory locations so retrieving items takes longer
  • Require memory to store pointers to next items so take up more space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

What is a recursive subroutine?

A

A subroutine this is defined in terms of itself.

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

What is the base case?

A

Condition that evaluates to a known value to stop recursion.

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

What is a call stack?

A

An area of memory used to store data used by running processes and subroutines.

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

How does the call stack work?

A
  1. Each new subroutine call pushes a stack frame onto the call stack
  2. When a process completes, its stack frame is popped off the call stack
  3. The previous process continues
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

What information does a stack frame contain?

A
  • local variables
  • parameter values
  • return addresses
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

What are graphs?

A

An ADT comprised of a network of nodes connected by edges used to model complex relationships.

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

What is a node?

A

Part of a graph that represents objects or entities

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

What is an edge?

A

Part of a graph that represents a relationship between entities

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

What is a weight in a graph?

A

A data value used to label an edge.

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

What are the uses of graphs

A
  • Human (social) networks
  • Transport networks , including road and rail networks
  • Connections between devices on a network
  • Planning telecommunications networks
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

What is an undirected graph?

A

A graph in which each relationship between nodes is two-way.

54
Q

What is a directed graph?

A

A graph where each relationship between nodes can be one-way as shown by arrows or bidirectional.

55
Q

What is a weighted graph?

A

A graph in which each edge is given a weight.

56
Q

What are some possible graph operations?

A
  • Adding/Removing a node
  • Adding/Removing an edge
  • Test if an edge exists between two nodes
  • Getting and updating weights on edges
  • Finding a valid path between two nodes
57
Q

What are the two main ways of implementing a graph?

A
  • Adjacency matrix - size of N squared
  • Adjacency list - size of N + E
58
Q

How can an adjacency matrix be represented?

A

Static 2D array

59
Q

How can an adjacency list be represented?

A

Dynamically as an array of graph nodes, each containing a pointer to a list of nodes

60
Q

What are the advantages of adjacency matrices?

A
  • Edges between nodes can be quickly identified using the coordinates of the nodes in the 2D array
61
Q

What are the disadvantages of adjacency matrices?

A
  • Almost half of the matrix is repeated data
  • Stores every possible edge between nodes, even those that don’t exist
  • Wasted data
62
Q

When are adjacency matrices used?

A
  • “Dense graphs” where there are a lot of edges
  • When edges need to be frequently created,removed,identified or their weights changed
63
Q

When are adjacency lists used?

A
  • “Sparse graphs” where there are not many edges
  • Nodes are frequently added/removed
64
Q

What are the advantages of adjacency lists?

A
  • Memory efficient as they only store edges that exist in the graph
65
Q

What are the disadvantages of adjacency lists?

A
  • They are slow to identify edges as each item in a list must be be searched linearly until the desired edge is found
66
Q

What is graph traversal?

A

Visiting every node within the graph to achieve an purpose

67
Q

What are the two different types of graph traversal?

A
  • Depth First
  • Breadth First
68
Q

How does Depth First traversal work?

A
  • Recursively visits nodes that are adjacent to a starting node
  • Until a node is reached with no unvisited adjacent nodes
  • At this point the algorithm backtracks
69
Q

How is a stack used in depth first traversal?

A

Uses it to keep track of the currently visiting node and the history of nodes required to get there.

70
Q

What are the uses of a depth first traversal algorithm.

A
  • Finding a solution to a maze, where the maze is modelled as a graph
  • Finding the valid path from one node to another
  • Determining the order with which processes that depend on one another should occur
71
Q

How does breadth first traversal work?

A

Adds all adjacent nodes to a queue and uses iteration to repeat the process with the node at the front of the queue.

72
Q

What are some uses of breadth first searches?

A
  • Identifying “friends” and first-degree contacts
  • Finding immediately connected devices on a network
  • Crawling web pages to build an index of linked pages as used by search engines
  • Mapping an unknown graph
73
Q

What is a tree data structure?

A

A specialised form of undirected graph with exactly one path between two nodes used to model hierarchical relationships.

74
Q

What are the features of a tree?

A
  • Undirected
  • Unweighted
  • Fully connected
  • Acyclical
75
Q

What is a binary tree?

A

A type of rooted tree where each node can have at most two children.

76
Q

What are the uses of trees?

A
  • Efficient searching and sorting algorithms
  • Storing data that has a hierarchical structure
  • Processing syntax in natural and programming languages
  • Implementing probability and decision trees
77
Q

Why are trees well suited for recursion?

A

They are a recursive data type such that each child node can be the root of a separate tree.

78
Q

What is a rooted tree?

A
  • One node is designated as the root which has no parents
  • All nodes described as parent or child nodes
  • Direction of hierarchy often shown by arrows
79
Q

What are the features on a rooted tree?

A
  • Root node: has no parent
  • Child and Parent nodes
  • Edges/Branches
  • Leaf node: has no children
80
Q

What is a binary search tree?

A

A type of binary tree where a particular method is used to insert new node in an optimal location for later search/retreival

81
Q

What are Binary Search Trees used for?

A

Provide an efficient way of searching for items as well as providing an effective way of returning all items in the correct order.

82
Q

What are the key operations of a tree?

A
  • Add nodes
  • Get child nodes
  • Getting a subtree
  • Searching for a node
  • Determining the height of the tree
83
Q

What is the height of a tree?

A

The number of edges along the longest path from the root to the furthest leaf node.

84
Q

What are the uses of a pre-order traversal?

A
  • Copying a tree
  • Evaluating mathematical expressions using prefix notation
85
Q

What are the uses of an in-order traversal?

A
  • Outputting the contents of a binary tree in ascending order
86
Q

What are the uses of a post-order traversal?

A
  • Converting mathematical expressions from infix to postfix notation (Reverse Polish)
  • Producing a postfix expression from an expression tree
  • Deleting a tree
  • Completing dependant processes in order
87
Q

What is an expression tree?

A

A tree that represents a mathematical expressions evaluated using post-order traversals.

88
Q

What it Reverse Polish Notation?

A

An alternate means of writing mathematical expressions using postfix notation

89
Q

What is infix notation?

A

The operator sits between the operands

90
Q

What is postfix notation?

A

Operator comes after operands

91
Q

What are the benefits of Reverse Polish Notation?

A
  • Simplifies mathematical expressions by eliminating the need for brackets as order is implied by notation
  • More easily evaluated by stack-based interpreters
92
Q

What are some properties of stack-based interpreters?

A
  • Translate and execute program code line-by-line
  • Invoke pre-complied subroutines to perform the line being translated
93
Q

What is a hash table?

A

A data structure that stores a key/value pair based on an index calculated from a hashing algorithm

94
Q

What is a collision in hash tables?

A

When two key values compute to the same hash value

95
Q

What are properties of good hash functions?

A
  • Make use of all info provided by the key
  • Uniformly distribute output across table
  • Maps similar keys to very different hash values
  • Make use of only the fastest operations
96
Q

How can collisions be dealt with?

A
  • Rehashing
  • Linear probing
  • Chaining
97
Q

What is linear probing and what are its disadvantages?

A
  • Look for the next available index and insert item there
  • However increases potential for further collisions and can promote clustering
98
Q

What is clustering in hash tables?

A

Nearby indexes are not randomly or evenly distributed

99
Q

What is chaining?

A

Replacing the existing contents of the index with a list and add the new items to the list

100
Q

What is rehashing?

A

Process of increasing the size of a hash table and redistributing the elements to new indexes based on their new hash values

101
Q

What are the uses of hash tables?

A
  • Databases: quick storage and retrieval of data based on primary keys
  • Cache memory: determining the memory address for a given item of data
  • Operating Systems: store locations of its programs and utilities for quick access
    (Encryption)
102
Q

How do hash tables work?

A
  • When an item is added, its key is processed by a hashing algorithm that returns a hash value
  • Items are placed in indexes specified by the hash value
  • To search for an item, key is processed again and the resulting index is checked for the item, if it does not exist we can confidently say it is not in the table
103
Q

What are the advantages of using hash tables to store data?

A
  • Faster to lookup a record
  • Time complexity of O(1) for retrieval
104
Q

What are the advantages of storing data in a dictionary?

A
  • More compact file as there are no empty records
  • Produce a sorted list
  • Do not have to design a hash algorithm so easier to design
  • No need to deal with collisions
105
Q

What is a vector?

A

A data structure that represents a size and a magnitude, made up of at least 2 components.

106
Q

How can vectors be represented?

A
  • List of numbers
  • Functions
  • Geometric point in space pointed to by an arrow
107
Q

How can a vector with n components from the set of reals be written?

A

Rn

108
Q

How can a vector be represented using a dictionary?

A
  • Key: The value in the domain
  • Value: The image in the codomain
109
Q

How can we express a vector as a function?

A

f:S —> R where S is the set of values that the function can be applied to (domain) and R is the potential outputs of the function (co-domain)

110
Q

What is the dot product of 2 vectors?

A

The single value result when applying one vector’s magnitude and direction to another

111
Q

How do you calculate the dot product?
U = [u1, u2, … , un]
V = [v1, v2, … , vn]

A

U x V = u1v1 + u2v2 + … unvn

112
Q

What are the uses of the dot product?

A

Can be used to find the angle between them using the formula:
ab = |a||b|cosx

113
Q

What is a convex combination of two vectors?

A

A vector that lies on the line between two vectors

114
Q

When is D a convex combination where:
D = aA + bB
Where A, B are vectors and a,b are scalars

A

If a and b are both greater than or equal to 0 and a + b = 1

115
Q

What is a linear search algorithm?

A

An algorithm that looks through each item in a set until the search key is found or every item has been inspected.

116
Q

What are the advantages and disadvantages of linear search?

A

+ Only option for unsorted lists
- Inefficient: O(n)

117
Q

What does the efficiency of a linear search depend on?

A
  • Size of the dataset
  • The location of the item to search for
118
Q

What is a binary search algorithm?

A

An algorithm that looks at the middle item, if it is less look at the middle item in the lower half, if it is more look at the middle item in the upper half. This is repeated until it is found or low pointer is above the high pointer

119
Q

What are the advantages and disadvantages of binary search?

A

+ Very efficient for large databases - O(log n)
- Can be more difficult to implement
- Must be a sorted list

120
Q

How do you search in a binary search tree?

A

Using an in-order traversal

121
Q

How does bubble sort work?

A

Each item in a list is compared to the one after it. If the item after is smaller that the current one then they swap until no swaps are made and it is sorted.

122
Q

What are the disadvantages of bubble sort?

A
  • Inefficient time wise as time complexity of O(n2)
  • Algorithm continues to iterate over the list even if no further swaps are required
123
Q

How can bubble sort be improved?

A
  • Reducing the number of comparisons after each pass
  • A sorted flag that can stop the sort if no swaps are made
124
Q

How does merge sort work?

A
  • Example of a divide and conquer algorithm where the program is broken down into smaller units
  • List is continuously divided until there is only one item in each
  • Sublists are combined in order until the list os fully sorted
125
Q

What are the disadvantages of merge sort?

A

If done recursively is not very memory efficient

126
Q

What are the advantages of merge sort?

A

Time efficient with an efficiency of O(nlogn)

127
Q

What is an optimisation algorithm?

A

An algorithm that finds the best possible solution to the problem proposed.

128
Q

What is an example of an optimisation algorithm?

A

Dijkstra’s Shortest Path (DSP)

129
Q

What does DSP do?

A

Calculates the shortest distance between a starting node to all other nodes in the graph

130
Q

What is the efficiency of DSP?

A

O(n2)

131
Q

What are the uses of DSP?

A
  • Shortest path between two locations in a transport network
  • Telephone and computer network planning
  • Network routing / packet switching

Comsci (5 decks)

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