Part 2

Question 1

What is an abstract data type?

Answer 1

A type that can be specified without using any programming language

Question 2

What are the elements of an abstract data type?

Answer 2

The name of the type

The name of the primitive operations, their arguments and result types

The semantic of the operations; a description of how they behave

Question 3

Why are ADTs beneficial?

Answer 3

They allow an application program to use the type without knowing how it is implemented.

Question 4

To guarantee that an ADT will work correctly, the objects of the ADT must only be accessed using the _____________

Answer 4

Primitive operations

Question 5

What are the primitive operations of a stack?

Answer 5

push

pop

top

isempty

createstack

Question 6

How are data items in a stack accessed?

Answer 6

From the top only

Question 7

What does the push operation do to a stack?

Answer 7

Adds an item to the top of the stack

Question 8

What does the pop operation do to a stack?

Answer 8

Removes the top item

Question 9

What does the top operation do to a stack?

Answer 9

Returns the top item of the stack (aka peek)

Question 10

What does the isempty operation do to a stack?

Answer 10

Deduces whether the stack contains any items or not

Question 11

What does the createstack operation do to a stack?

Answer 11

Creates a new stack object with no items

Question 12

What are the 4 stack axioms?

Answer 12

isempty(createstack()) = true

isempty(push(n, s)) = false

top(push(n, s)) = n

pop(push(n, s)) = s

Where s is the stack before the operation is applied, and n is the item being applied to the stack

Question 13

The stack axiom

isempty(createstack())

has the value

Answer 13

true

Question 14

The stack axiom

isempty(push(n, s))

has the value

Answer 14

false

Question 15

The stack axiom

top(push(n, s))

has the value

Answer 15

n

Question 16

The stack axiom

pop(push(n, s))

has the value

Answer 16

s

Question 17

How does one prevent having to frequently shift elements in an array-based stack?

Answer 17

Use a large array with a cursor that indicates the start position of the stack

Question 18

What is the advantage of using an ArrayList implementation of a stack?

Answer 18

Don’t have to manually keep track of cursors etc.

Arraylist handles it all for us

Question 19

What is the disadvantage of using an arraylist implementation of stack, compared with an array implementation?

Answer 19

Possibly less efficient than keeping track of the cursor ourselves.

Question 20

What is the advantage of using a linked-list stack?

Answer 20

Don’t have to worry about array sizes

Question 21

What is the disadvantage of using a linked list to store a stack?

Answer 21

Greater memory consumption than array

Question 22

What is a queue?

Answer 22

Structure where items are added at the back and removed from the front

Question 23

What are the primitive operations of the queue?

Answer 23

add

removefront

front

isempty

Question 24

What does the add operation do in a queue?

Answer 24

adds an item to the back of the queue

Question 25

What does the removefront operation do in a queue?

Answer 25

remove the front item

Question 26

what does the front operation do in a queue?

Answer 26

returns the front item without removing it

Question 27

What are the axioms for the Queue adt?

Answer 27

isempty(createqueue()) = true

isempty(add(n, q)) = false

front(add(n, q)) = n, if q is empty

front(add(n, q)) = front(q), if q is not empty

removefront(add(n, q)) = q, if q is empty

removefront(add(n, q)) = add(n, removefront(q)), if q is not empty

Question 28

The queue axiom

isempty(createqueue())

has the value

Answer 28

true

Question 29

The queue axiom

isempty(add(n, q))

has the value

Answer 29

false

Question 30

The queue axiom

front(add(n, q))

has the value

Answer 30

n, if q is empty

Question 31

The queue axiom

front(add(n, q))

has the value

Answer 31

front(q), if q is not empty

Question 32

The queue axiom

removefront(add(n, q))

has the value

Answer 32

q, if q is empty

Question 33

The queue axiom

removefront(add(n, q))

has value

Answer 33

add(n, removefront(q)), if q is not empty

Question 34

Using an array implementation of queues will require ___ cursors

Answer 34

Two

Question 35

With a linkedlist implementation of a queue, a reference to _________ will need to be stored in addition to the reference to the ____________

Answer 35

back item

front item