DATA STRUCTURE Using C Question Bank

CO BL PO
Short Type Mark

1 What do you mean by the efficiency of an algorithm? Discuss time 1 2 1,2

and space complexity?
2 Which asymptotic notion is used to represent for lower bound of a 1 1 1,2
function? Discuss it.
3 What is data structure? Differentiate between linear and non linear 1 2 1,2
data structure.
4 What do you understand by stack and queue? Give real life example 1 2 1,2
from each.
5 Suggest a data structure that can be used to reverse the content of an 1 3 1,2
array? Briefly explainhow your suggestion will help in solving the
problem. How your suggestion will help in solving the problem
6 Write the formulas to calculate the address of an element of a 2D arr 1 3 1,2
ay in row major order. Ifthe address of A[0][0] and A[0][1] are
1000 and 1010 respectively and each element occupies 2bytes
then in which order do you think the array elements are stored and
why you think so?
7 What is sparse matrix. Give an example. What are the disadvantages 1 2 1,2
of representing it in normal 2D array
8 Discuss some areas of application of data structure? 1 2 1,2
9 Define queue. 2 1 1,3
10 Define stack 2 1 1,3
11 Explain overflow and underflow condition in circular queue ( using a 2 2 1,3
rray).
12 Write some areas of application of stack 2 2 1,3
13 Suggest a data structure that can be used to check whether an 2 3 1,3
arithmetic expression has balanced parenthesis or not? Explain
how your suggested data structure can help to solve the problem
14 Write some areas of application of queues 2 2 1,3
15 Given in the digraph G(V,E) , V={v1,v2,v3,v4,v5}, 4 3
E={(v1,v2),(v2,v3),(v1,v5),(v5,v3),(v4,v3),(v4,v1)}.Draw the graph and
check .whether it is cyclic or not.
16 If the elements "A", "B", "C" and "D" inserted into queue and are 2 3 1,3
deleted one at a time, in what, in what order will they be removed?
17 Translate the following postfix to infix: A B * C + 2 3 1,3
18 What is linked list? Name different types of linked list. 2 2 1,3
19 Differentiate between array and linked list. 3 2 1,2,3
20 Write two disadvantages of linked list over array? 3 2 1,2,3
21 Explain Doubly Linked list with a suitable example. 3 2 1,2,3
22 Explain Circular Linked List with a suitable example 3 2 1,2,3
23 What the following C code will do? Assuming that curr holds addres 3 3 1,2,3
s of first node of a singlylinked list , n is an integer “next” is the link
part of the node and “data” is the integer info part of the node.
n=0;
while(curr!=NULL)
{
n=n+curr->data;
curr=curr->next;
 }
printf(“%d”,n);
24 Define a tree recursively. Give an example of a binary tree. 4 2 1,3
25 How many structurally different binary trees are possible with 5 4 3 1,3
nodes.
26 What is graph? Give an example. 4 2 1,3
27 What is AVL tree? Give an example. 4 2 1,3
28 Represent the following general tree as a binary tree: 4 2 1,3

29 Construct an expression tree for the expression : 4 3 1,3

A * B - (C + D) * (P /Q)
30 What is Max-heap? Give an example. 4 2 1,3
31 What is path matrix of a graph? 4 1 1,3
32 Define indegree and outdegree of a node in directed graph with an 4 2 1,3
example.
33 What are the three traversal strategies used in binary tree? Find the i 4 3 1,3
norder traversal of the following binary tree

34 What do you mean by Internal and External Sorting? 5 1 1,2

35 Compare the worst case time complexity of bubble sort, insertion 5 2 1,2

sort, and selection sort

36 What is the disadvantage of selection sort? 5 2 1,2

37 What do you understand by divide-and-conquer strategy? 5 2 1,2

38 For a list L = {8, 99, 3, 4, 6, 10}, find the output list at the end of 5 3 1,2

pass 1 using bubble sorting method.

39 Define Collision in hashing 5 2 1,2

40 What are the collision resolution methods? 5 2 1,2

Short Focussed Type

1 What is algorithm? Discuss its properties 1 2
2 In a two dimensional array A[5][10] Deduce the address of the 1 3 1,2
A[3][5] in row major order and column major order.
The base address of the array is 3000 and the size of element is
2bytes. Assume the lower bound of row and column indices to be 0.
3 Write an algorithm to find the largest and smallest element of an 1 3 1,2
array
4 Write an algorithm to transpose a matrix 1 3 1,2
5 Write an algorithm for binary search. 1 3 1,2
6 Discuss the triplet representation of sparse matrix 1 2 1,2
7 Convert the following Infix expression to Postfix form using a stack. 2 3 1,3
A + B – (C * D E + F / G ) + ( H + I*J ),
Follow usual precedence rule and assume that the expression is legal.
8 Write an algorithm to insert an element into a circular queue implem 2 3 1,3
ented using array.
9 Write algorithms for Push and Pop operation of stack implemented 2 3 1,3
using array
10 Discuss postfix evaluation process using stack and evaluate the 2 3 1,3
following postfix expression by
12 5 2 * 4 − 2 ^ 6 / +
Where ^ is exponent operator
11 Briefly discuss about priority queue and double ended queue 2 2 1,3
12 Can we implement queue using stack(s)?If yes how many minimum 2 2 1,3
no. of stack we need.
13 Write a code snippet for declaring the node of a doubly linked list. 3 3 1,2,3
and create a node dynamically.
14 Difference between calloc() and malloc() in C. 3 2 1,2,3
15 Write an algorithm to reverse a single linked list? 3 3 1,2,3
16 Write an algorithm to find largest data value present in a singly 3 3 1,2,3
linked list.
17 Write the algorithm for searching an element in a singly linked list. 3 3 1,2,3
18 Write the steps of the algorithm to insert a new node after the 3 3 1,2,3
node pointed by P in the following Linked List.

19 Briefly discuss about double ended and priority queue. 3 2 1,2,3

20 Find topological ordering for the following graph: 4 3 1,3

4 3 1,3
21 Construct the binary tree whose preorder and inorder traversal are
given
Preorder : a b d e g h c f n
Inorder : d b g e h a c n f
22 What is adjacency matrix? Find the adjacency matrix for the 4 3 1,3
following graph:

23 Write DFS algorithm for graph traversal. 4 2 1,3

24 Define the following terms with respect to tree: height of a node, d 4 2 1,3
epth of a node, path, leaf node with example from each.
25 Represent the following binary tree in an array 4 3 1,3

26 Write a C function for selection sort.? 5 3 1,2

27 Explain how insertion sort works taking an example and showing 5 3 1,2

the result of each pass.

28 Briefly describe radix sort and Sort the following data using radix/ 5 3 1,2

bucket sort: 42, 74, 11, 65, 94, 36, 87, 70, 81,1
29 Explain the merge sort process taking an example 5 3 1,2

30 Write any two techniques to overcome hash collision 5 3 1,2

31 What are the application of hashing? 5 2 1,2

32 Explain Open addressing method 5 2 1,2

Long Type
1 a) What is data structure? Briefly discuss the classification of data st 1 2 1,2

ructure with examples.

b) What is pseudo code ? Write a pseudo code to delete an element 1 2 1,2

from the array .

2 a) Write a complete C program to implement binary search 1 3 1,2

b) Write an algorithm to insert an element into the array at a given 1 3 1,2

position
3 a) What is sparse matrix? Discuss various types of commonly used 1 2 1,2

sparse matrices
b) Represent the following sparse matrix in triplet format 1 3 1,2
4 Write a menu driven C program to implement the following 2 3 1,3
operation on stack using array
I) PUSH ii. POP iii. DIPLAY to display content of
Stack.
5 Write a menu driven C program to implement the following 2 3 1,3
operations on linear queue
i. INSERT ii. DELETE iii. DISPLAY to display
content of queue
6 a) Write an algorithm to display circular queue 2 3 1,3
b) Write algorithm to PUSH and POP elements from stack 2 3 1,3
implemented using linked List
7 a) Write a C program to create and display a singly linked list. 3 3 1,2,3
b) Write an algorithm to insert a node at the beginning of a doubly 3 3 1,2,3
linked list
8 a) Write an algorithm to insert a node in a singly linked list at the 3 3 1,2,3
desired position.
b) Explain with a suitable diagram to implement queue using linked 3 2 1,2,3
list. Further write the
9 a) Write a C function to delete a node from a desired position of 3 3 1,2,3
singly linked list
b) Write an algorithm / C function to traverse a circular linked list wi 3 1,2,3
th at least one node.
10 A) What is binary search tree (BST) ? For the given sequence 4 3 1,3
of numbers construct a BST :
34 , 23 , 67 , 45 , 12 , 54 , 87 , 43 , 98 , 75 , 84 , 93 , 31
b) From the above constructed BST delete 12,67,93,34 4 3 1,3
sequentially. Show the reusltant BST after each deletion.
11 a) Write BFS algorithm for graph traversals. Perform BFS 4 3 1,3
traversal for the following graph by considering start node as
0.

Write DFS algorithm for graph traversals. Perform DFS 4 3 1,3

traversal for the above graph by considering start node as 0
12 a) What is AVL tree? State its properties. Construct an AVL 4 3 1,3
tree by inserting data as per following order:
MAR. MAY, NOV, AUG, APR, JAN, DEC, JUL, FEB, JUN, OCT, SEP

b) Write C procedures/functions for the three different types of 4 3 1,3

binary tree traversals
13 a) Discuss the Bubble sort technique taking the following array 5 3 1,2

as example ? Explain each pass. 12,34,5,78,4,56,10,23,1

b) Write a C program to implement Bubble sort technique to sort 5 3 1,2

the elements of an integer array in descending order.

14 a) Explain how selection works. Arrange the following elements 5 3 1,2

in ascending order using quicksort showing the result of every

pass.
5, 14, 2, 9, 21, 34, 17, 19, 1, 44
b) Write the program to implement Insertion Sort 5 3 1,2

15 a) What is hashing? Discuss any three hash function with example. 5 2 1,2

b) Discuss the Linear Probing Method. Discuss the disadvantages 5 2 1,2

of Linear Probing Method with an example.