h09: Dynamic Arrays, Structures, Linked Lists, Recursion

1.(8 pts) Write a definition for a structure type for records consisting of a person’s wage rate, accrued vacation (in whole days), and status (hourly or salaried - represent the status as one of the two character values ‘H’ and ‘S’). Call the type EmployeeRecord.

2.(12 pts) Write a program that has a definition for a structure type called UndergradStudents. This structure should contain student ID numbers, first and last names, major, and GPA scores for each undergraduate year. The program should declare and then initialize an array of 3 objects of this class (hint: you can do this with the same approach you define/initialize an array of any other type). You must initialize the values in the program, not by user input. The initial values are shown in the table below. The program should then print out some of the values of the array of objects as shown in the sample below, along with each student AVERAGE GPA score (which you should calculate, with a precision of 2 decimal places). You must use a loop to print the output.

Print out the program on a separate sheet of paper and attach it to this homework. Please do not use more than 1 page.

OUTPUT:

These are the student records:
ID# 1, Shmoe, Joe, Major: EE, Average GPA: 3.60
ID# 2, Chen, Macy, Major: CS, Average GPA: 3.95
ID# 3, Sadface, Patrick, Major: ME, Average GPA: 2.77

3.(10 pts) What is the output of the following code? Using a pointer diagram show the evolution of all data objects in memory. 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;

4.(10 pts) Implement a function that takes a simple linked list (that contains integer data) as an input and returns a dynamic array containing the data elements of the linked list. Call the function linkedListToArray (declaration is shown below). Print the function definition on a separate sheet of paper and attach that to this homework. Please do not use more than 1 page.

int* linkedListToArray(LinkedList * list);

5.(20 pts) In class, we went over node insertion in detail. Consider a linked list where each node is of the type struct Node, as defined on display 13.7 on page 754. Complete the definition of the function deleteNode (declaration is shown 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 there is no node with the given value, the function should not do anything. You can assume that the list will not be empty.

Print the function definition on a separate sheet of paper and attach that to this homework. Please do not use more than 1 page.

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

6.(4 pts) How does a recursive function know when to stop recursing?

7.(8 pts) What is a LIFO scheme and how does it relate to stacks?

8.(8 pts) What is stack overflow?

9.(20 pts) Write a recursive function program to find the nth element in the following arithmetic numerical sequence: 3, 11, 27, 59, 123, … You can use a separate sheet of paper for this answer and staple it to this one.

Hint: You first have to figure out what is the recursive pattern. You also have to identify the base case. If you cannot write out the program in the space provided below, then print out the program on a separate sheet of paper and attach that to this homework. Please do not use more than 1 page, one sided.

Some correct example outputs would look like this (there is no repeating loop - these are 2 separate runs):

Which element of the sequence would you like to know?
4
Element number 4 in the sequence is 59.


Which element of the sequence would you like to know?
7
Element number 7 in the sequence is 507.