1.4.2 Data Structures

Question 1

Array features

Answer 1

Ordered, mutable, static, one data type

Question 2

Tuple features

Answer 2

Preferred, immutable, static, different data types

Question 3

Record features

Answer 3

Fixed number of fields of different data types, implemented with each row as a tuple

Question 4

Static vs dynamic

Answer 4

Dynamic data structures can change static data structures cannot change size

Question 5

Examples of abstract data types

Answer 5

List, stack, queue, graph, tree, hash table, linked list

Question 6

Examples of compound data types

Answer 6

Strings, arrays

Question 7

Examples of primitive data types

Answer 7

Integer, boolean, real

Question 8

Four operations in queues

Answer 8

Add item to rear of queue
Remove item from front of queue
Check if queue is empty
Check if queue is full

Question 9

Adding to circular queue

Answer 9

next index = (current +1) MOD len

Question 10

Implementation of a dynamic list

Answer 10

New location taken from the heap of memory locations for dynamic allocation
When item is deleted, memory location is returned to heap, pointers keep list in user-specified order

Question 11

List operations

Answer 11

isEmpty()
append(item)
remove(item)
count(item)
len(list)
index(item)
insert(pos,item)
pop(pos) - default -1

Question 12

Linked list features

Answer 12

Composed of nodes with two parts: the data and the pointer
Start pointer identifies first node
Nextfree pointer shows index of next free space in array
(ALPHABETICAL/ASCENDING ORDER)

Question 13

Linked list operations

Answer 13

.data()
.pointer()

Question 14

Stack operations

Answer 14

push(item)
pop()
isFull()
isEmpty()
peek()
size()

Question 15

Stack overflow error

Answer 15

Attempting to push onto a full stack

Question 16

Stack underflow error

Answer 16

Trying to pop from a stack that is empty

Question 17

Call stack

Answer 17

System level data structure that provides mechanism for passing parameters and return addressees to subroutines

Question 18

Stack function in subroutine calls

Answer 18

The parameters are saved onto the stack
The address where execution will return to is saved
Execution is transferred to the subroutine code

Question 19

Stack function in subroutine execution

Answer 19

Stack space is allocated for local variables (recursive routines use much more space and more often cause overflow errors)
Subroutine code executes
Return address received
Parameters popped
Execution transferred back to return address

Question 20

Stack uses

Answer 20

Undo/redo in word processors
Holding website addresses just visited
Interrupts

Question 21

Hashing definition

Answer 21

Address of data to be stored is calculated from the data itself using a hashing algorithm (often involves MOD)

Question 22

Collision

Answer 22

When the hashing algorithm generated the same address for different primary keys (IMPOSSIBLE TO AVOID)

Question 23

Dealing with collisions

Answer 23

Put in next free spot, or next third free spot (must ensure every cell in table is covered)

Question 24

Searching for items in a hash table

Answer 24

Perform hashing algorithm on item
If not in that cell check next
Keep checking until item or empty cell is found
Empty cell means item is not in table

Question 25

Deleting items from a hash table

Answer 25

Replace with dummy item/marker

Question 26

Examples of hashing algorithms

Answer 26

Mid-square Folding

Question 27

How to hash alphanumeric data

Answer 27

Find ASCII value then hash that

Question 28

Mid-square method

Answer 28

Square the item Extract middle portion of digits MOD the d

Question 29

Folding method

Answer 29

Divide into equal sized pieces Add pieces together MOD

Question 30

Dictionaries

Answer 30

ADT made of associated pairs (key and value)

Question 31

Hashing and dictionaries

Answer 31

Dictionaries are unordered and address of key:value is calculated using a hashing algorithm (much quicker access times than array/list)

Question 32

Dictionary operations

Answer 32

Add new k:v pair Delete k:v pair Amend v in k:v pair Return v if given k Key in dict? Return length of dict

Question 33

Graph

Answer 33

Set of nodes connected by edges, edges can be weighted (cost of traversal)

Question 34

Undirected graph

Answer 34

All edges are bidirectional (same cost both ways)

Question 35

Directed graph

Answer 35

Edges have weights in a specific direction

Question 36

Two ways to represent graphs

Answer 36

Adjacency matrix Adjacency list

Question 37

Adjacency matrix

Answer 37

Each row and column represents a node, item at [row,column] indicates weight of path row -> column

Question 38

Advantages of adjacency matrix

Answer 38

Convenient to work with More visually understandable Adding edges is simple

Question 39

Disadvantages of adjacency matrix

Answer 39

A sparse graph will leave most of the cells empty ^ Wastes lots of memory space

Question 40

Adjacency list

Answer 40

Dictionary of dictionaries - key in the dictionary is a node. Value of that key is a dictionary with k:v pairs of nodes connected to:weights of edges

Question 41

Adjacency list advantages

Answer 41

Only uses storage for the connections that exist - saves space Good for representing large, sparse graphs

Question 42

Applications of graphs

Answer 42

Computer networks Web pages and links Maps Project management

Question 43

Features of trees

Answer 43

Root, branches, leaves

Question 44

Tree definition

Answer 44

A connected, undirected graph with no cycles

Question 45

Rooted tree definition

Answer 45

One node is the root, each node except the root has one unique parent

Question 46

Binary tree definition

Answer 46

A rooted tree where each node has a maximum of two children

Question 47

Parts of a node

Answer 47

Data, left pointer, right pointer

Question 48

Binary tree traversals

Answer 48

Pre-order, in-order, post-order, breadth-first

Question 49

Pre-order traversal

Answer 49

NLR - used to produce pre-fix or Polish notation

Question 50

In-order traversal

Answer 50

LNR - Traverses nodes in sequential order

Question 51

Post-order traversal

Answer 51

LRN - used to produce post-fix or reverse polish notation

Question 52

Breadth-first traversal

Answer 52

Reads each level (top to bottom) from left to right

Question 53

Balanced binary tree

Answer 53

Nodes are distributed to height is kept to a minimum so it is more efficient for searching

Question 54

Three cases of deleting nodes

Answer 54

Is a leaf Has one child Has two children

Question 55

Deleting a leaf

Answer 55

Just delete

Question 56

Deleting a node with one child

Answer 56

Move up subtree with the child replacing the deleted node

Question 57

Deleting a node with two children

Answer 57

Replace node with the next highest node in the whole subtree. Then repeat deleting process with that node - sometimes entire subtree will need to be rebuilt

Question 58

Uses for a tree

Answer 58

NOT FOR EDITING/DELETING Designed to be made, then traversed - very quick to traverse/search