Flashcards
Computing Paper 2: 1.4.2- Data structures
Cards in this deck (16)
- 1What is an array?Ordered, limited set of elements of a single type. Square brackets.
1D: Linear array
2D: visualised as table or spreadsheet, go down rows & across the columns.
3D: Multi-page spreadsheet (array no, row no, column no) - 2What is a record?A row in a file that is made up of fields. They are used in databases.
- 3What is a list?Number of ordered items which can occur more than once. Can contain more than one data types. Square bracket.
- 4What is a tuple?Ordered set of values of any type. It is immutable (cannot be changed). Regular brackets.
- 5What is a linked list?Dynamic data structure (grow/shrink in size). Each item called node & has data field & pointer field (address of next item). Also states next free space.
- 6What is a graph?Set of vertices/ nodes connected by edges.
Directed: can only traverse in 1 direction.
Undirected: Can traverse in both directions.
Weighted: cost attached to each edge. - 7Graph: Adjacency matrix
- 8Graph: Adjacency List
- 9What is a stack?Items can only be added or removed from top of stack. They are used to reverse an action such as going back on a web browser.
Dynamic:no of elements increase/decrease
Static: fixed size, more efficient use of memory - 10What is a queue?Items added to end of queue and removed from front of queue. E.g used in printers.
Linear: array, 2 pointers, point to back of queue and front.
Circular: Allows use of addresses again, once rear pointer = max size, loops back to front to store values in empty spaces. - 11What is a tree?Connected form of graph. Have root node (top) that are connected by branches to other nodes.
Child: node w/ incoming edges.
Parent: node w/ outcoming edges.
Edges: connects 2 nodes.
Subtree: section of tree w/ parent & child. - 12What is a binary tree?Tree that has a max of 2 children per node.
- 13Methods of traversing a binary tree: Pre-order traversalRoot node, left subtree, right subtree
- 14Methods of traversing a binary tree: In-order traversalLeft subtree
Root node
Right subtree
- 15Methods of traversing a binary tree: Post-order traversalLeft subtree (passed on the left)
Right subtree
Root node
- 16Methods of traversing a binary tree: Breadth-first traversalF, B, G, A, D, I, C, E, H
Top to bottom.
Parents to child nodes.