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.