# Data Structures and Algorithm Analysis Set 11

## Data Structures and Algorithm Analysis

### Questions 101 to 110

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.
 (a) TVSP (b) OBST (c) N-Queens (d) 15-Puzzle (e) Bin-Packing.
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
 (a) N, N2 (b) 1, Log N (c) Log N, N2 (d) 1, N log N (e) N, N.
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?
 (a) Insertion sort (b) Quick sort (c) Shell sort (d) Bubble sort (e) Radix sort.
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?
 (a) Integer (b) Float (c) Char (d) Void (e) Pointer.
109.
The mathematical definition for Omega can be defined as, provided f,g:NàR+ and c is a positive constant and n > n0,
 (a) f(n) ≥ c. g(n)  n (b) f(n) = c. g(n)  n (c) f(n) ≥ c + g(n)  n (d) f(n) = c + g(n)  n (e) f(n) =  g(n)  n.
110.
The q notation is
 (a) Symmetric (b) Reflexive (c) Transitive (d) Both (b) and (c) above (e) (a), (b) and (c) above.

#### Answers

 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.

<< PrevNext >>

#### No comments :

What you think about these Questions and Answers ? Let me know in comments.