C代写|C++代写|算法代写|数据结构: 这是一个基于C/C++进行的数据结构设计，包含了算法的一些知识和内容。
CS241: Data Structures and Algorithms
1. Which of the following statement is not true?A)Abstract data types like stack and queue support code-reuse so people can use them in problem-solving without implementing them repeatedlyB) Abstract data types like stack and queue support their alternative implementations so existingprojects can benefit from their new more efficient implementationsC) Abstract data types like stack and queue support divide-and-conquer so projects for theirimplementation and usage can progress in parallelD)Abstract data types like stack and queue ensure their more efficient implementation2. What is the output of executing the following program?
import java.util.*;
public class StackDemo {
public static void main(String[] args) {
String text = "sator arepo tenet opera rotas";
System.out.println(f(text)? "true" : "false");
}
static boolean f(String t) {
Stack<Character> s = new Stack<Character>();
char[] c = t.toCharArray();
int i = 0;
for (; i < c.length/2; i++)
s.push(new Character(c[i]));
if (c.length != 2*(c.length/2)) i++;
try {
for (; i < c.length; i++)
if (c[i] != s.pop().charValue()) return false;
}
catch (Exception e) {
return false;
}
return true;
}
}
A) True
B) False
3. Given the following binary search tree, what would the call bst.preorder() produce?
public void preorder() {System.out.print(getInfo() + " ");
if (left != null)left.preorder();if (right != null)right.preorder();}
4. Which of the following statement is true?
A. The best case running time complexity of the Euclid algorithm for finding the greatest common
divider is O(log N).
B. The worst case running time complexity of the binary search algorithm is O(log N).
C. The search algorithm using a hash table takes O(log N) on average.
D. A simple binary search tree always guarantees searching time in O(log N) while an AVL tree or
a red-black search tree does not.
5. Implement the following method to use not a specific primitive data type, but a Generic Type data as
parameter.
public void delete(int k){
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry "+ k +" is not present");
else {
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
}
}
6. You will implement a LinkedHashSet.java class using the following interfaces;
a. LinkedHashSetNodeInterface.java //givenb. LinkedHashSetInterfece.java //needs to be completed
The implementations;
c. LinkedHashSetNode.java //needs to be completedd. LinkedHashSet.java //needs to be completed
e. LinkedHashSetTester.java //driver for the set, given
f. TestObject.java //given
Properties of a LinkedHashSet you will implement;
- Uses Doubly Linked List ADT to hold items in it, LinkedHashSetNode is used for thenodes
- Does not allow duplicate values
- Items are ordered in insertion order
- BigO value for add, remove, contains methods is O(N)
- BigO value for clear, isEmpty, size methods is O(1)
public interface LinkedHashSetNodeInterface <E>{
//returns the information saved in the node
public E getInfo();
//modify/set the info of the node
public void setInfo(E e);
//returns next node reference
public LinkedHashSetNode<E> getNext();
//set next node reference of the node
public void setNext(LinkedHashSetNode<E> l);
//returns prev node reference
public LinkedHashSetNode<E> getPrev();
//set prev node reference of the node
public void setPrev(LinkedHashSetNode<E> l);
}
Constructors for LinkedHashSetNode;
public LinkedHashSetNode();
public LinkedHashSetNode(E info);
The interface you need to implement for the LinkedHashSet.java;
public interface LinkedHashSetInterface <E> {
//adds a new node to the set with data e
//returns true if added, false otherwise
public boolean add(E e);
//removes the node from the set with data e
//returns true if removed, false otherwise
public boolean remove(E e);
//checks the set if the item e is in
//returns true if set has e, false otherwise
public boolean contains(E e);
//clears the set
public void clear();
//returns true if there is at least one item in the set
//false otherwise
public boolean isEmpty();
//returns the number of items in the set
public int size();
}
Constructors for LinkedHashSet;
public LinkedHashSet();
Use the TestObject.java below;
public class TestObject {
private String value;
public TestObject(String s){
value = s;
}
public String getValue(){
return value;
}
public void setValue(String s){
value = s;
}
public String toString(){
return value;
}
public boolean equals(Object o){
if(o == null)
return false;
TestObject t = (TestObject) o;
return (value.equals(t.getValue()));
}
}
Use the following tester for your LinkedHashSet.java;
public class LinkedHashSetTester {
public static void main(String[] args) {
System.out.println("Using String items");
LinkedHashSet<String> lhs1 = new LinkedHashSet<>();
lhs1.add("One");
lhs1.add("One");
lhs1.add("Two");
lhs1.add("Three");
lhs1.add("Two");
lhs1.add("Four");
lhs1.add("Five");
lhs1.add("Six");
lhs1.add("Three");
System.out.println(lhs1.size());
System.out.println(lhs1);
System.out.println("");
System.out.println("Remove method test");
lhs1.remove("Two");
System.out.println(lhs1.size());
System.out.println(lhs1);
System.out.println("");
System.out.println("Remove everything one by one test");
lhs1.remove("One");
System.out.println(lhs1);
lhs1.remove("Three");
System.out.println(lhs1);
lhs1.remove("Four");
System.out.println(lhs1);
lhs1.remove("Five");
System.out.println(lhs1);
lhs1.remove("Six");
System.out.println(lhs1);
System.out.println("");
System.out.println("Using TestObject items String");
LinkedHashSet<TestObject> lhs2 = new LinkedHashSet<>();
TestObject p = new TestObject("Peter");
TestObject q = new TestObject("Peter");
TestObject r = new TestObject("Jack");
TestObject t = new TestObject("Kelly");
TestObject y = new TestObject("Frank");
TestObject z = new TestObject("Jack");
lhs2.add(p);
lhs2.add(r);
lhs2.add(q);
lhs2.add(t);
lhs2.add(y);
lhs2.add(z);
System.out.println(lhs2.size());
System.out.println(lhs2);
System.out.println("");
System.out.println("Remove method test using
TestObject");
lhs2.remove(y);
lhs2.remove(p);
System.out.println(lhs2.size());
System.out.println(lhs2);
System.out.println("");
System.out.println("Empty Set tester");
lhs2.clear();
System.out.println(lhs2);
}
}
Sample Output:
run:
Using String items
6
OneTwoThreeFourFiveSix
Remove method test
5
OneThreeFourFiveSix
Remove everything one by one test
ThreeFourFiveSix
FourFiveSix
FiveSix
Six
Using TestObject items String
4
PeterJackKellyFrank
Remove method test using TestObject
2
JackKelly
Empty Set tester
BUILD SUCCESSFUL (total time: 0 seconds)