Introduction to Computer Science: Final Exam

2008-06-12

(All the answers must be written in English.)

  1. (10 points) A grammar is ambiguous if it is possible to have more than one parse tree for one string. Give an example of ambiguous grammar with its associated parse trees.
  1. (10 points) Indicate whether each one of the following sentences is about “black box testing”or “white box testing”.

①It assumes that we know everything about the program.

②It is usually performed by the system test engineer and the user.

③We must make sure that every instruction and every possible situation have been tested.

④Test plans are developed by looking only at the requirements.

  1. (20 points)Answer each one of the following questions on data abstractions.

①Give a formula for finding the entry in the ith row and jth column of a two dimensional array if it is stored in “column major order”rather than “row major order”. (Assume the entry in the 1st row and 1st column is stored at address X.)

②Design a procedure to remove the bottom entry from a stack so that the rest of the stack is retained. You should access the stack using only “push”and “pop”operations. What auxiliary storage structure should be used to solve this problem?

③Draw a binary tree which stores 13 symbols (i.e., A, B, C, D, E, F, G, H, I, J, K, L, and M) for binary searching.

  1. lowing SQL statementinto a sequence of SELECT, PROJECT, and JOIN operations.

selectASSIGNMENT.StartDate
fromASSIGNMENT, EMPLOYEE
whereASSIGNMENT.EmplID = EMPLOYEE.EmplID and
EMPLOYEE.Name = “Joe E. Baker”

  1. (20 points) Answer each one of the following questions on artificial intelligence.

①What are the three main components of production systems?

②Design an XOR (Exclusive-OR) gate using two processing units of neural network.

③Fill in the blanks on evolutionary programming:
An important step is to find the ways in which parts of programs can be ______to produce meaningful new programs.
The ______programming paradigm has proved useful in this context.

  1. (20 points)Answer each one of the following questions on security.

①Give an example of nonrepudiation.

②What are the disadvantages of secret key encryption?

③Suppose site A is going to send a message to site B with digital signature on the digest of the message. What does site A do before transmitting the message and what does site B do after receiving the message?

  1. (10 points) Answer each one of the following questions on theory of computation.

①What is the main purpose of Turing machine?

②What is the halting problem? Is it computable or noncomputable?

------END ------