SOMEONE KIND PLEASE ANSWER THESE CORRECTLY. A. Using the Java programming langua
ID: 3590331 • Letter: S
Question
SOMEONE KIND PLEASE ANSWER THESE CORRECTLY.
A. Using the Java programming language, implement the deque ADT with a doubly linked list.
B.Implement an adapter class in Java programming language to support the stack interface using the methods from the array list ADT.
C.Use pseudo-code to describe an algorithm for computing the number of descedents of each node of a binary tree. The algorithm should be based on the Euler tour traversal.
D.Use pseudo-code to describe a nonrecursive method for performing an inorder traversal of a binary tree in linear time.
E.Illustrate the execution of the heap-sort algorithm on the following input sequence: (2, 5, 16, 4, 10, 23, 39, 18, 26, 15).
F.Draw the 11-entry hash table that results from using the hash function h(i)=(3i+5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by chaining.
G.What is the worst-case time for putting n entries in an initially empty hash table, with collisions resolved by chaining? What is the best-case?
H.Use pseudo-code to describe the design algorithms for the following operations for a binary tree T. (5% each)
a.preorderNext(T, o): return the node visited after node o in a preorder traversal of T.
b.inorderNext(T, o): return the node visited after node o in an inorder traversal of T.
c.postorderNext(T, o): return the node visited after node o in a postorder traversal of T.
Explanation / Answer
A. The code below indicates the Deque implementation by using doble linked list.
package com.java2novice.ds.queue;
public class DequeDblLinkedListImpl<T> {
private Node<T> front;
private Node<T> rear;
public void insertFront(T item){
//add element at the beginning of the queue
System.out.println("adding at front: "+item);
Node<T> nd = new Node<T>();
nd.setValue(item);
nd.setNext(front);
if(front != null) front.setPrev(nd);
if(front == null) rear = nd;
front = nd;
}
public void insertRear(T item){
//add element at the end of the queue
System.out.println("adding at rear: "+item);
Node<T> nd = new Node<T>();
nd.setValue(item);
nd.setPrev(rear);
if(rear != null) rear.setNext(nd);
if(rear == null) front = nd;
rear = nd;
}
public void removeFront(){
if(front == null){
System.out.println("Deque underflow!! unable to remove.");
return;
}
//remove an item from the beginning of the queue
Node<T> tmpFront = front.getNext();
if(tmpFront != null) tmpFront.setPrev(null);
if(tmpFront == null) rear = null;
System.out.println("removed from front: "+front.getValue());
front = tmpFront;
}
public void removeRear(){
if(rear == null){
System.out.println("Deque underflow!! unable to remove.");
return;
}
//remove an item from the beginning of the queue
Node<T> tmpRear = rear.getPrev();
if(tmpRear != null) tmpRear.setNext(null);
if(tmpRear == null) front = null;
System.out.println("removed from rear: "+rear.getValue());
rear = tmpRear;
}
public static void main(String a[]){
DequeDblLinkedListImpl<Integer> deque = new DequeDblLinkedListImpl<Integer>();
deque.insertFront(34);
deque.insertFront(67);
deque.insertFront(29);
deque.insertFront(765);
deque.removeFront();
deque.removeFront();
deque.removeFront();
deque.insertRear(43);
deque.insertRear(83);
deque.insertRear(84);
deque.insertRear(546);
deque.insertRear(356);
deque.removeRear();
deque.removeRear();
deque.removeRear();
deque.removeRear();
deque.removeFront();
deque.removeFront();
deque.removeFront();
}
}
class Node<T>{
private Node<T> prev;
private Node<T> next;
private T value;
public Node<T> getPrev() {
return prev;
}
public void setPrev(Node<T> prev) {
this.prev = prev;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
B. I've implemented the basic logic of a stack data structure
C. ALGORITHM DESCRIPTION FOR TRAVERSAL USING EULER COMPUTATION
Tree has global variable T.cnt initialized to 0
1. stores number of nodes seen so far
2. Each node has a local variable cnt
3.Visit on the left: increment T.cnt and set cnt = T.cnt
4.Visit on the right: set number of descendants v.desN = T.cnt - cnt
PSEUDO CODE
countEuler(T,v)
T.cnt++ //saw one more node, namely node
v cnt = T.cnt; //number of nodes seen so far
if T.hasLeft (v) then countEuler(T,T.left) //explore nodes to the left of v
if T.hasRight (v) then countEuler(T,T.right) //explore nodes to the right of v
//at this point we explored all descendants of node v
v.desN = T.cnt – cnt
D.
PSEUDOCODE:
E. EXECUTION OF HEAP SORT ALGORITHM
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.