Data Structures in C : Previous Year Questions

 Chapter 1: Introduction to Data structures.

1 mark

Q. Which notation is used to denote lower bound?

Q. what are different asymptotic notations.

-Q. Define omega (
) notation.

Q. Define Theta notation.

--Q. What are advantages of ADT?

--Q. What is ADT ? 

--Q. Define Data structure.

Q. What are the component of space complexity?

Q. Name the data structure used in recursion.

Chapter 2: Array as a data structure.

1 mark

Q. State any two limitations of an array.

Q. What is worst and best time complexity of merge sort ?

Q. What is time complexity of Quick Sort ?

Q. What is time complexity of bubble sort?

Q. Define stable sorting.

3 mark

-Q. What are the different ways of representing 2D arrays in memory? Give the formulae for address calculation. Explain with example.

Q. Write a short note on searching methods.

Q. Write an algorithm for binary search. Also state it's complexity.

5 mark

Q. Show all the steps of sorting the following data using quick sort. 26, 35, 24, 31, 11, 27, 19.

Q. Sort the following data using quick sort : 12, 24, 9, 46, 31, 53, 33.

Q. Sort the following elements using Insertion Sort (write passes) : 23, 6, 18, 29, 27, 4, 13.

Q. Sort the following numbers using insertion sort method: 30,40,10,50,25,35,15.

Q. Sort the following data using bubble sort : 13, 12, 14, 15, 19, 9.

Q. Sort the following data using bubble sort: 32, 51, 85, 66, 23, 13, 10, 57.

Chapter 3: Linked List.

 1 mark

Q. Explain node structure of SLL.

Q. what is circular linked list.

Q. Write node structure for a Doubly Circular Linked List.

Q. Define node structure of singly linked list.

Q. “A Linked List can only be traversal sequentially”. State True/ False.

3 mark

-Q. Write a short note on generalized linked list.

5 mark

Q. Write a ‘C’ function to insert and delete an element at particular position in SLL

Q. Write a ‘C’ function to display even element (data) in a single linked list of integer.

-Q. Write ‘C’ function to reverse a linked list.

Chapter 4: Stack

1mark

Q. State the principle on which stack works.

Q. What are applications of stack?

-Q. List different operation of stack

Q. Consider operations performed on a stack push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop. What is the sequence of popped out values are ?

Q. What are the postfix and prefix forms of the expression

A + B * (C - D)/(P - R)

Q. Define stack.

Q. Define multiple stack.

3 mark

Q. Give the output of the following code. 

int i = 1, x, y

 init stack ( );

 while (i < = 5) 

{

 Push (i * 5); 

i = i + 1; 

} 

x = POP ( ); 

x = POP ( ); 

Push (i * 5); 

y = POP ( ); 

Push (x + y) 

x = POP ( ); 

y = POP ( ); 

Push (x + y); 

while (! stack empty ( )) 

Printf(“%d”, POP ( ));

Q. Give the output of the following sample code :  

initstack (s)

 push (s, 9); 

push (s, 4); 

i = pop (s); 

while (i > 0) 

{ 

 push (s, i*i); i – –; 

} 

while (! stack empty (s)) 

printf(“%d\n”, pop (s));

Q. Give output of the following code:

int i=1,x,y,z;

initstack();

while(i<3)

{

push(i*i);

i=i+1;

}

x=pop();

y=pop();

push(i*i);

2=pop();

push(x+y+z);

push(x*y);

while(!stack empty())

printf("\n %d",pop());

4  mark

Q.Consider given infix expression (u + v * w). Write its postfix expression. Also show steps to evaluate the postfix expression using stack. Given : u = 3, v = 4, w = 2

Q. Convert the following infix expression to postfix expression showing the contents of stack at each step :

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

Q. Evaluate the following expression using stack.

A + B * C - D

Given data : A=4, B=3, C=5, and D=1.

First convert expression to postfix.

5 mark

Q. Write a ‘C’ program to implement stack using singly linked list.

Q. Write a 'C' function to push and pop for stack using singly linked list.

Q. Convert the infix expression A * B $ C + D * E/F into postfix expression. Assume $ for exponentiation and has highest priority. 

Q. Convert the infix expression : A | B $ C + D * E – A * C to postfix notation show the stack contents.

Chapter 5: Queue

1 mark

Q. Define doubly ended queue.

Q. Write a statement to increment rear in a circular queue implemented using array.

Q. Define Double Ended Queue

Q. “A priority queue is implemented using array of stacks”. State True or False.

3 mark

--Q. Define Priority Queue. 

-Q. List the types of priority queue.

5 mark

Q. Write a ‘C’ Function to add and delete element from a linear queue (Dynamic implementation).

--Q. Write a ‘C’ function to ADD and REMOVE elements from circular queue implemented using array.

Q.Write a ‘C’ program to implement circular queue as an array.