Brainscape's Knowledge GenomeTM

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


See full index

[OBSELETE] AQA - A Level CS > Data Structures > Flashcards

Data Structures Flashcards

1
Q

What is a data structure?

A
  • A way of organising and storing data in a computer
  • So that it can be accessed and modifided
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Name the different data structures you need to know?

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

What is an array

A
  • Allows multiple items of the same data type
  • Under a common name
  • The first element of an array is labled 0
  • Can be 2D arrays
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are 2D arrays?

A
  • Multiple axsis
  • Where references are like coordinates
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the limitations of arrays?

A
  • Must store the same data type
  • Static data structure where items cannot change in size once declared
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How do you setup records?

A
  1. Define record structure - what fields will be in the record
  2. Declare a variable or array to use with the record structure
  3. Assign and retrive data from the variable record
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are lists?

A
  • Pythons version of arrays
  • Which can be edited after creation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are tuples?

A
  • Pythons version of arrays
  • Which can be edited after creation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How do you declare tuples?

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

What are static data structures?

A
  • Organisation or collection of data in memory thats fixed in size
  • Max size needs to be known
  • Memory can’t be rellocated once program running
  • Arrays / tuples are static
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are dynamic data structures?

A
  • Organisation or collection of data in memoery that has flexibility to grow or shrink in size
  • Shows how much memory will be used
  • Unused memory is allocated or de-allocated as needed
  • Linked lists are dynamic
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the advantages of dynamic data structures?

A
  • Makes efficient use of memory
  • Data structure only uses memory as it needs
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are the disadvantages of dynamic data structures?

A
  • Risk of overflow when the allowed limit is exceeded
  • RIsk of underflow if data structure is empty
  • Harder to program because the code needs to keep traack of data size and location of items
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the advantages static data structures?

A
  • Memory allocation fixed
  • Meaning no issues with adding and removing items from data structure
  • Easier to program due to no requirement to check on size of data structure before accessing it
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the disadvangtages of static data structures?

A
  • Can be inefficient on memory
  • Due to portions of the allocated memory not being used
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the stack data structure?

A
  • LIFO data structure (Last in First out)
  • Last peice of data put in
  • Is the first peice of data taken out
  • Only uses pointer to see the item at the start of the stack
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the queue data structre?

A
  • FIFO (First Item in First Item Out)
  • Uses two pointers for the front and the back
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How does pushing , popping and peeking work in a stack data structure?

A

Push: Adds an element to the back of the queue. The pointer remains at the back of the queue.
Pop: Removes an element from the front of the queue. The pointer moves to the next element in the queue.
Peek: Returns the element at the front of the queue without removing it. The pointer remains at the front of the queue.

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

What is the algorithm for inserting an item into the stack?

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

How does insertion work in a queue?

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

How does deleting an item from a queue work?

A
  • If the queue is empty, return an error message
  • Remove the front node of the queue
  • Set the front pointer to the next node in the queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are graphs?

A
  • Dynamic data structure (grow and shrink)
  • used to model nav systems, data transmission
  • No rules or limitations of how the nodes can be linked to each other
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the differnce betwen directed and undirected graphs

A
  • Undirected = edges work in two ways
  • Directed = edges work in one way
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the weight or cost of a graph?

A
  • Depends on the application of the graph
  • Like distance or bits per second
  • Found on the edges of the graph
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

How do you represent vertices in text form?

A
  • The starting vertice and the ending one
  • Followed by weight of edge if able to
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is an adjacency matrix?

A
  • Used to represent a graph
  • Read the top then the side to find the wieght of an edge if able it exsists
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is an adjacency list?

A
  • Used to represent a graph
  • Implemented as a list of dictionaries
  • Key in each dictionary being the node and the edge weight

From A you can go to
- B - cost = 8
- C - cost = 2

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

What are the advantages of adjacency matrix?

A
  • Easy to work with
  • Adding new edges is simple and quick
  • Checking for presence of edges can be done using for loops and a 2D array
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What are the disadvantages of an adjacency matrix?

A
  • A sparse graph with lots of edges but few edges causes empty space(wasted memory)
  • Implementing the adjacent matrix in a 2D static arrya makes deletion / insertion difficult
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What are the advantages of adjaceny lists?

A

Very space efficient
Using much less memory to store a sparse graph

31
Q

What is a tree?

A
  • Connected
  • Undirected graph
  • With no cycles
32
Q

What are the parts that make up a tree?

A

Root nodes - the node which the tree stems form
Branches - Lines that connect nodes together
Children nodes - nodes that stem from the root node
Leaf nodes - nodes without any further sub trees

They are all recursive down the tree

33
Q

What are binary trees?

A
  • Binary search tree
  • Dynamic data type (add + remove)
  • Efficient sorting,searching and retrival of data
  • Can reflect structure data such as heirachys
  • Each nodecan have 0,1 or 2 children only
34
Q

What are the steps for contructing a binary tree?

A
  1. Look at the data and identify a root node
  2. Place child nodes on the left or right depending on if it is more or less than the root node (Example uses alphabetically)
  3. Continue with other nodes following the path made from the child nodes (eat is less than jack but more than could)
35
Q

How can you represent a binary tree in an array?

A
36
Q

What are linked lists

A
  • Can store data non continuously in memory
  • Dynamic (Able to grow)
  • Requires a whole list to be searched to find one item
37
Q

When do you need hash tables

A
  • Allows for the best qualities of linked lists and arrays
  • Use an array called a hash table which can be looked up
38
Q

What does a hash function do?

A
  • Takes in input data (Key)
  • Outputs a hash value which maps the initial key to a fixed index in the hash table
39
Q

How does a hash table work?

A
  1. Initial data is inputed into a hash function
  2. Which is then converted into a hash
  3. Which links the initial key to a fixed index in the hash table
40
Q

Explain this diagram

A

Main function
- Creates data for each person
- Uses hash function and prints out each persons hash

Hash Function
- Takes in the initial data
- Makes a key by MOD 50

41
Q

What’s a collision in hash tables?

A

Where an new item is added and the hash created from the hash function is already used for another item

42
Q

What is clustering

A
  • Due to duplicate hashes being created
  • Where the next available slot keeps being used
  • Which in turn causes higher chances of collisions occurring
43
Q

How does overflow occur?

A
  • Where a predetermined path is used when collisions occur
  • Meaning that hashes that are full are skipped when an item of the same hash is added
  • Meaning it occupies the next available space
44
Q

What psudocode can you make to search an item in a hash table

A
45
Q

Explain what this code is doing

A
  1. Feed in a key to hash function
  2. Then take the hash and go to the array index
  3. If the value is the key we want then return value found
  4. Else follow the linked list (overflow) until value found then return it
46
Q

What is the psudo code for inserting into a hashtable

A
47
Q

What is this code doing?

A
  1. Feed in key to hash function
  2. Use hash and fin the index it corresponds to in the array
  3. If the location is empty then insert the value
  4. If the location is full then follow the linked list (overflow) until a free space is found then insert the value
48
Q

What is the psudocode for deleting data in a hashtable

A
49
Q

What is this code doing?

A
50
Q

What are dictionaries?

A
  • General purpose / abstract data structure
  • Stores groups of objects
  • Has a set of keys which has a value associated with it
  • Which when supplied returns the associated value
51
Q

How would I access the craig and carol data?

A
52
Q

What are the required operations for dictionary implementation?

A
  1. Create a new empty dictionary
  2. Add a new key:value pair
  3. Delete a key:value pair
  4. Amend the value of a key:value pair
  5. Return the value of a key
  6. Return TRUE or FALSE depending if a key exsists
  7. Return the length of the dictionary
53
Q

How are key:value pairs organised?

A
  • Pairs are not in any order in the dictionary
  • Keys are hashed and placed in the corresponding resultant locaition
  • Making retrival quick and easy
54
Q

What are the purpose of vectors in CS?

A

Allows for programs to represent
- Spacital ionformation
- Movement
- In a numerical way

55
Q

What can vectors store?

A
  • Spacial information and movement
  • Acceleration
  • Velocity
  • Position
  • Force
56
Q

How can you represent vectors?

A
  • A list of numbers
  • A dictionary
  • A 1D array
  • A function
57
Q

What does it mean if a vector is R^4?

A
  • The vector is a 4-vector
  • As there is 4 items being stored in the vector
58
Q

How would you represent this vector as a dictionary

A
59
Q

How would you represent this vector as an array?

A
60
Q

How would you represent this vector as a function

A
61
Q

How would you represent the vector A=(5.0,7.0) on a multiaxsis graph?

A
62
Q

How would you represent the vector B=(-8.0,3.5) on a multiaxsis graph?

A
63
Q

How would you represent the vector C=(3.5,-5.0) on a multiaxsis graph?

A
64
Q

How can store a 3-vector?

A
  • Ue a 3D graph
  • Providing you with information needed to mapp a straight path form the origin to destination
65
Q

How do you add the two vectors

A
  1. Plot the two graphs
  2. Move the second graph onto the end of the first
  3. Draw a point from the origin to the tip of the extended vector
66
Q

How do you subtract vectors?

A
  1. Plot the two graphs
  2. Flip the first vector where its mirrored from the origonal and starts at the tip of the second vector instead of the origin
  3. Draw a line from the origin to the tip of the second vector
67
Q

How do you multiply vectors

A
  1. Draw the origional vector
  2. Then multiply the values by the multiplier given
  3. Extend the vector using dotted lines
68
Q

What is the convex combination of two vectors?

A
  • The space between two vectors when the tip is closed
  • Used in games for pespective and field of view
  • (a * u) + (a * v) OR au + bu
  • u adn v are vectors
  • a + b = 1
  • a and b must be >=0
69
Q

What is the dot or scalar product of two vectors?

A
  • Found by multiplying each component of first vector
  • By each matching component of the second vector
  • Adding all the results
70
Q

How would you find the dot cross scalar value of these two vectors?

A
71
Q

What can you do with the dot product of two vectors?

A
  • You can find the angle between two vectors
  • Usefull in graphical applications as well as games
72
Q

Whats the formula for finding the angle between two vectors?

A
  • A and B are vectors
  • Theta is the angle between the vectors
73
Q

What are the steps in calculating the angle between two vectors?

A

[OBSELETE] AQA - A Level CS (13 decks)

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