A collision in a symbol table hash occurs when
Answer: A
Distinct names sharing a bucket is unavoidable once the number of possible names exceeds the number of buckets. Chaining and open addressing are the two standard responses. The pigeonhole principle makes collisions unavoidable in any real table.
Please log in or register to report this question.
Separate chaining resolves collisions by
Answer: B
Each bucket holds a pointer to a list of the entries that hashed there. Lookup hashes once and then walks a short list, which stays cheap provided the load factor is kept modest. Unlike open addressing, chaining continues to work when the table is overfull.
Please log in or register to report this question.
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.
