Question

Question 1

The following statements illustrate which concept below?
var1 = 1
while var1 != 0:
var1 = var1+ 1

A. A P complex problem.

B. A deterministic problem.

C. An NP problem.

D. The halting problem.

Question 2

If a function is computable,

A. both a Turing machine and a Bare Bones Language program can solve it .

B. a Turing machine can solve it, but a Bare Bones Language program cannot .

C. a Turing machine cannot solve it, but a Bare Bones Language program can .

D. it must be non-deterministic.

Question 3

Which of the following questions has not yet been answered by researchers?

A. Is P contained in NP?

B. Is NP contained in P?

C. Are all the problems in NP solvable?

D. Are all the problems in P solvable?

Question 4

The class of problems known as NP complete

A. have no known solution

B. have clear, easily verified solutions

C. require a bare bones language to solve them

D. may have solutions, but it is not easy to verify them

Question 5

Which of the following algorithms represents an optimal solution (in terms of time complexity) for sorting a list?

A. Insertion sort

B. Bubble sort

C. Selection sort

D. Merge sort

Question 6

Which of the following represents the most costly algorithm for solving a problem?

A. Θ(2**n)

B. Θ(n log2 n)

C. Θ(log2 n)

D. Θ(n2)

Question 7

Which of the following statements belong to the Bare Bones language?

A. x = y

B. copy x to y

C. while x> y

D. while x not 0

E. if x == y

F. x = x + 1

G. increment x

H. decrement x

Answer 1

Answer:----------

1. D. The halting problem.
2. A. both a Turing machine and a Bare Bones Language program can solve it .
3. B. Is NP contained in P?
4. B. have clear, easily verified solutions
5. D. Merge sort
6. A. Θ(2**n)
7. D. while x not 0