SUB: DATA STRUCTURES AND APPLICATIONS (18CS32)
QUESTION BANK (PREVIOUS YEARS QUESTIONS)
MODULE 1
(Introduction, Array operations and Strings)
QUESTIONS YEARS
1 What is Data Structures? Classify and Explain them briefly. Jan18
Also explain the basic operations that can be performed on data structures. June19(17s)
List out the applications.
2 What is an Algorithm? Explain the criteria that an algorithm must satisfy. Jan17
3 What are the different types of memory Allocation? Explain the Different Jan18, 19(17s),
functions that supports Dynamic Memory Allocation June17,18,19(17s)
4 Differentiate between static and dynamic memory allocations. (TIE)
5 Explain with an example: Insertion and Deletion in an array. June18
6 Define Structures .Illustrate different ways of declaring structures with Example Jan18
7 List and explain 3 types of structures used to store the strings (10m) Jan19(17s)
8 What is an array and how the array pointers are declared. (TIE)
9 Define Pointers. Give advantages and disadvantages of pointers. Jan18
How do you declare and initialize the pointer. How do you access the value June19
pointed to by a pointer.
10 What is pointer to pointer? Give the following declaration. June19
int a=8; int b=9; int *p=&a; int *q=&b;
What is the value of each of the following expression?
++a, ++(*p), --(*q), --b
11 Write a function to swap the contents of 2 variables using pointer. (TIE)
12 Write a C Program to define details of the Employee with the fields like June17
EName, EmpID, DOJ(Date, Month, Year) and Salary(Basic, DA, HRA) Read Jan19
data for 10 employees and display them. Find the Employee who is getting
Highest Salary.
13 Suppose each student in a class of 25 students is given 4 tests, assume that June18
the students are numbered from 1 to 25, and the test scores are assigned in
the 25X4 matrix called SCORE. Suppose Base (SCORE) =200 w=4 and the
programming language uses row-major order to store this 2D array, then find
the address of 3rd test of 12th student i.e. SCORE (12,3).
14 Write appropriate structure definition and variable declarations to store Juny19
following information about 50 students:
Name, USN, GENDER, DOB and Marks in 3 subjects S1, S2, S3. Date of
birth should be a structure containing fields day, month and year.
15 What is self-referential structure? Bring out the difference between Structures June18
and unions.
16 Write a c program to implement (i)Linear Search (ii)Binary Search Jan17
(iii)Selection Sort (iv)Bubble Sort. (Also algorithms for these – Jan19(17s)) Jan19(17s)
17 Write a C Program to Create 1D and 2D Arrays using dynamic memory June19
Allocations. & also freeing the memory. (OR) What is dynamically allocated
arrays? Explain with suitable examples.
18 Explain about the representation of 2 D arrays in memory Jan19(17s)
19 Write a C Program to implement (i)Pattern matching (ii)strrev() (iii)strcpy() Jan18
(iv)strcat() (v)strcmp() June17,19(17s)
20 What is a string? (How is a string declared and initialized). Explain the July19
following string functions with example: STRTOK, STRCAT & SUBSTR (4M)
DATA STRUCTURES & APPLICATIONS (18CS32) | QUESTION BANK
21 Consider the pattern ababab, construct the table and the corresponding Jan19
labelled directed graph used in the second pattern matching algorithm.
22 What do you mean by pattern matching? Let P and T are 2 strings with Jan19 (17s)
lengths R and S respectively & stored as arrays with one character per
element. Write a pattern matching algorithm that finds index P in T. Also
discuss about this algorithm. (10m)
23 Write the Knuth Morris Pratt (KMP) pattern matching algorithm and apply the Jan17
same to search the pattern ‘abcdabcy’ in the text ‘abcxabcdabxabcdabcdabcy’. June19(17s)
24 What is Polynomial? What is degree of polynomial? Jan17
Write a C Program to add 2 polynomials A and B, store the result in Jan19
polynomials C. June17
June19(17s)
→Consider 2 polynomials, A(x) = 4x15+3x4+5 & B(x) = x4+10x2+1. Represent
polynomials using array of structures (show diagrammatically show these 2 June18
polynomials can be stored in 1D array) and also give its C representation Jan19
→Consider 2 polynomials, A(x)= 2x1000+1 and B(x)=x4+10x3+3x2+1 with a
diagram to show how these polynomials are stored in 1D Array.
25 What is Sparse Matrix? Show with a suitable example sparse matrix June17
representation storing as triples. Give a sample transpose function to Jan17
transpose sparse matrix. Jan19(17s)
OR
Write fast transpose algorithm to transpose the given sparse matrix. Express
the given sparse matrix as triplets and find its transpose.
10 0 0 25 0 15 0 0 22 0 −5
0 23 0 0 45 0 10 2 0 0 0
0 0 0 0 32 0 0 0 −4 0 0
A= A=
42 0 0 31 0 0 0 0 0 0 0
0 0 0 0 0 91 0 0 0 0 0
[0 0 30 0 0 ] [ 0 0 28 0 0 0 ]
Write an example to illustrate that “product of 2 sparse matrix may not be June18
sparse”. Also write C function for matrix multiplication of 2 sparse matrix.
DATA STRUCTURES & APPLICATIONS (18CS32) | QUESTION BANK
MODULE 2
(Stacks, Recursions and Queues)
Questions Year
1 Define Stacks. Write the stack implementations for push and pop functions using June19(17s)
arrays (using dynamic arrays - Jan 19) with StackFull & StackEmpty conditions. June18 June17
(OR) List operations of stack. Write C implementation of these ops. Jan18 Jan19
2 Write an algorithm to implement a stack using dynamic array whose initial Jan17
capacity is 1 and array doubling is used to increase the stack’s capacity (i.e.
dynamically reallocate twice the memory) whenever an element is added to full
stack. Implement the operations – push, pop and display.
3 Write a C Program to Convert infix expressions to postfix expressions. Convert June19(17s)
the following infix expressions to postfix expressions :
1. (a+(b-c)*(d-e)%f)
2. (a+b) * d – e / (f + a * d) +c (Write the post fix form using stack)
3. (( a / ( b – c + d)) * (e – f ) * g) (Write the post fix form using stack)
4. a+(b+c)+(b/d)*a+z*u (MANY TIMES)
5. A-B/C(C*D$E)
4 Write a C Program to evaluate the following Postfix Expressions. Also evaluate June19(17s)
(trace) the following Postfix Expressions. (Also Algorithm)
• a / b – c + d * e – a * c, Where a=6,b=3,c=1,d=2,e=4.
• abc + * de / - Where a=5,b=6,c=2,d=12,e=4. Jan19
• ab/c – de*+ac* Where a=6,b=3,c=1,d=2,e=4
• 123 + * 321 - + *
• 623+-382/+*2$3+ (MANY TIMES)
5 Write the postfix form of the expression: Jan19(17s)
A ÷ (B*C – D/E ↑ F)* G) * H. • ((6+93-2)*4↑5+7) • A $ B $ C *D Jan18
6 Write an algorithm for evaluating a valid postfix expression. Trace the same on June19
562+*841-
7 Explain in detail multiple stacks, with relevant functions in C June19(17s)
8 Define Recursion. What are the properties of recursion? Write recursive Repeated many
procedure for (1) factorial of a number and (2) Tower of Hanoi times.
9 Define queues. List the different types of queues. Write the implementation of June19,
ordinary queues using arrays. (* C function) Jan19(17s)
10 List the disadvantages of linear queue and explain how it is solved in circular Jan17
queue. Give the algorithm to implement a circular queue with suitable example.
11 Explain the implementation of circular queues using arrays. (dynamically allocated A) June17
12 Write C function for insert() and delete() operations on a circular queue. June19(17s)
List the advantages of circular queue over linear queue.
13 Write QINSERT and QDELETE procedures for queues using arrays. (also C Jan19(17s)
function) June19 Jan18
14 Write a short note on DE queues and priority queue. Jan19(17s) ,19
15 What is input restricted double ended queue? Implement the same with June17
supporting functions.
16 With a neat diagram, explain ONE-WAY list representation of priority queue. June18
17 Write a note on Ackermann function. Write its algorithm. Evaluate A (1,2) using Jan19(17s)
Ackermann function. June18 Jan17
18 Describe how you could model a MAZE, where 0 represents open paths and 1 June18
represents barriers. What moves are permitted in the matrix model? Provide an
example MAZE together with its allowable moves and table of moves.
DATA STRUCTURES & APPLICATIONS (18CS32) | QUESTION BANK
MODULE 3
(Linked Lists)
Questions Years
1 Define Linked Lists. Explain in detail, the primitive operations performed on Singly June19(17s)
Linked Lists. List the different types of linked lists. June19
2 Write the following algorithm for SLL. • Inserting ITEM as the 1st node in the list. Jan19(17s)
• Deleting the node with the given ITEM of information.
3 Write the function to perform the following on SLL: (usually using integer data type) Jan19(17s)
Creating an ordered SLL. (or create a list) • Count number of elements (Length) Jan19
Jan18
Search an element (Linear & Binary – Integer) • Display all the elements in SLL June19
Deleting a node at rear end of SLL. • Insert a node at front end of SLL. June18
Inverting a singly linked list. (Reversing) • Finding the length of a circular list.
Concatenating the singly linked list. (Ex: LIST_1 and LIST_2 for LIST_3)
Assume the list contains 3 nodes with data 10, 20, 30. Insert a node with data 40 at the Jan17
end of the list. June17
Insert a node with data 50 between the nodes having data values 10 and 20.
Delete the node whose data is 20.
4 How can an ordinary queue be represented using a singly linked list? Write C function June19
for linked implementation of ordinary queue insertion & deletion.
5 Explain the following with suitable example: Circular LL and Doubly LL June19
6 What is Doubly linked list? Write C functions for the following operations on Doubly June19(17s)
Linked List (DLL). June 19
Jan19
Concatenation of 2 DLL. • Search the DLL for the given key element. Jan18
Insert a node at beginning • Deleting a node at rear end
delete_front • Inserting a node at specified position.
(OR)
Illustrate with example the following operations on DLL:
June17
1. Inserting a node at the beginning
2. Inserting at the intermediate position
3. Deletion of a node with given value
4. Search a key element
7 What are the advantages of DLL over singly linked list? Explain with an example. Jan19 Jan17
8 List out the differences between SLL and DLL. June18,17
9 Write C program to implement linked stacks. June19(17s)
10 Write a note on header linked list. Explain the widely used header lists with diagrams. June18
11 Write an algorithm to add 2 polynomials using circular singly linked list (SLL). And also June19(17s)
P(x, y ,z) = 6x2y2z-4yz5+3x2yz-2xyz3 Jan18
12 Write node structure for linked representation of polynomial. Write function to add two Jan19(17s),
polynomials represented using linked list. (*with header nodes) 19,17,June17
13 Define sparse matrix. For the given sparse matrix give the linked list representation. June19(17s)
(4m) Jan19(17s)
2 0 0 0 0 10 0 0 Jan17
0 0 4 0 0 Jan18
4 0 0 3 3 0 0 5
6 5 0 0 0
A=[ ] A= 0 0 0 0 A= 8 0 2 0
0 3 0 1 0
8 0 0 1 0 0 0 0
0 0 0 0 2 [0 0 6 0] [0 0 8 0]
DATA STRUCTURES & APPLICATIONS (18CS32) | QUESTION BANK
