Queue Question Set

Queue

Data Structures 15CS33 

1.      What is a linear queue? What are the applications of linear queue? Implement/Write a C program to simulate the 1) insert 2) delete  3)display operations.

(December 2007)

(8 marks)

2.      What is circular queue? What ate the advantages of Circular queue over simple queue.

Write implementation for circular queue using array. Also write following routine of circular queue. 1)      insert 2) delete 3) display

(June 2009)

(December 2010)

(June 2011)

(December 2013)

(December 2015)

(10 marks)

3.      Explain priority queue.

(December 2009)

(6 marks)

4.      Explain the working of simple queue

(June 2010)

(5 marks)

5.      For a given circular queue shown in Fig below write the values of front and rear in the table after each specified operation is performed. Queue full/empty conditions must be considered. 0-7 indicates the array indices.

(December 2011)(4 marks)

6.      Explain how would you implement a circular queue using dynamically allocated arrays.

(June 2013)

Stack Questions set

Stack
Data Structures 15CS33 

1.     Define stack and List and implement basic operations in stack using C (push, pop, isempty, isfull). Implement reversing a string using stack (array implementation) in C.

(December 2007)

(June 2009)

(June 2010)

(December 2010)

(December 2010)

(December 2011)

(December 2012)

(December 2013)

(December 2014)

(December 2015)

(12 marks)

2.      Write a C program to implement multiple stacks using single array

(December 2007)

(12 marks)

3.      Write short notes on Applications of stacks

(December 2007)

(5 marks)

4.      Write an algorithm to evaluate postfix expression. Trace the same algorithm with stack contents for the following expression A B C + * C B A - + *    with A=1, B=2, C=3.

(June 2009)

(December 2009)

(10 marks)

5.      Convert each of the following expression to its postfix and prefix forms

a)      ( A + B ) * C – D $ E * F

b)     A - B / C * D $ E

c)      ( A + B ) * ( C + D – E ) * F

d)     ( ( ( A + ( B - C ) * D ) ^ E ) + F )

e)      ( a + b ) * d + e / ( f + a * d ) + c

f)       ( ( a / ( b - c + d ) ) * ( e - a ) * c )

g)      a / b – c + d * e – a * c

(June 2009)

(December 2012)

(December 2013)

(12 marks)

6.      What is stack? Indicate how stack is represented in C.

(December 2009)

(5 marks)

7.      Show using the tabular column how the expression (a+b)*c is converted to a postfix expression according to the infix to postfix coversion algorithm

(June 2010)

(5 marks)

8.  Write the algorithm to evaluate a valid postfix expression and hence evaluate the postfix expression.

      6 2 3 + - 3 8 2 / + *

  

      1 2 3 + * 3 2 1 - +  *

  

       A B + C D E - * /                   for A=5 B=6 C=4 D=3 E=7

  

       6 2 3 + 3 8 2 / + * 2 $ 3 +

All the operands are single digit positive integers and operators are binary in nature.

(June 2010)

(December 2010)

(December 2011)

(June 2013)

(June 2015)

(December 2015)

(10 marks)

9.      Write a algorithm and function to convert a valid infix expression to postfix expression. Demonstrate the same function with example.(using stack)

a)      ( a * b ) + c / d

b)     ( ( ( a / b ) – c ) + ( d * e ) ) - (a * c)

c)      a * ( b + c ) * d

d)     A $ B * C – D + E / F / ( G + H )

e)      A – B / ( C * D $ E )

(June 2011)

(June 2012)

(June 2014)

(December 2015)

(12 marks)

10.  Write a C program to implement a two primitive operations on stack using dynamic memory allocation.

(June 2012)

(8 marks)

11.  What is system stack? How the control is transferred to or from the function with the help of activation records.

(December 2012)

(6 marks)

12.  Convert the infix expression to postfix expression and evaluate the same.

a / b – c + d * e – a * c   for a=6 b=3 c=1 d=2 e=4

 (June 2013)

(6 marks)

13.  How multiple stacks implemented using one dimensional array? Explain with suitable example.

(June 2014)

(4 marks)

Arrays Questions set

Array

Data Structures 15CS33

1.      For a given sparse matrix and its transpose, give the triplet represntation using one dimensional array, a is the given sparse matrix, b will be its transpose.

             

(December 2011)

(Dec 2013)

(December 2015)

(June 2015)

(8 marks)

2.      Consider two polynomials A(x) = 2x¹⁰⁰ +  1 and B(x) = x⁴ + 10x³ + 3x² + 1, show diagrammatically , how these two polynomials can be stored in single 1D array. Also give its C representation.

(December 2011)

(June 2015)

(12 marks)

3.      Give ADT Sparse matrix and show with a suitable example sparse matrix representation storing as triples. Give search function to search for a key in triples and Give simple transpose function to transpose sparse matrix.

(June 2013)

(8 marks)

4.      How would you represent two sparse polynomials using array of structures and also write a function to add that polynomial and store the result in the same array.

(June 2013)

(December 2015)

(6 marks)

5.      What is polynomial? What is the degree of the polynomial? Write a function to add two polynomails.

(December 2013 )

(June 2015)

(8 marks)

6.      Explain with example, dynamic memory allocation for 2 D arrays.

(June 2014)

(4 marks)

7.      Write the fast transpose algorithm for sparse matrix. Why the name sparse matrix?

(June 2014)

(8 marks)

8.      Write a note on dynamically allocated arrays using example.

(December 2015)

(6 marks)

Strings Questions set

Strings

Data Structures 15CS33 

1.      Implement i) Copying one string to another ii) Reversing the given string. Without using string library functions in 'C'.        

(December 2007)

(12 marks)

2.      Write a function that accepts a string and returns 1 is the string is palindrome else 0 if string is not a palindrome without using any built in functions.

(June 2009)

(6 marks)

3.      Explain with syntax following string handling functions.

       a)      strncpy b) strcat c)strcmp

(December 2009)

(6 marks)

4.      What is string? How string is declared and initialized?

(June 2010)

(05 marks)

Pointers Questions Set

Pointers

Data Structures 15CS33

1.      Given the following declarations:

            int x ;

            double d;

            int *p;

            double *q;

            Which of the following expressions are not allowed?

i)                    p = &x;

ii)                  p = &d;

iii)                q = &x;

iv)                q = &d

v)                  p = x;

            (December 2007)

            (5 marks)

2.      Show what would be printed from the following block:

            #include<stdio.h>

            void fun (int (*p)[3])

            {

                        printf ("\n%d %d %d", (*p)[0], (*p)[1], *p[2]);

                        return;

            }

            void main()

            {

                        /* local definitions */

                        int x [2][3] =  { { 4,5, 2}, { 7,6, 9}  };

                        /* statements */

                        fun (x);

                        fun (x+1);

                        return 0;

            }

            (December 2007)

            (6 marks)

            Output:

            4          5          2686792

7              6          2130567168

3.      What is pointer variable? Can we have multiple pointer to variable?

(June 2009)

(December 2009)

(June 2010)

(6 marks)

   

4.      Show the output of the following block:

            main()

            {

                        int num[5] = {3,4,6,2,1};

                        int *p = num;

                        int *q = num+2;

                        int *r = &num[1];

                        printf("\n%d %d", num[2], *(num+2));

                        printf("\n%d %d", *p, *(p+1));

                        printf("\n%d %d", *q, *(q+1));

                        printf("\n%d %d", *r, *(r+1));

            }

            (June 2009)

            (December 2010)

            (6 marks)

            Output:

            6          6

            3          4

            6          2

            4          6

5.      What is pointer to pointer?Write a C program to find the smallest element in an array (using pointer and function)

(December 2009)

(7 marks)

6.      Write the output of the following

#include<stdio.h>

main()

{

                  int a = 5;

                  int b = 7;

                  int *p = &a;

                  int *q = &b;

                  printf("\n%d", ++a);

                  printf("\n%d", ++(*p));

                  printf("\n%d", --(*q));

                  printf("\n%d", --b);

}

(December 2009)

(4 marks)

Output:

6

7

6

5

7.      Write a C program to read 10 integers and store them in an array using pointers. Print their sum and average.

(June 2010)

(5 marks)

8.      What is pointer? What are the uses of pointers?  How do you declare and initialize the pointers? How do you access the value pointed by the pointers?

(June 2010)

(December 2010)

(June 2012)

(December 2012)

(June 2013)

(June 2014)

(December 2014)

(5 marks)

9.      Write a C function to swap two numbers using a pointers.

      (June 2012)(5 marks)

Circular Queue Using an Array

Circular Queue Using an Array

#include <stdio.h>

#include<stdlib.h>

#define MAX 3

char cq[MAX];

int front = -1,rear = -1;

void add(char);

void del();

void display();

int main()

{

            int ch;

            char item;

            while(1)

            {

                        printf("\n\n~~Main Menu~~");

                        printf("\n==> 1. Insertion and Overflow Demo");

                        printf("\n==> 2. Deletion and Underflow Demo");

                        printf("\n==> 3. Display");

                        printf("\n==> 4. Exit");

                        printf("\nEnter Your Choice: ");

                        scanf("%d", &ch);

                        switch(ch)

                        {

                                    case 1: printf("\n\nEnter the element to be inserted: ");

                                                scanf("%d", &item);

                                                add(item);

                                                break;

                                    case 2: del();

                                                break;

                                   case 3: display();

                                                break;

                                    case 4: exit(0);

                                    default: printf("\n\nPlease enter a valid choice");

                        }

            }

}

void add(char item)

{

            if(front == (rear+1)%MAX)

                        printf("\n\n~~Circular Queue Overflow~~");

            else

            {

                        if(front == -1)

                                    front = rear = 0;

                        else

                                    rear = (rear+1)%MAX;

                        cq[rear] = item;

            }

}

void del()

{

            char item;

            if(front == -1)

            {

                        printf("\n\n~~Circular Queue Underflow~~");

            }

            else

            {

                        item = cq[front];

                        if(front == rear) //only one element

                                    front = rear = -1;

                        else

                                    front = (front+1)%MAX;

                        printf("\n\nDeleted element from the queue is: %d ", item );

            }

}

void display ()

{

            int i ;

            if(front == -1)

            {

                        printf("\n\nCircular Queue Empty");

                        return;

            }

            else

            {

                        printf("\nCircular Queue contents are:\n");

                        printf("\nFront[%d]-> ", front);

                        for(i=front; i!=rear ; i=(i+1)%MAX)

                        {

                                    printf("  %d", cq[i]);

                        }

                        printf("  %d",cq[i]);

                        printf(" <-[%d]Rear", rear);

    }

}

Output:

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 11

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 22

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 33

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 44

~~Circular Queue Overflow~~

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[0]->   11  22  33 <-[2]Rear

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 2

Deleted element from the queue is: 11

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 2

Deleted element from the queue is: 22

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[2]->   33 <-[2]Rear

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 66

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[2]->   33  66 <-[0]Rear