THEORY EXAMINATION (SEM–) 2016-17 DATA STRUCTURE

DATA STRUCTURE – EEC012

B.Tech (SEM VI) | Section-wise Solved Answers

SECTION – A

(Explain the following – 2 marks each)

(a) Dynamic vs Static Data Structure

Static data structures have fixed memory size decided at compile time, such as arrays. Dynamic data structures can grow or shrink during runtime, such as linked lists.

(b) Big Omega (Ω) Notation

Big Omega notation represents the best-case time complexity of an algorithm. It provides a lower bound on running time.

(c) Pop Algorithm

Pop operation removes the top element from a stack and decreases the top pointer by one, provided the stack is not empty.

(d) Simulation Recursion

Simulation recursion replaces recursive calls with an explicit stack to avoid system recursion overhead.

(e) Preorder Traversal Algorithm

In preorder traversal, the root node is visited first, followed by the left subtree and then the right subtree.

(f) Node and Height of a Tree

A node is a basic unit containing data and links. Height of a tree is the number of edges on the longest path from root to leaf.

(g) Minimum Spanning Tree

A minimum spanning tree connects all vertices of a graph with minimum total edge weight and no cycles.

(h) Fully Connected Graph

A fully connected graph has an edge between every pair of vertices.

(i) Merge Sort

Given list: 3,5,4,6,8,2,9
Sorted list using merge sort:
2,3,4,5,6,8,9

(j) Sequential vs Binary Sort

Sequential sort compares elements one by one, while binary sort uses divide-and-conquer for faster searching and sorting.

SECTION – B

(Attempt any five – explained properly)

(a) Row Major and Column Major Order

Row major stores row elements consecutively, column major stores column elements consecutively.
Address calculation uses base address, element size, row and column limits.

(b) Linked List and Types

A linked list is a collection of nodes connected using pointers. Types include singly, doubly, circular, and doubly circular linked lists.
Algorithms exist for insertion at beginning, end, and specific position.

(c) Queue Insertion & Expression Conversion

Queue insertion adds an element at the rear after checking overflow.
Expressions are converted using stack precedence rules into prefix and postfix forms.

(d) Binary Tree Construction

Given inorder and postorder traversals, the binary tree is reconstructed by identifying root and subtrees recursively.

(e) Huffman Coding

Huffman algorithm builds an optimal prefix code based on probabilities.
Average code length is calculated using weighted path length.

(f) Quick Sort

Quick sort uses partitioning.
Best case complexity: O(n log n)
Worst case complexity: O(n²)
Sorted result: 26,38,43,48,50,53,60

(g) AVL Tree

AVL trees are self-balancing binary search trees.
After inserting elements, rotations are performed to maintain balance factor.

(h) BFS Traversal

Breadth First Search uses a queue to visit nodes level by level.
It is used to generate BFS spanning trees.

SECTION – C

(Attempt any two – long answers)

(3) Data Structure & Matrix Transpose

A data structure organizes data efficiently. Types include linear and non-linear structures.
Matrix transpose swaps rows and columns using nested loops in C.

(4) Tower of Hanoi & Expression Evaluation

Tower of Hanoi solves disk transfer using recursion.
Infix expression is converted to postfix using stack and evaluated step by step.

(5) Prim’s Algorithm

Prim’s algorithm finds MST by selecting minimum weight edges.
It starts from any vertex and expands the tree until all vertices are included.