4.2 data structures

Question 1

how do dynamic ds work

ds = data structure

Answer 1

allocate and deallocate memory from the heap

heap an area of memory used specifically for this purpose

Question 2

differences between dynamic and static data structures

Answer 2

• static ds have a fixed size;
• dynamic ds only take up the amt of storage space required for the actual data;
• dynamic ds require pointers to the next item;
• static ds store data in consecutive memory locations;

Question 3

advantages of dynamic data structures

Answer 3

• no wasted memory;
• no limit on number of items that can be added;
• resources only allocated as they are needed;

Question 4

disadvantages of dynamic data structures

Answer 4

• additional memory needed for pointers;
• can result in memory leak;
• can take longer to access an item directly;

Question 5

what is a dictionary

Answer 5

a collection of key-value pairs in which the value is accessed via the associated key;

Question 6

circular queue advantage

Answer 6

• items in a linear queue are all shuffled forward when an item is DELETED;
• this means circular queues are more time efficient;
• free spaces can be reused

Question 7

when to use a linear queue over a circular queue

Answer 7

when a queue is small in size

Question 8

attribute of a circular queue

Answer 8

a pointer to the front;

Question 9

what is a priority queue

Answer 9

system that aims to deal with tasks on FIFO basis, but after giving them a priority order

Question 10

remove an item from a circular queue

method

Answer 10

1. check the queue is empty;
2. compare the value of the front pointer with the max size of the array;
3. if equal, then front pointer becomes 1;
4. otherwise, add 1 to the front pointer;

Question 11

adding an item to a linear queue

method

Answer 11

• check that the queue is not already full;
• add 1 to the value of the rear pointer;
• then add the new item to the position indicated by the rear pointer;

Question 12

adding an item to a priority queue

method

Answer 12

• starting with the item at the rear of the queue, move each item back one piece in the array;
• until you find an item with the same OR higher priority than the item to add;
• add the new item in the position before that item;

Question 13

what is a tree

Answer 13

connected, undirected graph; with no cycles;

Question 14

what is a rooted tree

Answer 14

• a tree with one vertex designated as the root;
• has a parent-child relationship between the nodes;
• root is the only node with no parent and all other nodes are descendants of the root;

Question 15

what is a binary tree

Answer 15

• rooted tree;
• where each node has at most two child nodes;

Question 16

common application of a binary tree

Answer 16

binary search tree;

Question 17

pre-order traversal

Answer 17

follow the left of the node - go round and underneath tree, whenever line touches left of node, visit

Question 18

in-order traversal

Answer 18

follow the bottom of the node - go round and underneath tree, whenever line touches bottom of node, visit

Question 19

post-order traversal

Answer 19

follow the right of the node - go round and underneath tree, whenever line touches right of node, visit

Question 20

stack frame components

Answer 20

• local variables;
• return address;
• parameters;
• register values;

Question 21

peeking a stack

what does it do

Answer 21

returns the value of the top element without removing it

Question 22

implemening repeat and undo operations with one stack

method

Answer 22

1. stack is used to store the actions;
2. each time an action is completed it is pushed onto the TOP of the stack;
3. unless it is an undo action;
4. when repeat action is used, the result of peek function is used to indicate the action to complete;
5. when undo action is used, the top item is popped from the stack of actions;

Question 23

reverse order of items in a queue with a single stack

method

Answer 23

• (until queue empty) repeatedly remove (the front item) from the queue and push it on to the stack
• (until stack empty) repeatedly pop items from the stack and add them to (the rear of) the queue

Question 24

what does a front pointer do

Answer 24

points to the next item to remove

Question 25

what does a rear pointer do

Answer 25

points to the last item added

Question 26

overflow

Answer 26

trying to push onto a stack that is full

Question 27

underflow

Answer 27

trying to pop from an empty stack

Question 28

what is a hash table

Answer 28

a data structure that creates a mapping between keys and values;

Question 29

why is a hash table a suitable choice to implement a dictionary?

Answer 29

allows direct access to the value being looked up;

Question 30

adding a record to a hash table

method

Answer 30

• hash algorithm applied;
• to key value;
• result is location in table where the record should be stored;
• if location is not empty;
• then use next free location;

Question 31

rehashing

method

Answer 31

• larger hash table is created;
• each value in the existing table is inserted into the new table;
• in a position determined by a new hashing algorithm;

Question 32

when does a collision occur in a hash table

Answer 32

when two key values compute the same hash;

Question 33

when is it not suitable to use a hash table?

Answer 33

• when searches need to be done based on multiple different properties of an item;

Question 34

finding an item in a hash table

method

Answer 34

• apply hash function to the specified ID;
• this will give the position in the array where that item has been stored;
• if another item is in that position then use a method to check if a collision occurred when adding items to hash table
• if location is empty, then the item does not exist;

Question 35

when to use an adjacency matrix over an adjacency list

Answer 35

• when graph/matrix is not sparse;
• when edges are frequently changed;
• when presence of specific edges needs to be tested frequently;

Question 36

what is a weighted graph

Answer 36

a graph where each edge has a value associated with it

Question 37

when to use an adjacency list over an adjacency matrix?

Answer 37

• when graph/matrix is sparse;
• when edges are rarely changed;
• when presence/absence of specific edges does not need to be tested;

Question 38

what is a stack?

Answer 38

• a FIFO ds where new items are added to the top of the stack;
• and items are removed from the top of the stack;

Question 39

uses of stacks in a computing system

Answer 39

• call stack
• back buttons in a web browser
• undo buttons in an editor

Question 40

hashing algorithm

method

Answer 40

• an algorithm is applied to the primary key;
• to generate an address;
• where the data is stored;

Question 41

improving the performance of a hash table

Answer 41

• increase the size of the table and rehash all entries;
• so that the load factor is reduced and there are fewer collisions;

Question 42

effect of multiplying a vector by a scalar

Answer 42

the vector is scaled in size, but does not change direction