1.4.2

Question 1

Linear data structures

Answer 1

-arrays
-lists
-stacks
-queues
-hash table

Question 2

Non linear data structures

Answer 2

-graphs
-trees
-binary search

Question 3

Records

Answer 3

• A row in a file or table
• Widely used in databases
• Made up of fields

Question 4

Lists

Answer 4

• A number of items
• Items can occur more than once
• Data can be of more than one data type

Question 5

Tuples

Answer 5

• An ordered set of values
• Cannot be changed once initialised
• Initialised with regular rather than square brackets

Question 6

Arrays

Answer 6

• An ordered set of elements, each of the same type.
• A 1D array is like a list.
• A 2D array is like a table.
• A 3D array is like a multi page spreadsheet.
• 2D arrays are searched first by the rows and then the columns.

Question 7

Linked Lists

Answer 7

• Dynamic data structure.
• Stores an ordered list.
• Contents need not be in contiguous data locations.
• Items are called nodes.
• Each node contains a data field and a link or pointer field.
• The data field contains the data itself.
• The pointer field contains the address of the next item.

Question 8

Graphs

Answer 8

• Notes connected by edges or arcs.
• Directed graphs allow edges to be traversed in one direction only.
• Undirected graphs allow edges to be traversed in both directions.
• Weighted graphs attach a cost to each arc.
• Implemented using an adjacency list or adjacency matrix.
• Adjacency matrix - easy to add nodes and to work with.
• Adjacency list - space efficient.

Question 9

Stacks

Answer 9

• Last in first out
• Items can only be added or removed from the top
• Used for back or undo buttons
• Can be dynamic or static structure

Question 10

Queues

Answer 10

• First in first out data structure
• Items are added at the beginning and removed at the end
• Used in printers and keyboards
• Linear queue with items added into the next space
• Space inefficient
• Uses pointers at the front and back
• Circular queues have a rear pointer that can loop back to the beginning to use empty space.

Question 11

Stacks operations

Answer 11

• isEmpty() - Checks if the stack is empty
• push(value) - Adds a new value to the top of the stack
• peek() - Returns the top value of the stack
• pop() - Returns and removes the top value of the stack
• size() - Returns the size of the stack
• isFull() - Checks if the stack is full

Question 12

Queues operations

Answer 12

• enQueue(value) - Adds a new item at the end of the queue
• deQueue() - Removes the item at the end of the queue
• isEmpty() - Checks if the queue if empty
• isFull() - Checks if the queue is full

Question 13

Trees

Answer 13

• Connected graphs with root and child
  nodes.
• A node is an item in the tree.
• An edge connects two nodes together.
• A roof is a node with no incoming
  nodes.
• A child is a node with incoming edges.
• A parent is a node with outgoing edges.
• A subtree is a section of a tree
  consisting of a parent node with child
  nodes.
• A leaf is a node with no child nodes.

Question 14

Binary trees

Answer 14

• A binary tree is a tree where each node
  has two or fewer children.
• Binary trees store information in a way
  which is easy to search.
• They often store each node with a left
  and right pointer.

Question 15

Pre-order Traversal

Answer 15

1. Root node
2. Left subtree
3. Right subtree

Question 16

In-order Traversal

Answer 16

1. Left subtree
2. Root node
3. Right subtree

Question 17

Post-order Traversal

Answer 17

1. Left subtree
2. Right subtree
3. Root node