Canterbury QuestionBank

For the binary search algorithm implemented on a sorted list stored in an array, what is its running time?

O(1)

O(n)

O(n log₂ n)

O(n²)

Binary search repeately "throws away" half of the list still under investigation when looking for a given value in the list.  Hence the run time of the algorithm is the number of times a values can be divided in two, until one reaches the value 1: O(log₂ n)

Suppose we're modeling a person with just name and age. The notation {"Javier", 31} refers to a 31-year-old named Javier. Now, suppose we have this collection of five people:

{"Lupe", 29}

{"Dean", 29}

{"Lars", 28}

{"Javier", 31}

{"Di", 28}

Which of the following ordered collections is the result of applying a stable sort to this collection, where the sorting criteria orders by age?

{"Javier", 31}
{"Dean", 29}
{"Lupe", 29}
{"Di", 28}
{"Lars", 28}

{"Lars", 28}
{"Di", 28}

{"Dean", 29}

{"Lupe", 29}
{"Javier", 31}

{"Lars", 28}
{"Di", 28}
{"Dean", 29}

{"Lupe", 29}
{"Javier", 31}

{"Di", 28}

{"Lars", 28}
{"Dean", 29}

{"Lupe", 29}
{"Javier", 31}

A stable sort preserves the relative order of elements with the same keys. Thus, Lupe must appear before Dean and Lars must appear before Di. Only the correct answer maintains this order.

Which data structure provides direct access to elements using indexes?

a linked list

both

neither

If you declare an array in languages that have them, such as Pascal, C, C++, Java, etc., you can access an element of the array by giving the index of the value to be retrieved. 

The StackADT's pop operation:

adds a new item at the bottom of the Stack

returns without removing the top item on the Stack

adds a new item at the top of the Stack

returns true if the Stack is empty and otherwise false

"pop" is the traditional term for removing an element from a stack. By definition, the element removed from a stack is always the one that was added most recently, or the one at the "top."

The dequeue operation:

 adds a new item at the front of a queue

returns without removing the item at the front of a queue

adds a new item at the end of a queue

returns true if a queue is empty and otherwise false

dequeue is the name for the operation that removes an element from a queue. Specifically, it removes the item that was added *first* (just as the first person in a line gets served first). 

What does this function do?

void iFunction(char sz[])

{

     int iLen = 0;

     while ( sz[iLen])

      sz[iLen++] = '-';

}

Copies a string

Finds and returns a character in a string

Finds the length of a string

 Finds and returns the end of a string

The Function iterates through the array to the end, replacing each character with the "-" character

What will be printed?

public static void main(String [] args){

        int[] array = {1, 2, 3, 4, 1, 2, 3, 4};

        System.out.print( specialSum(array, 3));

}

public static int specialSum (int[] integerArray , int index){

        int sum = index % 2 ==0 ? integerArray [index]*2 : integerArray [index] +1;

        if( index == 0) return sum;

        return sum + specialSum(integerArray, index-1);

}

32

15

30

Consider this code segment:

boolean x = false;
boolean y = true;
boolean z = true;
System.out.println( (x || !y) && (!x || z) );

What value is printed?

true

Nothing, there is a syntax error

Since x is false and y is true, (x || !y) is false.  This forces the entire expression to be false, because of the && operator.

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

void main(void)

{

     static int aiTable[10] = {0,1,2,3,4,5,6,7,8,9};

     int i;

     for(i = 0; i < 10; i++)

     {

          if( !(aiTable[i] % 2))

               printf("%d", aiTable[i]);

     }

}

13579

01234

56789

0123456789

Modulus is the remainder of integer division of two numbers with the result placed somewhere.

The modulus function of a and b, a being the dividend and b being the divisor, is a - int(a/b) * b.

For example, using integer results...

47/4 = 11
47%4 = 3

Check it: 47 = 11*4 + 3

Source http://wiki.answers.com/Q/What_is_the_difference_between_division_and_modulus_in_%27C%27_language

In this case the negatively phrased line of code "if( !(aiTable[i] % 2))" is an alternative way of  expressing the more common phrasing of a modulus arithmetic expression as given below

If you wanted to know if a number was odd or even, you could use modulus to quickly tell you by asking for the remainder of the number when divided by 2.

#include <iostream>

using namespace std;

int main()

{

      int num;

     cin >> num;

     // num % 2 computes the remainder when num is divided by 2

     if ( num % 2 == 0 )

     {

           cout << num << " is even ";

     }

return 0;

}

The key line is the one that performs the modulus operation: "num % 2 == 0". A number is even if and only if it is divisible by two, and a number is divisible by another only if there is no remainder.

source: http://www.cprogramming.com/tutorial/modulus.html

In Java, which of the following is not considered to be part of the signature of a method?

Method name

Number of parameters

Types and order of parameters

All of the above are part of the signature

In Java the return type is not considered as part of the signature.  Why should I care?  If i want to use method overloading (have different methods with the same name) the methods must have unique signatures, and so i cannot have 2 methods with the same name that have the same number, type, and order of parameters that differ on return type.

Given the code

int x = 27;
int y = 12;

What is the value of the expression x%y?

2

2.25

3.0

None of the above.

In Java, the % operator means "remainder." So this question is asking, "What is the remainder when you divide 27 by 12?"   27 - (2*12) = 3, so the answer is 3.

Given the code

int x = 27;
int y = 12;

What is the value of the expression  x/y?

2.25

3

3.0

None of the above.

In Java, when we divide one int value by another, we get another integer. You can start by doing the usual division (which would give you 2.25 in this case) and then remove the decimal part. 

Suppose you have a binary search tree with no right children. Furthermore, key A is considered greater than key B if A.compareTo(B) >= 0. Which of the following explains how this tree may have ended up this way?

It was filled in ascending order.

The root value was the minimum.

All keys were identical.

The tree is a preorder tree.

If the greatest node was inserted first, with each successive node having a lesser key than its predecessor, we'd end up with all left children. Adding nodes with identical keys produces right children.

What is the logic error in the following implementation of sequential search?

1  def sequentialSearch(listOfValues):
2       target = input("value searching for: ")
3       listSize = len(listOfValues)
4       targetFound = False
5       targetLocation = 0
6       current = 0
7       while (current < listSize):
8            if (listOfValues[current] == target):
9                 targetFound = True
10               targetLocation = current

11          else:

12               targetFound = False
13          current = current + 1

14      if targetFound:
15           print "the target was found at location: ", targetLocation
16      else:
17          print "target was not found"

Line 10

Line 7

Line 8

None of the above.

The else clause resets targetFound if a match is ever found.  Hence, in effect, with this else clause present, only the test with the last element in the list is "remembered."

Which of the following lines of code will correctly read in the integer value foo?

scanf("%f", foo);

scanf("%f", &foo);

scanf("%f\n", foo);

(A) is the correct answer; %d is used for reading in integers. The \n in (D) is unnecessary. Finally, scanf requires a pointer to a variable's address -- hence the ampersand.

A printer is shared among several computers in a network. Which data structure is proper to keep the sent prints in order to provide service in turn?

Stack

Single Linked List

one dimensional array

Java virtual machine handles a chain of method calls. Which data structure is proper for this purpose?

Queue

single linked list

one dimensional array

Removing a node from a heap is

O(1)

O(N)

O(N log N)

O(N²)

The last node is moved into the empty spot, which may be the root, and it may trickle back down to the bottom level. The performance is based on the number of levels in the tree. As heaps are balanced, the performance is O(log N).

We need to keep track of the changes that a user makes when working with a word processor. Which data structure is more proper for this purpose?

Queue

Single Linked List

one dimensional array

Suppose you have a list of numbers stored in consecutive locations in a Java array. What is the worst-case time complexity of finding a given element in the array using linear search?

O(1)

O(log n)

O(n log n)

O(n²)

Linear search is O(n).

Which data structure has a better performance when customer offers needs to be stored/restored for an auction?

An array

A single linked list

A tree

Noor writes a program in C to evulate some Taylor series, to help her with her calculus homework. She remembers to #include<math.h> before calling the pow function. But when she compiles with gcc taylor.c, she gets an error that pow is undefined. What she should instead type in the command-line to compile successfully?

gcc taylor.c -01

gcc taylor.c -math

gcc taylor.c -o taylor

-lm will manually link the math library.

What node will be visited after A in a preorder traversal of the following tree?

S

D

I

public int factorial (int n) {
   if (n == 0) 
      return 1;
   else if (n > 0)
      return n * factorial(n - 1);
   else 
      return -1; // invalid input
}

The Big-Oh time complexity of this method is:

O(1)

O(log n)

O(n²)

none of the above

The factorial method will be called n times, so the time complexity is proportional to n.

Assuming "FRED" is an ASCII text file which opens correctly, what will be displayed by this code?

#define MAX 128

FILE *pFile = fopen("FRED", "r");

unsigned uCount = 0;

while(!feof(pFile))

{

     char ch;

     ch = fgetc(pFile);

     uCount++;

}

printf("%u", uCount);

The number of words in the file

The number of sentences in the file

The number of lines of text in the file

The number of words on the last line of text in the file

The function reads the file character by character and increments a counter on each read, the result of which is printed on reaching the end of file giving the total character count in the file

An array has been declared as shown then used to store the data in the table below.

int iTable[3][5]; /* Declaration */

27 32 14   9 26

74 42 30 15 19

41 63 48 20  3

What is the value of iTable [3] [4]?

3

B

19

20

The index values for the array start from 0 so iTable [3] [4] refers to the 4th row and the 5th column, where the 4th row does not exist

for additional explanation cf. http://www.tutorialspoint.com/cprogramming/c_multi_dimensional_arrays.htm

Which of the following is a list of Java class names that are both syntactically legal and obey the standard naming convention?

R2D2, Chameleon, public

r2d2, chameleon, public

R2D2, Iguana, _hello

none of the above

Choice (b) is correct, because all of the names start with an uppercase letter, followed by 0 or more letters, numbers, and/or underscores. 

When we use recursion to solve a problem, we have

1. a problem that contains one or more problems that are similar to itself
2. a version of the problem that is simple enough to be solved by itself, without recursion, and
3. a way of making the the problem simpler so that it is closer to (and ultimately the same as) the version in 2.

What is 2. called?

The simple case

The inductive case

The iterative case

None of the above

Base case is the term we use for the case that is simple enough to solve directly.   We probably lifted the term from induction proofs in Mathematics, which is fitting.

What will the following code output?

int arr[5];

int *p = arr;
printf("p is %p -- ", p);
++p;
printf("p is %p \n", p);

p is 0x7fffb04846d0 – p is 0x7fffb04846d1

p is 0x7fffb04846d0 – p is 0x7fffb04846d2

Segmentation fault

p will increase by the sizeof(int) == 4.

Consider the following short program, which does not meet all institutional coding standards:

void vCodeString(char szText[ ]); /* First line */

#include <stdio.h>

#include <string.h>

#define MAX_LEN 12

int main(void)

{

     char szData[MAX_LEN];

     printf("Enter some text to code: ");

     scanf("%s", szData);

     vCodeString(szData); /* Line 8 */

     printf("Coded string is %s\n", szData);

}

void vCodeString(char szText[ ])

{

     int i = -1;

     while(szText[++i])

     {

          szText[i] += (char)2;

     }

}

With the array size defined as MAX_LEN (or 12) bytes, what happens if I enter a word with more than 12 letters, such as hippopotamuses?

You will get a run time error

You will get a syntax error from the compiler

The array will be enlarged

Nothing - it is legal and perfectly normal.

Now, C provides open power to the programmer to write any index value in [] of an array. This is where we say that no array bound check is there in C. SO, misusing this power, we can access arr[-1] and also arr[6] or any other illegal location. Since these bytes are on stack, so by doing this we end up messing with other variables on stack. Consider the following example :

#include<stdio.h>

unsigned int count = 1;

int main(void)

{

int b = 10;

int a[3];

a[0] = 1;

a[1] = 2;

a[2] = 3;

printf("\n b = %d \n",b);

a[3] = 12;

printf("\n b = %d \n",b);

return 0;

}

In the above example, we have declared an array of 3 integers but try to access the location arr[3] (which is illegal but doable in C) and change the value kept there.

But, we end up messing with the value of variable ‘b’. Cant believe it?, check the following output . We see that value of b changes from 10 to 12.

$ ./stk

b = 10

b = 12

Source http://www.thegeekstuff.com/2011/12/c-arrays/

Suppose all of the computer's memory is available to you, and no other storage is available. Every time your array is filled to its capacity, you enlarge it by creating an array twice the size of the original, if sufficient memory is available, and copying over all elements. How large can your growable array get?

50% of memory

100% of memory

25% of memory

33% of memory

When the array consumes 33% of memory and needs to expand, it can do so. The new array will consume 66% of memory. After this, there is not enough room for a larger array.

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

h(x) = x mod 13

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

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

5

6

8

Which of the following is NOT a fundamental data type in C?

int

float

 short

 char

A String is not a primitive data type.  It can be thought of as an array of characters.

After the assignment statement
   String word = "entropy";
what is returned by
   word.substring(word.length());

"entropy"

"y"

an error

none of the above

word.substring(n) returns the substring of word that starts at index n and ends at the end of the String. If index n is greater than the index of the last character in the String, as it is here, substring simply returns the empty String. 

The worst-case time complexity of quicksort is:

O(1)

O(n)

O(n log n)

none of the above

In the worst case, every time quicksort partitions the list, it is divided 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 in the list are equal, or if the list is already sorted and you always choose the leftmost element as a pivot. 

Quicksort would 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 quicksort compares the pivot element with all n-1 other elements. The second time, quicksort compares the new pivot with n-2 other elements, and so forth down to n - (n-1). So it does work proportional to 1+2+3+...+(n-1), or n(n-1)/2.

The time complexity of linear search is:

O(1)

O(log n)

O(2ⁿ)

none of the above

The time required for linear search in the worst case is directly proportional to the amount of data. 

An NP-Complete problem is:

solvable, and the best known solution runs in polynomial time (i.e. feasible)

currently unsolvable, but researchers are hoping to find a solution.

provably unsolvable: it has been shown that this problem has no algorithmic solution.

NP-Complete problems typically have rather simplistic algorithmic solutions.  The problem is that these solutions require exponential time to run.  

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 "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] < 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=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 value of the SMALLEST number so far.

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.   

c)

INCORRECT

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

d)

CORRECT!

e)

INCORRECT:

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

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

What would the following line of code do with a form named frmMain?

frmMain.Caption = txtName.Text

Make the text “txtName” appear as the caption of the form.

B Execute the method Caption, passing txtName as a parameter.

Change the contents of the text box txtName to the caption of the form.

Generate a run time error. It is not possible to alter the caption of a form at run time.

The code assigns the contents of the text box to the caption for the form

Which one of the following methods should be made static?

public class Clazz {
  private final int num = 10;

  double a() {
    System.out.println(num);
    return c();
  }

  void b() {
    System.out.println(this);
  }

  double c() {
    double r = Math.random();
    System.out.println(r);
    return r;
  }

  void d() {
    a();
    a();
  }

  int e() {
    return num;
  }
}

a

b

d

e

Method c() does not depend on the invoking instance or its instance variables.

What output will the following code fragment produce?

public void fn()
{
    int grade = 91;
    int level = -1;
    if (grade >= 90)
        if (level <= -2)
            System.out.println("A-level");
    else
        System.out.println("B-status");
}

A-level

B-status

"A-level"

"B-status"

Despite the indentation, no braces appear around the body of either if statement's branch(es). As a result, the else is associated with the second (inner) if. Since the outer if statement's condition is true, but the inner if statement is false (and it has no else branch), no output is produced.

What output will the following code fragment produce?

public void fn()
{
    int grade = 81;
    int level = -3;
    if (grade >= 90)
        if (level <= -2)
            System.out.println("A-level");
    else
        System.out.println("B-status");
}

A-level

B-status

"A-level"

"B-status"

Despite the indentation, no braces appear around the body of either if statement's branch(es). As a result, the else is associated with the second (inner) if. Since the outer if statement's condition is false, no output is produced.

What output will the following code fragment produce?

public void fn()
{
    int grade = 81;
    int level = -1;
    if (grade >= 90)
        if (level <= -2)
            System.out.println("A-level");
    else
        System.out.println("B-status");
}

A-level

B-status

"A-level"

"B-status"

Despite the indentation, no braces appear around the body of either if statement's branch(es). As a result, the else is associated with the second (inner) if. Since the outer if statement's condition is false, no output is produced.

Consider the struct:

struct book{

    char title[50];
    int isbn;
};

Assuming no address padding, what will sizeof(struct book) return?

12

50

204

8

sizeof(the array) + sizeof(the int) = 50 + 4.

What will this code output on 64-bit Linux?

char vals[10];

1

4

10

80

Size of the pointer.

A compiler error existed in this code. Why is that happening?

public class test {

     int testCount;

     public static int getCount(){

          return testCount;

     }

     public test(){

         testCount ++;

     }

}

testCount has not been initialized.

testCount has never been used.

testCount’s access modifier is not public.

Which of the following choices would best be modeled by a class, followed by an instance of that class?

Sweden, Country

Country, ScandinavianCountry

Sweden, Norway

Sweden, Linnaeus

Choice B is wrong because the items listed are object, class, not class, object. Choice C is wrong, because the items listed are class,subclass, not class,object. Choices D and E are wrong because in each case, the items listed are both concrete objects. 

The following method, called maxRow(), is intended to take one parameter: a List where the elements are Lists of Integer objects. You can think of this parameter as a matrix--a list of rows, where each row is a list of "cells" (plain integers). The method sums up the integers in each row (each inner list), and returns the index (row number) of the row with the largest row sum. Choose the best choice to fill in the blank on Line 8 so that this method works as intended:

public static int maxRow(List<List<Integer>> matrix)
{
    int maxVec = -1;                                // Line 1
    int maxSum = Integer.MIN_VALUE;                 // Line 2

    for (int row = 0; row < __________; row++)      // Line 3
    {
        int sum = 0;                                // Line 4
        for (int col = 0; col < __________; col++)  // Line 5
        {
            sum = sum + __________;                 // Line 6
        }
        if (___________)                            // Line 7
        {
            maxSum = __________;                    // Line 8
            maxVec = __________;                    // Line 9
        }
    }
    return maxVec;                                  // Line 10
}

The local variable maxSum is used to keep track of the maximum row sum seen so far, as the outer loop progresses across all rows in the matrix.  The inner loop computes the sum of all cells in the current row, which is stored in the local variable sum.  If the current row's sum is larger than the maximum seen so far, the variable maxSum should be updated to be sum.

Given the following Java class declaration:

public class T2int
{
    private int i;

    public T2int()
    {
        i = 0;
    }

    public T2int(int i)
    {
        this.i = i;
    }

    public int get()
    {
        return i;
    }
}

The following method, called rangeSum(), is intended to take three parameters: a List of T2int objects, plus the low and high end of a range within the list. The method computes the sum of the values in the List that are within the "range" (but not including the range end values). Choose the best choice to fill in the blank on Line 8 so that the method will work as intended:

public int rangeSum(List<T2int> list, int low, int high)
{
    int num = 0;                                 // Line 1
    int sum = 0;                                 // Line 2

    for (int idx = 0; idx < list.size(); idx++)  // Line 3
    {
        int ival = list.get(idx).get();          // Line 4
        if (__________)                          // Line 5
        {
            num++;                               // Line 6
            sum = __________;                    // Line 7
        }
    }
    return __________;                           // Line 8
}

The method should return the sum of all of the list elements that are within the specified range.  From examining the body of the loop, it is clear that this value is accumulated in the local variable sum.

Consider the following class definition:

import java.util.Scanner; // 1

public class SillyClass2 { // 2
   private int num, totalRed, totalBlack; // 3
   public SillyClass2 () { // 4
      num = 0; // 5
      totalRed = 0; // 6
      totalBlack = 0; // 7
      this.spinWheel(); // 8
      System.out.print("Black: " + totalBlack); // 9
      System.out.println(" and red: " + totalRed); // 10
   } // 11

   public void spinWheel () { // 12

      Scanner kbd = new Scanner(System.in); // 13
      System.out.println("Enter 1 or 0, -1 to quit."); // 14
      num = kbd.nextInt(); // 15
      while (num >= 0) { // 16
         if (num == 0) // 17
            totalRed++; // 18
         else if (num == 1) // 19
            totalBlack++; // 20
         else System.out.println("Try again"); // 21
         System.out.println("Enter 1 or 0, -1 to quit)."); // 22
         num = kbd.nextInt(); // 23
      } // 24
      System.out.println("Thanks for playing."); // 25
   } // 26
} // 27

Which sequence of inputs will cause line 21 to be executed?

-1

0   1   -1

0   1   1   0   -1

1   1   1   0   -1

Answers A, B, C, and E are incorrect because they contain no inputs greater than 1. Answer D does contain an input greater than 1, and that input is after a 0 (which causes the loop to be entered) and before the -1 (which causes the loop to be exited). 

Which method call is an efficient and correct way of calling methods compute_1 and compute_2 inside main method?

public class test {

       public static void compute_1(){}

       public void compute_2(){}

       public static void main(String [] Args){}

}

test t = new test();

t.compute_1();

t.compute_2();

compute_1();

compute_2();

test.compute_1();

test.compute_2();

What output will the following code fragment produce?

public void fn()
{
    int grade = 91;
    int level = -3;
    if (grade >= 90)
        if (level <= -2)
            System.out.println("A-level");
    else
        System.out.println("B-status");
}

B-status

"A-level"

"B-status"

no output is produced

Despite the indentation, no braces appear around the body of either if statement's branch(es).  As a result, the else is associated with the second (inner) if.  Still, both if statement conditions are true, so the output is A-level.

Suppose you’re on a project that is writing a large program. One of the programmers is implementing a Clock class; the other programmers are writing classes that will use the Clock class. Which of the following aspects of the public methods of the Clock class do not need to be known by both the author of the Clock class and the programmers who are using the Clock class?

The methods’ names

The methods’ return types

The methods' parameter types

What the methods do

This question addresses the principle of encapsulation. All these items must be known to the author of the Clock class. In order to use the class, the other programmers must know what the methods do, and must know their names, parameter types, and return values. The method bodies, on the other hand, are hidden from the users.

Consider these two Java methods:

public void fuzzy(int x)
{
    x = 73;
    System.out.print(x + " ");
}

public void bunny()
{
    int x = 29;
    fuzzy(x);
    System.out.println(x);
}

What is printed when bunny() is called?

29 29

73 73

29 73

none of these

Remember that in Java, parameters are passed by value.  Although a method may assign to a parameter, this change only affects the method's local copy of the parameter and is not visible outside the method (i.e., does not affect the actual value passed in by the caller).

Given the following Java class declaration:

public class T2int
{
    private int i;

    public T2int()
    {
        i = 0;
    }

    public T2int(int i)
    {
        this.i = i;
    }

    public int get()
    {
        return i;
    }
}

The following method, called rangeSum(), is intended to take three parameters: a List of T2int objects, plus the low and high end of a range within the list. The method computes the sum of the values in the List that are within the "range" (but not including the range end values). Choose the best choice to fill in the blank on Line 5 so that the method will work as intended:

public int rangeSum(List<T2int> list, int low, int high)
{
    int num = 0;                                 // Line 1
    int sum = 0;                                 // Line 2

    for (int idx = 0; idx < list.size(); idx++)  // Line 3
    {
        int ival = list.get(idx).get();          // Line 4
        if (__________)                          // Line 5
        {
            num++;                               // Line 6
            sum = __________;                    // Line 7
        }
    }
    return __________;                           // Line 8
}

The local variable ival contains the integer value stored in the current position in the list.  To check this value to ensure it is within the desired range, use the condition (ival > low) && (ival < high).

What terminates a failed linear probe in a non-full hashtable?

The end of the array

A deleted node

A node with a non-matching key

Revisiting the original hash index

A null entry marks the end of the probing sequence. Seeing the end of the array isn't correct, since we need to examine all elements, including those that appear before our original hash index. A node with a non-matching key is what started our probe in the first place. Revisiting the original hash index would mean we looked at every entry, but we could have stopped earlier at the null entry. The purpose of leaving a deleted node in the table is so that probing may proceed past it.

If a hashtable's array is resized to reduce collisions, what must be done to the elements that have already been inserted?

All items must be copied over to the same indices in the new array.

The existing items can be placed anywhere in the new array.

The hashCode method must be updated.

Since calculating a node's position in the hashtable is a function of the node's key's hashcode and the array size, all items must be reinserted.

Consider the code below; what value will p have at the end?

int *p, i;

 i = 2;
 p = &i;
 *p = 5;

i++;

2

5

6

0x567def0000

0x567def0004

The memory address of i; p points to i

The following method, called maxRow(), is intended to take one parameter: a List where the elements are Lists of Integer objects. You can think of this parameter as a matrix--a list of rows, where each row is a list of "cells" (plain integers). The method sums up the integers in each row (each inner list), and returns the index (row number) of the row with the largest row sum. Choose the best choice to fill in the blank on Line 7 so that this method works as intended:

public static int maxRow(List<List<Integer>> matrix)
{
    int maxVec = -1;                                // Line 1
    int maxSum = Integer.MIN_VALUE;                 // Line 2

    for (int row = 0; row < __________; row++)      // Line 3
    {
        int sum = 0;                                // Line 4
        for (int col = 0; col < __________; col++)  // Line 5
        {
            sum = sum + __________;                 // Line 6
        }
        if (___________)                            // Line 7
        {
            maxSum = __________;                    // Line 8
            maxVec = __________;                    // Line 9
        }
    }
    return maxVec;                                  // Line 10
}

The local variable sum represents the sum of all cell values in the current row, which is computed by the inner loop in the code.  The if test on Line 6 checks whether to update the local variables maxSum and maxVec, which represent information about the largest row sum found so far.  This should happen when sum > maxSum.

Which sentence is NOT correct?

In a class, you can have a method with the same name as the constructor.

In a class, you can have two methods with the same name and return type, but different number and type of input arguments.

In a class you can have two constructors with the same name.

You see the expression n = -15 in some code that successfully compiles. What type can n not be?

int

float

short

long

Chars can only hold integers in [0, 65535]. Assigning an int variable to a char requires an explicit cast. Assigning an int literal in this interval does not require a cast. Assign an int literal outside of this interval is compile error.

After the assignment signal = ’abracadabra’, what is returned by signal[len(signal)]?

'a'

'abracadabra'

11

none of the above

This is the classic way to go one character over the edge of a String.

Which of the following sorting algorithms has a best-case time performance that is the same as its and worst-case time performance (in big O notation)?

Insertion sort

Bubble sort

None of the above

Selection sort has both O(n^2) worst and best case.

What advantage does using dummy nodes in a linked list implementation offer?

Reduced storage needs.

Easier detection of the list's head and tail.

Simplified iteration.

Dummy nodes consume a little more space, and they don't simplify iteration or bounds detection any. They do reduce the special casing that would otherwise need to be done when updating forward and backward links on an insertion.

How many asterisks will be printed as a result of executing this code?

int counter = 0, N = 10;

while (counter++ < N){

    if (counter%2 == 0)

        continue;

    System.out.print("*");

}

none, infinite loop.

10

1

Given the following Java class declaration:

public class T2int
{
    private int i;

    public T2int()
    {
        i = 0;
    }

    public T2int(int i)
    {
        this.i = i;
    }

    public int get()
    {
        return i;
    }
}

The following method, called rangeSum(), is intended to take three parameters: a List of T2int objects, plus the low and high end of a range within the list. The method computes the sum of the values in the List that are within the "range" (but not including the range end values). Choose the best choice to fill in the blank on Line 7 so that the method will work as intended:

public int rangeSum(List<T2int> list, int low, int high)
{
    int num = 0;                                 // Line 1
    int sum = 0;                                 // Line 2

    for (int idx = 0; idx < list.size(); idx++)  // Line 3
    {
        int ival = list.get(idx).get();          // Line 4
        if (__________)                          // Line 5
        {
            num++;                               // Line 6
            sum = __________;                    // Line 7
        }
    }
    return __________;                           // Line 8
}

Since the method computes the sum of all values found, and the local variable sum is used to accumulate this total, sum should be updated to sum + ival.

Consider the following Python code:

number = int(input("Enter a positive number: "))
while number > 1:
   if (number % 2 == 1):
      number = number * 3 + 1
   else:
      number = number/2
   print number
   if number == 1:
      break
   else:
      print "The end"

Given the input ’8’, what output is produced by the program?

an error

'The end'

4

2

1

The end

none of the above

Basically just trace the code.

Chris implements a standard sorting algorithm that sorts the numbers 64, 25, 12, 22, 11 like so:

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64

Which sorting algorithm is this?

Inserton sort

Bubble sort

Merge sort

In the first line, we see the min is pulled from the end of the array so we know it's selection sort.

If the following hierarchy of exception is defined by a user, which option is the correct order of catching these exceptions?

class firstLevelException extends Exception{}

class secondLevelException_1 extends firstLevelException{}

class secondLevelException_2 extends firstLevelException{}

class thirdLevelException extends secondLevelException_1{}

A.

try{

     //code was removed

}

catch (firstLevelException e){

      e.printStackTrace();

}

catch (secondLevelException_1 e){

     e.printStackTrace();

}

catch (secondLevelException_2 e){

     e.printStackTrace();

}

catch (thirdLevelException e){

     e.printStackTrace();

}

try{

     //code was removed

}

catch (firstLevelException e){

     e.printStackTrace();

}

catch (secondLevelException_2 e){

     e.printStackTrace();

}

catch (secondLevelException_1 e){

      e.printStackTrace();

}

catch (thirdLevelException e){

     e.printStackTrace();

}

try{

     //code was removed

}

catch (thirdLevelException e){

     e.printStackTrace();

}

catch (firstLevelException e){

     e.printStackTrace();

}

catch (secondLevelException_2 e){

     e.printStackTrace();

}

catch (secondLevelException_1 e){

     e.printStackTrace();

}

You see the expression n = 47 in some code that successfully compiles. What type can n not be?


int

double

float

byte

Ints cannot be stored in Strings directly.

Which sentence is NOT correct?

If you define a variable as a final, you will never be able to change its.

If you define a method as a final, you will never be able to override it.

If you define a class as a final, you will never be able to extend it.

What would be the output?

public class test {

    static int testCount = 0;

    public test(){

        testCount ++;

    }

    public static void main(String [] Args){

        test t1 = new test();

        System.out.println(t1.testCount);

        test t2 = new test();

        System.out.println(t1.testCount + " "+ t2.testCount);

        test t3 = new test();

        System.out.println(t1.testCount+ " "+ t2.testCount+ " "+ t3.testCount);

   }

}

0

0 0

0 0 0

1

1 1

1 1 1

1

2 3

4 5 6

Consider the code below; what value will i have at the end?

int *p, i;

 i = 2;
 p = &i;
 *p = 5;
 i++;

2

5

3

8

p updates i

Lennox has a method:
void dele_root(struct node **root)

{
    free(*root);
    *root = NULL;
}

What is most likely to happen?

Deletes a copy of root (will not have an effect outside the function)

Segfault

A lot of crazy stuff will be printed

This will free what root is pointing to; it is a pesumably valid memory location and hence won't segfault or core dump.

Consider the code below; what value will i have at the end of the code?

int *p, i;

 i = 3;
 p = &i;
 (*p)++;
 i++;

3

4

6

8

i is incremented twice, once through p

Consider the code below; fill in the table below of what values p and i will have at the end of the code.
int *p, i;

 i = 3;
 p = &i;
 (*p)++;
 i++;

0x567def0001

5

0x567def0000

3

0x567def0004

p gets i's address and the (*p)++ does not change it.

A compiler error existed in this code. Why is that happening?

public class test {

      static int testCount;

      public int getCount(){

          return testCount;

      }

      public test(){

          testCount ++;

      }

      public static void main(String [] Args){

          System.out.print(getCount());

      }

}

testCount has not been initialized

testCount as a static variable cannot be referenced in a non-static method such as getCount() or a constructor such as test().

testCount’s access modifier is not public.

The following method, called maxRow(), is intended to take one parameter: a List where the elements are Lists of Integer objects. You can think of this parameter as a matrix--a list of rows, where each row is a list of "cells" (plain integers). The method sums up the integers in each row (each inner list), and returns the index (row number) of the row with the largest row sum. Choose the best choice to fill in the blank on Line 9 so that this method works as intended:

public static int maxRow(List<List<Integer>> matrix)
{
    int maxVec = -1;                                // Line 1
    int maxSum = Integer.MIN_VALUE;                 // Line 2

    for (int row = 0; row < __________; row++)      // Line 3
    {
        int sum = 0;                                // Line 4
        for (int col = 0; col < __________; col++)  // Line 5
        {
            sum = sum + __________;                 // Line 6
        }
        if (___________)                            // Line 7
        {
            maxSum = __________;                    // Line 8
            maxVec = __________;                    // Line 9
        }
    }
    return maxVec;                                  // Line 10
}

The local variable maxVec is used to keep track of the row number of the maximum row sum seen so far, as the outer loop progresses across all rows in the matrix.  The inner loop computes the sum of all cells in the current row, which is stored in the local variable sum.  If the current row's sum is larger than the maximum seen so far, the variable maxVec should be updated to be row.

Consider the following classes:

public class A
{
    private int myNum;
    public A(int x)            { myNum = x;    }
    public int getNumber()     { return myNum; }
    public String getLetters() { return "A";   }
    public String getMessage()
    {
        return getLetters() + "-" + getNumber();
    }
}

public class AB extends A
{
    public AB(int x)           { super(x + 1); }
    public int getNumber()     { return super.getNumber() + 1; }
    public String getLetters() { return "AB";  }
}

What is the output of the following code segment?

A test = new AB(0);

A-0

A-2

AB-0

AB-1

The object created is an instance of class AB, despite the static type of the variable test. Because of the constructor defined in AB, the object's myNum field will be initialized with the value 1.  Because of polymorphism, when getMessage() calls getLetters(), the definition of the method in AB will be used, returning "AB".  Similarly, when getMessage() calls getNumber(), the definition of the method in AB will be used, returning 2.

Which data structure uses less space per object?

a linked list

they are both the same

In a linked list, you create a Node for each element that contains not only the element but a link to the next Node. In addition, you create a List object that contains additional fields such as a link to the first Node in the list and (often) the size of the list. In an array, you store only the elements, not a Node or a link to the next Node. 

Which code snippet is tail recursive?

int sum(int x)
{
    if(x == 1)

         {
         return x;

         }
    return x + sum(x - 1);

A) requires the call to sum() to be completed before adding x to it.

When deleting a node with both left and right children from a binary search tree, it may be replaced by which of the following?

its left child

its right child

its preorder successor

its postorder successor

A common choice for the replacement node is deleted node's right child's leftmost descendent. This descendent is the deleted node's inorder successor.

Suppose you are writing a program for a robot that will go around a building and clean the floor. Your program will contain, among other things, a Robot class and a Building class (with information about the layout of the building). The Building class is also used in a different program for scheduling maintenance of various parts of the building. 

The relationship between your Robot class and your Building class is best modeled as:

a class-subclass relationship

a subclass-class relationship

a whole-component relationship

A and B are wrong, because a Building object doesn't share all the properties and behaviors of a Robot object (or vice versa). D is wrong because the Building object is not part of the Robot object (unlike the Robot's wheels, for example). The two classes are sometimes part of different programs and sometimes work together -- a peer relationship. 

What is the worst-case time performance of heapsort?

O(n)

O(lgn)

O(n2)

What is output from the following section of code?

int i = 4;

int j = i - 1;

printf("%d bows = %d wows", i, j+1);

3 bows = 4 wows

3 bows = 5 wows

 4 bows = 5 wows

E 4 bows = 3 wows

Through the printf function the decimal integer values defined by the %d field specifiers are replaced by the values for i and j resulting from the expression. The value of variable j is both decremented and incremented to remain equivalent to that of variable i when printed.

Read the following method skeleton and choose the best expression to fill in the blank on line 4 so that the method will behave correctly:

/**
* Takes a string reference and counts the number of times
* the character 'A' or 'a' appears in the string object.
* @param aString   String reference to object containing chars.
* @precondition    aString is not null (you may assume this is true).
* @return          The number of times 'A' or 'a' appears in the string.
*/
public static int countAs(String aString)  // line 1
{
    int counter = __________;              // line 2
    int totalA = 0;                        // line 3
    while (counter < __________)           // line 4
    {
        if ( __________.equals("A") )      // line 5
        {
            totalA = totalA + __________;  // line 6
        }
        counter++;                         // line 7
    }
    return __________;                     // line 8
}

The variable counter is being used as an index into the string that is being examined, and from line 7 it is clear that this index is increasing on each loop iteration, moving from left to right.  Because the loop test uses the < operator, the correct upper limit is aString.length().  Remember that strings provide a length() method for obtaining their length (size() is used for containers like lists and maps, and length written as a field reference instead of a method call is used for arrays).

Consider the code
int i, *q, *p;
p = &i;
q = p;
*p = 5;

Which of the following will print out “The value is 5.”?

printf("The value is %d", &i);

printf("The value is %d", p);

printf("The value is %d", *i);

p and q are currently "sharing" --- they both point to the same variable (i).

What order must elements 1, 2, 3, 4, 5, 6, and 7 be inserted in a binary search tree such that the tree is perfectly balanced afterward?

4 1 2 3 5 6 7

2 1 3 4 6 5 7

1 2 3 4 5 6 7

2 1 3 6 5 7 4

The middle element 4 will need to be the root, so that must be inserted first. The middle elements of the remaining halves must be 4's children, so 2 and 6 must be inserted next. (Their relative order does not matter.) The last four elements can be inserted in any order.

Which algorithm does the following code implement?

def mystery(target, listOfValues):
     beginning = 0
     end = len(listOfValues)
     found = False
     while (! found and (beginning <= end)):
          middle = (beginning + end) / 2
          if (listOfValues[middle] == target):
               found = True
               print "Found it at location: ", middle
          else:
               if (target < listOfValues[middle]):
                    end = middle -1
               else:
                    beginning = middle + 1

     if (! found):
     print "Item not found"

Short Sequential Search

Sequential Search

Bubble Search

None of the above.

This a classic implementation of binary search.

What abstract data type is best suited to help us implement a breadth-first search?

priority queue

stack

hashtable

array-based list

In a breadth-first search, we visit the starting element, its neighbors, its neighbors' neighbors, and so on. We want to make sure we visit the neighbors of the elements we saw earliest before we visit the neighbors of elements we saw later. This suggests a first-in, first out approach.

This sorting algorithm repeatedly examines neighboring elements, swapping those pairs that are out of order.

selection sort

insertion sort

quick sort

merge sort

Bubble sort operates by reordering neighbors.

The enqueue operation:

adds a new item at the front of the queue

returns without removing the item at the front of the queue

removes and returns the item at the front of the queue

returns true if the queue is empty and otherwise false

enqueue is the name for the operation that adds an element to a queue. Specifically, it adds each item to the end of the queue (just like standing in line). 

If Matthew is entering the values 1, 2, 3, 4, 5 into a complete tree, where insertion happens in level-order, in what order should he enter the values so he produces a binary search tree?

1, 2, 3, 4, 5

3, 1, 5, 2, 4

1, 3, 2, 5, 4

Only B will produce a complete BST.

Consider the following code:

if (!somethingIsTrue())
{
    return true;
}
else
{
    return false;
}

Which replacement for this code will produce the same result?

none of these

The method somethingIsTrue() must return a boolean value, because of the way it is used in the if statement's condition.  If it returns the value false, the if statement will cause the value true to be returned; otherwise, the if statement will cause the value false to be returned.  Therefore, the entire if statement is equivalent to return !somethingIsTrue();.

You are storing a complete binary tree in an array, with the root at index 0. At what index is node i's right child?

2i

2i + 1

i / 2 + 1

(i - 1) / 2

You've got a byte variable holding the value 127. You add 1 with byte += 1. What happens?

It becomes a short with value 128.

An OverflowException is raised.

It remains a byte and stays at the value 127.

It remains a byte and takes on the value 0.

When you exceed the maximum value of an integral type, you wrap around to other extreme. Bytes range from -128 to 127.

What is the size of the largest min-heap which is also a BST?

2

4

3

You cannot add a left child to the root because it would break the BST/min-heap property.

Which of the following is true about both interfaces and abstract classes?

They do not have constructors

All of their methods are abstract

They can have both abstract and non-abstract methods

They can be used to model shared capabilities of unrelated classes

Abstract methods have constructors, interfaces do not

An anstract class can include both abstract and non-abstract methods, while all methods in interfaces are abstract

An abstract class can model shared capabilities of classes, but only those who share the abstract class as an ancestor (so related), whereas there is no such restriction on interfaces.

Jacob has written some code using our standard linked list node definition (it has an int val and a struct node *next, in that order ):

struct node *my_node = malloc(sizeof(struct node));

my_node->val = 4;
my_node->next = NULL;
struct node **ptr_node = &my_node;
*(*ptr_node)++;

If the value of my_node is initially 0x50085008, what will the value of my_node most likely be after this code?

0x50085008

0x50085010

0x5008500C

You would it expect it to be 0x50085014 (0x50085008 + size of int + size of pointer), but C actually does address padding, pushing it up to 0x50085018, which is wha you would see if you run the code.

A coworker suggests that when you delete a node from a hashtable that you just set it to null. What is your response?

Yes, that way the garbage collector can reclaim the memory.

Yes, that will speed up probing.

No, the user may have alias references to the node.

When using probing to resolve collisions, the probing algorithm walks along the probing sequence until it finds a null element. If nulls appear in the wrong places, probing may terminate earlier than it should.