Open addressing resolves collisions by
Answer: C
Correct answer: probing further buckets until a free one is found
Open addressing keeps everything in the table itself: on a collision it probes the next bucket, or one chosen by a further computation, until it finds a free one. It avoids the pointers that chaining needs, at the cost of performance falling away sharply as the table fills.
Please log in or register to report this question.
A hash table has 64 buckets and holds 48 entries. What is its load factor?
Answer: D
The load factor is entries divided by buckets, that is forty eight divided by sixty four, giving nought point seven five. Chained tables tolerate a load factor above one; open addressed tables degrade sharply as it approaches one.
Please log in or register to report this question.
A good hash function for identifiers should
Answer: A
Correct answer: distribute names evenly and use every character of the name
Using every character means that names differing anywhere hash differently, and even distribution keeps the chains short. Hashing on the first character alone would bucket every name beginning with the same letter together, which in real programs - full of names sharing prefixes - is close to the worst case.
Please log in or register to report this question.
Assertion (A): A hash function that uses only the first character of an identifier performs badly in a compiler.
Reason (R): Programmers habitually choose related names sharing a common prefix, so such a function clusters them into few buckets.
Answer: B
Both are true and the reason gives the mechanism, and the effect is easy to observe. A program full of names beginning with the same letter would reduce the table to a handful of long chains and lose the advantage of hashing entirely.
Please log in or register to report this question.
Scope determines
Answer: C
Correct answer: the region of the program in which a declaration is visible
Scope is a textual region in a statically scoped language: the block in which the declaration appears, less any inner block redeclaring the same name. It determines which declaration a use refers to, and it is what the symbol table’s nesting machinery exists to represent.
Please log in or register to report this question.
Under the most closely nested rule, a use of a name refers to
Answer: D
An inner declaration hides an outer one of the same name for the extent of the inner block. This is the rule almost every block structured language adopts. The alternative, where an inner declaration is simply an error, is rare.
Please log in or register to report this question.
A one table implementation of nested scopes handles block entry and exit by
Answer: A
Correct answer: pushing entries onto a stack and popping them when the block ends
A single table organised as a stack matches the nesting exactly: entering a block records a mark, declarations are pushed above it, and leaving the block pops back to the mark. Lookup searches from the top down, so the innermost declaration is found first - which is precisely the scoping rule.
Please log in or register to report this question.
A chained symbol table implementation searches
Answer: B
Following the chain outward realises the most closely nested rule directly. A failed lookup at every level means the name is undeclared and an error is reported. A placeholder entry is then usually installed to suppress repeated messages.
Please log in or register to report this question.
Arrange the actions taken when a compiler enters and leaves a nested block.
1. resolve uses within the block against the scope chain
2. create or push a new scope on entering the block
3. discard or pop the scope on leaving the block
4. install the declarations found in the block into that scope
Answer: C
Correct answer: 2 - 4 - 1 - 3
The scope must exist before anything can be installed in it, and the declarations must be installed before uses can be resolved against them. Discarding comes last, when the block ends and its names go out of scope. Resolving before installing would fail on any name declared in the block itself.
Please log in or register to report this question.
An inner declaration that hides an outer one of the same name is said to
Answer: D
Shadowing is temporary and lexical: the outer declaration becomes visible again on leaving the block. Overloading and aliasing are quite different relationships between names. Confusing the three is one of the commonest terminological errors in this area.
Please log in or register to report this question.
