COP 4530 Homework 4

Exercises 6.4

2. Write an algorithm to determine the average of a linked list of real numbers with first node pointed to by

first.

4. Write an algorithm to determine whether the data items in a linked list with first node pointed to by first

are in ascending order.

Page 1 of 7

COP 4530 Homework 4

9. The shuffle-merge of two lists x1, x2, . . . , xn and y1, y2, . . . , ym is the list

z =

x1, y1, x2, y2, . . . , xn, yn, yn+1, yn+2, . . . , ym n < m

x1, y1, x2, y2, . . . , xm, ym, xm+1, xm+2, . . . , xn n > m

x1, y1, x2, y2, . . . , xn, yn n = m

Write an algorithm to shuffle-merge two linked lists with first nodes pointed to by first1 and first2,

respectively. The items in these two lists should be copied to produce the new list; the original lists should

not be destroyed.

10. Proceed as in Exercise 9, but do not copy the items. Just change links in the two lists (thus destroying the

original lists) to produce the merged list.

Page 2 of 7

COP 4530 Homework 4

Exercises 6.6

1. An ordered linked list of characters has been constructed using the array-based implementation described in

this section. The following diagram shows the current contents of the array that stores the elements of th

linked list and storage pool:

Node Data Next

[0] J 3

[1] Z 6

[2] C 0

[3] P -1

[4] B 2

[5] M 1

[6] K 7

[7] Q 8

[8] ? 9

[9] ? -1

first = 4 free = 5

(a) List the elements of this list.

(b) List the nodes in the storage pool in the order in which they are linked together.

2. Assuming the contents of the array node pictured in Exercise 1, show the contents of node and the values of

first and free after the letter F is inserted into the list so that the resulting list is in alphabetical order.

Page 3 of 7

COP 4530 Homework 4

3. Proceed as in Exercise 2, but for the operation Delete J.

4. Proceed as in Exercise 2, but for the following sequence of operations: Delete J, Delete P, Delete C, Delete B

5. Proceed as in Exercise 2, but for the following sequence of operations: Insert A, Delete P, Insert K, Delete C

Page 4 of 7

COP 4530 Homework 4

6. Assuming the array-based implementation as described in this section, write a function to count the nodes in

a linked list.

7. Assuming the array-based implementation as described in this section, write a boolean-valued function that

determines whether the data items in the list are arranged in ascending order.

Page 5 of 7

COP 4530 Homework 4

8. Assuming the array-based implementation as described in this section, write a function that returns a pointer

to the last node in a linked list.

9. Assuming the array-based implementation as described in this section, write a function to reverse a linked list

in the manner described in Exercise 12 of Section 6.4.

Page 6 of 7

COP 4530 Homework 4

Worksheet Questions

1. Give asymptotic bounds on the worst-case time complexity of your algorithms for Exercises 6.4 questions 2.,

4., 9. and 10 and for Exercises 6.6 questions 7., 8., and 9. Justify your answer.

Page 7 of 7

Sale!

# COP 4530 Homework 4

$30.00

## Reviews

There are no reviews yet.