Download AKTU B-Tech 4th Sem 2016-17 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) 2016-17 Data Structure Question Paper

Printed Pageszl Roll No.| l l l l I l l l l l NEC401
B.TECH.
THEORY EXAMINATION (SEM?IV) 2016-17
DATA STRUCTURE
Time : 3 Hours Max. Marks : 100
Note : Be precise in your answer. In case Ofnumerical problem assume data wherever not provided.
SECTION A
1. Answer all the questions. 10X2=20
a) Given a 2?D Array A [?100: 100, ?5: 50]. Find the address of element A [99, 49] considering
base address 10 and each element requires 4 bytes for storage. Follow row major order.
b) Write down the difference between static and dynamic memory.
0) What is the advantage of doubly linked list over singly linked list? What is an algorithm?
d) What is recursion? A recursive procedure should have two properties. What are they?
6) Define the following: (i) Tree (ii) Level of a node. (iii) Height of a tree.
i) Write down any four applications of queues.
g) Define garbage collection and compaction
h) What is a sparse matrix? How is it stored in the memory of a computer?
i) Differentiate between Linear and N on?Linear Data Structures with examples.
j) Define adj acency matrix with suitable example.
SECTION B
2. Answer any five questions from this section. 5X10=50
a) Explain Breadth First Search with suitable example.
b) Explain Kruskal?s algorithm to find minimum spanning tree in a weighted directed graph. Can
there be two minimum spanning trees of given weighted directed graph?
0) Convert E=abcde""*+ postfix expression to infiX and prefix using stack.
d) Write an algorithm for finding solution to the Towers of Hanoi problem. Explain the working.
6) Write a C-Function for Linked List Implementation of stack. Write all the Primitive
Operations.
i) Perform the Merge Sort on following set of elements. Also, write merge sort algorithm. 18, 25,
4, 26, 10, 15, 20, 5.
g) Why circular queue is used over simple queue? Write algorithms to implement all operations in
a circular queue using arrays.
h) Explain binary search tree and its Operations. Make a binary search tree for the following
sequence of numbers, show all steps : 45,32,90,34,68,72,15,24,30,66,11,50,10 .
SECTION C
Answer any two questions of the following. Each question carries equal marks. 2X15=30
3. a) Draw a binary tree which has following traversal
Inorder:DJGBAEHCFI
Preorder:ABDGJCEHFI
b)Explain threaded binary tree with suitable example.
4. i) What are doubly linked lists? Write a C program to create doubly linked list.
ii) Define internal sorting techniques

5. Write short notes on any three of the following
a) Huffman Algorithm
b) Depth First Search
c) Priority Queue
d) Abstract Data Type(ADT)