Brainscape's Knowledge GenomeTM

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


See full index

Computer Science 1.4 - Data Types, Data Structures, and Algorithms > 1.4.2: Data Structures > Flashcards

1.4.2: Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What are Data Structures?

A
  • A way of organising and storing data to perform operations upon effectively
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an Array?

A
  • An ordered, finite set of elements of a single type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a Linear Array?

A
  • A one-dimensional Array
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How can Two-Dimensional Arrays be visualised?

A
  • Tables or Spreadsheets
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What can a three-Dimensional Array be visualised as?

A
  • A multi-page spreadsheet
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a Record?

A
  • A row (entry) in a file, made up of fields
  • Used in databases
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a List?

A
  • A data structure consisting of a number of ordered items where the items can occur more than once
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do Lists differ from Arrays?

A
  • Lists are stored non-contiguously in memory, while Arrays store data in order
  • Lists can contain more than one data type, while Arrays store data of one type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Linked List?

A
  • A dynamic data structure used to hold an ordered set of items which are not stored in contiguous locations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How are Linked Lists set up?

A
  • Each item is a node, and contains a Data Field alongside the Link, or Pointer Field
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does the Data Field hold in a Linked List?

A
  • Contains the value of the actual data which is part of the List
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does the Pointer Field contain in a Linked List?

A
  • The address of the next item in the List
  • The index of the first item is also a pointer
  • A pointer identifying the index of the next available space is also stored
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How is a Linked List traversed?

A
  • The algorithm begins at the index given by the ‘Start’ pointer and outputs the values at each node until it finds that the pointer is empty or null - Signals the end of the linked list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is an advantage of using a Linked List?

A
  • Values can be easily added or removed by editing pointers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How can a value be added to a Linked List?

A
  1. Add the new value to the end of the linked list and update the ‘NextFree’ Pointer
  2. The pointer field of the value before where the value is to be inserted is updated to point to the inserted value
  3. The pointer field of the value just inserted is updated to point to the next value
  4. When traversed, the Linked List should contain the newly inserted value
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How can a value be removed?

A
  1. The pointer field of the node before the the node being removed should be updated to point to the node after
  2. When traversed, the Linked List will omit the node that no longer has pointer fields leading to it
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the disadvantage of Linked Lists?

A
  • A node is not truly removed from the List, it is only ignored, which wastes memory
  • Linked Lists can only be traversed in order; an item cannot be directly accessed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What does isEmpty() do to a List?

A
  • Checks if the List is empty
  • Example: listName.isEmpty()&raquo_space; False
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What does append(value) do to a List?

A
  • Adds a new value to the end of the List
  • Example: listName.append(15)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What does remove(value) do to a List?

A
  • Removes the value the first time it appears in the List
  • Example: listName.remove(23)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What does search(value) do to a List?

A
  • Searches for a value in the List
  • Example: listName.search(38)&raquo_space; False
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What does length() do to a List?

A
  • Returns the length of the List
  • Example: listName.length()&raquo_space; 7
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What does index(value) do to a List?

A
  • Returns the position of the item
  • Example: listName.index(23)&raquo_space; 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What does insert(position, value) do to a List?

A
  • Inserts a value at a given position
  • Example: listName.insert(4, 25)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What does pop() do to a List?

A
  • Returns and removes the last value in the List
  • Example: listName.pop()&raquo_space; 12
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What does pop(position) do to a List?

A
  • Returns and removes the value in the List at the given position
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is a Tuple?

A
  • An immutable (unchangeable), ordered set of values of any type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

How are Tuples initialised?

A
  • Using regular brackets ( ) instead of square brackets
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a Graph?

A
  • A set of vertices/nodes connected by edges/arcs
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is a Directed Graph?

A
  • The edges can only be traversed in one direction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What is an Undirected Graph?

A
  • The edges can be traversed in both directions
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is a Weighted Graph?

A
  • A cost is attached to each edge
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

How do Graphs differ from Linked Lists and Binary Trees?

A
  • Each vertex is able to have more than two edges and point to any vertex in the data structure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What are the advantages of an Adjacency Matrix?

A
  • Convenient to work with due to quicker access time
  • Easy to add nodes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is the advantage of an Adjacency List?

A
  • More space efficient for large, sparse networks
36
Q

What is Breadth-First?

A
  • Node-based method of finding the shortest path through a Graph
  • Makes use of a Queue and FIFO
  • One Node at a time is selected, visited, and marked: Adjacent Nodes are visited and stored in a Queue
37
Q

What is the process of a Breadth-First traversal?

A
  1. Set the Root Vertex as the current vertex
  2. Add the current Vertex to the list of visited Vertices if not already on the list
  3. For every Edge connected to the Vertex
    a) If the linked Vertex is not in the visited List:
    i. Enqueue the listed Vertex
    ii. Add the linked Vertex to the visited List
  4. Dequeue and set the Vertex removed as the current Vertex
  5. Repeat step 2 until the Queue is empty
  6. Output all the visited Vertices
38
Q

What is Depth-First?

A
  • Edge-based technique that makes use of a Stack and LIFO
39
Q

What are the two main stages of a Depth-First search?

A
  • Visited Nodes are pushed onto the Stack
  • When there are no Nodes left to visit, the Nodes are popped off the Stack
40
Q

What is the process of a Depth-First traversal?

A
  1. Set the Root Node as the current Node
  2. Add the current Node to the list of visited Nodes, if it isn’t already on the list
  3. For every Edge connected to the Node:
    a) If the connected Node is not in the visited List, push the linked Node onto the Stack
  4. Pop the Stack and set the removed item as the current Node
  5. Repeat from step 2 until there are no Nodes left to visit
  6. Output all the visited Nodes
41
Q

What are the main points of a Breadth-First traversal?

A
  • Uses a Queue to find the shortest path through an Unweighted Graph
  • Reaches a Node with the minimum number of Edges from the source Node
  • More suitable for searching Nodes that are closer to the source Node
  • Considers all neighbours first, so isn’t suitable for decision-making Trees used in games or puzzles
42
Q

What are the main points of a Depth-First traversal?

A
  • Uses a Stack
  • May traverse through more Edges to reach a destination Node from the source
  • More suitable when there are solutions further away from a source
  • More suitable for game or puzzle problems: A decision is made, all paths of the decision are explored, and if the decision leads to a win situation, it is stopped
43
Q

What is a Stack?

A
  • A Last In First Out (LIFO) Data Structure
44
Q

What is the key feature of a Stack?

A
  • Items can only be added or removed from the top of the stack
45
Q

What are Stacks used for?

A
  • Reversing actions, such as going back a page in web browsers, and undo buttons
46
Q

How can Stacks be implemented?

A
  • As either a static structure or a dynamic structure
  • Using a pointer that points to the top of the stack, where the next piece of data will be inserted
47
Q

When are static Stacks preferred?

A
  • When the maximum size required is known in advance, as they are easier to implement and make more efficient use of memory
48
Q

What does isEmpty() do to a Stack?

A
  • Checks if the Stack is empty
  • works by checking the value of the top pointer
  • Example: stackName.isEmpty()&raquo_space; True
49
Q

What does push(value) do to a Stack?

A
  • Adds a new value to the end of the Stack
  • Needs to check that the Stack is not full before pushing to the Stack
  • Example: stackName.push(“Jay”)
50
Q

What does peek() do to a Stack?

A
  • Returns the top value from the Stack
  • First checks the Stack is not empty by looking at the value of the top pointer
  • Example: stackName.peek()&raquo_space; “Jay”
51
Q

What does pop() do to a Stack?

A
  • Removes and returns the top value of the Stack
  • First checks the Stack is not empty by looking at the value of the top pointer
  • Example: stackName.pop()&raquo_space; “Jay”
52
Q

What does size() do to a Stack?

A
  • Returns the size of the Stack
  • Example: stackName.size()&raquo_space; 2
53
Q

What does isFull() do to a Stack?

A
  • Checks if the Stack is full
  • works by comparing stack size to the top pointer
  • Example: stackName.isFull()&raquo_space; False
54
Q

What is Underflow?

A
  • If the Stack Pointer is at -1
  • An attempt to pop() will result in an Underflow Error
55
Q

What is Overflow?

A
  • An attempt to push() another item onto the Stack when the Stack has reached maximum size
56
Q

What is a Queue?

A
  • A First In First Out (FIFO) Data Structure
57
Q

What is the key feature of a Queue?

A
  • Items are added to the end of the Queue and are removed from the front of the Queue
58
Q

Where are Queues commonly used?

A
  • In printers, keyboards, and simulators
59
Q

What is a Linear Queue?

A
  • A Data Structure consisting of an Array
  • Items are added to the next available space in the Queue, starting from the front
  • Items are removed from the front of the Queue
60
Q

How do Queues make use of Pointers?

A
  • Two pointers: One pointing to the front of the Queue, and one pointing to the back where the next item can be added
61
Q

What is the disadvantage of a Linear Queue?

A
  • As the Queue removes items, there are addresses in the Array which cannot be used again, making a Linear Queue an ineffective implementation of a Queue
62
Q

What is a Circular Queue?

A
  • A Queue where once the rear pointer is equal to the maximum size of the queue, it can loop back to the front of the Array to store values, provided it is empty
  • Use space in an Array more effectively, but can be harder to implement
63
Q

What does enQueue(value) do to a Queue?

A
  • Adds a new item to the end of the Queue
  • Increments the back pointer
  • Example: queueName.enQueue(“Jay”)
64
Q

What does deQueue() do to a Queue?

A
  • Removes the item from the front of the Queue
  • Increments the front pointer
  • Example: queueName.deQueue()
65
Q

What does isEmpty () do to a Queue?

A
  • Checks if the Queue is empty by comparing the front and back pointer
  • Example: queueName.isEmpty()&raquo_space; False
66
Q

What does isFull() do to a Queue?

A
  • Checks if the Queue is full by comparing the back pointer and Queue size
  • Example: queueName.isFull()&raquo_space; False
67
Q

What is a Tree?

A
  • A connected form of a Graph
68
Q

How are Trees laid out?

A
  • Contain a Root Node, the top of the Tree, connected to other Nodes using branches, with the lower-level nodes being the children of the higher-level Nodes
69
Q

What is a Node?

A
  • An item in a Tree
70
Q

What is an Edge?

A
  • Connector of two Nodes
  • Also known an a Branch, or Arc
71
Q

What is a Root?

A
  • A single Node which does not have any incoming Nodes
72
Q

What is a Child?

A
  • A Node with incoming Edges
73
Q

What is a Parent?

A
  • A Node with outgoing Edges
74
Q

What is a Subtree?

A
  • A subsection of a Tree consisting of a Parent and all the Children of the Parent
75
Q

What is a Leaf?

A
  • A Node with no Children
76
Q

What is a Binary Tree?

A
  • A type of Tree in which each Node has a maximum of two Children
77
Q

What are Binary Trees used for?

A
  • To represent information for Binary Searches, as information in these Trees is easy to search through
78
Q

What is the most common way of representing a Binary Tree?

A
  • Storing each Node with a left Pointer and a right Pointer in a two-dimensional Array
79
Q

What is a Hash Table?

A
  • An Arrays that is coupled with a Hash Function that takes in data (a key) and releases an output (the Hash)
80
Q

What is the role of the Hash Function?

A
  • To map the key to an index in the Hash Table
81
Q

What is a Collision in a Hash Table?

A
  • When two inputs result in the same Hash value
82
Q

What is the feature of a good Hashing Algorithm?

A
  • Low probability of Collisions
83
Q

What is Collision Resolution?

A
  • Placing an item that has had a Collision into the next available location
84
Q

What are Hash Tables used for?

A
  • Indexing as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored
85
Q
A

Computer Science 1.4 - Data Types, Data Structures, and Algorithms (3 decks)

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