Data Structures Flashcards
What data type is an integer and why?
Primitive - as it can only contain 1 value
What are some examples of primitive data types?
Integers
What is a compound/composite data type? What is an example?
More than 1 primitive data types combined together for example, a record or a class
Define data structure
Collection of data that is organised to allow efficient processing
Define abstract data type
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
What do static data structures do with memory? Who controls this?
Reserves memory for a set amount of data - the programmer establishes this in advance
How is an array usually implemented?
As a static data structure that is fixed in size and can only contain elements of the same data type
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?
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 are static data structures efficient?
Can access elements directly (by index)
How are static data structures inefficient?
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
Why are dynamic data structures better than static data structures?
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
What is an example of the dynamic data structure, a linked list, and state it’s advantages and disadvantages
Linked list:
+: size is not predetermined
-: elements cannot be readily accessed directly as they are accessed by memory location rather than index
Where is memory for dynamic data structures taken from? What does this do?
The memory heap - allocated memory for a program at runtime
Define array
Data structure that holds a number of data items/elements of the same type
What index do most languages use when identifying a position in an array?
0
What type of data structure is an array?
A static data structure
What do you need to ensure you refer to when retrieving a particular value from an array?
The correct index
How can you envisage a two dimensional array?
A table with rows and columns
What is another word for a two dimensional array?
Matrix
Which indexes do you need when implementing a two dimensional array
Column index and row index
What order do the indexes for a two dimensional array go in?
Column and then row
How are items positioned in a 3 dimensional array?
Using 3 indexes
What is a field?
A fixed number of variables
What is a record?
A data structure that consists of a fixed number of variables (fields)
Do fields in a record need to have the same data type?
No
How would you create a record for player data? And then retrieve information from this record?
- Create a class that contains fields that state what attributes for each piece of information will be stored about the player
- Create a player record by using the PayerRecord() subroutine
- Store the details of the player: I.e.:
player1.playernumber= 1;
player1.DateOfbirth= new DateTime(1994,7, 3) - 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}”);
Where is memory for a dynamic data structure taken from?
The memory heap
What is the heap?
Amount of memory allocated to a program at runtime
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.
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
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.
What type of data structure is a stack? Why?
Dynamic - it uses unused memory
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
Where does a stack use memory from?
The heap
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
What are lists examples of?
Abstract data types
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
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)
What does the PEEK operation do in a stack?
It returns the top element in the stack to the user
Which operation checks whether the stack is empty?
Is_empty()
Which operation checks whether the stack is full?
Is_full() - checks whether stack is at maximum capacity when stored in a static data structure
What structure does a stack use?
LIFO - last in first out
What index does the first item in the stack take?
0
What will happen if ha stack exceeds the allowed number of elements ?
Stack overflow
Where is entry placed when a subroutine is called?
When it is placed on the call stack
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
What is the call stack?
An area of memory that is allocated to a program to store information about an active subroutine
What is an active subroutine?
A subroutine that has been called but hasn’t finished executing
What is the size of a call stack?
Finite
How is memory for a call stack allocated?
Before the program is run
When is a stack frame created?
When a subroutine is called
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
What is a stack frame also referred to as?
A return pointer
What does a stack frame contain?
Return address, value of parameters and value of local variables for each active subroutine
Define hashing
When a large data set is organised so each record is assigned a unique address
What is a hash table
A data structure that creates a mapping between keys and values
How does a collision occur?
When two key values compute the same hash
What is a collision referred to as?
Synonym
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
What can one collision handling method lead to?
Putting item in next free slot can lead to clustering of items in a table
What is a dictionary?
A collection of key-value pairs in which the value is accessed via the associated key.
What is a graph an example of?
An abstract data structure representing a complex relationship
What are the features of an undirected graph? (2)
- has no arrows on edges (doesn’t indicate direction)
- the edge can have a weight
What are the features of a directed unweighted graph?(2)
No weights are associated with the edges however does have arrows to represent direction
Define graph
Set of vertices/nodes connected by edges
What are the 2 ways a graph can be represented?
- adjacency matrix
- adjacency list
Describe how an adjacency matrix looks like
A table with rows and columns
What are the advantages of an adjacency matrix?
It is convenient to work with and adding edges is simple
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)
How does an adjacency list look like?
A table with rows only
What syntax is used in a an adjacency list?
Square brackets and commas
How do you represent no links on an adjacency list?
Empty square brackets
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
What is a tree?
A connected, undirected graph with no cycles
Does a tree have a root?
No
Define a rooted tree
A tree that has one vertex that has been designated as the root
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
What is a binary tree?
A rooted tree
What is a key feature of a binary tree
Each node to at most 2 children
What is a common application of a binary tree?
Binary search tree
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
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
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
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
What do you call a node with no children?
A leaf
What is a branch?
A path from the root to a leaf
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)
What type of structure is a binary search tree?
A dynamic data structure
How can a vectors be represented?
As a list of numbers
As a function
As a way of representing a geometric point in space
What is a dictionary a useful way of representing
A vector if viewed as a function
How can you represent a 4-vector over R
R^4
How can you represent a vector as a function?
An integer followed by an arrow followed by the value it takes
What does vector addition achieve
Translation
What does scalar-vector multiplication achieve?
Scaling
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
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
How can you apply the dot product
When finding the angle between 2 vectors
