[CS]请教ETS2004官方题里几道不明白的题

@amy@UID: 209096

下面这几道题对着答案也不明白，有没有知道的人给我解释一下，多谢啦~~~

1、Hash tables can contribute to an efficient average-case solution for all of the problems described below EXCEPT:
(A) Counting distinct values: Given a set of n keys, determine the number of distinct key values.
(B) Dynamic dictionary: Support the operations of insert, delete, and search in a dictionary
(C) Range search: Given values a and b, find all the records whose key value is in the range [a,b].
(D) Symbol table lookup: Given a program identifier, find its type and address.
(E) Finding intersections: Given two sets of keys, find all key values in common to both sets.

Answer: C
请问E答案说的问题怎么通过hash table解决阿？

2、A certain pipelined RISC machine has 8 general-purpose registers R0, R1, . . . , R7 and supports the following operations.
    ADD Rs1, Rs2, Rd Add Rs1 to Rs2 and put the sum in Rd
    MUL Rs1, Rs2, Rd Multiply Rs1 by Rs2 and put the product in Rd
An operation normally takes one cycle; however, an operation takes two cycles if it produces a result required by the immediately following operation in an operation sequence. Consider the expression AB+ABC+BC, where variables A, B, C are located in registers R0, R1, R2. If the contents of these three registers must not be modified, what is the minimum number of clock cycles required for an operation sequence that computes the value of AB+ABC+BC?
(A) 5   (B) 6   (C) 7    (D) 8    (E) 9

Answer: B
难道执行过程是下面这样的？自己不确定
MUL R0, R1, R3    // 计算AB，1 clock cycle
MUL R1, R2, R4    // 计算BC，1 clock cycle
MUL R3, R2, R5    // 计算ABC，1 clock cycle
ADD R3, R4, R6    // 计算AB + BC， 2 clock cycles
ADD R6, R5, R7    // 计算AB + BC + ABC， 1 clock cycles

3. In systems with support for automatic memory management, a garbage collector typically has the responsibility for reclaiming allocated memory objects whose contents cannot affect any future legal computation. Such objects are identified by determining that they cannot be reached from a root set. Which of the following is NOT part of the root set in a typical garbage collector?
(A) Actual parameters of the active procedures
(B) Dynamically allocated objects on the heap
(C) Global variables of the program
(D) Local variables on the call stack
(E) Values in machine registers

Answer: B
root set是什么意思？难道寄存器的值也算在内？

4. Let M be a single-tape, deterministic Turing machine with tape alphabet {blank, 0, 1},   and let C denote the (possibly infinite) computation of M starting with a blank tape. The input to each problem below is M, together with a positive integer n. Which of the following problems is (are) decidable?
I. The computation C lasts for at least n steps.
II. The computation C lasts for at least n steps, and M prints a 1 at some point after the nth step.
III. M scans at least n distinct tape squares during the computation C.

(A) None
(B) III only
(C) I and II only
(D) I and III only
(E) I, II, and III

Answer: D

5. Assume that a debugger places a breakpoint at a load instruction at virtual address 0x77E81234 (hexadecimal notation) in a debugged process P. If the text segment of P begins at 0x77E80000 in P's virtual address space and if the debugger has mapped this same text segment at 0x01000000 in its virtual address space, which of the following is the virtual address used by the debugger in its WRITE operation, along with a description of how the debugger has mapped the virtual memory page containing this address?
(A) 0x01001234; page mapped with READ/WRITE access
(B) 0x01001234; page mapped with COPY-ON-WRITE access
(C) 0x76E81234; page mapped with READ/WRITE access
(D) 0x76E81234; page mapped with COPY-ON-WRITE access
(E) 0x77E81234; page mapped with READ/WRITE access

Answer: A
READ/WRITE access 和 COPY-ON-WRITE access有什么区别？

AutoseaUID: 192045

1,先对一个集合中的每个元素作哈希，放到数组里面。在对另一个集合的元素作哈希，如果落在了同一个数组元素里面，就表明这个元素在两个集合中都有。

2,指南上有这道题，倒数第二个指令应该是1 clock

3,我也不大清楚root set到底是什么，我认为就是当前有用的内存访问。从这些访问出发，遍历heap，遍历到的就作标记，最后把没遍历到的都给清掉。

4,I显然，III我也不清楚，可能是由于Turing Machine是确定了的，它的状态转移函数就是确定了的，所以可以确定C可以扫描几个不同的块。

5,copy-on-write是写时复制，google一下吧

@amy@UID: 209096

谢谢Autosea这么快就解答了~~   ^_^

yuren78UID: 2111432

2>

MUL R0, R1, R3    // 计算AB，1 clock cycle
MUL R1, R2, R4    // 计算BC，1 clock cycle
MUL R3, R2, R5    // 计算ABC，1 clock cycle
ADD R3, R4, R6    // 计算AB + BC， 2 clock cycles [这一个是 1 cycle]
ADD R6, R5, R7    // 计算AB + BC + ABC， 1 clock cycles [这一个是 2 cycles].

5>Copy - On - Write

Different processes can share the common pages in memory if they only need read, but if they want to write, then the process initiating the write need to copy a page.

This is mainly for efficiently reasons.