Canterbury QuestionBank

Suppose you try to perform a binary search on a 5-element array sorted in the reverse order of what the binary search algorithm expects. How many of the items in this array will be found if they are searched for?

5

0

2

3

Only the middle element will be found. The remaining elements will not be contained in the subranges that we narrow our search to.

Which data structure used to implement Set yields the worst performance for Set.contains?

Binary search tree

Sorted array

Hashtable

Implementing Set.contains involves a search of the data structure. A binary search tree and a sorted array are searched in O(lg n) time, and a hashtable in O(1), assuming a sane hash function. A linked list is searched in O(n) time.

The simplified UML diagram above shows the relationships among Java classes Bird, Crow, and Duck.

Suppose Bird has a fly(Location place) method, but we want Crows to makeNoise() just before they take off and then behave like other Birds. Assuming Crows have a makeNoise() method, we should

Define a fly method in Crow by copying the fly code from Bird  then adding in makeNoise() at the start, i.e.

public void fly(Location place) {
   this.makeNoise();
 //  [paste the body of Bird's fly method here]
}

Define a fly method in Crow  that just consists of makeNoise(), i.e.

public void fly(Location place) {
   this.makeNoise();
}

Define a fly method in Crow that just consists of makeNoise() and this.fly(place), i.e.

public void fly(Location place) {
   this.makeNoise();
   this.fly(place);
}

Define a fly method in Crow that just consists of makeNoise() and Bird.fly(place); i.e.

public void fly(Location place) {
   this.makeNoise();
   Bird.fly(place);
}

D is the best: super.fly(place) invokes Bird's fly method, so produces fly behavior like other Birds.  A would also work, but is does not take advantage of inheritance, and would be incorrect if you change the flying behavior of Birds by modifying Bird's fly method.

B wouldn't involve any flight, C wouldn't terminate, and E assumes a static fly method in Bird (which would be unusual design, so I would have mentioned it).

For a graph with N nodes, what's the minimum number of edges it must have for it to contain a cycle?

N + 1

N

N - 1

2

A vertex with an edge to itself is a cycle.

Read the following method skeleton and choose the best expression to fill in the blank on line 8 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 return type of the method is int, so an integer return value must be provided.  Since counter is used as a loop index, it will always end up being the total number of characters in the given string.  The variable totalA is used as an accumulator that is incremented each time a letter A is found in the string, so it is the choice that will provide the correct return value for the method.

Two algorithms accomplish the same task on a collection of N items. Algorithm A performs log₂ N operations. Algorithm B performs log₃ N operations. Under what conditions does algorithm A offer better performance?

N <= 2

N < log₂ 3

N < log₃ 2

N < 8

For no possible collection size N is log₂ N < log3 N.

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

O(log N)

O(N)

O(N²)

O(N log N)

The median is the element that has M elements less than it and M elements greater than it. This can only be said of the root node in a complete and balanced binary tree. The root is accessed in constant time.

For a heap of size n, which is indexed at 0, at what position will its last child be?

2n + 1

n / 2

floor(n / 2) + 1

The last element will be at the end of the array.

What design stategy does Quicksort use?

Greedy

Dynamic programming

Brute force

Quicksort is divide and conquer.

If you did not have a base case in a recursive function in C, and were working on a modern Unix-based system, what would most likely happen?

Segmentation fault

Stack overflow error

Nothing, that’s fine

It really depends on the program for whether it would be B or C. Both can be argued to be correct.

The following Python method determines whether or not a list of values, passed in as a parameter, has any duplicate values.

What is the Big-Oh running time of this algorithm?

def duplicates(lov):

    dupCount = 0
    outer = 0
    while (outer < len(lov)):
        inner = outer + 1
        while (inner < len(lov)):

            if (lov[inner] == lov[outer]):

                dupCount = dupCount + 1

            inner = inner + 1

        outer = outer + 1

    if (dupCount == 0):
        print "there are no duplicate values"
    else:
        print "there are ", dupCount, " duplicate values"

O(1) 

O(n)

O(n log₂ n)

O(n³)

Each item in the list is compared against each other item in the list: a classic example of the all-pairs programming pattern.  The first item is compared against n-1 other values.  The second item is compared against n-2 other values, etc.  The total number of comparisons is 

What is printed when the following program runs?

public class Main {
  public static boolean getTrue() {
    System.out.print("T");
    return true;
  }

  public static boolean getFalse() {
    System.out.print("F");
    return false;
  }

  public static void main(String[] args) {
    getTrue() || getTrue();
  }
}

TT

F

TF

Nothing is printed.

If the first operand for || is true, as is the case here, the second is not evaluated.

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

2i

2i + 1

i + i + 2

i / 2 + 1

Which of the following abstract datatypes would be the best choice for part of the implementation of the part of a compiler that determines whether the parentheses in a program are balanced?

A Queue

A List

A PriorityQueue

A Dictionary

A close parenthesis must match the most recently entered open parenthesis. So for example, the sequence )()(  doesn't match, while ()() and (()) do, even though they all have two open and two close parentheses. To make this work, you can push each open parenthesis on a Stack, and pop it off each time you see a close parenthesis. The last-in-first-out nature of a Stack makes it easy to determine whether the parentheses are balanced.

Given the above binary tree rooted at Node A, what is the order of nodes visited by an inorder search?

A, B, C, D, E, F, G

A, B, D, E, C, F, G

D, E, B, F, G, C, A

G, F, E, D, C, B, A

An inorder search of a binary tree is: visit the left subtree, visit the root, visit the right subtree.

It procedes as

Visit left subtree:

     Visit its left subtree:

           Visit D

     Visit B (its root)

     Visit its right subtree: 

           Visit E   

Visit A (the root)

Visit right subtree:

     Visit its left subtree:

          Visit F

     Visit C (its root)

     Visit its right subtree:

          Visit G

What is printed when the following program runs?

public class Main {
  public static boolean getTrue() {
    System.out.print("T");
    return true;
  }

  public static boolean getFalse() {
    System.out.print("F");
    return false;
  }

  public static void main(String[] args) {
    getTrue() || getFalse();
  }
}

TF

F

TT

Nothing is printed

If the first operand for || is true, as is the case here, the second is not evaluated.

Kexin is hashing the values 9, 45, 22, 48, 38 into a hash table of size 20. Which hash function will give her no collisions?

h(k) = k % 10

h(k) = k / 10

h(k) = (k % 10) + (k / 10)

A will collide on the 48/38; B will collide with 45/48; C will collide with 9/45.

Given the above binary tree rooted at Node A, what is the order of nodes visited by a postorder search?

A, B, C, D, E, F, G

A, B, D, E, C, F, G

D, B, E, A, F, C, G

G, F, E, D, C, B, A

A postorder search of a tree is: visit the left subtree, visit the right subtree, visit the root

It procedes as

Visit left subtree:

     Visit its left subtree:

          Visit D

     Visit its right subtree:

          Visit E

     Visit B (its root)

Visit right subtree:

     Visit its left subtree:

          Visit F

     Visit its right subtree:

          Visit G

     Visit C (its root)

Visit A (the root)

The order of nodes visited corresponds to answer D

True or False:

Breadth-first search (BFS) and Depth-first search (DFS) visit nodes of a graph in the same order only if the graph looks like a linear chain, or linked list, and the traversal starts at one of the ends.

For example, BFS and DFS starting at node A are the same for the following graph:

A <-> B <-> C

True

We could add any number of nodes to node B, and visit nodes in the same order starting at node A and node B.

For the Insertion sort algorithm; what is its best case and worst case performance?

Best: O(n)
Worst: O(n)

Best: O(log₂ n)
Worst: O(n²)

Best: O(n²)
Worst: O(n²)

None of the above.

Insertion sort, if given an already sorted list, will still perform O(n) comparisons to ascertain the list is sorted.  If the list is "reverse sorted,"  then the  first pass will require 1 exchange.  The second pass will require 2 exchanges, etc.  Hence, in the worst case, O(n²) exchanges.

For the selection sort algorithm; what is its best case and worst case running time?

Best: O(1)
Worst: O(n)

Best: O(n)
Worst: O(n²)

Best: O(log₂ n)
Worst: O(n)

None of the above.

Selection sort repeatedly runs the Find-largest algorithm as its helper function.  So, regardless of the list's initial ordering, Find-largest will cost n-1 comparisons for the first pass, n-2 for the second, etc.  Hence selection sort's run time performence is independent of the list's initial ordering: O(n²)

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

int

float

double

long

Shorts can only hold values in [-32768, 32767].

Suppose you try to perform a binary search on the unsorted array {1, 4, 3, 7, 15, 9, 24}. Which element will not be found when you try searching for it?

7

1

9

24

The answer is 15. The first check will look at 7. 15 is greater than 7, so we search to its right. The second check will look at 9. 15 is greater than 9, so we search to its right. The third check will look at 24. 15 is less than 24, so we look to its left. However, our range has just been inverted and our searching stops, not having found 15.

Given the above binary tree rooted at Node A, what is the order of nodes visited by a breadth-first traversal?

A, B, D, E, C, F, G

D, B, E, A, F, C, G

D, E, B, F, G, C, A

G, F, E, D, C, B, A

A breadth-first traversal procedes by levels --  the root, then all of the nodes that are children of the root, then all of the nodes that are grandchildren of the root, etc.

In this case we get:

Visit A (the root)

Visit B, C (children of the root)

Visit D, E, F, G (grandchildren of the root)

This corresponds to answer A.

What node will be in a same rank (position) if the following tree is traversed by preorder, postorder and inorder algorithm?

A

B

D

Fill in the single missing line of code:
int p, *r, **q;

p = 27;
r = &p;

// MISSING LINE
printf("The value is %d", **q); // prints 27.

*q = *r;

**q = p;

q = &&p;

*q = *p;

B gets q to point to r, which points to p.

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

O(1) , O(1)

O(n) , O(1)

O(n) , O(n)

What is the value of j after this code is executed?

int i = 6, j = 10;

j += i;

4

6

10

 Undefined

The value of variable i (6) is added to that of variable  j (10) resulting in 16 as the  new value of j

Suppose q is an instance of a queue that can store Strings, and I execute the following statements starting with q empty:

1. q.enqueue("Sweden");
2. q.enqueue("is");
3. q.enqueue("my");
4. String w = q.dequeue();
5. String x = q.peek();
6. q.enqueue("neighbor");
7. String y = q.dequeue();
8. String z = q.dequeue();

What is the value of z after executing these expressions in order?

None of the above

If we consider the contents of the queue after each expression (listing contents from head to tail), we have

1. ["Sweden"]

2. ["Sweden" "is"]

3. ["Sweden" "is" "my"]

4. ["is" "my"]  (and w gets set to "Sweden")

5. ["is" "my"]  (and x gets set to "is")

6. ["is" "my" "neighbor"]

7. ["my" "neighbor"] (and y gets set to "is")

8. [ "neighbor"]  (and z gets set to "my")

Which of the following parts of a process’ memory is the largest?

The code area

The globals area

The stack

Heap is the largest.

Prim’s Algorithm is used to solve what problem?

Finding the lowest parent of a heap

Shortest path in a graph from a source

Sorting integers

Prim's is used for MST.

Suppose you have a tree with a maximum depth of d and an average branching factor of b (i.e. each node has b children). You are searching for a particular node S located at depth m (m <= d). You don't know where the node S is located, just that it is at depth m.

What is an upper bound on the space complexity of breadth-first search (i.e. big-O notation) to find the node S starting from the root?

O(d * b)

O(d^b)

O(b * m)

O(b^m)

In the worst case, we need to store all of the nodes, because the very last node we check at the maximum depth will be S.  The deepest nodes of the graph will have O(b^d) nodes, and in the worst case we would need to store all of these nodes.

Which of the following abstract datatypes would be the best choice for part of the implementation of the back button on a Web browser?

a Queue

a Priority Queue 

a List 

a Dictionary

When you click on the back button, you should see the last page you visited, so the datatype that stores the previously visited webpages must be last-in-first-out. Of the abstract datatypes listed, Stack is the only one that is last-in-first-out.

Which of the following abstract datatypes would be the best choice for part of the implementation of a program modeling the arrival of patients to an emergency room in a hospital?

a Stack

a Queue

A List

a Dictionary

In an emergency room, you want to serve patients in the order of how urgent their condition is, and if two patients have equally urgent conditions, in the order that they arrived. A PriorityQueue is the only abstract datatype listed that meets both of these conditions. 

Two algorithms accomplish the same task on a collection of N items. Algorithm A performs N/2 operations. Algorithm B performs N log N operations. Under what conditions does algorithm A offer better performance?

N <= 4

N > 8

N > 2

For no N.

For all legal collection sizes, N/2 < N log N.

When is an adjacency matrix a good choice for implementing a graph?

When the graph is undirected.

When a graph has few edges.

When the graph contains no cycles.

When the graph is connected.

The adjacency matrix will compactly and efficiently store edges when it contains little wasted space. In a complete graph, each vertex shares an edge with each other vertex, meaning all elements in the adjacency matrix will be used.

What is true about the pivot in quicksort?

Before partitioning, it is always the smallest element in the list

After partitioning, the pivot will always be in the centre of the list

A random choice of pivot is always the optimal choice, regardless of input

As the pivot will be to the right of all smaller elements and to the left of all larger elements, it is in the same position it will be when the array is sorted.

When is an adjacency list a good choice for implementing a graph?

When the graph is undirected.

When the graph is nearly complete.

When the graph contains no cycles.

When the graph is connected.

With adjacency lists are used, each vertex stores its own list of vertices it's connected to. When a graph contains few edges, these lists will be very short and will likely consume less memory than the adjacency matrix.

You've got an algorithm that is O(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 much time does the second run take?

1/2 of the first

2/3 of the first

3/4 of the first

1/8 of the first

The first run took time proportional to M². The second run took (M/2)², or M²/4. The second run is 1/4 of the first.

Two algorithms accomplish the same task on a collection of N items. Algorithm A performs N² operations. Algorithm B performs 10N operations. Under what conditions does algorithm A offer better performance?

N < 100

N > 10

For all N.

For no N.

The two algorithms offer equal performance when N = 10. For N greater than 10, N² > 10N.

1.  public BallPanel extends javax.swing.JPanel {
2.     private Ball[] _balls;
3.     public BallPanel(int numberOfBalls){
4.        ??????
5.        for (int i=0;i<_balls.length;i++)
6.           _balls[i] = new Ball();
7.     }
8.  }

We need to add something at line 4 above to avoid an error in line 5.  Which of the following line 4 expressions fix the error in line 5?

 _balls.length = numberOfBalls;

B, C, and D all work.

The problem with line 5 (without adding line 4) is that _balls is declared, but not instantiated as an array, so _balls is null.   The code compiles fine (assuming you have a class Ball that has a constructor with no parameters), but will crash at run time if you instantiate a BallPanel.

B and D wouldn't help: B would crash at run time for the same reason as 5, and D gives a compile-time error since length is not directly settable for a Java array.   A would work, but would have no effect on the problem.

Which of the following makes an appropriate pre-condition for this code?
double calculate_percentage(double sum, double n)
{

    // calculates and returns a percentage given a sum and a length (n)
    // <missing pre-condition>
    // POST: none
    return (sum / n) * 100;
}

PRE: sum < 100

PRE: sum != NULL and n != NULL

PRE: none

The code will faill if n = 0, as it will divide by 0.

Consider writing a program to be used by a farm to keep track of information about the fruits and vegetables they sell. For each sale, they would like to keep track of the type of item (eggplant, tomato, etc.), the quantity sold, the price, and the market at which the sale was made. Which of the following is the best way to represent the information?

Define one superclass, FarmSale, with four subclasses: Type, Quantity, Price, and Market.

Define five unrelated classes: FarmSale, Type, Quantity, Price, and Market.

Define five classes: FarmSale, Type, Quantity, Price, and Market.. Make Market a subclass of Price, make Price a subclass of Quantity, make Quantity a subclass of Type, and make Type a subclass of FarmSale.

Define five classes: FarmSale, Type, Quantity, Price, and Market. Make FarmSale a subclass of Type, make Type a subclass of Quantity, make Quantity a subclass of Price, and make Price a subclass of Market.

Which classes you define depends generally on the needs of the software. It might be good to have Market be a class of its own, with the address of the market, contact information for the organizers, etc. The item type might be modeled with a Product class, with information about the date it was planted, for example.

But of the choices given, A is the best. We can rule out choices B, C, D, and E because price and quantity don't need data and associated methods of their own and are most appropriately modeled as fields in the FarmSale class. That leaves A.

The word abstract in the class box for Vehicle means:

Vehicle is the top level of the hierarchy

Objects of type Vehicle can not be instantiated

All concrete subclasses of Vehicle must implement or inherit all of Vehicle’s abstract methods

All of the above

An object cannot be directly instantiated from an abstract class, i.e.  Vehicle v = new Vehicle(); is not legit, so B is true.  It is also true that every concrete (non-abstract) subclass of Vehicle must implement or inherit all of the methods defined as abstract in Vehicle.  So D is the answer.

Suppose you are writing a Java program to be used to manage information about the inventory in a store. The store’s products include pagers, cell phones, and cameras. The cell phones are used for both communication and taking pictures, the pagers are only used for communication, and the cameras are used for taking pictures.

Assume that a Product class has been defined. Which of the following is the best way to represent the remaining data?

Define two subclasses of the Product class: Communicator and PictureTaker. Define two subclasses of the Communicator class: Pager and CellPhone; and define two subclasses of the PictureTaker class: CellPhone and Camera.

Define five new classes, not related to the Product class: Pager, CellPhone, Camera, Communicator, and PictureTaker.

Define five subclasses of the Product class: Pager, CellPhone, Camera, Communicator, and PictureTaker.

Define two subclasses of the Product class: Communicator and PictureTaker. Also define three interfaces: Pager, CellPhone, and Camera. Define the Communicator class to implement the Pager and CellPhone interfaces, and define the PictureTaker class to implement the CellPhone and Camera interfaces.

Answer A is the easiest to rule out -- it gives CellPhone two superclasses, which is not permitted in Java.

C is not the best choice because it doesn't capture the relationships among the various items. D captures some of the relationships but not all (for example, it's missing the relationship between PictureTaker and Camera).

Answers B and E are very similar -- they focus on the question of which items should be modeled by interfaces and which by classes. B is a better choice for several reasons. Pagers, phones, and cameras all have both behaviors and data -- for example, the list of phone messages for a phone and the ability to take pictures for both phones and cameras -- while PictureTaker and Communicator correspond to behaviors. In addition, defining PictureTaker as an interface allows us to capture the fact that a cell phone is a product, a picture taker, *and* a communicator. 

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;

     }

}

I would like to combine lines 8 and 9 into

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

Unfortunately, this gives me a syntax error. Why?

The %s should be replaced by %c.

The parameter to vCodeString should be szText

The parameter to vCodeString should be shown as szData[ ].

 printf can only match %s to a variable, not to a function.

The printf function cannot take as a parameter a function which does not return a value

The binary value 11011101 when coverted into a decimal value from two's complement notation is:

35

221

-221

-33

Conversion of negative numbers in two's complement into decimal requires a bit flip, followed by the binary addition of 1.  This value is then interpreted as an unsigned binary value.

Note draft only topics and explanation tba

Consider the following short program:

#include <stdio.h>

void f1(void);

int a;

void main(void)

{

     int b;

     a = b = 1;

     f1();

     printf("%d %d", a, b);

}

void f1(void)

{

     int b = 3;

     a = b;

}

The output from the print statement will be:

1 1

1 3

3 3

3 5

Explanation to be completed

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

O(1)

O(N)

O(N²)

O(N log N)

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

An interface in Java can appropriately be used to model

Abstract classes

Related classes that share particular attributes

Classes that communicate using the same network protocol

None of the above

Interfaces allow us to specify common capabilities in unrelated classes: a way to say that two classes have the same methods without specifying the implementation (and allowing completely different implementations).  For closely related classes (near each other in inheritance hierarchy) we can get common capabilities by having them in a common ancestor.  Abstract classes provide a method to specify common capabilities via inheritance.  Interfaces cannot be used to specify that two classes share a set of attributes (i.e. instance variables), which can be done by having classes inherit from a common ancestor with those attributes.

Suppose you are defining a Java ProductItem class to store information about the inventory in a store, and you want to give the class an instance variable for the number of those items currently in stock. Choose the best datatype for modeling this number:

a user-defined NumberInStock class

A and B are wrong because you want to model an integer, not a floating point number.

E is wrong because you probably want to use this number for adding and subtracting, not just for display. 

D is less good than C, because the built-in operations on ints will most likely be sufficient for the purposes of this variable. 

Suppose you have a tree with a maximum depth of d and an average branching factor of b (i.e. each node has b children).  You are searching for a particular node S located at depth m (m <= d).  You don't know where the node S is located, just that it is at depth m.

What is an upper bound on the runtime complexity of breadth-first search (i.e. big-O notation) to find the node S starting from the root?

O(d * b)

O(d^b)

O(b * m)

O(b^m)

In the worst-case, you would keep choosing sub-tree containing S last, and have to keep searching.  Thus the worst-case is O(b^d).

The following picture may help:

What wil the following code print, assuming that N is a positive integer?

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

N

N/2

N/2+1

0 (i.e. the loop body never executes)

If N is even, for example N=12, N/2 works.  However, suppose N is odd, for example N=13.  Here the result should be 7, which is (N+1)/2.  However, for N=12, (N+1)/2 also works.  (N+1)/2 works for all positive integer.

Two algorithms accomplish the same task on a collection of N items. Algorithm A performs (N/2)³ operations. Algorithm B performs N² operations. Under what conditions does algorithm A offer strictly better performance?

N <= 8

N > 8

For all N

For no N

For N <= 7, (N/2)³ < N².

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

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

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

There is no base case

The problem is not self-similar

The problem does not get smaller

None of the above

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

Here (2) is satisfied -- lists contain smaller lists. (1) is satisfied by lines 2-5 of the method. And (3) is satisfied because line 7's recursive call takes the rest of the list as a parameter, rather than the whole list.

Suppose QueueADT is implemented using a singly linked list. What is the lowest Big-Oh time complexity that can be achieved for an enqueue method?:

O(log₂ n)

O(n)

O(n²)

none of the above

If you keep a pointer to the last element of the queue, then the enqueue method just needs a fixed number of statements, which are the same independent of the size of the queue. 

What terminates a failed linear probe in a full hashtable?

The end of the array

A deleted node

A null entry

A node with a non-matching key

A null entry will not appear in a full hashtable. 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. The purpose of leaving a deleted node in the table is so that probing may proceed past it. Revisiting the original hash index means we've looked at every entry and determined the item doesn't appear in the table.

Which of the following assertions is incorrect?

A Python expression may return a value

A Python statement may produce a side effect

A Python expression may produce a side effect

None of the above (i.e., all are correct)

Basically, a statement in Python is a special kind of function that doesn't return a value.  Statements are things like print (in Python 2.x but not Python 3) and import.

I think this is not a great question to put on a CS-1 exam beacuse it relies on terminology (statement, expression, side-effect) that doesn't really mean much until CS-2 or later.

Consider the following class for a Ninja:

public class Ninja {
  private int honor;
  public Ninja(int h) {
   this.honor=h;
  }
}

Suppose we instantiate two Ninjas like this:

Ninja n1=new Ninja(50);
Ninja n2=new Ninja(50);

Is the following statement True, False, or It Depends:

n1 == n2

True

It depends

(Note:  Be ready to explain what it depends upon during the discussion phase of this question)

These two references are not equal because they reference different instances.

What is not a property of a max-heap?

It is complete

A node’s value is less than or equal to that of its parent

Its root is the maximum element in the tree

A max-heap need not be sorted.

Barack Obama wants to know the most efficient way to sort a million 32-bit integers. He knows it’s not bubble sort. What is?

Heapsort

Insertion sort

Mergesort

Quicksort

Radix sort will be O(n) and works nicely on integers; at such a large scale it will outperform the O(nlgn) sorting algorithms.

(question is a reference to http://www.youtube.com/watch?v=k4RRi_ntQc8 )

Read the following method skeleton and choose the best expression to fill in the blank on line 2 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
}

1

aString.size()

aString.length

aString.length() - 1

This method must examine each character in the given string to see if it is 'A' or 'a', and uses a loop to do so.  The variable counter is being used as a loop index, and by imagining what will fill in other blanks, is also being used to keep track of the position of the current character in the string that is being examined.  Since line 7 methodically increases counter on each loop iteration, it must be traversing left-to-right through the string, so zero is the best choice for its initial value.

You are writing a depth-first search on a platform that doesn't support recursion. What data structure can help you complete your task?

queue

priority queue

hashtable

linked list

As you visit nodes, if you push their neighbors on a stack, the neighbors will be the first popped off when you need to backtrack. This behavior is what makes a depth-first search depth-first.

The worst-case time complexity of radix sort is:

O(1)

O(n)

O(n²)

none of the above

n is the number of items to be sorted, as usual, and k is the number of digits in the largest number in the list. Radix sort processes the entire list (n numbers) once for each of the k digits in the largest number in the list, so the work done is proportional to n*k. 

A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

256

511

512

1024

In a hashtable with chaining, each element is assigned to a particular cell in the array (a "bucket") using the hash function. Each bucket has a pointer to the start of a linked list, and the elements assigned to that bucket are stored in the linked list. 

Read the following method skeleton and choose the best expression to fill in the blank on line 6 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
}

0

The variable totalA is being used as an accumulator to keep track of how many A's have been seen so far as the loop progresses.  The if condition inside the loop is intended to detect whether the current character is an "A", and so the variable totalA should be incremented each time the condition is true.  Therefore, the best answer for Line 6 is 1, so that totalA is incremented.

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

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

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

       bestSoFar = y[i];             // line 3

  } // for

  return bestSoFar;                  // line 4

} // method minVal


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

line 1

line3

line4

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

The other three lines use bestSoFar to remember the best VALUE seen thus far, whereas the buggy line is using bestSoFar as if bestSoFar contains the POSITION seen thus far.

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

1

4

3

You can have a left child of the root, but as soon as you add the right child, it falls apart.

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

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

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

       bestSoFar = i;                // line 3

  } // for

  return bestSoFar;                  // line 4

} // method minVal

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

line 1

line2

line4

line 3 should be bestSoFar = y[i];

How many objects and object reference would we have if the following code is executed?

Student first_st = new Student();

Student second_st = new Student();

Student third_st = second_st;

3, 2

2, 2

3, 3

Suppose you try to perform a binary search on the unsorted array {1, 4, 3, 7, 15, 9, 24}. How many of the items in this array will be found if they are searched for?

3

4

6

0

7, 4, 9, 24, and 1 will be found if searched for. 15 and 3 will not, since they lie to the wrong side of a subrange's midpoint.

Consider the following class for a Ninja:

public class Ninja {
  private int honor;
  public Ninja(int h) {
    this.honor=h;
  }
}

Suppose we instantiate two Ninjas like this:

Ninja n1=new Ninja(50);
Ninja n2=new Ninja(50);

Is the following statement True, False, or It Depends (i.e. depends on a factor external to this question)

n1.equals(n2)

True

It depends

(Be ready to discuss what it depends on when we get to the discussion phase of this question)

The equals() method has not been overloaded, so it's using the default implementation of equals() in Java, which falls back on ==.

This is sort of a trick question, but it's a reasonably common error pattern in CS-2.

Dummy question: Bloom tags. 

blaha

blaha

This question has a tag for each one of the Bloom tags so we can see how many questions there are of each. (Note: delimiters are included in case of errors).

How many number will be printed if n = 5?

public static void cSeries(int n) {

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

      if (n == 1) return;

      if (n % 2 == 0) cSeries(n / 2);

      else cSeries(3*n + 1);

}

3

4

5

For Club Scripting, to be a member a person must be aged 15 or older, but less than
50. What values would you use to boundary test a script designed to check if a
person was a suitable age to join?

14, 15, 50, 51

15, 16, 50, 51

15, 16, 49, 50

13, 15, 49, 52

The boundary values are those at the boundary and those respectively one before and one past the boundary

Consider a picture that is x pixels wide and y pixels tall.  Furthermore, consider storing the x*y pixels in a one-dimensional array which stores the pixels in a left-to-right, top-to-bottom manner.

Consider the following code:

def pixelSwap (pixels):
     pixCount = len(pixels) - 1
     for p in range (0, len(pixels)/2):
          tempPixel = pixels[p]
          pixels[p] = pixels[pixCount - p]
          pixels[pixCount - p] = tempPixel

If the array of pixels originally represented the following picture:

Which of the following pictures represents the pixel array after invoking pixelSwap?

The picture is unchanged.

The picture is rotated 90 degrees clockwise.

The picture is rotated 90 degrees counterclockwise.

None of the above.

The first pixel becomes the last, the second pixel, becomes the second last, etc.  This is a list reversing algorithm.  For a picture, the result is to rotate it 180 degrees.

Read the following method skeleton and choose the best expression to fill in the blank on line 5 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
}

While both charAt() can be used to examine a single char in a string, char is a primitive type without any methods.  Since the condition on Line 5 uses the equals() method to compare against another String value, the expression used to fill in the blank must produce a String object, so the substring() method is a better fit.  The substring() method takes two parameters--a starting index and an ending index one past the end of the substring--and since the method counts both upper case and lower case A's, the result should be converted to upper case form before testing for equality against "A".  Thus, the best answer is aString.substring(counter, counter + 1).toUpperCase().

You need to traverse a singly-linked list in reverse. What's the best worst-case performance you can achieve?

O(1)

O(log N)

O(N log N)

O(N²)

Iterate through the list in the forward direction, but prepend each node on a second list as you do. Then iterate through the second list, which will be in the desired reverse order and traversable in O(N) time.

Which data structure can be used to implement an abstract datatype such as the StackADT or QueueADT?

an array

a linked list

neither

StackADT and QueueADT can both be implemented with either an array or a stack. Either may be the better choice, depending on the purpose of the program and the nature of the data being stored. 

Which data structure uses space more efficiently if the program is storing substantially less data than expected?

An array

They are both the same

For an array, you must set aside a block of memory in advance. A linked list only creates nodes for those elements that are actually contained in the list. 

How many objects are created in the following declaration?

String[] names = new String[10];

0

10

11

None of the above

The declaration introduces a new variable called "names" and initializes it to a newly created array object.  This array object is the only object that is created.  Remember that when you create an array object that holds references to other objects, all of the references in the array are initially null.  The "new" expression used here creates the array only, not any of the String objects that may (eventually) be held in the array.  The array is initially completely empty.

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, unsorted linked lists offer:

slow indexing, slow search, slow insertions and deletions.

fast indexing, fast search, slow insertions and deletions.

fast indexing, slow search, slow insertions and deletions.

slow indexing, fast search, fast insertions and deletions.

Linked lists do not support fast indexing. To get at element i, one must traverse the list i steps. Slow indexing makes for slow searching, as the binary search relies upon fast indexing to retrieve the middle element. Insertions and deletions, on the other hand, can be done in constant time, as only one or two neighboring links are affected.

Consider the following code snippet that copies elements (pixels) from one 2-d array (called pict), with maximum dimensions of maxWidth and maxHeight into another 2-d array called canvas.

canvas = [][]
for row in range (0, maxHeight):
    for col in range (0, maxWidth):
        origPixel = pict[col][row]
        canvas[width-1-col][row = origPixel

If one were to display canvas, how would it compare to the orignal picture (as represented by pict)?

Rotated 180 degrees around the horizontal center line/row.

Rotated left 90 degrees.

Rotated right 90 degrees.

Rotated 180 degrees.

Each pixel remains on the same row (line) that it originally was on.  For any given row, the leftmost pixel swaps positions with the rightmost.  The second pixel in a row swaps positions with the second last pixel in that row, etc.  Hence, the picture is rotated across the vertical center line.

What is a shorter way to write if(p == NULL) ?

if(p)

Answer is B.

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

The undo operation in a word processor

the back button in a web browser

a hundred names in alphabetical order, where names are added and removed frequently

the roads and intersections in a city

Choices A and B are applications where when you delete, you need to delete the item that was added most recently (a LIFO structure). This is not possible in a queue, where you always delete the item that was added *first*.

Choice D is an application where you need to be able to delete from the beginning, middle, or end of the structure, something that is also impossible in a queue. 

Choice E is an application where a element (an intersection) could be connected to several other elements. This is also impossible in a queue.

Choice C is the only one where it makes sense to retrieve the elements in the order in which they arrived. 

This sorting algorithm splits the collection into two halves, sorts the two halves independently, and combines the results.

selection sort

insertion sort

bubble sort

quick sort

Merge sort splits the collection, sorts the two halves, and merges them.

Locating a new node's insertion point in a binary search tree stops when

We find a node greater than the node to be inserted.

We reach the tree's maximum level.

We find a node lesser than the node to be inserted.

We find a node without any children.

Finding nodes less than or greater than the new node happens frequently as we traverse the tree. Tree's don't have maximum levels. The insertion point isn't necessarily a leaf node. The remaining option of stopping when we reach null is the correct answer because we have found the new node's parent node.

What are hash functions not used for? (Or at least, should not be used for.)

Storing values in hash tables

Checking file integrity

Digital signatures on files

Hash functions should be used to store passwords, but not to encrypt them!

How many objects are created in the following declaration?

1

This declaration causes a run-time error

It is not legal to write this declaration in Java

This declaration defines a new name, but does not initialize the name to a value.  No objects are created, since "new" is not used to create any.  Since the new name is not initialized, it will be null until it is assigned a new value later in the code.

Nathan is on the run (apparently the US is about to invade Canada). He needs to grab food.
Each piece of food around him has a nutritional value, and a weight. He wants to put the
most calories in his backpack, but it can only hold up to certain weight. What should he
optimize for when deciding which foods to bring?

The value of food

The weight / value ratio of food

The weight of food

Greedy approach to fractional knapsack.

Suppose you are defining a Java ProductItem class to store information about the inventory in a store, and you want to give the class an instance variable for the price of that item. Which of the following is the best datatype for the instance variable that models the price?

Arguments can be made for any of these choices (except perhaps "int"). I would give Money an edge, because a user-defined class allows you to write methods to display the value properly, do arithmetic on it, and perhaps convert it to different currencies. But I'm going to tag this as a question with more than one answer. 

1.public class FirstApp extends wheels.users.Frame {
2.    private wheels.users.Ellipse _ellipse;
3.
4.    public FirstApp() {
5.       _ellipse = new wheels.users.Ellipse();
6.    }
7.
8.    public static void main(String[] args) {
9.       FirstApp app = new FirstApp();
10.   }
11.}

What does line 2 accomplish (cause to happen)?

wheels.users.Ellipse is given _ellipse as an alias

An invisible Ellipse is drawn on the screen

wheels.users.Ellipse is set to be a private object

_ellipse is instantiated as a wheels.users.Ellipse

Remember that in Java we need to declare variables, and then instantiate them (using new).  Line 2 is simply a declaration -- the variable gets instantiated (in line 5) when a FirstApp gets instantiated.

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, unsorted arrays offer:

slow indexing, slow search, slow insertions and deletions.

fast indexing, fast search, slow insertions and deletions.

slow indexing, slow search, fast insertions and deletions.

slow indexing, fast search, fast insertions and deletions.

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

One of the things in Java that allows us to use polymorphism is that the declared type and actual type of a variable may be different.

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

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

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

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

A and B above, but not C

The rule of thumb is that the declared type is the same or more abstract than the actual type.  If the declared type is a class, the things that are equally or less abstract are its descendants -- a subclass specializes a class.  If declared type is an interface, it is an abstraction of any class that implements it, or by the relationship between classes and its descendants, any class that is a subclass of something that implements it.

Java wants a guarantee that the actual type will have the declared type's methods.  That can be via inheritance or implementing an interface, or a combination of the two.

An example of something that could be implemented using a Stack is:

The undo operation in Word

The back button in a web browser

A postfix calculator

Items (A) and (B) only

Anytime you're solving a problem where you're adding and removing data and you always need to remove the item that was added most recently is suited to a Stack. This is called a last-in-first-out property, or LIFO. Back buttons, the undo operation, and postfix calculators all have the last-in-first-out property. 

Suppose you are writing software for a helpdesk. Each request is entered into the system as it arrives. 

Which of the following abstract datatypes would be the best choice to ensure that the requests are handled in exactly the same order in which they arrive?

A Stack

A List

A PriorityQueue

A Dictionary

A Queue is the only abstract datatype where elements are removed in exactly the same order that they arrived in. 

If an inorder traversal of a complete binary tree visits the nodes in the order ABCDEF (where each letter is the value of a node), which order are the nodes visited during an postorder traversal?

ABDECF

DEBFCA

DBFACE

DBACFE

What is not true about a binary search tree?

It is a binary tree

The leftmost node is the smallest node in the tree

When printed with inorder traversal, it will be sorted

BSTs need not be perfect.

Suppose you are trying to choose between an array and a singly linked list to store the data in your Java program. Which arguments would correctly support one side or the other?

Linked lists are better suited to a program where the amount of data can change unpredictably. 

Arrays provide more efficient access to individual elements. 

Linked lists provide more efficient access to individual elements. 

A, B, and C

Array elements can be accessed in constant time, but access to an element of a linked list is O(n), so B is correct and C is incorrect. A is also correct, because arrays require you to guess how much memory will be needed and set aside a fixed amount, while linked lists use memory as needed for the data that are being stored. Since A and B are correct and C is not, the answer is D.

The insertion sort operates by maintaining a sorted list. When a new element is added, we traverse the list sequentially until will find the new element's appropriate location. Suppose instead that the new location was found using a binary search instead of a sequential search. What is the complexity of this new binary insertion sort?

O(N)

O(log N)

O(N + log N)

O(N * log N)

The binary search will indeed speed up finding the location of the newly added object. However, we still have the problem of shifting all subsequent elements. This algorithm, like the regular insertion sort, is O(N²).