Midterm Exam Review

The complexity of T(n)=5n² + 1000n +3000 is ____________________

exponential

constant

logarithmic

quadratic

quadratic

A loop body is controlled by the following statement:

for (int count = 2; count <= n; count *=2)

If the statements in the body of the loop are all O(1), what is the complexity of the loop?

O(n³)

O(n²)

O(1)

O(logn)

O(logn)

If a growth function is f(n) = 100n12 + 1.5n +9999n3 + 9999, what is its complexity?

9999

O(n¹²)

O(1.5ⁿ)

O(n³)

O(1.5ⁿ)

Sort the time complexities of the expressions from most efficient to least efficient. Which answer is correct?

1. 23n² + 10n + 999999

2. 3n + 100n⁴

3. 29n log n

4. 40n¹∙⁵+100

2,1,4,3

3,4,1,2

4,3,1,2

1,3,4,2

3,4,1,2

What is the running time of the following code fragment:

for (int count = 0; count < n; count ++)

{

for (int count2 = 0; count2 < n*n; count2++)

{

System.out.println(count, count2);

sum=sum+count+count2;

}

}

5O(n³)

O(n³)

O(n³+n)

n³

O(n³)

Big - Oh notation establishes a(n) ____________ on a growth function.

lower bound

upper bound

average (or mean) bound

both a) and b)

upper bound

Theta notation establishes a(n) ____________ on a growth function.

lower bound

upper bound

average (or mean) bound

both a) and b)

average (or mean) bound

In computer science, algorithm refers to a special method usable by a computer for the solution to a problem.

True

False

True

A(n) _____________________ is a list collection with elements that are ordered by a characteristic of the elements.

ordered list

unordered list

linked list

indexed list

ordered list

When a linked list is created initially, how many element(s) does it have?

1

100

10

0

0

Which of the following is/are not operation(s) on a LinkedList object?

getValue()

getLast()

push()

delete()

getValue()

delete()

The operation clear() in a LinkedList clears the list of all its elements.

True

False

True

A(n) _____________________ is a data structure that uses object reference variables to create links between objects.

object

primitive type

array

Linked List

Linked List

A LinkedList class has an isEmpty() method defined. What should this method return?

an int representing the number of items in the LinkedList

a boolean value representing whether the LinkedList is empty or not.

a double representing the average of the values of the items in the LinkedList.

a String representing the contents of the items in the LinkedList

a boolean value representing whether the LinkedList is empty or not.

In an indexed list, elements are referenced by their numericposition in the list.

True

False

True

The _______ method available in the iterator interface returns a boolean result - true if there are items left to process in the list.

hasNext()

next()

has()

hasIt()

hasNext()

In a UML diagram the symbol "#" means the data fields are declared with the the _________ visibility modifier.

protected

private

public

class

protected

Interface relationships are shown in a UML class diagram using a ______ arrow with an _____ triangular arrowhead pointing to the parent class

solid, filled

dotted, filled

dotted, unfilled

solid, unfilled

dotted, unfilled

Two advantages of the Java generic classes are:

type-safety

type-definition

type-unsafety

type-casting is not required

type-safety

type-casting is not required

A(n) __________ stores a variable number of objects and it can be resized dynamically.

String

Wrapper

ArrayList

Array

ArrayList

Given a singly linked list contains five nodes and simply show as 5->4->3->2->1, where the head reference refers to the first node contains an Integer with value 5. If Node curr = head; curr= curr.next; are applied to this list, what is the number you can find in the first node?

2

4

5

3

5

If a sequence of numbers 2, 6, 7, 13, 5, 4, 20 is added to a stack, in the order given, which number will be the second number to be removed from the stack?

6

5

7

4

4

Which of the following methods inserts an element into a stack data structure?

append

insert

put

push

push

A stack is a LIFO data structure.

True

False

True

If a sequence of number 12, 8, 10, 7, 6, 15 is added to a queue, in the order given, which number will be the third number to be removed from the queue?

10

6

7

8

10

In an ideal implementation of a stack, the operations push() is ______________________ .

O(n)

O(n²)

O(1)

O(n log n)

O(1)

What values are returned during the following series of stack operations, if executed upon an initially empty stack? push(21), push(19), pop(), push(2), push(8), pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(), pop(), push(4), pop(), pop(). (Please provide the returned values in the format "value1, value2, value3...")

Answer = Value1 = 19, value2 = 8, value3 = 2, value4 = 1, value5 = 6,value6 = 7, value7 = 4, value8 = 9

OR

Answer: {19, 8, 2, 1, 6, 7, 4, 9}

Provide a method with signature transfer(S, T) that transfers all elements from stack S onto stack T. After transfer, S and T will contain the same set of elements in the same order. The element that at the top of S is the element that at the top of T. (Pseudo code is good enough. You can directly use the methods defined in Queue or Stack class. Temporary queue or stack can be used in the solution if needed)

public class transfer(S, T){Stack tempStack;while (!S.isEmpty()){element = S.pop();tempStack.push(element);}while (!temp.isEmpty()){element = temp.pop();T.push(element);S.push(element);}

Draw the linked-list that is created by the following statements:

StringNode str1 = new StringNode();

str1.setData("Dino");

StringNode str2 = new StringNode("Fred", str1);

StringNode str3 = new StringNode("Barney");

str1.setLink(str3);

Fred --> Dino --> Barney

Show your steps on how you evaluate the following postfix expression by using a stack: (the calculations will be simple enough that you won't need a calculator).

7 5 + 9 - 4 * 2 /

Push 7 to the stackPush 5 to the stackPop 5 and 7 from the stack --> 7 + 5 = 12Push 12 to the stackPush 9 to the stackPop 9 and 12 from the stack --> 12 - 9 = 3Push 3 to the stackPush 4 to the stackPop 4 and 3 from the stack --> 3 * 4 = 12Push 12 to the stackPush 2 to the stackPop 2 and 12 from the stack --> 12 / 2 = 6

Convert the following infix expressions to postfix notation: (hint: make it fully parenthesized, then follow the method we used in the notes.)

A * B + C / D

((A * B) + (C / D))

A B * C D / +