Introduction to Data Structures and Software Engineering

CS1704 : Summer Session II 2000 : Midterm 2

Question One [20]
  1. List one advantage and one disadvantage of doubly linked lists, as compared to singly linked lists. [5]

    2. Advantage: We can find the previous element without a traversal from the Head so some insertion/deletion operations are faster.
    Disadvantage: More space required for additional pointers.

  2. What is a dangling pointer? Write a few lines of code to illustrate the inappropriate use of a dangling pointer. [5]

    3. A dangling pointer is a pointer that points to a block of memory that has been deallocated or which does not belong to the program. 

    int *p = new int;  // create dynamic variable
delete p;          // destroy dynamic variable, creating dangling pointer
*p = 5;            // illegally dereference the dangling pointer

  3. Is recursion a better solution technique than iteration? Justify your answer. [5]

    4. Sometimes it is and at other times iteration is better.
    For some problems recursive solutions are easier to implement and understand. For other problems, iterative solutions may be more natural and they execute faster. Thus, the choice has to be made based on the specific problem being considered.

  4. In the context of OOP, copy constructors and assignment operators perform almost the same task. What are the two assumptions we can make when writing copy constructors, that we cannot make when writing assignment operators? [5]

    5. The object does not already exist.
    The object is not being copied onto itself.

Question Two [15]

Indicate the correct answer for each of the following:
  1. Deep copying is necessary to copy an object ...
    1. with static variables, when the object is passed by value to a function
    2. with static variables, when the object is passed by reference to a function
    3. with dynamic variables, when the object is passed by value to a function
    4. with dynamic variables, when the object is passed by reference to a function
    5. in none of the above situations
  2. An example of de-referencing is:
    1. int &a = b;
    2. c = &d;
    3. int *e = f;
    4. g = *h;
    5. none of the above
  3. Insertion at the tail (before the head in the case of a circular list) requires a full traversal of this type of linked list:
    1. Linear, singly linked list, only a head pointer
    2. Linear, doubly linked list, head and tail pointers
    3. Circular, doubly linked list, only a head pointer
    4. a and c
    5. a, b and c
  4. Recursion allows us to solve problems by ...
    1. defining them in terms of smaller versions of themselves
    2. iteratively looping over successively smaller problems
    3. reusing a single function to solve multiple instances of a problem
    4. a and c
    5. a, b and c
  5. A destructor is ...
    1. called automatically by the compiler/runtime environment
    2. called when an object is destroyed
    3. used to deallocate dynamic variables in an object
    4. a and c
    5. a, b and c

Question Three [40]

  1. List two possible reasons to use a linked list instead of an array. [6]

    2. Size of data is not known a priori.
    Some operations on the list are more efficient (eg. sorted insertion)

  2. To store a fixed number of integers, which always uses more memory: a singly linked list or an array? Why? [4]

    3. Singly linked list, because extra space is required for the pointers in each node.

  3. If an array is encapsulated within a class, a byte-by-byte comparison of its instances will be sufficient to prove equality of the data. Is this also true if a linked list is encapsulated within a class? Why or why not? [4]

    4. Yes, because the Head is in the class, and if the heads are equal then, trivially, the lists are equal.

    or

    No, because only the Head is in the class and if the Heads are different the lists of nodes need to be traversed so that each corresponding pair of dynamic nodes stored externally to the object is checked.

  4. Write the constructor for a typical singly linked list with head and tail pointers (assume that it is not inline). [6]

    5. LinkedList::LinkedList ()
{
   Head = NULL;
   Tail = NULL;
}

  5. Write out the definition for a non-recursive function that computes and returns the number of nodes in a doubly linked list. Use the following node type definition and function prototype. [10]
    6. struct Node 
{
   int Data;
   Node *Next, *Prev;
};

int CountNodes ( Node *Start );


    int CountNodes ( Node *Start )
{
   int Count = 0;
   while (Start != NULL)
   {
      Count++;
      Start = Start->Next;
   }
   return Count;
}

  6. Now rewrite the same function from Question 5, but this time recursively. [10]

    7. int CountNodes ( Node *Start )
{
   if (Start == NULL)
      return 0;
   else
      return 1+CountNodes (Start->Next);
}

Question Four [25]

Consider the following C++ function:

void SomeFunction ( NodeType *n )
{
   if (Head == NULL)
      Head = n;
   else
      Tail->Next = n;
   n->Next = NULL;
   Tail = n;
}
  1. What does the function do? [5] Insertion at the tail
  2. Is the list singly linked or doubly linked? [2] singly
  3. Is the list linear or circular? [2] linear
  4. Will this function work if there are already 3 nodes in the list? [2] yes
  5. Will this function work if there are no nodes already in the list? [2] yes
  6. Will the function work if called as "SomeFunction (NULL)"? [2] no
  7. Is this a recursive function? [2] no
  8. Does memory for "n" have to be assigned/allocated before the function is called? [2] yes
  9. Name one field/variable that is part of the "NodeType" struct. [2] Next
  10. Which of "Head", "Tail" and "n" are pointers? [2] All
  11. What is another valid syntax for "n->Next"? [2] (*n).Next