联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2021-02-24 11:27

ECE36800 Non-Programming Homework Exercise #5

Due Friday, February 26, 2021, 11:59pm (Submit through Gradescope)

IMPORTANT: Read and complete the following Academic Honesty Statement. Failure in

submitting a complete academic honest statement will result in a 0 for this homework.

“In signing this statement, I hereby certify that the work on this exercise is my own and

that I have not copied the work of any other student while completing it. I understand that,

if I fail to honor this agreement, I will be subject to disciplinary action as outlined in the

course policy.”

Printed Name:

login:

Signature:

I have discussed this homework with:

This homework covers learning objective 1: An understanding of basic data structures, including

stacks, queues, and trees; learning objective 2: An understanding of basic data structures,

including stacks, queues, and trees.

ECE36800 Purdue University 1

c Cheng-Kok Koh

1. The following functions construct a binary search tree from a sorted array.

1 typedef struct _Tnode {

2 int info ;

3 struct _Tnode * left ;

4 struct _Tnode * right ;

5 } Tnode ;

6

7 Tnode * Tnode_construct ( int info )

8 {

9 Tnode * node = malloc ( sizeof (* node ) ) ;

10 if ( node == NULL ) {

11 fprintf ( stderr , " can ’ t get memory \ n ") ;

12 return NULL ;

13 }

14 node -> info = info ;

15 node -> left = node - > right = NULL ;

16 return node ;

17 }

18

19 Tnode * BST_build ( int * array , int lb , int ub )

20 {

21 if ( lb > ub ) {

22 return NULL ;

23 }

24 int mid = ( lb + ub ) /2;

25 Tnode * node = Tnode_construct ( array [ mid ]) ;

26 if ( node == NULL ) {

27 return NULL ;

28 }

29 node - > left = BST_build ( array , lb , mid - 1) ;

30 node - > right = BST_build ( array , mid + 1 , ub ) ;

31 return node ;

32 }

Consider the statements in the main function:

33 int array [] = {1 , 3 , 5 , 7, 9 , 11 , 13 , 15};

34 int array_size = sizeof ( array ) / sizeof ( array [0]) ;

35 Tnode * bst = BST_build ( array , 0 , array_size - 1) ;

Draw the computation tree that corresponds to the function call BST build(array, 0, array size

- 1). You should show the last two parameters of the recursive function BST build in each node

of the computation tree.

Draw the binary search tree constructed.

ECE36800 Purdue University 2

c Cheng-Kok Koh

Ignoring the space required to store the array and the space to store the binary search tree, what

is the space complexity when array size is n? What is the time complexity when array size is

n? Justify your answers.

ECE36800 Purdue University 3

c Cheng-Kok Koh

2. This question is based on a question from Spring 2017 Exam 1. The following code fragment

defines a structure for storing a binary tree and a function for re-constructing a binary search tree

from an array of integers. The integers in the array are ordered according to the postorder traversal

of the original binary search tree. We also assume that all integers are distinct. Also assume that

all malloc calls are successful.

1 typedef struct _tnode {

2 int value ;

3 struct _tnode * left , * right ;

4 } tnode ;

5

6 tnode * build_bst_from_postorder ( int * array , int lb , int ub )

7 {

8 if ( lb > ub ) {

9 return NULL ;

10 }

11 tnode * node = malloc ( sizeof (* node ));

12 node -> value = array [ ub ];

13

14 // find the left subtree and the right subtree of node in the array

15 // assume that all integers in left subtree <= node -> value

16 int partition_idx = lb ;

17 while (( partition_idx < ub ) && ( array [ partition_idx ] <= array [ ub ])) {

18 partition_idx ++;

19 }

20 node -> left = build_bst_from_postorder ( array , lb , partition_idx -1);

21 node - > right = build_bst_from_postorder ( array , partition_idx , ub -1);

22 return node ;

23 }

(a) Instead of using a linear search to search for partition idx, replace lines 16–19 with an

iterative binary search to determine partition idx. Write down the pseudo-code for a suitable

replacement.

(b) Consider the replacement that you have made in (a). Let n be the number of integers in the array

passed to the function build bst from postorder. (i) What is the worst-case space complexity

for the re-construction of the entire binary search tree in terms of n using the big-O notation? (ii)

What is the best-case space complexity? Justify your answers. Your answers should not include

the space required for the input array and the re-constructed binary search tree.

(c) Consider the replacement that you have made in (a). Let n be the number of integers in the array

passed to the function build bst from postorder. (i) What is the worst-case time complexity

for the re-construction of the entire binary search tree in terms of n using the big-O notation? (ii)

What is the best-case time complexity? It is important to take into account the time complexity in

ECE36800 Purdue University 4

c Cheng-Kok Koh

executing lines 16–19 (the replaced version in (a)) of the function. Justify your answers.

ECE36800 Purdue University 5

c Cheng-Kok Koh

3. This question is based on a question from Spring 2019 Exam 2. The following code fragment

defines a structure for storing a binary tree and a function for re-constructing a binary search tree

(BST) from an array of integers. The integers in the array are ordered according to the preorder

traversal of the original BST. The array is called preorder in the function. Assume that all malloc

calls are successful.

typedef struct _Tnode {

int key ;

struct _Tnode * left ;

struct _Tnode * right ;

} Tnode ;

Tnode * Reconstruct_BST ( int * index , int * preorder , int size , int ub )

{

if (* index >= size )

return NULL ;

if ( preorder [* index ] > ub )

return NULL ;

Tnode * node = malloc ( sizeof (* node ));

node -> key = preorder [* index ];

* index += 1;

node -> left = Reconstruct_BST ( index , preorder , size , node -> key );

node -> right = Reconstruct_BST ( index , preorder , size , ub );

return node ;

}

(a) The following statements are in the main function.

int preorder [] = {16 , 12 , 10 , 14 , 20 , 18};

int index = 0; // initial position in preorder array

int size = sizeof ( preorder )/ sizeof ( preorder [0]); // array size

Tnode * root = Reconstruct_BST (& index , preorder , size , INT_MAX );

Draw the re-constructed BST. Note that INT MAX is the largest int possible. You may treat it

as ∞.

(b) Draw the computation tree that corresponds to the recursive calls of the function Reconstruct BST

in 3(a). The node that corresponds to the first call is shown below. The two terms in the node

correspond to *index and ub, where index and ub are parameters passed to the function. You

computation tree must show *index and ub in each node.

0, INT_MAX

*index, ub

(c) Let n be the number of integers in the preorder array passed to Reconstruct BST. (i) What

is the worst-case space complexity for the re-construction of the entire BST in terms of n using the

ECE36800 Purdue University 6

c Cheng-Kok Koh

big-O notation? (ii) What is the best-case space complexity? Justify your answers. Your answers

should not include the space required for the input array and the re-constructed BST.

(d) Let n be the number of integers in the preorder array passed to Reconstruct BST. (i) What

is the worst-case time complexity for the re-construction of the entire BST in terms of n using the

big-O notation? (ii) What is the best-case time complexity? Justify your answers.

ECE36800 Purdue University 7

c Cheng-Kok Koh

4. Consider the function Reconstruct BST in question 3. Write a version of that with the tail

recursion removed. We call the new version Reconstruct BST trr.

void Reconstruct_BST_trr ( int * index , int * preorder , int size ,

int ub , Tnode ** root )

{

}

ECE36800 Purdue University 8

c Cheng-Kok Koh


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp