CS440 Final Review

If you are looking for some review material, this might be a good start.

Understand the following terms and the different contexts in which they can occur.

translator
source language
host language
target language
macro processor
conditional translation
compiler
assembler
linker
loader
mode of an expression
absolute
relative
external
object module
executable binary image
symbol table
unsorted linear array
sorted linear array
BST
AVL Tree
Hash Table
Hash Method
Mid Square
Division
Multiplicative
Collision handling
Open Addressing
Linear Probing
primary clustering
secondary clustering
Pseudo-random probing
Radke's Quadratic Residue Search
chaining
Frame
Location
Target
Logical Segments
Relocatable Segments
Absolute Segments
Segment Alignment
Concatenated Segments
Object Record
Implicit Reference
Indexed Reference
Segment Relative
Self Relative

Test Type Questions

  1. Many microprocessors use relative addressing. An example in the 6502 world would be bne top. What impact does relative addressing have upon the characteristics of an object module?
  2. Give two different situations where the mode of an expression is determined to be absolute. Explain why the mode is absolute.
  3. The year is 2008 and you are the lead on a project to write an assembler for a new microprocessor. A yound intern with a BS (from Linfield) in CS working for you produces a design that includes a symbol table that uses an AVL (balanced binary search tree). Is this design acceptable or not and what would you tell this young intern in regard to your decision?
  4. Explain how the mode of an expression is determined. Under what circumstances does an expression produce a value of mode: (a) absolute (b) relative (c) external?
  5. What is one main difference between an object module and a load module?
  6. What would be the advantage (if any) of requiring the programmer to place all entry and extern statements immediately following the title (or name) assembler directive?
  7. Explain what restrictions (if any) are placed on the operand of a db.
  8. Although linking is conceptually different from relocation, the two functions are often combined. Why?
  9. If you separate the two functions, which one of the following statements is true: (a) Linking must come first (b) Relocation must come first (c) Either linking or relocation may come first.
  10. Discuss the differences between segment relative and self relative references.
Will the following C program compile correctly or not?

#include <stdio.h>
main()
{

typedef struct Foo *NODEPTR;
struct Foo
{
  int data;
  NODEPTR ptr;
};

NODEPTR one, two;

one->data = 0;
one->ptr = two;

printf ("%d\n", one->data);
}
If the program compiles correctly, what will be the result of running the program?

Consider the following declarations:

typedef struct BinNode *pBinNode;

struct BinNode
{
  int data;
  pBinNode pLeft, pRight;
};
Write a function VInsert that accepts the pointer to the head of a binary tree and an integer value. Add the integer anywhere in the binary tree. The root pointer will either be NULL or point to a struct of type BinNode.

What will a call to your function look like?

Write the function.