cs 2.1 data structures (ALEVEL)

Question 1

Linear queues

Answer 1

has two pointers (front +rear)
- identify which item at front and where to place new item
Add item:

check if list is full - if not…
the item is added to where rear pointer is pointed to
and rear pointer moves to nest available position

remove item:

check if list is empty - if not…
item that the front pointer is pointing at is removed
front pointer moves to the next item

Question 2

queues operations

Answer 2

Enqueue
Dequeue
IsEmpty
IsFull

Question 3

circular queue

Answer 3

front and rear pointer can move over the two ends of the queue making for more memory efficient data structure
know how to:
add item, remove item

Question 4

priority queues

Answer 4

items are assigned a priority, items with highest priority are dequeued before low priority items.
if 2/more items have same priority items are removed in FIFO order
e.g. priority printer queue

Question 5

Stacks + operations

Answer 5

has a top pointer
push
pop
peek
IsFull (if it is = stack overflow)
IsEmpty (if it is = Stack underflow)
know how to:
add, remove,peek, an item

Question 6

graphs - adjacency matrices

Answer 6

-stores every possible edge between nodes even those that don’t exist = almost half of matrix is repeated data (memory inefficient)
-allows specified edge to be queried very quickly (time efficient)
-suited to dense graphs where there’s large no. of edges.

Question 7

graph -adjacency list

Answer 7

-only stores edges that exist in graph(memory efficient)
-slow to query, each item in list must be searched sequentially (time inefficient)
-well suited to sparse graph, where there’s few edges

Question 8

hash tables

Answer 8

constant time complexity - O(1)
stores key-value pairs
key sent to hash function, resulting hash is index of key-value pair in hash table

Question 9

hashing algorithm

Answer 9

takes an input and returns a hash
-hash is unique to its input + cannot be reversed to retrieve the input value

Question 10

hash table -collisions

Answer 10

different inputs produce same hash
rehashing technique = keep on moving to next position until an available one is found

Question 11

Dictionaires

Answer 11

• collection of key-value pairs
  -value accessed by associated key
• application = dictionary-based compression

Question 12

Vectors

Answer 12

if viewed as function - represented by dictionary
if viewed as a list - represented by one-dimensional array

Question 13

Static data structure

Answer 13

fixed in size
if no. of data items to be stored exceeds no. of memory location allocated to structure = overflow error

Question 14

Dynamic data structure

Answer 14

change in size
no. of memory locations required isn’t fixed
computer can’t allocate contiguous memory locations, each item is stored alongside a reference to where next item is stored in memory