CS 326 STUDY GUIDE 2025/2026 QUESTIONS AND
SOLUTION RATED A+
✔✔code improvement - ✔✔optimizes into a new version with more efficiency
✔✔Chomsky hierarchy: - ✔✔form of language classification
-regular vs. context free languages
-regular grammar vs. context-free grammar
-finite vs. pushdown automaton
-scanning vs. parsing phase
✔✔regular languages are a subset of: - ✔✔context free languages
✔✔Formal language - ✔✔set of strings of symbols drawn from a finite alphabet
✔✔What is an ambiguous grammar? - ✔✔one string has multiple parse trees
✔✔What does a regular expression do? - ✔✔defines what tokens are valid in a
programming language
✔✔regular expression options - ✔✔character, empty string, concatenation, alternation,
repetition 0 or more times
✔✔Scheme Program structure - ✔✔all expressions
- atoms: numbers, strings, identifiers, characters, booleans
- lists: sequences of expressions separated by spaces
Ex: list -> ( expr_seq )
✔✔What is does the quote do in Scheme? - ✔✔use the quote to prevent evaluation
✔✔How to force evaluation in Scheme? - ✔✔eval
✔✔What are special forms? - ✔✔they have different rules regarding whether/how
arguments are evaluated
Ex: define/quote
✔✔cons - ✔✔returns a list built from head and tail
✔✔car - ✔✔returns first member of a list (head)
✔✔cdr - ✔✔returns the list without its first member (tail)
✔✔null? - ✔✔returns if list is null
, ✔✔list - ✔✔returns a list built from its arguments
✔✔length - ✔✔returns length of a list
✔✔reverse - ✔✔returns the list reversed
✔✔append - ✔✔returns the concatenation of the lists received as arguments
✔✔How can you check the type of an argument? - ✔✔argument_type?
✔✔and, or - ✔✔evaluate arguments only as needed
✔✔form of if: - ✔✔(if <test_exp> <then_exp> <else_exp>)
✔✔form of cond: - ✔✔(cond
(<test_exp1> <exp1> .. )
(<test_exp2> <exp2> .. )
(else <exp> ...))
✔✔lambda expression - ✔✔An expression used to define an anonymous function (a
function without a name)
(lambda (id1 id2 ...) exp1 exp2 ...)
- can't reuse the function, but useful to return a function from another function
✔✔define - ✔✔allows you to bind a name to a function, so that it can be reused
✔✔member? - ✔✔checks if an element exists in a list
✔✔input-output commands in Scheme: - ✔✔read and display
✔✔How to make local definitions in Scheme? - ✔✔let
✔✔General rules for recurrence in Scheme: - ✔✔− When recurring on a list lst, ask two
questions about it: (null? lst) and else
− When recurring on a number n, ask two questions about it: (= n 0)and else
− When recurring on a list lst, make your recursive call on (cdr lst)− When recurring on a
number n, make your recursive call on (- n 1)
✔✔first-class object - ✔✔can be passed as an argument to another function, it can be
returned as a result from another function, and it can be created dynamically
✔✔higher-order function - ✔✔it takes a function as a parameter, or returns a function as
a result
SOLUTION RATED A+
✔✔code improvement - ✔✔optimizes into a new version with more efficiency
✔✔Chomsky hierarchy: - ✔✔form of language classification
-regular vs. context free languages
-regular grammar vs. context-free grammar
-finite vs. pushdown automaton
-scanning vs. parsing phase
✔✔regular languages are a subset of: - ✔✔context free languages
✔✔Formal language - ✔✔set of strings of symbols drawn from a finite alphabet
✔✔What is an ambiguous grammar? - ✔✔one string has multiple parse trees
✔✔What does a regular expression do? - ✔✔defines what tokens are valid in a
programming language
✔✔regular expression options - ✔✔character, empty string, concatenation, alternation,
repetition 0 or more times
✔✔Scheme Program structure - ✔✔all expressions
- atoms: numbers, strings, identifiers, characters, booleans
- lists: sequences of expressions separated by spaces
Ex: list -> ( expr_seq )
✔✔What is does the quote do in Scheme? - ✔✔use the quote to prevent evaluation
✔✔How to force evaluation in Scheme? - ✔✔eval
✔✔What are special forms? - ✔✔they have different rules regarding whether/how
arguments are evaluated
Ex: define/quote
✔✔cons - ✔✔returns a list built from head and tail
✔✔car - ✔✔returns first member of a list (head)
✔✔cdr - ✔✔returns the list without its first member (tail)
✔✔null? - ✔✔returns if list is null
, ✔✔list - ✔✔returns a list built from its arguments
✔✔length - ✔✔returns length of a list
✔✔reverse - ✔✔returns the list reversed
✔✔append - ✔✔returns the concatenation of the lists received as arguments
✔✔How can you check the type of an argument? - ✔✔argument_type?
✔✔and, or - ✔✔evaluate arguments only as needed
✔✔form of if: - ✔✔(if <test_exp> <then_exp> <else_exp>)
✔✔form of cond: - ✔✔(cond
(<test_exp1> <exp1> .. )
(<test_exp2> <exp2> .. )
(else <exp> ...))
✔✔lambda expression - ✔✔An expression used to define an anonymous function (a
function without a name)
(lambda (id1 id2 ...) exp1 exp2 ...)
- can't reuse the function, but useful to return a function from another function
✔✔define - ✔✔allows you to bind a name to a function, so that it can be reused
✔✔member? - ✔✔checks if an element exists in a list
✔✔input-output commands in Scheme: - ✔✔read and display
✔✔How to make local definitions in Scheme? - ✔✔let
✔✔General rules for recurrence in Scheme: - ✔✔− When recurring on a list lst, ask two
questions about it: (null? lst) and else
− When recurring on a number n, ask two questions about it: (= n 0)and else
− When recurring on a list lst, make your recursive call on (cdr lst)− When recurring on a
number n, make your recursive call on (- n 1)
✔✔first-class object - ✔✔can be passed as an argument to another function, it can be
returned as a result from another function, and it can be created dynamically
✔✔higher-order function - ✔✔it takes a function as a parameter, or returns a function as
a result
