=========================preview======================
(comp251)[2009](f)midterm~ph_wdg^_10184.pdf
Back to COMP251 Login to download
======================================================
COMP 251 2009 Fall Semester Midterm Exam

Date Friday, Oct 16, 2009 Time 7:00-9:00pm Instructions: (a) This exam has 6 questions. You have 120 minutes.
(b)
Attempt ALL questions.

(c)
The total mark is 100.

(c)
Write ALL answers in the exam book. Do not use any other papers.


Name: Student ID: Questions 1. Mark
Lab Section: 2.
3.
4.
5.
6.

Total:

datatype tree = empty_tree | leaf of string | node of (string * tree * tree);
(*display1*)
fun display1(empty_tree) = ""
| display1(leaf(x)) = x
| display1(node(x,L,R)) = x ^ display1(L) ^ display1(R);
(*display2*)
fun display2(empty_tree) = ""
| display2(leaf(x)) = x
| display2(node(x,L,R)) = display2(L) ^ display2(R) ^ x;
(*display3*)
fun display3(empty_tree) = ""
| display3(leaf(x)) = x
| display3(node(x,L,R)) = "(" ^ display3(L) ^ x ^ display3(R) ^ ")";
val t = node("+",node("*",leaf("a"),leaf("b")),leaf("c"));
(a)
display1(t);

(b)
display2(t);

(c)
display3(t);

datatype treeInt = leaf | node of (int * treeInt * treeInt);

(a)
(*insert*) fun insert(leaf,x) = node(x,leaf, leaf) | insert(node(x,L,R),y) = if x = y then node(x,L,R)

else if x > y then node(x,insert(L,y),R) else node(x,L,insert(R,y));

(b)
(*valuef*)

fun valuef(node(x, L,R), f) = if R = leaf then f(x) else valuef(R, f);

(c)
(*deleteMax*)


fun deleteMax(node(x,L,R)) = if R = leaf then L else node(x,L,deleteMax(R));
(a)
exist (v, L) = fn : a * a list -> bool. It returns true if v is an ele-ment in L and false otherwise.

(b)
elementAt (i, L) = fn : int * a list -> a. It returns the element at index i of L if i is between 0 and length(L)-1; otherwise, it raises exception NotFound. Element at index 0 is the .rst element in L, element at index 1 is the second element in L, and so on. You can use length(L), an SML built-in function fn : a list -> int, which returns the number of elements of L.

(c)
removeAt (i, L) = fn : int * a list -> a list. If there is no element at index i of L, it returns the original L; otherwise, it returns L with the element at index i removed. Element at index 0 is the .rst element in L, element at index 1 is the second element in L, and so on.

(d)
indexOf(v, L) = fn : a * a list -> int. If v is an element in L, it returns the index (ranged from 0 to length(L)-1) of the .rst occurrence of v in L; otherwise, it raises exception NotFound.


<S>:= <A><S><A> |a <A>:= a|b
(a)
Generate all strings of length less than 6 using this grammar.

(b)
Determine whether string bababab belongs to the language this grammar generates. If your answer is yes, draw a parse tree for the string. If your answer is no, just say so, and no explanation is needed.


1.
Both TRUE and FALSE are boolean expressions.

2.
if A and B are boolean expressions, then A or B, A and B, not A, A if B, A i. B are boolean expressions as well.


In decreasing order,