QUESTION 1 If each key is mapped to a different index in the hash table, this is

Question

QUESTION 1

If each key is mapped to a different index in the hash table, this is called ________ hashing.

quadratic

normal

perfect

linear

QUESTION 2

In a preorder tree traversal, each node is processed ____ its children.

after

instead of

before

relative to the ordinal values of

QUESTION 3

A tree node that has zero children is called a ________ node.

terminal

leaf

swollen

root

QUESTION 4

What is the base case in the following recursive function?

void xMethod(int n)
{
if (n > 0)
{

  cout << (n % 10) << endl;
  xMethod(n / 10);
}
}

n > 0

There is no base case.

n <= 0

n != 0

QUESTION 5

Resolving collisions by sequentially finding the next available location is called ________.

double hashing

bucketed hashing

quadratic probing

linear probing

QUESTION 6

Fill in the code to complete the following function for computing a Fibonacci number.

long fib(long index)

{

if (index == 0) // Base case

return 0;

else if (index == 1) // Base case

return 1;

else // Reduction and recursive calls

return __________________;

}

fib(index - 1)

fib(index + 2) + fib(index + 1)

fib(index - 1) + fib(index - 2)

fib(index - 2)

QUESTION 7

A binary tree gets its name from the fact that it ________.

is made of nodes that have, at most, two children

involves math and a number system that most people do not understand

has leaves that resemble little ones and zeros

is represented in memory using a binary number format

QUESTION 8

The ________ traversal algorithm processes the nodes of a binary tree in alphabetical or numeric order.

unordered

preorder

postorder

inorder

QUESTION 9

In a postorder tree traversal, each node is processed ____ its children.

instead of

relative to the ordinal values of

after

before

QUESTION 10

Which of the following statements is FALSE?

Every recursive function must return a value.

Every recursive function must have a base case or stopping condition.

Infinite recursion can occur if the problem is not reduced in a way that brings it to a base case.

Every recursive call reduces the original problem, bringing it closer to a base case.

QUESTION 11

When is the right subtree of a binary tree processed before the left?

When using a preorder traversal algorithm.

Never. The left always goes before the right in the standard traversal algorithms.

When using a postorder traversal algorithm.

When using an inorder traversal algorithm.

QUESTION 12

In hashing, a collision occurs when:

many elements share the same key

two or more keys map to the same hash value

the requested data is not found

we try to insert new data when the hash table is already full

QUESTION 13

If you have an array of 4,000 sorted data items, about how many comparisons will it take for a binary search to discover that a certain value is not present?

12

It depends on where the value would fall in the array.

4000

64

QUESTION 14

Fill in the code to complete the following method for computing a factorial.

long factorial(int n){

   if (n == 0) // Base case

   return 1;

   else

   return _____________; // Recursive call }

factorial(n) * factorial(n - 1)

n * (n - 1)

n

n * factorial(n - 1)

QUESTION 15

Which of the following statements is true about this recursive function?

long f(int n)

{

return n * f(n - 1);

}

Invoking f(1) returns 1.

The function runs infinitely and causes a crash.

This function works perfectly for all n > 0.

Invoking f(0) returns 0.

QUESTION 16

A hashing function ________.

maps a key to an index in the hash table

resolves conflicts between data with identical hash codes

is usually implemented recursively

stores an element in a hash table

QUESTION 17

Rather than finding a new location for colliding data, a(n) ________ scheme stores the data in linked lists.

double hashing

open addressing

linear probing

bucketing/separate chaining

QUESTION 18

In the following recursive function, what is the base case?

int xFunc(int n)

{

if (n == 1) return 1;

else return n + xFunc(n - 1);

}

n is greater than 1.

n is 1.

There is no base case.

n is less than 1.

QUESTION 19

Suppose a list is {2, 9, 5, 4, 8, 1}. After the first pass of bubble sort, the list becomes:

2, 5, 4, 8, 1, 9

2, 9, 5, 4, 8, 1

2, 9, 5, 4, 1, 8

2, 1, 5, 4, 8, 9

2, 5, 9, 4, 8, 1

QUESTION 20

A binary tree whose left and right subtrees are similar in height is said to be ________.

abstract

fictitious

balanced

inefficient

quadratic

normal

perfect

linear

Explanation / Answer

If you post more than 1 uestion, as per chegg guidelines I have to solve only first question.

Ques 1. Answer : (c) Perfect Hashing

Perfect Hashing is a type of hashing in whichwe map the set of element to another set of integers. As we map it to another set of integers, we can say that each key is mapped to a different index in the hash table.

Ques 2. Answer : (b) before

The preorder traversal algorithm is

Function preorder(root)

BEGIN

                // process current node before children

                Print( root.data )

                // recursively call the function to process left child

                Preorder( root.left )

                // recursively call the function to process right child

                Preorder( root.right )

END

Ques 3. Answer : (b) leaf

A leaf node is a node which has no children.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.