Fundamentals of Data Structure

Question 1

Abstract Data Type

Answer 1

A conceptual model of how the data is stored and the operations that were performed upon them.

Question 2

Static Data Structure

Answer 2

A method of storing data where the amount of data stored (and memory used to store it) is fixed.

Question 3

Dynamic Data Structure

Answer 3

A method of storing data where the amount of data stored (and memory used to store it) will vary as the program is being run.

Question 4

Stack

Answer 4

A stack is an example of LIFO

A stack in a computer works exactly as a stack of books waiting to be marked - whichever item was added to the top is the first to be dealt with. However, data dealt with is NOT removed from the stack. What happens is that a variable called the stack pointer keeps track of where the top of the stack is.

Data is ‘pushed’ onto the stack or is ‘popped’ from the stack.

Question 5

Stack Frame

Answer 5

A collection of data about a subroutine call

Question 6

Call Stack

Answer 6

A special type of stack used to store information about active subroutines and functions within a program

Question 7

Recursion

Answer 7

The process of a subroutine calling itself

Question 8

Stack Pointer

Answer 8

A small register that stores the address of the last program request in a stack.

Question 9

Queue

Answer 9

A queue is an example of FIFO

FIFO - First in First out (where the first data item is first to leave)

A common use for queues is when sending a document to the printer.

Question 10

Linear Queue

Answer 10

http://image.ibb.co/dgKP0y/20180603_155036.jpg

Question 11

Circular Queue

Answer 11

http://image.ibb.co/kO8j0y/20180603_155042.jpg
A common implementation for Circular Queue is for buffering, when items of data need to be stored temporarily while they are waiting to be passed to/from the device.

Question 12

Priority Queues

Answer 12

A variation of a FIFO structure where some data may leave out of sequence where it has a higher priority than other data items.

Example: If documents are being sent to a printer on a network, the administrator may be able to control the queue.

Question 13

Graph

Answer 13

A mathematical structure that models the relationship between pairs of objects.

A tree is similar to a graph, but with no loops.

Question 14

Arc/Edge

Answer 14

Join/show relationship between 2 nodes

Question 15

Vertex/Vertices

Answer 15

An object in a graph - also known as a node

Question 16

Weighted Graph

Answer 16

A graph with data values on each arc/edge

Question 17

Graph/Weighted graph/Undirected Graph/Directed Graph

Draw examples of each one.

Answer 17

http://image.ibb.co/b7ksnd/20180603_155953.jpg

Question 18

Adjacency List

Answer 18

A data structure that stores a list of nodes with their adjacent nodes.

http: //image.ibb.co/exjP0y/20180603_160223.jpg
http: //image.ibb.co/dRD3Sd/20180603_160343.jpg

Question 19

Adjacency Matrix

Answer 19

This uses a two-dimensional array or grid populated with 1s and 0s

http: //image.ibb.co/hNigDJ/20180603_160355.jpg
http: //image.ibb.co/jLOWDJ/20180603_160359.jpg

Question 20

Binary Tree

Answer 20

A tree where each node can only have up to two child nodes attached to it.

Question 21

Hashing Algorithm

Answer 21

Code that creates a unique index from given items of key data

Question 22

Hash Table

Answer 22

A data structure that stores key/value pairs based on an index calculated from an algorithm

Question 23

Uses of hashing algorithms

Answer 23

Databases - Used to create indices for databases enabling quick storage and retrieval of data (more efficient than linear for example)

Memory addressing - Used to generate memory addresses where data will be stored

Question 24

Collision

Answer 24

When a hashing algorithm produces the same index for two or more different keys

Question 25

Clustering

Answer 25

When a hashing algorithm produces indices that are not randomly distributed.

Question 26

Index

Answer 26

The location where values will be stored, calculated from the key. When collision occurs, there must be some way of handling it so that a unique index can be assigned to the key: Chaining - adding the key/value to a list stored at the same index. Rehashing - The process of running the hashing algorithm again when a collision occurs. This normally uses a technique called probing, which means that the algorithm probes or searches for an empty slot, and uses it.

Question 27

Dictionary (Data Structure)

Answer 27

An abstract data type that maps keys to data. It is called an associative array in that it deals with two sets of data that are associated with each other. eg http://images.slideplayer.com/16/4911256/slides/slide_3.jpg

Question 28

Representing vector as a data structure

Answer 28

eg fibonacci[0] = 0; fibonacci[1] = 1; fibonacci[2] = 1 in a dictionary, would be represented as {0:0, 1:1, 2:1}

Question 29

Vector Addition

Answer 29

``` A = (A1, A2, A3) B = (B1, B2, B3) ``` A + B = (A1+B1, A2+B2, A3+B3)

Question 30

Dot Product

Answer 30

``` A = (3,5) B = (7,2) ``` A.B = 3*7+5*2 = 31

Question 31

Convex Combinations

Answer 31

``` The convex combinations is inbetween the two vectors. It is calculated as au+Bv Where u and v are vectors a+B = 1 a and B must be 0 or greater ``` https://www.youtube.com/watch?v=6N_caSzNpkc