Key for Exam 2

• Problem 1

  (a)
  apvector <node <Item>> myNodes;
  int myNumNodes;
  
  grading
  10 pts for myNodes
  5 pts for myNumNodes
  

  
  

  (b)

  template <class Item>
  int graph<Item>::NumberOfEdges() const
  {
     int num = 0;
  
     for(int i=0; i<myNumNodes; i++)
         num += list_length(myNodes[i].link());
  
     return = num/2;
  }
  
  grading
  5 pts for header, 10 pts for body, 10 pts for division by 2

  
  

  
  

• Problem 2
  
  

  A:0	B:1	C:9	D:10
  E:1	F:1	G:8	H:8
  I:11	J:3	K:2	L:2
  M:5	N:6	O:7	P:4
  Q:3	R:4	S:5	T:6

  
  grading
  40 pts if everything is correct.
  30 pts if non-alphabetical order was used.
  10 pts otherwise.
  
  

• Problem 3

  (a) 1 3 3 7 7 9 11 30
  
  grading
  -5 pts if  descending order
  -5 or -15 pts if some numbers are missing, depending on the description in (b)
  
  (b) It merges two singly linked-lists. The resulting list will be sorted in acending order, given that the original lists were already sorted.
  
  grading
  -5 pts if descending order
  -10 pts if incorrect description
  

• Problem 4

  int j;
  for(j = i+1; j<myNumberNodes; j++) // checking row
       if(myMatrix[i][j])
              neighbors.push_back(myNodes[j]);
  for(j=0; j<i; j++)  // checking column
       if(myMatrix[j][i])
              neighbors.push_back(myNodes[j])
  
  grading
  -15 pts for picking up only "half" the neighbors by using only one loop.