Introduction to Computer Science - Final Exam

1. Describe three test cases you would use, and why you chose them, to test a method which takes a LinkedListNode representing the head of a singly linked list and reverses the list. 

2. Describe two advantages and two disadvantages of using a doubly linked list as opposed to a singly linked list. 

3. Give the definition of a polymorphic (generic) iterator interface. 

4. Describe how a stack may be implemented using a linked list. As part of your answer, provide a sequence of diagrams showing how your data structure changes as values are pushed and subsequently popped. 

5. Briefly explain why recursive methods tend to be seen as less efficient than iterative ones and how tail-call optimization can help overcome the issue. 

6. We sometimes describe a finite-state machine (FSM) as being a black box. What does this mean? What effects does it have? 

7. State the five components that define a finite-state automaton (FSA), explaining the purpose of each and any constraints upon them. 

8. Explain what happens when the basic quick sort algorithm is presented with an already-sorted list. Explain how the median-of-three technique reduces this problem, but why it doesn’t completely eliminate it. 

9. What is meant by the asymptotic best-case space complexity of an algorithm? 

10. What does it mean for two stochastic events to be independent? How does independence simplify the construction of belief networks? 

11. What is a hash function? What is a compression map? Explain in detail how a hash table uses these two functions to retrieve the value associated with a key from storage under the separate chaining approach. 

Section B

1. Recursion and Iteration

(a) Provide two examples of recursive data structures, explaining why they are recursive. 

(b) Briefly explain what would happen if a recursive method had either no base case or an incorrectly formed base case. 

(c) Write a recursive and an iterative implementation of the factorial function which takes a non-negative integer as input. 

(d) Give a definition of a SLLNode class suitable for representing nodes in a singly linked list of Comparable objects. 

(e) Write recursive implementations of the methods shown below.

(i) a length method which establishes the number of nodes in the list starting at head

(ii) a contains method which returns whether the list starting at head contains a particular value, 

(iii) a elementAt method which returns the nth element in the list starting at head or null if there is no such element. 

(f) Write iterative implementations of the methods in (e) above. 

2. Queues and Testing

(a) Write five JUnit tests for the following IQueue interface and explain why you chose each test

You may assume the existence of a queue field which refers to an instance of IQueue. 

(b) Considering that you may wish to test multiple concrete implementations of IQueue, outline a sensible organization of your tests to avoid unnecessary duplication of code. 

(c) Write an array-based implementation of IQueue. 

Section C

1. Finite state automata, grammars, and parsing

(a) Explain what is meant by the following terms:

(i) Terminal symbol (of a grammar)

(ii) Accepting state (of a finite state automaton)

(iii) Recognizer function (in a recursive-descent parser)

(iv) Reducing (in a table-driven parser)

(b) Define a grammar that will accept numbers in binary or hexadecimal. Binary numbers consist of a sequence of the digits 0 and 1 followed by the letter ‘b’ (for example ‘101b’); hexadecimal numbers consist of ‘0x’ followed by a sequence of digits 0—9 and letters a—f (for example ‘0x8fe9’). The grammar should not admit leading zeros in either base.

(c) Grammars often include productions that allow zero or more repetitions of a pattern: for example A ® B* denotes a production for zero or more repetitions of B. Explain how grammars can always do without this “syntactic sugar”, illustrating your answer by re-writing the production to use explicit recursion. Why do grammars typically use the “sugared” notation, even though it is strictly unnecessary? 

(d) What is the process of tokenization? Why is it important? Explain how tokens for identifiers will appear to a parser, and how these identifiers might then be incorporated into a parse tree.

咨询 Alpha 小助手，获取更多课业帮助。