Question # 1 of 10 Total Marks: 1

The _____ of the in a binary tree is defined as the height of its left sub tree

minus the height of its right sub tree.

Height

Balance

Depth

None of above

Question # 2 of 10 Total Marks: 1

In which case of insertion a single rotation can make the AVL tree balanced?

An insertion into left subtree of the left child of α.

An insertion into right subtree of the left child of α.

An insertion into left subtree of the right child of α.

None of above.

Question # 3 of 10 Total Marks: 1

The _____ of a binary tree is the maximum levels of its leaves (also called

the depth)?

Level

Width

Height

None of the above

Question # 4 of 10 Total Marks: 1

Maximum time an insertion operation can take in AVL tree is? Here Log

stands for Log to the base of 2.

Log(n)

1.44 Log (n)

1.66 Log (n)

Log (n+1)

Question # 5 of 10 Total Marks: 1

Which one of the following is to more close to AVL Tree?

BST

Complete BST

Heap

None of above

Imrangee

Question # 6 of 10 Total Marks: 1

Which of the following data structure is of linear type?

Strings

Queues

Lists

All of above

Question # 7 of 10 Total Marks: 1

A binary search tree (BST) every node has two or zero node is called_____.

Complete BST

BST

Extended BST

None of above

Question # 8 of 10 Total Marks: 1

Which data structure allows inserting elements at the back and removing

from the front?

Stacks

Queues

BST

Deques

Question # 9 of 10 Total Marks: 1

BST violates the condition of AVL when any node has a balance equal

to____

2 or -2

1 or -1

0

None of above

Question # 10 of 10 Total Marks: 1

Incase of insertion of left outer node in BST we apply___

Single right rotation to make it AVL

Single left rotation to make it AVL

Double rotation, first left then right rotation.

None of above

"We use ER Data Model in conceptual database design instead of using other models but we never use ER data model in our logical database design"

Idea Solution:-

Conceptual database designs is used to define the objects and relations between them. ER diagram is best suited for defining relation and there respective functions. This model is flexible enough to bear a change with out any harm to other data's structure. ER data base model represent association. which is needed to define relations.

Logical database model is some what advanced of this model. In this model you need to define keys, attributes, behaviors and foregn keys to be inherit and possible representation which can be converted into physical data models. here we do not need association and other functionalities thats why we did not use ER diagrams.

Please do make changes in these assignment otherwise every one who copy this assignment as it is will awarded zero marks 

Question: Mark:5+5+5+5 Consider the following Context Free Grammar (CFG) S → aY | Ybb | Y X → Λ | a Y → aXY | bb | XXa a) Is the CFG ambiguous, if Yes then justify your answer. b) Draw a Total Language Tree (TLT) for the given CFG. c) Convert the CFG into CNF. d) Build the PDA corresponding to the CFG (in CNF) of part (c).

Solution:-

i think it will help u>>>>>>

Question: Mark:5+5+5+5 Consider the following Context Free Grammar (CFG)
S → aY | Ybb | Y

X → Λ | a
Y → aXY | bb | XXa a) Is the CFG ambiguous, if Yes then justify your answer. b) Draw a Total Language Tree (TLT) for the given CFG. c) Convert the CFG into CNF. d) Build the PDA corresponding to the CFG (in CNF) of part (c).

Part a

this CFG Is not ambiguous because any string in not shown two derivation tree.


Part b

second is its total language tree may be arbitrary wide as well as infinity long.


Part c

CFG Into CNF removing null and unit production

s-> Ay| yBB | b
x-> a | a
y-> Axy | Ax |BB | xxa| xx | xA | a
A->a
B->b
part d

This is wrong.I was not able to convert it into CNF, but I am very close to do it so!
S->aY|Ybb|Y
X->^|a
Y->aXY|bb|XXa
null production
Y->aY|bb|Xa|a
after removing null production
S->aY|Ybb|Y
X->a
Y->aY|bb|Xa|a
Unit production
S->Y
S->Y->aY gives S->abb (Y->bb)
S->Y->aY gives S->aa (Y->a)
S->Y->aY->aXa gives S->aaa (X->a)
New CFG will be
S->aY|Ybb|abb|aa|aaa
X->a
Y->aY|bb|Xa|a
(i am stuck here)
 

Please do make changes in these assignment otherwise every one who copy this assignment as it is will awarded zero marks