Deck 10: Sorting Algorithms

Question 1

A sequential search assumes that the data is in a particular order.

Answer 1

False

Question 2

A binary search is very fast for array-based lists.

Answer 2

True

Question 3

In a selection sort, the first step we locate the smallest item in the entire list, the second step we locate the smallest item in the list starting from the second element in the list, and so on.

Answer 3

True

Question 4

Initially, in a selection sort we consider that the entire list is unsorted.

Question 5

In a selection sort, we find the largest item in the list first.

Question 6

When sorting a list, the smallest item must be moved to position 0.

Question 7

Selection sort involves the following steps in the unsorted portion of the list: find the location of the smallest element and move the smallest element to the beginning of the unsorted list.

Question 8

A sorting algorithm makes key comparisons and also moves the data.

Question 9

Insertion sort cannot be applied to linked lists.

Question 10

If the list is stored in a linked list, we can traverse the list in only one direction starting at the first node because the links are only in one direction.

Question 11

The modified insertion sort introduced in 1959 by D. E. Shell is known as the diminishing return sort.

Question 12

In quicksort, the list is partitioned in such a way that combining the sorted lowerSublist and upperSublist is trivial.

Question 13

Mergesort uses the divide-and-conquer technique to sort a list.

Question 14

Mergesort and quicksort are similar in how they partition the list.

Question 15

Once the sublists are sorted, the next step in mergesort is to merge the sorted sublists.

Question 16

Sorted sublists are merged into a sorted list by comparing the elements of the sublists, and then adjusting the references of the nodes with the smaller info.

Question 17

In the mergesort presented in this chapter, every time we move a node to the merged list, we advance either first1 or first2 to the previous node.

Question 18

In C++, the array index starts at 0.

Question 19

In heapsort, only the elements at position 2k + 1 are accessed frequently.

Question 20

When converting the subtree into a heap, if the root node of the subtree is larger than the larger child, we swap the root node with the larger child.

Question 21

After inserting the new element in the heap, the list might no longer be a heap.

Question 22

When inserting an element in the priority queue, restoring the heap might result in moving the new entry to the root node.

Question 23

Assuming a priority queue is implemented as a stack, to remove the first element of the priority queue, we copy the last element of the list into the first array position, reduce the length of the list by 1, and restore the heap in the list.

Question 24

In a(n) ____, a list is sorted by selecting elements in the list, one at a time, and moving them to their proper positions.

A) quicksort
B) insertion sort
C) selection sort
D) bubble sort

Question 25

A(n) ____ finds the location of the smallest element in the unsorted portion of the list and moves it to the top of the unsorted portion of the list.

A) selection sort algorithm
B) quicksort algorithm
C) insertion sort algorithm
D) bubble sort algorithm

Question 26

With selection sort, we can keep track of the unsorted portion of the list and repeat the steps involved with sorting with the help of a ____ loop.

A) when
B) for
C) while
D) do

Question 27

____ sort sorts the list by moving each element to its proper place.

A) Quick
B) Bubble
C) Selection
D) Insertion

Question 28

If the list is stored in an array, we can traverse the list in either direction using an ____.

A) interface variable
B) increment variable
C) index variable
D) iterator variable

Question 29

In ____, the elements of the list are viewed as sublists at a particular distance.

A) quicksort
B) Shellsort
C) bubble sort
D) insertion sort

Question 30

In quicksort, all the sorting work is done in ____ the list.

A) partitioning
B) combining
C) duplicating
D) replicating

Question 31

Quicksort first selects an element in the list, called the ____, and then partitions the list so that the elements in one sublist are less than pivot.

A) primate
B) key
C) pivot
D) index

Question 32

We use ____ to implement mergesort.

A) recursion
B) iteration
C) revision
D) succession

Question 33

To divide the list into two sublists, we need to find the ____ node of the list.

A) first
B) middle
C) last
D) largest

Question 34

In mergesort, most of the sorting work is done in ____.

A) dividing the lists
B) sorting the sublists
C) calculating the division points
D) merging the sorted sublists

Question 35

In mergesort, all the comparisons are made in the method____, which merges two sorted sublists.

A) sortList
B) divideList
C) mergeList
D) insertList

Question 36

On average, quicksort is of the order ____.

A) O(nlog₂n)
B) O(n)
C) O(n²)
D) O(1)

Question 37

The____ for array-based lists is of order O(n log2n) even in the worst case, therefore overcoming the worst case of the quicksort.

A) mergesort
B) ShellSort
C) holdsort
D) heapsort

Question 38

A ____ is a list in which each element contains a key, such that the key in the element at position k in the list is at least as large as the key in the element at position 2k + 1 (if it exists) and 2k + 2 (if it exists).

A) hash table
B) hemp
C) heap
D) pile

Question 39

The first step in the heapsort of this chapter is to convert the list into a heap, called ____.

A) newHeap
B) buildHeap
C) convertHeap
D) addHeap

Question 40

In heapsort, after we convert the array into a heap, the ____ phase begins.

A) division
B) merging
C) inserting
D) sorting

Question 41

In a heap, the ____ is the largest element of the tree

A) root node
B) base node
C) top node
D) low node

Question 42

In the average case of quicksort, the number of key comparisons is ____.

A) O(n)
B) 1.39nlog₂n + O(n)
C) 2.39logn + O(n)
D) 1.39nlog₂n + O(2n)

Question 43

In a ____ queue, customers or jobs with higher priorities are pushed to the front of the queue.

A) structured
B) divided
C) priority
D) hold

Question 44

In a heap, the ____ element of the list is always the first element of the list.

A) smallest
B) largest
C) most important
D) least important

Question 45

To ensure that the largest element of the priority queue is always the first element of the queue, we can implement priority queues as ____.

A) piles
B) stacks
C) trees
D) heaps

Question 46

Inserting the new element in the first available position in the list ensures that the array holding the list is a complete ____.

A) binary tree
B) heap
C) selection tree
D) forest

Question 47

Assuming the priority queue is implemented as a heap, the first step is to insert the new element in the ____ available position in the list.

A) smallest
B) largest
C) first
D) last