[go: up one dir, main page]
Scribd
Upload
60 views56 pages

Day3 Session 1

AVL Tree - An AVL tree is a self-balancing binary search tree. It ensures that the height of the two subtrees of any node never differ by more than one. - The maximum height of any AVL-tree with 7 nodes is 3. During construction of an AVL tree with elements added in a given order, 2 left rotations and 3 right rotations are required. Heap - A heap is a complete binary tree with the property that the key stored in each node is either greater than or equal to (for max-heap) or lesser than or equal to (for min-heap) the keys in its children nodes. - Inserting an element into a min-heap

Uploaded by

schweser Books
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
60 views56 pages

Day3 Session 1

AVL Tree - An AVL tree is a self-balancing binary search tree. It ensures that the height of the two subtrees of any node never differ by more than one. - The maximum height of any AVL-tree with 7 nodes is 3. During construction of an AVL tree with elements added in a given order, 2 left rotations and 3 right rotations are required. Heap - A heap is a complete binary tree with the property that the key stored in each node is either greater than or equal to (for max-heap) or lesser than or equal to (for min-heap) the keys in its children nodes. - Inserting an element into a min-heap

Uploaded by

schweser Books
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 56

AVL Tree

Which of the following is AVL Tree?


A. Only A
B. Only B
C. A and C
D. A, B and C
Ans: C
• What is the maximum height of any AVL-tree
with 7 nodes?
(Assume that the height of a tree with a single
node is 0.)

(A) 2
(B) 3
(C) 4
(D) 5
Ans: B
Ans: C
• How many rotations are required during the
construction of an AVL tree if the following
elements are to be added in the order given?
35, 50, 40, 25, 30, 60, 78, 20, 28

A. 3 left rotations, 2 right rotations


B. 2 left rotations, 2 right rotations
C. 2 left rotations, 3 right rotations
D. none of these
Ans: C

RL + LR + RR
2 LL rotations and 3 RR rotations are required.
What will be the post order traversal of the AVL
tree formed by the nodes given below:
10, 15, 40, 20, 50, 30, 18, 5, 7

A. 20, 15, 7, 5, 10, 18, 40, 30, 50


B. 5, 7, 10, 15, 18, 20, 30, 40, 50
C. 10, 5, 18, 30, 7, 30, 50, 20, 40
D. 5, 10, 7, 18, 15, 30, 50, 40, 20
Ans: D
• What will be post order traversal of the
resultant tree after insertion of
10,15,40,20 and 22
in the following AVL tree?

(A) 10 15 12 20 30 22 45 18 40
(B) 10 15 12 20 22 30 45 40 18
(C) 10 15 12 20 30 22 45 40 18
(D) none of these
Ans: C
In the AVL tree shown here, How many
nodes will become unbalanced if a node
is inserted as a child of node g?

A. 2
B. 3
C. 4
D. Depends whether the node inserted is
left child of g or right child.
Ans: B
On addition of a node below g in the previous
question, which of the following will make the
tree balanced again with minimum movement?

A.Making c as root
B.Connecting left subtree below c as right subtree
of b.
C.g as left subtree of f.
D.None of These
Ans: D
How many LL rotations will be applied to
construct an AVL tree with given nodes?
30, 40, 20, 50, 35, 33, 15
A. 0
B. 1
C. 2
D. 3 
Ans: B
Which of the following is TRUE?
A.Every Binary Search Tree is an AVL.
B.Complexity of searching an element in AVL
tree is O(n).
C.LL rotation is consists of two Left rotations on
different nodes.
D.None of These
Ans: D
HEAP
Consider a binary min-heap implemented
using an array. Which one of the following
array represents a binary min-heap?

A. 10, 40, 45, 20, 30, 25, 55, 60, 45


B. 20, 40, 45, 10, 25, 30, 60, 55, 50
C. 10, 40, 20, 50, 45, 25, 30, 55, 60
D. 10, 45, 20, 40, 50, 25, 30, 60, 55
Ans: C
Consider a min heap, represented by the
following array:
10, 30, 20,70,40, 50, 80, 90
After inserting a node with value 31, which of
the following is the updated min heap?
A. 10,30,20,31,40,50,80,90,70 
B. 10,30,20,70,40,50,80,60,31
C. 10,31,20,30,40,50,80,60,31
D. 31,10,30,20,70,40,50,80,60
Ans: A
Which of the following operations on a max-heap require
Ѳ(logn) time?
(i) Finding the maximum element
(ii) Inserting any element
(iii) Inserting an element greater than the maximum element
(iv) Inserting an element lesser than the minimum element

A. (ii),(iv)
B. (ii),(iii)
C. (i),(ii),(iii)
D. (ii),(iii),(iv)
Ans: B
Consider the following array of elements.
〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〈.
The minimum number of interchanges needed
to convert it into a max-heap is:

A.2
B. 3
C. 4
D. 5
Ans: B
Consider any array representation of an n
element binary heap where the elements are
stored from index 1 to index n of the array.
For the element stored at index i of the array
(i <= n), the index of the parent is:
A. i-1
B. (i+1)/2
C. ceiling(i/2)
D. floor(i/2)
Ans: D
In a heap with n elements with the smallest
element at the root, the 7th smallest element
can be found in time:

A.  O(n log n)


B.  O(n)
C. O(log n)
D. O(1)
Ans: D
We have a binary heap on n elements and wish
to insert n more elements (not necessarily one
after another) into this heap. The total time
required for this is:

A.  O(logn)
B.  O(n)
C.  O(nlogn)
D. O(n^2)
Ans: B
• A 3-ary max heap is like a binary max heap, but instead of 2
children, nodes have 3 children. A 3-ary heap can be
represented by an array as follows: The root is stored in the
first location, a[0], nodes in the next level, from left to right, is
stored from a[1] to a[3]. The nodes from the second level of
the tree from left to right are stored from a[4] location onward.
An item x can be inserted into a 3-ary heap containing n items
by placing x in the location a[n] and pushing it up the tree to
satisfy the heap property. Which one of the following is a valid
sequence of elements in an array representing 3-ary max heap?

A. 1, 3, 5, 6, 8, 9 B. 9, 6, 3, 1, 8, 5
C. 9, 3, 6, 8, 5, 1 D. 9, 5, 6, 8, 3, 1
Ans: D
Suppose the elements 7, 2, 10 and 4 are inserted, in
that order, into the valid 3- ary max heap found in the
above question, Which one of the following is the
sequence of items in the array representing the
resultant heap?
 
A. 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
B. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
C. 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
D. 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Ans: A
B-Tree
Which one of the following is a key factor for
preferring B-trees to binary search trees for indexing
database relations?

A. Database relations have a large number of records


B. Database relations are sorted on the primary key
C. B-trees require less memory than binary search
trees
D. Data transfer form disks is in blocks.
Ans: D
A B-tree of order 4 is built from scratch by 10
successive insertions. What is the maximum
number of node splitting operations that may
take place?
A. 3
B. 4
C. 5
D. 6
Ans: C
Huffman Coding
Huffman coding is an encoding algorithm used
for:

A. lossy data compression


B. lossless data compression
C. files greater than 1 Mbit
D. broadband systems
• Ans: B
The basic idea behind Huffman coding is to:

A. Compress data by using fewer bits to encode


more frequently occurring characters
B. Expand data by using fewer bits to encode
more frequently occurring characters
C. Compress data by using more bits to encode
more frequently occurring characters
D. Compress data by using fewer bits to encode
fewer frequently occurring characters
• Ans: A
A Huffman code:
A = 1, B = 000, C = 001, D = 01
P(A) = 0.4, P(B) = 0.1, P(C) = 0.2, P(D) = 0.3
The average number of bits per letter is:

A. 2.0 bit
B. 2.1 bit
C. 1.9 bit
D. 1.8 bit
• Ans: C
A Text consists of the letters A, B, C and D.
The probability of occurrence is 
P(A) = 0.4, P(B) = 0.1, P(C) = 0.2 and P(D) = 0.3.
The Huffman code is:

A. A = 01,B = 111,C = 110,D = 10


B. A = 0,B = 11,C = 10,D = 111
C. A = 0,B = 111,C = 11,D = 101
D. A = 0,B = 111,C = 110,D = 10
• Ans: D

You might also like