. Choose the correct answers. Each one carries 2 points (10 Points). 1) Which of
ID: 3916891 • Letter: #
Question
. Choose the correct answers. Each one carries 2 points (10 Points). 1) Which of the following is correct recurrence for worst case of Binary Search? a) T(n) = 2T(n/2) + 0(1) and T(1)-T(0)-0(1) b) T(n) T(n-1)+ 0(1) and T(1)-T(O)-0(1) c) T(n)-T(n/2)+ 0(1) and T(1) - T(O) 0(1) d) T(n) T(n-2)+ 0(1) and T(1)-T(O) 0(1) A hash table of length 10 uses open addressing with hash function h(kj-k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below. 2) 242 23 34 52 46 8 9 which the key values could have Which one of the following choices gives a possible order in been inserted in the table? a) 46, 42, 34, 52, 23, 33 b) 34, 42, 23, 52, 33, 46 c) 46, 34, 42, 23, 52, 33 d) 42, 46, 33, 23, 34, 52 How many different insertion sequences of the key values using the same hash function and linear probing will result in the below hash table ? 3) 0 2 3 42 34 52 46 5 6 7 8Explanation / Answer
1)c)
Because in a binary search first key is compared with middle element if not found then left half /right half is searched using same procedure.
2)c)
Because 42,23,34 appear befre 52,33 and 46 before 33
3)c)
Beacuse 46 can be in 5 places whereas 42,23,34 can be arranged in 3! ways so 5*3!=30
4)a)
Bcause when arr[mid]<key then mid+1 and high should be searched
when arr[mid]>key then low and mid-1 should be searched.
5)a)
The array is searched till its length-1 whereas in option3 if no element is found till the end of array index out of range exception will come beacuse i<=size is used so for arr size 5 a[5]==data gives error.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.