Topic 2:Data Structures

Question 1

The static implementation is less efficient at inserting new items into the list than the dynamic implementation.
Explain why this is the case.

Answer 1

-Not possible to simply insert item into middle of a list
-Must move all the items that come after the new process down in the array
-Moving items is time consuming/ in dynamic implementation, insertion is achieved by adjusting pointers

Question 2

Explain the differences between a static and data structure.

Answer 2

-Static data structures have storage determined at compile time whilst a dynamic structure can grow and shrink during run time
-Static data structure can waste storage space if the number of items stored are relatively smaller than the size of the structure whereas the dynamic only uses the storage space necessary
-Static data structure has fixed size where dynamic can change

Question 3

Explain two differences between a dynamic data structure and a static data structure.

Answer 3

-Static has a fixed size pre determined at compile time whilst a dynamic data structure grows and shrinks during run time
-Static structures waste space if the number of items stored are significantly smaller than the size of the structure
-Dynamic structure require memory to store pointers to the next item , static structures store data in consecutive memory locations

Question 4

Explain how a single stack can be used in the implementation of the repeat action and undo action

Answer 4

Stack is used to store the pointers actions.
Each time an action is completes it is pushed onto the top of the stack
Unless it is an undo action
When repeat action is used the top item from the stack is used to indicate the action to complete, when the repeat action is used the result of the peek function is used to indicate the action is complete
When undo action is used the top item is popped from the stack of actions

Question 5

State the type of error that occurs if the user tries to complete an undo action before they have completes any other action

Answer 5

Stack empty error// stack underflow

Question 6

Explain the situation where it is more appropriate to represent a graph using an adjacency list instead of an adjacency matrix

Answer 6

Adjacency list appropriate when there are few edges between vertices // when graph is sparse
When edges rarely change
When the presence/absence of specific edges does not need to be

Question 7

What is an array?

Answer 7

A data structure that can store the same data type contiguously in memory .
Has random access to all elements via it’s direct index

Question 8

What is a Linked lists

Answer 8

A data structure that can store data non contiguously in memory.
They are dynamic .

Question 9

What is the advantage of an array?

Answer 9

They allow random access to the elements

Question 10

What is a disadvantage of an array?

Answer 10

They are a static data structure with a fixed sized which is set at compile time

Question 11

What us a hash table?

Answer 11

An array that we call a hash table that is coupled in with a hash function. They compose of a primary key and a value(key value pairings).

Question 12

What is a collision?

Answer 12

A collision occurs when different inputs produces the same hash

Question 13

How can you avoid a collision?

Answer 13

Creating a larger hash table and using a different hash function

Question 14

How do you rehash a table?

Answer 14

A larger hash table is created
Each existing value in the table is inserted into the new table
This new position is determined by a new hashing algorithm

Question 15

Explain how a value is stored in a hash table

Answer 15

Hashing algorithm is applied to the key
The result is an index of where to store the value in the array
It is possible for a collision to occur when to keys provide the same hash
A collision handling method would be used and this could be using the next available memory location to store the value

Question 16

Why is hashing used?

Answer 16

So that searching, adding and deleting can be done efficiently
To speed up searching adding and deleting

Question 17

What is a dictionary?

Answer 17

A dictionary is an abstract general purpose data structure.
Used for storing groups of data
Has a set of keys
Each key has a single value associated with it
When the key is supplied the associated value is returned

Question 18

Pairs in a dictionary are held in any sort of order
True or Flase

Answer 18

False

Question 19

What is a stack?

Answer 19

A FILO abstract data structure (first in last out ). Based on an array. Which has a top pointer

Question 20

What operations are used in a stack data structure?

Answer 20

Pop- Remove element from the top of stack
Push-Add an item to the top of stack
Peek-Return the top value of the stack

Question 21

What is a queue?

Answer 21

This is an FIFO abstract data structure(FIFO). Which has a front and rear pointer

Question 22

What are the operations applied to a queue?

Answer 22

Enqueue- Add an item to the queue
Dequeue- Remove an item from the queue

Question 23

What is a tree?

Answer 23

A tree is an undirected, connected graph with no cycles

Question 24

What is a rooted tree?

Answer 24

A rooted tree is a tree in which one vertex has been designated as the root

Question 25

What are the advantages and disadvantages of the adjacency matrix?

Answer 25

-A:Time efficient(can be searched very easily)
-D:Memory inefficient(stores every possible edge)