所屬科目：中山◆電機◆離散數學
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 Kn 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.
阿摩線上測驗
登入
阿摩線上測驗
登入
is equivalence, prove that the following formula is true.
partition 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.
