1.4.2 Data Structures Flashcards
what is the difference between static and dynamic structures
static structures have a fixed length while dynamic structures have a changeable length
what is the difference between an array and a tuple(1)
Tuples are immutable (data cannot be changed), arrays can be modified(1)
what is a 2d array
a 2d array is an array that contains other arrays
what is a queue
a static first in first out structure for ordering data
what is an abstract data structure
a data structure made by the programmer
what is a list
an abstract data structure which stores a number of items
what is a linked list
an abstract dynamic data structure to ordered data from different locations
what is a stack
a last in first out data structure used to store instructions
what does the purpose of the call stack
to hold the active suboutines and their data
what is the difference between a list and a stack
a list is first in first out a stack is last in first out
what is the difference between a weighted and unweighted graph
with a weighted graph each edge has a value with an unweighted graph edges have no value
what is the difference between a directed and undirected graph
with a directed graph edges can only be traversed in one direction with an undirected graph they can be traversed in any direction
what is an adjacency matrix
a table to show the relationships in a graph
what is a tree
an abstract data structure used to represent structures making data easier to search
what is a Root Parent and Child
root: node with no incoming edges parent: a node with an outgoing edge child: a node with an incoming edge
what is the difference between depth and breadth first traversal
depth: explore the entirety of a route before continuing to the next breadth: checking all available roots from a node before progressing
what is a binary search tree
a rooted tree each node has a maximum of 2 children
Describe the difference between an array and a linked list.(2)
A linked list is a dynamic data structure (1) whereas an array is static (1).
Define the term ‘array’. (2)
A data structure (1) Has a single identifier (1).
Describe what is meant by the term ‘linked list’ (3)
A data structure (1) Each node consists of data and pointer. (1) Pointer gives location of next node (1)
State which of a stack or queue would be considered as a ‘First In First Out’ data structure.(1)
A queue (1)
What is meant by a ‘tuple’? (3)
A tuple is an ordered sequence of elements that is immutable (1) which means that the values within the tuple cannot be modified when the program is running (1) . The elements of a tuple can be of different data types (1)
What is meant by a ‘list’? (3)
A list is an abstract data type (1) that describes a linear collection of data items in some order (1) in that each element occupies a specific position in the list.(1)
What is meant by a ‘record’
A record is a data structure (1) that consists of a fixed number of variables called fields (1) . Each field in a record can have a different data type (1)
State the meaning of the term static.(1)
Size is fixed when structure created cannot change during processing (1)
State one type of data structure that is always considered to be static.
(1)
Array (1)
State the meaning of the term dynamic.(1)
Size can change during processing (1)
Give one disadvantage of using a dynamic data structure.(1)
Storage required is unknown initially (1) OR more difficult to program (1)
How would you add a new value to an unordered linked list? (3)
Create a node with the value (1) and set the next pointer to the value of the head pointer (of the linked list) (1) and set the head pointer (of the linked list) to point to the new node (1)
What is meant by a graph having a loop? (1)
It has an edge that connects a node to itself (1)
What is meant by the path of a graph? (1)
It is the sequence of nodes that are connected by edges (1)
What is meant by the degree of a node? (1)
The number of other nodes that it is connected to (i.e. the number of neighbours it has) (1)
Define the term ‘stack’. (4)
It is an abstract data type (1) that holds an ordered (1) linear sequence of items (1). It is a last in first out structure (1)
Define the term ‘queue’. (4)
It is an abstract data type (1) that holds an ordered (1) linear sequence of items (1). It is a first in first out structure (1)
Define a ‘binary tree’. (2)
It is a rooted (1) tree where every node has at most two children (1)
