代做CSE 2231 — Midterm Exam #2 Review代做迭代

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>