Abstract Data Types

Question 1

what is an ADT

Answer 1

describes the desired behaviour in terms of supported operations and their effects.

Question 2

what is a data structure

Answer 2

describes how data values are stored and operated on. implements one or more ADTs

Question 3

give the vector ADT

Answer 3

e = element, r = rank = number of elements before

get(r)
insert(r,e)
remove(r)

Question 4

give the list ADT

Answer 4

simply have elements

first()
last()
after(p)
before(p)
insertBefore(p,e)
insertAfter(p,e)
remove(p)

Question 5

give the stack ADT

Answer 5

push(o)
pop()
peek() - top object without removing
size()
isEmpty()

Question 6

give the queue ADT

Answer 6

enqueue(o) - insert object at reer
dequeue()- remove and return front object
peek() - return front object without returning
size()
isEmpty()

Question 7

give the set ADT

Answer 7

add(o)
remove(o)
find(o)
size()
isEmpty()

Question 8

give the dictionary ADT

Answer 8

also known as associative array or map

find(k)
insert(k,v)
remove(k)

Question 9

give the priority queue ADT

Answer 9

insert(k,e)
removeMin()
size()
isEmpty()