CSci 1901: Practice Exam
  1. (10 points) Write a procedure (precedes el lst) that returns a list of all the elements that immediately precede el in lst. It should work like this:

    STk>(precedes 3 '(1 2 3 6 3 4))
    (2 6)
    STk>(precedes 3 '(1 2 3 2 3 4))
    (2 2)
    STk>(precedes 8 '(1 2 3 6 3 4))

  2. (10 points) Suppose you have defined the following two procedures to append a list to the end of an existing list. The procedures are destructive, in the sense that they are meant to modify the existing list.

    (define (append1! lst new)
      (set! lst (append lst new))
    (define (append2! lst new)
      (set-cdr! (last-pair lst) new)

    Suppose you execute the following:

    STk> (define a (list 1 2 3))
    STk> (define b (list 1 2 3 4))
    STk> (append1! a (list 5 6))
    STk> a
    STk> (append2! b (list 5 6))
    STk> b

    Fill in the dots above. Explain why a and b have the values you have given.

  3. (15 points) Write a procedure delete! that destructively deletes the last item from a non-empty list which contains more than one element (i.e. after deleting the last element the list won't be empty). It should work like this:
    STk> (define a (list 1 2 3))
    STk> (delete! a)
    (1 2)
    STk> (delete! a)

  4. (15 points) You are given two queues implemented with the representation shown in the textbook (pages 260-265). Write a procedure (append-queue! q1 q2) to attach the queue q1 in front of the queue q2. The procedure should return the queue q1 and make the queue q2 empty.

    It is required that you write a procedure whose cost is INDEPENDENT on the length of the queues. Use the predicates/selectors/mutators (empty-queue? queue), (front-queue queue), (front-ptr queue), (rear-ptr queue), (set-front-ptr! queue item), (set-rear-ptr! queue item) from the texbook.

    It should work like this.

    STk> (define q1 (make-queue))
    STk> (insert-queue! q1 'a)
    ((a) a)
    STk> (insert-queue! q1 'b)
    ((a b) b)
    STk> (define q2 (make-queue))
    STk> (insert-queue! q2 'x)
    ((x) x)
    STk> (append-queue! q1 q2)
    ((a b x) x)
    STk> q1
    ((a b x) x)
    STk> q2
    (() x)

  5. (15 points) Write a procedure (translate text table) to return a list of the values in the table table of the keys that are included in the list text. Use the selector (lookup key table) from the textbook to access the entries in the table.

    It should work like this: suppose you are given a table dictionary containing English words as keys and their Italian translation as values. Suppose you are also given a list text of words in English. (translate text dictionary) should return the word for word translation into Italian of text.

    STk> (define dict '(*table* (noodles . pasta) (love . amo) (i . io)))
    STk> (translate '(i love noodles) dict)
    (io amo pasta)

  6. (15 points) Consider the bank account object defined in your textbook on page 223. Add a message split and associated procedure that will create a new account (i.e. a new object), and put half the old account's funds into the new account. The new account will be returned. Show how to modify dispatch and show the procedure needed to split the account. It should work like this:
    STk> (define john (make-account 100)) ;; create new account with $100
    STk> ((john 'deposit) 0)              ;; check balance with a zero deposit
    STk> (define mary ((john 'split)))    ;; split the account in two.
                                          ;; NOTE the double parentheses
    STk> ((john 'deposit) 0)              ;; john is left with half the money.
    STk> ((mary 'deposit) 0)              ;; mary is left with half the money.

  7. (10 points) Write a procedure (make-adder) to return an object that operates like a simple adder. Write the object using message passing style. The object created by make-adder should recognize the following messages:

    Message Argument Definition
    + number adds the number to the current value
    clear!   resets the current value to 0
    show   show the current value

    It should work like this:

    STk> (define calc (make-adder))
    STk> ((calc '+) 18)
    STk> (calc 'show)
    STk> (calc 'clear!)

  8. (10 points) Write a procedure (num-first-actions agenda) to count the number of actions in the first segment of an agenda.

  9. (10 points) Write in Python a function to replace every occurrence of the element old with the element new in the list lst. If the element does not appear in the list the function should return the list unchanged. [Hint: this is easy if you write it using map] It should work like this:

    >>> replace('a','b',['a',2,'c'])
    ['b', 2, 'c']
    >>> replace('a','b',['b',2])
    ['b', 2]

  10. (10 points) Write in Python a function to replace every element in a list with the number 0. It should work like this:
    >>> zero(['a',2,'c'])
    [0, 0, 0]

Copyright: © 2006 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.