Data Structures and Algorithm Analysis Set 11

Data Structures and Algorithm Analysis

101.

What of the following cases is a so-called "collision"?

(a)	A hash function produces the same address for two different keys: h( key1 ) = h( key2 ) where key1 =\= key2
(b)	Two different hash functions produce the same address for a given key: h1( key ) = h2( key )
(c)	Two different hash functions produce the same address for two different keys: h1( key1 ) = h2( key2 ) where key1 =\= key2
(d)	A hash function produces the same address for two different keys with different lengths: h( key1 ) = h( key2 ) where length(key1) =\= length (key2)
(e)	A hash function produces the same address for two keys of the same length: h( key1 ) = h( key2 ) where length(key1) = length(key2).

102.

Which of the following statements is INCORRECT when the differences/similarities between binary search trees and heaps?

(a)	Both binary search trees and heaps are binary trees
(b)	Both binary search trees and heaps require ascending order between sibling nodes
(c)	With heaps the smallest value is stored at the root, while with binary trees the smallest value is on the leftmost leaf
(d)	In heaps no gaps are allowed apart from the right side of the leaves' level, but in binary search trees gaps are allowed
(e)	The order of root, left, right nodes are different for both the trees.

103.

Find the odd one out from the following categories of algorithms.

104.

For the ease of searching in a linked list, the linked list be created in

(a)	Descending order
(b)	Ascending order
(c)	Without underflow condition
(d)	Any order
(e)	With underflow condition.

105.

The time complexity of binary search in best, worst cases for an array of size N is

106.

Folding is a method of generating

(a)	A hash function
(b)	Index function for a triangular matrix
(c)	Linking the tail node to the head node in linked list
(d)	Linear probing
(e)	Chaining.

107.

Which of following algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of desired order?

108.

What is the linked list that contains a variable whose value is the address of the location of the other node in the list?

109.

The mathematical definition for Omega can be defined as, provided f,g:NàR⁺ and c is a positive constant and n > n₀,

110.

The q notation is

101.	Answer : (a) Reason: Collision happens if the hash function produces the same address for two different keys in the prime area.
102.	Answer : (b) Reason: As this statement is totally wrong as Binary search trees require ascending order between siblings node, but heaps don't.
103.	Answer : (e) Reason: This one belongs to NP-Class category.
104.	Answer : (d) Reason: What ever the order it may be, always we have to search for a node in the entire linked list, which is always organized in discrete locations. Hence no any particular order is needed.
105.	Answer : (b) Reason: Best case is; if the element to search is there at mid of he list. Worst case is; if the element we are searching is either not there in the list or at the beginning of the list or end of the list.
106.	Answer : (a) Reason: Folding is one of the methods in hashing functions. It can be shift folding or rounded folding.
107.	Answer : (d) Reason: Bubble sort only is the algorithm from the given options which compares the adjacent keys.
108.	Answer : (e) Reason: A self referential pointer variable is used to hold the address of the next node in the list.
109.	Answer : (a) Reason: According to the mathematical definition of the Asymptotic notations.
110.	Answer : (e) Reason: Because q notation is equivalence relationship in nature.