Exam - Practise Questions (set 2)

Past Exam Papers 

1.  Explain the main difference between a stack and a queue.  
    Use the terms LIFO and FIFO in your explanation.

    (2 marks)

2.  Why does a linked-list implimentation of a queque need to store a
    pointer at both the head an the tail nodes, whereas a linked-list
    implimentation of a stack only needs to store a pointer at 
    the top of the node?

    (2 marks)


3.  Imagine a stack of integers which is originally empty.  The following
    sequence of operations is performed where PS represents a push 
    operation, and PP represents a pop operation.  Each push places the 
    number in brackets onto the stack.

    PS(5)  PS(17)  PP  PS(107)  PS(90)  PP  PS(15)  PS(38)

    If the stack is now popped until it is empty again, show the 
    sequence of numbers which would be generated.

    (2 marks)

4.  The following declaration appeared in a C program

    struct datanode
      {
         char               givenname[10];
         struct datanode    *next;
      }
   
    struct datanode  *list;

    list is a pointer to a linked list which is to be used to store a list
    of names in alphabetical order.  At a particular moment in the 
    processing of this list it will contain nodes for the 4 names POWER,
    DALTON, WALTERS and GREEN.

    a)  Draw a diagram showing the list pointer list and the 4 nodes,
        including arrows showing how the pointers are arranged to create 
        the list in the required order.  Be sure to include a 'head' pointer
        and end of list marker.

    b)  Draw another diagram showing the list after the name SMITH is
        added to the list

    c)  Draw another diagram showing the list after the name ADAMS is added
        to the list.

    d)  Draw another diagram showing the list after the names GREEN and
        WALTERS have both been removed fromt he list

    e)  Write down a sequence of C statements which would have to be used
        to create a new node containing the name AARDVARK and add this to
        the correct place at the head of the list
  
     (9 marks)



5.  Given the following binary search tree

                                  20
                                /    \
                               /      \
                              /        \
                             5         30
                            / \        / \
                           2   8      22  32
                              / \    / \
                             7  15  21  26
                                / \ 
                               /   \
                              11   16

   
   Show the result of performing

   a)  An inorder traversal of the tree

   b)  A postorder trversal of the tree

   (NB.  As nodes are visited, the contents are printed out)

   (3 marks) 

6.  Write a C function to perform a preorder trversal of a binary tree

    Use the following assumptions:

         Your function will be recursive;
         Your function will recieve a pointer to a "treenode" as its only
         parameter;
         The contents of the nodes are to be printed as the nodes 
         are visited

   The declarations

   typedef strct tnode
    {
       int                   data;
       struct tnode          *left, *right;
    }  treenode;

    typedef treenode *treenodeptr;

   
   have been included in a header file.


   (4 marks)


7.  Given the declarations

    struct anotherstudent
    {
      char       name[20]
      long       id;
      int        age;

    }

    typedef  sruct anotherstudent  *stdptr;

    stdptr  this;

  a)  Expain what is accomplished by the statement

      this = (studptr) malloc(sizeof(struct anotherstudent));

  b)  Suppose a student named Richard with identification number 925368
      is 23 years old.  Using ONLY the variables declared above, show how
      you would assign values to the tree componets of the record to
      represent such a student.

     ( 6 marks)

8.  Write a function MY_SORT(int a[], int b) which will sort the array a[]
    into descending order.  Array a[] holds n integers at the time the
    function is invoked.
    You may use any sorting alogorithm EXCEPT bubblesort or the inbuilt
    qsort() function.

    (8 marks)

9.  Our inptrepid student programmer has been at work again.  This time,
    she as required to write a program which will copy stdin to stdout,
    except that multiple new lines are to be reduced to a single newline.
    Here is the program that she has written.

    /* copy stdin to stdout, single linespace only */

    #include

    void main(void)
    {
      char  c, lastc = '*';
      while (c = getchar() != EOF)
      {
         if(c = '\n')
           if (lastc != '\n' )
                putchar('\n');
         else
           putchar(c);
        
         lastc = c;
       }
    }

  
   Unfortunately the program is flawed and when run produces as output a 
   large number of blank lines.

   Itentify the logical errors in the program and write the correct 
   versions of those lines below.  If it is necessary to add new lines
   do so.

   (5 marks)

10. Rewrite the following function so that it accomplishes the same 
    result in a less trick manner

    void tricky (int *first, int *second)
    {
       *first  = *first + *second;
       *second = *first - *second;
       *first  = *first - *second;
    }


    ( 3 marks)
      

11.  Write a C function to recursivley compute the greatest common
     divisor of two numbers using the algorithm:


                                gcd(m,n)          if n < m

           gcd(n,m)  =          m                 if n>=m and n mod m = 0

                                gcd(m, n mod m)   otherwise

    ( 6 marks )


12. Show the sets of numbers compared when sorting the following array
    with a SHELLSORT algorithm.

    80  42  12  3  65  87  23  30  13  91  89  98  46  44  22  7

    a)  With gap values of  9 , 5 , 3 , 1

    b)  With gap values of  8, 4 , 2 , 1

    Which of these two sets of gap values is likely to produce faster
    sort times?  Why?

    (5 marks)