Sale!

COP 4530 Homework 4

\$30.00

Category:

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
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
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

Reviews

There are no reviews yet.