Canterbury QuestionBank

Suppose you are trying to choose between an array and a singly linked list to store the data in your program. Which data structure must be traversed one element at a time to reach a particular point?

an array

both

neither

In a basic linked list, each element is connected to the one after it. To reach a given element, you must start with the first node, if it's not the one you want, follow the link to the next one, and so forth until you reach the end of the list. (These are called "singly linked lists"; it is also possible to construct a doubly linked list, where each node is connected to the previous *and* the next element.) 

Richard has the following struct:

struct node{

    int val;
    struct node *next;
};

And he creates a node:
struct node **ptr = &( malloc(sizeof(struct node)) );

Which of the following will NOT set ptr’s associated val to 6?

(**ptr).val = 6

(*ptr)->val = 6

***ptr is not useful here

Consider the following recursive method:

public int examMethod(int n) {
   if (n == 1) return 1;
   else return (n + this.examMethod(n-1));
}

What value is returned by the call examMethod(16)?

1

16

None of the above.

This method returns the sum of the numbers from 1 to the parameter n (as long as n is greater than or equal to 1). 

Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

s + m

s − m

m − s

s/m

The load factor is the number of elements in the array, divided by the size of the array. It gives you an idea of how full the hashtable is. 

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13 ... Any term (value) of the sequence that follows the first two terms (0 and 1) is equal to the sum of the preceding two terms. Consider the following incomplete method to compute any term of the Fibonacci sequence:

public static int fibonacci(int term)
{
    int fib1 = 0;          // Line 1
    int fib2 = 1;          // Line 2
    int fibn = 0;          // Line 3

    if (term == 1)         // Line 4
    {
        return fib1;       // Line 5
    }
    if (term == 2)         // Line 6
    {
        return fib2;       // Line 7
    }

    for (__________)       // Line 8: loop to the nth term
    {
        fibn = __________; // Line 9: compute the next term
        fib1 = __________; // Line 10: reset the second preceding term
        fib2 = __________; // Line 11: reset the immediate preceding term
    }
    return fibn;           // Line 12: return the computed term
}


Choose the best answer to fill in the blank on line 8.

From the question, it is clear that the terms in the sequence are numbered starting at 1.  The two base cases cover terms 1 and 2, and the loop must then repeat (term - 2) times in total.  This will be achieved if the initial value on the loop counter is 1.

Which of these relationships best exemplify the "IS-A" relationships in object-oriented programming (OOP)?

Empire State Building IS-A Building

Angry Cat IS-A Cat

(Note that "Angry Cat" is a specific cat that has become an online internet meme)

All of the above

None of the above

A and C are wrong because the Empire State Building would be best be described as an instance of the category Cuilding, while Angry Cat is an instance of the category Cat.

B is correct because Cat is a sub-category of Mammal, which best exemplifies the IS-A relations.  In OOP, the IS-A relationship is used to denote relationships between classes, which are sort of like categories.

What does this print when x is assigned 1?

if (x==1) {
   System.out.println("x is 1");
} if (x==2) {
   System.out.println("x is 2");
} else {
   System.out.println("not 1 or 2");
}

x is 1

x is 2

x is 1

x is 2

x is 2

not 1 or 2

This code snipped does not have an else-if!  It may as well be written like this:

if (x==1) {
   System.out.println("x is 1");
}

if (x==2) {
   System.out.println("x is 2");
} else {
   System.out.println("not 1 or 2");
}

So when x==1, clearly we get "x is 1" printed, bu since 1 does not equal 2, we also get "not 1 or 2" with the else.

Be aware of when you are using an if, and when are are using an else-if, because they are quite different!

In C, which of the following will return 1, if s1 = "hi" and s2 = "hi"? Circle all that apply.

s1 == s2

strlen(s1)

s1 == "hi"

C is not Python! Only strcmp will do what Python and similar languages would do. (My CS2 students come into C having learnt Python.)

Inserting a node into a heap is

O(1)

O(N)

O(N log N)

O(N²)

Inserting a node involves putting the new node into the bottom level of the heap and trickling up, possibly to the root level. Since heaps are balanced and the number of levels is log N, the performance is O(log N).

Consider the following Java method:

public void printMenu(){
   System.out.println("Choose one of the following options:");
   System.out.println("1) Display account balance");
   System.out.println("2) Make deposit");
   System.out.println("3) Make withdrawal");
   System.out.println("4) Quit");
} 

Select the best reason for making this a separate method with a name, instead of including the code in some other method:

By breaking your program up into logical parts, you make it more readable. 

By giving this block of code a name, you make your program more readable. 

It's necessary to keep the calling method under 20 lines long. 

There are multiple correct answers to this question. A, B, and C are all reasonable answers. D is less good, because while it's a good idea to keep your methods relatively short, it won't always make sense to stick to an arbitrary limit like 20 lines. 

A given O(n²) algorithm takes five seconds to execute on a data set size of 100.  Using the same computer and the same algorithm, how many seconds should this algorithm run for when executed on a data set of size 500?

25 seconds

100 seconds

42 seconds

None of the above.

Quadratic algorithms represent an n² increase in run time.  Hence if the data set size increases by a factor of  five, for a quadratic algorithm, the increase in run time becomes a factor of 25.  Hence 25 times 5 (base run time) is 125.

If the StackADT operation push is implemented using a linked list, the big-Oh time complexity of the method is:

O(log₂n)

O(n)

O(n²)

O(2ⁿ)

The push method adds a new element to a stack. Regardless of the size of the list, the operations needed to add a new element include creating a node to store it in and setting the values of a few pointers, all of which can be done in constant time. 

Which line of the following code has a compilation error?

import java.util.*;

public class bicycles {

        public static void main(String[] Main) {

              Vector<bike> q = new Vector();

              bike b = new bike();

              q.add(b);

       }

}

class bike{

       private int bikePrice;

       private bike(){

                bikePrice = 0;

       }

      private bike(int p){

               bikePrice = p;

       }

}

public static void main(String[] Main)

Vector<bike> q = new Vector();

private int bikePrice;

After the assignments a = True and b = True, what is returned by (not a or b) and (a or not b)?

False

1

0

an error

the not operator has a higher precedence than or, so this expression should be read:

((not a) or b) and (a or (not b))

Which is True when a=True and b=False

Consider the following 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"

What output is produced when the input is '-1'?

an error

no output is produced

-1

none of the above

if number is not greater than 1, we immediately get to "The end".  In Python, while loops are allowed to have an else statement.

3. Consider the following class definition.

import java.util.Scanner;

public class SillyClass2 {
   private int num, totalRed, totalBlack;

   public SillyClass2 () {
      num = 0;
      totalRed = 0;
      totalBlack = 0;
      this.spinWheel();
      System.out.print("Black: " + totalBlack);
      System.out.println(" and red: " + totalRed);
   }

   public void spinWheel () {
      Scanner kbd = new Scanner(System.in);
      System.out.println("Enter 1 or 0, -1 to quit.");
      num = kbd.nextInt();
      while (num >= 0) {
         if (num == 0)
            totalRed++;
         else if (num == 1)
            totalBlack++;
         else System.out.println("Try again");
         System.out.println("Enter 1 or 0, -1 to quit).");
         num = kbd.nextInt();
      }
      System.out.println("Thanks for playing.");
   }
}

Which of the following sequences of inputs causes every line of code to be executed at least once?

0    0    10    -1

1    0    1    -1

1    1    10    -1

1    0    10    0

This question tests understanding of a conditional nested inside a loop. Choice A is wrong, because the initial value must be >= 0 for the loop to be executed. Choice E is wrong, because the last value must be -1, or the code never exits the loop and the last line of code is not executed. Choices B and C are wrong, because inside the loop, we need one value that's 0, one value that's 1, and one value that's greater than 1, so that each branch of the conditional will be executed. 

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

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

O(log n)

O(n)

O(n²)

O(2ⁿ)

The method body is executed in a fixed amount of time, independent of the size of the stack. 

You need to store a large amount of data, but you don't know the exact number of elements. The elements must be searched quickly by some key. You want to waste no storage space. The elements to be added are in sorted order. What is the simplest data structure that meets your needs? 

Ordered array

Linked list

Hashtable

Binary search tree

Hashtables provide fast searching, but they may waste storage space. A tree makes better use of memory. Since the keys are in a sorted order, it's likely a binary tree will end up looking like a linked list instead of a well-balanced tree. With a self-balancing tree, we can make sure searching goes faster.

Which one of the following is a limitation of Java's arrays?

They can only hold primitive types.

They can only hold reference types.

Once an element is assigned, that element cannot be modified.

Their length must be stored separately.

Arrays hold primitives and references, have a builtin length property, and allow modification of individual elements. They cannot be resized.

What will be printed?

String name = "John";

String surname = "Smith";

name.concat(surname);

System.out.print(name + " ");

System.out.println(surname);

John Smith Smith

JohnSmith Smith

Smith John

What should be done to change the following code to a correct one?

public class exam {

     float mark;

     public static void main(String[]arg){

     float aCopyofMark;

     exam e = new exam();

     System.out.println( e.mark + aCopyofMark);

     }

}

Change float mark; to static float mark;

Delete exam e = new exam();

This is a correct code.

Consider the following two simple Java classes:

public class Base {
  protected int x;
}

public class Derived extends Base {
  protected int y;
}

Which of the following is/are legal?

Base b=new Base();

Derived d=b;

Base b=new Derived();

Derived d=new Base();

All of the above

B and C are OK.  Remember your Liskov substitution principle:  You can swap in a derived class anywhere that you expect a base class, because a derived class has at least as much information as a base class.

The reverse, however, is not true!  A derived class may add many more instance variables that the base class knows nothing about!

This question refers to a method "swap", for which part of the code is shown below:

public static void swap(int[] x, int i, int j) {

 // swaps elements "i" and "j" of array "x".

    int temp;     // temporary storage for swapping

    xxx missing code goes here xxx

} // method swap

The missing code from "swap" is:

temp = x[i];
x[j] = x[i];
x[j] = temp;

temp = x[j];
x[j] = x[i];
x[j] = temp;

temp = x[j];
x[i] = x[j];
x[j] = temp;

temp = x[i];
x[j] = x[i];
x[i] = temp;

Suppose  initially x[i]=A, x[j]=B.  After swap, we want x[i]=B, and x[j]=A, in both cases it doesn’t matter what temp equals, so long as x[i] and x[j] values have been swapped after completion.

a)

temp = x[i] = A

x[i] = x[j] = B

x[j] = temp = A

Before: x[i] = A, x[j] = B

After: x[i] = B, x[j] = A

Both have been swapped, .’. CORRECT

b)

temp = x[i] = A

x[j] = x[i] = A

x[j] = temp = A

Before: x[i] = A, x[j] = B

After: x[i] = A, x[j] = A

Only x[j] has been swapped, .’. INCORRECT

c)

temp = x[j] = B

x[j] = x[i] = A

x[j] = temp = B

Before: x[i] = A, x[j] = B

After: x[i] = A, x[j] = B

Neither have been swapped, .’. INCORRECT

d)

temp = x[j] = B

x[i] = x[j] = B

x[j] = temp = B

Before x[i] = A, x[j] = B

After: x[i] = B, x[j] = B

Onlu x[i] has been swapped, .’. INCORRECT

e)

temp = x[i] = A

x[j] = x[i] = A

x[i] = temp = A

Before: x[i] = A, x[j] = B

After: x[i] = A, x[j] = A

Only x[j] has been swapped, .’. INCORRECT

Class B extends class A in which a method called firstMethod existed. The signature of firstMethod is as follow. In class B we are going to override firstMethod. Which declaration of this method in class B is correct?

protected void firstMethod(int firstVar)

private void firstMethod(int firstVar)

default void firstMethod(int firstVar)

void firstMethod(int firstVar)

You've got a class that holds two ints and that can be compared with other IntPair objects:

class IntPair {
  private int a;
  private int b;
  
  public IntPair(int a, int b) {
    this.a = a;
    this.b = b;
  }
 
  public int compareTo(IntPair other) {
    if (a < other.a) {
      return -1;
    } else if (a > other.a) {
      return 1;
    } else {
      if (b == other.b) {
        return 0;
      } else if (b > other.b) {
        return -1;
      } else {
        return 1;
      }
    }
  }
}

Let's denote new IntPair(5, 7) as [5 7]. You've got a list of IntPairs:

[5 7], [2 9], [3 2]

You sort them using IntPair.compareTo. What is their sorted order?

[5 7], [3 2], [2 9]

[3 2], [5 7], [2 9]

[2 9], [5 7], [3 2]

compareTo orders on IntPair.a first, in ascending fashion. Since all elements have unique a values, we simple sort according to the first element.

What does the following Java code print?

int inner=0;
int outer=0;
for (int i=0; i<6; i++) {
   outer++;
   for (int j=0; j<=3; j++) {
      inner++;
   }
}
System.out.println("outer "+outer+", inner"+inner);

outer 6, inner 3

outer 7, inner 4

outer 6, inner 18

outer 7, inner 24

For nested loops, the inner loop runs to completion one time for each iteration of the outer loop.  So if the outer loop executes 6 times, that means the inner loop, which normally executes its loop body 4 times, will actually run the loop body 24 times (4 executes times 6 outer executions).  I probably could explain that better.

After the assignments x = 27 and y = 12, what is returned by x/y?  (Assume Python <= 2.7, not Python3).

2.25

3

3.0

None of the above

This is an integer division question.  Python will return 2, since 27/12 is 2, with a remainder.  But integer division only cares about the quotient, not the remainder.

Note that you may get a different answer using Python3 rather than with Python2.x

Which of the following is not an ADT?

List

Queue

Stack

Hashtable is a data structure, not an abstract datatype.

Note: this question is based on a question by Andrew Luxton-Reilly.

What kind of variable is label?

public class Labeller extends JFrame {

      public Labeller () {

                JLabel label = new JLabel("Field or Variable");

      }

      public static void main (String[] args) {

               new Labeller();

      }

}

local variable, primitive

Instance variable, primitive

Instance variable, Object Reference

A method called myMethod has been defined in a class with the following signature. Which of these four choices cannot be an overloaded alternative for myMethod?

public void myMethod (int i, double d)

public void myMethod (double d)

public void myMethod (String i , double d)

public int myMethod (int i)

In quicksort, what does partitioning refer to?

How the list/array always has three partitions: the area before low, the area between
low and high, and the area after high.

The process in which the memory allocated for the list/array that you are sorting is
partitioned into different parts of memory, to improve memory efficiency.

The process in which the list/array is partitioned into two equal halves; the sort proceeds
by recursively partitioning until we have partitions of size 2, in which case elements are
merged in correct order.

D is how it works.

Many languages allow negative indexing for arrays: items[-1] for the last item, items[-2] for the second to last, and so on. Java doesn't support this indexing directly, but we can create a class that wraps around an array and converts a negative index into the appropriate positive one:

class WrappedStringArray {
  private String[] items;

  ...

  public String get(int i) {
    if (i >= 0) {
      return items[i];
    } else {
      return TODO;
    }
  }
}

What expression must we replace TODO with to support negative indexing?

(int) Math.abs(i)

(int) Math.abs(i + 1)

items.length - 1 - i

items.length - i

We want items[-1] to map to items[items.length - 1], and only the correct answer handles this case.

What happens if you forget to define the equals method for your key class used to insert elements into a hashtable?

The elements can be inserted but remain inaccessible.

Inserting an element will raise an exception.

All elements will map to the same location in the table.

When a key lookup is performed, we will find the hashtable location and then compare the keys using Object.equals. Object.equals returns true only when the two keys refer to the same object.

You've got two classes, Key and Value, both of which descend from Object. You intend to use these classes to populate a hashtable. Which class needs the hashCode method and which needs the equals method?

Key.hashCode, Value.equals

Value.hashCode, Object.equals

Key.hashCode, Object.equals

Value.hashCode, Value.equals

Only the Key needs these methods. On a search, only the Key will be provided, so that alone must provide the necessary information for finding the corresponding Value. Object's implementation of the equals method is too restrictive, comparing Keys only for identity.

If you are about to evaluate the following code, which following comments would you choose?

FileReader inputStream = null;

try {

       inputStream = new FileReader("in.txt");

       int c;

       while ((c = inputStream.read()) != -1)

                 // ... code has been deleted

}catch (IOException e){

        System.out.println(e.getLocalizedMessage());

}

Add finally to the above structure.

Buffering input streams is a must.

All of the above choices must be applied.

Double hashing

involves hashing the hash code

avoids collisions by computing a hash code that's a double instead of an int

prevents collisions by keeping two tables

produces a second index in [0, table.length)

With double hashing, a second hash function is used to determine the step size for the probing sequence. With linear or quadratic probing, elements that collide also tend to have the same step size, which leads to clustering. A secondary hash breaks up this uniformity.

The above instance (or Object) diagram represents a Queue. If I invoke wilma.dequeue(),  it returns:

A red car

A chartreuse car

A Node whose _element is a blue car

A Node whose _element is a chartreuse car

Dequeue removes the least-recently enqueued element from the Queue and returns it.  This element is at the "head" end of the Queue.  What it returns is specified by the interface, which is independent of implementation, so it is a Car, not a Node.

The time complexity of selection sort is:

O(1)

O(n)

O(n log n)

none of the above

Selection sort requires n(n-1)/2 comparisons. 

Martina has created an array, arr[50], and she has written the following line of code:
*(arr + 20) = 6;
Rewrite this line to use the [ ] notation for arrays.

arr[21] = 6

*arr[20] = 6

*arr[21] = 6

arr[20] == *(arr + 20)

Which statement or statements store 0.8 into the variable d of type double?

double d=8/10;

double d=8/10.0;

double d=8.0/10;

None of the above

A is wrong because 8/10 is zero.  But the B,C,D (8.0/10.0, 8/10.0, 8.0/10) all produce 0.8 because Java will promote any ints to a double in an arithmetic expression so long as there is at least one double in the expression.

Suppose you have a Java array of ints. The worst-case time complexity of printing out the elements in the list is:

O(1)

O(log n)

O(n log n)

O(n²)

If we assume that printing a single value can be done in constant time for some constant k, then printing n values can be done in kn time, which is O(n).

Suppose you have a binary search tree with no left children. Duplicate keys are not allowed. Which of the following explains how this tree may have ended up this way?

The root value was the maximum.

All keys were identical.

The tree is a preorder tree.

It was filled in descending order.

If the least node was inserted first, with each successive node having a greater key than its predecessor, we'd end up with all right children. Adding nodes with identical keys is prohibited by the problem statement, though it would yield a similar tree.

Mohamed has a brute force solution for vertex covering that takes one milisecond to test a possible vertex covering. The large graph has 64 nodes, so there are 264
possibilities (approx 1.85 * 10¹⁹ ). (There are 1000 ms in a second.) How long will Mohamed’s code take to run?

about 500,000 days

about 500,000 years

((1 / 1000*60*60*24) day ) * 1.85 * 10^19  = about 2 * 10^11 days -- so not A.

2 * 10^11 days is about 5 * 10^8 years.

After the Java assignment statement

   String word = "blank";

which of the following Java code fragments prints

   blink

?

word[2] = "i";
System.out.println(word);

System.out.println(word);

All of (a)–(c).

None of (a)–(c) .

(a) is wrong because the Java syntax word[n] requires the variable word to be an array. (c) is almost right; it just needs to have a 2 instead of the 1 in the first call to substring. Since (a) and (c) are wrong, (d) must be wrong. (b) is correct, so (e) must be wrong. 

Consider the following possible Java class names:

   General, colonel, Private, Major-General, Strategy&Tactics

When determining which names are valid, which of the following factors is important:

Class names start with a capital letter.

Class names must not be a Java reserved word. 

Class names are generally nouns, corresponding to a person, place, thing, or idea. 

Class names must start with a letter or underscore, followed by zero or more letters, digits, and/or underscores. 

Choices (b) and (d) are Java syntactic rules; A and C are generally accepted conventions.

In Java, what value will the variable d have after this declaration:

None of these

While the variable d is being declared as a double, the initial value provided on the righthand side is actually an int expression, consisting of one integer value divided by another.  When the int expression is evaluated, its result is also an int and any fractional part is truncated.  The value of 18 / 4 is 4 (an int).  After this int value is produced, it is then promoted to a double value when initializing the variable d, giving d the initial value 4.0.

This code fails to compile:

char current = 'a';
current = current + 1;

Why?

We can't add ints and chars.

The character after 'a' is platform-dependent.

We're trying to squeeze a String into a char.

The assignment is infinitely recursive.

The char is promoted to an int when an int is added to it. Thus, our right-hand side is an int while our left-hand side is a char. Assigning an int into a char may result in information less, which requires us to sign off on this risky operation with an explicit cast.

Which problem is not P (assuming P!=NP)?

Single-source shortest path

Minimum spanning tree

Sorting

Integer knapsack is considered NP-Complete.

What will this code output on a 64-bit machine?

int vals[10];

4

40

80

sizeof(vals + 0) will get the size of the memory address of the first element in vals; a pointer is 8 bytes on the 64-bit machine

Which algorithm is most arguably a greedy algorithm? (Circle the best answer.)

merge sort

insertion sort

bubble sort

Selection sort greedily takes the min/max of the array. This is a clicker question to discuss what greedy means; none of the algorithms are really greedy!

GIven the "standard" set of Stack methods, what would fred.pop() return?

A Node whose element is a blue Car

A Node whose element is a red Car

A red Car

A Stack that contains the remaining Car

Pop removes the most-recently pushed element from the Stack and returns it.   What it returns is specified by the interface, which is independent of implementation.  A user should be able to interact with a stack using push, pop, peek, and isEmpty without knowing the implementation details.

The above instance (or Object) diagram represents:

A collection of Car and Node objects

A Node list

A Stack with a red Car on top

None of the above

The diagram represents a Stack whose top element is a blue Car.   It includes a Node list, and a number of Node and Car objects, but the whole picture represents a Stack.

Anastasiya has written code that loops over an int array named a which is of length N. Fill in the missing parts of the for loop’s declaration.

int sum = 0;

int *p;
for(p = a;  ; ) // complete this line
{
    sum += *p;
}

p < N; p++

p; p++

p; p = p->next

p->next; p = p->next

p will not work as the ending condition as you don't know what's at the end of the array; N is not an appropriate ending condition as it needs to be relative from where you started. D and E are wrong as those would be for linked lists.

You've got an algorithm that is O(log N). On the first run, you feed it a collection of size M. On the second run, you feed it a collection of size M / 2. Assuming each run has worst-case performance, how many fewer operations does the second run take?

0

2

3

4

The first run takes log M operations. The second run takes log (M/2) = log M - log 2 = log M - 1 operations. The second is just one operation less than the first.

In Java, what value will the variable i have after this declaration:

0

4

4.0

6

When evaluating the initialization expression, precedence requires the modulo operator % to be applied first. 8 % 4 produces the value 0, since 8 divided by 4 has a remainder of zero.  When zero is then added to 2, the result is 2, which becomes the initial value of the newly declared variable.

Assume M and N are positive integers. What does the following code print?

int sum=0;
for (int j=0; j<M; j++) {
  for (int i=0; i<N; i++) {
    if (N%2==0) {
      sum += 1;
    }
  }
}
System.out.println(sum);

M

M^N

M*N

M*(N/2+1)

The outer loop executes M times, while the inner loop executes N/2 times (i.e. if N is 6, the loop executes 3 times because there are 3 even numbers (0,2,4) between 0 and 5).

Which definition is not right?

ArrayList<Character> charArray = new ArrayList<Character>();

ArrayList<Object> objectArray = new ArrayList<Object>();

ArrayList<Integer> intArray = new ArrayList<Integer>(10);

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

CountryInAfrica, Botswana

Botswana, CountryInAfrica

CountryInAfrica, Country

Botswana, SouthAfrica

Choices A and B are wrong, because one of the items listed is a concrete item that would be better modeled by an object. Choice E is wrong because both items listed are concrete. Choices C and D both list a class and a subclass, but only in Choice D does the class come first, followed by the subclass. 

In Java, the actual type of a parameter or variable’s value can be any concrete class that is

a. the same as the declared type, or any subclass of the declared type (if the declared type is a class)

b. any subclass of a class that implements the declared type (if the declared type is an interface)

c. any class that implements the declared type (if the declared type is an interface)

e. A and C above, but not B

The declared type must be the same or more abstract than the actual type, so the actual type must be below the declared type in the class hierarchy (if both are classes), or below some class that implements the declared type in the class hierarchy if the declared type is an interface.

Given the code:

if (x >= 0)
   System.out.println("1");
else if (x < 20)
   System.out.println("2");
else
   System.out.println("3");
System.out.println("4");

for what integer values of x will 2 be among the values printed? 

x >= 0

x < 20

All values of x

None of the above

The if-else clause will be executed only when the if-clause is false. So for all int values less than 0, 2 will be printed.

What will the display look like after these lines of code, with [ ] representing a space?

float fData = 3.6239;

printf("%3.1f \n", fData);

3.62

3.624

[ ] 3.62

[ ] [ ] 3.6

The printf function follows the pattern printf("format" [, list of_ fields]).  Within the "format" element the field specifiers have the following format [% [-] [+] [width [.precision]] data_type], where the square brackets indicate that the element is optional.   In this case %f represents a floating point element, and 3.1  the required precision of 1 decimal place.

What will be output by this loop?

for(n = 1, m = 5; n <= 5; n++, m--)

printf("%d %d\n", n, m);

1 4

2 3

3 2

4 1

5 0

 5 1

4 2

3 3

2 4

1 5

1 5

2 4

3 3

4 2

1 4

2 3

3 2

4 1

The loop increments the value of n and decrements the value of m on each iteration printing the value of each variable, until n reaches the terminal value of 5

What would be the performance of a method called addAfter(p), in which p is a position of a node or an index of an array, if the data structure is implemented by an array or linked list structure respectively?

 O(1), O(1)

O(1), O(n)

O(n), O(n)

public class RecursiveMath
   ...
   public int fib (int a) {
      if (a == 1)
         return 1;
      else
         return fib(a-1) + fib(a-2);
   }
...
}

Given the above definition, what is the result of executing the following?

RecursiveMath bill = new RecursiveMath();
int x = bill.fib(-1);

x is set to -1

x is set to undefined

The code cannot be executed, because it won't compile

None of the above

The problem:  When we invoke fib(-1),  a gets bound to -1; since that is not equal to 1, we call fib(-2) and fib(-3), and so on.  We keep making recursive calls, and the parameter will never be equal to 1 since we are getting further away from 1 with each call.  So it will not terminate.

You don't know exactly how much data you need to store, but there's not much of it. You'd like to not allocate any memory that won't be used. You do not need to be able to search the collection quickly. What is the simplest data structure that best suits for your needs?

Unordered array

Ordered array

Hashtable

Binary search tree

Since arrays must be allocated before they are used, we tend to overallocate to make sure we have sufficient capacity. This wastes space. If we're not exactly sure of how much storage we need and without a need for fast searching, a linked list is a good choice.

Which of the choices will produce the same result as the following statement?

if ( mark == 'A' && GPA > 3.5)

    System.out.println("First Class");

else

    System.out.println("Not First Class");

if ( mark != 'A' && GPA <= 3.5)

    System.out.println("First Class");

else

    System.out.println("Not First Class");

if ( mark != 'A' || GPA <= 3.5)

    System.out.println("First Class");

else

    System.out.println("Not First Class");

if ( mark == 'A' || GPA > 3.5)

    System.out.println("First Class");

else

    System.out.println("Not First Class");

Which one of the following assignments will be resulted in 1.0?

double x = 6.0/4.0;

double y = (int)6.0/4.0;

double t = 6.0/(int)4.0;

If class test is going to listen to an event, which statement, if added to the following code, cannot be a solution for event handling?

public class test implements ActionListener{

     JButton okButton;

     public static void main(String [] args){

          SimpleGui_V2 firstGui = new SimpleGui_V2();

          firstGui.draw();

     }

     public void draw(){

          JFrame rootFrame = new JFrame();

          okButton = new JButton("OK");

          // missing code

          rootFrame.add(okButton);

     }

     public void actionPerformed (ActionEvent event){

          if (okButton.getText().compareToIgnoreCase("ok")== 0)

                okButton.setText("clicked");

          else

                okButton.setText("OK");

     }

}

okButton.addActionListener(new test());

okButton.addActionListener(this);

okButton.addActionListener(new ActionListener(){

    public void actionPerformed (ActionEvent event){

        if (okButton.getText().compareToIgnoreCase("ok")== 0)

            okButton.setText("clicked");

        else

            okButton.setText("OK");

}});

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

public class test {

    final int testCount1;

    final static int testCount2;

    static int testCount3;

    int testCount4;

}

testCount2 and testCount3 have not been initialized.

testCount3 and testCount4 have not been initialized.

None of the instance variables have been initialized.

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

public class test {

       final int testCount;

       int classCount;

       public int getCount(){

               return testCount+classCount;

       }

}

testCount and classCount have not been initialized.

classCount has not been initialized.

testCount and classCount cannot be added in return statement.

consider the section of code below:

int a = 3, b = 4, c = 5;

x = a * b <= c

What will x be after executing this code?

1

3

12

17

Due to the precedence of operators here, first a and b are multiplied and then the total [12] is compared with c [5].  If the logical comparison evaluates to true x assumes the value 1,  otherwise (as in this case) , it evaluates to false and x assumes the value 0.

What would be the output?

Vector<Object> vect_1 = new Vector<Object>();

Vector<Integer> vect_2 = new Vector<Integer>();

vect_1.addElement(1);

vect_1.addElement(2);

vect_2.addElement(3);

vect_2.addElement(4);

vect_1.addElement(vect_2);

System.out.print(vect_1.toString());

System.out.print(vect_1);

This is a compiler Error. A vector of type Integer cannot be added to a vector of type Object.

[1, 2, [3, 4]][]

[1, 2, 3, 4][]

How many times will the printf statement be executed in this piece of 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!

while (i < 20)

{

     if ( i = 2 )

          printf("Count me!");

     i++;

}

0

1

19

 20

The program fails the test of equality on the first pass through as i=0, so falls through the if statement without incrementing the index.  This triggers the while loop again (which again fails the equality test  as the index remains at 0) and the program loops in an endless cycle.

How many times will the printf statement be executed in this piece of 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!

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

{

     switch ( i )

     {

           case 0: puts("Case 0");

           break;

          case 1: puts("Case 1");

          case 2: puts("Case 2");

          default: printf("Count me!");

     }

}

0

 1

 2

an infinite number

The code iterates until the index reaches 3 (a total of four times) but on the first iteration the case statement bresk before executing the printf function.  On subsequent iterations the printf fucntion is executed, twice by matching the index values and once by default.

This sorting algorithm starts by finding the smallest value in the entire array. Then it finds the second smallest value, which is the smallest value among the remaining elements. Then it finds the third smallest value, the fourth, and so on.

insertion sort

bubble sort

quick sort

merge sort

This procedure describes the steps of the selection sort, which repeatedly selects outs the ith smallest element.

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

int

char

float

double

Bytes only hold values in [-128, 127].

Which one of the codes bellow will NOT compute the summation of 10 consecutive even numbers starting from zero?

sum = 0;

for (int i = 0; i <20 ; i = i+2){

    sum+=i;

}

sum = 0;

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

    sum+=i*2;

}

sum = 0;

for (int i = 0; i <20 ; i++){

    sum+=i/2;

}

What will be printed by this code?

public static void main(String [] args){

        int [] number = {1, 2, 3};

        changeNumber (number);

        for (int i=0; i<number.length; i++)

                System.out.print(number[i] + " ");

}

public static void changeNumber(int [] number){

         for (int i=0; i<number.length; i++)

                  number[i] *=2 ;

}

1 2 3

2 2 2

0 0 0

The following method isSorted should return true if the array x is sorted in ascending order. Otherwise, the method should return false:

public boolean isSorted (int[] x){

   //missing code goes here
}

Which of the following is the missing code from the method isSorted?

boolean b = true;
for (int i=0; i<x.length-1; i++) {
   if (x[i] > x[i+1])
      b = false;
   else
      b = true;
}
return b;

boolean b = false;
for (int i=0; i<x.length-1; i++) {
   if (x[i] > x[i+1])
      b = false;
}
return b;

for (int i=0; i<x.length-1; i++){

   if (x[i] > x[i+1])
      b = true;
}

return b;

for (int i=0; i<x.length-1; i++){

   if (x[i] > x[i+1])
      return true;
}
return false;

This code should check each pair of consecutive values in the array and return false (that is, the array is not sorted) if it finds a single pair where the first value is greater than the second.

Choice A is wrong because its answer depends only on the relationship of the last two values it checks. Choice C is wrong because it always returns false. Choices D and E are wrong  because they return false when the array *is* sorted and true when it isn't. 

For the purposes of this question, two code fragments are considered to be equivalent if, when they are run using the same input, they always produce the same output. Which line could be removed from the following code fragment so that the resulting code fragment is equivalent to the original one?

1.  Scanner kbd = new Scanner(System.in);
2.  int x, product;
3.  x = -1;
4.  product = 1;
5.  x = kbd.nextInt();
6.  while (x >= 0) {
7.    if (x > 0) {
8.       product *= x;
9.    }
10.   x = kbd.nextInt();
11. }
12. System.out.println(product);

Line 4

Line 5

Line 8

Line 10

Line 3 can be removed because x is initialized again in line 5, before it is ever used. 

What will be outputted?

char initial = 'a';

switch (initial){

case 'a':

          System.out.print("a");

case 'A':

          System.out.print("A");

          break;

case 'b':

         System.out.print("B");

default:

         System.out.print("C");

         break;

}

a

aAB

aABC

Depth-first traversal is kind of like selection sort, in the same way that breadth-first traversal is like what sorting algorithm?

Radix sort

Bubblesort

Heapsort

Quicksort

Insertion sort is breadth-first-like as you keep increasing the "breadth" of the array that is sorted.

Thomas has the following program that he is running on a 64-bit machine:

#include<stdlib.h>

int main()
{
    int x = rand();
    int y = rand();
}

What is not true about y?

y is four bytes in size

y is stored in the same stack frame as x

y’s value cannot be deduced from x’s

y <= RAND_MAX, not y < RAND_MAX. As rand has not been seeded, and is pseudorandomly generated, y can theoretically be deduced from x.

Consider the following output consisting of a block of stars, with no spaces between each star, and no blank lines in between the lines of stars:

   *****

   *****

   *****

   *****

Considering a plan for a program to print out this shape, which of the following would be your main control structure?

sequence

selection

or something else

Analysing the output, we have four rows of five stars, exactly on top of one another.  Textual output (in almost any language) is row by row, moving downwards - meaning that if we  print something out on one line, and then print something on the next line, we cannot go back up to the previous line and print out some more.

Thinking this way, we can create this output by writing out each line, one at a time.  Every line is the same, and there are four lines in total.  This, then, can be written as a repetition:

      repeat four times:

            write out one line of stars

If you picked "sequence", maybe you were thinking of:

      write out one line of stars

      write out one line of stars

      write out one line of stars

      write out one line of stars

This is a correct answer, but not as elegant as the solution using repetition.  If you had 100 lines to write out, would you want to enter them all?  And if you made a mistake in the line, you'd need to edit it in 100 places... ugh!

Which of the following recommendations for testing software is good advice?

Limit your test cases to one assertion, since each test should check only one expected outcome.

Save your testing until after the solution is completely written, so you can concentrate solely on testing without distractions.

Test a program with all possible values of input data.

Longer tests that focus on combinations of multiple features are preferable, because they test your code more strenuously.

Incrementally testing your code as you write it helps you find errors more quickly, and ensures that new work builds on previous work you have already confirmed works.  The other four choices here represent less effective or impractical advice.

Which of the following is not an abstract datatype?

List

Queue

Hashtable

Array

Hashtables and arrays are data structures, not abstract datatypes. 

Note: This question was written by A. Luxton-Reilly. K. Sanders entered and tagged the question and added choice E, after A. Luxton-Reilly had to withdraw from the WG due to illness.

What algorithm does mystery implement, when a list of values is passed in as its argument?

def mystery (listOfVals):
    current = 1
    while (current < len(listOfVals)):
        pivot = listOfVals[current]
        underExam = current - 1
        while ((underExam >= 0) and (listOfVals[underExam] > pivot)):
            listOfVals[underExam+1] = listOfVals[underExam]
            underExam = underExam - 1
        listOfVals[underExam+1] = pivot
        current = current + 1
    return (listOfVals)

Quicksort

Selection Sort

List Reverser

Bubble Sort

This is a classic implementation of Insertion Sort.  Each item in the list is repeatedly inserted into its correct spot in the portion of the list already sorted.

What operation contributes the log N to heap sort's O(N log N) complexity?

Trickling up only

Trickling down only

Searching the array

Splitting the array in half

The heapsort involves inserting all elements and removing all elements. Inserting requires a trickle up and removing requires a trickle down.

We say indexing is fast if it's done in O(1) time, searching is fast if done in O(lg N) time, and inserting and deleting are fast if done in O(1) time. Compared to other data structures, sorted arrays offer:

slow indexing, slow search, slow insertions and deletions.

fast indexing, slow search, slow insertions and deletions.

slow indexing, slow search, fast insertions and deletions.

slow indexing, fast search, fast insertions and deletions.

Sorted arrays can be indexed in constant time (which is fast), searched in O(lg N) time (which is fast), and restructured in O(N) time (which is not as good as O(1) time).

True or False:

Public methods and public variables are the only part of your class that clients can access and use.

True

Clients can also inherit protected variables.  If you are writing code that will be used by clients, you need to think carefully about whether you want clients to extend your classes, and if so, how.

Jack has the code below. What will it print out?

int array[] = { 45, 67, 89, 22, 13 };

int *array_ptr = &array[1];
printf("%d, ", array_ptr[1]);
printf("%d, ", *(array_ptr++));
printf("%d, ", *array_ptr++);
printf("%d\n", *array_ptr);

67, 67, 67, 89

67, 45, 67, 89

89, 89, 89, 67

67, 89, 22, 22

The array pointer starts at the second element; the incrementing is done post-evaluation.

Which of the following is not a reason why wall clock time is a poor measure of an algorithm's performance?

It's dependent on processor speed.

Other programs may interrupt the one being measured.

The input cases may not capture the worst case running time.

Subsequent runs may read data from cache instead of disk.

Wall clock time is a measure of real elapsed time between two events, which is no different from one computer to the next.

Choose the answer that best describes how to compute the value of the following Java arithmetic expression:
     4 * 3 + 6 / 4

Evaluate the operations from left to right: * then + then /.

Evaluate * and / first (from left to right), and then evaluate +.

Round the answer to 6/4 towards 0. 

A and C.

In Java, multiplication and division have higher precedence than addition, and division is closed under ints.

How many times will F be called if n = 5, ignoring F(5) itself?

public static long F(int n) {

      if (n == 0)return 0;

      if (n == 1) return 1;

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

}

12

7

5

Compared to a sorted linked list, a balanced binary search tree offers

slower searching and faster insertion

slower searching and slower insertion

the same performance for searching and insertion

faster searching and slower insertion

Insertion is O(n) for a sorted linked list, as we must traverse the list to find the correct insertion point. Searching is O(n) since we only have sequential access; the binary search does not work for linked lists. Balanced BSTs can be traversed in O(lg N) time, making it faster for both operations.

You need to sort an array but have no extra memory to spare. Which algorithm do you avoid?

bubble sort

quick sort

heap sort

insertion sort

Merge sort requires a secondary array to merge into.

Which of the following is true of a Java interface?

Instance variables are allowed, but they must be public.

Static and final constants may not defined.

Methods may have implementations provided they are marked final.

All methods must be explicitly declared abstract.

All methods in an interface are public, even if you leave off the access modifier.

After calling the following function, what will the values of n and m be? Assume that before
calling the function, n = 2 and m = 5.

void example(int *n, int *m)
{
   *n++;
   *m += 5;
}

void main()
{
   int n = 2;
   int m = 5;
   example(&n, &m);
   printf("n = %d and m = %d", n, m);
}

n = 2 and m = 5

n = 3 and m = 5

n = 3 and m = 10

Due to order of operations, the ++ will not change n.

Finding the maximum value in a complete and balanced binary search tree is

O(1)

O(N)

O(N²)

O(N log N)

The maximum is the root's right-most descendent, which can be reached in log N steps.

You need to store a large amount of data that can be searched quickly by some key, but you don't know exactly how many elements you'll need to store. You want to waste no storage space. The elements to be added are in random order. What is the simplest data structure that meets your needs?

Ordered array

Linked list

Hashtable

Self-balancing tree

Hashtables provide fast searching, but they may waste storage space. A tree makes better use of memory. Since the keys are in a random order, it's likely a binary tree will end up balanced just through the insertion price.