SRI KRISHNA INSTITUTE OF TECHNOLOGY
(Accredited by NAAC, Approved by A.I.C.T.E. New Delhi, Recognised by Govt. of Karnataka & Affiliated to V.T U., Belagavi)
#29, Chimney Hills, Hesaraghatta Main Road, Chikkabanavara Post, Bengaluru- 560090
Dept. of Information Science & Engineering
Data Structures and Application (BCS304)
Question Bank
Module 1- Introduction to Data Structures
1. What is Data Structures? What are the various types of data structure? Explain
2. Define data structures. List and explain the different operations that can be carried on arrays
3. What is Structure? How it is different from array? Explain different types of structure
declaration with examples and give difference between Union and Structure.
4. Write a function to sort integers using bubble sort & Selection Sort algorithm.
5. Explain the representation of linear arrays in memory. Also consider the linear arrays
AAA(5:50) and BBB(-5:10)
a. Find the number of elements in each array.
b. Suppose Base(AAA)=300, Base(BBB)= 500 and 4 words per memory cell for AAA
and 2 words per memory cell for BBB, find the address of AAA[15], AAA[55],
BBB[8] and BBB[0].
6. What is a structure? How it is different from array? Explain different types of structure
declarations with example.
7. Describe unions used in C. How is it different from structures?
8. Define a structure for the employee with the following fields Emp_ID(integer),
Emp_Name(string), Emp_Basic(float), Emp_Dept(string) & Emp_Age(integer). Write the
following to process employee data.
a. Function to read an employee record.
b. Function to print an employee record
9. Develop a structure to represent planets in a solar system. Each planet has fields for planet
name, its distance from the sun in miles and the number of moons it has. Write a program to
read the data for each planet and store. Also print the name of the planet that has the highest
number of moons.
10. Write approximate structure definition and variable declarations to store the following
information about 50 students:
Name, USN, Gender and Marks in three subjects m1,m2 and m3. Find average of the best of
two subject’s marks.
11. Define pointers. How to declare and initialize pointers, explain with example
12. Write a C function to swap two numbers using pointers.
13. Define pointers. List the advantages of pointers over arrays.
14. What is a pointer? What is the difference between pass by value and pass by reference.
15. What is the difference between int *a , int a[5] and int *[5]?
16. Explain how address calculation is done in row major ordering for a 2D array, also
generalizing for n-dimensions.
Ragini Krishna, Dept. ISE, SKIT. Page 1
SRI KRISHNA INSTITUTE OF TECHNOLOGY
(Accredited by NAAC, Approved by A.I.C.T.E. New Delhi, Recognised by Govt. of Karnataka & Affiliated to V.T U., Belagavi)
#29, Chimney Hills, Hesaraghatta Main Road, Chikkabanavara Post, Bengaluru- 560090
Dept. of Information Science & Engineering
17. Find out the error in the following code and justify.
#include <stdio.h>
void main()
{
struct XX
{
int X;
struct YY
{
char s;
struct XX * p;
};
struct YY *q;
};
}
18. Obtain the count for the C function to add two matrices of MxN size using the counting
method and tabular method.
void add_matrix( int a[][max_size], int b[][max_size], int c[][max_size], int m, int n)
{ int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{ c[i][j] = a[i][j] + a[i][j];
}
}
}
19. Explain how address calculation is done in row major ordering for a 2D array, also
generalizing for n-dimensions.
20. What are the drawbacks of static memory? Explain Dynamic Memory Allocation functions
in details with example
21. Explain how memory can be dynamically allocated using malloc() function.
22. Explain dynamic memory allocation functions in detail.
23. Define dynamic memory allocation. List and write with explanation the syntax of dynamic
memory allocating functions.
24. What is the purpose of using free()? With an example, explain the problem that occurs when
free() is not used?
25. Define strings. List and explain any 5 operations with example
26. Write a program to search for key element in an array using binary search.
Ragini Krishna, Dept. ISE, SKIT. Page 2
SRI KRISHNA INSTITUTE OF TECHNOLOGY
(Accredited by NAAC, Approved by A.I.C.T.E. New Delhi, Recognised by Govt. of Karnataka & Affiliated to V.T U., Belagavi)
#29, Chimney Hills, Hesaraghatta Main Road, Chikkabanavara Post, Bengaluru- 560090
Dept. of Information Science & Engineering
27. Write a program to sort integers in increasing order using selection sort algorithm.
28. Write a program to search for an element in the sparse matrix.
29. Write a program in C to read a sparse matrix of integer values and search this matrix for an
element specified by the user.
30. Give ADT sparse matrix and show with suitable example sparse matrix representation
storing triple. Give simple transpose function to transpose function to transpose sparse
matrix and give its complexity.
31. Write the Fast Transpose algorithm to transpose the given Sparse Matrix. Express the given
Sparse Matrices as triplets and find its transpose.
32. With the help of an example. Explain sparse matrix. How the sparse matrix is represented in
memory. Design the algorithm to transpose a given matrix represented as triplets in a 1D
array.
33. Write a C program to read and display sparse matrices and perform the following operations
on it:
• Transpose of a sparse matrix
• Fast Transpose of a matrix
34. Consider 2 polynomials, A(x) = 4x15+3x4+ 5 & B(x) = x4+10x2+1. Show diagrammatically
how these two polynomials can be stored in a 1D array. Also give its C representation.
35. Consider 2 polynomials, A(x) = 2x1000+1 & B(x) = x4+10x3+3x2+1. Show diagrammatically
how these two polynomials can be stored in a 1D array. Also give its C representation.
36. What is the degree of the polynomial? Consider the two polynomials A(x) = x100+1 and
B(x) = 10x3 + 3x2 + 1. Show diagrammatically how these two polynomials can be
represented in a array.
37. Design an algorithm to add two polynomials using ADT polynomial.
38. What is a string? Explain the different string handling functions
39. Write a program that would sort a list of names in alphabetical order
40. Write the Knuth Morris Pratt pattern matching algorithm and apply the same to search the
pattern ‘abcdabcy’ in the text: ‘abcxabcdabxabcdabcdabcy’
41. Write a C program to: i) Comparing strings ii) Concatenate two strings iii) Length of the
string without using built-in functions
Ragini Krishna, Dept. ISE, SKIT. Page 3
SRI KRISHNA INSTITUTE OF TECHNOLOGY
(Accredited by NAAC, Approved by A.I.C.T.E. New Delhi, Recognised by Govt. of Karnataka & Affiliated to V.T U., Belagavi)
#29, Chimney Hills, Hesaraghatta Main Road, Chikkabanavara Post, Bengaluru- 560090
Dept. of Information Science & Engineering
42. Consider the pattern P=ababab. Construct the table and the corresponding labeled directed
graph used in the fist or the second pattern matching algorithm. Trace it for the input text
T=abaabababba
Stacks
1. Define stack. Give the implementation of push, pop and display functions in detail.
2. What is stack? Write a program to implement push, pop and display operations for stacks
using arrays and show them using diagrammatic representations.
3. Define stack and give the ADT of stack. Write and explain C functions for push() and pop()
operations of stack.
4. Convert the following infix expression to post expression:
i) ((A+(B-C)*D^E+F) ii) X$Y$Z-M+N+P/Q iii) A$B*C-D+E|F|(G+H) iv) A-B|(C*D$E)
5. Write a program to evaluate the postfix expression.
6. Convert the infix expression, ((a/(b-c+d))*(e-a)*c) to postfix expression. Write a function to
evaluate that postfix expression and trace for the given data a=6, b=3, c=1 d=2, e=4.
7. Write a recursive program to find out the GCD of two numbers.
8. Write an algorithm to implement a stack using dynamic array whose initial capacity is 1 and
array doubling is used to increase the stack’s capacity( that is dynamically reallocate twice
the memory) whenever an element is added to a full stack. Implement the operations – push,
pop, display.
9. Write an algorithm to convert a parenthesized infix expression to postfix. Apply the
algorithm and show the contents of stack during conversion for the expression:
(A+B*C) * ((D+E-F)/J).
10. Define recursion. Write a C-recursive function for
i) Adding n-odd natural numbers
ii) Adding n-even natural numbers
iii) Factorial of a number
iv) Tower of Hanoi
11. What is recursion ? Write a recursive function for computing nth term of Fibonacci
sequence. Hence give the stack contents for n=3.
12. Define Tower of Hanoi Problem. Write its recursive function and also draw its recursive tree
for n=3.
13. Write an algorithm to evaluate a postfix expression and apply the same for the given postfix
expression.
a. ABC –D*+E$F+ and assume A=6, B=3, C=2, D=5, E=1 and F=7.
b. 651-4*23$/+
Ragini Krishna, Dept. ISE, SKIT. Page 4