Brainscape's Knowledge GenomeTM

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


See full index

A Level Computer Studies > Unit 7 - Data Structures > Flashcards

Unit 7 - Data Structures Flashcards

1
Q

Why do abstract data types make it easier to manage data?

A

We do not have to be concerned with how the data is stored or how operation work on the data we just need to know the outcome

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

How is an abstract data type an example of encapsulation?

A

It self contains all of the data and the methods associated with that data within one object

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

How is an abstract data type an example of abstraction?

A

The user is not concerned with how the methods associated with the data work they just need to know how to initialise them

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

Give an example of an abstract data type

A

Queue, tree, stack, list, graph

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

Describe the principles of operation of a queue

A

When you add an item to a queue it is added at the back, you cannot add an item at the front of a queue. When an item is deleted from a queue it is not removed from the data structure the pointer just moves on to the next one

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

Describe how a queue works

A
  1. When an item is added it is added to the back of the queue
  2. There is a front pointer and an end pointer
  3. The item being processed is the one in the same position as front pointer
  4. Once it has been processed the front pointer moves up one but the item remains in the queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the four operations performed on a queue?

A
  1. enQueue()
  2. deQueue()
  3. isEmpty()
  4. isFull()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the front pointer?

A

It indicates which item is next to be processed

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

What is the rear pointer?

A

Indicates which item was last added to the queue

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

T/F: Queues do not shuffle data

A

True

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

What is the disadvantage of linear queues?

A

They only have a finite number of blocks in the queue and once they have been filled no more can even be added because queues do not shuffle or remove data

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

How do circular queues work?

A

In a circular queue the front and rear pointers are able to double back on themselves meaning that they can loop around the queue and write over data in previous slots that has already been processed even though it cannot be deleted

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

What function enables you to determine the location of an item in a circular queue from the beginning?

A

The MOD function

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

How do priority queues work without shuffling data and still using the ‘first in first out’ principle?

A

They work by organising the elements added into priorities which are effectively sub-queues. This means that the first in first out principle does still apply but just within a priority

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

Why can you not add infinitely to any data structure?

A

Because the memory heap for that data structure will always have a finite size

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

Describe how to find the position of an item in a circular queue

A

(Position of front pointer + Number of items in the queue) + (Change in time/Time taken to deQueue an item) (%)

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

Define memory heap

A

A section of memory that is reserved for use by a data structure

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

Define array

A

A set of related data items stored under a single identifier

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

What are the 9 programming operations used on lists?

A
  1. isEmpty()
  2. append(item)
  3. remove(item)
  4. count(item)
  5. len(list)
  6. index(item)
  7. insert(pos, item)
  8. pop() < last item in the list
  9. pop(pos)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Why is a list an abstract data type?

A

We can perform operations on a list and on the data in the list without needing to know how they work .e.g. append

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

How does a memory heap contribute to the management of a list?

A

A memory heap is allocated to the list and when an item is added it is added to a location designated to the heap assigned to the list, when it is removed the empty location is returned to the heap

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

Why is a stack useful?

A

When using recursive algorithms it is used to unravel the recursion when the function is returned .e.g. depth-first searches of trees

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

Define stack

A

A data structure where the last item added is the first item removed

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

Why is a stack useful for reversing strings?

A

The order of insertion is the opposite of the order of removal

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

What are the 6 basic operations used with stacks?

A
  1. push(item)
  2. pop() < removes the top item and removes it
  3. isFull()
  4. isEmpty()
  5. peek() < returns the top item without removing it
  6. size()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How can a stack be implemented as a list?

A

Use the list commands to refer to stack commands .e.g. append refers to push

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

Define overflow in terms of a stack

A

When you try to push an item onto a stack and it is full

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

Define underflow in terms of a stack

A

When you try to pop and item from a stack and it is empty

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

Define system level data structure

A

A data structure that dictates how computational processes are carried out

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

Give an example of a system level data structure

A

A call stack or stack frame

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

What is a stack frame?

A

A stack frame consists of an individual subprogram’s local variables, arguments and return address

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

How is a call stack formed?

A

Multiple stack frames are combined

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

What does a stack frame do with regards to subprograms?

A

It dictates how parameters and return addresses are passed to subroutines

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

Define a return address

A

The address to the point in the program execution is to return to after a subprogram has been executed

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

What are the two stages of running a subprogram?

A

Subroutine call and subroutine execution

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

What happens during the subroutine call?

A

The computer saves the parameters to the stack, saves the local variables to the stack, saves the return address to the stack and then transfer execution to the subroutine code

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

What happens during the subroutine execution?

A

The computer allocates a stack space for local variables, executes the subroutine code, retrieves the return address from the stack, pops the parameters from the stack (used in the return) and transfers execution back to the return address

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

Define hash table

A

A data structure that stores key:value pairs based on an index calculated from an algorithm

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

What is the purpose of a hash function?

A

To calculate the position of a data item within an abstract data type called a hash table dependent on the value of the data item

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

What is the typical format for a hash function?

A

Address = key % No.slots

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

Why is the MOD function used in hash functions?

A

To ensure that the address location for a key does not exceed the maximum size of the hash table

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

Define collision/synonym

A

When two values end up with the same memory location within a hash table

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

What is the simplest solution when a collision or synonym occurs?

A

To put the second item in the next available slot

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

Define load factor

A

The percentages of the hash table that has values stored in it

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

What is a cluster?

A

When the majority of items in a hash table are located in one area of the table

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

How does a cluster arise in a hash table?

A

When collisions are resolved by just placing the second item in the next available slot

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

What is the solution to clustering?

A

Introducing a skip factor

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

What does a skip factor do?

A

Spreads values involved in collisions across the hash table

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

What happens when the load factor gets too high?

A

Collisions increase which decreases efficiency

42
Q

What is the best way to reduce the load factor on a table?

A

Remove the data, increase the size of the hash table and rehash the data

43
Q

Why is rehashing the data better than trying to work with a high load factor?

A

The time taken to rehash the data is less than the time lost through data collisions with a high load factor

44
Q

Describe the mid-square method

A

The item to be stored is squared and a portion of these digits are selected and the MOD function is applied to them

45
Q

Describe the folding method

A

The item to be stored is split into equal parts (the last part may be uneven if the number of digits is a prime number) and the MOD function is applied to the sum of these parts

46
Q

What are the mid-square method and folding method examples of?

A

A hash function

47
Q

How is alphanumeric data stored in a hash table?

A

Characters are converted to their binary equivalent in the ASCII tables and then treated the same as digits

48
Q

How is a dictionary different to a list?

A

Each value is assigned to a key and referenced from the main program using that key

49
Q

Why is a dictionary more efficient than a list?

A

The whole list does not need to be searched each time one item needs to be located

50
Q

What can you do if you want to store multiple items under one key?

A

Assign a key to another ADT such as a list

51
Q

What is one thing you can never do with a dictionary?

A

Store multiple values under one key

52
Q

What are the 6 main operations used when working with a dictionary?

A
  1. Adding a new pair
  2. Deleting a pair
  3. Amending a pair
  4. Returning a value associated with a key
  5. Returning True or False depending on whether the key is in the dictionary
  6. Returning the length of the dictionary
53
Q

How do dictionaries used hash functions?

A

Hash functions are used to determine the location of each key:value pair within the memory heap

54
Q

Why does a dictionary not need to be sorted?

A

Values are referenced using their key and not using any other form of search such as a binary search

55
Q

What is a graph used for?

A

A graph represents complex relationships between data points

56
Q

Define node

A

An element of a graph or tree that represents a piece of data

57
Q

Define edge

A

An element of a graph or tree that represents the relationship between two nodes

58
Q

Define edge weight

A

The cost of travelling an edge between two nodes

59
Q

Define a directed graph

A

A graph where the relationship between nodes is unidirectional

60
Q

Define an undirected graph

A

A graph where the relationship between nodes is bidirectional

61
Q

Define a weighted graph

A

A graph that has weights attached to edges

62
Q

Define an unweighted graph

A

A graph that does not have weights attached to edges

63
Q

What are two other ways of representing a graph?

A

An adjacency list or an adjacency matrix

64
Q

How is an adjacency matrix structure?

A

Each row or column represents a node
A directed graph: the y-axis is the node the relationship is going to and the x-axis is the node the relationship is going to (need to change this)
A weighted graph: the edge weight is placed in the box corresponding to the relationship
An unweighted graph: a one is placed in the box corresponding to the relationship

65
Q

T/F: an adjacency matrix for an undirected graph is symmetrical across the line y = -x

A

True

66
Q

What are the advantages of an adjacency matrix?

A
  1. Easy to work with
  2. Adding an edge is easy
67
Q

What are the disadvantages of an adjacency matrix?

A
  1. A sparse graph takes up unnecessary memory space as empty cells still have to be allocated
68
Q

How does an adjacency list work?

A

Each node is linked to a list of adjacent nodes (a dictionary is typically used to do this)

69
Q

How is a dictionary used for an adjacency list in a weighted graph?

A

Key:value pairs are nested in a sub-dictionary with the main key being the node and the sub-keys being the nodes adjacent to it with the values being the weight of the edges

70
Q

What are the advantages of an adjacency list?

A
  1. Storage efficient
  2. Effective for large and sparse graphs
  3. Useful for implementing graphs in programming languages
71
Q

What are the disadvantages of an adjacency list?

A
  1. Can be complicated to work with
  2. Not efficient for large and full graphs
72
Q

List some of the applications of graphs

A

Computer networks, chemistry, project management and web pages

73
Q

Define tree

A

A graph that is unidirectional and has no cycles

74
Q

Define rooted tree

A

A tree that has one node identified as the root and every node has a parent except for the root

75
Q

Define root

A

The node upon which all others are dependent in a rooted tree

76
Q

Define child

A

A node which has other nodes above it in the hierarchy

77
Q

Define parent

A

A node which has other nodes below it in the hierarchy

78
Q

Define subtree

A

A tree that falls below a node in the hierarchy

79
Q

Define leaf

A

A node that does not have any other beneath it in the hierarchy

80
Q

Define binary tree

A

A rooted tree in which each node has a maximum of two children and is ordered to ease the searching processes

81
Q

Define traversal

A

The process of reading data from a tree by visiting all of the nodes

82
Q

Describe pre-order traversal

A

Visiting the root, traversing the left subtree and then the right and repeating this until the whole tree has been traversed

83
Q

Describe in-order traversal

A

Traversing the left subtree, then visiting the root and the traversing the right subtree

84
Q

Describe post-order traversal

A

Traversing the left subtree, then traversing the right subtree and then visiting the root

85
Q

What is the easy way to remember the order of visiting nodes in each traversal?

A

A dot to the left of the node is pre-order, a dot under the node is in-order and a dot to the right of the node is post-order; the order in which you pass the dots moving from left to right around the tree is the order the nodes are visited

86
Q

How are items added to a binary tree?

A

If the value of the child is less than the value of the parent it is added to the left of the parent, if it is greater it is added to the right of the parent

87
Q

Why is a binary tree beneficial?

A

It is easier to search for an item in a binary tree because it is conducted in a similar way to a binary search, being able to discard half of the items with each evaluation

88
Q

Define a balanced binary tree

A

A binary tree where each node has exactly two children

89
Q

Why is a balanced binary tree ideal?

A

It is the most efficient as the height is kept to a minimum

90
Q

How is a binary tree represented as an array of records?

A

Each node is associated with three piece of information [right pointer, data, left pointer] and these sublists can be added to a larger list representing the whole tree

91
Q

Define vector

A

A mathematical quantity that has both magnitude and direction

92
Q

List three ways a vector can be represented in a program

A

A function (S → R where S = {0, 1} and R = [2.55, -3.88]), a list of real numbers ([5.77, 2.4]) or in a dictionary ({0: 9.22, 1: 3.41, 2: 5.67})

93
Q

Why can’t 4D vectors be illustrated on graphs?

A

They involve the curvature of spacetime

94
Q

How are vectors added together?

A

Pairs of corresponding numbers in each mathematical function are added together or you can graphically top and tail them

95
Q

What happens to vectors in scalar multiplication?

A

The magnitude of the scalar is increased as each value in the mathematical expression is multiplied by a constant

96
Q

Describe convex combination of vectors

A

This is the method used to derive an equation for a vector that will lie anywhere in an area enclosed by two other vectors

97
Q

What is the equation for the convex combination of vectors?

A

w = au + bv
(u and v are the original vectors and a and b are constants)

98
Q

What are the requirements for a and b in the equation for the convex combination of vectors?

A

a > 0, b > 0 and a + b = 1

99
Q

What is one real world application of the convex combination of vectors?

A

Defining the field of view for first person perspective shooter games

100
Q

What is the dot product used for?

A

It is used to calculate the angle formed by a vector

101
Q

What is the general formula for the dot product of two vectors?

A

u x v = u1v1 + u2v2 + u3v3 …

102
Q

Define dynamic data structure

A

A data structure with a variable size

103
Q

Define static data structure

A

A data structure with a fixed size

104
Q

Define abstract data type

A

A mathematical model for a data structure

105
Q

What are the advantages of a dynamic data structure?

A
  1. No wasted memory
  2. No limit on the number of items that can be added unless there are hardware limitations
  3. Resources only allocated as they are needed
106
Q

What are the disadvantages of a dynamic data structure?

A
  1. Additional memory needed for pointer
  2. Can result in a memory leak if memory that is no longer needed is returned to the heap
107
Q

What is the MOD function to identify the position of pointer for a circular queue?

A

Number of pieces of data added % the number of slots available (this means it will loop back round to the start when the size of the circular queue has been reached)

108
Q

Define cycle with respect to graphs

A

A closed path that starts and ends at the same node

109
Q

Define path with respect to graphs

A

A sequence of nodes connected by edges

110
Q

What are the common uses of a hash table?

A
  1. Creating indices for databases to enable quick storage and retrieval of data
  2. Generate memory addresses for data to be stored, particularly used in cache memory
  3. Indexing keywords and identifiers in programming to enable quick access
  4. Producing a checksum to check if transmitted data it corrupted
111
Q

What is the ideal load factor for a hash table?

A

0.75

112
Q

T/F: Keys in dictionaries can be any data type

A

False: they must be a primitive data type

A Level Computer Studies (15 decks)

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