The time complexity for the recursive Fibnacci algorithm in the text is ________.

O(2^n)

O(logn)

O(nlogn)

O(n^2)

The worst-time complexity for selection sort is ________.

O(n*n)

O(n)

O(nlong)

O(1)

O(logn)

Estimating algorithm efficiency is ________.

to estimate their execution time

to estimate their growth function

to measure their actual execution time

The worst-time complexity for linear search is ________.

O(n*n)

O(1)

O(logn)

O(n)

O(nlong)

________ approach is the process of solving subproblems, then combining the solutions of the subproblems to obtain an overall solution. This naturally leads to a recursive solution. However, it would be inefficient to use recursion, because the subproblems overlap. The key idea behind dynamic programming is to solve each subproblem only once and store the results for subproblems for later use to avoid redundant computing of the subproblems.

Backtracking

Divide-and-conquer

Dynamic programming

Brutal-force

To remove the root, you need to start a process by first placing ________ to the place of the root and move it down to maintain the heap property.

the last node in the heap

the larger child of the root

one of the root's children

the smaller child of the root

The best-time complexity for bubble sort is ________.

O(n)

O(1)

O(nlogn)

O(n*n)

O(logn)

Which of the following statements are true?

A heap is a complete binary tree.

A binary tree is complete if every level of the tree is full except that the last level may not be full and all the leaves on the last level are placed left-most.

A heap is a full binary tree.

Each node is greater than or equal to any of its children.

The most efficient algorithm for sorting integer keys is ________.

quick sort

merge sort

radix sort

heap sort

A heap is represented using an array. Is the array {64 42 59 32 39 44} a heap?

No

Yes

Which of the following operations are supported by a list?

Delete an element from this list.

Find whether an element is in this list.

Find how many elements are in this list.

Insert a new element to this list.

Retrieve an element from this list.

Suppose you want to store students and perform the operations to insert and delete students. Which data structure is best for this application?

A stack

An array list

A queue

A linked list

Which of the following statements are true?

MyLinkedList is implemented using a linked structure.

MyArrayList is implemented using an array. The array is dynamically created. If the capacity of the array is exceeded, create a new larger array and copy all the elements from the current array to the new array.

MyArrayList and MyLinkedList are two concrete implementations of MyList.

MyAbstractList partially implements MyList.

A linked structure consists of nodes. Each node is dynamically created to hold an element. All the nodes are linked together to form a list.

Suppose list1 is a MyArrayList and list2 is a MyLinkedList. Both contains 1 million double values. Analyze the following code: A: for (int i = 0; i < list1.size(); i++) sum += list1.get(i); B: for (int i = 0; i < list2.size(); i++) sum += list2.get(i);

Code fragment A is more efficient that code fragment B.

Code fragment B is more efficient that code fragment A.

Code fragment A is as efficient as code fragment B.

Suppose list1 is an MyArrayList and list2 is a MyLinkedList. Both contains 1 million double values. Analyze the following code: A: while (list1.size() > 0) list1.remove(size() - 1); B: while (list2.size() > 0) list2.remove(size() - 1);

Code fragment A runs faster than code fragment B.

Code fragment B runs faster than code fragment A.

Code fragment A runs as fast as code fragment B.

A Huffman tree is constructed using the ________ algorithm.

dynamic programming

greedy

back-tracking

divide-and-conquer

In the implementation of BST, which of the following are true?

Node is defined as a static inner class inside BST because it does not reference any instance data fields in BST.

Node has a property named left that links to the left subtree and a property named right that links to the right subtree and a property named right.

Node is defined as an inner class inside BST.

BST contains a property named root. If tree is empty, root is null.

A ________ (with no duplicate elements) has the property that for every node in the tree the value of any node in its left subtree is less than the value of the node and the value of any node in its right subtree is greater than the value of the node.

binary tree

binary search tree

list

linked list

The ________ of a node is the length of the path from the root to the node.

height

length

depth

degree

The ________ of a path is the number of the edges in the path.

depth

ag this Question

Question 185 pts

length

degree

height