讲解CS 2468、Python，Java，c/c++编程设计调试、data辅导
- 首页 >> Java编程 CS 2468 Midterm test (March 20, 2020)
Hint: Since this is an on-line test, the workload is very heavy so that you do not have time to
do other things. Each question, contains a large number of sub-questions. If you do not have
enough time to complete all the sub-questions, please try to do the first few sub-questions (that
have heavy weights) and ignore the last few sub-questions (that have relatively light weights).
In general, the first few sub-questions are easier than the last few sub-questions.
Question 1. (Binary tree and heap)
(a) Give the in-order, post-order and pre-order traversal for the following binary tree:
(b) Give the heap (in terms of the complete binary tree) after inserting an entry with key=2 in the
following heap:
1
/ \
3 4
/ \ / \
8 5 9 6
Answer:
(c) Give the heap (in terms of the complete binary tree) after removeMin() from the following
heap:
1
/ \
3 4
/ \ / \
8 5 9 6
Answer:
(d) Give the array representation of the heap in (b).
Answer:
Question 2. (Estimating running time in terms of Big Oh notation)
Describe the worst case running time of the following pseudocode functions in Big-Oh notation.
(a)
void test (int n){
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < n/2; ++i ) {
++sum;
}
}
}
Answer: total running time is _____________.
(b)
void test (int n, int sum) {
for (int i = 0; i < n * 100; ++i) {
for (int j = n; j > 0; j--) {
sum++; }
for (int k = 0; k < i; ++k){
sum++;}
}
}
Answer: total running time is _____________.
(c)
void happy (int n, int sum) {
int j = n;
while (j > 2) {
sum++;
j = j / 2;
}
}
Answer: total running time is _____________.
(d)
int sum(int n) {
if (n != 0)
return n + sum(n-1);
else
return n;
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
(e)
int f(int n){// n is a positive integer
if (n <= 1)
return 2;
else
return 2 * f(n - 1);
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
(f)
int ff(int n){// n is a positive integer
if (n<=1) return 2;
int x=n/2;
int y=ff(n/2);
if (2*x==n){
return y*y;
}
else{
return 2*y*y;
}
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
(g) (hard)
int fff(int n){// n is a positive integer
if (n<=1) return 2;
int x=n/2;
if (2*x==n){
return fff(n/2)*fff(n/2);
}
else{
return 2*fff(n/2)*fff(n/2);
}
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
Question 3. (Recursive methods) For this question, you are not allowed to use global variables.
(a) For class DList, add a recursive method “public int min(DNode h)” that returns the smallest
number in the list (assuming that element part of each DNode in the list is of class Integer
and the input parameter DNode h of the method is the header of the list).
Answer:
(b) For class DList, add a recursive method “public int count(DNode h)” that returns the number
of DNodes whose element part is an integer >10 (assuming that element part of each DNode
in the list is of class Integer and the input parameter DNode h of the method is the header of
the list).
Answer:
(c) For class BinaryTree, add a recursive method “public int count(BNode r)” that returns the
number of nodes (BNodes) whose element part is an integer >10 in the tree rooted at r
(assuming that element part of each BNode is of class Integer).
Answer:
(d) For class BinaryTree, add a recursive method “public int numLR(BNode h)” that returns the
number of notes (BNodes) in the binary tree rooted at r that have both left and right children.
Answer:
Question 4. (links)
(a) For class DList, add an iterative method “public int min()” that returns the smallest number
in the list (assuming that element part of each DNode in the list is of class Integer and the
input parameter DNode h is the header of the list). Your method should go through every
node in the list. Here method min() does not have any input parameter.
Answer:
(b) For class DList, add a method “public void remove(DNode p)” that removes the node p from
the list (assuming that p is a node in the list).
Answer:
(c) For class BinaryTree, add a function “public Boolean isRIght(BNode p)”, that returns true if
and only if node p is the right child of its parent.
Answer:
(d) For class BinaryTree, add a function “public void remove(BNode b)” that removes BNode b
from the binary tree if b is a leaf. Otherwise, the binary tree has no change. (Here we assume
that b is a node in the binary tree.)
Answer:
Question 5.
Define a class TNode that contains two attributes “Object element “ and “DList list”, where
the type of element is Object and the class of list is DList. Moreover, list contains a list of children
for the current node. The class supports the following methods:
1. “public Object getElement()” that returns the value of attribute element;
2. “public void setElement(Object elem)” that sets the value of attribute element to be elem;
3. “public DList getDList()” that returns the attribute list,
4. “public void addTNode (TNode x, TNode c)” that adds node c as the first node in x.list
(by call insertFirst() in DLIst.
5. “public static void main(String args[])” that creates five nodes of type TNode, where (1)
TNode y=(“g”, null) that is the only child for its parent, (2) three TNodes (“b”, null),
(“c”, null), and (“d”, list4), where list4 contains one item/child y=(“g”, null); (3) another
TNode x=(“a, list1), where the attribute list=list1, and list1 contains the three nodes (of
class TNode) (“b”, null), (“c”, null), and (“d”, list4). Here the strings “a”, “b”, “c”, “d”
and “g” are the values for the attribute element for different TNodes. See the following
figure:
(“a”, list1)
(“b”, null)ß>(“c”, null)ß>(“d”, list4)
(“g”, null).
This is a tree with root (“a”, list) that has three children (“b”, null), (“c”, null), and (“d”,
list4), where (“d”, list4) has a child (“g”, null).
(“a”, list1)
(“b”, null) (“c”, null). (“d”, list4)
(“g”, null).
Bonus: (5% for midterm)
Define a class Tree, where each node in the tree is of class TNode, it has attributes root
and numElements, where root is the root of the tree and numElements is the number of
nodes in the tree. The class supports a method “public void addChild(TNode x, TNode
y)” that adds y as the first child of x and the old children of x remain the same, e.g., if x
has 2 children as follows:
(“c”, null)ß>(“d”, list4),
after addChild(TNode x, TNode y), where y=(“b”, null), x now has 3 children as follows:
(“b”, null)ß>(“c”, null)ß>(“d”, list4).
Answer:
Hint: Since this is an on-line test, the workload is very heavy so that you do not have time to
do other things. Each question, contains a large number of sub-questions. If you do not have
enough time to complete all the sub-questions, please try to do the first few sub-questions (that
have heavy weights) and ignore the last few sub-questions (that have relatively light weights).
In general, the first few sub-questions are easier than the last few sub-questions.
Question 1. (Binary tree and heap)
(a) Give the in-order, post-order and pre-order traversal for the following binary tree:
(b) Give the heap (in terms of the complete binary tree) after inserting an entry with key=2 in the
following heap:
1
/ \
3 4
/ \ / \
8 5 9 6
Answer:
(c) Give the heap (in terms of the complete binary tree) after removeMin() from the following
heap:
1
/ \
3 4
/ \ / \
8 5 9 6
Answer:
(d) Give the array representation of the heap in (b).
Answer:
Question 2. (Estimating running time in terms of Big Oh notation)
Describe the worst case running time of the following pseudocode functions in Big-Oh notation.
(a)
void test (int n){
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < n/2; ++i ) {
++sum;
}
}
}
Answer: total running time is _____________.
(b)
void test (int n, int sum) {
for (int i = 0; i < n * 100; ++i) {
for (int j = n; j > 0; j--) {
sum++; }
for (int k = 0; k < i; ++k){
sum++;}
}
}
Answer: total running time is _____________.
(c)
void happy (int n, int sum) {
int j = n;
while (j > 2) {
sum++;
j = j / 2;
}
}
Answer: total running time is _____________.
(d)
int sum(int n) {
if (n != 0)
return n + sum(n-1);
else
return n;
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
(e)
int f(int n){// n is a positive integer
if (n <= 1)
return 2;
else
return 2 * f(n - 1);
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
(f)
int ff(int n){// n is a positive integer
if (n<=1) return 2;
int x=n/2;
int y=ff(n/2);
if (2*x==n){
return y*y;
}
else{
return 2*y*y;
}
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
(g) (hard)
int fff(int n){// n is a positive integer
if (n<=1) return 2;
int x=n/2;
if (2*x==n){
return fff(n/2)*fff(n/2);
}
else{
return 2*fff(n/2)*fff(n/2);
}
}
Answer:
The recurrence equation for running time is :
Total running time is _____________.
Question 3. (Recursive methods) For this question, you are not allowed to use global variables.
(a) For class DList, add a recursive method “public int min(DNode h)” that returns the smallest
number in the list (assuming that element part of each DNode in the list is of class Integer
and the input parameter DNode h of the method is the header of the list).
Answer:
(b) For class DList, add a recursive method “public int count(DNode h)” that returns the number
of DNodes whose element part is an integer >10 (assuming that element part of each DNode
in the list is of class Integer and the input parameter DNode h of the method is the header of
the list).
Answer:
(c) For class BinaryTree, add a recursive method “public int count(BNode r)” that returns the
number of nodes (BNodes) whose element part is an integer >10 in the tree rooted at r
(assuming that element part of each BNode is of class Integer).
Answer:
(d) For class BinaryTree, add a recursive method “public int numLR(BNode h)” that returns the
number of notes (BNodes) in the binary tree rooted at r that have both left and right children.
Answer:
Question 4. (links)
(a) For class DList, add an iterative method “public int min()” that returns the smallest number
in the list (assuming that element part of each DNode in the list is of class Integer and the
input parameter DNode h is the header of the list). Your method should go through every
node in the list. Here method min() does not have any input parameter.
Answer:
(b) For class DList, add a method “public void remove(DNode p)” that removes the node p from
the list (assuming that p is a node in the list).
Answer:
(c) For class BinaryTree, add a function “public Boolean isRIght(BNode p)”, that returns true if
and only if node p is the right child of its parent.
Answer:
(d) For class BinaryTree, add a function “public void remove(BNode b)” that removes BNode b
from the binary tree if b is a leaf. Otherwise, the binary tree has no change. (Here we assume
that b is a node in the binary tree.)
Answer:
Question 5.
Define a class TNode that contains two attributes “Object element “ and “DList list”, where
the type of element is Object and the class of list is DList. Moreover, list contains a list of children
for the current node. The class supports the following methods:
1. “public Object getElement()” that returns the value of attribute element;
2. “public void setElement(Object elem)” that sets the value of attribute element to be elem;
3. “public DList getDList()” that returns the attribute list,
4. “public void addTNode (TNode x, TNode c)” that adds node c as the first node in x.list
(by call insertFirst() in DLIst.
5. “public static void main(String args[])” that creates five nodes of type TNode, where (1)
TNode y=(“g”, null) that is the only child for its parent, (2) three TNodes (“b”, null),
(“c”, null), and (“d”, list4), where list4 contains one item/child y=(“g”, null); (3) another
TNode x=(“a, list1), where the attribute list=list1, and list1 contains the three nodes (of
class TNode) (“b”, null), (“c”, null), and (“d”, list4). Here the strings “a”, “b”, “c”, “d”
and “g” are the values for the attribute element for different TNodes. See the following
figure:
(“a”, list1)
(“b”, null)ß>(“c”, null)ß>(“d”, list4)
(“g”, null).
This is a tree with root (“a”, list) that has three children (“b”, null), (“c”, null), and (“d”,
list4), where (“d”, list4) has a child (“g”, null).
(“a”, list1)
(“b”, null) (“c”, null). (“d”, list4)
(“g”, null).
Bonus: (5% for midterm)
Define a class Tree, where each node in the tree is of class TNode, it has attributes root
and numElements, where root is the root of the tree and numElements is the number of
nodes in the tree. The class supports a method “public void addChild(TNode x, TNode
y)” that adds y as the first child of x and the old children of x remain the same, e.g., if x
has 2 children as follows:
(“c”, null)ß>(“d”, list4),
after addChild(TNode x, TNode y), where y=(“b”, null), x now has 3 children as follows:
(“b”, null)ß>(“c”, null)ß>(“d”, list4).
Answer: