MCX1/4
Math
Department
Mr. Gary Jaye
Danny
Jaye, A.P.S.
1993 Question 3 from APCS AB Exam: Part II (adapted for C++)
This problem concerns linked lists of integers defined as follows.
struct NodeType {
int Info;
NodeType *Next;
};
A. Write a function ListSum whose header is given below. The function ListSum
has one
NodeType * parameter L. ListSum returns a new
linked list with one node whose Info field
contains the sum of the values in L. By definition, the sum of
the values of the empty list is 0.
For example:
L--->[2|]--->[-3|]--->[9|]--->[3|/]
ListSum(L)--->[11|/]
Complete function ListSum below the following header.
NodeType *ListSum(NodeType *L) {
// precondition: L represents the list (a1, a2,...,
an), n ³ 0
// postcondition: ListSum returns a pointer to the
one-element list (m), where m = a1 + a2 +
...+ an
B. Consider a linked list, each of whose elements is a linked list of integers. Such
lists are implemented
using the following definitions.
struct LLNodeType {
NodeType *Ptr;
LLNodeType *Next;
};
Write a function ListOfListSums whose header is given
below. ListOfSums has one parameter M of type
LLNodeType *. If M is NULL, ListOfListSums
returns NULL; otherwise ListOfListSums returns a new
linked list of integers with the property that the value stored
in the kth node of the new list is sum of the integers
in the kth element of M.
For example:
M--->[|]--->[|]--->[|]--->[/|]--->[|/]
|
| |
|
[5]
[9] [10]
[-3]
[ ]
[/] [
]
[/]
|
|
[6]
[0]
[ ]
[/]
|
[-2]
[/]
ListOfListSums(M)--->[9|]--->[9|]--->[10|]--->[0|]--->[-3|/]
Complete ListofListSums below the following header.
NodeType *ListOfListSums(LLNodeType *M) {
// precondition: M represents the list of lists (L1,
L2,..., Ln), n ³
0
// postcondition: ListOfListSums returns a pointer to a list
of integers (a1, a2,..., an)
//
such that for all k, 1 £ k £ n, ak = ListSum(Lk).