Paper 1 Module 4 Flashcards
(35 cards)
What are arrays?
An array is an ordered, finite set of elements of a single data type.
What are lists?
A list is a data structure consisting of a number of ordered items where the items can occur more than once. The values are stored non-contiguously. This means that they do not have to be stored next to each other in memory.
What are tuples?
An ordered set of values of any type is called a tuple. A tuple is immutable, which means it cannot be changed. elements cannot be added or removedonce it has been created.
What is a linked list?
A linked list is a dynamic data structure used to hold an ordered sequence. Each item is called a node, and contains a data field alongside another address called a link or pointer field.
What is a graph and what are the 3 types of a graph?
A graph is a set of vertices/nodes connected by edges/arcs.
Directed Graph
Undirected graph
Weighted Graph
What is a directed graph?
It is a graph where it’s edges can only be traversed in one direction.
what is an undirected graph?
It is a graph where its edges can be traversed boths directions.
What is a weighted graph?
It is a graph where a “cost” is added to each edge.
What two ways do computers process graphs?
Adjacency matrix
Adjacency List
What are the advantages for using an Adjacency Matrix for graphs?
Convinient to work with due to quicker access times.
Easy to add nodes.
What is an advantage for using an adjacency list?
More space efficient for large, sparse networks.
What is a dynamic data structure?
It is a data structure whose size and structure can be changed during runtime.
What are stacks?
A stack is a last in first out data structure. Items can only be added to or removed from the top of the stack. Stacks are key data structures in computer science; they are used to reverse an action.
What are queues?
A queue is a first in first out data structure ; items are added to the end of the queue and are removed from the front of the queue.
What is a tree? (in computer science)
A tree is a connected form of a graph. Trees have a root node which is the top node in any tree. Nodes are connected to other nodes using branches, with the lower-level nodes being the children of the higher-level nodes.
What is a binary tree?
A binary tree is a type of tree in which each node has a maximum of two children. These are used to represent information for binary searches, as information in these trees is easy to search through. The most common way to represent a binary tree is storing each node with a left pointer and a right pointer.
What are the 3 ways that a binary tree can be traversed?
Pre-order
In-order
Post-order
What way do you go when traversing a binary using Pre-order traversal?
Pre-order traversal follows the order :- root node, left subtree, then right subtree.
What way do you go when traversing a binary using In-order traversal?
In-order traversal follows the order: left subtree, root node, right subtree.
What way do you go when traversing a binary using Post-order traversal?
Post order traversal follows the order : Left subtree, right subtree, root node.
What is the definition of a graph?
It is a data structure used to represent relationships between objects, often visualized as nodes (vertices) connected by edges (arcs)
what is a loop when in context of graphs?
it is a node with an edging pointing to itself.
what are leaf nodes?
They are nodes in a tree that do not have any children.
How do we add items to a binary tree?
If the value of the new data added is less than the value in the current node then branch left, otherwise branch right.
