1st Midterm Exam
Important Concepts
The test will cover all material from chapters 1, 2, and 3. In addition all material covered during lecture and lab may be tested. Here is a listing of some of the most important concepts:
- Chapter 1
- Definition of Computer Science
- Definition of Algorthim
- History of Computing
- Chapter 2
- Pseudocode
- Sequential, Conditional, and Iterative Operations
- Find largest algorithm
- Premitives
- Chapter 3
- Efficiency of Algorithms
- Order of Magnitude – Order n, n2, log n, 2n
- Binary Search and Sequential search algorithms
- Sorting algorithms (selection, insertion, bubble, quick, merge)
- Data Cleanup algorithms
- Common Exponential Problems (Hamiltonian Circuit Problem, Satisfiability Problem, Bin-Packing Problem)
Sample Questions
(this is not meant to be a comprehensive list of all questions that may be asked on the exam. This is just a sampling if questions that may be asked during the exam.)
True/False
Indicate whether the statement is true or false.
____1.Whether or not an operation is a primitive depends, in part, on the computing agent that is expected to execute it.
____2.Computer science work was carried out even before the electronic computer was invented.
____3.The five generations of modern computers are distinguished mainly by fundamental changes in the underlying computer architecture.
____4.John Von Neumann created the modern computer architecture when he developed a computer that stored its program in its own memory.
____5.The first accurate definition of computer science described it as a study of algorithms.
____6.The three types of operations used to construct algorithms are sequential, conditional, and iterative.
____7.The statement: “If the mixture is too dry, then add one-half cup of water to the bowl” is an example of a conditional operation.
____8.Euclid's algorithm finds prime numbers between any two given numbers.
____9.If you can specify an algorithm to solve a problem you can automate its solution.
____10.Algorithms usually contain a set of instructions to be executed in any order.
____11.The first electronic programmable computer, ENIAC, was built during World War I.
____12.A sequential algorithm executes its instructions in a straight line from top to bottom and then stops.
____13.In a posttest loop, it is possible for the loop body to never be executed.
____14.Finding the maximum number in a given set is an example of a problem that computer scientists want to solve.
____15.Java and C++ are examples of pseudocode languages.
____16.Languages such as Java and C++ are the algorithmic design languages of choice.
____17.The fact that natural language can have many different meanings in different contexts makes it difficult to use for designing algorithms.
____18.The three basic sequential operations are called addition, multiplication, and exponentiation.
____19.Input and output allow the computing agent to communicate with the outside world.
____20.One of the most powerful features of a computer is its ability to handle loops.
____21.Iteration should be minimized when designing algorithms.
____22.In the sequential search algorithm, the worst case occurs when the value being searched for is the first value in the list.
____23.With sequential search, the bigger the list of items, the more work that must be done to search it.
____24.Elegance is the first and foremost expectation of a proper algorithm.
____25.A collection of sets and vectors is called a graph.
Multiple Choice
Identify the choice that best completes the statement or answers the question.
____26.The operation “Replace i with i - 1” is a(n) ____ operation.
a. / Sequential / c. / iterativeb. / Conditional / d. / hierarchal
____27.The ____ was the first computing device to use the base-2 binary numbering system.
a. / Mark I / c. / Analytic Engineb. / Difference Engine / d. / ENIAC
____28.FORTRAN and COBOL, the first high-level (“natural”) programming languages, appeared during the ____ generation of computing.
a. / First / c. / thirdb. / Second / d. / fourth
____29.What is a computing agent?
a. / something that carries out steps of the algorithmb. / a person who works with users and developers for improving software
c. / a person that writes computer code
d. / the hardware that powers the computer
____30.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 resultb. / it is ambiguous
c. / it does not halt in a finite amount of time
d. / it is not well-ordered
____31.Integrated circuits, built on silicon chips, were introduced during the ____ generation of computing.
a. / First / c. / thirdb. / Second / d. / fourth
____32.Automation of mental tasks was part of a movement known as the ____ revolution.
a. / Industrial / c. / computerb. / Technological / d. / designer
____33.Most computer scientists use ____ to design and represent algorithms.
a. / natural languages / c. / low-level programming languagesb. / high-level programming languages / d. / pseudocode
____34.A purely ____ algorithm is also called a straight-line algorithm.
a. / Sequential / c. / iterativeb. / Conditional / d. / control
____35.Together, conditional and iterative operations are called ____ operations.
a. / Sequential / c. / hierarchicalb. / Control / d. / dynamic
____36.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. / iterativeb. / Control / d. / random
____37.____ is the process of searching for a special pattern of symbols within a larger collection of information.
a. / Sequential search / c. / Pattern matchingb. / Dynamic processing / d. / Pattern search
____38.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 sizeb. / top-down / d. / increasing depth
____39.____ is an example of a natural language.
a. / C / c. / Englishb. / Java / d. / Perl
____40.Consider this line of code: Set the value of Area to length*width
“Area” is a____.
a. / Value / c. / constantb. / Variable / d. / primitive
____41.If, then, and else are examples of ____ statements.
a. / primitive / c. / sequentialb. / iterative / d. / conditional
____42.A(n) ____ is a collection of useful algorithms.
a. / primitive / c. / setb. / binary / d. / library
____43.In order to implement a “find” functionality in a word processor, one would have to design a ____ algorithm.
a. / pattern matching / c. / sequentialb. / natural language / d. / do-while
____44.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.
____45.An ____ algorithm is called an exponential algorithm.
a. / (lg n) / c. / (n2)b. / (n) / d. / (2n)
____46.____ is the term to describe an algorithm’s careful use of resources.
a. / Resourcefulness / c. / Effectivenessb. / Time-Space Tradeoff / d. / Efficiency
____47.____ is the fixing of errors uncovered through repeated use of an algorithm.
a. / Program maintenance / c. / Data cleanupb. / Recycling / d. / Garbage collection
____48.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-leftb. / sequential / d. / binary
____49.A ____ is a path through a graph that begins and ends on the same node and goes through every node exactly once.
a. / Newtonian loop / c. / Hamiltonian circuitb. / McCarthian path / d. / complete trip
____50.The process of timing an algorithm using the same machine but searching for different items is called ____.
a. / time trials / c. / comparison timingb. / Benchmarking / d. / intensive testing
51. Show what is printed by each of the following partial algorithms:
a. Assign Count a value of 1 ANSWER:
If Count < 0 then
Print 'Yes'
else Print 'No'
b. Set GPA to a value of 1.0 ANSWER:
If GPA < 2.0 then
Print 'Uh-oh'
Print the value of GPA
c. Assign GPA a value of 2.3 ANSWER:
If GPA < 2.0 then
Print 'Uh-oh'
Print the value of GPA
d. Set the value of Count to 3 ANSWER:
While Count < 6 do
Print the value of Count
Set Count to the value of Count + 1
Print 'END'
52. Write pseudocode for the following operations:
a. Compute and display the value x divided by y if y is not zero. Otherwise, display "Sorry".
b. Set n to the value of 1. While n ≤ 10, print n and increment n by 1.
53.Trace the following algorithm showing the values of sum, n and the step number being executed displayed as:
Stepsumn
If the value isn't assigned yet, write G for its value. Assume your computing agent can add numbers two at a time and can square numbers.
Step 1: Set sum equal to 0.
Step 2: Set n equal to 1.
Step 3: Repeat steps 4 and 5 until n > 4.
Step 4:Set sum equal to sum + n2.
Step 5:Replace n with n + 1.
Step 6: Print sum.
Step 7. Stop.
54. For the following list, perform a bubble sort, and show the list after each exchange.
4, 8, 2, 6
55. Suppose selection sort and bubble sort are both performed on a list that is already sorted. Does bubble sort do fewer exchanges than selection sort?
56. Find an assignment for the variables to make the following logic statement true (satisfiability problem):
(A or B or C) and (¬A or ¬B) and (¬B or ¬C) and (¬A or ¬C)
1st Midterm Exam
Answer Section
TRUE/FALSE
1.ANS:T
2.ANS:T
3.ANS:F
4.ANS:T
5.ANS:T
6.ANS:T
7.ANS:T
8.ANS:F
9.ANS:T
10.ANS:F
11.ANS:F
12.ANS:T
13.ANS:F
14.ANS:T
15.ANS:F
16.ANS:F
17.ANS:T
18.ANS:F
19.ANS:T
20.ANS:T
21.ANS:F
22.ANS:F
23.ANS:T
24.ANS:F
25.ANS:F
MULTIPLE CHOICE
26.ANS:A
27.ANS:A
28.ANS:B
29.ANS:A
30.ANS:C
31.ANS:C
32.ANS:C
33.ANS:D
34.ANS:A
35.ANS:B
36.ANS:A
37.ANS:C
38.ANS:B
39.ANS:C
40.ANS:B
41.ANS:D
42.ANS:D
43.ANS:A
44.ANS:B
45.ANS:D
46.ANS:D
47.ANS:A
48.ANS:A
49.ANS:C
50.ANS:B
51.ANS: a. NO b. Uh-oh c. 2.3 d. 3 4 5
52.a. if y is not 0 then
set z to be x/y
else
print “sorry”
b. set n to 1
while n <= 10
print n
set n to be n+1
53.step sum n
10 G
20 1
41 1
51 2
45 2
55 3
414 3
514 4
430 4
530 5
630 5
730 5
54.4, 8, 2, 6
4, 2, 8, 6
2, 4, 8, 6
2, 4, 6, 8
55.Both do zero exchanges
56.A=false, B=false, C=true