Download AKTU B-Tech 4th Sem 2016-17 Data Structure Question Paper

Roll FirstRanker.com

B.TECH.

THEORY EXAMINATION (SEM–IV) 2016-17

DATA STRUCTURE

Time: 3 Hours Max. Marks : 100

Note: Be precise in your answer. In case of numerical problem assume data wherever not provided.

--- Content provided by​ FirstRanker.com ---

SECTION A

1. Answer all the questions. 10x2=20
   1. 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.
   2. Write down the difference between static and dynamic memory.
   3. What is the advantage of doubly linked list over singly linked list? What is an algorithm?
   4. What is recursion? A recursive procedure should have two properties. What are they?
   5. Define the following: (i) Tree (ii) Level of a node. (iii) Height of a tree.

   --- Content provided by⁠ FirstRanker.com ---

   6. Write down any four applications of queues.
   7. Define garbage collection and compaction
   8. What is a sparse matrix? How is it stored in the memory of a computer?
   9. Differentiate between Linear and Non-Linear Data Structures with examples.
   10. Define adjacency matrix with suitable example.

   --- Content provided by⁠ FirstRanker.com ---

SECTION B

2. Answer any five questions from this section. 5x10=50
   1. Explain Breadth First Search with suitable example.
   2. 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?
   3. Convert E=abcde^^*+ postfix expression to infix and prefix using stack.
   4. Write an algorithm for finding solution to the Towers of Hanoi problem. Explain the working.

   --- Content provided by⁠ FirstRanker.com ---

   5. Write a C-Function for Linked List Implementation of stack. Write all the Primitive Operations.
   6. Perform the Merge Sort on following set of elements. Also, write merge sort algorithm. 18, 25, 4, 26, 10, 15, 20, 5.
   7. Why circular queue is used over simple queue? Write algorithms to implement all operations in a circular queue using arrays.
   8. 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 .

--- Content provided by⁠ FirstRanker.com ---

SECTION C

Answer any two questions of the following. Each question carries equal marks. 2x15=30

3. 1. Draw a binary tree which has following traversal Inorder: DJGBAEHCFI Preorder: ABDGJCEHFI
   2. Explain threaded binary tree with suitable example.
4. 1. What are doubly linked lists? Write a C program to create doubly linked list.

   --- Content provided by​ FirstRanker.com ---

   2. Define internal sorting techniques
5. Write short notes of the following:
   1. Huffman Algorithm
   2. Depth First Search
   3. Priority Queue

   --- Content provided by‍ FirstRanker.com ---

   4. Abstract Data Type(ADT)