Very short questions

Chapter 1

Quadratic probing to handle ______________

Correct Answer: collision

What kind of deletion is implemented by hashing using open addressing?

Correct Answer: active deletion

Hashing technique which allocates fixed number of buckets is classified as ______

Correct Answer: external hashing

What is a hash table?

Correct Answer: A structure that maps keys to values

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash
function x mod 10. Each element hashes to a different value. True/False
Correct Answer: False

In simple chaining, what data structure is appropriate?

Correct Answer: Doubly linked list

In simple uniform hashing, what is the search complexity?

Correct Answer: O(1)

What is simple uniform hashing?

Correct Answer: Every element has equal probability of hashing into any of the slots

What can be the techniques to avoid collision?

Open addressing, chaining ets.

Correct Answer: Make the hash function appear random,

Use the chaining method, Use uniform hashing
Keys of dictionary must be
Correct Answer: unique

In Dictionary, when duplicate keys encountered, the last assignment

wins. True/False

Correct Answer: True

The keys of a dictionary can be accessed using values. True/False

Correct Answer: False

Chapter 2
What is indexed skip list?

Correct Answer: it stores width of link in place of element

The nodes in a skip list may have many forward references. Their number is determined
__________
Correct Answer: probabilistically

What is the time complexity improvement of skip lists from linked lists in insertion and deletion?
Correct Answer: O(n) to O(log n) where n is number of elements

Skip lists are similar to ________ data structure.

Correct Answer: balanced binary search tree

Consider the 2-level skip list

How to access 38?

Correct Answer: travel 20-30-35-38

 What is a skip list?
Correct Answer: a linked list that allows faster search within an ordered sequence

Chapter 3

2-3 tree is a specific form of

Correct Answer: B – tree

What output does the below pseudo code produces?
Tree_node function(Tree_node x)
{
Tree_node y = x.left;
x.left = y.right; y.right
= x;
return y;
}
Correct Answer: right rotation of subtree

Cache implementation is an application of __________ trees?

Correct Answer: splay

What is a splay operation?

Correct Answer: moving a node to root

Why to prefer splay trees?

Correct Answer: easier to program and faster access to recently accessed items

What are splay trees?

Correct Answer: self adjusting binary search trees

When it would be optimal to prefer Red-black trees over AVL trees?

Correct Answer: when there are more insertions or deletions

________________ an application of Red-black trees.

Correct Answer: can be used in process schedulers, maps, sets

What are the operations that could be performed in O(log n) time complexity by red-black
tree?

Correct Answer: insertion, deletion, finding predecessor, successor

Why do we impose restrictions like

. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black to

Correct Answer: to get logarithm time complexity

What is the special property of red-black trees and what root should always be?

Correct Answer: a color which is either red or black and root should always be black color only

Chapter 4

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

Correct Answer: Suffix tree

What traversal over trie gives the lexicographical sorting of the set of the strings?
Correct Answer: inorder

Trie is also known as

Correct Answer: Digital Tree

Reducing search space by eliminating irrelevant trees is known as ______

Correct Answer: pruning

What is the worst case of finding the nearest neighbour?

Correct Answer: O(n)

Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and
“cbhgrsfnmq” ?
Correct Answer: fgmna

What
15. is the time complexity of the brute force algorithm used to find the longest common
subsequence?
Correct Answer: O(n)

Longest common subsequence is an example of

Correct Answer: 2D dynamic programming

Consider
17.
the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest
common subsequence?

Correct Answer: 7

Both
18.
recursion and dynamic programming methods can be used to solve the longest common
subsequence problem. True/False

Correct Answer: True

The failure function f (k) is defined as ______________

Correct Answer: the length of the longest prefix of P that is a suffix of P[1:k+1]

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

Correct Answer: O(m)

What is the worst case running time in searching phase of Boyer-Moore’s algorithm?

Correct Answer: O(n)

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

Correct Answer: both good and bad character shift tables

Which algorithm formed the basis for the Quick search algorithm?
Correct Answer: Boyer-Moore’s algorithm

Which is the fastest algorithm in string matching field?

Correct Answer: Quick search algorithm

Chapter 5

What will be the correct sequence of insertion for the following k-d tree?

Correct Answer: (30,40),(5,25),(10,12),(70,70),(50,30),(35,45)

In a k-d tree, k originally meant?

Correct Answer: number of dimensions

Which data structure supports range searching?

Correct Answer: K-d trees

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

Correct Answer: True

In what time can a 2-d tree be constructed?

Correct Answer: O(n log n)
Short Questions (5 Marks)

Chapter 1
Enlist the key features properties of a Dictionary Data Type.
What do you understand by Abstract Data Type?
State the purpose of a hash function
What do you understand by a good Hash Function?
Explain a hash function
What is Rehashing?
What is the difference between proper and improper hash function?

Chapter 2
Define a Skip List

Chapter 3
Define a Binary Search Tree.
Define a B-Tree
What is the difference between B-Tree and B+ Tree
Define 2-3 Tree
Define AVL tree
Define a Splay tree

Chapter 4
Write the Brute-Force Pattern Matching algorithm
State the Longest Common Subsequence Problem
What is a Trie Data Structure?

Chapter 5
Define a Priority Search Tree
Define a Range Tree
Define k-D Trees
 Long Questions (15 marks)
Chapter 1
Explain the concept of Abatract Data Type with Suitable Example. Explain any one of
the ADT. Discuss the advantages of abstract data type.

State some application area of hashing? Explain the advantages and disadvantages of
hashing. Describe the chaining technique in hashing? What is the advantage of
changing?

What is Open addressing hashing? What are the different types? Explain any one of the
technique with suitable example.

Chapter 2
Explain the concept of randomization in Data Structure. Describe the randomized Quick
Sort algorithm. What is the complexity of the algorithm?

How is a skip list different from conventional linked list? Describe the Insertion and
Deletion process in a skip list. Find out the complexity of the algorithm.

Chapter 3
Define a binary search tree? Explain the algorithm how a node is inserted in a binary
search tree with suitable example.

State the properties of an AVL tree? Write an algorithm to insertion a node in an AVL
tree. Find the time complexity of searching a value in an AVL tree.

State the properties of a Red Black tree. Explain how a Red Black tree maintain it’s self-
balancing property with suitable example.

State the properties of a B-Tree. Describe the insertion and deletion algorithms in a B-
Tree.
State the properties of a splay tree. Explain the different rotation techniques with examples.

Chapter 4
State the pattern matching problem. Describe any pattern matching technique with
example.

Describe the Brute-Force Pattern Matching algorithm. Find out the time complexity of
the algorithm.

Explain the Boyer-Moore Pattern Matching algorithm with suitable example. Find out
the time complexity of the algorithm.

Describe the Knuth-Morries-Pratt algorithm for Pattern Matching with suitable example.
Find out the time complexity of the algorithm.

Explain the importance of Huffman coding. Describe the Huffman coding technique with
example.

State the Longest Common Subsequence Problem. Describe the dynamic programming
approach to solve this problem.

Chapter 5
Describe the one dimensional range search technique with example. Find out the time
complexity of the algorithm.

Explain how a priority search tree is constructed. What is the running time of the
technique?

Mention some applications of K-D trees. Describe how a K-D tree is constructed.

Describe a Nearest neighbor search technique with suitable example. Find out the time
complexity of the algorithm.