Practice Questions for Exam 3

The following are a set of questions to help you prepare for Exam 3. I recommend trying out these problems with paper and pencil. Remember that any material from the course is eligible, whether or not it appears in a problem below. There will be a focus on material from after the second exam, however since most things build on our previous work, ideas from those first weeks will appear as well.

Topics these questions cover:

• Memory Allocation: realloc, free, dynamically allocated arrays
• ADTs: Queues
• Pointers to Functions
• Linked List implementations

Problem 1

Suppose that we have a dynamically allocated array called arr, where elements of the array contain pointers to a structure type called someStruct.

a) Write code to change the size of the array to 100.

b) Suppose that arr containts non-NULL pointers in the first m indices. Write code to free all of the relevant memory in arr.

c) Why do we free dynamically allocated memory? What can go wrong if we neglect to free memory?

Problem 2

a) What functions would we like to have in the interface of a queue ADT?

b) Write code for a structure (or structures) to hold the relevant implementation details needed to create a queue with a dynamically allocated array.

c) Write code for a structure (or structures) to hold the relevant implementation details needed to create a queue with a linked list.

Problem 3

Suppose you are asked to write a program to compute a circle’s circumfrence and area for radii between 0 and 9. The desired output might be:

radius   circumference   area
0.0000      0.0000      0.0000
1.0000      6.2832      3.1416
2.0000     12.5664     12.5664
3.0000     18.8496     28.2743
4.0000     25.1327     50.2655
5.0000     31.4159     78.5398
6.0000     37.6991    113.0973
7.0000     43.9823    153.9380
8.0000     50.2655    201.0619
9.0000     56.5487    254.4690

In order to limit some redundancy in the code, write a function named myPrint. myPrint should take in two parameters, the radius, and a function f which takes in and returns a double. myPrint should not return anything.

Then, fill in the main function to create the desired output table by repeated calls to your function myPrint.

/* program to compute a circle's circumference and area using function with a function parameter */

#include <stdio.h>
#include <math.h>

/* identity function (return the value given) */
double identity (double radius)
{
  return radius;
} // identity


/* calculate the circumference of a circle given its radius */
double circum (double radius)
{
  return 2 * M_PI * radius;
} // circum


/* calculate the area of a circle given its radius */
double area (double radius)
{
  return M_PI * radius * radius;
} // area


/* main processing */
int main (void)
{



  return 0;
} // main

Problem 4

Suppose we want to implement a variation of a linked list which is circular. In particular, each node contains two links, one to the previous and one to the next. Additionally, the first node’s “previous” node is defined to be the last node in the list, and the last node’s “next” node is defined to be the first node.

Create the following pieces of the ADT implementation:

• Struct for the list. Include a pointer to the first and the last nodes. (head and tail)
• Struct for nodes.
• A function for insertion at the front of the list. Be sure to consider edge cases!