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
2
Q
Name the different data structures you need to know?
A
- Queues and Stacks
- Grpahs
- Trees
- Hash Tables
- Dictionary
- Vector
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
4
Q
What are 2D arrays?
A
- Multiple axsis
- Where references are like coordinates
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
6
Q
How do you setup records?
A
- Define record structure - what fields will be in the record
- Declare a variable or array to use with the record structure
- Assign and retrive data from the variable record
7
Q
What are lists?
A
- Pythons version of arrays
- Which can be edited after creation
8
Q
What are tuples?
A
- Pythons version of arrays
- Which can be edited after creation
9
Q
How do you declare tuples?
A
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
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
12
Q
What are the advantages of dynamic data structures?
A
- Makes efficient use of memory
- Data structure only uses memory as it needs
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
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
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
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
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
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.
19
Q
What is the algorithm for inserting an item into the stack?
A
20
Q
How does insertion work in a queue?
A
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
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
23
Q
What is the differnce betwen directed and undirected graphs
A
- Undirected = edges work in two ways
- Directed = edges work in one way
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
25
How do you represent vertices in text form?
- The starting vertice and the ending one
- Followed by weight of edge if able to
26
What is an adjacency matrix?
- Used to represent a graph
- Read the top then the side to find the wieght of an edge if able it exsists
27
What is an adjacency list?
- 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
28
What are the advantages of adjacency matrix?
- 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
29
What are the disadvantages of an adjacency matrix?
- 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
30
What are the advantages of adjaceny lists?
Very space efficient
Using much less memory to store a sparse graph
31
What is a tree?
- Connected
- Undirected graph
- With no cycles
32
What are the parts that make up a tree?
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
What are binary trees?
- 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
What are the steps for contructing a binary tree?
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
How can you represent a binary tree in an array?
36
What are linked lists
- Can store data non continuously in memory
- Dynamic (Able to grow)
- Requires a whole list to be searched to find one item
37
When do you need hash tables
- Allows for the best qualities of linked lists and arrays
- Use an array called a hash table which can be looked up
38
What does a hash function do?
- Takes in input data (Key)
- Outputs a hash value which maps the initial key to a fixed index in the hash table
39
How does a hash table work?
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
Explain this diagram
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
What’s a collision in hash tables?
Where an new item is added and the hash created from the hash function is already used for another item
42
What is clustering
- Due to duplicate hashes being created
- Where the next available slot keeps being used
- Which in turn causes higher chances of collisions occurring
43
How does overflow occur?
- 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
What psudocode can you make to search an item in a hash table
45
Explain what this code is doing
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
What is the psudo code for inserting into a hashtable
47
What is this code doing?
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
What is the psudocode for deleting data in a hashtable
49
What is this code doing?
50
What are dictionaries?
- 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
How would I access the craig and carol data?
52
What are the required operations for dictionary implementation?
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
How are key:value pairs organised?
- 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
What are the purpose of vectors in CS?
Allows for programs to represent
- Spacital ionformation
- Movement
- In a numerical way
55
What can vectors store?
- Spacial information and movement
- Acceleration
- Velocity
- Position
- Force
56
How can you represent vectors?
- A list of numbers
- A dictionary
- A 1D array
- A function
57
What does it mean if a vector is R^4?
- The vector is a 4-vector
- As there is 4 items being stored in the vector
58
How would you represent this vector as a dictionary
59
How would you represent this vector as an array?
60
How would you represent this vector as a function
61
How would you represent the vector A=(5.0,7.0) on a multiaxsis graph?
62
How would you represent the vector B=(-8.0,3.5) on a multiaxsis graph?
63
How would you represent the vector C=(3.5,-5.0) on a multiaxsis graph?
64
How can store a 3-vector?
- Ue a 3D graph
- Providing you with information needed to mapp a straight path form the origin to destination
65
How do you add the two vectors
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
How do you subtract vectors?
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
How do you multiply vectors
1. Draw the origional vector
2. Then multiply the values by the multiplier given
3. Extend the vector using dotted lines
68
What is the convex combination of two vectors?
- 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
What is the dot or scalar product of two vectors?
- Found by multiplying each component of first vector
- By each matching component of the second vector
- Adding all the results
70
How would you find the dot cross scalar value of these two vectors?
71
What can you do with the dot product of two vectors?
- You can find the angle between two vectors
- Usefull in graphical applications as well as games
72
Whats the formula for finding the angle between two vectors?
- A and B are vectors
- Theta is the angle between the vectors
73
What are the steps in calculating the angle between two vectors?
[OBSELETE] AQA - A Level CS
flashcards
Decks in class (13)
# Cards
