CSE 2231 — Midterm Exam #2 Review
The midterm will be similar to the midterms in Software I. It will be a written exam done in class. The topics covered will be everything from SortingMachine up to and including Context-Free Grammars. This also includes topics from labs, homework, and projects. It will not include Recursive-Descent Parsing or Code Generation. You should also be familiar with general ideas of implementing kernel classes, such as the usage of instance variables, the representation, the correspondence, and the convention.
Questions may be on any of these topics, but you are not expected to memorize everything. For example, if a question deals with something from a project, you will be given the relevant information from the project in order to complete the question. As another example, you will not be expected to remember any context-free grammars, but you should be able to understand and interpret a grammar if given one. Additionally, the exam will include the contracts from the API for any components that are needed to answer a question.
Topics:
• SortingMachine
• Sorting Algorithms – Insertion Sort, QuickSort, Heapsort
• Heaps – siftDown, heapify
• Linked Data Structures – Singly-linked List, Doubly-Linked List, Smart Nodes
• Linked List Implementations of Components – Stack, Queue, List
• Trees
• Abstract Syntax Trees
• Program and Statement
• Context-Free Grammars
The format of the exam will have different styles of questions, including true-false, multiple-choice, fill-in-the-blank, diagram drawing, short answer, and coding questions.
Below are some practice questions for the exam.
1. Consider the following grammar that defines a subset of URLs for web addresses. The symbol [a-z] means a|b|c|d|...x|y|z, that is, any lowercase character.
s t a r t → sub . domain . top
sub → www j ?1?
domain → char—seq
top → com j net j ?2?
char—seq → char j char char—seq
char → [ a—z ]
1.1 Suppose the following string is in the langauge of the grammar.
print.osu.org
If this string is in the language, what are the values of ?1? and ?2? in the grammar?
1.2 What are the terminal symbols in the grammar?
1.3 what are the non-terminal symbols in the grammar?
1.4 Which of the following strings are in the langauge defined by the grammar? If they are in the language, draw their derivation tree.
www.osu.com √
www.Mi.net ×
www.a.net √
2. Implement the following pair of methods. The methods convert a program so that any while loops in the program are modified to be infinite while loops (yes, it is a ridiculous method). You should think of what we did when implementing the simplify-if-else method and the rename method from the lectures.
public static void infiniteLoop ( Program p) {
}
public static void infiniteLoop ( Statement s) {
}
3. Draw the abstract syntax tree for the following BL snippet.
WHILE true DO
FindEnemy
infect
IF next -is - friend THEN
HighFive
turn left
ELSE
turnright
END IF
END WHILE
4. Draw the heap that results from heapifying the following array of characters, assuming alpha- betical order. You should interpret the array of characters as a binary tree like in the Heap- Sort project. Remember that buildHeap recursively calls buildHeap on the left and right subtrees and the base case is a single node .
Build the heap for <s, o, f, t, w, a, r, e>
5. Draw the corresponding representation of a doubly-linked list implementation of the following List object with two smart nodes .
<1,2,3>,<4,5>