代做CS 2468、Python，Java，c/c++编程设计调试、data代写

日期：2020-05-07 11:11

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: