Compilation principle and operating system of the 2009 Program of Computer Technology Research Institute of the Chinese Academy of Sciences
I. (15 points) The expression is as follows: A B * (CD) ** n (** is power multiplication) (1) gives the expression of the reverse polish expression (suffix); (2) give A fourth-dollar and tribal sequences of the above expression.
II. (15 points) There is a C procedure as follows: main () {Printf ("% D,% D,% D / N", 10);} (1) Try to write the result of the above PRINTF statement output; (2) The implementation of the operational environment and the Printf is analyzed why there will be such an output result.
III. (5 points) Constructing a DFA (determined finite automatic), so that it accepts an idby "1" 0,1 set.
IV. (5 points) There is a grammatical g, which is as follows: S-> S (s), S-> ε / * empty generation style * / test writes a syntax guided definition, which outputs the number of brackets.
5. (10 points) Known language L = {A ^ (m) b ^ (n) | n> m> = 0}. Try to write two grams of literature between the language, where G1 is LR (1) The grammar, G2 is non-LR (1) and non-unspective grammar.
6. Fill in the blanks (a total of 20 points per empty) 1. Two most basic features of the modern operating system are ___ and ___. 2. The initialization of the process control block includes ___, ___ and ___ .3. The main purpose of introducing thread concepts in the operating system is ___. 4. UX system V, system call to the user to create new processes is ___; system call for establishing an unnamed pipeline is ___; System call for creating a famous pipe is ___. 5.Unix system V, cause process scheduling for ___, ___, ___ and ___, etc. 6. In partition allocation algorithm, first time The adaptation algorithm tends to prioritize the idle partition of the ___ portion in the memory, thereby retain the large space zone of the ___. 7. The data table required for the device allocation is mainly ___, ____________ __ et al .8. When using symbolic chain to implement file sharing, the pointer caused by the file main delete the pluggable problem after sharing files, and the solution is ___.
7. (8 points) In the message delivery communication mode, a. Sending process and reception process can adopt three synchronous mode in communication process? B. Try the sending process and reception process given below (will receive Data Store S) Takes an example, indicating that the three synchronization mode is used when the reception process is executed to the label L2, and the value of X may each matter how much? Send process P: Receive process Q: m = 10; L1: Send M to Q; L1: Receive S from P; L2: M = 20; L2: x: = S 1; Goto L1;
Eight. (8 points) One system has 150 storage units, allocated to three processes in the table below: Process Maximum Demand CURRENT AllocationP1 70 25P2 60 40p3 60 45 The following request application banker algorithm analysis determines if it is Safety: a. The fourth process P4 arrives, the maximum requirement 60 storage units, the current request is allocated. The fourth process P4 arrives, the maximum requirement 50 storage units, the current request is allocated 35 units. If It is safe, please give a possible process security execution sequence. If it is not safe, please explain the reason.
Nine, (14 points) The page table of a process that is executing on the processor is as follows. The virtual page number and physical block number of the page table are decimal, and the start page number (block number) is 0. All addresses Is the memory byte address, the size of the page is 1024 bytes .A. Details in the request page storage management system with a quick table, a virtual address is converted into a physical memory address. B. The following emotive address corresponds to what? Physical address: (1) 5499; (2) 2221; Virtual page number status bit access bit modified physical block number 0 1 1 0 41 1 1 72 0 0 0 --- 3 1 0 0 24 0 0 0 - -5 1 0 1 0 Note: Access bit - • When a page is accessed, its access bit is set to 1. ※ Test Paper provides: Wang Min ※ Source: Tianji.com Http://edu.yesky.com/ JXZL / KAOYAN / KAOYAN.HTM -
China Academy of Sciences Computer Technology Research Institute, 2009 Master's Enrollment Question, Compilation Principle and Operating System Reference Answer
I. (1) Sudular: Abcd - * ECD-N ** / (2) Quadruple Trimage (1) (-, C, D, T1) (1) (-, C, D) (2) (*, b, t1, t2) (2) (*, b, (1))) (3) ( , a, t2, t3) (3) ( , A, (2)) (4) (-, C, D, T4) (4) (-, C, D) (5) (**, T4, N, T5) (5) (**, (4), N) (6) (6) ( /, E, T5, T6) (6) (/, E, (5)) (7) ( , T3, T6, T7) (7) ( , (3), (6))
II. (1) (5 points) Output: 10, x, y where x, y is random integer value (2) (10 points) From the activity record content arrangement, in the running stack, the caller's activity record is The caller is below, as shown: in which the parameter domains and possible return values are placed on the place where the caller activity record is. Such benefits is that the caller is not required to understand local data or temporary amounts of the caller. To do information hide. Another benefit is that the process of variable change can be handled, such as Printf. From the Printf implementation, the Printf function in the C language, his first change pointed out the nature of the remaining parameters So once the printf can determine the first variable changing position, he can find the remaining variables. C is in reverse order calculation and inrest, so that the caller can know the first change in the first variable element. In the case, the main function calls the Printf only in the two parameters to the stack, and the first parameter indicates that three integer values are to be displayed, but only (press the stack (a valid value). So The above results.
III. (5 points) See attachment pictures
