1
h11
CS16 W18
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h11: Chapter 9: Dynamic memory allocation and dynamic arrays), Chapter 13: Linked-lists

ready? assigned due points
true Tue 02/20 09:00AM Tue 02/27 08:00PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the three lowest scores (if you have zeros, those are the three lowest scores.)


Read Chapter 9, sections 9.1-9.2 (pages 508 - 533), Chapter 13, section 13.1 (pages 740- 759). The key learning goals are dynamic memory allocation and its use in dynamic arrays and linked-lists. If you do not have a copy of the textbook yet, there is one on reserve at the library under “COMP000-STAFF - Permanent Reserve”.

PLEASE MARK YOUR HOMEWORK CLEARLY, REGARDLESS OF IF YOU WRITE IT OUT IN INK OR PENCIL! FOR BEST RESULTS, SAVE THIS PAGE AS A PDF, THEN PRINT THE PDF.

1.(10 pts) What is the output of the following program? Using a pointer diagram show the evolution of all data objects in memory, clearly marking elements on the run-time stack and on the heap. Mark the size of all data objects. Assume the code is embedded in a correct and complete program.

int *p1, *p2, *p3;
p1 = new int;
p2 = new int;
p3 = p1;
*p1 = 20;
*p2 = 30;
cout<< *p1<< " "<< *p2<<" "<<*p3<< endl;
p1 = p2;
cout<< *p1<< " "<< *p2<<" "<<*p3<< endl;
*p3 = *p2;
cout<< *p1<< " "<< *p2<<" "<<*p3<< endl;

2.(10 pts) What is the output of the following program? Using a pointer diagram show the evolution of all data objects in memory, clearly marking elements on the run-time stack and on the heap. Mark the size of all data objects. Assume the code is embedded in a correct and complete program.

int array_size = 4, *a ;
a = new int[array_size];
int *p = a;
for(int i=0; i< array_size; i++)
    *(a+i) = 2*i;
p[0] = 10;
for(int i=0; i< array_size; i++)
    cout<<a[i]<<" ";
cout<<endl;

3.(2 pts) Consider the ‘head’ variable on page 741. What is the value of head for an empty list?

4.(6 pts) Assume you are given a pointer to the head of an existing list (named head). The nodes of the linked-list are of type struct Node (as defined on display 13.7 on page 754). Write a for-loop to iterate through the list and print the data of every other element of the list (starting with the first element).

5.(12 pts) Consider a linked list where each node is of the same type as in the previous question. Complete the definition of the function deleteNode given below, that takes as input a pointer to the head of the list, and an integer value. The function should delete all the nodes in the list whose data members have the given value. If the list is empty or if there is no node with the given value, the function should not do anything.

void deleteNode(struct Node*& head, int value){








































}