CSci 1933 Study Question Set 4CSci 1933 Week 8 Study Questions
These are some self-test questions to check your absorption of the material on singly-linked
lists and inheritance.
Linked List Questions
1. Give two reasons for using a headed rather than a non-headed list.
2. What must the programmer be careful of when using a headed list?
3. Comparing linked lists to arrays to hold sorted data, both will have O(n) insert and delete,
but can you expect one to run faster than the other? Why or why not?
4. Give two advantages of a linked list over an array for representing sorted data where there
will be frequent insertions and/or deletions.
5. For what types of operations will an array be faster than a linked list?
6. Assume we have a *non-headed* linked list of IntNode (from lecture). Complete the method:
public static IntNode delete(IntNode ls, int n) {
to return the list with the n-th node deleted. Indices will start with 0; if n exceeds the length of
the list or n is negative, nothing will be deleted.
7. If we write the same method as in Question (6) above, except with a void signature that does
not return the new list, will the method continue to work in all cases? Explain.
8. Would your answer to Question (7) above change if a headed list were used instead of a
non-headed list? Why or why not?
9. Complete the method reverse() below to reverse the order of the nodes in a headed list.
public static void reverse(IntNode ls) {
10. There are several ways to solve Question (9) above. What is the time complexity of your
solution? Explain.
11. If the method signature remained the same for Question (9) above, but a non-headed list
were used, would your method still work? Explain.
12. At the start of our discussion of linked lists, the question of whether or not a Node was also
a list was raised. Can a Node do what a list can do? Explain. Are Node and list
interchangeable? Explain.
Inheritance Questions
13. What is a widening conversion? What is a narrowing conversion? Give examples of each.
Which are allowed in Java?
14. What is meant by dynamic binding of methods names and method bodies?
15. What is static type checking with Java object references?
16. Assume that a class SUV extends class Car, and a class Car extends a class Vehicle.
Each of the classes contains its own toString() method that returns one of “This is an SUV,”
“This is a Car,” or “This is a Vehicle,” respectively depending on which class (SUV, Car or
Vehicle) it is.
a. Is a Car object an instanceof SUV?
b. Is a Vehicle object an instanceof Car?
c. Given:
Object o = new SUV();
System.out.println(o);
What will be printed?
d. Given:
Vehicle v = new Car();
System.out.println(v);
What will be printed?
e. Given:
Object o = new Car();
Car c = (Car) o;
System.out.println(c);
What will be printed?
f. The second line in part (e) above looks like a narrowing conversion. Is it? Explain. Will
the compiler accept it? Will it run without error?
17. For each of the access modifiers below, indicate when a variable declared (with the given
access modifier) will be inherited by an extending class.
public
private
protected
default
18. “Super” has two contexts: super(…), and super.item. What does super do in each context?
19. When an accessor method is public and inherited by an extending class, the method
becomes part of the extending class. Will the inherited method continue to have access to the
private variables it had access to in the parent class in which it was defined?
20. What is the difference between “overloading” and “overriding” a method between classes.
CSci 1933 Study Question Set 5
CSci 1933 Week 12 Study Questions
These are self-test questions relating to the lecture material application on stacks/queues, binary trees,
hash tables and some other misc. topics.
These are some self-test questions to check your absorption of the lecture material in the last
several weeks of the course covering some of stacks/queues, binary trees, hash tables, and
some other misc. topics.
Binary Trees
1. Compare the amount of space used by a binary search tree implemented as a linked node
structure with the same binary search tree implemented as an array.
2. Complete the BTNodeGen instance method countData(BTNodeGen t) below to return the
number of nodes in a binary tree, t. Assume the BTNodeGen class is the one from the lecture
examples.
public int countData(BTNodeGen t) {
3. Complete the BTNodeGen instance method addLeft(BTNodeGen t, T item) below to return a
new binary tree t that is formed from adding item to the “bottom left” of binary tree t. Use a recursive
algorithm,
public BTNodeGen addLeft(BTNodeGen t, Object item) {
4. Write the same method as in Question 3 above, except this time, assume the binary tree is
represented in an *array* of Object rather than generic BTNodeGen objects.
public static Object[] addLeft(Object[], Object item) {
5. Why are full or complete binary search trees desirable in comparison with binary search trees
that are sparse?
Hash Tables
6. What is the difference between open addressing and chaining for a hash table?
7. Assuming a good hash function that evenly maps keys over a hash table, what is the likey time
time complexity to add, delete, and lookup a key?
8. Worst case, if a hash table has a very poor hash function and most keys collide, what is the
expected time complexity of add, delete, and lookup.
Binary Search and Merge Sort
9. Complete the binary search algorithm below generating a *recursive* process. The method
should return the index of the array where the element was found or -1 if the element is not present.
The array will contain integers.
public static int BSearchRecursive(int[] a, int item) {
10. What is the time complexity of your method in Question 9 above?
11. Given the merge() method from lecture, complete the mergeSort() algorithm below.
public static mergeSort(int[] a, int start, int end, int[] temp) {
12. Explain the time complexity of the merge() method used by mergeSort.
Explain the time complexity of the mergeSort() algorithm.
13. What is the general approach of a “divide and conquer” algorithm?
From our discussion in lecture, which of the following are “divide and conquer” algorithms: recursive
factorial, binary search of an array, mergeSort? Briefly explain.
14. In general, are arrays or linked node structures better for implementing stacks and queues?
Explain.
15. What is the difference between the system stack and system heap? What are each used for?
Which is easier to manage? Briefly explain.
Stacks and Queues
16. Without violating the abstraction barrier of the StackGen.java interface (from lecture examples in
Week 9), complete the instance method below to return a duplicate of “this” stack.
Hint: Use “this” to refer to the stack that is to be duplicated. The duplicate stack should contain all
the same values in the same order as “this” original stack.
public Stack duplicate() {
17. Same as Question 14 above, but this time, make duplicate() a static method as shown to
duplicate the stack passed as parameter, s:
public static StackGen duplicate(StackGen s) {
18. Give the complexity of your method in the question above. Briefly explain.
5. (10 points) Given the following interfaces and classes,
public interface Person {
String getName();
int getID();
String getCategory();
}
public class Member implements Person {
…
public String toString() {
return “Member”;
}
}
public class BoardMember extends Member {
…
public String toString() {
return “Executive Board”;
}
}
public abstract class Student implements Person {
…
}
public class GradStudent extends Student {
…
}
public class UndergradStudent extends Student {
…
}
a. (8 points)
For the eight Java statements below, identify each of the following statements as legal or illegal, and whether legal
or not, state whether it represents a “narrowing,” or “widening”
conversion, or neither.
Object u1 = new GradStudent();
Legal or Illegal
Narrowing, Widening or Neither
BoardMember b = new Member();
Legal or Illegal
Narrowing, Widening or Neither
GradStudent g1 = new Student();
Legal or Illegal
Narrowing, Widening or Neither
Student s1 = new UndergradStudent();
Legal or Illegal
Narrowing, Widening or Neither
UndergradStudent u2 = new Member();
Legal or Illegal
Narrowing, Widening or Neither
Person p2 = new GradStudent();
Legal or Illegal
Narrowing, Widening or Neither
Member m2 = new Person();
Legal or Illegal
Narrowing, Widening or Neither
b. (2 points)
Given: Member m = new BoardMember();
What will be printed by: System.out.println(m.toString());
Questions 6 and 7 refer to the following BTNodeGen code modified from lecture.
public class BTNodeGen {
// constructor
public BTNodeGen(T d, BTNodeGen l, BTNodeGen r) {
data = d;
left = l;
right = r;
}
// selectors
public BTNodeGen getLeft() { return left; }
public BTNodeGen getRight() { return right; }
public T getData() { return data; }
// instance variables
private T data;
private BTNodeGen left;
private BTNodeGen right;
public int search(T s) {
if (getData().compareTo(s) == 0)
return -1;
else if (getLeft() != null && getLeft().search(s) != -1)
return 1 + getLeft().search(s);
else if (getRight() != null && getRight().search(s) != -1)
return 1 + getRight().search(s);
return 1;
}
public static void main(String[] args) {
:
// assume tree t (drawn below) is defined here
:
System.out.println(“Searching A at: ” + t.search(“A”));
System.out.println(“Searching C at: ” + t.search(“C”))
System.out.println(“Searching X at: ” + t.search(“E”));
System.out.println(“Searching E at: ” + t.search(“X”));
} // main
} // BTNodeGen.java