adplus-dvertising
frame-decoration

Question

Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values:

1. Choose an i uniformly at random from 1..... n;
2. If A[i] = x then Stop else Goto 1;

Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates ?

a.

n

b.

n - 1

c.

2n

d.

n/2

Answer: (a).n

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values: 1. Choose an i uniformly at random from 1........

Similar Questions

Discover Related MCQs

Q. The running time of the following algorithm Procedure A(n)

If n < = 2 return (1)
else return (A(Image not present√nImage not present));

is best described by :

Q. A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

Q. Consider the following C function.

float f(float x, int y)
{
float p, s; int i;
for (s=1, p=1, i=1; i < y; i ++)
{
p*= x/i;
s+=p;
}
return s;
}

For large values of y, the return value of the function f best approximates

Q. Assume the following C variable declaration

int *A [10], B[10][10]; 

Of the following expressions:

I A[2]
II A[2][3]
III B[1]
IV B[2][3]

which will not give compile-time errors if used as left hand sides of assignment statements in a C program?

Q. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree ?

Q. Consider the following three claims

1. (n + k)^m = Θ(n^m), where k and m are constants
2. 2^(n + 1) = O(2^n)
3. 2^(2n + 1) = O(2^n)

Which of these claims are correct ?

Q. The unusual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where and element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

Q. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

Q. Which of the following statements is FALSE ?

Q. How many perfect matchings are there in a complete graph of 6 vertices ?

Q. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

-Delection of the smallest element
-Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

Q. Let S be a stack of size n ≥ 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥ 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

Q. The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
int i = 10;
print(x + 10);
i = 200;
j = 20;
print(x);
}
main()
{
P(i + j);
}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

Q. The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
int i = 10;
print(x + 10);
i = 200;
j = 20;
print(x);
}
main()
{
P(i + j);
}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are :

Q. Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.

Class P
{
void f(int i)
{
print(i);
}
}

Class Q subclass of P
{
void f(int i)
{
print(2*i);
}
}

Now consider the following program fragment:

P x = new Q();
Q y = new Q();
P z = new Q();
x.f(1); ((P)y).f(1); z.f(1);

Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be

Q. In the following C program fragment, j, k n and TwoLog_n are interger variables, and A is an array of integers. The variable n is initialized to an integer ≥ 3, and TwoLog_n is initialized to the value of 2*⌈log2(n)⌉

for (k = 3; k < = n; k++)
A[k] = 0;
for (k = 2; k < = TwoLog_n; k++)
for (j = k + 1; j < = n; j++)
A[j] = A[j] || (j % k);
for (j = 3; j < = n; j++)
if (!A[j]) printf("%d", j);

The set of numbers printed by this program fragment is

Q. Consider the C program shown below.

#define print(x) printf("%d ", x)
int x;
void Q(int z)
{
z += x;
print(z);
}
void P(int *y)
{
int x = *y + 2;
Q(x);
*y = x - 1;
print(x);
}
main(void)
{
x = 5;
P(&x);
print(x);
}

The output of this program is

Q. The goal of structured programming is to

Q. Consider the following C function

void swap (int a, int b)
{
   int temp;
   temp = a;
   a = b;
   b = temp;
}

In order to exchange the values of two variables x and y.

Q. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?