tailieunhanh - Faculty of Computer Science and Engineering Department of Computer Science Part 2

Tham khảo tài liệu 'faculty of computer science and engineering department of computer science part 2', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Faculty of Computer Science and Engineering Department of Computer Science DATA STRUCTURES ALGORITHMS Tutorial 2 Questions Linked List Stack and Queue Part 1. Linked List We use linked lists to represent polynomials whose coefficients are integers. For example the list in Figure 1 will represent for fo 6x3 5x2 8x 3 head tail Figure 1. Required Questions Question 1. Draw the lists for the following expressions a. i 2x2 1 b. X d. 4 3x3 x l 2X 1 2t5 3 3 2x -1 2 ĩ-f6 fĩ f4 3x g- -f h. p Note Operation V denotes our polynomials division where the remainders will be discarded and the result coffeicients will be rounded to integer values. For more information of polynomial division refer to http greenFcourses 152a polyexp For example x2 1 2 1 2 x2 1 2 x2 l coefficients rounded X4 3x2- 5 X2 4x X2 - 4x 19 remainder discarded Question 2. x4 3x2 - 5 x 2 4 - 4x 3x2 -5 v 2 -4x x 19 The list is implemented as a class List. In Listing 1 is the algorithm of a method to calculate f k where is the object calling the method and k a constant. algorithm addConstant val k int 1. tmp head 2. while tmp- next is not NULL 1. tmp tmp- next 3. tmp- data tmp- data k 4. return endaddConstant Listing 1 Develop similar algorithms for the methods of the following operations Page 1 10 Faculty of Computer Science and Engineering Department of Computer Science a. b. c. d. e. f - k f k f 10 f X f f Page 2 10 Faculty of Computer Science and Engineering Department of Computer Science Part 2. Stack Suppose that the following algorithms are implemented - Pushstack ref s Stack val n data push the value n to the stack s - PopStack ref s Stack ref x data remove the top element of the stack s and assign the data of that top element to x - EmptyStack val s Stack check whether the stack s is empty Required Questions Question 3. Imagine we have two empty stacks of integers s1 and s2. Draw a picture of each stack after the following operations 1 PushStack s1 1 2 PushStack s1 9 3 .