讲解data留学生、辅导Python，Java编程设计、讲解c/c++语言

August, 2020 Final
Question 1. [20 marks]
Implement the function int findHeightTree(Position> root); that computes the height
of a binary tree. The following functions are available for your use:
• Position> left(Position> 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> right(Position> 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> 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> 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> LinkedListQueue();
∗ Constructor of the queue
– void enqueue(Vertex u);
∗ Inserts into a queue
– Vertex dequeue();
∗ Removes from the queue
– boolean isEmpty();
∗ Checks if the queue is empty
• Graph ADT:
– Iterable> outgoingEdges(Vertex u);
∗ Returns an iterable list of outgoing edges that are incident to u
– Iterable> vertices();
∗ Returns an iterable list of vertices in the Graph
– int numVertices();
∗ Returns the total number of vertices in the Graph
– Vertex opposite(Vertex v, Edge e);
∗ Returns the vertex that forms the edge e with vertex v
• Vertex Class:
– int getLabel(Vertex 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> LinkedListStack();
∗ Constructor of the stack
– void push(Vertex u);
∗ Inserts into a stack
– Vertex pop();
∗ Removes from the stack
– boolean isEmpty();
∗ Checks if the stack is empty
• Graph ADT:
– Iterable> outgoingEdges(Vertex u);
∗ Returns an iterable list of outgoing edges that are incident to u
– Iterable> vertices();
∗ Returns an iterable list of vertices in the Graph
– int numVertices();
∗ Returns the total number of vertices in the Graph
– Vertex opposite(Vertex v, Edge e);
∗ Returns the vertex that forms the edge e with vertex v
• Vertex Class:
– int getLabel(Vertex 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