NAME OF PROGRAMME: MCA
SEMESTER / YEAR: 2/1
SUBJECT NAME (SUBJECT CODE): DATA STRUCTURE ANALYSIS OF ALGORITHM
SECTION-A (Very Short Answer Type Questions)
(Blooms levels L1: Remember, L2: Understand, L3: Apply, L4: Analyse, L5: Evaluate, L6: Create)
UNIT-I
[Link]. Question COURSE Blooms
OUTCOMES Level
a) What is an algorithm? CO1 L1
b) Write down difference between Data Type and Data CO1 L2
Structure.
c) Differentiate Linear and Non-Linear Data Structure. CO1 L2
d) List operations on Data structure. CO1 L1
e) Explain Complexity. CO1 L4
f) Define Big ‘O notation. CO1 L3
g) Define Time space Tradeoff. CO1 L3
h) Declare and Initialize Linear array. CO1 L2
i) Write 4*4 sparse matrix. CO1 L3
j) Write an Asymptotic Notations. CO1 L2
UNIT-II
[Link]. Question COURSE Blooms
OUTCOMES Level
a) Define Link List. CO2 L1
b) Which type of Data structure is link list? CO2 L2
c) What do you understand by Static Binding? CO2 L2
d) What do you understand by Dynamic Binding? CO2 L2
e) Define Two way list. CO2 L2
f) What is Header link list? CO2 L1
g) Analyze the Insertion in Link List. CO2 L3
h) Analyze the deletion in link list. CO2 L3
i) Evaluate the node of Singly link list. CO2 L3
j) Create the Node of Doubly link list. CO2 L3
UNIT-III
[Link]. Question COURSE Blooms
OUTCOMES Level
a) Write two operations of stack as an ADT. CO3 L2
b) Define queue. CO3 L1
c) Write down condition of stack when it is Full? CO3 L3
d) What are the operations of a queue? CO3 L1
e) What do you mean by Peek(). CO3 L2
f) Write down condition of stack when it is Empty? CO3 L3
g) What are the methods to implement queue in C? CO3 L3
h) What is real time examples of uses of stack in Computer CO3 L2
Science?
i) What are enqueue and dequeue operations? CO3 L2
j) Write a routine for IsEmpty condition of queue. CO3 L3
UNIT-IV
[Link]. Question COURSE Blooms
OUTCOMES Level
a) Define tree in data structure? CO4 L1
b) What is an ordered tree? CO4 L2
c) What is meant by traversing of a tree? CO4 L2
d) What are the applications of binary tree? CO4 L1
e) Explain the node of a B-Tree. CO4 L2
f) How to search a key in a B-Tree? CO4 L2
g) What is the various representation of a binary tree? CO4 L2
h) What is the length of the path in a tree? CO4 L3
i) How to calculate the height of B-Tree? CO4 L3
j) How to find the order of B-Tree? CO4 L3
UNIT-V
[Link]. Question COURSE Blooms
OUTCOMES Level
a) Define Sorting. CO5 L1
b) Define Hashing. CO5 L1
c) What is full form of AVL, ADT and int? CO5 L2
d) What is the purpose of insertion sort? CO5 L2
e) What do you understand by types of internal sorting? CO5 L2
f) Mention the types of sorting. CO5 L2
g) Explain sorting algorithms complexity. CO5 L3
h) Explain best, worse and average cases briefly. CO5 L3
i) How to evaluate time complexity of linear search? CO5 L3
j) Explain the working of array. CO5 L3
SECTION-B (Short Answer Type Questions)
UNIT-I
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) What do you understand Push and Pop? CO1 L1
b) Write down the characteristics of an Algorithm. CO1 L2
c) What do you understand by Time and Space Complexity? CO1 L2
d) How a stack differ from queue. CO1 L3
e) Apply the Algorithm of creation and Traversal on 2-d array. CO1 L3
f) Apply the algo of Linear search in 1-D array. CO1 L3
g) What is Polynomial Representation? CO1 L3
h) Explain circular list by diagram. CO1 L3
i) WAP for accessing Linear Array. CO1 L2
j) WAP for multiplying 2-d array CO1 L2
UNIT-II
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) How singly Link list differ from doubly link list. CO2 L2
b) Advantage of link list over array. CO2 L1
c) Write down algorithm for list Traversal. CO2 L3
d) Write down Algorithm for list creation. CO2 L2
e) Explain Basic operation on Doubly link list. CO2 L3
f) Explain circular link list with example. CO2 L1
g) Analyze the node insertion at between. CO2 L3
h) Analyze the node deletion at between. CO2 L3
i) Write down an algorithm for link list insertion at first. CO2 L3
j) Write down an algorithm for link list deletion at last. CO2 L3
UNIT-III
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) What is Stack? Define stack as an ADT. CO3 L1
b) What are the types of queue? CO3 L2
c) Write Down Pop operation Algorithm. CO3 L3
d) Analyze the postfix conversion algorithm. CO3 L2
e) Analyze the expression Evaluation algorithm. CO3 L2
f) Write Down Push Operation Algorithm. CO3 L3
g) Write the routine to insert an element onto a queue. CO3 L3
h) Write the routine to delete an element from a queue. CO3 L3
i) What are the applications of queue? Explain evaluation of CO3 L3
Batch processing.
j) How do you test for an empty queue? CO3 L3
UNIT-IV
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) What is meant by binary search tree? CO4 L1
b) Write the advantages of threaded binary tree. CO4 L2
c) What are the steps to convert a general tree into binary tree? CO4 L3
d) What are the different types of traversing of a tree? CO4 L2
e) List out the steps involved in deleting a node from a binary CO4 L2
search tree.
f) Write an algorithm for creating a B-Tree. CO4 L3
g) Write an algorithm for searching in B-Tree. CO4 L3
h) Analyse the binary tree node structure. CO4 L2
i) Draw a B-Tree of order 3. CO4 L3
j) There are 8, 15, 13, 14 nodes were there in 4 different trees. CO4 L3
Which of them could have formed a full binary tree?
UNIT-V
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) What is meant by external and internal sorting? CO5 L1
b) Differentiate linear search and binary search. CO5 L2
c) What is the purpose of quick sort? CO5 L2
d) How the insertion sort is done with the array? CO5 L2
e) What is the need for hashing? CO5 L1
f) Mention some methods for choosing the pivot element in CO5 L2
quick sort?
g) Is the heap sort always better than the quick sort? CO5 L3
h) Sort the following numbers using heap sort: 46, 25, 35, 10, CO5 L3
49, 91, 84, and 32.
i) Write the function in C for insertion sort? CO5 L3
j) Write the function in C for selection sort. CO5 L3
SECTION-C [Descriptive Answer Type Questions / Case Study (for MBA COURSES only)]
UNIT-I
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) Define Data Structure, its Types and their Brief Explanation. CO1 L1
b) What are the measures of an efficiency of an algorithm? CO1 L2
Explain.
c) Explain Linear and multidimensional array with memory CO1 L3
implementation in primary memory including concept of row
and column major.
d) What do you understand by Insertion and deletion in Linear CO1 L3
array, explain their Algorithms.
e) Give a brief overview of Sparse matrix its memory storage, CO1 L2
types and examples.
f) What do you understand by complexity of an algorithm? Write CO1 L3
down Time and Space complexity and Explain time space
trade-off.
g) WAP for Deletion in linear array. CO1 L3
h) WAP for search big element within linear array of 10 CO1 L3
elements.
i) WAP for implementation of Sparse matrix CO1 L3
j) Differentiate array and link list. CO1 L3
UNIT-II
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) What do you understand by dynamic data structure? Explain CO2 L2
link list with its advantage and disadvantage.
b) Write an algorithm for List Creation and Traversal. CO2 L3
c) Explain node deletion algorithms for doubly link list CO2 L3
d) Explain node insertion algorithms for singly link list CO2 L3
e) How do traversal works for forward and backward direction CO2 L3
in doubly link list.
f) Explain Dynamic binding, its examples and a program in c CO2 L1
language that show dynamic binding procedure.
g) Analyze and compare all variants of link list. CO2 L3
h) Analyze and compare memory allocation, garbage collection CO2 L2
and overflow and underflow in Link list.
i) Write Notes on: 1. Doubly Circular 2. Header link List. CO2 L1
j) WAP for creation and Traversal of Singly link list in C CO2 L3
language.
UNIT-III
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) WAP in C language for the Array Implementation of Stack. CO3 L3
b) i) Convert ((A+B)*C) in to postfix ii) Convert (A+B*C/D- CO3 L2
F+A^E)
c) Evaluate the following using Stack: CO3 L3
a) 5 9 8 +4 6 *+7 -* b) 5* ( 6+2)-12/4
d) Write the C function for Push and Pop operations. CO3 L2
e) Represent and Analyze the concept of Stack with Link list CO3 L3
representation.
f) What are the various operations performed on the Queue? CO3 L1
g) Write an algorithm to insert an element in a circular queue. CO3 L3
h) How the queue is implemented by linked list? CO3 L3
i) Write two scenarios in which queue is not full. CO3 L2
j) Write down the function to insert an element into a queue, in CO3 L3
which the queue is implemented as an array.
UNIT-IV
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) Explain the steps of deletion in BST. CO4 L3
b) What is multilevel indexing in terms of tree indexes? CO4 L1
c) What are the two methods of binary tree implementation? CO4 L2
Explain them.
d) Explain Inorder, Preorder and Postorder Traversal operation CO4 L3
on Binary tree with example.
e) Write an algorithm to split a node in a B-Tree. CO4 L3
f) Explain the differences between B-Tree and BST. CO4 L2
g) Create a Binary Search Tree for the following data and do in- CO4 L3
order, Preorder and Post-order traversal of the tree. 50, 60,
25, 40, 30, 70, 35, 10, 55, 65, 5
h) Construct a tree for the given Inorder and postorder CO4 L3
traversals. Inorder : DGBAHEICF Postorder : GDBHIEFCA
i) Give the pre & postfix form of the expression (a + ((b*(c- CO4 L3
e))/f).
j) Construct an expression tree for the expression (a + b * c) CO4 L3
+((d * e + 1) * g). Give the outputs when you apply preorder,
inorder and postorder traversals.
UNIT-V
[Link]. Question COURSE Bloom’s
OUTCOMES Level
a) Explain the Bellman Ford Algorithm? CO5 L1
b) How many passes are required for the elements to be sorted CO5 L3
in insertion sort? Explain in detail.
c) Write a C programming code for Matrix Multiplication. CO5 L3
d) Write a C programming code for merge sort. CO5 L3
e) Explain the situation for collision and overflow area. CO5 L2
f) Explain with example the open and closed hashing CO5 L3
addressing.
g) Explain Kruskal algorithm in detail. CO5 L3
h) Explain Dijikstra Algorithm in detail. CO5 L3
i) Write down the merge sort algorithm and give its worst case, CO5 L3
best case and average case analysis.
j) Write down the insertion sort algorithm and give its worst CO5 L3
case, best case and average case analysis.