REVIEW FOR FINAL:

Topics from text and notes that we have covered this semester and may be covered on final exam

* -- Topics with an asterisk have an extremely high probability of appearing on the final. Other items may also be on final.

Chapter 1 -- Language design issues

Chapter 2 -- Impact of machine architectures

Chapter 3 -- Language translation issues

Chapter 4 -- Modeling language properties

Chapter 5 -- Elementary data types

Chapter 6 -- Encapsulation

Chapter 7 -- Inheritance

Chapter 8 -- Sequence control

Chapter 9 -- Subprograms

Chapter 10 -- Storage Management


Test questions will be similar to questions in: (1) your previous exams, (2) your homeworks, and (3) the sample questions below. The questions on the final may not be identical to any previously given questions but they will be similar in content.

SAMPLE QUESTIONS FOR CHAPTER 9:

  1. For the code segment below state the values of a[1], a[2], and element after completion of the call to whichmode() for each of the following parameter passing mechanisms:
    Mechanism:
    • call by value
    • call by value-result
    • call by reference
    • call by name 
    
   ...
   var element : Integer;
       a: array[1..2] of Integer;

   procedure whichmode(x: ? mode Integer)
      begin
         a[1] := 6;
         element := 2;
         x := x + 3;
      end;

   begin
      a[1] := 6;
      a[2] := 2;
      element := 1;
      whichmode(a[element]);
       ...
  2. List all the variables, along with the program units in which they are declared, that are visible in the bodies of sub1, sub2 and sub3 in the example below, assuming static scoping. 
    
program example;
   var a, b: integer;
        ...
   procedure sub1;
      var x, y : integer;
      begin { sub1 }
          ... 
      end; { sub1 }
   procedure sub2;
      var x : integer;
         ...
      procedure sub3;
         var x: integer;
         begin { sub3 }
            ... 
         end; { sub3 }
      begin { sub2 }
         ... 
      end; { sub2 }
   begin { example }
       ... 
   end. { example }


SAMPLE QUESTIONS FOR CHAPTER 10:

  1. How is a heap element identified as "active" by the garbage collection mechanism if:
    1. reference counts are used
    2. if the mark/sweep algorithm is used?
  2. Describe three strategies for managing the allocation of variable-sized heap storage blocks.
  3. Explain why compaction is necessary.
  4. In the code segment below, identify which variables will be stored on the heap and which will be stored on the stack. 
    
void f(void) {                         
  BigTable  Tom(300) ;     
  BigTable *Jerry ;          
  Jerry = new BigTable(500) ;
}
  5. Identify the pointer anomaly that occurs in each code segment below: 
    1. 
Link *Fun1(void) {
	Link  staticL(200) ;
	Link *dynamoL ;
	dynamoL = new Link(100, &staticL) ;
	return dynamoL ;
}

    2. 
Link *Fun2(void) {
	Link *dynamoL1, *dynamoL2 ;
	dynamoL2 = new Link(200) ;
	dynamoL1 = new Link(100, dynamoL2) ;
	delete dynamoL2 ;
	return dynamoL1 ;
}

    3. 
Link *Fun3(void) {
	Link *DynamoL1, *DynamoL2, *DynamoL3 ;
	DynamoL3 = new Link(300) ;
	DynamoL2 = new Link(200, DynamoL3) ;
	DynamoL1 = new Link(100, DynamoL2) ;
	return DynamoL2 ;
}

    4. 
template  class BigTable {
private:
  int  tsize;        // Size of table
  Elem *table;       // Table pointer
public:
  BigTable(int size = 100)
    { tsize = size ; table = new Elem[tsize]; }
  ~BigTable()
    { delete[] table ; }
	SetLast(Elem& newLast)
	  {table[tsize] = newLast ; }
	… other methods
};


SAMPLE QUESTIONS FOR SPECIFIC PROGRAMMING LANGUAGES:

  1. XML (ok, it may not be a full fledged programming language, but...)
    1. Answer the following questions regarding the XML document given below: 
      
<?xml version="1.0" ?>
<addressbook>
  <contact id="1">
    <firstname>Daisy</firstname>
	<lastname>Flemming</lastname>
	<email>daisyf@stanford.edu</email>
  </contact>
  <contact id="2">
    <firstname>Lois</firstname>
	<lastname>Brooks</lastname>
	<email>lbrooks@stanford.edu</email>
	<address>Meyer 380</address>
	<phone type="office" >650-723-3064</phone>
  </contact>
</addressbook>
      1. What is the root element, and how many root elements can a document have?
      2. How many XML elements does this document have?
      3. Which XML tags contain attributes?
      4. Would the following modification of the document be "well-formed"? 
        
<?xml version="1.0" ?>
<addressbook>
  <contact id="1">
    <firstname>Daisy
	<lastname>Flemming
	<email>daisyf@stanford.edu
  </contact></email></lastname></firstname>
  ...
</addressbook>
    2. Answer the follow questions regarding the DTD given below. 
      
<!ELEMENT pizzas (pizza+)>
   <!ELEMENT pizza (pizza-name, created-by?, description?, crust, 
                    sauce, topping*, cheese+, picture?, review*)> 
      <!ATTLIST pizza pizza-id CDATA #REQUIRED>
      <!ELEMENT pizza-name (#PCDATA)>
      <!ELEMENT created-by (person)>
      <!ELEMENT description (#PCDATA)>
      <!ELEMENT crust (#PCDATA)>
      <!ELEMENT sauce (#PCDATA)>
      <!ELEMENT topping (#PCDATA)>
      <!ELEMENT cheese (#PCDATA)>
      <!ELEMENT picture EMPTY>
         <!ATTLIST picture src CDATA #REQUIRED>
         <!ATTLIST picture width CDATA #REQUIRED>
         <!ATTLIST picture height CDATA #REQUIRED>
         <!ATTLIST picture alt CDATA #REQUIRED>
      <!ELEMENT review (reviewer, rating, date, 
                        review-text)>
         <!ELEMENT reviewer (person)>
         <!ELEMENT rating (#PCDATA)>
         <!ELEMENT date (#PCDATA)>
         <!ELEMENT review-text (#PCDATA)>
      <!ELEMENT person EMPTY>
         <!ATTLIST person fname CDATA #REQUIRED>
         <!ATTLIST person lname CDATA #REQUIRED>
      1. What are the children element of pizza?
      2. Which elements are optional?
      3. Which elements may appear more than once?
      4. Which elements have attributes?


  2. FORTRAN:
    1. What is printed by the following code segments? 
      1. 
     DO 20 i = 2,10,2 
        PRINT *, i 
20 CONTINUE 

      2. 
     DO 20 n = 25,5,-5 
        PRINT *,n 
20 CONTINUE 

      3. 
	PROGRAM Fun
	REAL temp
	PRINT *,'Enter a number'	
	READ *,temp
	PRINT*,'It is ',(temp.gt.80.0),' that the number is greater than 80'
	PRINT*,'It is ',(temp.lt.80.0),' that the number is less than 80'
	STOP
	END
      4. Assume the user enters: 2 
        
      program fun
      real r, t, sum
      integer m
      read (*,*) t
      sum = 0.0
      do 10 m = 1, 5
         sum = sum + r(m, t)
  10  continue
      write (*,*) 'The output is ', sum, 'inches'
      stop
      end

      real function r(m,t)
      integer m
      real t
      r = t + 1.0*m
      if (r .LT. 0) r = 0.0
      return
      end


  3. ADA
    1. What will be printed by the following code segments 
      1. 
count := 0;
while count /= 10 loop
   count := count +1;
   put(count,3);
   new_line;
end loop;

      2. 
for i in reverse 1..10 loop
   put(i,3);
   new_line;
end loop;

      3. 
procedure fun is
   package Int_IO is new Integer_IO(Integer); use Int_IO;
   type ArrayType is array(1..7) of Integer;
   myList : ArrayType := (3,5,2,7,-9,1,-10);
   begin
      Fun2(myList,7);
      for i in 1..7 loop
         put(mylist(i),4);
      end loop;
   end fun;
 
procedure fun1(a,b: in out Integer) is
   temp : Integer := a;
   begin
      a := b;
      b := temp;
   end fun1;

procedure Fun2(list: in out ArrayType; size: in Integer) is
   m : Integer;
   begin
      for i in 1..size-1 loop
         m := i;
         for j in i+1..size loop
            if list(j) < list(m) then
               m := j;
            end if;
         end loop;
         fun1(list(i), list(m));
      end loop;
   end fun2;


  4. SMALLTALK
    1. What is output by each of the following code segments?
      1. Assuming the user types: Object new hello: 5 
        
hello: times
	1 to: times do: [:i | (Transcript show: 'Hello World') cr]
      2. Assuming the user types: Object new hello: 5 say: 'Hi world!' 
        
hello: times say: text
	(times > 100) 
		ifTrue: [ Transcript show: 'You will get bored!']
		ifFalse: [1 to: times do: [:i | (Transcript show: text) cr]]

      3. 
x := 0.
[ (x < 10) ] 
whileTrue: [Transcript show: (x) printString.
            Transcript show: ' '.
            x := x + 1.].

      4. 
1 to: 10 by: 2 do: [:x | Transcript show: (x) printString.
                         Transcript show: ' '.].


  5. PROLOG
    1. What will be printed in the following situations: 
      1. 
bonus(Number) :- Number is 2 + 3.
?- bonus(3).

      2. 
bonus(Number) :- Number is 2 + 3.
?- bonus(X).

      3. 
tape(1,van_morrison,astral_weeks,madam_george).
tape(2,beatles,sgt_pepper,a_day_in_the_life).
tape(3,beatles,abbey_road,something).
tape(4,rolling_stones,sticky_fingers,brown_sugar).
tape(5,eagles,hotel_california,new_kid_in_town).

?- tape(5,Artist,Album,Fave_Song).   

      4. 
tape(1,van_morrison,astral_weeks,madam_george).
tape(2,beatles,sgt_pepper,a_day_in_the_life).
tape(3,beatles,abbey_road,something).
tape(4,rolling_stones,sticky_fingers,brown_sugar).
tape(5,eagles,hotel_california,new_kid_in_town).

?- tape(4,rolling_stones,sticky_fingers,Song). 

      5. 
fun(X) :- red(X), car(X). 
fun(X) :- blue(X), bike(X). 

bike(harley_davidson).
car(ford_escort).
car(vw_beatle).
red(vw_beatle).
red(ford_escort).
blue(harley_davidson). 

?- fun(What).

      6. 
hold_party(X):- birthday(X), happy(X). 
birthday(tom). birthday(fred). birthday(helen). happy(mary). 
happy(jane). happy(helen). 

?- hold_party(Who).

      7. 
function(X,[X|_]).
function(X,[_|T]) :- function(X,T).

?- function(X, [1,2,3])


  6. SML
    1. What will be printed by the following code segments: 
      1. 
fun function1 n = if n = 0 then 1 else n * function1 (n-1);
function1 3;

      2. 
fun function2 [] = 1
 | function2 (fst::rest) = fst * (fnction2 rest);

function2 [1,2,3];

      3. 
fun function3 [] = []
 | function3 (h::t) = function3(t)@[h];  

function3 [1,2,3]

      4. 
fun  function4 [] = 0
  |  function4 (x :: xs) = 1 + function4 xs; 

function4 [1,2,3]


  7. SCHEME
    1. What will be output by the following functions 
      1. 
(cdr (cdr (list 1 2 3)))

      2. 
(define list-1 (list 1 2 3))
(define list-2 (cons 0 list-1))

      3. 
(define function1 (lambda (a l)
    (cond ((null? l) #f)
          ((equal? a (car l)) #t)
          (else (function1 a (cdr l))))))

(function1 1 '(1,2,3))

      4. 
(define (function2 a l)
  (cond ((null? l) l)
	((equal? a (car l)) (function2 a (cdr l)))
	(else (cons (car l) (function2 a (cdr l))))))

(function2 1 '(1,2,3))