Section 7: Data structures

Question 1

When searching for a value in a 2-D array table, would you start with columns or rows?

Answer 1

In a 2-D array table you start your search along the rows.

Question 2

How does a tuple differ from an array?

Answer 2

Unlike an array, a tuple can have different data types. However, a tuple is immutable i.e. its elements can’t be changed.

Question 3

What is a record?

Answer 3

A record is a way of storing data from a program permanently. It stores values in columns as a table.

Question 4

What is an abstract data type?

Answer 4

An abstract data type is a data type that is created by the programmer rather than embedded in the language itself.

Question 5

What are some examples of abstract data types?

Answer 5

Examples include queues, stacks, trees and graphs.

Question 6

What is the basic dynamic of a queue?

Answer 6

The basic dynamic of a queue is First in First out.

Question 7

Where can queues be used?

Answer 7

Examples of uses for queues:

• Keyboard
• Simulation e.g. simulating customers at a checkout
• Outputs waiting to be printed (stored as a queue on the disk)

Question 8

What is a dynamic data structure?

Answer 8

A dynamic data structure refers to a collection of data in the memory that has the ability to shrink or grow in size.

Question 9

What is heap?

Answer 9

Heap is a portion of memory from which space is allocated or de-allocated.

Question 10

What is a static data structure?

Answer 10

A static data structure refers to a data structure that is fixed in size, meaning it cannot increase or decrease its memory allocation while the program is running.

Question 11

What is a linked list?

Answer 11

A linked list is a dynamic data structure used to hold ordered data that may not be held in contiguous memory locations.

Question 12

What is a stack?

Answer 12

A stack is a Last in First out data structure.

Question 13

What are the main areas that a stack will be used?

Answer 13

A major use of stacks is to store information about the active subroutines while a program is running. This includes holding return addresses, parameters and local variables.

Question 14

Is a stack a dynamic or static data structure?

Answer 14

A stack can be implemented as EITHER a dynamic data structure or a static data structure, depending on the preference of the programmer and the context in which it is being implemented.

Question 15

What does the “peek()” operation do when applied to a stack?

Answer 15

The “peek()” operation returns the item at the top of the stack, but does not remove it from the stack.

Question 16

How does a hash table work?

Answer 16

In a hash table, a hashing algorithm is applied to the value that requires storage, which transforms the value into an address in which the value itself will be held.

Question 17

How is an item searched for in a hash table?

Answer 17

Hash table search:

• Hashing algorithm is applied to the inputted value
• Examines the resulting memory address
• If the item is there, return the item. If the address is empty, the item is not there. If there is another value there, check the neighboring addresses.

Question 18

What is the “folding method” hashing algorithm?

Answer 18

The folding method divides the item into equal parts, and adds the parts to give the hash value. E.g. the phone number 01543677896 can be written as 01, 54, 36, 77, 89, 6 which add together to make 263.

Question 19

How can a string be hashed?

Answer 19

A string can be hashed by converting it to its ASCII value and then taking the modulus depending on how many spaces you have in your hash table.

Question 20

How can you minimise collisions in a hash table?

Answer 20

Firstly, you can take collision resolution into account when designing the hash table in a way in which only 70% of the table’s cells would be occupied when the table is full. You could also tailor the rehashing algorithm towards the particular data set that you’re using in order to make the best use of the space that you have in your hash table.

Question 21

Where might a hash table be used?

Answer 21

Uses for a hash table:

• Storing phone numbers
• Storing customer ID codes
• Storing encrypted passwords

Question 22

What is a node in a tree?

Answer 22

A node is a part of the tree that contains data.

Question 23

What is a branch/edge in a tree?

Answer 23

A branch/edge in a tree is the part of the tree that connects two nodes.

Question 24

What is the root of a tree?

Answer 24

The root of a tree is the only node that has no incoming edges.

Question 25

What is a child in a tree?

Answer 25

A child in a tree is technically any node with an incoming edge, but is only referred to as a child in relation to its parent.

Question 26

What is a parent in a tree?

Answer 26

A parent in a tree is a node that has outgoing nodes.

Question 27

What is a subtree?

Answer 27

A substree is the set of nodes and edges comprised of a parent and all descendants of the parent (it may also be a leaf)

Question 28

What is a leaf node in a tree?

Answer 28

A leaf node is a node that has no children.

Question 29

What is a binary tree?

Answer 29

A binary tree is a rooted tree in which each node has a maximum of two children.

Question 30

How do you draw a pre-order traversal?

Answer 30

A pre-order traversal is drawn by drawing an outline of the tree, starting to the left of the root node. Each time you pass the left of a node, the data in that node would be outputted.

Question 31

How do you draw an in-order traversal?

Answer 31

An in-order traversal is drawn by drawing an outline of the tree, starting to the left of the root node. Each time you pass the bottom of a node, the data in that node would be outputted.

Question 32

How do you draw a post-order traversal?

Answer 32

A post-order traversal is drawn by drawing an outline of the tree, starting to the left of the root node. Each time you pass the right of a node, the data in that node would be outputted.

Question 33

In words, how is a post-order traversal implemented as an algorithm?

Answer 33

Post-order traversal algorithm:

• Traverse the left subtree
• Traverse the right subtree
• Visit the root node

Question 34

In words, how is a pre-order traversal implemented as an algorithm?

Answer 34

Pre-order traversal algorithm:

• Visit the root node
• Traverse the left subtree
• Traverse the right subtree