Symbol Tables

1)      AVL trees have a faster ________________
A.    Insertion
B.    Deletion
C.    Updation
D.    Retrival

Answer: D

2)      In ______________ tree, the heights of two child subtree of any node differ by at most one
A.    Binary tree
B.    Red black tree
C.    Splay tree
D.    AVL tree

Answer: D

3)      A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as             A  Full binary tree

B  AVL tree             C  Threaded tree             D  Complete binary tree                         Answer A 4)      Number of comparisons required to search a balanced binary search tree of N nodes is A   O(N) B   O(log N) C   O(log2 N)             D   None of these                     Answer A 5)      In a binary balanced tree the difference between the heights of left and right subtrees of every node is A  within ±1 B  ±1 C   0             D  None of these             Answer A 6)      An AVL tree is a A   binary search tree B   binary tree C   complete binary tree             D   None of these             Answer C 7)      In hashing a record is located by using A   a function B   an index C   a key             D   None of these             Answer A 8)      When key values are reals a similar data representation might be produced by using a hashing function with A.    Mod B.     Div C.     Trund D.    LogN Answer: Option C 9)      A hash table with 10 buckets with one slot per bucket is depicted. The symbols, S1 to S7 are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is A.    6 B.     5 C.     4 D.    3             Answer: Option B Explanation : It will be one more than the size of the biggest cluster(which is 4)because,assume a search key hashing onto in 8.By linear probing the nest location for searching is bin 9.Then 0,then 1.If all these resulted in a miss, we try at bin 2 ans stop as it is vacant.This logic may not work if deletion operation is done before the search. 10)  A hash function f defined as f (key) = key mod 7, with linear probing, us used to insert the keys 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6. What will be the location of key 11? A.    3 B.     4 C.     5 D.    6 Answer: Option B Explanation : f(37)=37 mod7 = 2  So,37 will be put in location 2. f(38)= 3.  So,38 will be in third location f(72)= 2  (Collision) With linear probing as the collision resolving strategy, the alternate location for 72 should be the 4 but there is element  11 so 72 will be stored at location 5        11  Hashing for disk files is called: a) external hashing; b) static hashing; c) dynamic hashing;  d) extensible hashing Answer: Option A 12 An advantage of chained hash table over the open addressing scheme is A. Worst case complexity of search operation os less B. Space used is less C. Deletion is easier D. None of these Answer: Option C 13: The average search time of hashing with linear probing will be less if the load factor A. Is far less than one B. Equals one C. Is far greater than one D. None of these Answer: Option A 14 A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is A. (x-1) (x-2)...(x-(m-2))(m-1)/xm-1 B. (x-1) (x-2)...(x-(m-1))(m-1)/xm-1 C. (x-1) (x-2)...(x-(m-2))(m-1)/xm D. (x-1) (x-2)...(x-(m-1))(m-1)/xm Answer: Option A Explanation : Probability for the first record not colliding is x/x. Probability for the second record not colliding is x-1/x. (This is because one place is already occupied, So, favorable number of cases is x-1). Probability for the third record not colliding is x-2/x. Probability for the (m-1)th record not colliding is x-(m-2)/x. Now the next (mth) record is resulting in a collision. Out of the x places, it should has to one of the (m-1) places already, filled. So probability is (m-1)/x. The required probability is (x/x) (x-1/x) (x-2/x) ... (x-(m-2)/x) (m-1/x)   15: A hash table with 100 buckes with one slot per bucket is depicted in Fig. 6.3. The symbols, Sl to S7 are initially entered using a hashing fucntion with linear probing. The maximum number of comparisons needed in searching an intem that is not present is A. 4 B. 5 C. 6 D. 3 Answer: Option B Explanation : It will be one more than the size of the biggest cluster (which is 4) in this case. This is because, assume a search key hashing onto bin 8. By liner probing the next location for searching is bin 9. Then 0, then 1. if all these resulted in a miss, we try at bin 2 and stop as it is vacant. This logic may not work if deletion operation is done before the search. 16: The average search time of hashing, with linear probing will be less if the load factor A. is far less than one B. equals one C. is far greater than one D. none of the above Answer: Option A Explanation : Load factor is the ration of number of records that are currently present and the total number of records that can be present. If the load factor is less, free space will be more. This means proability of collision is less. So, the search time will be less. 17: A hash table can store a maximumof 10 rdcords. Currently there are records in locations 1, 3, 4, 7, 8, 9, 10. The probability of a new record going ono location 2, with a hash function resolving collisions by linear probing is A. 0.6 B. 0.1 C. 0.2 D. 0.5 Answer: Option A Explanation : If the new record hashes onto one of the six locations 7, 8, 9, 10, 1 or 2, the location 2 will receive the new record. THe probability is 6/10 (as 10 is the total possible number of locations). 18: Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8. Which of the following locations will never be probed if a collision occurs at position 4? A. 4 B. 5 C. 8 D. 2 Answer: Option D Explanation : You can varify that the 1st, 3rd, 5th, 7th, ... probes check at location 5. The 2nd, 6th, 10th... probes check at location 4. The rest of the address space will never be probed. 19: A hash table has space for 100 records. What is the probability of collision before the table is 10% full? A. 0.45 B. 0.5 C. 0.3 D. 0.34 (approximately) Answer: Option A Explanation : If there is only one record, then the probability of a collision will be 1/100. If 2, then 2/100 etc., If 9 then 9/100. So, the required probability is, (1+2+3...9)/100 = 0.45. 20: Which of the following statements is true? I. As the number of entries inthe hash table incrases, the number of collisions increases. II. Recursive programs are efficient. III. The worst time complexity of quick sort is O (n2). IV. Binary search implemented using a linked list is efficient. A. I and II B. II and III C. I and IV D. I and III Answer: Option D Recursive programs take more time than the equivalent non-recursive version and so not efficient. This is because of the function call overhead. In binary search, since every time the current list is probed at the middle, random access is preferred. Since linked list does not support random access, binary search implemented this way in inefficient. 21: A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is A. (x-1) (x-2) ... (x-(m-2)) (m-1)/xm-4 B. (x-1) (x-2(... (x-(m-1()(m-1)/xm-1 C. (x-1) (x-2) ... (x-(m-2))(m-1)/xm D. (x-1)(x-2)...(x-(m-1))(m-1)/xm Answer: Option A Explanation : Probability for the first record not colliding is x/x. Probability for the second record not colliding is x-1/x. (This is because one place is already occupied. So, favourbale number of cases is x-1). Probability for the third record not colliding is x-2/x. Probability for the (m-1)th record not colliding is x-(m-2)/x. Now the next (mth) record is resulting in a collision. Out of the x places, it should hast to one of the (m-1) places already, filled. So probability is (m-1)/x. The required probability is (x/x) (x-1/x) (x-2/x) ... (x-(m-2)/x) (m-1/x) 22: If the hashing function is the remainder on division, then clustering is more likely to occur if the storage space is divided into 40 sectors rather than 41. this conclusion is A. more likely to be false B. more likely to be true C. is always false D. none of the above Answer: Option B 23 Hashing collision resolution techniques are A Huffman coding, linear hashing B Bucket addressing, Huffman coding C Chaining, Huffman coding D Chaining, Bucket addressing Answer D 24: The average search time of hashing, with linear probing will be less if the load factor A. is for less than one B. equals one C. is for greater than one D. none of these Answer: Option A 25: Heap allocation is required for languages A. That support recursion B. That support dynamic data structure C. That use dynamic scope rules D. All of above Answer: Option B 26: A list integers is read in, one at a time, and a binary search tree is constructed. Next the tree is traversed would result in a printout which duplicates the original order of the list of integers? A. Preorder B. Postorder C. Inorder D. None of these Answer: Option D 27: A character of the data that binary search uses but the linear search ignores, is A. Order of the list B. Length of the list C. Maximum value in the list D. Minimum value in list Answer: Option A 28: Which of the following need not to be a binary tree ? A. Search tree B. Heap C. AVL-Tree D. B-Tree Answer: Option D 29: What is the best definition of a collision in a hash table? A. Two entries are identical except for their keys. B. Two entries with different data have the exact same key. C. Two entries with different keys have the same exact hash value. D. Two entries with the exact same key have different hash values.          Answer: Option D  30: A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table? A. 256 B. 511 C. 512 D. 1024 E. There is no maximum. Answer: Option C