Data structure

Question 1

array

Answer 1

An array allows you to store multiple items of the same data type under a shared common name.

Question 2

Arrays can store data of the same data type contiguously in memory. This means…

Answer 2

… random access to all element is available via its direct index.

Question 3

Limitations of arrays:

Answer 3

A
They can only store one data type
- They’re a static data structure (their scope is predetermined)

Question 4

record

Answer 4

an unordered data structure which is accessed through an attribute. It can store many different data types

Question 5

What are pythons versions of arrays?

Answer 5

Lists and tuples

Question 6

Tuples

Answer 6

Tuples are lists that cannot be edited and is said to be immutable.

Question 7

immutable

Answer 7

structure and data cannot be changed at run time.

Question 8

mutable

Answer 8

structure and data can be changed at run time.

Question 9

Static data structure

Answer 9

size of the structure cannot change at run time

Question 10

Dynamic data structure

Answer 10

size of the structure can change at run time.

Question 11

Stack data structure

Answer 11

A stack is known as a LIFO, a single pointer is used to point to the top item of the stack, when a new item is pushed onto the stack the pointer is incremented. When an item is popped off the stack the pointer decrements to point to the new top of the stack.

Question 12

LIFO

Answer 12

last in first out - the last item you push to the top of the list is the first item you pop off the stack.

Question 13

Queue data structure

Answer 13

A queue is known as a FIFO structure. A pair of pointers is used to point to the front and back of the queue. If an item is popped from the queue the front pointer points to the item being popped. If an item is pushed onto a queue the tail pointer increments by one and points to the new end of queue.

Question 14

FIFO

Answer 14

first in first out - because the new items get pushed to the back of the queue and new items get popped from the front of the queue.

Question 15

Algorithm for insertion into a stack:

Answer 15

1)Check to see if the stack is full
If the stack is full report error
and stop
2)Increment the stack pointer
Insert new data item into
location pointed to by the
stack pointer and stop

Question 16

Algorithm for deletion/fetching from a stack:

Answer 16

1)Check to see if the stack is empty

2)If the stack is empty report an error and stop

3)Copy the data item in location pointed to by the stack pointer/ delete the data item
Decrement the stack pointer

Question 17

Algorithm for insertion into a queue:

Answer 17

1)Check to see is the queue is full

2)If the queue is full report an error ad stop

3)Insert new data item into location pointed to by the head pointer

4)Increment the head pointer and stop

Question 19

LIFO

Answer 19

last in first out - the last item you push to the top of the list is the first item you pop off the stack.

Question 20

Queue data structure

Answer 20

A queue is known as a FIFO structure. A pair of pointers is used to point to the front and back of the queue. If an item is popped from the queue the front pointer points to the item being popped. If an item is pushed onto a queue the tail pointer increments by one and points to the new end of queue.

Question 21

FIFO

Answer 21

first in first out - because the new items get pushed to the back of the queue and new items get popped from the front of the queue.

Question 22

Algorithm for insertion into a stack:

Answer 22

Check to see if the stack is full

If the stack is full report error and stop

Increment the stack pointer

Insert new data item into location pointed to by the stack pointer and stop

Question 23

Algorithm for deletion/fetching from a stack:

Answer 23

Check to see if the stack is empty

If the stack is empty report an error and stop

Copy the data item in location pointed to by the stack pointer/ delete the data item
Decrement the stack pointer

Question 24

Algorithm for insertion into a queue:

Answer 24

Check to see is the queue is full

If the queue is full report an error ad stop

Insert new data item into location pointed to by the head pointer

Increment the head pointer and stop

Question 25

Algorithm for deletion/fetching from a queue:

Answer 25

Check to see if the queue is empty

If the queue is empty report an error and stop

Copy data item in location pointed to by the tail pointer/ delete the data item
Increment tail pointer and stop

Question 26

linked lists

Answer 26

A list of data together with a set of links to sort the data. Data is stored in the order its input and pointers are used to link the data into the desired order

Question 27

uses of linked lists

Answer 27

Implementing undo functionality
Dealing with browser cache
Helping with operating system job queues

Question 28

Adding data from linked lists

Answer 28

Store the data at the location indicated by the free storage pointer

Alter the free storage pointer to the next free storage space

Set the pointer for the item that will precede it to the new data item

Update the pointer for the new data item to that previously stored in the item the preceded it (i.e. the next data item)

Question 29

Traversing data from linked lists

Answer 29

Set the pointer to the start value
Repeat:
a. Go to the node
b. Output the data at the node
c. Set the pointer to the value of the next item pointer at the pointer
d. until pointer = 0/null

Question 30

Removing data from linked lists

Answer 30

If the item to remove is in the first position
a. Then update starting pointer value of item you want to delete and update all the pointers
Else if the item is in any other position
a. Update the pointer value in the preceding node from the one you want to delete to the value of the pointer in the item to be removed and all the succeeding data items pointers
Update the free storage

Question 31

Searching for an item in a linked list

Answer 31

Set the pointer to the start value
Repeat:
a. Go to node (pointer value)
b. If the data at the node is the search item
i. Then Output the data and stop
c. Else
i. Set the pointer to the value of the next item pointer at the node
d. Until pointer = 0
Output data not found

Question 32

Benefits of Hash tables

Answer 32

Speed of lookup, deletion and insertion of items is fast

Question 33

hash table

Answer 33

an array which is coupled together with a hash function. The value from the hash function (hash value) maps the initial key to a fixed index in the hash table

Question 34

collision

Answer 34

the same hash value is given by two different keys.

Question 35

collision solution

Answer 35

Storing the key in the next available space
- adding a linked list to the location where the hash value is repeated

Question 36

clustering

Answer 36

when there is a collision and the key is stored in the next available space increasing the likelihood of collisions