____1. In theoretical computer science, researchers study the logical and ____ of problems and their solutions.

a. mathematical properties c. mathematical uniqueness

b. difficulty level d. mathematical formulation

____2. ____ is one of the most common applications of computers.
a. Searching a list
b. Running a company
c. Writing a program
d. Generating a list of all the prime numbers

____3. Designing programming languages and translating algorithms into these languages is known as ____ realization.
a. programming language c. linguistic
b. compiler d. interpreter

____4. A(n) ____ instruction carries out a single well-defined task.
a. sequential c. iterative
b. conditional d. hierarchal

____5. In computer science terminology, the machine, robot, person, or thing carrying out the steps of the algorithm is called
a(n) ____.
a. computing agent c. computing representative
b. algorithmic agent d. algorithmic representative

____6. An algorithm is essentially useless when ____.
a. its difficult to read c. it takes too long to create
b. it takes too long to execute d. people might be offended by the
results

____7. A(n) ____ is a well-ordered collection of unambiguous and effectively computable operations that, when executed,
produces a result and halts in a finite amount of time.
a. sequence c. mechanical calculator
b. computing agent d. algorithm

____8. An operation that is unambiguous is called a ____ operation of the computing agent carrying out the algorithm.
a. primary c. basic
b. complementary d. primitive

____9. What is wrong with the following algorithm?
1. Set X to be 1
2. Increment X
3. Print X
4. If X > 0, repeat from 2
a. It does not produce a result.
b. It is ambiguous.
c. It does not halt in a finite amount of time.
d. It is not well-ordered.

____10. Automation of repetitive mental tasks was part of a movement known as the ____ revolution.
a. industrial c. computer
b. technological d. designer

____11. The history of mathematics begins ____ years ago.
a. 250 c. 2,000
b. 1,000 d. 3,000 or more

____12. In 1672, a French philosopher and mathematician designed and built one of the first mechanical calculators named
the ____ that could do addition and subtraction.
a. Pascaline c. abacus
b. Leibniz Wheel d. TI-85

____13. The first slide rule appeared around ____.
a. 1183 c. 1882
b. 1622 d. 1945

____14. In 1614, John Napier invented ____ as a way to simplify difficult mathematical computations.
a. algorithms c. electronic computers
b. logarithms d. mechanical calculators

____15. ____ was the first programmable device.
a. A Leibniz Wheel c. The Pascaline
b. The Analytic Engine d. Jacquards loom

____16. In Babbage's analytical engine, a mill was used to ____.
a. store memory c. perform arithmetic operations
b. process instructions d. accept input

____17. The ____ was the first fully electronic general-purpose programmable computer.
a. EDVAC c. ENIAC
b. EDSAC d. Mark I

____18. In 1946, John Von Neumann proposed a radically different computer design based on a model called the ____
computer.
a. stored program c. programmable function
b. external program d. memory unit

____19. Integrated circuits, built on silicon chips, were introduced during the ____ generation of computing.
a. first c. third
b. second d. fourth

____20. During the ____ generation of computing, the desktop machine shrunk to the size of a typewriter.
a. first c. third
b. second d. fourth

____21. ____ is an example of a natural language.
a. C c. English
b. Java d. Perl

____22. In the line of code, Set the value of Area to length*width, Area is a ____.
a. value c. constant
b. variable d. primitive

____23. A(n) ____ is a named storage location that can hold a data value.
a. expression c. computation
b. variable d. constant

____24. ____ operations provide the computing agent with data values from the outside world that it may then use in later
instructions.
a. Ingoing c. Input
b. Outgoing d. Output

____25. ____ operations send results from the computing agent to the outside world.
a. Input c. Send
b. Put d. Output

____26. A purely ____ algorithm is sometimes termed a straight-line algorithm.
a. sequential c. iterative
b. conditional d. control

____27. Together, conditional and iterative operations are called ____ operations.
a. sequential c. hierarchical
b. control d. dynamic

____28. ____ statements are the question-asking operations of an algorithm.
a. Primitive c. Sequential
b. Iterative d. Conditional

____29. A ____ is the repetition of a block of instructions.
a. cycle c. matrix
b. nucleus d. loop

____30. An algorithm can fall into an infinite loop when ____.
a. the input operations were missing
b. the algorithm uses more than one loop
c. the output operations were missing
d. the continuation condition of the loop never becomes false

____31. In a pretest loop, the continuation condition is tested at the ____ through the loop.
a. beginning of each pass c. end of each pass
b. beginning of only the first pass d. end of only the last pass

____32. The ____ loop is an example of a posttest loop.
a. do/while c. while
b. do d. if/then/else

____33. To create a loop that executes exactly b times, we create a ____.
a. control object c. counter
b. counting method d. variable

____34. Print the value of product is an example of a(n) ____ operation.
a. sequential c. input
b. conditional d. output

____35. The technique of looking at all the items in a list, starting at the beginning of the list, one at a time, until we either
find what we are looking for or come to the end of the list is called ____ search.
a. sequential c. iterative
b. control d. random

____36. The selection of an algorithm to solve a problem is greatly influenced by the way the input ____ for that problem are
organized.
a. words c. solutions
b. data d. pseudocode

____37. A(n) ____ is a collection of useful, prewritten algorithms.
a. primitive c. set
b. binary d. library

____38. In order to implement a find functionality in a word processor, one would have to design a ____ algorithm.
a. pattern matching c. sequential
b. natural language d. do-while

____39. Which statement exemplifies abstraction?
a. The president of General Motors views the company in terms of every worker, every
supplier, and every car.
b. The president of General Motors views the company in terms of its corporate divisions
and high-level policy issues.
c. A good approach to algorithm design and software development is to focus on how we
might actually implement a particular operation.
d. A convenient way to view the hardware component called memory is to focus on
the billions of electronic devices that go into constructing a memory unit.

____40. Viewing an operation at a high level of abstraction and fleshing out the details of its implementation at a later time is
known as ____ design.
a. bottom-up c. increasing size
b. top-down d. increasing depth

____41. ____ is the algorithmic equivalence of style.
a. Efficiency c. Aesthetics
b. Elegance d. Complexity

____42. ____ involves the fixing of errors that are uncovered through repeated usage with different input values.
a. Program maintenance c. Data cleanup
b. Recycling d. Garbage collection

____43. ____ are useful for rating one machine against another and for rating how sensitive a particular algorithm is with
respect to variations in input on one particular machine.
a. Time trials c. Comparison times
b. Benchmarks d. Intensive tests

____44. The study of the efficiency of algorithms is called the ____ of algorithms.
a. design c. implementation
b. analysis d. testing

____45. In the sequential search algorithm, the minimum amount of work is done if the value being searched for is the ____
value in the list.
a. first c. middle
b. second d. last

____46. The ____ case of an algorithm requires the least work.
a. best c. smallest
b. worst d. largest

____47. In the sequential search algorithm, the worst case occurs when the value being searched for is the ____ value in the
list.
a. first c. middle
b. second d. last

____48. Placing a list of items into alphabetical or numerical order is called ____.
a. simplifying c. sorting
b. searching d. pattern matching

____49. The ____ sort algorithm performs the task of sorting a list by growing a sorted subsection of the list from the back to
the front.
a. selection c. shuffle-left
b. sequential d. binary

____50. Selection sort is a(n) ____ algorithm in all cases.
a. 1) c. (2n)
b. (n) d. (n
2
)

____51. Sequential search is a(n) ____ algorithm in the worst case.
a. 1) c. (2n)
b. (n) d. (n
2
)

____52. Part of the job of program ____ is to make clear any assumptions or restrictions about the input size the program was
designed to handle.
a. design c. documentation
b. implementation d. maintenance

____53. The shuffle-left algorithm is a(n) ____ algorithm in the worst case.
a. 1) c. (2n)
b. (n) d. (n
2
)

____54. The copy-over algorithm is ____ in time efficiency in the worst case.
a. 1) c. (2n)
b. (n) d. (n
2
)

____55. The worst case in binary search occurs ____.
a. when the object to be searched is in the middle of the list
b. when the object to be searched is at the end of the list
c. when the object to be searched is at the beginning of the list
d. when the object to be searched is not in the list

____56. Binary search does ____ comparisons in the worst case.
a. 1) c. (n)
b. (lg n) d. (n
2
)

____57. (lg n), (n) and (n
2
) are ____ in the amount of work they do as n increases.
a. restricted c. polynomial bounded
b. useful d. exponential

____58. An ____ algorithm is called an exponential algorithm.
a. (lg n) c. (n
2
)
b. (n) d. (2
n
)

____59. Problems for which no known polynomial solution algorithm exists are sometimes approached via ____ algorithms.
a. alternative c. polynomial
b. intractable d. approximation

____60. A surprising number of problems fall into the ____ category.
a. suspected intractable c. bin-packing
b. approximation algorithm d. declared intractable