CS STUDY

The following figure shows the merge sort tree for sorting 8 elements. When sorting n elements, the asymptotically tight bound for the height of the merge sort tree is _____

O(logn)

O(nlogn)

O(n)

O(n^2)

All operations of binary search tree starts at the _____

internal nodes

leaves

root

sibling

Although not getting into the details, we have mentioned in the class several balanced trees, which of the following are not one of them?

AVL trees

2-4 trees

binary search trees

red-black trees

The insertion of an element into a binary search tree starts with an _____

deletion in the tree

search in the tree

addition of a second root

restructure of the tree

The ____ sort algorithm cannot be easily implemented as an in-place sorting algorithm

merge

insertion

heap

quick

The _____ traversal of a binary search tree renders all elements in sorted order of the keys

eulur-order

pre-order

post-order

in-order

A divide - and - conquer algorithm is always a ____ algorithm.

mathematical

recursive

tree

sorting

Worst case performance of the quick sort algorithm happens _________.

only when the pivot is always either the minimum or maximum value in the sequence to be sorted.

only when the pivot is always the average of all the values in the sequence to be sorted.

only when the pivot is always the minimum value in the sequence to be sorted.

only when the pivot is always the maximum value in the sequence to be sorted.

Because of the ______, the element with the smallest key can always be found at the root of a minHeap.

both heap order and complete binary tree properties

complete binary tree property

either heap order or complete binary tree property

heap order property

Both the merge sort and quick sort are _______ algorithms.

parallel

mathematical

sequential

divide-and-conquer

The best asymptotically tight bound for insertion sort is _________

O(n^2)

O(logn)

O(nlogn)

O(n)

In general, hash functions consist of two components, they are ______

hash codes and compression functions

comparison and calculation functions

mapping and unmapping functions

conversion and reduction functions

Because of the _____, a heap can be efficiently represented by an array-based sequence

complete binary tree property

either heap order or complete binary tree property

heap order property

both heap order and complete binary tree properties

There are three steps in divide-and-conquer algorithms. They are:

combine, divide, and conquer

conquer, combine, and divide

divide, combine, and conquer

divide, conquer, and combine

Which of the following implementation of hash table allows a load factor greater than 1

double hashing

drop lists

seperate chaining

linear probing

If we use a heap to implement the priority queue ADT and use the priority queue to implement the priority queue sort algorithm, then the resulting algorithm is _______ sort.

heap

selection

insertion

quick

the asymptotically tight bound for worse case performance in comparison based sorting algorithms cannot be better than ______

O(n^2)

O(logn)

O(nlogn)

O(n)