Data structures AND algorithms

PLEASE BE CLEARLY

THANKS

Q1

In a disjoint set data structure, the union operation is done using ranks. That is, the lower rank is added to the larger one. If equal, the right is added to the left. For example, in union(1, 2), if the ranks of the two sets are equal, the set of 2 is added to 1. Accordingly, after the elements 1, 2, 3, 4, 5, 6, 7, 8, 9 are set with make-set, union(1,2), union(3,4), union(3,5), union( What is the height of the tree resulting from operations 1,7), union(3,6), union(8,9), union(1,8), union(3,1)? A-1 B-2 C-3 D-4 E-5

Q2

What value does the dequeue() operation return after the operations enqueue(5), enqueue(3), dequeue(), enqueue(2), enqueue(8) are performed on an initially empty queue? A-5 B-3 C-2 D-8

Q3

What is the runtime of the following code in O (big-oh) notation?

A---O(n) B----O(n^2) C---O(n^3)

Q4

It is desired to add a few new data to a sequential data. Which sorting algorithm is expected to spend less time for this? Assume that the data is stored in an array. A-insertion sort B-selection sort C-merge sort D-quick sort

Q5

Which of the following is true about the tree?

A- The depth of the "cs252/" node is 1. B- The height of the "cs252/" node is 3. C- The height of the "papers/" node is 2. D- The "papers/" node has a depth of 4. E- The height of the "buylow" node is 0. F- The height of the "buylow" node is -1. G- This tree is balanced.

Q6

What value is returned if pop() is performed after push(5), push(3), pop(), push(2), push(8), pop(), push(9) operations on an empty stack? A-5 B-3 C-2 D-8 E-9

Q7

In insertion sort, if the positions of the elements to be inserted are found using binay search, the algorithm sorts n elements in O(n log n) time.

A- Correct B- Wrong

Q8

In a hash structure where the hash function defined as h(i) = (i) mod 11 is used and chaining is used for the resolution of collisions, the key values are 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 18 elements are added. What is the load factor of this hash function? A- 1 B-

Q9

Which of the following is generally a better choice (for fewer collisions) for hash table size? A- 2^n, n small positive integer B- prime 2^n-a, a and n are small positive integers C- prime 2^n-a, n is small but a is a large positive number D- 3^n, n is a small positive number

Q10

When using BALANCED binary search tree (eg AVL tree) in buckets, what is the time to find an element in the hash table in the WORST case in big O notation? (a: load factor, n: number of elements) * A- O(1) B- O( 1+ log a) C- O(1 + a) D- O(1 + log n) E- O(n)

Q11

If merge sort is used as a subroutine in radix sort, how long would it take at worst to sort n numbers with d digits? A- O(d nlog n) B- O(d n^2) C - O(dn) D- O(n)

Q12

An airline company wants to control the takeoff and landing of aircraft. These events come with a timestamp and basically two operations are performed for these events: 1) Add a future event with a timestamp 2) Extract the closest event in time These two operations are the most efficient. Which of the following can be done?

A-stack B- queue C-list D- min-heap E- binary search tree

Q13

When is it time to find an element in the hash table in the IDEAL case in big O notation? A- O(1) B- O(n) C - O(log n)

Q14

When using BALANCED binary search tree in buckets, what is the time to find an element in the hash table in AVERAGE-case, big O notation? (a: load factor, n: number of elements) * A- O(1) B- O(1 + log a) C- O(1 + a) D- O(1 + log n) E- O(n)

Q15

The tree is balanced when 30, 40, 24, 58, 48, 26, 11, 13 elements are added to an empty binary search tree, respectively. A- Correct B- Wrong

Q16

After insert(5), insert(4), insert(7), insert(2), removeMin(), insert(3), insert(1), operations in an empty min-priority queue, removeMin() returns which value does it? A- 1 B-2 C-3 D-7 E-5

Q17

In a hash structure where the hash function defined as h(i) = (i) mod 11 is used and chaning is used for the resolution of collisions, the key values are 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 18 elements are added. What is the length of the longest chain (linked list) (including the first element)? A- 1 B-2 C-3 D- 4

Q18

A tree is a graph without a cycle. A- Correct B- Wrong

Q19

What will be the height of the tree when 30, 40, 24, 58, 48, 26, 11, 13 elements are added respectively to an empty binary search tree? A- 1 B-2 C-3 D- 4

Q20

Which of the following algorithms are "in place" in standard implementations? A- insertion sort B- selection sort C - quick sort D- merge sort e-heap sort

Q21

The runtime of comparison-based sorting algorithms is (nlogn). A- Correct B- Wrong

/** Returns the number of times second array stores sum of prefix sums from first. */ public static int examples(int[] first, int[] second) { // assume equal-length arrays int n = first.length, count = 0; for (int i=0; i<>