Feaculty of Computer Science and Engineering Department of Computer Scienc Tutorial 3 Questions

Chia sẻ: P.lOc Loc | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

84
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

For each of the AVL trees obtained in Question 1 determine the tree obtained when the root is withdrawn. Question 3. Write a global function in pseudo code to generate an AVL tree from an input list by insert elements in the list into an initial empty AVL. Refer to Question 1 for an example. algorithm generateAVLfromList (val list ) This algorithm generate a AVL from the input list Pre Post the AVL is built by inserting elements in the list into an initial empty tree one-by-one from the beginning...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Feaculty of Computer Science and Engineering Department of Computer Scienc Tutorial 3 Questions

Faculty of Computer Science and Engineering Department of Computer Science DATA STRUCTURES & ALGORITHMS Tutorial 3 Questions Recursion and Binary Tree Part 1. Recursion Required Questions Question 1. What would be the contents of queue Q1 after the following code is executed and the following data are entered? 1 Q1 = createQueue 2 S1 = createStack 3 loop (not end of file) 1 read number 2 if (number not 0) 1 pushStack (S1, number) 3 else Q1= 5, 4, 6, 8, 67, 32,9,5 1 popStack (S1, x) 2 popStack (S1, x) 3 loop (not empty S1) S1= 10,6,20,23,54 1 popStack (S1, x) 2 enqueue (Q1, x) 4 end loop 4 end if 4 end loop The data are: 9, 5, 10, 4, 0, 5, 4, 6, 8, 67, 32, 25, 51, 0, 54, 23, 20, 6, 10 Question 2. The following algorithm is to reverse a queue Algorithm append ((val q , val s Algorithm reverse (val q ) )) Pre true Pre true Return a reversed queue of q Return a reversed queue of q 1 S = createStack 2 Q = createQueue 1 S = createStack 3 while (not empty(q)) 2 Q = creatQueue 1 dequeue(q,temp) 3 while(not empty(S)) 2 pushStack(S,temp) 1 popStack(S,temp) 4 while (not empty(S)) 2 enqueue(q,temp) 1 popStack(S,temp) reverse(Q) 4 2 enqueu (Q,temp) 5 while(not empty(q)) 4 return Q 1 dequeue(q,temp) End reverse 2 enqueue(Q,temp) 6 return Q Develop a similar algorithm to append a stack to a queue Algorithm append (val q , val s ) End append Pre true 1/ 4
Faculty of Computer Science and Engineering Department of Computer Science Return element of s is appended into q with the same order. For example if q = {1,2,3}, s = {4,5,6} then q = {1,2,3,4,5,6} after append. Queue {front ... rear} Stack {bottom ... top} 6,5,4 Question 3. 4,5,6 Consider the following algorithm: Algorithm fun1 (x ) 1 if (x < 5) 1 return (2 * x) 2 else 1 return (2 * fun1 (x – 2) + 5) 3 end if end fun1 What would be returned if fun1 is called as a. fun1 (4)? 8 b. fun1 (5)? 17 c. fun1 (8)? 47 aánh 3233 (2*(2*2 d. fun1 (20)? Question 4. Algorithm compute (x ) Develop recursive algorithm for the following problems. 1 if (x =0) 1 return (0) a. Compute the sum of all numbers from 1 to n, where n is given as parameter. 2 else Algorithm compute (val n ) 1 return (n+compute(n-1)) Pre n >=0 Return the sum 0 + 1+ 2+ 3+ ...+ n 3 end if b. Find and return the maximum element in an array, where the array and its size are given as parameters. Algorithm compute (val a , val n ) Algorithm compute (val a , val n ) Pre n >=0 1. if (n=0) Return the maximum element in a[] 1 return a[0] 2.else Advanced Questions return (compute(a,n)>compute(a,n-1))?compute(a,n):compute(a,n-1) Question 5. Develop recursive algorithm for the following problems. a. Find and return an element in an array, where the array and its size are given as parameters. This element should be in middle position when the array is re- ordered increasingly. 2/ 4
Faculty of Computer Science and Engineering Department of Computer Science Algorithm compute (val a , val n ) Pre n >=0 Return the the element in the middle position when the array is reordered increasingly in a[] For example if a = {4,1,5,2,3}, then the value of the last element should be returned. b. Could we design an algorithm for solving question (a) without sorting the array? Algorithm compute (val a , val n ) Pre n >=0 Return the the element in the middle position when the array is reordered increasingly in a[] Question 6. Develop algorithms for the following problems. The algorithms must be fully recursive in that they contain no loops at all (neither for, while or do-while). a. Algorithm listnumber (val start , val end ) Pre start =0 Return the power ab. The only two arithmetic operations that you are allowed to use in this problem are multiple * and subtraction - return (b==1)?a:a*pow(a,b-1) append (Queue*Q,Stack *S) Question 7. Pre true Develop fully recursive algorithms for the functions reverse and aReturn ia reversed queue of q ppend n Question 2 S=new Stack(); Q = new Queue(); while(S->top!=NULL) popStack(S,temp) enqueue(q,temp) reverse(Q) while(Q->front!=NULL) dequeue(q,temp) 3/ 4 enqueue(Q,temp) return Q End append
Faculty of Computer Science and Engineering Department of Computer Science 1. if (subroot is NULL) 1. Allocate subroot Part 2. Binary Tree 2. subroot->data = DataIn Required Questions 3. return success 2. else if (DataIn.key < subroot->data.key) Question 8. 1. return recursive_Insert(subroot->left, DataIn) 3. else if (DataIn.key >tsubroot->data.key) For each of the following key sequences determining he binary search tree obtained when the keys are inserted one-by-one in 1. return recursive_Insert(subroot->right, DataIn) 4 the order given into an initially empty tree: 1 4. else 6 2 1. return duplicate_error2 1 a) 1, 2, 3, 4, 5, 6, 7. 3 3 5. End recursive_Insert 6 b) 4, 2, 1, 3, 6, 5, 7. 7 1 5 4 2 c) 1, 6, 7, 2, 4, 3, 5. 5 7 4 6 Question 9. 2 1 7 For each of the binary search trees obtained3in Question 1, d2 etermine the tree obtained 6 5 3 when the root is withdrawn. 4 6 2 4 7 5 3 3 Question 10. 5 7 1 Write a global function in pseudocode to generate a BST from an input list 6 insert by elements in the list into an initial empty BST. Refer to Question 1 for an example. 7 algorithm generateBSTfromList (val list ) This algorithm generate a BST from the input list Pre Post the BST is built by inserting elements in the list into an initial empty tree one-by-one from the beginning of the list. Return the BST end generateBSTfromList Advanced Questions Question 11. Devise an algorithm that takes two values, a and b such that a < b, and which visits all the keys x in a binary search tree such that a  x  b. 4/ 4