# 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.