Download AKTU B-Tech 4th Sem 2015-16 NEC 401 Data Structure Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 4th Semester (Fourth Semester) 2015-16 NEC 401 Data Structure Question Paper

Printed Pages: 6 NEC-401
(Following Paper ID and Roll No. to be ?lled in your
Answer Books)
Roll Nam
B.TECH.
Theory Examination (Semester-IV) 2015-16
DATA STRUCTURE
Time : 3 Hours Max. Marks : 100
Seclion-A
Q1. Attempt all parts. All parts carry equal marks. Write
answer of each part in short. (ZXI0=20)
(a) What is an abstract data type? Is time and space com-
plexity considexed in de?ning ADT?
(b) Pa?fonn evaluation of post?x expmsion using slack: ABC
+ *DE /? , where
A=5, B=6, C=2, D=12, E=4
(l) P.T.O.
2605/1757235/5875 ?

(C)
(d)
(e)
(f)
(h)
(1)
How does linked list differ from an array?
At most, how many comparisons are required to search
an element from a sorted vector of 1023 elements using
the binary search algorithm ?
Demonstrate how will you represent the following sparse
matrix having integer values ?
MOOO
OOWH
COCO
COCO
Generate a binary search tree for the list - 53, 65, 86,
78, 5, 25, 34, 29
J
How will be the elements having same priority med
m a priority queue?
How many pointers are contained as data members in
the nodes of a circular doubly linked list of integcls with
?ve nodes?
Draw a directed weighted (assume random weights)
graph having 5 vertices and each node having drgree 4.
(2)
2605/173/235/5875
(i)
A certain sorting algorithm is applied to the follow-
ing data set 45,1,27,36,54,90.A?er two passes the re-
arrangement of the data is 1, 27, 45, 36, 54, 90.
Identify the sorting algorithm that was applied ? Jus-
tify the answer.
Section-B
Q2. Attempt any ?ve questions from this section.
(10X5= 50)
(a) Explain asymptotic notations. Discuss Big(0)
notation.
(b) Explain how polynomial can be expressed using linked
list. Write a C program to add two polynomials using
linked list.
(0) Write a C program to implement stack using linked list
and perform PUSH and POP operations onto the stack.
((1) Explain the concept of circular queue. Discuss the base
cases to be ven'?ed for canying our insertion and dele-
tion operations in a circular queue.
(3) P.T.O.
2605/W235/5875

(e)
(f)
(g)
(h)
Find out degree of each node for a graph given be-
low. Apply BFS algorighm and obtain the graph node
traversal sequence, considering stattind node of the
BFS traversal as Node 1.
What is tail recursion? Write a C program using
recursive function that solves tower of Hanoi prob-
lem.
Draw Huffman tree and generate Hu??man code for
the fbllowing symbols whose frequency of occurance
in a message is stated along with symbols given below
:Also estimate the total number of memory bits saved
using the Huffman coding scheme.
A115 8:16 C:l7 D:12 E:25 F:4 G:6 Hzl 1:15
(3) Write a C program to search an element in array
using binary search technique.
(4)
2605/176/235/5875
(b) Perform two way merge sort operation on the
array given-
F24|7|46|41|85|4l94|14|
Section-C
Note: Attempt any two questions from this section.
(15X2=30)
Q3. (a) What is the importance of Garbage Collection?
(b) Write an algorithm to delete and insert elements in
DEQUE.
(c) Write an algorithm to delete last element from a doubly
linked list.
Q4. (3) Sort 20, 35, 40, 100, 3, 10, 15 using selection sort.
(b) Explainwi?lanexampleto ?ndminimmnoostspanning
tree using Kmskal algorighm.
(5) P.T.O.
2605m6/235/5875

Q5. (a) Generate a binary u'ee for the following traversal
sequences given -
IN-ORDER: BFGHPRSTWYZ
PRE-ORDER: PF?BHGSRYTWZ
(b) Write an algorithm to convert an in?x expression into
post?xfmm.
(6)
2605/m/235/5875