Cis 120 Final

Front 1

In an ordered linked list, the search algorithm is somewhat improved because

Back 1

the list is sorted

Front 2

What should be used to traverse a list

Back 2

a reference variable not in the list

Front 3

What is the time complexity to print a linked list

Back 3

O(n^2)

Front 4

The algorithms to implement the operation of find, insert, and remove are

Back 4

not identical for sorted and unsorted lists

Front 5

the data type of each list

Back 5

depends on the specific application

Front 6

What is the time complexity to insert at the end of an array based linked list

Back 6

O(1)

Front 7

When using one reference variable to insert an item into a linked list

Back 7

the order of the sequence of events matters

Front 8

retrieving the information of the first node

Back 8

is a basoc operation of the list ADT

Front 9

Searching through a linked list or inserting an item in a linked list

Back 9

requires a traversal of the list

Front 10

a linked list is

Back 10

a collection of nodes

Front 11

the address of the first node in a linked list is stored in

Back 11

a separate location called the list

Front 12

In general, the list reference variable, which points to the first node

Back 12

should be used in the traversal of a linked list

Front 13

What is the time complexity to print a linked list

Back 13

O(n)

Front 14

Which of the following should be used to traverse a list

Back 14

the head of the list

Front 15

in a linked list

Back 15

every node has a successor

Front 16

a header node

Back 16

contains actual list information

Front 17

In the Dale textbook, when implementing a circular lists

Back 17

we can make use of the same nodes class, LLObjectNode, as we did when we implemented our unsorted, sorted, and indexed lists

Front 18

In a circular linked list

Back 18

every node has a successor

Front 19

the getNext method is more complicated for our circular list

Back 19

than it is for its linear counterpart

Front 20

In the Dale textbook's doubly linked list, the nodes are linked in

Back 20

two directions, front and back

Front 21

A circular node is a placeholder node

Back 21

at the end of a list, used to simplify list processing

Front 22

The header node contains

Back 22

information for the first element in the list

Front 23

In a diagram of a binary tree

Back 23

each node in the binary tree is represented as a circle and the circle is labeled by the node

Front 24

the term for the maximum level of the binary tree

Back 24

height

Front 25

In preorder traversal

Back 25

you start at the top of the tree and move down the tree using the values of the nodes to determine the next move

Front 26

In postorder traversal

Back 26

you start at at the lowest node on the left side and work your way out

Front 27

What is the level of the children of the root node of a binary tree

Back 27

1

Front 28

In a binary search tree the key in the root node is larger than every key in the left subtree

Back 28

is smaller than every key in the right subtree

Front 29

If a binary tree has two subtrees, left and right, which of the following must be true about left and right

Back 29

left and right are binary trees

Front 30

Each node in a binary tree contains

Back 30

data and a link to the left child and a link to the right child

Front 31

If T is a binary search tree with n nodes, where n>0

Back 31

the average number of nodes visited in a search of T is O(log 2 n)

Front 32

In a binary search tree, the key in the root node

Back 32

is larger than every key in the left subtree and smaller than every key in the right subtree

Front 33

In a binary search tree, the average number of nodes visited in a search of T

Back 33

is approximately O(log 2 n)

Front 34

For a heap, the order says that the child can be

Back 34

larger than both of the parents

Front 35

In a priority queue, we access the element

Back 35

that has the highest priority

Front 36

There are many ways

Back 36

to implement a priority queue

Front 37

A heap is based on a

Back 37

complete binary search tree

Front 38

A precondition of the reheapDown operation

Back 38

is that the root of the tree is empty

Front 39

A heap must exhibit two proporties, these are

Back 39

shape and order

Front 40

The insertion algorithm sorts the lists by

Back 40

moving each element to its proper place

Front 41

A selection sort can be implemented by selecting the largest element in the (unsorted portion of the) list and

Back 41

moving it to the bottom of the list

Front 42

Selection sort can be applied to

Back 42

linked lists and array based lists

Front 43

Heap sort overcomes the worst case for

Back 43

quick sort

Front 44

Merge sort divides the list into

Back 44

2 sublist of nearly equal size

Front 45

Quick sort does use a

Back 45

splitValue

Front 46

A priority queues may be implemented

Back 46

as a heap

Front 47

Suppose that L is a list of n elements, where n > 0. Let W(n) denote the number of key comparisons in the worst case of merge sort. Which of the following is true?

Back 47

W(n) = O(n Log2n)

Front 48

A selection sort can also be implemented by selecting the

Back 48

largest element in the (unsorted position of the) list and moving it to the bottom of the list

Front 49

Heap sort, for array-based lists

Back 49

is of the order O(n log2n) even in the worst case

Front 50

It can be shown that the average number of key comparisons for insertion sort is

Back 50

O(n2)

Front 51

The selection sort algorithm repeatedly moves the smallest element from the unsorted list

Back 51

to the beginning of the unsorted list

Front 52

If the list above were sorted with selection sort, which two elements would be swapped first?

Back 52

5 and 16

Front 53

In quick sort, the list is partitioned into two sublists by selecting a pivot, and the two sublists are then sorted and combined into one list in such a way

Back 53

so that the combined list is sorted

Front 54

A quick sort uses this for implementation

Back 54

recursion

Front 55

A heap is an array 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

Back 55

2k+1 and 2k+2

Front 56

The selection sort algorithm sorts a list by selecting the smallest element in the (unsorted portion of the) list

Back 56

and then moving this smallest element to the top of the unsorted list

Front 57

The quick sort algorithm uses the

Back 57

divide-and-conquer technique to sort a list

Front 58

The lower bound on comparison-based algorithm is

Back 58

O(n log2n)

Front 59

In quick sort, the average case for the number of swaps

Back 59

is O(n log2n)

Front 60

A selection sort can be applied to

Back 60

linked list

Front 61

Merge sort

Back 61

does not use a pivot

Front 62

Suppose that L is a list of n elements, where n > 0. Let A(n) denote the number of key comparisons in the average case of merge sort. Which is the following is true

Back 62

A(n) = O(n log2n)

Front 63

A merge sort algorithm partitions the list into two sublists of roughly equal size, sorts the sublists

Back 63

and then combines the sorted sublists into one sorted list

Front 64

The worst case for the number of comparisons in quick sort is

Back 64

O(n2)

Front 65

The selection sort algorithm sorts a list by selecting the smallest element in the (unsorted position of the) list

Back 65

and then moving this smallest element to the top of the unsorted list

Front 66

In the merge sort algorithm

Back 66

most of the sorting is done in the merging and sorting sublists

Front 67

Priority queues may be implemented as

Back 67

a heap