data structures

Question 1

what is a queue

Answer 1

an ordered set of items which area added at the tail and removed from the head - fifo

Question 2

what are the 5 operations needed to use a queue

Answer 2

Queue() - creates an empty queue
dequeue()
enqueue(item)
IsEmpty()
size()

Question 3

what is an abstract data type

Answer 3

defines a data type logically rather than structurally

Question 4

data structure

Answer 4

the physical representation of the structure of data being stored in memory

Question 5

strong encapsulation

Answer 5

completely hides the details on howl the data structure is stored from the user

Question 6

records

Answer 6

a compound item with components of various different types called fields

Question 7

what does malloc do

Answer 7

dynamically allocates marmot and return the base location for the allocated space
e.g. student = malloc(sizeof(student));

Question 8

what is a pro of 2d arrays

Answer 8

very fast access compared to a list using indexing

Question 9

what are cons of 2d arrays

Answer 9

has a fixed size and doesn’t resize easily (you have to copy the contents into a bigger array)
insertions and deletions can be costly

Question 10

what is a stack

Answer 10

adt - filo

Question 11

bounded stacks

Answer 11

have a max size

Question 12

stack overflow

Answer 12

trying to push when the stack is full

Question 13

stack underflow

Answer 13

trying to pop when the stack is empty

Question 14

what are some common applications for stacks

Answer 14

function calls
depth first search
evaluating expressions
braces matching

Question 15

list

Answer 15

stores a set of items in a linear order

Question 16

doubly linked lists

Answer 16

each data entry has a next and previous order

Question 17

singly linked lists

Answer 17

each data entry has a next pointer therefore they can only be traversed forward

Question 18

what is theoretical time complexity

Answer 18

the relationship between the size of the input and the algorithm running time

Question 19

what is a recursive function

Answer 19

a function that calls itself

Question 20

what are some positives of iteration

Answer 20

stack overflows are less likely as memory usage is controlled explicitly by the programmer
can execute quicker s there’s no overhead from the creation/destruction of the stack frame

Question 21

why should you use recursion (positives)

Answer 21

naturally recursive functions are more concise compared to expressing them iteratively
languages that support recursion can eliminate some of the extra cost to performance and stack overflows

Question 22

key

Answer 22

unique identifier for what you want to store and remove

Question 23

how can you deal with collisions in indexed retrieval

Answer 23

use indexed arrays; recomputing the array when you want to insert new data
using chains

Question 24

how can chains help with collisions

Answer 24

when storage is based on the first letter you can have an index pointing to a chain for each one
dynamic so extra objects can be added easily
no need to recompute the index

Question 25

what does a hashing function do

Answer 25

converts a key into an integer which is then used for indexing a storage array

Question 26

how can you minimise collisions in a hash table

Answer 26

larger array - a wide range of index values
can use multiplication as well as addition to get your index
uniform hashing; each key is equally as likely to map to an array location

Question 27

why is shift usually used for hashing tables

Answer 27

hashing is meant to be quite fast however multiplication and division are quite slow