1.4.2 Data structures

Question 1

Describe a primitive data type

Answer 1

A data type which is assigned to a variable used to hold a single piece of data

Question 2

Describe a composite or compound data type

Answer 2

A data type which is assigned to a variable used to hold multiple related pieces of data

Question 3

Describe an abstract data type

Answer 3

A conceptual model that describes how data is stored and which operations can be carried out on them

Question 4

Describe what a data structure is

Answer 4

The implementation of an abstract data type in a program

Question 5

Explain what a static data structure is

Answer 5

A set amount of memory locations / size to store data

Question 6

Explain what a dynamic data structure is

Answer 6

Can group data, while also being able to grow in size

Question 7

What is an array data structure?

Answer 7

A data type that holds data that are usually related. It has a fixed size that cannot be changed during running.

Question 8

What is a tuple data structure?

Answer 8

A data structure that cannot mutate, which contains multiple constants

Question 9

Describe a list data structure

Answer 9

A dynamic array

Question 10

Describe a record data structure

Answer 10

A data structure which allows you to make your own data type consisting of different fields

Question 11

Describe a linked list data structure

Answer 11

A list data structure which stores data in the next free space, and links them together with pointers

Question 12

What is a node, for a linked list, and what does it contain?

Answer 12

An individual element of the linked list

Contains the data item and the next address location

Question 13

What are some advantages of a linked list?

Answer 13

• Flexible structure - pointers can be changed to shape the ordering system
• Can easily remove nodes, as very few pointers need to be changed

Question 14

What are some disadvantages of a linked list?

Answer 14

• Slow to check through as it must be started at the beginning and then worked through
• Hard to update with new nodes, as all previous nodes have to be checked and pointers moved to add the new item
• Hard to find a specific item, as every node has to be gone through to find it
• More storage space is required since the pointers also have to be stored

Question 15

Describe a linear queue data structure

Answer 15

FIFO. Pointers point to the start of the queue where items are removed, and to the end where items are added

Question 16

Describe a circular queue data structure

Answer 16

Functions the same as a linear queue, except it reuses the empty spaces at the front of the queue

Question 17

What is the advantage of a circular queue over a linear queue?

Answer 17

After elements are removed, the circular queue can reuse the space left behind

Question 18

Describe a priority queue structure

Answer 18

Each element has a priority value alongside the data, and it is all stored in priority order. This is similar to an ordered linked list.

A new element is added according to its priority value, and the highest priority element is removed first

Question 19

Describe a stack data structure

Answer 19

LIFO. The last item to be added to the stack is the first item to be removed.

Question 20

What is the purpose of the peek() operation?

Answer 20

Returns the item at the top of a stack without removing it

Question 21

What is the purpose of the push() operation?

Answer 21

Adds an element to the top of the stack

Question 22

What is the purpose of the pop() operation?

Answer 22

Removes an element from the top of a stack

Question 23

Describe a tree data structure

Answer 23

A hierarchical structure of data, stored as nodes, with parent nodes branching into children nodes.

Question 24

Define a node in a tree data structure

Answer 24

A unit for data, containing: a sub-tree pointer, the node’s data, and pointers to other nodes on the same level

Question 25

Define a parent and child for a tree data structure

Answer 25

Parent: the predecessor node to branching nodes Child: a node branching from a predeceasing node

Question 26

Describe a binary search tree data structure

Answer 26

A dynamic data structure, which can change size during program running. It can have **only** 0, 1 or 2 branches from each node

Question 27

What is an advantage of binary search trees over standard root search trees?

Answer 27

Binary trees take a shorter time to search for a particular item than a rooted tree

Question 28

What are the 3 methods of traversing a binary tree?

Answer 28

Preorder traversal Inorder traversal Postorder traversal

Question 29

What are the features of a preorder traversal?

Answer 29

Is a 'top down' method Can be used to duplicate the data to create an identical binary tree

Question 30

Describe a preorder traversal

Answer 30

Pointers are to the left of the node * Root visited first * Traverses left sub-tree * Traverses right sub-tree

Question 31

What are the features of an inorder traversal?

Answer 31

Outputs the data in ascending order

Question 32

Describe an inorder traversal

Answer 32

Pointers below the nodes * Traverses the left sub-tree * Visits the root * Traverses the right sub-tree

Question 33

What are the features of a postorder traversal?

Answer 33

A 'bottom up' method Used if data needs to be deleted from the tree

Question 34

Describe a postorder traversal

Answer 34

Pointers to the right of the node * Traverses left sub-tree * Traverses right sub-tree * Visits the root

Question 35

What is a hash table?

Answer 35

An array structure with an associated hash function

Question 36

What is the process of hashing?

Answer 36

When the data being stored (the key) is inserted into the hashing function and a hash value is output The hash value relates to a specific location in the hash table

Question 37

What are two applications of hashing?

Answer 37

Speeding up data retrieval Checking validity of data

Question 38

How would you search for a particular record in a hash table?

Answer 38

The record would be inserted into the hashing function, and then the output is the location in which you need to search

Question 39

How is hashing used to check the validity of data?

Answer 39

If data is sent to a new location, the hash value is sent too Once the data arrives, the hash function is carried out again, and if the new and old hash values don't match, then the data is invalid

Question 40

What is the advantage of a hash table when locating a record in a file?

Answer 40

Using the hash function means there will be only one location outputted that needs to be searched

Question 41

What are 3 features of a good hash algorithm?

Answer 41

* Generates a uniform spread of unique indexes to avoid collisions * Produces hash values quickly, thus being fast * Is complex, thus reducing the chance of collisions, with unique hash values

Question 42

What is a collision in the context of hashing?

Answer 42

A collision occurs when the hash function produces the same hash value for different keys, thus giving the same memory location in the hash table to both keys

Question 43

What are two methods of dealing with collisions in the context of hashing?

Answer 43

Open addressing (closed hashing): inserts a colliding key into the next available memory location, known as rehashing Closed addressing (open hashing): apply a linked list to a memory location where a collision occurs. This is an overflow list, which holds all subsequent keys which collide with the data already stored in this location

Question 44

What are some uses of hashing?

Answer 44

Searching a database: can quickly find data in a database Sending files: used to validate the data sent Storing passwords safely: hashes the user's password before storing it

Question 45

Describe the structure of a graph

Answer 45

A graph is composed of multiple vertices, each connected to others by edges

Question 46

Describe the difference between a directed and undirected graph

Answer 46

Directed graph: the edges have a direction, the way of travel Undirected graph: no specific direction on an edge

Question 47

Describe the difference between a weighted and unweighted graph

Answer 47

Weighted: has weights/costs marked on each edge Unweighted: has no additional edge values

Question 48

How can an adjacency matrix be used to store a graph?

Answer 48

Question 49

How can a list be used to store a graph?

Answer 49

Question 50

How can a dictionary be used to store a graph?

Answer 50

Question 51

How can ordered pairs be used to store a graph?

Answer 51