4.2 (every spec covered) Flashcards
(106 cards)
1
Q
What is a composite data type?
A
A data type that can group together multiple values of different types under a single name.
2
Q
What are the two composite data types?
A
String, Array
3
Q
What are abstract data types?
A
A logical description of how a data structure behaves not how its implemented
4
Q
3 Abstract data types
A
List, stack, queue
5
Q
What are elementary data types
A
basic building blocks for representing data and used to define variables and specify the kind of values they can store
6
Q
3 Elementary data types
A
Integer, real, boolean, char
7
Q
Do arrays exist in python?
A
No, have to be imported by a library
8
Q
Key differences between arrays and lists
A
Arrays: defined size, data is stored contiguously in memory
Lists: list is free to grow, values are stored in various locations in memory
9
Q
What are Contiguos elements?
A
contiguous elements are positioned in a continuous, uninterrupted sequence
10
Q
What type of data structure is a queue
A
FIFO (first in first out)
11
Q
Functions needed for a linear queue
A
enqueue
dequeue
peek
Check if the queue is empty
Check if the queue is full
12
Q
What is enqueue and how is it acheived (4)
A
Adding items to a queue
Check that queue is not full
Add to the value of the rear pointer
Then add the new item to the position indicated by the rear pointer.
13
Q
What is dequeing and how is it achieved (4)
A
Removing an item
Return value at the front of the queue and deleter or pop
Move remaining items up the queue one by one
Decrement the rear pointer.
14
Q
Difference between circular and linear queues
A
Circular queues do not move items up when an item is dequeued.
15
Q
What is different with the items in a priority queue
A
All items have a level of priority
16
Q
What are static data structures and what is a example
A
Static data structures are fixed in size
Memory cant be reallocated once the program is running.
Array
17
Q
What are abstract data structures
A
can grow or shrink.
Allocates and deallocates memory from the heap
18
Q
What problem may come with abstract data structures
A
may cause overflow(exceeding maximum memory limit).
19
Q
What is a stack
A
A stack is a last in, first out abstract data type
20
Q
What is a matrix
A
An array of tables or values
21
Q
What are the six methods required in a stack
A
push(item) - adds item to the top of the stack.
pop() - removes and returns the item on top of the stack.
isFull() - checks if the stack is full
isEmpty() - checks if the stack is empty
peek() - returns the top item without removing it from the stack.
size() - return the number of items on the stack.
22
Q
What is stack overflow
A
attempting to push an item onto a stack that is full
23
Q
what is stack underflow
A
attempting to pop from a stack that is empty
24
Q
What is the call stack
A
data structure that provides the mechanism for passing parameters and return addresses to subroutines.
25
What is a stack frame
A stack frame contains all the parameters, the return address and the local variables for a single call to a subroutine which has not yet completed.
26
What is a dictionary
A dictionary is an abstract data type made up of associated pairs each pair has a key and a value.
27
Why are hash tables used
a hash table will find any record in a dataset almost instantly, no matter how large the data set.
28
What is a hash table
a data structure that creates a mapping between the keys and values.
29
What causes a collision in a hash table
when an algorithm generates the same address for different primary keys.
30
What is the fix for a collision in hash tables
linear probing happens, this is where the item is put in the next free slot in the table following a collision
31
What is rehashing (3)
process of resizing and reorganizing a hash table when it becomes too full or inefficient.
It involves creating a new, larger hash table
reinserting all existing elements using a new hash function or the same one with a larger table size.
32
What features must a circular queue have
They must have a front and rear pointer. They must have a size attribute.
the front pointer is simply adjusted when an item is removed from the queue - the data is not deleted.
33
6 functions/features of a dictionary
Add
Delete
Amend
Return the value associated with a key
Return True or False depending on whether the key is in the dictionary,
Return the length of the dictionary.
34
Python function to get a list of the key:value pairs of a dictionary named thisdict
x = thisdict.items()
35
Python function to return the keys of a dictionary
x = thisdict.keys()
36
How is a new record added to a hash table (3)
Hash table has an algorithm applied to the key value,
the result is the location in the table where the record should be stored.
If location is not empty the use next free location.
37
What are graphs (3)
Graphs are abstract data structures representing complex relationships between the items of data.
a set of nodes connected by edges
way or representing relationships between entities
38
What is a weighted graph
a type of graph where each edge (connection between nodes) has a numerical value associated with it
39
What is a vertex/node
vertices/nodes can represent any discrete object or entity on a graph
40
what is a edge/arc
a relationship or connection between two nodes in a graph.
41
What is the difference between directed and undirected graph
In an undirected graph, edges do not have a direction associated with them.
In a directed graph, each edge has a direction associated with it.
42
How do adjacency matricies represent a graph
For an undirected graph with
n nodes, the adjacency matrix is a
n×n matrix.
43
What is the advantage of representing a graph with an adjacency matrix (3)
Fast edge lookups, O(1)
easy to implement and understand
more memory efficient for dense graphs
44
What is the disadvantage of representing a graph with an adjacency matrix (2)
Space complexity O(n^2)
inefficient for sparse graphs
45
What is a tree
a connected, undirected graph with no cycles.
46
What is a rooted tree
a tree in which one nopde/vertex has been designated as the root.
A rooted tree has parent-child relationships between nodes.
47
How do we create a dictionary in python
my_dict = {key: value, key: value etc}
48
How do we check for a value in a dictionary
Use the in keyword
if 2 in mydict.values():
print(True)
49
what are tuples
are lists that cant be changed once created, they are an immutable and static.
50
what are dynamic data structures
organisations or collections of data in memory that have the flexibility to grow or shrink in size.
51
A data structures is immutable if
The structure/ data cannot be changed during run time
52
what are the applications of stack
performing depth first searches on graph data structures
keep track of user inputs
used in RPN
53
What is queue overflow
attempting to enqueue an item to a full queue
54
what is queue underflow
attempting to dequeuean item from a empty queue
55
describe the steps involved in adding an item to a stack(3)
check stack full
increment stack pointer
insert data item at new pointer
56
describe the steps in removing an item from a stack (3)
check for stack underflow
copy output data item indicated by back pointer
decrement the rear pointer
57
How do we represent a graph using an adjacency list
List all nodes,
Each node points to a list of all the adjacent to nodes to which it is linked
this can be implemented using dictionaries,
graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
}
dictionary keys represent the nodes, values represent connected nodes
58
What are the disadvantages of representing a graph using an adjacency list
(3)
Disadvantages:
Checking for presence or absence of an edge requires traversing the linked list of all corresponding nodes O(k)
more complex to implement
inefficient for dense graphs
59
what are the advantages of representing a graph using an adjacency list (2)
Advantages:
more space efficient than a matrix for a sparsely connected graph
uses less memory when representing a graph with fewer edges.
60
What are the applications of graphs
map networks
61
What is an adjacency matrix
For a graph with
n vertices, the adjacency matrix
A is an n×n matrix where:
A[i][j]=1 if there is an edge from vertex
A[i][j]=0 if there is no edge between them.
62
What is an adjacency list
n adjacency list is another way to represent a graph, using a collection of lists (or dictionaries) where each node stores a list of its adjacent (connected) nodes.
63
What is meant by connected in the definition for a tree, which is a connected undirected graph with no cycles
It is always possible to find a path from one node to another
64
What is meant by undirected in the definition for a tree, which is a connected undirected graph with no cycles
The edges between nodes are bi-directional there is no arrow pointing in one direction
65
What is meant by no cycles in the definition for a tree, which is a connected undirected graph with no cycles
there is no path in the tree that returns to the start node
66
What is a binary tree
a rooted tree where each node can only have one, zero or two pointers/edges
each node can have at most two children
67
What are operations that can be performed on a tree
add node
delete node
binary search return data in node
traversals
searches
68
What is the difference between a rooted tree and a binary tree
a binary tree is a rooted tree where each node can have at most two child nodes,
rooted tree can have more
69
what are the characteristics of a good hashing algorithim
be calculated quickly
result in as few collisions as possible
use as little memory as possible
70
What problems may linear probing cause
prevents other items from being stored in their correct location
can result in clustering
71
What is meant by clustering in the context of hash tables
when linear probing results in several positions being filled around common collision values
72
What is an alternative to having to deal with collisions when using hash tables (2 ways)
By using a 2d hash table
allows for more than one item to be placed at the same position known as chaining
OR
Create an second table for collisions known as an overflow table
73
What are the applications for hash tables
file systems linking a file name to the file path
74
What are the three opeartions that can be performed on a hash table
Add new item to hash table
Delete
Retrieve
75
Describe the process of adding an item to a hash table
Calculate position of item using hash function
If empty insert item
if full, either linear probe or check overflow table
76
Describe the process of removing an item from the hash table
calculate position of item using hashing function
if position contains item, delete
if no check overflow table, increment position until item is discovered or end of overflow table is reached
77
Uses of dictionaries
Storing and retrieving data efficiently
Implementing other data structures
78
what is a vector
a series of numbers that represent information such as position or force
79
what is vector addition known as
translation
80
what is the convex combination of two vectors defined as
the shaded area between two vectors
81
What is the formula for the convex combination of vectors
(a*u) + ( Beta * v)
au + betav
where u and v are vectors
a + beta = 1
a and beta must be larger than 0
82
What is meant by the dot product of two vectors
number formed when multiplying each component of the first vector by the matching component of the second vector
then adding those two numbers together
83
What are the applications of dot product.
Graphical applications
finding the angle between two vectors
84
Describe how to find the angle between two vectors uding dot product (4 steps)
1. calculate dot product
2. calculate length of vectors using pythagoras
3. Multiply the lengths
4. use formula.
(dot product of vectors a and b) / (lengtha * lengthb) = cosx
85
What is the formula for cos x of two vectors
(dot product of vectors a and b) / (lengtha * lengthb) = cosx
86
What is meant by static allocation
Memory is assigned at compile-time and does not change at runtime.
87
What is meant by Dynamic allocation
Memory is assigned at runtime and can grow or shrink.
88
what are 2d arrays
Contains multiple arrays, where two indices are required to access elements.
89
what is meant by an n dimensional array and whats it useful for (3)
an array that can have n dimensions
n indices are required to access an individual data item
useful for complex data structures like images and videos
90
how would we write "hello world" to a text file called "data.txt" (2 lines)
with open("data.txt,"w")
file.write("hello world")
91
how would we output the contents of a text file called "data.txt" (2 lines)
with open ("data.txt","r")
print(file.read)
92
how do we add a value to the end of a list data structure
list.append(x)
93
how do we slice a list so that the first two values are cut off
list = list[2:]
94
how do we remove a value from the front of a list data structure
list.pop(0)
95
how do we add a key value pair to a dictionary called mydict
mydict["newkey"] = "newvalue"
96
how do we amend a value in a dictionary called my dict and we want to alter the value at the key "key"
mydict["key"] = "newvalue"
97
how do we return the value at a given key in a dictionary called mydict
print(mydict.get("given key")
98
how do we check if a key exits in a dictionary
if 'age' in my_dict:
print("The key 'age' exists.")
99
how do we check if a value exists in a dictionary
if value in dictionary.values:
print(value ,"exists")
100
what are the advantages of static structures like a fixed size array: (3)
Size defined at compile time
memory efficient for known size data sets
faster access because of contiguous memory
101
What are the disadvantages of static data structures like a fixed size array (2)
Not flexible, as memory allocation cannot change during runtime
memory may be allocated that isn't used
102
what are the advantages of a dynamic data structure like a list(3)
flexible as size of structure can grow or shrink during runtime
because of flexible memory allocation
uses memory from heap as opposed to stack, larger and more flexible than the stack
Memory is not allocated when unneeded
103
what are the disadvantages of a dynamic data structure like a list (2)
may result in memory overflow w
hen the program tries to allocate more memory than is available, leading to a failure in memory allocation
104
what is the application of the convex combination of vectors (2):
blending
geometry
105
what are the typical uses of rooted trees(4)
file systems
binary search tree
conversion into rpn
representing hierarchical structures
106
