Need Answers ASAP. Thanks!

Question 1

One of the ways an abstract data type can be implemented in C++ is by using a(n) _____.

array of nodes

friend function

class

virtual method

Question 2

(TCO 1) These operations are present in most of the ADTs: _____.

push, pop, top

inorder traversal, postorder traversal

sort, remover all, find duplicates

insert, remove, search

Question 3

(TCO 1) Which behavior is not represented in a bag?

Report the number of items in the bag.

Report if the bag is empty.

Reorder the bag.

Add an item to the bag.

Question 4

(TCO 1) When deleting an entry from an array-based implementation of the ADT list at the end of the list _____.

all of the previous elements must be shifted toward the front of the array

no shift is necessary

only one element is shifted toward the end of the array to close the gap

only one element is shifted toward the beginning of the array to close the gap

Question 5

(TCO 2) In the node object of a linked list, the next field contains _____.

the data portion of the node

a pointer to the beginning of the list

a pointer to another node

an int value

Question 6

(TCO 2) _____ can be traversed backward.

Doubly linked lists

Heaps

Stacks

Binary search trees

Question 7

(TCO 2) In a doubly linked list, the running time of accessing the first node is _____.

O(1)

O(n)

O(log n)

O(n log n)

Question 8

(TCO 2) Including a tail pointer to a linked implementation of a list makes which functionality more efficient?

Adding a node to the end of a list

Searching for a node on the list

Removing a node from the list

All of the above

Question 9

(TCO 3) If the numbers 9, 17, 21, 34 are inserted, in that order, in a stack, which will be the first element to be removed?

9

17

21

34

Question 10

(TCO 3) What is the stack operation implemented in the following function? The variable top represents the stack top. int operation() { return list[top-1]; }

peek

getLength

search

clear

Question 11

(TCO 3) Consider the following program fragment. Stack s; s.push(1); s.push(2); s.push(3); s.push(4); cout << s.peek() << endl; What is the value displayed by the cout statement?

1

2

3

4

Question 12

(TCO 3) A queue can be implemented using a(n) _____.

stack

array

linked list

B and C

Question 13

(TCO 4) Which of the following functions has a constant growth rate?

n

n2

n log n

1

Question 14

(TCO 4) Algorithms can be described using _____.

pseudo-code

assignment and arithmetic operations

loops and decision statements

All of the above

Question 15

(TCO 4) The running time of an algorithm is _____.

the time, in milliseconds, it takes to complete its execution

the running time of its implementation

the maximum number of basic operations executed by the algorithm (over all inputs of size N)

the number of steps given in its description

Question 16

(TCO 4) The running time of an algorithm to find the maximum of a collection of n numbers stored in an array is _____.

O(n2)

O(n log n)

O(n)

O(1)

Question 17

(TCO 5) Which of the following is a search algorithm or technique?

Quadratic search

Binary search

Fibonacci sequence

Divide and conquer

Question 18

(TCO 5) In a binary search, the main loop executes, approximately, _____. (Note: Below, n is the number of elements in the array.)

log(n) times

once

n times

1,000 times

Question 19

(TCO 5) There are two basic types of hashing, _____.

linear probing and random probing

searching and sorting

open addressing and separate chaining

dynamic and static

Question 20

(TCO 5) In separate chaining, the keys that map to the same hash value are stored in a(n) _____.

class

vector

array

linked list