ADS LAB Quiz-2

Which of the following special type of trie is used for fast searching of the full texts?

• Ctrie

• Hash tree

• Suffix tree

• T tree

Which of the following is not true?

• Trie requires less storage space than hashing

• Trie allows listing of all the words with same prefix

• Tries are collision free

• Trie is also known as prefix tree

What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?

• O(n) for all

• O(Logn) for all

• O(Logn) for search and insert, and O(n) for delete

• O(Logn) for search, and O(n) for insert and delete

How can we define a AVL tree?

• A tree which is binary search tree and height balanced tree.

• A tree which is a binary search tree but unbalanced tree.

• A tree with utmost two children

• A tree with utmost three children

Why do we prefer Red Black tree over AVL tree?

• Red Black trees are not strictly balanced

• Red black tree requires lesser rotations than AVL tree.

• AVL tree needs more space to store the balance factor.

• Both Red black tree requires lesser rotations than AVL tree and AVL tree needs more space to store the balance factor.

What is a splay operation?

• moving parent node to down of child

• moving a node to root

• moving root to leaf

• removing leaf node

What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?

• O(n)

• O(n*m)

• O(m)

• O(log n)

How does KMP improve the brute-force-method?

• By comparing the characters right to left instead of left to right.

• By searching for text in pattern instead of pattern in string

• By not doing redundant comparisons and using the information gained from previous comparisons

• All of the mentioned

What character shift tables does Boyer-Moore's search algorithm use?

• good-character shift tables

• bad-character shift tables

• next-character shift tables

• both good and bad character shift tables

In a two-dimensional search tree, the root is arbitrarily chosen to be?

• Even

• Odd

• Depends on subtrees

• 1