代做data留学生、代写Python，Java编程设计、代做c/c++语言

日期：2020-08-23 02:33

August, 2020 Final

Question 1. [20 marks]

Implement the function int findHeightTree(Position<Entry<V,K>> root); that computes the height

of a binary tree. The following functions are available for your use:

? Position<Entry<V,K>> left(Position<Entry<V,K>> root);

– This function returns the reference to the left child of the input argument root. This value will

be NULL if root is a leaf node.

? Position<Entry<V,K>> right(Position<Entry<V,K>> root);

– This function returns the reference to the right child of the input argument root. This value

will be NULL if root is a leaf node.

The function findHeightTree takes in one argument (Position<Entry<V,K>> root) which is the root of

the tree. This function returns an integer indicating the height of the tree. You may not create any helper

functions. You can only use recursion. If you are not sure about the definition of the height of a tree,

write your assumption and carry on with the question.

Page 2 of 12 cont’d. . .

Examination EECS 2011

public int findHeightTree(Position<Entry<V,K>> root)

{

}

Page 3 of 12 over. . .

August, 2020 Final

Question 2. [20 marks]

Implement the function int maxVerticesTraversal() that computes the maximum vertices that can be

traversed in a connected directed Graph. Consider the following diagram:

For instance, starting from vertex 0, the total number of vertices that can be traversed is 6 (i.e. vertices

0, 1, 2, 4, 3, 2, 5) whereas starting from vertex 3, you can traverse two vertices (i.e. 3 and 5). Hence,

for this Graph the function should return the value 6. You may assume that the following definitions and

declarations are provided to you:

? Queue ADT:

– LinkedListQueue<Vertex<V>> LinkedListQueue();

? Constructor of the queue

– void enqueue(Vertex<V> u);

? Inserts into a queue

– Vertex<V> dequeue();

? Removes from the queue

– boolean isEmpty();

? Checks if the queue is empty

? Graph ADT:

– Iterable<Edge<E>> outgoingEdges(Vertex<V> u);

? Returns an iterable list of outgoing edges that are incident to u

– Iterable<Vertex<V>> vertices();

? Returns an iterable list of vertices in the Graph

– int numVertices();

? Returns the total number of vertices in the Graph

– Vertex<V> opposite(Vertex<V> v, Edge<E> e);

? Returns the vertex that forms the edge e with vertex v

? Vertex Class:

– int getLabel(Vertex<V> u);

? Returns the integer label associated with the vertex u

Hint: You may use breadth-first traversal from each vertex in the graph to compute the total number of

vertices traversed. You may not define additional helper functions.

Page 4 of 12 cont’d. . .

Examination EECS 2011

public int maxVerticesTraversal()

{

}

Page 5 of 12 over. . .

August, 2020 Final

.

Page 6 of 12 cont’d. . .

Examination EECS 2011

Question 3. [20 marks]

Implement a function boolean isCycle() that detects whether a cycle exists in a directed Graph. This

function will return true if there exists a cycle in the graph and false otherwise. You may assume that

the following classes and functions are available to you:

? Stack ADT:

– LinkedListStack<Vertex<V>> LinkedListStack();

? Constructor of the stack

– void push(Vertex<V> u);

? Inserts into a stack

– Vertex<V> pop();

? Removes from the stack

– boolean isEmpty();

? Checks if the stack is empty

? Graph ADT:

– Iterable<Edge<E>> outgoingEdges(Vertex<V> u);

? Returns an iterable list of outgoing edges that are incident to u

– Iterable<Vertex<V>> vertices();

? Returns an iterable list of vertices in the Graph

– int numVertices();

? Returns the total number of vertices in the Graph

– Vertex<V> opposite(Vertex<V> v, Edge<E> e);

? Returns the vertex that forms the edge e with vertex v

? Vertex Class:

– int getLabel(Vertex<V> u);

? Returns the integer label associated with the vertex u

Hint: You may use depth-first search to identify cycles from each node in the Graph. You may not define

helper functions.

Page 7 of 12 over. . .

August, 2020 Final

public boolean isCycle()

{

}

Page 8 of 12 cont’d. . .

Examination EECS 2011

.

Page 9 of 12 over. . .

August, 2020 Final

[Use the space on this page for rough work. Indicate clearly any work you want us to mark.]

Page 10 of 12 cont’d. . .

Examination EECS 2011

[Use the space on this page for rough work. Indicate clearly any work you want us to mark.]

Page 11 of 12 over. . .

[Use the space on this page for rough work. Indicate clearly any work you want us to mark.]

Page 12 of 12 Total Marks = 60 End of Final Examination