Data Structures代写、代做CS、Java，Python编程设计、Algorithms程序代做

日期：2021-01-14 10:34

School of Computer Science

Data Structures & Algorithms Endterm Class Test

Class Test 2020/21

1

Data Structures & Algorithms Endterm Class Test

1. A circular doubly linked list Abstract Data Type has a private header pointer, called lst ,

which points to the first node of a circular doubly linked list. This ADT does not maintain

a specific header pointer to the last node of the list.

Given a pointer to a node n , assume that values can be read or written to by using the

field names n.prev , n.val and n.next for the previous, value and next fields of the

node respectively.

Assume that a garbage collector is being used, so nodes do not need to be explicitly freed.

Use END for invalid or null address pointer values.

cddl delete last is a member function of the ADT that removes the last element from

the list (if there is one). Fill in the missing part of the pseudocode for this function below:

1 void c d d l d e l e t e l a s t ( )

2 {

3 // WRITE THE CODE THAT SHOULD BE HERE

4 r e t u r n

5 }

[5 marks]

2

2. For each of the following functions to calculate the largest element of an array, state which

complexity class in big O notation the function belongs to and justify your answer with a

short explanation:

(a)1 i n t l a r g e s t 1 ( i n t [ ] a r r ) {

2 i n t n = a r r . l e n g t h ;

3 i n t max = 0 ;

4

5 f o r ( i n t i =0; i <n ; i ++) {

6 b o o l l a r g e s t = t ru e ;

7 f o r ( i n t j =0; j<n ; j ++) {

8 i f ( a r r [ i ] < a r r [ j ] )

9 l a r g e s t = f a l s e ;

10 }

11

12 i f ( l a r g e s t )

13 max = a r r [ i ] ;

14 }

15 r e t u r n max ;

16 }

[5 marks]

(b)1 i n t l a r g e s t 2 ( i n t [ ] a r r ) {

2 i n t n = a r r . l e n g t h ;

3 i n t max = 0 ;

4

5 i f ( a r r . l e n g t h == 0 ) {

6 r e t u r n 0 ;

7 } e l s e {

8 max = a r r [ 0 ] ;

9 f o r ( i n t i =0; i <n ; i ++) {

10 i f ( a r r [ i ] > max )

11 max = a r r [ i ] ;

12 }

13 r e t u r n max ;

14 }

15 }

[5 marks]

(c)1 i n t l a r g e s t 3 ( i n t [ ] a r r ) {

2 s o r t ( a r r ) ;

3

4 i f ( a r r . l e n g t h == 0 ) {

5 r e t u r n 0 ;

6 } e l s e {

7 i n t l a s t = a r r [ a r r . l e n g t h − 1 ] ;

8 r e t u r n l a s t ;

9 }

10 }

[5 marks]

3

3. Consider a binary search tree used to store integers with methods isEmpty(t) , left(t) ,

right(t) and root(t) , to return whether the tree t , is empty, the left child tree, the

right child tree and the integer value stored at the root respectively.

• Write a recursive function sum rec(tree) to calculate and return the sum of all

integers stored in the tree. [5 marks]

• A Queue ADT has, for a queue q , methods q.enqueue(val) and q.dequeue()

to enqueue a value val in the queue and to dequeue and return a value from the queue

respectively. It also has a constructor which can be invoked with the commmand

new Queue() to create and return a new empty queue.

Write the pseudocode for a non-recursive function sum nonrec(tree) , to calculate

and return the sum of all integers stored in the tree. [10 marks]

4. Draw the result of merging the following two Binomial Heaps: