# Unit 5 Long Answer Important Questions of Data Structure

Q 1: Explain the following terms:

i.

Tree

Tree

ii.

Vertex of Tree

Vertex of Tree

iii.

Depth

Depth

iv.

Degree of an element

Degree of an element

v.

Degree of Tree

Degree of Tree

vi

Leaf

Leaf

Q 2: Show that the maximum number

of nodes in a binary tree of height h

is 2^(h+1)-1.

of nodes in a binary tree of height h

is 2^(h+1)-1.

Q 3: Explain binary tree

representation using array.

representation using array.

Q 4: Explain binary tree

representation using linked list.

representation using linked list.

Q 5: Write a C program to

implement binary tree insertion, deletion with example.

implement binary tree insertion, deletion with example.

Q 6: Write a C program to

implement various traversing techniques of

binary tree with neat example.

implement various traversing techniques of

binary tree with neat example.

Q 7: 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,72,24,30,66,11,50,10.

and its operations. Make a binary search

tree for the following sequence of numbers, show all steps: 45,32,90,34,72,24,30,66,11,50,10.

Q 8: Define binary search tree.

Create BST for the following data, show

all steps: 20,10,25,5,22,30,3,14,13.

Create BST for the following data, show

all steps: 20,10,25,5,22,30,3,14,13.

Q 9: Write a short note on

strictly binary tree, complete binary tree and

extended binary tree.

strictly binary tree, complete binary tree and

extended binary tree.

Q 10: Define tree, binary tree,

complete binary tree and full binary tree.

Write algorithm or function to obtain traversals of a binary tree in pre-order, post order and in order.

complete binary tree and full binary tree.

Write algorithm or function to obtain traversals of a binary tree in pre-order, post order and in order.

Q 11: Construct a binary tree for

the following:

the following:

Inorder:

Q,B,K,C,F,A,G,P,E,D,H,R

Q,B,K,C,F,A,G,P,E,D,H,R

Preorder:

G,B,Q,A,C,K,F,P,D,E,R,H

G,B,Q,A,C,K,F,P,D,E,R,H

Find

the post order of the tree.

the post order of the tree.

Q 12: Construct a binary tree for

the following:

the following:

Inorder:

D,B,H,E,A,I,F,J,C,G

D,B,H,E,A,I,F,J,C,G

Preorder:

A,B,D,E,H,C,F,I,J,G

A,B,D,E,H,C,F,I,J,G

Q 13: Construct a binary tree for

the following:

the following:

Inorder:

B,C,A,E,G,D,H,F,I,J

B,C,A,E,G,D,H,F,I,J

Preorder:

A,B,C,D,E,F,G,H,I,J

A,B,C,D,E,F,G,H,I,J

Q 14: Write procedure to insert a

new element in a binary search tree.

new element in a binary search tree.

Q 15: Write the algorithm for

deletion of an element in binary search

tree.

deletion of an element in binary search

tree.

Q 16: Write procedure to delete an

element in a binary search tree where node does not have two children.

element in a binary search tree where node does not have two children.

Q 17: Write procedure to delete an

element in a binary search tree where node

has two children.

element in a binary search tree where node

has two children.

Q 18: Write procedure to search an

element in a binary search tree.

element in a binary search tree.

Q 19: What is a threaded binary

tree ? Explain the advantages of using

a threaded binary tree.

tree ? Explain the advantages of using

a threaded binary tree.

Q 20: What is Huffman tree ?

Create a Huffman tree with following numbers

: 24,55,13,67,88,36,17,61,24,76.

Create a Huffman tree with following numbers

: 24,55,13,67,88,36,17,61,24,76.

Q 21: Explain Huffman algorithm.

Construct Huffman tree for MAHARASHTRA

with its optimal code.

Construct Huffman tree for MAHARASHTRA

with its optimal code.

Q 22: Define AVL trees. Explain

its rotation operations with example.Construct

an AVL tree with the values 10 to 1 numbers

into an initially empty tree.

its rotation operations with example.Construct

an AVL tree with the values 10 to 1 numbers

into an initially empty tree.

Q 23: Consider the following AVL

tree and insert 2,12,7,and 10 as new

node. Show proper rotation to maintain the tree as AVL.

tree and insert 2,12,7,and 10 as new

node. Show proper rotation to maintain the tree as AVL.

Q 24: What is height balanced tree

? Why height balancing of tree is

required ? Create an AVL tree for the following elements: a,z,b,y,c,x,d,w,e,v,f.

? Why height balancing of tree is

required ? Create an AVL tree for the following elements: a,z,b,y,c,x,d,w,e,v,f.

Q 25: Construct a height balanced

binary search tree by performing following

operations :

binary search tree by performing following

operations :

step1:

Insert: 19,16,21,11,17,25,6,13

Insert: 19,16,21,11,17,25,6,13

step2:

Insert 3

Insert 3

step3:

Delete 16

Delete 16

Q 26: Describe all rotations in

AVL tree. Construct AVL tree from the

following nodes: B,C,G,E,F,D,A.

AVL tree. Construct AVL tree from the

following nodes: B,C,G,E,F,D,A.

Q 27: Write a short note on B

tree.

tree.

Q 28: Define B tree. What are the

applications of B tree ? Draw a B-tree

of order 4 by inserting following keys:

applications of B tree ? Draw a B-tree

of order 4 by inserting following keys:

a,b,c,d,e,f,g,,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z

Q 29:Construct a B-tree of order 5

by inserting following elements:

3,14,7,1,8,5,11,13,6,23,12,20,26,4,16,18,,24,25,19 also delete elements 6,23 and 3 from the constructed tree.

by inserting following elements:

3,14,7,1,8,5,11,13,6,23,12,20,26,4,16,18,,24,25,19 also delete elements 6,23 and 3 from the constructed tree.

Q 30: Construct a B-tree of order

3 by inserting following elements:

10,20,30,40,50,60,70,80,90.

3 by inserting following elements:

10,20,30,40,50,60,70,80,90.

Q 31: Compare and contrast the

difference between B+ tree index files

and B-tree index files with an example.

difference between B+ tree index files

and B-tree index files with an example.

Q 32: Write a short note on Binary

heaps.

heaps.