1.4.2 Data Structures

Question 1

Array

Answer 1

A static data structure used for storing a finite, ordered set of data of the same data type within a single identifier. They are contiguous.

Question 2

How to find a given position within a 2D/3D array

Answer 2

Use the reverse to the method used to find a set of coordinates.
EG: 3D [z,y,x]

Question 3

How can a 2D array be visualized as?

Answer 3

Table/spreadsheet

Question 4

How can a 3D array be visualised as?

Answer 4

Multi-page spreadsheet / multiple 2d arrays

Question 5

Record

Answer 5

A data structure that stores data in elements called fields, organised based on attributes.

Question 6

What is a List?

Answer 6

• A dynamic data structure that can store multiple values of different data types.
• They are mutable, meaning values can be changed or replaced.
• List values are stored non-contiguously.

Question 7

Tuple

Answer 7

A data structure for storing an immutable, ordered set of data, which can be of different data types, within a single identifier.

Question 8

Linked list

Answer 8

• A dynamic data structure consisting of an ordered sequence of nodes.
• Each node has a data field and pointer field.
• Each pointer points to the next node in the sequence.
• They are non-contiguous.

Question 9

Name the pointers used by linked lists.

Answer 9

Start Pointer
Free Pointer

Question 10

What is the procedure for adding an item to a linked list.

Answer 10

Add the new value to the end of the linked list, and update the free pointer.
Update the node that currently has a null pointer to point to the new item.
Update the pointer of the new item to have a null pointer.

Question 11

What is the procedure for removing an item from a linked list.

Answer 11

The pointer in the previous item changes to the pointer held by the item that is to be removed, effectively bypassing the removed item.

Question 12

Disadvantages of linked list

Answer 12

• Removing nodes from a linked list does not truly remove it. This wastes memory.
• Storing pointers also means more memory is required compared to an array.
• As items in linked lists are stored in a sequence, they can only be traversed in this order. This means they cannot be directly accessed, as is possible in an array.

Question 13

Graph

Answer 13

A dynamic data structure. It is a collection of data nodes (known as vertices), connected by edges.

Question 14

Describe the three categories of graph.

Answer 14

Directed: Edges can only be traversed in one direction
Undirected: Edges can be traversed in both directions
Weighted: A cost is attached to each edge.

Question 15

What are the two ways of traversing a graph?

Answer 15

Breadth-first (using queue)
Depth-first (using stack)

Question 16

Stack

Answer 16

A LIFO data structure, meaning items are added to the top and removed from the top.
They have a pointer which points to the top of the stack, where the next piece of data can be added.

Question 17

Name some operations you can perform with a stack.

Answer 17

Push
Pop
isFull
isEmpty
peek
size

Question 18

Queue

Answer 18

A FIFO data structure, meaning items are added to the end of the queue and removed from the front.
It uses a front and back pointer to show the item that can be removed and the item that can be added.

Question 19

Name some operations you can perform with a queue

Answer 19

enQueue
deQueue
isEmpty
isFull

Question 20

What is the difference between circular and linear queues?

Answer 20

Once the queue’s rear pointer is equal to the queue’s max size, it loops back to the front of the array and stores values there (provided it is empty).

Question 21

Pros/Cons of circular queue

Answer 21

Uses space in an array more effectively.
Harder to implement.

Question 22

Why are linear queues ineffective compared to circular queues.?

Answer 22

Linear queues implemented using an array can become ineffective over time as dequeued elements leave unused spaces in the array, while circular queues are more efficient as they wrap around and reuse the array space as elements are dequeued.

Question 23

Tree

Answer 23

• A dynamic data structure that branches.
• It has a root node at the top, and other nodes arranged in levels beneath it.
• Each node in a tree can have zero or more child nodes, which are connected to it by edges/branches.

Question 24

Edge/Branch

Answer 24

Connects two nodes togetherq

Question 25

Root

Answer 25

Single node which does not have incoming nodes

Question 26

Child

Answer 26

Node with incoming edges

Question 27

Parent

Answer 27

Node with outgoing edges

Question 28

Subtree

Answer 28

Subsection of a tree consisting of a parent and all the children of a parent.

Question 29

Leaf

Answer 29

Node with no children.

Question 30

Binary Tree

Answer 30

A type of tree where each node has a maximum of two children.

Question 31

How are binary trees commonly implemented?

Answer 31

A 2D array holding the left pointer, data value and right pointer.

Question 32

Why use binary trees?

Answer 32

To represent info for binary searches

Question 33

What are the three methods for traversing a binary tree? What is an easy method that covers all of these?

Answer 33

Pre-order, In-order, Post-order. Use the outline method (draw around the tree starting from left side)

Question 34

Pre-order (binary tree)

Answer 34

Order: Root node, left subtree, right subtree.

Question 35

In-order (binary tree)

Answer 35

Order: Left subtree, rootnode, right subtree

Question 36

Post-order (binary tree)

Answer 36

Order: Left subtree, right subtree, root node.

Question 37

What two data structures allow random access to elements?

Answer 37

Array (via direct index) Hash table

Question 38

What is a hash table?

Answer 38

- A dynamic data structure. - Data is stored in a table. - A mapping function uses the data that is going to be entered into the table to generate the location in the table where the data should be stored.

Question 39

What is a simple way of dealing with collisions in a hash table? Whats the problem with this?

Answer 39

The data can be stored in the next available space. However, this further increases the likelyhood of collisions (clustering).

Question 40

What makes a hashing algorithm good?

Answer 40

If it has a low probability of collisions occuring.

Question 41

What are hash tables normally used for?

Answer 41

Indexing, as they provide fast access to data.

Question 42

How are linked lists used in hash tables to solve the problem of collisions and clustering?

Answer 42

- A technique called separate chaining is used. - The original table is used to store an overflow linked list for the index where a collision occurs. - This means when a collision occurs, a new node can be created in the linked list to hold the new data.

Question 43

Whats a simple hash function?

Answer 43

(k*k) MOD m k: key value m: a prime number close to the required num of locations.

Question 44

What is one way of using non-numeric fields for key values?

Answer 44

Use the ASCII values of the characters to create a numeric value, then use a suitable hashing function.