Exam - Practise Questions (set 1)

Past Exam Papers

1.  Explain the difference between a stack and a queue.  Use the terms
    LIFO and FIFO in your explanation.  Be sure to include the kinds 
    of operations that can be performed on the data structure and any
    error conditions that could result from such operations.

    (4 marks)

2.  A and B are two sorting algorithms.  The complexity of A is O(N^2)
    and the complexity of B is O(N).  Generally which of them will be
    faster?  Based on the complexity information, can you tell which
    is the better algorithm?  Why?

    (3 marks)

3.  a)  An integer stack is defined as follows

        #include 
        #include 

        #define M 10

        typedef struct 
            {
               int        data;
            } Element;

        typedef struct
            {
               Element    data_stack[M];
               int        top;
            } Stack;

       /*=============================================================
          Function prototypes. You should assume that these 
          have been declared elsewhere for this problem.
        ==============================================================*/

      void new_stack(Stack *s);  // creates an empty stack with s->top = -1
      void push(Stack *s, Element *e)  // push an element onto the stack
      Element pop(Stack *s)  // pop an element from the top of the stack
      int isfull(Stack *s) // return 1 if the stack is full, 0 otherwise
      int isempty(Stack *s) // return 1 if the stack is empty, 0 otherwise


   Given the declarations above, predict the output of the following
   pieces of code.

   void main(void)
   {
      Stack     st;
      Element   elem;
      int       i;

      new_stack(&st);
  
      for(i = 0 ; i < M ; i++)
       { 
         elem.data = 2*i + 1;
         push(&st, &elem);
       }

      while( !isempty(&st) )
       {
         elem = pop(&st);
         printf("%d", elem.data);
       }
    }

    Write your solution to this problem.

    b)  Impliment the function int sum(Stack *s) which returns the sum
        of the values of the stack.

    (8 marks)

4.  Write a recursive function int sum_sq(int n) which will calculate and
    return the value of 1*1 + 2*2 + 3*3 +.....+ n*n.  You may assume that 
    n will be a positive integer.

    (4 marks)

5.  When searching an array, what preconditions must be ineffect if 
    we are going to perform a binary search?

    (1 mark)

6.  The following items are to be placed in a binary search tree:

    27, 8, 35, 42, 5, 19, 40, 9, 12, 16, 27, 2

    a)  Construct a binary search tree (in diagram form) for the above 
        items in the order given

    b)  Clearly mark on your diagram
        
        i)  a leaf node
       ii)  a root

    c)  How many comparisons whould you require to locate the number 40
        in your search tree?

    d)  Show the result of performing:
 
        i) an in-order trversal of the tree.
       ii) a post order trversal of the tree.

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

    (9 marks)

7.  Given the declarations

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

    typedef struct anotherstudent *studptr;

    studptr this;

    Explain what is accomplished by the statement

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

8.  Given an array containing the numbers
  
    7, 8, 1, 4, 2, 5, 9 

    a)  Show the state of the array after each pass of sorting by 
        simple insertion

    b)  Show the array and sub-arrays generated by each operation
        performed by the quicksort.

    (8 marks)

9.  A link list is declared as follows

#include
#include
#include




typedef int Data_t;

typedef struct node
	{
		Data_t 			data;
		struct node    *next;

	} Node;

typedef Node *Node_ptr;



void p_list (Node_ptr h);
Node_ptr  new_node(void);
Node_ptr hinsert(Node_ptr h, Node_ptr n);



void main(void)
{
	Node_ptr 	head , temp;
	int         i;

	head = NULL;
	printf("%x\n\n",head);

	for(i = 5 ; i >= 1 ; i--)
	{

		temp = new_node();
		printf("%x\n",temp); getch();
		temp -> data = i * i;
		head = hinsert(head, temp);
	
	}

	p_list(head);
}

void p_list (Node_ptr h)
{
	Node_ptr		temp = h;
	printf("The linked list contains ");
	while(temp != NULL)
	{
		printf("%d - ", temp -> data);
		temp = temp -> next;
	}

	printf("\n");

}


Node_ptr  new_node(void)
{
	Node_ptr		n;
	n =  (Node_ptr) malloc(sizeof (Node) );
	n -> next = NULL;
	return n;
}


Node_ptr hinsert(Node_ptr h, Node_ptr n)
{
	n -> next = h;
	return n;
}


a)  Predict the output from the following code

   
b)  What kind of data structure does this behaviour exemplify?

(5 marks)