103年 - 103 國立嘉義大學_碩士班(乙組)招生考試試題_資訊管理學系：計算機概論#146002

(a) Please draw the heuristic search tree for solving the famous8 puzzle problem. The puzzle is contained in a tray that can bethought of as a grid of nine squares. The tray contains onlyeight tiles, which means that one of the grids is always empty.The tiles are numbered from 1 to 8. The rule of the game isthat a tile can be slid into an empty slot. The initial and goalstates of an 8-puzzle are shown as the follows. Please draw theheuristic search tree for solving the puzzle.

(b) Use a truth table to find whether the following argument isvalid.
{P → Q, Q → R} |− (P → R)

(a) List and define three kinds of identification witness in entityauthentication.

(b) Define a certification authority (CA) and its relation to public-key cryptography.

(a) The input data to a program is made up of a combination ofthree integers in the range of 1000 to 1999 (inclusive). Findthe number of exhaustive tests to test all combinations of thesenumbers.

(b) A random number generator creates a number between 0and 0.999. How can this random number generator be used todo random testing for the system described in (a).

(a) Write a recursive algorithm in pseudocodeto find thecombination of n objects taken k at a time using the followingdefinition.
\( C(n, k) = \begin{cases} 1 & \text{if } k = 0 \text{ or } n \\ C(n-1, k) + C(n-1, k-1) & \text{if } n > k > \end{cases} \)

(b) Using the above definition, find C(10,3) and C(2,7).

(a) Sending a frame to the next node.

(b) Sending a packet from the source to the destination.

(c) Delivery of a long message from the source computer to thedestination computer.(d) Logging in to a remote computer.