4.2.1.4 Abstract data types/data structures

Question 1

What is a static data structure

Answer 1

Static - collection of data in memory that is fixed in size, for storing a well-defined number of data items. Stores its elements in adjacent locations, in a particular order in main memory. When an array is declared the compiler reserves the space for the array elements so that there’s space to store it. To delete an element every element after it must be moved up, which is time-consuming

Question 2

What are the differences between static and dynamic data structures?

Answer 2

Static structures have fixed maximum sizes, which means they can waste memory, but there will be no problem with adding and removing data items.
Dynamic data structures only take up the amount of space they require, making it more efficient. Dynamic structures need memory to store pointers to the next item, static structures don’t. it is possible for the structure to ‘overflow’ should it exceed its allowed limit. It can also ‘underflow’ should it become empty. the software needs to keep track of its size and data item locations at all times

Question 3

What is a queue and how do they work?

Answer 3

a first-in first-out (FIFO) abstract data type, which uses pointers. Elements join at one end and leave the queue at the other end. The front and end pointers can only move forwards and sooner or later would reach the end of the allotted memory - at this point, no more items could be added to the queue.
used when you want things to happen in the order that they were called, e.g operating system, printers

Question 4

What is a stack and how do they work?

Answer 4

Last-in first-out (LIFO) data type; when an object is added to a stack, it is placed on the top of all previously entered items. if a stack runs out of memory, it will cause a “stack overflow.” If not handled correctly by the program, a stack overflow may generate an error message or cause the program to crash.
Used for recursion, parameter passing and local variable storage

Question 5

What is a tree?

Answer 5

A connected undirected graph with no cycles. Connected means that every node is connected to at least one other node. Undirected means there is no direction associated with an edge, i.e. lines are used, not arrows. A cycle is a circuit (a succession of edges that start and end at the same vertex) in which all the edges are different and all the vertices visited are different
e.g file system on a computer, searching through data

Question 6

What is a hash table?

Answer 6

When we want to retrieve one record from many in a file, searching the file for the required record takes time that varies with the number of records. If we can generate a hash for the record’s key, we can use that hash value as the “address” of the record and move directly to it; this takes the same time regardless of the number of records in the file, so every piece of data can be stored in a hash table (array)

Question 7

What is a vector?

Answer 7

one dimensional array, dynamic data structure that stores direction and magnitude of a line

Question 8

What is a priority queue?

Answer 8

Some items have higher priority which go to the front or behind the last high priority item.

Question 9

What is a dynamic data structure?

Answer 9

Dynamic - the amount of memory taken up by the data type can vary as the size of the structure can change. Linked lists can have elements stored in any memory location where there is space that are linked by storing pointers. Memory space is allocated for the list when required at run time from a pool of memory locations called a heap, known as dynamic allocation. The memory space is returned to the heap, if this doesn’t happen it may cause memory leakage, because the memory is being taken for no reason

Question 10

What is a shuffle queue?

Answer 10

A shuffle queue is where when something leaves the queue everyone moves one forward, which means a front pointer wouldn’t need as the front would always be position one

Question 11

What is a circular queue?

Answer 11

A circular queue uses a front and rear pointer. The next element to join the queue reuses the vacated location at the beginning of the array. They reuse memory space, meaning they won’t overwrite data or run out of memory (within limits), but they involve storing pointers as well as data, taking up more space than linear queues, Limited by the amount of data available in the buffer (array)

Question 12

If the list were to be implemented as a dynamic data structure, explain what the heap would be used for

Answer 12

Heap is pool of free/unused/available memory;

Memory allocated/de-allocated at run-time (to dynamic data structure);