VALLIAMMAI ENGINEERING COLLEGE

SRM Nagar, Kattankulathur – 603 203

DEPARTMENT OF INFORMATION TECHNOLOGY

QUESTION BANK

VI SEMESTER

CS6301-PROGRAMMING DATASTRUCTURE II

Regulation – 2013

Academic Year 2017 – 18

Prepared by

Ms. R.Thenmozhi, Assistant Professor (Sel.G)/IT

Ms. K.Mohanambal, Assistant Professor (O.G)/IT

 VALLIAMMAI ENGINEERING COLLEGE
SRM Nagar, Kattankulathur – 603 203.

DEPARTMENT OF INFORMATION TECHNOLOGY

QUESTION BANK
SUBJECT : Programming and Data Structures II
SEM / YEAR: III Sem/ II Year

UNIT 1 – OBJECT ORIENTED PROGRAMMING FUNDAMENTALS

Be familiar with the C++ concepts of abstraction, encapsulation, constructor, polymorphism, overloading and
Inheritance.
C++ Programming features – Data Abstraction – Encapsulation – class – object – constructors – static members –
constant members – member functions – pointers – references – Role of this pointer – Storage classes – function as
arguments.
PART – A
BT
Q.No. Questions Competence
Level
1 Define Data Abstraction. BTL-1 Remembering
2 What is the use of “this” pointer? BTL-1 Remembering
3 Which is used for achieving data Hiding in C++? BTL-1 Remembering
4 List the various storage classes available in C++. BTL-1 Remembering
What is the significance of static data & static member function in BTL-1 Remembering
5
object oriented programming?
6 Define Encapsulation. BTL-1 Remembering
7 Give the significance of declaring a member of a class static. BTL-2 Understanding
8 Give the characteristics of the constructor function. BTL-2 Understanding
9 Differentiate between realloc () and free (). BTL-2 Understanding
10 Give the features of object oriented C++ programming. BTL-2 Understanding
11 Show the working of copy constructor. BTL-3 Applying
12 What is a default constructor? Illustrate. BTL-3 Applying
13 What are objects? Illustrate with an example. BTL-3 Applying
14 Point out a when a function will be made online? BTL-4 Analysing
What are pointers? Point out the advantages of using pointers in BTL-4 Analysing
15
programming.
16 Analyze and define operator overloading with an example. BTL-4 Analysing
17 Compare the working of structures and classes in C++. BTL-5 Evaluating

18 Summarize the working of destructors with an example. BTL-5 Evaluating

 Develop the member function to find the greater of two numbers BTL-6 Creating
19
using “this” pointer.
Develop a simple C++ program using a class concept. BTL-6 Creating
20

PART – B

(i) List the types of constructors with examples. (6) BTL-1 Remembering
1 (ii) Describe the features of C++ programming Language . (7)
(i) Describe the ways in which member functions of class can be BTL-1 Remembering
2 defined & called using a suitable example. (7)
(ii) Describe with an example the use of static members. (6)
(i) What are the differences between pointer to constant & constant to BTL-1 Remembering
3 pointer? Give an example program & explain it. (7)
(ii) Describe the role of “this” pointer with an suitable program. (6)
Explain the different types of storage classes of C++ using suitable BTL-1 Remembering
4
examples. (13)
Discuss about the need to use the default arguments with an example BTL-2 Understanding
5 program. (13)
(i) Describe about the copy constructor with an example. (7) BTL-2 Understanding
6
(ii) Differentiate between constructor and destructor. (6)
Describe briefly about the following term with an suitable example: BTL-2 Understanding
(i) Objects. (3)
7 (ii) Classes. (3)
(iii) Polymorphism. (3)
(iv) Methods and message passing. (4)
(i) Illustrate and write a C++ program to check how many instances of BTL-3 Applying
a class are created using the static member function. (7)
8 (ii) Illustrate and write a C++ program that prints the factorial of a
given number using a copy constructor and destructor member
function. (6)
(i) How would you declare function to be a constant in C++? What are BTL-3 Applying
the properties of such function? Demonstrate with a program. (7)
(ii) Demonstrate the mechanism for accessing data members and
9 member functions in the following cases. (6)
a. Inside the main program.
b. Inside a member function of the same class
c. Inside a member function of another class

10 Explain about constructors and destructors with example program. (13) BTL-4 Analysing
 (i)What do you mean by static member function? Explain in detail with an BTL-4 Analysing
11 example. (7)
(ii) Point out a detailed note on const member function. (6)
(i) Pointout the advantages of OOP? (3) BTL-4 Analysing
12 (ii)Explain in detail about const,volatile and static functions. (10)

Summarize the various function call mechanisms with suitable BTL-5 Evaluating
13 programming example. (13)

Develop an object oriented program in C++ to prepare the mark sheet BTL-6 Creating
of a university exam with the following items read from the keyboard.
Name of the student, Rollno, Subjectname, Subjectcode,
Internalmarks, and External marks.
14 Design a base class consisting of the data members such as name of the
student, roll number and subject code, internal marks and external
marks. The program should be able to do the following tasks” Build a
table, Display the table, Insert into the table, Delete from the table,
Edit entry and search for a record that is needed to be printed. (13)

PART - C
Define a class time with string containing seconds elapsed till midnight BTL-6 Creating
(12.00AM) as a single data member. Write AddTime function which
1 adds two different Time objects and returns a new Time object. Write a
Display Normal function which converts the time in seconds and
display in a normal fashion HH:MM:SS. (15)
(i) Write a program in C++ that contains a function which takes an BTL-5 Evaluating
integer array as argument and returns the sum of the array elements.(7)
(ii)Construct a class by name ‘Box’ with a constructor method and
volume method. Constructor initializes the length, breath, and height
2
of the box objects. Volume method computes the volume of the box
using the formula length*breath*height. Create three box objects and
compute their volume by declaring a pointer to the box class. (8)

BTL-6 Creating
(i)Write a C++ Program to find the smallest in an array of ‘n’ elements
3 using pointers. (7)
(ii)Write a C++ program to sort a list of strings using pointers. (8)
 Consider an example of declaring the examination result. Design three BTL-5 Evaluating
classes: student, Exam and result. The “student” class has data
members such as that representing roll number, names etc.create the
4 class “Exam” by inheriting the “student” class. The “Exam” class adds
data members representing the marks scored in six subjects. Write an
interactive program to model this relationship. what type of inheritance
this model belongs to? (15)

UNIT 2 – OBJECT ORIENTED PROGRAMMING CONCEPTS

String Handling – Copy Constructor – Polymorphism – compile time and run time polymorphisms – function
overloading – operators overloading – dynamic memory allocation – Nested classes - Inheritance – virtual functions

PART – A

BT
Q.No. Question Competence
Level
1 List any four operators of C++ that cannot be overloaded. Remembering
BTL-1
2 What are pure virtual functions? Give example BTL-1 Remembering

3 Tell how the ‘C’ string differs from a C++ type string? BTL-1 Remembering

4 What is dynamic initialization of objects? BTL-1 Remembering

5 Define copy constructor & its use. BTL-1 Remembering
6 State the uses of virtual functions. BTL-1 Remembering
7 Distinguish the term overloading &overriding. BTL-2 Understanding
Summarize the different operators of C++ that can be overloaded. BTL-2 Understanding
8
Give an example
9 Differentiate virtual function and pure virtual function. BTL-2 Understanding
10 Define multiple inheritance.Give example. BTL-2 Understanding
11 What is Inheritance? Illustrate. BTL-3 Applying
12 Examine how one invoke a constructor function. BTL-3 Applying
13 Illustrate the working of type conversion with an example. BTL-3 Applying
14 Compare multiple and inheritance with example. BTL-4 Analysing
15 Differentiate Operator overloading and function overloading. BTL-4 Analysing

16 Compare Run time polymorphism and Compile time polymorphism. BTL-4 Analysing
17 Summarize the working of inline functions with an example. BTL-5 Evaluating
18 Compare private and protected visibility. BTL-5 Evaluating
19 Develop a simple C++ program using inline function. BTL-6 Creating
 Develop and write the syntax to dynamically allocate memory BTL-6 Creating
20
through constructor.

PART – B

BTL-1 Remembering
(i) Describe how memory is dynamically allocated & recovered in C++?
Illustrate with an example program. (7)
1 (ii) List the rules associated with operator overloading? What are the
operators that cannot be overloaded? Write a program to overload any one of
the binary operator. (6)

(i) Define a class shape with constructor, destructor & pure virtual BTL-1 Remembering
functions GetArea (), GetPrim () &Draw (). Derive class circle &
Rectangle from shape. Derive another class square from rectangle.
2 Implement this hierarchy with essential functions & write a main. (7)
(ii) Define a class area to identify the area of square & rectangle using
constructor & destructor. Use the parameter length (l) & breadth (b) for the
constructor functions. (6)
With suitable C++ program describe how the polymorphism is BTL-1 Remembering
3
achieved at compile time & run time. (13)
Describe about the following concepts with their syntax. BTL-1 Remembering
(i) Copy constructor. (3)
4 (ii) Virtual functions. (3)
(iii) Pure virtual functions. (3)
(iv) Inline functions. (4)
(i) Describe and Write a C++ program to overload the increment BTL-2 Understanding
5 operator with prefix & postfix forms. (7)
(ii) Distinguish the term overloading & overriding. (6)
6 Discuss the types of inheritance in detail. (13) BTL-2 Understanding
Assume the classes Person Student and PartTimeStudent are inherited from BTL-2 Understanding
one another. Describe classes with suitable data members(common and
7 special attributes)and methods using C++ program to demonstrate the types
of inheritance. (13)
(i) Write a program to illustrate dynamic initialization of objects. (6) BTL-3 Applying
8 (ii)Write a program to illustrate the process of multilevel-multiple
inheritance concepts of C++ language. (7)
What is meant by function overloading? Write a C++ program to BTL-3 Applying
9
illustrate the concept of function overloading. (13)
 (i)Analyze and Write a C++ program using operator overloading to add BTL-4 Analysing
two time values in the format HH:MM:SS to the resulting time along
with rounding off when 24 hours is reached. A time class is created and
10
operator +is overloaded to add the two time class objects. (7)
(ii)Write a C++ program to explain unary and binary operator
overloading. (6)
11 Explain overloading the assignment operator with examples. (13) BTL-4 Analysing
Explain the following string operations using C++ program.(i)Finding the BTL-4 Analysing
length of string (ii)finding the substring from the string.(iii)replace a given
12 substring in a string (iv)concatenate two strings (v)compare two strings
(vi)insert a substring in a given string. (13)

(i) Explain and Write a program to perform string copy operation using BTL-5 Evaluating
dynamic constructor. (6)
(ii) Consider the following arithmetic operations.
13 C=2+B & k=S-T where B,C,K,S &T are the objects of a class called
‘ID Array’ Write a program to perform these operations by overloading
the + and – operators appropriately. (7)
Develop a program in C++ to demonstrate runtime polymorphism in BTL-6 Creating
14 hierarchy of classes on a member function that performs dynamic
casting. (13)

PART - C
Write a C++ program to create a base class called house. There are BTL-5 Evaluating
two classes called door and window available. The house class has
members which provide information related to the area of construction,
1. doors and windows details. It delegates responsibility of computing the
cost of doors and window construction to door and window classes
respectively. Write a C++ program to model the above relationship and
find the cost of constructing the house. (15)
Consider an example of book shop which sells book and video tapes. BTL-6 Creating
These two classes are inherited from the base class called media. The
media class has command data members such as title and publication.
The book class has data members for storing number of pages in a
2. book and the tape class has the playing time in a tape. Each class will
have member function such as read() and show() in the base class,
these members have to be defined as virtual functions, Write a program
which models the class hierarchy for book shop and process objects of
these classes using pointers to the class. (15)
 The manager class is derived from Employee class.Use C++ virtual function BTL-6 Creating
to calculate salary of Employee/Manager class.Increments for employees
3 differ based on their category.Assume suitable common and special attributes
for the classes.Implement this scenario using C++ code to prepare the
monthly and annual payment of each employee category. (15)

Write a C++ program to calculate the volume of cube,cylinder and BTL-5 Evaluating
4 rectangular box. Summerize the concept of function overloading and
write a main class to call these functions. (15)

UNIT 3 – C++ PROGRAMMING ADVANCED FEATURES

Abstract class – Exception handling – Standard libraries – Generic Programming – templates – class template –
function template – STL – containers – iterators – function adaptors – allocators - Parameterizing the class – File
handling concepts.

PART – A

Q.No Question BT Level Competence

1 When do we use multiple catch handle BTL-1 Remembering
2 What is the significance of Iterators? BTL-1 Remembering
3 List out the types of containers. BTL-1 Remembering
4 When do we use multiple catch handlers? BTL-1 Remembering
5 What is an abstract class? Give example. BTL-1 Remembering
6 What is a function adaptor? BTL-1 Remembering
7 Distinguish the term template class & class template. BTL-2 Understanding
8 Give the various file stream classes needed for file manipulation. BTL-2 Understanding
9 Summarize the use of abstract base class with an example. BTL-2 Understanding
10 Give the meaning of the flag ios::out. BTL-2 Understanding
11 Illustrate how overriding can be prevented. BTL-3 Applying
What happens when a raised exception is not caught by catch block? BTL-3 Applying
12
Summarize
13 Demonstrate the use of an exception with an example. BTL-3 Applying
14 Compare overloaded functions versus function Template. BTL-4 Analysing
15 Point out the uses of templates in C++ programming. BTL-4 Analysing
16 Point out the advantages of using streams in a program. BTL-4 Analysing
Is Abstract base class, used to create objects? Justify your answer in BTL-5 Evaluating
17
brief.
18 Compare the working of function and class template. BTL-5 Evaluating
19 Develop a simple C++ program to demonstrate exception handling. BTL-6 Creating
 Develop a simple C++ program to demonstrate a abstract class BTL-6 Creating
20 concept.

PART – B
(i)Write C++ file handling routine to copy one content of file into another BTL-1 Remembering
file. (7)
1 (ii)Explain the use of exception handling in C++ with suitable example. (6)

(i)Write short notes on C++ exception handling. (7) BTL-1 Remembering

2 (ii) Write a C++ program to write a set of characters to a file. (6)
(i)Define STL. Explain its key components and types. (5) BTL-1 Remembering
3 (ii)Write C++ code using function template to sort the items of an array. (8)
(i)Describe the components of STL. (6) BTL-1 Remembering
4 (ii)Describe and Write a class template to represent a stack of any
possible data types. (7)
(i) Describe and write a program to implement stack operations using BTL-2 Understanding
class template. (7)
(ii) Describe and Write a template function to sort the elements of an
5
array. (3)
(iii)What is an exception? Explain how the control is transferred and
handled in C++ programs. (3)
Discuss in detail about exception handling constructs and write a BTL-2 Understanding
6 program to illustrate divide by zero exception. (13)

(i) Discuss about class template with suitable example. (7) BTL-2 Understanding
7 (ii)Discuss about Abstract classes with suitable example. (6)
(i) Write a class template to represent a queue of any possible data BTL-3 Applying
type with illustration. (7)
8 (ii) Illustrate about how exceptions are handled using multiple catch
handlers. (6)
Illustrate the working of the following concepts with an example BTL-3 Applying
(i)Containers. (3)
9 (ii)Function adapters. (3)
(iii)Iterators. (3)
(iv Allocators. (4)

(i) Explain and Write a program to illustrate the concept of re- BTL-4 Analysing
throwing an exception. (7)
10 (ii) Explain and Write a program to read a string to store it in a file
and read the same string from the file to display it on the output
device. (6)
11 Explain in detail about different STL containers. (13) BTL-4 Analysing
 Explain various file stream classes needed for file manipulations. (13) BTL-4 Analysing
12

(i) Write a function template to find the minimum value contained in BTL-5 Evaluating
an array . (7)
13 (ii) Write a C++ program that reads a text file & creates another file
that is identical except that every sequence of consecutive blank space
is replaced by a single space. (6)
(i) Develop a program to write the text in a file. Read the text from the BTL-6 Creating
file, from end of the file. Display the contents of file in reverse order.
14 Append the contents to the existing file. (7)
(ii) Develop a C++ program using exception handling concept. (6)

PART - C
What are abstract classes? Write a program having student as an BTL-6 Creating
abstract class and create many derived classes such as engineering,
1 science, medical etc., from the student class. Create their object and
process them. (15)

Write a program in C++ using a random access file function to create BTL-5 Evaluating
a database of student’s information such as name, roll no,sex,address
and the program should have the following facilities (15)
(i) To display the entire database
2
(ii) To display only a particular record
(iii)To update a record
(iv) To delete a record

Prepare a C++ generic function with multiple parameters that performs BTL-6 Creating
3 recursive binary search on a linear array. (15)
Write a C++ Program to compute the square root of a number .The BTL-5 Evaluating
4 input value must be tested for validity .If it negative the user defined
function mysqrt() should raise and exception. (15)

UNIT 4 – ADVANCED NON-LINEAR DATA STRUCTURES

AVL trees – B-Trees – Red-Black trees – Splay trees – Binomial Heaps – Fibonacci Heaps – Disjoint Sets –
Amortized Analysis – accounting method – potential method – aggregate analysis.

PART – A
Q.No Question BT Level Competence
1 Define Fibonacci Heaps BTL-1 Remembering
2 Write a note on amortized analysis. BTL-1 Remembering
3 Define Balance Factor of AVL Tree. BTL-1 Remembering
4 What are splay trees? BTL-1 Remembering
5 List out the various operations that can be performed on B-trees BTL-1 Remembering
What are the various types of rotations in AVL tree during the BTL-1 Remembering
6
insertion of a node?
7 Differentiate Fibonacci heaps and binomial heaps? BTL-2 Understanding
8 Give the properties of Red Black Tree. BTL-2 Understanding
9 What are Red black trees? Give an example. BTL-2 Understanding
10 Predict a binary tree for the expression A*B-(C+D)*(P/Q). BTL-2 Understanding
What is amortized analysis? Show that the stack operation BTL-3 Applying
11
MULTIPOP costs O(1) amortized time
Show the result of inserting 2;1;4;5;9;3;6;7 into an initially empty BTL-3 Applying
12
AVL tree.
13 Illustrate aggregate analysis with an example. BTL-3 Applying
14 Point out the applications of trees. BTL-4 Analysing
15 Compare AVL tree and B-tree. BTL-4 Analysing
Analyze and write a Pseudo code to find the smallest element in the BTL-4 Analysing
16
binary search tree.
17 Summarize the advantages of using Fibonacci heaps. BTL-5 Evaluating

18 Compare AVL tree and Binary search tree. BTL-5 Evaluating

19 Develop an algorithm for inserting an element in a binary search tree. BTL-6 Creating
20 Develop an algorithm for simple disjoint set Find () operation. BTL-6 Creating

PART – B
(i)What is a red-Black tree? Mention the properties that a Red-Black BTL-1 Remembering
tree holds. (7)
1 (ii)Define AVL tree & starting with an empty AVL search tree, Insert
the following elements in the given order 35,45,65,55,75,15,25 (6)

(i) Describe the AVL rotations with suitable example . (7) BTL-1 Remembering
(ii) Describe in detail the binary heaps. Construct a min heap tree for
2 the following: (6)
5,2,6,7,1,3,8,9,4

(i) Delete AVL tree and starting with an empty AVL search tree, BTL-1 Remembering
insert the following elements in the given order: 2,1,4,5,9,3,6,7 (7)
3 (ii) Construct a B-tree with order m=3 for the key values
2,3,7,9,5,6,4,8,1 & delete the values 4 &6.Show the tree in performing
all operations . (6)
 Describe insertion and deletion operations on Fibonacci heaps. Construct BTL-1 Remembering
4 Fibonacci heaps for the following set of elements 10, 11, 5, 35, 8, 4, 2, 3,
77,1, 45. (13)

(i)Perform the splaying operation on a binary search tree obtained by BTL-2 Understanding
inserting the key values 1,2,3,4,5,6,7,8 in this order into an initially
empty tree. Describe and Write the code to do the same (splay &
insert) (7)
(ii) On an initially empty binomial heap, carry out the following
5
sequence of operations
Insert(27) Insert(17) insert(19) insert(20) insert(24) insert(12)
insert(11) insert(10) insert(14) insert(18) deletemin. After each
operation Describe and draw the resulting structure of the binomial
heap. (6)
(i) Describe the properties of binary heaps with an example. (7) BTL-2 Understanding
6 (ii) Describe about Amortized Analysis in detail. (6)

(i)Draw B-tree of order m=5 for the keys{K,O,S,V,M,F,B,G,T,U,W } (7) BTL-2 Understanding
(ii)Delete the keys K and G in order. (3)
7 (iii) Justify the number of splits needed for insert/delete with proper reasons.
(3)
Illustrate the construction of Binomial Heaps & its operations with a BTL-3 Applying
8 suitable example. (13)
(i) Show the result of inserting 43, 11, 69, 72&30 into an initially BTL-3 Applying
empty AVL tree. Show the results of deleting the nodes 11 & 72 one
9 after the other of the constructed tree. (7)
(ii) Illustrate the concept of potential method and accounting method
with an example. (6)
(i) Explain about aggregate analysis with an example. (7) BTL-4 Analysing
10 (ii)Explain about the smart union algorithms with suitable example.(6)
 (i) Merge the given Binomial heaps.Explain the procedure for merge BTL-4 Analysing
operation. (5+3)

2
9
1
8 4 7
H1:
1 1
1 5 1
0
11 2
2
1
6
3
H2:
1
4

(ii)Delete three elements from the merged Binomial Queue. (5)

Starting from an empty height balanced tree insert the following data BTL-4 Analysing
one-by-one in the sequence as given and ensure that insertion of each
12 node results a height balanced tree. Explain and write the algorithm
for balancing the tree. (13)
8,9,10,2,1,5,6,4,7,11,12,3
(i) Consider the following list of numbers BTL-5 Evaluating
14,15,4,9,7,18,3,5,16,4,20,17,9,14,5
13 Using that construct a binary search tree. (7)
(ii)Summarize the working of Find () operation using a path
compression. (6)
(i)Create a max heap tree for the numbers(in order): BTL-6 Creating
95,85,45,75,25,35,15,55 and then (7)
a. insert 17
14 b. insert 100
c. delete 100
(ii)Formulate algorithms to perform insertion and deletion in a binary
search tree. (6)

PART - C
(i) Construct an AVL tree with values F,S,Q,K,C,L,H,T,V,M,R into BTL-6 Creating
an initially empty tree. Write the algorithm for inserting into an AVL
1 tree. (10)
(ii)Write a note on general trees with an example. (5)
 Write a program to accept keys from the user one at time. Build them BTL-5 Evaluating
2 into an AVL tree and write out the tree at each stage. Also write a
function to delete a node from AVL tree. (15)
Assume the following keys form the Binary search BTL-6 Creating
tree{50,30,60,40,35,80,90} Analyze the time complexity involved in
3 searching the keys 90 and then 80,when the given BST is converted into
AVL or Splay tree. Formulate the suitable tree data structure for representing
this data and justify your answer with valid reasons. (15)
(i) Prepare the function to insert and delete a node from a binary BTL-5 Evaluating
search tree. (8)
(ii) Make a Binary search tree for the following sequence of numbers:
4
45,36,76,23,89,115,98,39,41,56,69,48
Traverse the tree in Preorder, Inorder, Postorder. (7)

UNIT 5 – GRAPHS
Representation of Graphs – Breadth-first search – Depth-first search – Topological sort – Minimum Spanning
Trees – Kruskal and Prim algorithm – Shortest path algorithm – Dijkstra’s algorithm – Bellman-Ford algorithm –
Floyd – Warshall algorithm
PART – A
Q.No Question BT Level Competence
1. Define minimum spanning tree for a graph. BTL-1 Remembering
2 State the principle of Topological Sorting. BTL-1 Remembering
What is the minimum number of spanning trees possible for a BTL-1 Remembering
3 complete graph with ‘n’ vertices?
What is the principle behind Bellman-Ford algorithm to delete the BTL-1 Remembering
4 negative weight cycles?
5 List the drawbacks of Floyd-Warshall algorithm. BTL-1 Remembering
6 Write procedure for Depth First search algorithm. BTL-1 Remembering
7 Give the way in which a graph can be represented with an example. BTL-2 Understanding
8 Discuss about Undirected graph in a very short way. BTL-2 Understanding
9 Give any 2 applications of graph. BTL-2 Understanding
10 What is an articulation point? Give a suitable example. BTL-2 Understanding
 Illustrate the Breadth First Search for the following instance of Graph BTL-3 Applying

A
11 B C D
A A A

A A A
E F
B B
Show that “Number of vertices ,V(g), in rank group g>0 is at most BTL-3
A A Applying
12 N/2F(g-1) A A

13 Illustrate the working of Euler’s circuit with an example. BTL-3 Applying

14 Compare the graph traversal methods. BTL-4 Analysing

Analyze and Write the adjacency matrix for the following graph. BTL-4 Analysing

15

16 Differentiate indegree and outdegree of a graph. BTL-4 Analysing

Does either prim’s or kruskal’s algorithm work if there are negative BTL-5 Evaluating
17 edge weights? Justify your answer.
Summarize the working of topological sort in a short and precise way. BTL-5 Evaluating
18

19 Design a looping graph and give the definition. BTL-6 Creating

20 Design a bi-connected graph and give the definition. BTL-6 Creating

PART – B
Describe Prim’s&Kruskal’s algorithm in detail. Find the minimum BTL-1 Remembering
spanning tree for the following graph using any one of the algorithm.
(13)
1
 3

b c
4 3
4
4 2

2
11
4 d
a e
B A

2 1
B A
4
A 3
5 A 4
4 f g
4
B A

4
B A

A A
Fig(1)

Describe and Explain the Dijksra’s algorithm for finding the shortest BTL-1 Remembering
2 path with a sample graph. (13)
Show the minimum spanning tree of a given Graph using BTL-1 Remembering
Kruskal’saalgorithm.Write Kruskal’s MST algorithm. (10+3)

8 7
1 2 3
4
9
2
0
3 4
1 8 1
1 7 4 4
8
6

1
7 5
6 0
1 2
 (i) What are the different ways of representing a graph? Represent the BTL-1 Remembering
following graph using those ways. (7)

F B A

E D C

(ii)Describe and Show the result of running BFS and DFS on the
directed graph given above. (6)

(i) Describe Topological sort? Write a Pseudo code to perform a BTL-2 Understanding
topological sort. (7)
5 (ii)Describe and explain Kruskal’s algorithm to construct minimum
spanning tree in an undirected graph. (6)
Describe and explain prim’s algorithm to find the minimum spanning BTL-2 Understanding
tree of the following graph. write the algorithm. (13)

1
A C E
6 4
F F F
3 3 5
4F F2 F

F
D F
B FF
4 6
F
F F
F FF
F
F F
F FF

F F F

F F F

F F F
 (i) Describe and Write an algorithm to determine the biconnected BTL-2 Understanding
components in the given graph. (7)
(ii) Interpret the biconnected components from the following graph.(6)

1 8
7

7 2 4 10
0
9
3

5 6

Examine how transitive closure of a graph can be found using Warshalls BTL-3 Applying
8 algorithm. (13)
(i)Illustrate the Dijkstra’s algorithm for finding the shortest path with BTL-3 Applying
the following graph . (7)

2
10 3
10

1 30 20
9
100

5 4
60

(ii) Illustrate the comparison of Floyd’s algorithm with Dijkstra’s

algorithm. (6)

(i) Explain any two applications of depth-first search. (7) BTL-4 Analysing
(ii)Explain briefly about single shortest path algorithm with an
10 example. (6)

(i) Explain and write a pseudo code to find a minimum spanning tree BTL-4 Analysing
using kruskal’s algorithm. (7)
11
(ii)Write routines to find shortest path using Dijkstra’s algorithm. (6)
 BTL-4 Analysing
Consider the following graph.Determine the shortest distance to all other
nodes using Dijikstra’s algorithm Write Procedure. (10+3)

9 3
2

2 6

12 6 2
2
4
2
1
4 6

2
8
0

(i) Explain in detail about bi connectivity. (7) BTL-5 Evaluating

(ii) Consider the following specification of a graph G
V(G)={1 , 2, 3, 4}
13 E(G)={(1, 2),(1, 3),(3, 3),(3, 4),(4, 1)}
1. Draw an undirected graph.
2. Draw its adjacency matrix. (6)
Prepare the pseudocodes of the different graph traversal methods BTL-6 Creating
14 and demonstrate with an example. (13)

PART - C

(i) Create an algorithm for breadth first search on a graph & give the BTL-6 Creating
nodes of the graph ‘G’ given in the fig(1). based on the algorithm. (8)
1 (ii) Using Dijiktra’s algorithm, find the shortest path from the source to
all other nodes of the graph ‘G’ given in fig(2). (7)
 V 2 V2 10
1
4
A 1 3
4

2 2
4 4 V5
V3 V4
B A

8 B A

A
4
A 6
5 4
4 V6 V7

B A
1 B A

4
A Afig(1)

A B E F

fig(2)

(i) Find the Shortest weighted path from A to all other vertices for the BTL-5 Evaluating
graph in given below figure. (8)
(ii) Find the shortest weighted path from B to all other vertices for the
graph in the given below figure. (7)
1
B G 1
5
3
A

A 2 B A

1
2 3 A7 E
4 4
A 4 C
2
7 B A

4 B A

1 A
2 D A F 4
4 6
B A

A
 Using Dijkstra’s algorithm to find the shortest path from the source node BTL-5 Evaluating
A. (15)

(i)Prepare the pseudo code to find a minimum spanning tree using BTL-6 Creating
kruskal’s algorithm. (7)
(ii)Find the topological ordering of the below graph. (8)

g
4
e c
f

b
d