CS301 Quiz 2 by Junaid

Q1. If unions are done by weight (size), the depth of any element is never greater then

1. n log2 n
2. log 3n
3. log n*n

Q2. Which of the following is NOT true regarding the skip list

1. Each list Si contains the special keys + infinity and – Infinity
2. List SO contains the keys of S in non-decreasing

order c. List Sh contains only then n special keys d. Each list is a subsequence of the previous one

Q3. Which of the following is NOT an open addressing technique to resolve collisions

1. Quadratic probing
2. Double hashing
3. Cubic probing
4. Linear probing

Q4. Which of the following possible operations are performed on Table ADT?

1. Insert, Remove
2. Find, Remove
3. Insert, Find
4. Insert, Find, Remove

Q5. Binary search can be categorized into which of the following?

1. Greedy algorithm
2. Dynamic

programming c. Divide and conquer d. Brute force technique

6. Suppose there is an image of 7*7 now we will have matrix of rows and

colum ns. a. 7.7 b. 49.49 c. 100.100 d. 8.8 a. log2 n

Q7. Which of the following is NOT true regarding the maze generation?

1. Randomly remove walls until the entrance and exit cells are in the same set
2. Removing a wall is the same as doing a union operation
3. Do not remove a randomly chosen wall if the cell it separates are
4. None of the given
5. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty. Which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

1. 8, _, _, _, _, _, 10
2. 1, _, _, _, _, _, 3
3. 1, 10, 8, _, _, _, 3
4. 1, 8, 10, _, _, _, 3

Q9. Suppose a hash function returns 6 for the given value. At which index of array the value will be saved?

1. 0
2. 5
3. 6
4. 7

Q10. If a hash function returns 4 for more than one value, this condition is called

1. Mergin

g b. Collision c. Mapping d. Clustering

Q11. During the union by size method, all the array element initialized to -1 shows;

1. Tree is complete
2. Initial condition of tree
3. Every tree has two elements each.
4. None of the

given

Q12. What is a skip list?

1. A linked list with size value in nodes
2. A linked list that allows slower search within an ordered sequence
3. A linked list that allows faster search within an ordered sequence
4. A tree which is in the form of linked list

Q12. Which of the following is true regarding the maze generation?

1. Randomly remove walls until the entrance and exit cells are in the same set
2. Removing a wall is the same as doing a union operation
3. Do not remove a randomly chosen wall if the cell it separates are
4. All of the given

Q13. What is the best definition of a collision in a hash table?

1. Two entries are identical except for their keys
2. Two entries with different data have the exact same key
3. Two entries with different keys have the same exact has value.
4. Two entries with the exact same key have different hash values.
5. Suppose there is an image segmented into pixels. Each pixel has neighbor(s).

1. 0
2. 4

c.

d. 16 15The array in binary search in sub divided a. Once b. Twice c. N time d. Until a sublist is no more divisible

Q16. What is the time complexity of binary search with iteration?

1. O(nlogn)
2. O(n2)
3. O(n)

search/

Q17. Which of the following is NOT an implementation of Table ADT?

1. Sorted Sequential

Array b. Stack c. Linked List d. Skip List

Q18. In 1990, Bill Pugh proposed an enhancement on linked lists and the new data structure was termed as

1. Linked list
2. B-
3. O(logn)