Week 5

Question 1

What are the two types of file systems?

Answer 1

Contiguous and Fragmented.

Question 2

What is the difference between parallel and concurrent execution?

Answer 2

In parallel, one core handles one task.

In concurrent, the cores will switch between the tasks.

Question 3

What are lists classified as?

Answer 3

A list is classfied as a linear data structure.

May be one dimenionsal or multidimensional.

Could be ordered or not.

Question 4

What can an element of a list consist of?

Answer 4

A single data item or a record or object (compound data)

Question 5

True for false, a list is an abstract data type.

Answer 5

This is true.

Question 6

What are some ways that lists may be implemented?

Answer 6

It can be implemented in arrays or linked lists, or it can be done in RAM or secondary storage.

Question 7

True or false, are arrays physically ordered lists?

Answer 7

Yes, arrays are also called physically ordered lists.

Question 8

What is the definition of an array?

Answer 8

They are linear random access data structures whose elements are accessed by unique identifiers called an index or subscript.

Elements are stored contiguously in RAM or in secondary storage.

Question 9

In languages like C, C++ and Java where does the index start at?

Answer 9

It starts at 0.

languages like Pascal and FORTRAN are more flexible.

Question 10

In compiled languages, arrays have a fixed…

Answer 10

Set at compile time for compiled languages. Some languages enforce this, but some languages are more flexible.

Note that typically the compiler actually adds slightly more memory just in case small changes are needed to be made inplace.

Question 11

What is the difference between size and capacity?

Answer 11

Size is the amount of elements in the array.

The capacity is slighty bigger than the size so changes can be easily made.

If capacity wasn’t slightly bigger it would need to move. We reduce the chances of this operation since this change can be costly.

Question 12

What is a dynamic array?

Answer 12

In interpreted languages like python and javascript arrays are dynamic.

We can add elements beyond the end of the array. The interpreter resizes the array and reallocates if neeeded.

Question 13

What do we need to keep in mind if we are inserting a value in the middle.

Answer 13

If you have enough space, you can simply shift everything.

If you don’t have enough space, you need to reallocate it to another space in memory.

Inserting an array in the middle can be quite expensive.

Question 14

What is the worst case scenario for inserting in an array.

Answer 14

O(n) is the worst case (Inserting at position 0)

The best case is constant.

Question 15

What is the worst case complexity for deletion.

Answer 15

The worst case for deletion is O(n).

Question 16

What is a grow factor? What is python’s grow factor?

Answer 16

A grow factor is 1.125.

A grow factor is when an array allocates more memory than needed so that it can quickly use it. For example growing an array.

The tradeoff between performance and memory efficiency.

Question 17

What are the advantages and disadvantages of arrays?

Answer 17

Advantages are they are simple to use. Retrievals and replacements are quick if the index is known O(1).

Disadvantages are adding and removing elements are awkward. Dynamic sized arrays require copying. Fixed size arrays either limits the size of the list or wastes space.

Question 18

How are arrays stored in memory?

Answer 18

Arrays are stored contiguously in memory. This means one after the other.

Question 19

What is the definition of a linked list?

Answer 19

A linear data structure that consists of zero or more nodes where each node contains data and a pointer to the next node.

Question 20

What is the advantages and disadvantages to linked lists?

Answer 20

They are easily resizable, they are non-contiguous.

But they are no longer indexable. You need to start from the beginning.

Question 21

What does a node consist of?

Answer 21

The data and a reference to a node type.

Question 22

Is it possible to have private members in python?

Answer 22

No. Data members cannot be private in python.

We use the notation of a _ to indicate if they are supposed to be private.

Question 23

What are some of the types of linked lists?

Answer 23

Singly Linked List: Unidirectional.

Doubly Linked List: Bidirectional

Circular Linked List: Unidirectional closed loop.

Circular Doubly Linked List: Bidirectional closed loop.

Question 24

What is the wost case for inserting in an array?

Answer 24

The worst case for inserting in an array is at position 0, since all the other values need to move as well.

Question 25

What is the worst case for inserting in a linked list?

Answer 25

The worst case for inserting in a linked list is at the end.

Question 26

When traversing a linked list what do we have to make sure we do?

Answer 26

Make sure you have a temporary variable.

Question 27

What does the garbage collector do in python?

Answer 27

The garbage collector will collect anything that is no longer referred to.

Question 28

Is it possible to delete from an empty list?

Answer 28

No, this will cause issues.

Question 29

What is the complexity for insertion and deletion in a linked list once the position is known?

Answer 29

The complexity is O(1).

Question 30

What is the complexity in a linked list in the average and worst case.

Answer 30

The complexity is O(n).

Question 31

In a linked list, what is the complexity for adding a head or tail pointer?

Answer 31

The complexity os O(1).

Question 32

What is the complexity for getting an entry at position other than the head.

Answer 32

O(n).