# Fundamentals of Data Structures

5.0 / 5 based on 2 ratings

- Created by: Suicidal_Kitten
- Created on: 25-04-18 11:48

Static Data Structure

The amount of data stored and the memory allocated is of a fixed amount

1 of 36

Dynamic Data Structure

The amount of data stored and the memory allocated will vary during runtime

2 of 36

Stack

First-in Last-out data structure

3 of 36

What are the uses of a stack?

1. Reversing List contents. 2. Handling interrupts. 3. Nesting and recursion

4 of 36

Stack Overflow

Occurs when more items are pushed onto a astack than can be stored

5 of 36

Stack Underflow

Occurs when more items are popped from a stack thana re currently stored

6 of 36

What are the operations of a stack?

1. Push(), 2. Pop(), 3. Peek()

7 of 36

Queue

First-in First-out data structure

8 of 36

Linear Queue

Fixed or dynamically sized queue

9 of 36

Circular Queue

Front and rear pointers can wrap around from the end to the start - more efficient

10 of 36

Priority Queue

Some data may leave the queue out of sequence due to having a higher priority

11 of 36

What are the operations of a Queue?

Enqueue(), Dequeue(), isEmpty(), isFull()

12 of 36

Graph

Data structure that models relationships between pairs of objects

13 of 36

Vertex/Node

Object in a graph

14 of 36

Edge/Arc

Relationship between two nodes

15 of 36

Weighted Graph

Data values label the edges

16 of 36

Undirected Graph

Relationships work two ways

17 of 36

Directed Graph

Relationships work one way

18 of 36

What are the uses of a Graph

1. Human newtorks e.g. Family/Work groups. 2. Transport Networks e.g. Calculating fastest route. 3. The internet + Web e.g. mapping the internet

19 of 36

Advantages of List to store graph adjecencies

More memory efficient as they only store data where adjecencies exist whereas matricies store every possible combination. Lists are used for graphs with few adjecencies

20 of 36

Advantages of matricies to store graph adjecencies

Allow adjecencies to be identified mroe quickly as every combination is recorded, whereas lists need to be parsed to identify whether particular adjecencies exist. Matricies used for graphs with many adjecencies

21 of 36

Tree

Undirected graph with no loops

22 of 36

Binary Tree

Tree with a maximum of two child nodes

23 of 36

How are binary trees created?

1. Input data in order given. 2. Always start from root. 3. < goes left. 4. > goes right

24 of 36

What are the uses of binary trees?

1. Binary search trees. 2. Compilers: veryfying syntax. 3. Storing data with an inherant heirarchal structure

25 of 36

Hash Table

Data structure thats stores key/value pairs based on an index generated from a hashing algorithm

26 of 36

What are the uses of hash tables?

1. Operating Systems - Storing and locating executable files of programs and utilities. 2. Encryption: encrypting data. 3. Checksums: calculating a value from a set of data

27 of 36

WHat must a good hashing algorithm do?

1. Generate usnique values that create as few collisions as possible. 2. Create a unifrom spread of data to avoid clustering. 3. Balance speed and complexity

28 of 36

Load Factor

Ratio of available indicies to total indicies. A high load factor means it will be increasingly difficult to produce a unique index

29 of 36

Collision

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

30 of 36

How can collisions be dealt with?

1. Chaining - Create a list in that slot and append elements t the list. 2. Rehashing - apply the same or an alternative algorithm is applied until a unique key is generated. 3. Probing - Placing in the next empty slot

31 of 36

Dictionary

Similar to hash tables in that it maps keys to data. Known as an associative array in that it deals with two sets of asociated data. Values are accessed using the associated key

32 of 36

What is a use of a dictionary?

Information Retreival

33 of 36

Vector

Measurement with both magnitude and direction

34 of 36

How can vectors be represented?

List, Dictionary, Array, Function (F:->R), Arrows, Notation 'n vector over R'

35 of 36

How is Dot Product done?

(a,b).(c,d) = (a * c + b * d) = (a AND c XOR b AND d): Can be used to find the angle of a vector

36 of 36

## Other cards in this set

### Card 2

#### Front

The amount of data stored and the memory allocated will vary during runtime

#### Back

Dynamic Data Structure

### Card 3

#### Front

First-in Last-out data structure

#### Back

### Card 4

#### Front

1. Reversing List contents. 2. Handling interrupts. 3. Nesting and recursion

#### Back

### Card 5

#### Front

Occurs when more items are pushed onto a astack than can be stored

#### Back

## Similar Computing resources:

0.0 / 5

0.0 / 5

5.0 / 5 based on 5 ratings

5.0 / 5 based on 2 ratings

5.0 / 5 based on 1 rating

Teacher recommended

0.0 / 5

0.0 / 5

0.0 / 5

0.0 / 5

## Comments

Report