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
  1. 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
  1. 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)

30
Q

What are the different types of queues?

A
  • Linear
  • Circular
  • Priority
31
Q

How do you test if a linear queue is empty?

A

Check if the front pointer is greater than rear pointer

32
Q

How do you test of a linear queue is full?

A

Check if the rear pointer points to the last element

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 of rear pointer
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
35
Q

How do you peek a linear queue?

A
  1. Check if empty
  2. Return value at front pointer
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 that rear pointer points to
  4. Increment queue size
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
38
Q

Linear queue summary:

A
  • FIFO structure organised as a linear sequence
  • results in unused capacity at the front when dequeued
  • Useful if the queue represents a finite resource e.g. tickets
39
Q

Circular queue summary:

A
  • FIFO structure organised as a ring
  • front and rear pointers can wrap around from end to start
  • More complex to implement and maintain but can utilise space capacity at from of queue
40
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
41
Q

What is a priority queue?

A

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

42
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
43
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
44
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
45
Q

What is a recursive subroutine?

A

A subroutine this is defined in terms of itself.

46
Q

What is the base case?

A

Condition that evaluates to a known value to stop recursion.

47
Q

What is a call stack?

A

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

48
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
49
Q

What information does a stack frame contain?

A
  • local variables
  • parameter values
  • return addresses
50
Q

What are graphs?

A

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

51
Q

What is a node?

A

Part of a graph that represents objects or entities

52
Q

What is an edge?

A

Part of a graph that represents a relationship between entities

53
Q

What is a weight in a graph?

A

A data value used to label an edge.

54
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
55
Q

What is an undirected graph?

A

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

56
Q

What is a directed graph?

A

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

57
Q

What is a weighted graph?

A

A graph in which each edge is given a weight.

58
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
59
Q

What are the two main ways of implementing a graph?

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

How can an adjacency matrix be represented?

A

Static 2D array

61
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

62
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
63
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
64
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
65
Q

When are adjacency lists used?

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

What are the advantages of adjacency lists?

A
  • Memory efficient as they only store edges that exist in the graph
67
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
68
Q

What is graph traversal?

A

Visiting every node within the graph to achieve an purpose

69
Q

What are the two different types of graph traversal?

A
  • Depth First
  • Breadth First
70
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
71
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.

72
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 schools occur

Comsci (4 decks)

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