Canterbury QuestionBank

What does the following Java code print?

int sum=0;
for (int i=0; i>100; i++) {
   sum += i;
}
System.out.println(sum);

100

0 + 1 + 2 + ... + 99 + 100

0 + 1 + 2 + ... + 98 + 99

none of the above

This is a trick question!  The stop condition of the for loop is i>100, and since i starts at 0, i is never > 100, so the loop immediately ends.

Suppose the following Java code prints "statement 2":

if (num < 6) {
   System.out.println("statement 1");
} else {
   System.out.println("statement 2");
}

What must be true about num?

greater than 6

less than 6

less than or equal to 6

this program cannot print "statement 2"

The opposite of less than is greater than or equal to.  Not just greater than.

Suppose a is true, b is false, and c is false. Which of the following expressions is true?

c && !a

Substitute:

1. !c && !b
2. !false && !false
3. true && true
4. true

Only one of the following will not compile and run under Quick C. Which one?

main(){}

 main(void){}

int main(void){return 1}

void main(void){}

The semi-colon end of line delimiter occurs within a curly bracket pairing, which is not a logical combination from the compiler's parsing perspective

What is output by the code shown in the question below. Think about it carefully - it may be a bit tricky!

void main (void)

{

     #define LIMIT 8

     int i = 0;

     while ( i++ < LIMIT )

    {

          if ( i )

         {

               printf( "%d", LIMIT - i );

         }

     }

}

Nothing

876543210

876543210-1

76543210-1

The while loop increments the index before each iteration of the loop and the resulting increased index value is subtracted from the Limit of 8.  Thus the values printed range from 7 to 0.

You are preparing test data for this function that accepts a day of the month (as a number) from the user:

int iGetDay(int iMonth);

You are currently working with a month value of 5 (May). What should your boundary test values be for iGetDay?

-1, 0, 30, 31

-1, 0, 31, 32

0, 1, 29, 30

0, 1, 30, 31

The month of May has 31 days and starts on the 1st of May.  So the day before and the day after these boundary days consitute the boundary test conditions

How many times will the printf statement be executed in this code?

In each case assume the definition

int i = 0;

WARNING There are some very nasty traps in some of the code here. LOOK AT IT ALL VERY CAREFULLY!

 do

{

     printf("Count me!");

     i++;

} while(++i < 10);

0

 6

10

11

The line i++; in the body of the loop after the printf function, in combination with the ++i preceding each iteration in the while loop, causes the index to increment twice in each iteration, so the printf function is only executed 5 times

The worst-case analysis (Big-Oh) of the following Java code is:

for (j=0; j<n; j++) {
   for (k=0; k<n; k++) {
      base = base * 2;
   }

}

O(1)

O(n)

O(log₂n)

O(2ⁿ)

The body of the inner loop will be executed n² times. Each execution will take a constant amount of time. Thus, the total amount of time will be a function of n^2.

The worst-case analysis (Big-Oh) of the following Java code is:

for (j=0; j<n; j++) {

   base = base * 2;
}

O(1)

O(n²)

O(log₂n)

O(2ⁿ)

The loop will be executed n times, and each time involves a certain constant amount of work. 

Consider the following Java code:

public interface StackADT<T> { // 1
   public void push (T element);
   public T pop();
   public T peek();
   public boolean isEmpty(); 
}

The capital letter “T” on line 1 stands for:

a temporary value

a class named T defined somewhere else in the program

the top of the stack

none of the above

This interface is defined using Java's generics. We can tell what the T means by looking at how it is used.  The "T" in angle brackets on line 1 corresponds to the type of the parameter to push and the type of value returned by pop and peek. In other words, it is the type of value stored in the stack. 

The StackADT's push operation:

adds a new item at the bottom of the Stack

returns without removing the top item on the Stack

removes and returns the top item on the Stack

returns true if the Stack is empty and otherwise false

"push" is the traditional term for adding a new item to a stack. Stacks work like a pile of paper. The bottom piece of paper is the first one that was put in the pile. The top piece of paper was added most recently. When another piece of paper is added to the stack, it goes on top of the rest of the pile.

Suppose you are trying to choose between an array and a linked list to store the data in your Java program. Which data structure can change size as needed while the program is running?

an array

both

neither

When initializing a Java array, you must allocate a fixed amount of memory for storing data. Linked lists vary in size depending on how much data they contain. 

Suppose StackADT is implemented in Java using a linked list. The big-Oh time complexity of the following pop method is:

public T pop() {
   T tmp;
   if (this.top == null) 
      tmp = null;
   else {
      tmp = this.top.getElement();
      this.top = this.top.getNext();
   }
   return tmp;
}

O(log n)

O(n)

O(n²)

O(2ⁿ)

These operations can be done in constant time, independent of the size of the stack. 

Consider the following Java method:

public T pop() { \\ 1
   T tmp; \\ 2
   if (this.top == null) \\ 3
      tmp = null; \\ 4
   else { \\ 5
      tmp = this.top.getElement(); \\ 6
      this.top = this.top.getNext(); \\ 7
   } \\ 8
   return tmp; \\ 9
} \\ 10

What would happen if line 7 were before line 6?

The code would not compile.

The code would compile, but it wouldn't run.

The code would compile and run, and it would work just the same. 

If the two lines are re-ordered, the code will change the value of top to the second node, and then the second value in the stack will be the one that is returned. 

Consider the following Java method:

public T pop() { // 1
   T tmp; // 2
   if (this.top == null) // 3
      tmp = null; // 4
   else { // 5
      tmp = this.top.getElement(); // 6
      this.top = this.top.getNext(); // 7
   } // 8
   return tmp; // 9
} // 10

What would happen if line 7 were before line 6?

The code would not compile.

The code would compile, but it wouldn't run.

The code would compile and run, and it would work just the same. 

If the two lines are re-ordered, the code will change the value of top to the second node, and then the second value in the stack will be the one that is returned. 

What is output by the code shown below. Think about it carefully - it may be a bit tricky!

#define DEF_1 (2 + 2)

#define DEF_2 DEF_1 - DEF_1

int main(void)

{

printf("%d", DEF_2);

}

2

4

6

8

The declaration of DEF_2 [DEF_1 after subtracting DEF_1 = 0 ] is the value printed.

What is output by the code shown below. Think about it carefully -it may be a bit tricky!

void main( void )

{

static char szCode[] = "111";

szCode[2] = '0';

puts( szCode );

}

Nothing

011

101

111

The value of the character in the array at index [2] (where index starts from 0)  is set to zero and the other initialized array values remain unchanged

What would be the performance of removeMin and insert methods in a priority queue if it is implemented by an unsorted list?

O(1) , O(1)

 O(1) , O(n)

O(n) , O(n)

Consider this code. It is part of a program that receives MMP list votes from constituencies and stores them in a database. The field PartyName stores the names of each party involved, and the field VoteTotal keeps a running total of list votes for a party. Tally is a table-type Recordset.

Do

   ' Get a name and vote pair from the newly arrived text

   ' Returns 0 when there are no more pairs

   Start% = ExtractNextPair((txtData.Caption), Start%,_
                                                PartyName$,_Votes&)

   If Start% > 0 Then

     ' See if the party name is already present

     KeyField$ = UCase$(Trim$(PartyName$))

    Tally.Seek "=", KeyField$

     If Tally.NoMatch Then

       ' Add a new record

       Tally.AddNew

       Tally("PartyName") = KeyField$

       Tally("VoteTotal") = Votes

    Else

        ' Update the existing record - add latest votes

        Tally.Edit

        Tally("VoteTotal") = Tally("VoteTotal") + Votes

    End If

  End If

Loop While Start% > 0

Tally.Update

Why does this code not successfully store all the incoming data?

The loop logic is wrong - it should be Start% < 0

There was no call to Tally.Refresh

There was no call to Tally.UpdateRecords

The AddNew and Edit lines should be swapped

Because the line Tally.Update is outside the loop it is only executed once at the end of the program

What node will be visited prior to E in an inorder traversal of the following tree?

A

B

D

Consider these lines of code:

txtName.SetFocus

txtName.SelStart = 0

txtName.SelLength = Len(txtName.Text)

txtName is an edit text box which is currently visible.

The code may cause a run time error. This will happen if:

txtName is a multiline text box.

there is no text in txtName.

some of the text in txtName is currently highlighted.

none of the text in txtName is currently highlighted.

A disabled edit text box may not be accessed by the setfocus method as this combination is not a logical action and therefore clashes with the underlying VB event model which controls the permissible sequences of events.

What would be the minimum number of required queue, to implement a stack?

1

3

4

Which data structures would be proper in terms of performance to implement flight waiting lists?

Priority Queue

Array

Linked list

To implement student's database, which data structure is more appropriate?

Heap

Binary Tree

Priority Queue

Using double hashing and following hash function and data, in which array slot number 31 will be inserted*?

N = 13

h(k) = k mod 13

d(k) = 7 - k mod 7

(h(k) + jd(k)) mod 13

18, 41, 22, 44, 59, 32, 31, 73

*Credit goes to Goodrich et.al. (Data Structures & Algorithms in Java)

5

9

10

Given the declaration

Public StudentRecords as Collection

What line of code is required before the first student record is added to the collection?

StudentRecords = New Collection

Set StudentRecords = Collection

Set Collection = StudentRecords

Set StudentRecords.New

Set assigns an object reference to the new Collection object named StudentRecords

Using Dijkstra’s Algorithm what would be the path between A and B?

(Picture taken from Data Structures & algorithms in Java by Goodrich at. al.)

AB

ACB

ADCEB

The following processes are arranged in alphabetical order:

1 Application event procedure is called.

2 Event procedure code is executed.

3 User clicks on a button with the mouse.

4 Windows detects an event.

5 Windows passes a message to the application containing the button.

In what order will these processes normally occur in a Visual Basic application?

2, 3, 5, 4, 1

4, 3, 2, 5, 1

3, 5, 4, 1, 2

 1, 2, 3, 5, 4

The button click causes windows to detect an event and pass a message to the application containing the button. 

The application event procedure is called and the event procedure code is executed.

This Perl script does not work correctly. It is supposed to work out the average assessment mark for a student who has 6 marked exercises.

Whatever data the student enters, the script always displays an average mark of zero.

Note that line numbers have been added for reference only – they are not part of the script

1 my $total = 0;

2

3 for(my $mk = 1; $mk <= 6; $mk++)

4 {

5     print "Enter mark $mk: ";

6     my $mark = <STDIN>;

7     my $total += $mark;

8 }

9

10 my $average = $total / 6;

11 print "Average mark = $average.\n";

What is the problem?

<= 6 on line 3 should be <

The my on line 6 should not be there.

 Line 10 should show $mark / 6.

A <= 6 on line 3 should be <

B The my on line 6 should not be there.

C The my on line 7 should not be there.

D Line 10 should show $mark / 6.

A my declares the listed variables to be local (lexically) to the enclosing block, file, or eval.

source http://perldoc.perl.org/functions/my.html

Therefore the accumulated value of $total is not available to the following block where the average is calculated

This Perl subroutine does not work correctly. It is supposed to work out whether or not a person qualifies for a discount and return the correct fare, discounted or not as the case may be. Children under 13, and elderly people 65 and over qualify for a discount.

The subroutine never gives a discount

Note that line numbers have been added for reference only – they are not part of the script

1 sub getDiscount

2 {

3   my $age = $_[0]; # First parameter is age

4   my $fare = $_[1]; # Second parameter is fare

5

6   if(($age < 13) && ($age >= 65))

7   {

8   $fare *= 0.9; # 10% discount

9   }

11

12   return $fare;

13 }

What is the problem?

$_ on lines 3 and 4 should be @_.

On line 6, the < should be replaced by <=.

The return statement on line 12 should return $_[0].

No age can be less than 13 AND 65 and over. It should be OR.

This Bash command was supposed to run a Perl script, exE1.pl from a University student's bin directory on the Cislinux server, passing it a command line argument which was a text file in the copy area. It was supposed to put the results into a text file in the student's bin directory.

~/bin/exE1.pl /copy/ex/exe-1.txt > /bin/exe1out.txt

Why will this give an error?

~ cannot be used at the start of a line

.txt is not a valid extension in linux

> does not redirect output

The /bin directory has restricted access for security reasons to prevent students running unauthorised code on the server or modifyng or overwriting other programs in the directory

The following is a skeleton for a method called "maxPos":

public static int maxPos(int[] y, int first, int last) {
/* This method returns the position of the maximum element in the
* subsection of the array "y", starting at position
* "first" and ending at position "last".
*/

int bestSoFar = first;

xxx missing for loop goes here

return bestSoFar;

} // method maxPos

In this question, the missing "for" loop is to run "forwards". That is, the code should search the array from the low subscripts to the high subscripts. Given that, the correct code for the missing "for" loop is:

for (int i=last; i>first; i--) {
    if ( y[i] < y[bestSoFar] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[i] > y[bestSoFar] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
     if ( y[i] < bestSoFar ) {
        bestSoFar = i
     } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( y[i] > bestSoFar ) {
       bestSoFar = i;
    } // if
} // for

Explanation
a)

INCORRECT:

if (y[i] < y[bestSoFar]) ... This is setting bestSoFar to the index of the SMALLEST number so far, but this is MAXPOS, it needs to find the highest!

b)

CORRECT:

The code finds the maximum position in the array, searching forwards as intended.

c)

CORRECT:

The loop is running backwards.

d)

INCORRECT:

The if statement compares y[i] with the integer bestSoFar, not what is in the array at the position bestSoFar.

c)

INCORRECT:

Same as c) and d)

The following is a skeleton for a method called "maxPos":

public static int maxPos(int[] y, int first, int last) {
/* This method returns the position of the maximum element in the
 * subsection of the array "y", starting at position
 * "first" and ending at position "last".

 */

  int bestSoFar = first;

  xxx missing for loop goes here

   return bestSoFar;

In this question, the missing "for" loop is to run "backwards".  That is, the code should search the array from the high subscripts to the low subscripts.  Given that, the correct code for the missing "for" loop is:

for (int i=last; i>first; i--) { 
    if ( y[i] < y[bestSoFar] ) { 
       bestSoFar = i; 
   } // if 
} // for

for (int i=first+1; i<=last; i++) {
    if ( y[i] > y[bestSoFar] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[i] < bestSoFar ) {
       bestSoFar = i
    } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( y[i] > bestSoFar ) {
       bestSoFar = i;
    } // if
} // for

a)

INCORRECT:

if (y[i] < y[bestSoFar])  ... This is setting bestSoFar to the index of the SMALLEST number so far, but this is MAXPOS, it needs to find the highest!

b)

INCORRECT:

The loop starts at [first+1] ... This loop is not running backwards.

c)

CORRECT:

The code finds the maximum position in the array, searching backwards as intended.

d)

INCORRECT:

The if statement compares y[i] with the integer bestSoFar, not what is in the array at the position bestSoFar.

c)

INCORRECT:

Same as b) and d)

The following code for a method "minVal" contains a logic error on a single line in the method body, on one of the four lines indicated by comments:

public static int minVal(int[] y, int first, int last) {

/* This method returns the value of the minimum element in the
 * subsection of the array "y", starting at position
 * "first" and ending at position "last".
 */
 
  int bestSoFar = first;             // line 1
 
  for (int i=first+1; i<=last; i++) 
  {
    if ( y[i] < bestSoFar )          // line 2

       bestSoFar = y[i];             // line 3

  } // for

  return bestSoFar;                  // line 4

} // method minVal

Which one of the four lines indicated by the comments contains the logic error?

line 2

line 3

line 4

line 1 should be int bestSoFar = y[first];

This correct code assigns the value at y[first] into bestSoFar. This is because the other lines are using bestSoFar to remember the best VALUE seen thus far.

The following code for a method "minVal" contains a logic error on a single line in the method body, on one of the four lines indicated by comments:

public static int minVal(int[] y, int first, int last) {

/* This method returns the value of the minimum element in the
 * subsection of the array "y", starting at position
 * "first" and ending at position "last".
 */
 
  int bestSoFar = first;             // line 1
 
  for (int i=first+1; i<=last; i++)
  {
    if ( y[i] > bestSoFar )          // line 2

       bestSoFar = y[i];             // line 3

  } // for

  return bestSoFar;                  // line 4

} // method minVal

Which one of the four lines indicated by the comments contains the logic error?

line 1

line 3

line4

line 2 should be if ( y[i] < bestSoFar )

The following code for a method "minVal" contains a logic error on a single line in the method body, on one of the four lines indicated by comments:

public static int minVal(int[] y, int first, int last) {

/* This method returns the value of the minimum element in the
 * subsection of the array "y", starting at position
 * "first" and ending at position "last".
 */
 
  int bestSoFar = y[first];          // line 1
 
  for (int i=first+1; i<=last; i++)
  {

    if ( bestSoFar < y[i] )          // line 2

       bestSoFar = y[i];             // line 3

  } // for

  return bestSoFar;                  // line 4

} // method minVal

Which one of the four lines indicated by the comments contains the logic error?

line 1

line 3

line 4

line 2 should be if ( bestSoFar >  y[i] )

The < sign in this buggy line is looking for the MAXIMUM value in the array.

Does this compile?

yes

It depends on the version of the compiler

This doesn't compile.  Although 7.0 could be converted to an integer without loss of precision, Java will not perform any conversion of a double to an int without an explicit cast by the programmer.

What does this print?

double d = 8 / 10;
System.out.println(d);

d

0.8

2

None of the above

Integer division!  10 goes into 8 zero times, with a remainder of 8.  But since this is integer division, we only care about the quotient, which is zero!

After the assignments x = 27 and y = 12, what is returned by x%y?

2

2.25

3.0

None of the above

The % operation performs "mod" (modular division), which means "do the division but return the remainder rather than the quotient".

After the assignments x = 27 and y = 12, what is returned by not x <= y < x + y ?

True

1

0

An error

Python has an incredibly flexible syntax which allows expressions like x <= y < x + y (this statement would not compile in many other languages). 

If we break this expression down:

x+y is 39, so the expression is asking:

not 12 <= 27 < 39

12 <= 27 < 39 is True, as 27 is in fact between 12 and 39.  And if we apply not to True, we get False.

Which of the following assertions about the effect of int(my_var) is correct?

It modifies the value of my_var, truncating it to make it an integer.

It returns True if my_var is an integer; and False, otherwise.

It produces an error if my_var is not an integer.

None of the above

A is wrong because the int() function does not modify (mutate) its parameter

B is wrong because the int() function does not return a Boolean, it returns an int()

C is wrong because the int() function works with double/float inputs, which are not ints (although it will generate an error if invoked with a String, for example)

D is correct!  int() converts ints and doubles to an int, truncating any extra information (i.e. the decimal portion of a double), and will generate an error if called with a non-numeric value

The following methods are in Java's String class:

• int indexOf(int ch) - Returns the index within this string of the first occurrence of the specified character.
• int indexOf(int ch, int fromIndex) - Returns the index within this string of the first occurrence of the specified character, starting the search at the specified index.
• String substring(int beginIndex, int endIndex) - Returns a new string that is a substring of this string. The substring begins at the specified beginIndex and extends to the character at index endIndex - 1. Thus the length of the substring is endIndex-beginIndex.

Given these specifications, what does the following code print?

String s = "ichi,ni,san,go";
int i1 = s.indexOf(',');
int i2 = s.indexOf(',', i1);
System.out.println(s.substring(i1, i2));

The empty string

i1 is 4, and so is i2, since the second indexOf call begins searching at the position of the same comma that was found by the first indexOf call. Calling substring with identical parameters yields a 0-length String.

The following is a skeleton for a method called "minPos":

public static int minPos(int[] y, int first, int last) {
/* This method returns the position of the minimum element in the
* subsection of the array "y", starting at position
* "first" and ending at position "last".
*/

  int bestSoFar = first;

  xxx missing for loop goes here

  return bestSoFar;

} // method minPos

In this question, the missing "for" loop is to run "backwards". That is, the code should search the array from the high subscripts to the low subscripts. Given that, the correct code for the missing "for" loop is:

for (int i=last; i>first; i--) {
    if ( y[bestSoFar] < y[i] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( y[bestSoFar] < y[i] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[bestSoFar] < y[i] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( bestSoFar < y[i] ) {
       bestSoFar = i;
    } // if
} // for

a)
INCORRECT:
if (y[bestSoFar] < y[i])  ... This is setting bestSoFar to the index of the LARGEST number so far.

b)
INCORRECT:
The loop starts at first+1 ...not running backwards.

This loop is if (y[bestSoFar] < y[i])  ... This is setting bestSoFar to the index of the LARGEST number so far.

c)
INCORRECT:
if (y[bestSoFar] < y[i])  ... This is setting bestSoFar to the index of the LARGEST number so far.

d) CORRECT!

e)
INCORRECT:
The if statement compares y[i] with the integer bestSoFar, not what is in the array at the position bestSoFar.
The loop starts at first+1 ... This loop is not running backwards.

The following is a skeleton for a method called "minPos":

public static int minPos(int[] y, int first, int last) {
/* This method returns the position of the minimum element in the
 * subsection of the array "y", starting at position
 * "first" and ending at position "last".
 */

  int bestSoFar = first;

  xxx missing for loop goes here

  return bestSoFar;

} // method minPos

In this question, the missing "for" loop is to run "forwards". That is, the code should search the array from the high subscripts to the low subscripts. Given that, the correct code for the missing "for" loop is:

for (int i=last; i>first; i--) {
    if ( y[bestSoFar] < y[i] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[bestSoFar] > y[i] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( bestSoFar < y[i] ) {
       bestSoFar = i
    } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( bestSoFar > y[i] ) {
       bestSoFar = i;
    } // if
} // for

a)
INCORRECT:
The loop starts at last ... This loop is not running forwards.
if (y[bestSoFar] < y[i])  ... This is setting bestSoFar to the index of the LARGEST number so far.

b)
CORRECT!

c)
INCORRECT:
The loop starts at last ... This loop is not running forwards.

d)
INCORRECT:
The loop starts at last ... This loop is not running forwards.
The if statement compares y[i] with the integer bestSoFar, not what is in the array at the position bestSoFar.

e)
INCORRECT:
The if statement compares y[i] with the integer bestSoFar, not what is in the array at the position bestSoFar.
The loop starts at first+1 ... This loop is not running forwards.

Assume this Perl subroutine is called like this:

&compare(6, 4);

sub compare

{

  my $ret = 0;

  if($_[0] > $_[1])

  {

       $ret = 1;

   }

  elsif($_[0] < $_[1])

  {

       $ret = -1;

  }

  return $ret;

}

What will the subroutine return?

-1

0

undef

6 (the first parameter) is greater than 4 (the second parameter) so it returns 1

In this question, you are given a Perl regular expression that you are required to evaluate.  

There are no leading or trailing spaces in any of the text, nor are there any spaces in the regex.

Identify the answer which best matches the regex below:

/write/

Write your name at the top.

Your writing is hard to read.

Who sends handwritten letters anymore?

The expression generates a match for a sentence which contains the full string (case sensitive) given between the / / delimiters

In this question, you are given a Perl regular expression that you are required to evaluate.

There are no leading or trailing spaces in any of the text, nor are there any spaces in the regex.

Identify the answer which best matches the regex below:

/^[A-Z]\d/

ABC123

3Y3

a5D2

Must begin with an upper case letter followed by a digit.

An example of something that could be built using a ListADT is a structure that models:

The undo operation in a word processor

The back button in a web browser

the customers waiting to pay at the university dining hall

the computers at the university and the network that connects them

In ListADT, items can be added to or removed from the beginning, middle, or end of the structure. This is not well suited for choices A or B, where you need to remove only the most recently added item.

For choice C, you need to ensure that the item removed is always the one that was stored first, so ListADT won't work there either. 

Choice E would be best modeled by a nonlinear structure, and ListADT (like StackADT and QueueADT) is linear.

That leaves Choice D. A list of things to do can be linear -- one thing after another -- and it may be desirable to add new items at the beginning, middle, or end, depending on how important they are. 

Identify the bug in the following code (if any):

public boolean search(T item,MyList<T> list){ // 1

} // 3

The problem is not self-similar

There is a base case, but the problem does not get smaller

There are no bugs

None of the above

For a recursive solution to a problem, you need three things:

(1) a base case (where the problem can be solved without recursion)

(2) a self-similar problem (one that contains similar problem(s) to itself)

(3) a way of making the problem smaller so you get closer to the base case

Here (2) is satisfied -- lists contain smaller lists. (3) is satisfied by line 2 of the method. But there is no base case. 

Identify the bug in the following code (if any): 

public boolean search(T item, ListADT list){ // 1

   if (list == null) // 2
      return false; // 3
   else if (list.first()==item) // 4
      return true; // 5
   else // 6
      return this.search(item, list); // 7

} // 8

There is no base case

The problem is not self-similar

There are no bugs

None of the above

For a recursive solution to a problem, you need three things:
(1) a base case (where the problem can be solved without recursion)
(2) a self-similar problem (one that contains similar problem(s) to itself)
(3) a way of making the problem smaller so you get closer to the base case

Here (2) is satisfied -- lists contain smaller lists. (1) is satisfied by lines 2-5 of the method. But the recursive call in line 7 has the same parameter as the method itself (line 1), so the problem never gets smaller. 

The worst-case time complexity of the following Java method is:

public int fibonacci (int n) {
   if (n == 1) 
      return 1;
   else if (n == 2) 
      return 1;
   else if (n > 2) 

      return fibonacci(n-1)+fibonacci(n-2);

   else 
      return -1; // invalid input

}

O(1)

O(log n)

O(n)

O(n²)

This code is exponential, because it's doubly recursive. 

The worst-case time complexity of quicksort is:

O(1)

O(n)

O(n²)

none of the above

In the worst case, every time we partition the list, we divide it into two parts, one of size 0 and one of size n-1 (plus the pivot element). This would happen, for example, if all the elements of the list are equal, or if the list is already sorted and you choose the left-most element as your pivot. 

We'd have to partition the list n times, because each time the pivot element is the only one that gets put in place.  The first time we compare the pivot element with all n-1 other elements. The second time, we compare the new pivot with n-2 other elements, and so forth down to n - (n-1). So we do work proportional to 1+2+3+...+(n-1), or n(n-1)/2.

The following is a skeleton for a method called "minVal":

public static int minVal(int[] y, int first, int last) {

/* This method returns the value of the minimum element in the
* subsection of the array "y", starting at position
* "first" and ending at position "last".
*/
 
  int bestSoFar = y[first];
 

  xxx missing for loop goes here

  return bestSoFar;

} // method minVal

In this question, the missing "for" loop is to run "forwards". That is, the code should search the array from the low subscripts to the high subscripts. Given that, the correct code for the missing "for" loop is:

for (int i=last; i>first; i--) {
    if ( y[i] < bestSoFar ) {
       bestSoFar = y[i];
    } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( y[i] > y[bestSoFar] ) {
       bestSoFar = y[i];
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[i] > y[bestSoFar] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( bestSoFar < y[i] ) {
       bestSoFar = i
    } // if
} // for

a)
INCORRECT
The loop starts at last ... This loop is not running backwards.

b)
INCORRECT:
if  ( y[i] > y[bestSoFar] ) ... bestSoFar is storing a value, not a position.  In any event, this if condition is searching for the maximum value.

c)
INCORRECT:
The loop starts at last ... This loop is not running backwards.
if  ( y[i] > y[bestSoFar] ) ... bestSoFar is storing a value, not a position.  In any event, this if condition is searching for the maximum value.
bestSoFar = i; ... bestsoFar is being set to the position, not the value.

d)
INCORRECT:
The loop starts at last ... This loop is not running backwards.
if ( bestSoFar < y[i] ) ... this if condition is searching for the maximum value.
bestSoFar = i; ... bestsoFar is being set to the position, not the value.

e)
CORRECT!

The following is a skeleton for a method called "minVal":

public static int minVal(int[] y, int first, int last) {
/* This method returns the value of the minimum element in the
* subsection of the array "y", starting at position
* "first" and ending at position "last".
*/

  int bestSoFar = y[first];

  xxx missing for loop goes here

  return bestSoFar;

} // method minVal

In this question, the missing "for" loop is to run "backwards". That is, the code should search the array from the high subscripts to the low subscripts. Given that, the correct code for the missing "for" loop is:

for (int i=first+1; i<=last; i++) {
    if ( y[i] > y[bestSoFar] ) {
       bestSoFar = y[i];
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[i] > y[bestSoFar] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( bestSoFar < y[i] ) {
       bestSoFar = i
    } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( y[i] > bestSoFar ) {
       bestSoFar = i;
    } // if
} // for

a)

CORRECT!

b)

INCORRECT:

The loop starts at first+1 ... This loop is not running backwards.

if  ( y[i] > y[bestSoFar] ) ... bestSoFar is storing a value, not a position.  In any event, this if condition is searching for the maximum value.

c)

INCORRECT:

if  ( y[i] > y[bestSoFar] ) ... bestSoFar is storing a value, not a position.  In any event, this if condition is searching for the maximum value.

bestSoFar = i; ... bestsoFar is being set to the position, not the value.

d)

INCORRECT:

if ( bestSoFar < y[i] ) ... this if condition is searching for the maximum value.

bestSoFar = i; ... bestsoFar is being set to the position, not the value.

e)

INCORRECT:

The loop starts at first+1 ... This loop is not running backwards.

if  ( y[i] > y[bestSoFar] ) ...  this if condition is searching for the maximum value.

bestSoFar = i; ... bestsoFar is being set to the position, not the value.

The following is a skeleton for a method called "maxVal":

public static int maxVal(int[] y, int first, int last) {
/* This method returns the value of the maximum element in the
* subsection of the array "y", starting at position
* "first" and ending at position "last".
*/

int bestSoFar = y[first];

xxx missing for loop goes here

return bestSoFar;

} // method maxVal

In this question, the missing "for" loop is to run "forwards".  That is, the code should search the array from the low subscripts to the high subscripts.  Given that, the correct code for the missing "for" loop is:

for (int i=last; i>first; i--) {
    if ( y[i] < bestSoFar ) {
       bestSoFar = y[i];
   } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[i] > y[bestSoFar] ) {
       bestSoFar = i;
    } // if
} // for

for (int i=last; i>first; i--) {
    if ( y[i] < bestSoFar ) {
       bestSoFar = i;
    } // if
} // for

for (int i=first+1; i<=last; i++) {
    if ( y[i] > bestSoFar ) {
       bestSoFar = i;
    } // if
} // for

a)

INCORRECT:

The loop starts at  last ... it is NOT running forward.

if (y[i] < y[bestSoFar]) ... This is setting bestSoFar to the value of the SMALLEST number so far.

b)

CORRECT!

c)

CORRECT:

The loop starts at  last ... it is NOT running forward.

if ( y[i] > y[bestSoFar] ) ... bestSoFar is storing the minimum value, NOT the position of the minimum value.

bestSoFar = i  ... bestSoFar is being set to a postion, not the value at that poisition.

d)

INCORRECT:

The loop starts at  last ... it is NOT running forward.

if (y[i] < bestSoFar) ... This is lokking for theSMALLEST value.

e)

INCORRECT:

bestSoFar = i  ... bestSoFar is being set to a postion, not the value at that position.

Suppose you have the following partial code to sum up an array of ints:

int sum(int[] nums) {
  int sum = 0;
  ...
  return sum;
}

Which of the following does not correctly complete this method?

for (int i = 0; i < nums.length; ++i)
  sum += nums[i];

for (int i : nums)
  sum += i;

int i = 0;
while (i < nums.length) {
  sum += nums[i];
  ++i;
}

It appears in this solution that we are iterating through the list in reverse. However, we incorrectly increment the iterator, leading to an IndexOutOfBoundsException.