CS115 Final Exam Reference Sheet

Warning: You may use built-in functions that do not appear on this Reference Sheet, provided they meet the requirements
of the question and you were permitted to use them on any of the assignments.

Selected String and Character Functions

(char? x) produces true if x is of type char, and false otherwise
(string? x) produces true if x is a string, and false otherwise
(char=? c d) produces true if characters c and d are equal, false if the two characters are
different
(string=? s t) produces true if the strings s and t are character-by-character the same, false if the
two strings differ in some way
(char<? c1 c2) produces true if c1 comes before c2, and false otherwise
(string<? s1 s2) produces true if s1 comes before s2 alphabetically, and false otherwise
(char<=? c1 c2) produces true if c1 equals or comes before c2, and false otherwise
(string<=? s1 s2) produces true if s1 equals or comes before s2 alphabetically, and false otherwise
(char-alphabetic? c) produces true if c is a alphabetic character (upper or lower case), and false if not
(char-numeric? c) produces true if c is a numeric digit, and false if not
(char-lower-case? c) produces true if c is a lowercase letter, false otherwise
(char-upper-case? c) produces true if c is an uppercase letter, false otherwise
(string-alphabetic? s) produces true if all characters in s are alphabetic, false otherwise
(string-numeric? s) produces true if all characters in s are numeric, false otherwise
(string-append s t) produces a string containing all the characters in s followed by all the characters in t
(string-length s) produces the number of characters in string s
(substring s p1 p2) produces the string containing all the characters from index p1 of s up to, but not
including, index p2, where the first character in s is at index 0

Selected List Functions

(cons v lst) constructs a list with first element v followed by list lst
(first lst) produces the first element in the nonempty list lst
(second lst) produces the second element in a list lst with at least 2 elements
(third lst) produces the third element in a list lst with at least 3 elements
(rest lst) produces the rest of the nonempty list lst
(length lst) produces the number of elements in the list lst
(empty? lst) produces true if lst is the empty list, false otherwise

Abstract List Functions

(build-list n f) produces a list of length n, obtained by applying f to 0,1,2,…,n-1
(filter pred lst) produces a list of the elements x in lst for which (pred x) => true
(foldr combine base produces the value of (combine x1 (combine x2 (… (combine xN
lst) base) …))) where lst contains x1,x2,…,xN
(map f lst) produces a list with the same length as lst obtained by applying f to each
element in lst
(andmap pred lst) produces true if pred produces true when applied to all elements in lst,
and false otherwise
(ormap pred lst) produces true if pred produces true when applied to at least one
element in lst, and false otherwise
(sort lst comp) produces sorted version of lst, using comp as comparison function

Other Selected Functions and Special Forms

(integer? x) produces true if x is an integer, false otherwise
(number? x) produces true if x is a number, false otherwise
(abs x) produces absolute value of x
(add1 n) produces n+1
(equal? e1 e2) produces true if e1 and e2 are equal, false otherwise
CS115 Fall 2022 Page 1
(even? x) produces true if x is even, and false otherwise (0 is even)
(expt b p) produces the value of b raised to exponent p
(max x y) produces x if x >= y, and y otherwise
(min x y) produces x if x <= y, and y otherwise
(negative? x) produces true if x < 0, false otherwise
(odd? x) produces true if x is odd, and false otherwise
(positive? x) produces true if x > 0, false otherwise
(quotient n m) produces the quotient when integer n is divided by integer m
(remainder n m) produces the remainder when integer n is divided by integer m
(sqr x) produces the square of x
(sqrt x) produces the square root of x
(sub1 n) produces n-1
(symbol? x) produces true if x is a symbol, and false otherwise
(symbol=? s t) produces true if symbols s and t are equal, false otherwise
(zero? x) produces true if x is 0, and false otherwise
(list->string loc) produces a string containing, in order, the characters in the list loc
(string->list s) produces a list of the characters in string s
(number->string n) produces a string version of the number n
(string->number s) produces the numeric equivalent of the string s if the characters of s form
a number, and false otherwise
(check-expect act exp) test passes if act and exp are equal, fails otherwise
(check-within act exp test passes if |act-exp| <= tol, fails otherwise
tol)

Data Definitions
;; A (listof τ) is one of:
;; * empty
;; * (cons τ (listof τ))

;; A Pair is a (list Str Num)

(define (make-pair key val) (list key val))
(define (pair-key p) (first p))
(define (pair-val p) (second p))

;; An AssociationList (AL) is a (listof Pair)

(define-struct node (key left right))

;; A Node is a (make-node Num BT BT)

;; A Binary Tree (BT) is one of:

;; * empty
;; * a Node

(define-struct node (key left right))

;; A Node is a (make-node Num BST BST)

;; A Binary Search Tree (BST) is one of:

;; * empty
;; * a Node
;; Requires:
;; * In a non-empty tree,
;; - Every key in the left subtree is less than the root key
;; - Every key in the right subtree is greater than the root key

CS115 Fall 2022 Page 2