Compiler Design Test 2015

1. Which of the following is NOT a characteristic of a greedy algorithm?

Answers:

• A greedy algorithm always gives an optimal problem solution.

• A greedy algorithm can be recursive.

• A greedy algorithm can be iterative.

• A greedy algorithm can be used with graph data structures.

2. Which among the following is NOT a common element of parser internals?

Answers:

• Finite state machine

• Indefinite state machine

• Petri net

• Language grammar rules interpreter

3. Assume that two instructions L1 and L2 are dependent in a flow graph. What does it mean when one says that they are output-dependent?

Answers:

• They map to the same instruction position in the generated code

• They produce the same result when called

• They write to the same memory location when called

• They share the same output stream block in a code generation phase

4. Which among the following is NOT a standard Common Lisp stream?

Answers:

• *query-io*

• *terminal-input*

• *trace-output*

• *debug-io*

5. Which of the following algorithms is NOT related to a graph mining?

Answers:

• Breadth-first search algorithm

• Fast Fourier transform algorithm

• Dijkstra's algorithm

• Prim's algorithm

6. Which of the following is a dispatch macro character in Common Lisp?

Answers:

• `

• ,

• %

• #

7. Which of the following is NOT a garbage collection algorithm?

Answers:

• Train algorithm

• Baker algorithm

• Cheney algorithm

• Car algorithm

8. Is it possible to multiply two matrices with dimensions 4*6 for the first matrix and 8*10 for the second matrix?

Answers:

• It is always possible.

• It is always impossible.

• It is possible only in complex analysis but not in real domain.

• It is possible only the determinant of first matrix is non-zero.

9. When using "&optional" keyword for declaring a lambda, such as "&optional (x y z)", what does x, y and z signify?

Answers:

• They are all optional variables names

• x is a variable name, y is a binding flag and z is the default value for the variable x

• y is a variable name, x is a binding flag and z is the default value for the variable y

• x is a variable name, z is a binding flag and y is the default value for the variable x

10. Which of the following is NOT a garbage collection technique?

Answers:

• Simple reference counting

• Deferred reference counting

• 1-bit reference counting

• Composed reference counting

11. Is garbage collection available in Common Lisp implementations?

Answers:

• No, it isn't.

• Yes, but only in SBCL.

• Yes, in all implementations.

• Yes, except in CMUCL.

12. What is the return value of the subtype "predicate", in case it CANNOT decide what is the relation between types it is asked about?

Answers:

• It will raise an exception "Unknown types passed to the subtypep predicate"

• It will return nil

• It will return (nil nil)

• It will return (nil nil t)

13. When does a memory leak happen?

Answers:

• It happens when a object created, is not destroyed.

• It happens when memory is still marked as used even after the object has been deleted.

• It happens when two objects hold references to each other and thus they cannot be deleted.

• All of the above

14. Which data structure does a compiler use to solve the register allocation problem?

Answers:

• registers relation map

• registers interference graph

• registers dependency list

• registers allocation tree

15. Which of the following is NOT a Common Lisp equality test predicate?

Answers:

• e

• eq

• eql

• equal

16. Which of the following is NOT a standard Common Lisp type testing predicate?

Answers:

• standard-string-p

• standard-char-p

• simple-bit-vector-p

• random-state-p

17. Which of the following is NOT a valid Common Lisp symbol name?

Answers:

• ||||

• <><><>M<

• ?/?

• #?#

18. What branching instructions type is more resource-consuming on the RISC processor?

Answers:

• Long branch instruction

• Short branch instruction

• All instructions are equal in CPU resources consumption

• RISC processor typically has only long branch instruction. The question therefore is incorrect

19. Which of the following problems prevents garbage collectors from being used in the real-time systems?

Answers:

• They involve huge memory fragmentation.

• They can not be thread-safe.

• They can make real-time systems hang for some period of time.

• All of the above

20. What functionality of the listed below is NOT common to a parser?

Answers:

• Syntax errors handling in a program sources

• Semantic errors handling in a program sources

• Converting a program sources to a syntax tree

• Applying a language grammar rules to a program sources

21. What is the relationship between lexical and syntax analysis?

Answers:

• They are one and the same thing.

• Lexical analysis includes syntax analysis.

• Syntax analysis includes lexical analysis

• They have no relationship with each other.

22. What is the advantage of using a suballocator in a memory management system?

Answers:

• It allows to have memory chunks of any size

• It obtains large blocks of memory from the system memory manager and allocates the memory to the application in smaller pieces.

• It hides memory leaks from the operating system

• All of the above answers are correct

23. Which of the following options is NOT a technique used in "peephole optimization" of the generated code in a compiler?

Answers:

• Sequential load and store instructions elimination

• Identifying patterns in the instruction stream which are known to be performance gaps

• Constants folding in the memory addresses used by the generated instructions

• Optimization of the generated code by performing branching analysis algorithms which take target machine characteristics into account

24. What is the difference between eq and eql type predicates in Common Lisp?

Answers:

• There are no such type predicates, so the question is incorrect

• eq is true only when tested object are the same identical object and eql is true only when tested objects have the same type and value

• eql is true only when tested objects are the same identical object and eq is true only when tested objects have the same type and value

• eq is a function, whereas eql is a macro.

25. What is the optimal way of copying the contents of one array to another in C language?

Answers:

• By using the memcpy function.

• By using a loop.

• By using a SSE3 instructions for fast memory chunks movement.

• All of the above approaches are equivalent

26. What is the main advantage of using segregated lists usage in the manual memory management?

Answers:

• They keep track of memory leaks in an application

• They allow to allocate memory chunks of any required size

• Memory management systems based on segregated lists are extremely fast

• All of the above

27. What does the following Common Lisp line describes?

(vector 'integer 1234567890)

Answers:

• This is a vector of integer type whose absolute value can not be more than 1234567890

• This is a vector of integers and its tag index is 1234567890

• This is a vector of integers and its length is 1234567890

• This type definition is incorrect

28. What is amortized analysis is used for?

Answers:

• To prove the stability of an algorithm.

• To analyze an algorithm behavior on random input data

• To find out the average algorithm performance in worst case

• None of the above

29. What is a bytecode interpreter?

Answers:

• A program for the vulnerability analysis of a bytecode.

• A program for automatic translation of a bytecode from Unicode to UTF-8.

• A program which executes bytecode instructions.

• All of the above.

30. What is a generated code optimization method which is NOT suitable for use in a compiler?

Answers:

• Code branching prediction

• Constants folding and propagation

• Loop invariant relocation outside

• Common subexpressions elimination in a code blocks

31. What is the fastest way to establish a relationship between two objects?

Answers:

• By using a hash map.

• By using a B-tree.

• By using a binary search tree.

• All of the above

32. What does it mean if when an algorithm "A", belongs to the O(n) algorithms:

Answers:

• That algorithm "A" is not dependent on the input data sequence length.

• That algorithm "A" takes no more than N CPU cycles to execute.

• That algorithm "A" does not use loops.

• None of the above

33. Which of the following sorting algorithms has average speed estimation defined as : O(n)?

Answers:

• Counting sort

• Bucket sort

• Radix sort

• All of the above

34. What is the difference between a general binary search tree and an optimal binary search tree?

Answers:

• An optimal binary search tree can be used only with unique nodes values

• An optimal binary search tree has less average expected search time as compared with a general binary search tree's one.

• An optimal binary search tree can not be used for solving optimization problems.

• All of the above

35. What is a heapsort?

Answers:

• A phase in incremental garbage collection.

• A phase in generational garbage collection.

• A fast and memory-effective sorting algorithm.

• None of the above

36. Is it possible to prove the theoretical stability (that is, prove that a collection algorithm will work as expected) of a garbage collector used in conjunction with C language?

Answers:

• Yes, and in case of all garbage collector types.

• Yes, but only in the case of a generational garbage collector.

• Yes, but only in the case of an incremental garbage collector.

• It is not possible to prove the theoretical stability of any garbage collector type.

37. What is an NP-complete problem?

Answers:

• A problem which can not be solved using a Turing machine

• A problem which cannot be solved quickly.

• A problem which can not be solved without involving neural networks involvement

• None of the above

38. What is the main disadvantage of the bitmapped memory allocation scheme of the manual memory management?

Answers:

• Bitmapped memory allocation scheme belongs to automated memory management methods, so question is incorrect.

• It is extremely hard to code on C and requires a great debugging effort before it starts working.

• Iit causes huge and frequent memory fragmentations.

• It allocates memory too slow.

39. What is the most important problem of the a conservative garbage collector?

Answers:

• It has risk of misidentifying an application data as a heap pointer

• It tends to have memory leaks in its own implementation

• It is not suitable for use with low-level (such as C) languages

• It is the slowest type of garbage collectors

40. What is the difference between a Static Single Assignments graph (SSAG) and a Control Flow Graph (CFG) which are used for the intermediate compiled sources representation in a compiler?

Answers:

• An SSAG is more suitable for a code optimization than a CFG.

• All SSAG graph elements have unique names but CFG ones do not.

• SSAG graph construction is much more complicated than CFG construction.

• All of the above.