Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Total Pages : 03
BT-3/D-22 43139
DATA STRUCTURES AND ALGORITHMS
PC-CS-201A.
Time : Three Hours] » [Maximum Marks : 75
Note : Attempt Five questions in all, selecting at least one
question from each Unit. All questions carry equal
marks.
Unit I
1. Differentiate between different Dynamic memory allocation
methods used in C. Explain the problems associated with
these methods and how to overcome those problems.
Also, implement a C program to store and display record
of an Employee dynamically and the record contains
Name, age and ID. 15
2. Answer the following questions related with sorting and
searching :
(a) Write down the pseudo code of Insertion sort and
computer the time complexity of insertion sort in
all the three cases ie. worst case, average case and
best case. 8
(6-32/3) 1-43139 P.T.O, (b) Explain step by step how to perform searching with
Binary search if given data is :
15, 23, 45, 66, 78, 99, 125, 150, 266, 280 and
searched item in the given array is 150. 7
Unit I
Consider the following arithmetic expression X, written
in Infix notation. Translate X, into its equivalent Postfix
expression with the help of Infix to Postfix expression
algorithm :
X:K+L-M*N + (0% P) * W/UV*T+Q
Also, discuss the advantages of Postfix and Prefix
expressions over Infix expression. 15
Discuss the difference between simple queue and circular
queue. Also, consider any array and write the pseudo
code for how elements are enqueued and dequeued from
the circular queue along with their overflow and underflow
conditions. 15
Unit U1
What is linked list ? Why do you add header node in the
linked list ? Also define circular linked list and write a
function of how to add an element at the specified position
and at the end of the circular linked list. 15
L-43139 2 7
8.
(a) What is the difference between singly linked list
and doubly linked list ? Also discuss pros and cons
of these, 8
(b) Write an algorithm to construct a simple linked list
with 5 nodes and print the content of linked list
starting from the given node. 7
Unit IV
What is Balanced Multiway Search Tree ? Explain its
construction and applications. Consider a graph with five
vertices and six edges, then explain how to find out
Minimum Spanning Tree (MST). Also explain Warshal’s
algorithm. 15
What is AVL tree ? Explain its need. With input data
125, 112, 117, 130, 15, 69, 115, 114, 137. 127. 140, 129,
128 depict step by step construction of an AVL Tree.
Also, delete 140, 129, 128 from the AVL tree and draw
the final one after deletion. 15
(5-32/4) L-43139 3 1,200
