106年 - 106 國立中山大學_碩士班招生考試_電機系(丙組)：離散數學#109065

1.(10%) Given Boolean variables p, q, and r where -p is the complement of p, A is logical AND, v is logical OR, → is logical imply, and is equivalence, prove that the following formula is true.

2.(15%) Given a directed graph G as in Figure 1, derive a relation matrix R of the graph, and derive the matrix of transitive closure R* of relation R.
  

3.(15%) In a 2D n ✖ n checkerboard as shown in Figure 2, given two integers p and a (1≤p ≤ q≤n), write the formula of the number of all possible squares in the checkerboard with side length s satisfying p ≤s≤g. Write the result in a formula of n, p, and q.

4.(15%) Given a bag having 4 white balls and 3 red balls, let us proceed a drawing run that a drawing

takes a ball from the bag, record its color, put it back, and do such drawing for 5 times. Assume that

the probability of each distinct red ball being drawn is two times of that of a distinct white ball

being drawn. Calculate the probability to draw exactly 3 white balls and 2 red balls in the run.

5.(10%) A complete graph K_n is a graph G(V,E) with n vertices (n ≥ 1) that have an edge between each pair of vertices in the vertex set. Write the formula of the number of all complete suberaphs K, existing in Kn. (1 ≤p ≤n) The formula is a function of n.

6.(10%) Write an algorithm queue partitioning(g. k) to reorder all data elements in a queue q. Assume that the queue q has n integer elements initially. Given an integer k ＞ 1, the reordering will form k ordered partitions of these integers. The resulting queue should be in the order of partition 0, partition 1, and partition k-1. Thepartition of these integer elements contains all integer elements e in the original queue such that e mod k= i. (In this algorithm, you can utilize an empty queue q2 as a local variable.) You can use a function length(q) to get the length of the queue q.
For illustration, Figure 3 shows an example with an initial queue state, k = 3, ordered partitions, and a final queue state.

7.(15%) A binary expression tree data structure uses the node data element given as follows. A node either represents a value or represents an arithmetic operator in { +, -, *, / }. An evaluation of an example expression tree is shown in Figure 4. Write a recursive algorithm evaluate(roos) to perform such expression evaluation task where root points to the root element of the expression tree.