Data Structures and Algorithms Mid-Term Study

Question 1

The Queue ADT

Answer 1

-stores arbitrary objects- insertions and deletions follow the first-in, first-out scheme-insertions at the rear,removals at the front

Question 2

enqueue()

Answer 2

inserts an element at the end of the queue

Question 3

dequeue()

Answer 3

removes and returns the element at the front of the queue

Question 4

object first() (Queue)

Answer 4

returns the element at the front without removing it

Question 5

integer size() (Queue)

Answer 5

returns the number of elements stored

Question 6

boolean isEmpty() (Queue)

Answer 6

indicates whether no elements are stored

Question 7

Queue boundary cases

Answer 7

Attempting the execution of deqeueue() or first() on an empty queue returns null

Question 8

Direct Applications for a Queue

Answer 8

• Waiting lists, bureaucracy- Access to shared resources- Multiprogramming

Question 9

Indirect Applications for a Queue

Answer 9

• Auxiliary data structure for algoritms- Component of other data structures

Question 10

Queue is limited to the __________ of the array.

Answer 10

size

Question 11

Queue Performance runs in _________.

Answer 11

O(1)

Question 12

enqueue() corresponds to what java.util.Queue?

Answer 12

add(e)offer(e)

Question 13

dequeue() corresponds to what java.util.Queue?

Answer 13

remove()poll()

Question 14

In a queue, first() corresponds to what java.util.Queue?

Answer 14

element()peek()

Question 15

In a queue, size() corresponds to what java.util.Queue?

Answer 15

size()

Question 16

In a queue, isEmpty() corresponds to what java.util.Queue?

Answer 16

isEmpty()

Question 17

How do you impliment a round robin scheduler using a queue?

Answer 17

repeat the following steps:- e = Q.dequeue()- Service element e- Q.enqueue(e)

Question 18

What method does a circular queue have that other queues don’t?

Answer 18

rotate()

Question 19

List the methods of the Double Ended Queue.

Answer 19

enqueueLast(object)enqueueFirst(object)dequeueFirst()dequeueLast()

Question 20

What does ADT stand for?

Answer 20

Abstract Data Type

Question 21

What’s an example of an ADT?

Answer 21

A simple stock trading system.order buy(stock, shares, price)order sell(stock, shares, price)void cancel(order)

Question 22

Stack

Answer 22

Follows Last in first out scheme.Think of the pez despenser!push(object)object pop()top()size()isEmpty()

Question 23

What built in utility does java use for the stack?

Answer 23

java.util.Stack

Question 24

Can the operations pop and top be performed even though the stack is empty?

Answer 24

Yes

Question 25

Direct Applications of using the stack.

Answer 25

• Page-visited history in a web browser- undo sequence in a text editor- Chain of method calls in the Java Virtual Machine

Question 26

Indirect applications of the stack.

Answer 26

Auxiliary data structure for algorithmsComponent of other data structures

Question 27

Operator precedence

Answer 27

• has precedence over +/-

Question 28

Recursive definition

Answer 28

f(n) = { 1 if n = 0n-f(n-1) else

Question 29

factorial function

Answer 29

n! = 123……..(n-1)n

Question 30

Base Cases

Answer 30

Values of the input variables for which we perform no recursive calls

Question 31

Recursive Calls

Answer 31

• calls to the current method- Each recursive call should be defined so that it makes progress towards a base case.

Question 32

Application on using Recursion

Answer 32

Drawing ticks on an English Ruler

Question 33

reversing an array

Answer 33

reverseArray(A, i, j)if (i < j){Swap A[i] and A[j]reverseArray(A, i+1, j-1)}return

Question 34

Recursive power function

Answer 34

p(x,n) = { 1 if n=0x*p(x,n-1) else

Question 35

What is an Algorithm?

Answer 35

A step by step process that creates a result in a finite amount of time

Question 36

The Seven Important Functions

Answer 36

Constant = 1Logarithmic = log nLinear = nN-Log-N = n log nQuadratic = n^2Cubic = n^3Exponential = 2^n

Question 37

Big-Oh Notation

Answer 37

Characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.