Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

A-Level Computer Science (A1+A2) > Data Structures > Flashcards

Data Structures Flashcards

1
Q

What data type is an integer and why?

A

Primitive - as it can only contain 1 value

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

What are some examples of primitive data types?

A

Integers

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

What is a compound/composite data type? What is an example?

A

More than 1 primitive data types combined together for example, a record or a class

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

Define data structure

A

Collection of data that is organised to allow efficient processing

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

Define abstract data type

A

A conceptual model that describes how data is organised and which operations can be carried out on the data (i.e. delete, insert) from the perspective of an end user who does not know how it is implemented

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

What do static data structures do with memory? Who controls this?

A

Reserves memory for a set amount of data - the programmer establishes this in advance

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

How is an array usually implemented?

A

As a static data structure that is fixed in size and can only contain elements of the same data type

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

What can and cannot be changed in a static data structure? What would you need to do if you wanted to change something that cannot be changed?

A

The contents can be changed however the size of it cannot be changed - if you needed an array of a different size, you would need to create a whole new array and then copy the contents from the original array to the new structure

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

How are static data structures efficient?

A

Can access elements directly (by index)

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

How are static data structures inefficient?

A

In terms of memory use - for example, if you allocate a space worth 100 elements but when running it only uses 10 - waste of memory. On the other hand, if too less memory is allocate, the program can crash when run due to insufficient memory

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

Why are dynamic data structures better than static data structures?

A

They are memory efficient and the number of data items that it can hold is limited only by the overall memory location to the program

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

What is an example of the dynamic data structure, a linked list, and state it’s advantages and disadvantages

A

Linked list:

+: size is not predetermined
-: elements cannot be readily accessed directly as they are accessed by memory location rather than index

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

Where is memory for dynamic data structures taken from? What does this do?

A

The memory heap - allocated memory for a program at runtime

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

Define array

A

Data structure that holds a number of data items/elements of the same type

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

What index do most languages use when identifying a position in an array?

A

0

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

What type of data structure is an array?

A

A static data structure

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

What do you need to ensure you refer to when retrieving a particular value from an array?

A

The correct index

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

How can you envisage a two dimensional array?

A

A table with rows and columns

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

What is another word for a two dimensional array?

A

Matrix

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

Which indexes do you need when implementing a two dimensional array

A

Column index and row index

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

What order do the indexes for a two dimensional array go in?

A

Column and then row

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

How are items positioned in a 3 dimensional array?

A

Using 3 indexes

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

What is a field?

A

A fixed number of variables

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

What is a record?

A

A data structure that consists of a fixed number of variables (fields)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Do fields in a record need to have the same data type?
No
26
How would you create a record for player data? And then retrieve information from this record?
1. Create a class that contains fields that state what attributes for each piece of information will be stored about the player 2. Create a player record by using the PayerRecord() subroutine 3. Store the details of the player: I.e.: player1.playernumber= 1; player1.DateOfbirth= new DateTime(1994,7, 3) 4. You need to specify the name of the record and the field that you need to retrieve information from the record ie. console.WriteLine($”Name: {player1.playernumber}{player1.dateOfbirth}”);
27
Where is memory for a dynamic data structure taken from?
The memory heap
28
What is the heap?
Amount of memory allocated to a program at runtime
29
What is the default coding for text files? What is its main property?
UFT-8 = backward compatibility with ASCIIN which means it can take a text file that is encoded as ASCII and convert it to a human readable text without any compatibility issues.
30
What is the difference between a private and protected attribute?
A private attribute can be accessed (within its class) by derived subclasses however a public attribute can only be accessed within its class
31
Why are some attributes private whilst other methods are public?
Attributes are private so they cannot be altered throughout the program/outside the class however methods are public so certain fields can have a change in value without affecting the entire class.
32
What type of data structure is a stack? Why?
Dynamic - it uses unused memory
33
What concept is a stack an example of and why?
abstraction - conceptual model that describes how data is organised from the perspective of an end user that does not know how it is implemented
34
Where does a stack use memory from?
The heap
35
How can you delete items in a stack (impact on pointer too) and what does this do to the memory?
You can delete items by simply removing them and then moving the pointer to the next data item - when items are deleted, the memory location is freed up and returned to the heap
36
What are lists examples of?
Abstract data types
37
What happens if you PUSH an element in a stack?
The item goes to the very top of the list and the top pointer is moved to that element
38
What happens if you POP an element in a stack?
When you pop an element, it can mean you have either replaced, deleted or overwritten the top element - the element does not actually disappear but instead the top pointer moved to the next element in the list (the element you popped waits to be overwritten)
39
What does the PEEK operation do in a stack?
It returns the top element in the stack to the user
40
Which operation checks whether the stack is empty?
Is_empty()
41
Which operation checks whether the stack is full?
Is_full() - checks whether stack is at maximum capacity when stored in a static data structure
42
What structure does a stack use?
LIFO - last in first out
43
What index does the first item in the stack take?
0
44
What will happen if ha stack exceeds the allowed number of elements ?
Stack overflow
45
Where is entry placed when a subroutine is called?
When it is placed on the call stack
46
When a subroutine calls another subroutine, what happens?
(1) parameter values must be passed from the caller to subroutine (2) called subroutine must be executed (3) returned values from the subroutine must be passed back to the caller
47
What is the call stack?
An area of memory that is allocated to a program to store information about an active subroutine
48
What is an active subroutine?
A subroutine that has been called but hasn’t finished executing
49
What is the size of a call stack?
Finite
50
How is memory for a call stack allocated?
Before the program is run
51
When is a stack frame created?
When a subroutine is called
52
What is a stack frame
A reference to the ‘execution point’ of a subroutine which is like the line number where the program control needs to return to if another subroutine is called
53
What is a stack frame also referred to as?
A return pointer
54
What does a stack frame contain?
Return address, value of parameters and value of local variables for each active subroutine
55
Define hashing
When a large data set is organised so each record is assigned a unique address
56
What is a hash table
A data structure that creates a mapping between keys and values
57
How does a collision occur?
When two key values compute the same hash
58
What is a collision referred to as?
Synonym
59
How can you deal with a collision?
(1) put the item in the next free slot available in the table (2) algorithm can increase the skip increments value ie. 1, 3, 5 … etc. rather than by 1 to find a free space
60
What can one collision handling method lead to?
Putting item in next free slot can lead to clustering of items in a table
61
What is a dictionary?
A collection of key-value pairs in which the value is accessed via the associated key.
62
What is a graph an example of?
An abstract data structure representing a complex relationship
63
What are the features of an undirected graph? (2)
- has no arrows on edges (doesn’t indicate direction) - the edge can have a weight
64
What are the features of a directed unweighted graph?(2)
No weights are associated with the edges however does have arrows to represent direction
65
Define graph
Set of vertices/nodes connected by edges
66
What are the 2 ways a graph can be represented?
- adjacency matrix - adjacency list
67
Describe how an adjacency matrix looks like
A table with rows and columns
68
What are the advantages of an adjacency matrix?
It is convenient to work with and adding edges is simple
69
What are the disadvantages of an adjacency matrix?
A sparse graph will not have many connections(edges) which will leave lots of empty cells (wasted memory)
70
How does an adjacency list look like?
A table with rows only
71
What syntax is used in a an adjacency list?
Square brackets and commas
72
How do you represent no links on an adjacency list?
Empty square brackets
73
What are the advantages of an adjacency list?
Space efficient - uses storage for links that exist only Good way of representing large sparsely connected graphs
74
What is a tree?
A connected, undirected graph with no cycles
75
Does a tree have a root?
No
76
Define a rooted tree
A tree that has one vertex that has been designated as the root
77
What type of relationship does a rooted tree have with other nodes? What node is the exception to this?
A parent child relationship. It’s own node (root node) is the exception to this as it has no parent and all other nodes are it’s descendants
78
What is a binary tree?
A rooted tree
79
What is a key feature of a binary tree
Each node to at most 2 children
80
What is a common application of a binary tree?
Binary search tree
81
How would you carry out an in order traversal of a binary tree?(where is the root seen and positions)
Upwards: (1) Left most bottom node is FIRST (2) Followed by the node that connects it (3) Followed by the node that is next to the first (also connected to (2)) (4) followed by node that is above (2) (5) followed by root node Now goes downwards following same pattern … ends with the rightmost bottom node
82
How would you carry out a pre-order traversal?
Starts with the root Goes left Then goes left again Then outputs the next left node and it’s right node Then goes to the next node coming out of (2) Repeats Then goes to the right hand side of root Repeats Rightmost node at bottom is also last node in order
83
How would you carry out a post order traversal?
Starts with bottom left most node (2) goes to node next to it Then goes to it’s parent node Then goes to bottom node next to (2) Goes to node next to it Then goes to it’s parents node Then goes to next parent node Repeats starting on right side bottom leftmost node …root comes very last as it is the biggest parent node there
84
What is a balanced binary tree?
A tree where the nodes are Distributed in a way that height is kept to a minimum which allows efficient searching
85
What do you call a node with no children?
A leaf
86
What is a branch?
A path from the root to a leaf
87
What is the height of the tree equal to?
The number of edges that connect the root node to the leaf node that is furthest away from it (the longest branch)
88
What type of structure is a binary search tree?
A dynamic data structure
89
How can a vectors be represented?
As a list of numbers As a function As a way of representing a geometric point in space
90
What is a dictionary a useful way of representing
A vector if viewed as a function
91
How can you represent a 4-vector over R
R^4
92
How can you represent a vector as a function?
An integer followed by an arrow followed by the value it takes
93
What does vector addition achieve
Translation
94
What does scalar-vector multiplication achieve?
Scaling
95
What is the convex combination of the 2 vectors u and v an expression of the form of…
au + bv where a and b are >= 0 and a+b=1
96
How would you find the dot product of 2 vectors, ie. U and V u = [u1, …, un] v=[v1, …, vn]
u . v = u1v1 + u2v2 + … + unvn
97
How can you apply the dot product
When finding the angle between 2 vectors

A-Level Computer Science (A1+A2) (4 decks)

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