Test Review Questions -------------------- String and Recursion -------------------- You may only use these methods from String class for problems 1-6 o public char charAt(int index); o public String substring(int beginIndex); o public boolean equals(Object o); Implement the following methods 1) public boolean contains(String s, char c); /*This method should return true if the given string contains the given character and false otherwise. Implement this problem using RECURSION only.*/ 2) public String sameWithout(String s, char c); /*This method should return the String given with all the occurrences of the given char taken out. exp. sameWithout("abc", 'b'); should return "ac". Implement this problem using RECURSION only.*/ 3) public boolean isAll(String s, char c); /*This method should return true is all characters in s are equal to c and false if and only if s contains some letter other than c. For example, isAll("", 'b') would return true, isAll("aaaaa",'a') would return true, and isAll("aaabaaa", 'a') would return false. You must use RECURSION only to implement this method.*/ 4) public String replaceOccurancesOf(String s, char from, char to); /*This method should return a string that is the same as s, except with all occurances of the character from replaced by the character to. You must use RECURSION only to implement this method. */ 5) public int firstIndexOf(String s, char c); /*This method should return the index of the first occurence of c in the String s, or -1 if c does not appear in s. For example, firstIndex("", 'x') should return -1, firstIndexOf("abcde", 'c') should return 2 and firstIndexOf("qwexy", 'd') should return -1. You must use RECURSION only to implement this method.*/ 6) public int countOccurancesOf(String s, char from, char to); /*This method should return a count of the number of times the character c appears in s. For example, countOccurencesOf("",'b') should return 0, countOccurencesOf("abceabaa",'a') should return 4 and countOccurencesOf("abcdefq",'q') should return 1. You must use RECURSION only to implement this method.*/ Refer to the following inheritance structure for problems 8, 11, and 15: public class Animal{ public String name; public static animalCount=0; //A count of all the animals created public Animal(){ this("Bob"); } public Animal(String name){ this.name=name; animalCount++; } public void eat(){ System.out.println("Yummy"); } public void speak(){ System.out.println("I am an Animal. My name is "+ this.name); } public String toString(){ return "I am an animal named " + this.name; } } public class Dog extends Animal{ public void speak(){ System.out.println("Woof. My name is "+this.name); } public void play(){ System.out.println("I am playing."); } public String toString(){ return "I am a dog named " + this.name; } } public class Cat extends Animal{ public void speak(){ System.out.println("Meow. My name is " + this.name); } public void nap(){ System.out.println("Taking a nap. Zzzzzz"); } public String toString(){ return "I am an cat named " + this.name; } } ------------ Polymorphism ------------ 7) Why is Polymorphism useful? 8) Using the above classes, which of the following code segements is valid? a) Dog d=new Animal(); b) Animal a=new Dog(); c) Cat c=new Cat(); d) Dog d=new Cat(); e) Animal a=new Dog(); Cat c=new Cat(); a=c; --------------- Dynamic Binding --------------- 9) What is Dynamic Binding? 10) How does Dynamic Binding relate to Polymorphism? 11) Using the above classes what would be the output for the following pieces of code: a) Dog d=new Dog(); dog.eat(); b) Animal a=new Dog(); a.play(); c) Animal a=new Dog(); a.speak(); d) Dog d=new Dog(); ((Animal)d).speak(); e) Animal a=new Cat(); ((Cat)a).nap(); f) Animal a=new Dog(); ((Cat)a).speak(); ------------------ Static Vs Instance ------------------ 12) What is the difference between an instance variable/method and a static variable/method? 13) When would you want to use an instance variable? 14) When would you want to use a static variable? 15) Consider the following code: Dog d=new Dog("Fido"); Cat c=new Cat("Fluffy"); Animal a=new Animal(); System.out.println(d); System.out.println(d.animalCount); System.out.println(c) System.out.println(c.animalCount); System.out.println(a); System.out.println(a.animalCount); 16) What would be the output of the above code? 17) What would be the output of the above code if we made the name variable static? if we made the animalCount variable an instance variable? ----------- Linked List ----------- 18) What are linked lists? 19) Why would you use one? What are some advantages over other data structures we have learned about? For problems 20-24, assume that you have a standard (as in p2) LLNode implementation and write the following methods from the LinkedList class: 20) public void removeAllRec(Object data); /*This method will remove the all occurances of this object found in the list. You must use RECURSION only for this method*/ 21) public void removeAllItr(Object data); /*This method will remove the all occurances of this object found in the list. You must use ITERATION only for this method*/ 22) public boolean find(Object data); /*This method should return true if the data is found in the list and false otherwise*/ 23) public int size(); /*this method should return the number of nodes in the list*/ 24) Assume that you are given a typical LLNode, and a LinkedList class, but it is possible that the LinkedList might end up wihth a loop in it, rather than terminating at null. One algorithm to find out if there is a loop is to have two references, and advanced one by one step and the other by two steps repeatedly. if one ever reaches null, there is no loop, if they both reference the same node [besides at the very start], there is a loop. Implement the method public boolean hasALoop() /*This method determines if a loop exists in the LinkedList.*/ ------- Stacks ------- 25) What is a stack? 36) Give an real life example of a stack. 27) How would this relate to a linked list? What restrictions would there if you used a linked list to implement a stack? ----- Queue ----- 28) Whats is a queue? 29) Give a real life example of a queue. 30) How would this relate to a linked list? What restrictions would there if you used a linked list to implement a queue?