a. array
     b. singly-linked list
     c. doubly-linked list
     d. queue
     e. stack

For each of the following questions choose the best answer from the above list. Sometimes it may seem as though two or more choices would be equally good. In those cases think about the operations that the data structures support and choose the data structure whose operations are best suited for the problem. You may have to use the same answer for more than one question:

1. ____________ The most space-efficient data structure you could use to implement a stack in which there is an upper limit, max, on the number of elements that can be stored on the stack.
2. ____________ The most space-efficient data structure you could use to implement a stack in which the the number of elements that can be stored on the stack is unlimited.
3. ____________ The data structure which allows any of its elements to be accessed in constant time.
4. ____________ The data structure you would use if you needed to be able to insert an element anywhere in the data structure.
5. ____________ The data structure you would use to ensure that the last item added to the data structure is always the first item removed from the data structure.
6. ____________ The data structure that allows you to traverse its elements in either forward or reverse order.
7. ____________ The easiest data structure you could use to implement a queue with an unbounded number of elements.
8. ____________ The data structure you would use to ensure that items are always added to the end of the data structure and removed from the front of the data structure.

1. Which program has the better guarantee on the running time, for large values of N (N > 10,000)?

2. Which program has the better guarantee on the running time, for small values of N (N < 100)?

3. Which program will run faster on average for N = 1,000?

4. If you did not know the size of the input, which program would you prefer to use? Why?

     struct node {
         struct node *next;
	 struct node *prev;
	 int value;
     };

     struct node *my_node;

1. Suppose you are given the following information:

        my_node = 0xa0
        my_node->prev = 0x9c
        my_node->next = 0xb4
        my_node->value = 6
        my_node->next->next = 0xc8
        my_node->next->value = 8
        

   Draw the memory diagram for my_node and its successor node. In particular, label the boxes in the following diagram with the appropriate hexadecimal addresses and in each box either indicate the name of the field and the value stored at that memory location or leave the box blank if the contents at that memory location are unknown.

                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
   		     |                              |
   		     |                              |
                        --------------------------------
        

2. Write a fragment of code that swaps my_node and its predecessor by adjusting only the links (and not the data). You may declare whatever temporary variables you need in order to perform the swap.

     int max_sum(int *array, int size, int *save_i, int *save_j) {
         int max = 0;
	 int i, j;

	 for (i = 0; i < size-1; i++) {
	     for (j = i+1; j < size; j++) {
	          if (array[j] > array[i]) {
		      if ((array[j] + array[i]) > max) {
		          max = array[j] + array[i];
			  *save_i = i;
			  *save_j = j;
		      }
		  }
	     }
          }
	  return max;
      }
      

1. What is T(size) for the inner-most loop? You are allowed to use i in your mathematical expression for T(n). Note that size represents the size of the input for max_sum. Hint: when trying to figure out how many times the inner loop will iterate, choose the most pessimistic value of i possible. Remember that we are looking for the worst case, not the best case or even the average case.

2. What is T(size) for max_sum as a whole?

3. What is the big-O running time of max_sum?

4. Suppose main has the following declarations:

         #define SIZE 10
         int a[SIZE];
         int max;
         int index1;
         int index2;
         

   Write a line of code that will call max_sum and save the return result in max, the value of save_i in index1 and the value of save_j in index2.

• f(n) = 10n + 3n log n + 6
• f(n) = 6n³ - 4n² - 3n - 1000
• f(n) = 23
• f(n) = .000005n² + 5000000n - 20