CSCI 431 Final Exam Review

 

The final will include material from previous exams and homeworks, in fact that may be your best study guide.  Below I have compiled a list of topics and sample questions to give you a feel for the depth and breadth of the exam.  You will also be asked to recognize and explain (but not write) code in the

following languages:

        Scheme

        Prolog

        Ada

        Smalltalk

        ML

        PHP

 

 

Topic: Programming language history and Language Paradigms

Sample questions:

 

What are the three components of a language definition?

 

Briefly describe/contrast the following:

  1. A high level language
  2. A low level language

 

For each of the languages below provide the following information:

  1. what paradigm does the language most closely fit
  2. is the language compiled, interpreted or hybrid
  3. approximate year when introduced

Lisp, Pascal, Cobol, C++

 

List and discuss four characteristics of a good programming language.

 

Give an example of a language in each of the following paradigms:

1.        Imperative

2.        Functional

3.        Object oriented

4.        Declarative

 

What are the major contribution(s) of each of the following language?  Examples of contributions are:

·         Support for recursion

·         Introduction of block structure

·         First in a paradigm

·         First formally described syntax

 Fortran, Lisp, Algol

 

Characterize the difference in local variable allocation between Fortran and C.

 

Characterize the difference between an Ada package and a C++ class.

 

Characterize the difference in parameter passing between Fortran and Pascal. 

 

Characterize the differences in referencing of local and non-local variables between Pascal and C. 

 

 

Topic: Syntax including grammars and formal models

Sample Questions:

 

Describe the difference between a Finite State Automata and a Pushdown Automata.

 

Consider the grammar with start symbol <S>:

<S> ::= if ( <E> ) <S> | { <S> <S> } |  <E> ;

<E> ::= a | b | c | <E> + <E> | <E> = <E> | <E> == <E>

Give a syntax diagram, or parse tree, for the following strings.

a + b + c;                                 

if ( a ) { b; c = b; }

 

Give an example of a string in the language of the grammar above that proves that the grammar is ambiguous. Give two different parse trees for that string.

 

Given the context-free grammar for expression:

E -> E + T | T

T-> T * P | P

P -> i | ( E )

where i is a terminal symbol standing for any variable name or literal construct the parse tree for the following expression:

     2 * 3 + 4 * 5

 

The regular expression (a b | b a)*a defines the same language as:

1.        (a b)* (b a)*a

2.        (a | b)* a

3.        (a* |b)* a

4.        all of the above

5.        none of the above

 

Classify the following grammars according to their most restrictive type.

1.                S -> e | aB | bA

                                                             A -> a | aS | bAA

                                                              B -> b | bS | aBB

2.        S - SS | (S) | ()

3.        B -> 0B | 1B | 0 | 1

4.        bABc -> dC | bCd

 

 

Given the regular grammar for binary numbers with an even number of 1's:

B -> 0B | 1P | 0

P -> 0P | 1B | 1

formulate the equivalent FSA and regular expression

 

For the grammar below, which operator has the highest precedence.

          E à   E  #  T  |  T  ^  E  |  T

          T à  F  $  T |  F

          F à (E)  | a

 

        1.  #

        2.  ^

        3.  $

        4. parentheses

        5. both ^  and  $ share the high precedence

 

 

In the grammar of the previous problem, which operators are right associative?

1.                #

2.                ^

3.                $

4.                ^  and $

5.                parenthesis

 

 

Topic: Semantics including axiomatic semantics

Sample Questions:

 

Define weakest pre-condition.

 

State the weakest preconditon for the following assignment statement

 

 A = B / 2 - 1;

 if the postcondition is {A < 10}.

 

State the weakest preconditon for the following selection statement 

                    if (X > 0)
                                 X = X - 1;
            else 
                                 X = X + 1;

if the postcondition is {X > 10}.

 

 

Topic: Compilers verses interpreters

Sample questions:

 

What is the purpose of the "symbol table"?

 

Give a brief description of the functional components of a compiler.

 

 

Topic: Data types and Type Checking

Sample questions:

 

If a language with strong typing, such as Pascal, requires name equivalence what difficulties, if any, would occur trying to call a procedure with the following header?

                FUNCTION MaxElement(A: ARRAY[1..10] OF INTEGER): INTEGER;

What difficulties, if any, would occur if structural equivalence were required?

 

Formulate the machine representation of the following numeric values:

Calculate l-values for:

A[i] given the declaration: A:array [3..10] of real;

A[i][j] given the declaration: A:array [1..10, -5..5] of real;

What problems are associated with unions and variant records?

Name one advantage and one disadvantage of a packed representation.

What is printed by the following C program assuming write simply writes out the values: 

main()
{
   union{ union {int A; real B} C; int D} E[4]; 
          E[1].C.A = 2; 
          E[1].C.B = 3; 
          E[1].D = 4; 
   write(E[1].C.A , E[1].D );
}

 

 

Topic: Binding times

Sample questions:

Explain the meaning of "binding", and "binding time".   

Contrast "static type binding" with "dynamic type binding" making sure that you define each term and mention at least one advantage and one disadvantage of each.

Name 4 attributes that can be associated with an identifier and state their binding times in a language of your choice.

 

Topic: Abstract data types and Object Orientated Programming

Sample questions:

 

How does C++ support encapsulation?

 

How does Ada support encapsulation?

 

Define the term “Abstract Data Type” (ADT).

 

Define all of the following terms:

overloading

encapsulation

                information hiding

abstract data type

friend functions

polymorphism

 

 

In an OO language such as C++, components of a class can be declared public, protected, or private. Do these declarations provide the same function as the private declaration in an ADT? Why do we need three

categories?

 

Consider the following C++ code:

 

   #include <iostream.h>

       class A {

       public:

         A() { i = 1; }

         virtual void print() { cout << i << endl; }

       protected:

         int i;

       };

      

       class B : public A {

       public:

         B() { j = 2; }

         void print() { cout << j << endl; }

       private:

         int j;

       };

      

       void main() {

         A a, *pa, *pc;

         B b, *pb;

         a = b;

         pa = &a;

         pc = &b;

         pa->print();

         pc->print();

       }

 

     (a) What is printed by the program? Briefly explain the result.

 

     (b) What is printed if the word virtual is deleted? Briefly explain the result.

 

 

Topic: Sequence control

Sample questions:

 

Give the (a) Postfix and (b) Prefix forms of the C ­language expression 8 + 4/2 - 5

 

Name 3 problems associated with using infix notation to write expressions.

 

Contrast the implementation of iteration statements in 2 languages.

 

Define the term “Prime Programs”.

 

True or false, is it possible to write any program using only if and while sequence control structures

 

 

Topic: Subprogram control

Sample questions:

 

Consider the following block structured language. 

1.       Procedure A
2.       { int a = 0
3.        
4.          Procedure C
5.          {                   Procedure D
6.                {  print a;
7.                }
8.          Call D
9.          }
10.      Procedure B
11.      {  char a = 'b';
12.      
13.      Call C;
14.      }
15.      Call B;
}

What is printed when A calls B calls C calls D?

    1. 0 for either static or dynamic scoping
    2. 0 if static scoping, 'b' if dynamic scoping
    3. 'b' if static scoping, 0 if dynamic scoping
    4. 'b' if static scoping, 'b' if dynamic scoping
    5. None of the above.

 

In a statically scoped language, when a static link exists from the activation record for procedure A to the the activation record for procedure B, this means

    1. A is nested directly within B
    2. B is nested directly within A
    3. A is nested directly or indirectly within B
    4. B called A
    5. none of the above

 

In a call to a function doit() in which B is the actual parameter, to pass B by name, B is evaluated:
(a) in the called environment (b) in the calling environment (c) at the point of call (d) a single time.

 

C is said to support only one parameter passing mechanism, what is it?  Are there exceptions to this rule?

 

What is a Display vector, and what is the max number of memory accesses needed to retrieve and non-local variable when a Display vector is used?

 

What information is stored in an activation record, list specific items.

 

True or False, when static scoping is used, activation records must contain an environment table listing the names and values of all local variables.

 

What is the "lifetime" of a variable. What is the "scope" of a variable. Give examples of when they are different?

 

In general, statically declared variables are stored in the _________, and dynamically declared variables are stored in the __________.

 

Explain the differences between the following parameter passing

mechanisms:

                pass by value

                pass by result

                pass by value result

                pass by reference

                pass by name

 

 

Topic: Storage management

Sample questions:

 

Describe where and how dangling references and inaccessible storage problems arise in the following code segment.

struct node {

                int v;

                struct node *pt;

}

 

struct  node *x, *y, *z;

int num = 1000;

while (num) {

                x = malloc (sizeof (struct node));

z = malloc (sizeof (struct node));

                y = z;

                z->v = num;

                z->pt = y;

                y = x;

                                free (y);

                                x->pt = z;

                                num--;

}

 

What are the problems associated with recovery of variable-sized memory blocks in garbage collection.

How are "reference counts" used in memory management?

Which statements are true?

    1. C uses the mark­sweep algorithm to clean up the runtime heap.
    2. LISP, ML and Smalltalk all use automatic garbage collection.
    3. If C used reference counts, then dangling references would never occur.

 

Circle all correct answers:

(1)     Dangling references are possible in:

C, C++, LISP

(2)     Garbage collection is a feature in:

C, LISP, Smalltalk, ML

 

The first stage of a mark/sweep garbage collection algorithm is the identification of reachable objects. Discuss the possible implementation of this stage of mark/sweep in LISP.

 

 

Topic: Parallel programming

Sample questions:

 

Explain the differences between the following synchronisation

mechanisms:

                semaphores

                monitors

                message passing

 

Define the following terms:                                                                                                                                         

         mutual exclusion

         synchronization

         critical region

 

Name three approaches to implementing mutual exclusion.

 

Define a binary semaphore.

 

Use semaphore(s) to maintain mutual exclusion and synchronize the tasks below.  That is, indicate the number and kind of semaphores to be used and where the wait and release calls (messages) would occur.

task A; 
begin 
 --prepare first data set 
loop
            input dataset into shared buffer
            --prepare next data set 
   endloop 
end A;
 
task B;
begin
loop
            --Extract data from shared buffer
            --Process the data
endloop;
end B;