Data Structures

Question 1

Define static data structures (e.g. arrays)

Answer 1

A static data structure has a fixed size so can waste or run out of space; fixed region of main memory so element can be directly accessed (by index number) as always in the same place.

Question 2

Define dynamic data structures (e.g. linked lists)

Answer 2

A dynamic data structure can grow; each index made up of data and point to the next index. Needs external point (start) to first index and the last index has a null pointer.

Question 3

Define a pointer in terms of data structures

Answer 3

A reference variable that contains a memory location.

Question 4

Define a heap in terms of data structures

Answer 4

Memory available to applications / programs for dynamic allocation at runtime.

Question 5

Define memory leakage in terms of data structures

Answer 5

Memory locations not returned to heap when no longer referenced.

Question 6

Define an abstract data type

Answer 6

A complex data type that exists in the real world.

Question 7

Define a stack as a data structure

Answer 7

A LIFO (Last in, First out) data structure. Needs 1 pointer at the top of stack. Used to store a functions data when another is called using a stack frame.

Question 8

Define the methods a stack should have

Answer 8

Push - Adding to a stack. 
Pop - Removes from a stack.
Peek - Allows top item to be viewed. 
IsEmpty - Check if the stack is empty.
IsFull - Check if the stack is full.

Question 9

Define a queue as a data structure

Answer 9

A FIFO (First in, First out) data structure. Needs a pointer at the head (start) and at the tail (end) of the queue. (Can be linear or circular).

Question 10

Define a priority queue as a data structure

Answer 10

Elements join after all others of same priority and / or before those of lower priority.

Question 11

Define a graph as a data structure

Answer 11

An ADT (Abstract data type) that is a set of nodes (vertices) and connections between them known as edges (arcs). Can be used to represent computer and social networks, maps, mazes etc. Can be directed and / or weighted.

Question 12

Suggest when to use an adjacency matrix to store a graphs data

Answer 12

if the number of edges are large compared to fewer nodes (makes it quicker to search).

Question 13

Suggest when to use an adjacency list to store a graphs data

Answer 13

if the number of edges / connections are fewer compared to more nodes.

Question 14

Define a tree in terms of data structures

Answer 14

A graph that is fully connected, undirected with no cycles

Question 15

Define a rooted tree in terms of data structures

Answer 15

A tree where one node (vertex) is designated as the root with every edge (arc) directed away from the root

Question 16

Define a binary tree in terms of data structures

Answer 16

A rooted tree where each parent has at most two children, efficient for searching and sorting.

Question 17

Define a hash table in terms of data structures

Answer 17

An ADT (Abstract data type) that is a table to store data efficiently.

Question 18

Define a hashing algorithm in terms of data structures

Answer 18

An algorithm that hashes a key into an index value that is used as the placement of the item in the hash table. A bad algorithm can cause collisions.

Question 19

Define a dictionary in terms of data structures

Answer 19

A collection of key/value pairs. Values are accessed via key.

Question 20

Define a vector in terms of data structures

Answer 20

A vector is a type of one dimensional array that instead of a normal array, it uses its own memory management mechanisms.