Question

Question 1 5 pts A binary heap's structure is an AVL tree a complete binary tree a particular case of binary search tree a sparse tree Question 2 5 pts When using a hash table with quadratic probing, and the table size is prime, then a new element can always be inserted if the table is at least half empty the table is full the table is at least half full the table is larger than any data value

C++

Answer 1

1) Answer is 2nd option - a complete binary tree.

Binary heap is data structure which is in the form of a binary tree. These binary heaps are the common way in implementing priority queue data structures. These are of the form in complete binary tree, where value of the parent node is greaterthan its left child and lessthan its right child respectively.

2) Answer is 1st option - atleast half empty.

​​​​​​Quadratic probing is used to reduce number of collisions in hash table. Quadratic coefficients are added into hashtable if the space in hash table is empty. If the size if table is prime, then the value is added if the table is atmost half full. It means that the table must be atleast half empty.

​​​​​​3) Answer is 4th option - nlogn.

Comparison based sorting algorithms are bubble sort, selection sort, merge sort, heap sort and quick sort.

Worst case time complexity are

Bubble sort - n^2

Selection sort - n^2

Merge sort - nlogn

Heap sort - nlogn

Quick sort - n^2.

So, nlogn is the best in worst time complexity in sorting. But nlogn is not present in options. So n^2 is the best worst case.

4) Answer is 3rd option - O( N+M ).

Rehashing occurs if the size of the hash table becomes full. Time complexity of hash table is N for the size, N. If new hashing table of size M is used , then its time complexity is M. So, time complexity of using N+M size is, O(N+M).

-----------

Comment if u have any doubt and upvote if u like it.

Thank you.