110 final 题库加精选2

javaIsTheBest

(define-struct dir (name num-files subs))
;; Dir is (make-dir String Natural ListOfDir)
;; interp. a Directory on a computer, with the name of the directory
;;         the number of files contained in the directory
;;         a list of sub-directories found in the directory

;; ListofDir is one of:
;;  - empty
;;  - (cons Dir ListOfDir)
;; interp. a list of directories

(define SELFIES   (make-dir "Selfies" 853 empty))
(define FIRSTYEAR (make-dir "First Year" 14 empty))
(define HACKATHON (make-dir "Hackathons" 9 empty))
(define UBC       (make-dir "UBC" 14 (list FIRSTYEAR HACKATHON)))

(define PROBLEMSETS (make-dir "Problem Sets" 10 empty))
(define PRACTICE  (make-dir "Practice Exams" 3 (list (make-dir "MT1" 6 empty)
                                                     (make-dir "MT2" 22 empty))))
(define HOMEWORK (make-dir "Homework" 56 (list
                                          (make-dir "Everything else" 4 empty)
                                          (make-dir "CPSC110" 123 (list PROBLEMSETS
                                                                        PRACTICE)))))
(define DOCUMENTS (make-dir "Documents" 156 (list HOMEWORK
                                                  (make-dir "Job" 13 empty))))
(define PICTURES (make-dir "Pictures" 260 (list
                                           (make-dir "Holidays" 28 empty)
                                           UBC
                                           SELFIES)))
(define STUFF (make-dir "My Stuff" 399 (list DOCUMENTS PICTURES)))



#;
(define (fn-for-dir d0)
  (local [(define (fn-for-dir d)
            (... (dir-name d)
                 (dir-num-files d)
                 (fn-for-lod (dir-subs d))))

      (define (fn-for-lod lod)
        (cond [(empty? lod) (...)]
              [else
               (... (fn-for-dir (first lod))
                    (fn-for-lod (rest lod)))]))]
(fn-for-dir d0)))

;Part A
;;=================accumulator with mr + tail==============================
;Design a function consumes a Dir and produces a sum of
;the number of files in that directory combined with the number
;of files in its sub-directories (and their sub-dirs, etc).
;Your solution MUST be tail recursive.

Solution:
;; WebPage -> Natural
;; produce the total number of views for a webpage and its sub-pages
(check-expect (total-files SELFIES) 853)
(check-expect (total-files UBC) (+ 14 14 9))
(check-expect (total-files STUFF) 1970)

;(define (total-files d0) 0) ;stub

;<template as encapsulated function from types with rsf and worklist accumulators>
(define (total-files d0)
  (local [;; rsf is Natural: total files seen so far
          ;; todo is (listof Dir): the dirs that still need to be visited
          (define (fn-for-dir d todo rsf)
            (fn-for-lod (append (dir-subs d) todo) (+ (dir-num-files d) rsf)))

      (define (fn-for-lod todo rsf)
        (cond [(empty? todo) rsf]
              [else
               (fn-for-dir (first todo) (rest todo) rsf)]))]
(fn-for-dir d0 empty 0)))

;PartB
;;=================accumulator with mr + none tail==============================
;Design a function that consumes a Dir and produces a list of the names
;of sub-directories that have more files than their parent directory.

;Note: the directory named "Documents" is considered the parent of the
;directory named "Homework" because the Homework directory is found within
;the Document directory's list of sub-dirs.

;If a directory does not have a parent directory - such as "My Stuff" - or
;the parent is unknown, you may assume the parent contains 0 files.

;NOTE: Your solution does NOT have to be tail-recursive.

;;Solution
;; Dir -> (listof String)
;; produce the names of directories that contain more files than their parent directory
(check-expect (full-dirs UBC) (list "UBC"))
(check-expect (full-dirs PICTURES) (list "Pictures" "Selfies"))
(check-expect (full-dirs PRACTICE) (list "Practice Exams" "MT1" "MT2"))
(check-expect (full-dirs STUFF) (list "My Stuff" "CPSC110" "MT1" "MT2" "Selfies"))

;(define (full-dirs d) empty) ;stub

;<template as encapsulated function from types using cp accumulator>
#;
(define (full-dirs d0)
  (local [;; parent-files is Natural: number of files in current dir's parent
          (define (fn-for-dir d parent-files)
            (if (> (dir-num-files d) parent-files)
                (cons (dir-name d) (fn-for-lod (dir-subs d) (dir-num-files d)))
                (fn-for-lod (dir-subs d) (dir-num-files d))))

      (define (fn-for-lod lod parent-files)
        (cond [(empty? lod) empty]
              [else
               (append (fn-for-dir (first lod) parent-files)
                       (fn-for-lod (rest lod) parent-files))]))]
(fn-for-dir d0 0)))

;PartC Bonus
;;=================none tail -> tail use tandem worklist==============================
;(Try a tail-recursive solution as an extra challenge if you'd like, but
;you will need to use a tandem worklist accumulator)

(define (full-dirs d0)
  (local [;; todo is (listof Dir): todo
          ;; lopfs is  (listof Natural): number of files in current dir's parent
          ;; rsf is (listof String): resull so far
          (define (fn-for-dir d parent-files todo lopfs rsf)
            (if (> (dir-num-files d) parent-files)
                (fn-for-lod (append (dir-subs d) todo)
                            (append (map (lambda (cur) (dir-num-files d)) (dir-subs d)) lopfs)
                            (cons (dir-name d) rsf))
                (fn-for-lod (append (dir-subs d) todo)
                            (append (map (lambda (cur) (dir-num-files d)) (dir-subs d)) lopfs)
                            rsf)))

      (define (fn-for-lod todo lopfs rsf)
        (cond [(empty? todo) (reverse rsf)]
              [else
               (fn-for-dir (first todo)
                           (first lopfs)
                           (rest todo)
                           (rest lopfs)
                           rsf)]))]
(fn-for-dir d0 0 empty empty empty)))

javaIsTheBest

Practice

(require spd/tags)
(require 2htdp/image)

(@htdd Region)
(define-struct single (label weight color))
(define-struct group (color subs))
;; Region is one of:
;;  - (make-single String Natural Color)
;;  - (make-group Color ListOfRegion)
;; interp.
;;  an arbitrary-arity tree of regions
;;  single regions have label, weight and color
;;  groups just have a color and a list of sub-regions
;;
;;  weight is a unitless number indicating how much weight
;;  given single contributes to whole tree

;; All the Ss and Gs are Regions
(define S1 (make-single "A" 20 "red"))
(define S2 (make-single "B" 40 "blue"))
(define S3 (make-single "C" 60 "orange"))
(define S4 (make-single "D" 30 "red"))
(define S5 (make-single "E" 10 "blue"))
(define S6 (make-single "F" 80 "yellow"))

(define G1 (make-group "red"    (list S1 S2 S3)))
(define G2 (make-group "blue"   (list G1 S4)))
(define G3 (make-group "orange" (list S5 S6)))
(define G4 (make-group "black"  (list G2 G3)))

(define (fn-for-region r)
  (local [(define (fn-for-region r)
            (cond [(single? r)
                   (... (single-label r)
                        (single-weight r)
                        (single-color r))]
                  [(group? r)
                   (... (group-color r)
                        (fn-for-lor (group-subs r)))]))

  (define (fn-for-lor lor)
    (cond [(empty? lor) (...)]
          [else
           (... (fn-for-region (first lor))
                (fn-for-lor (rest lor)))]))]

(fn-for-region r)))

Questions

;;
;; Please read over the data definition for a Region provided above,
;; which you have used multiple times this semester.
;;
;; Design a function that consumes a region and produces the names of any
;; single regions that have the same color as one of their ancestors.
;;
;; Ancestor means a parent, or a parent of a parent, or a parent of a parent
;; of a parent, etc.
;;
;; For example, the tree with root G4 should produce (list "A" "B"):
;;  - S1 has the same color (red) as it's parent G1.
;;  - S2 also has the same color (blue) as it's parent's parent, G2.
;;  - No other single regions have the same color as an ancestor
;;
;; Your function MUST NOT BE TAIL-RECURSIVE.
;; Any tail-recursive solutions WILL NOT RECEIVE ANY MARKS
;;

(@HtDF same-as-ancestor)
(@signature Region -> (listof String))
;; produce a list of the names of singles with the same color as an ancestor
(check-expect (same-as-ancestor S1) empty)
(check-expect (same-as-ancestor G1) (list "A"))
(check-expect (same-as-ancestor G3) empty)
(check-expect (same-as-ancestor G4) (list "A" "B"))

(@template Region (listof Region) accumulator)

(define (same-as-ancestor r0)
  ;; acc is (listof Color): list of current region's ancestors' colors
  (local [(define (fn-for-region r acc)
            (cond [(single? r)
                   (if (member? (single-color r) acc)
                       (list (single-label r))
                       empty)]
                  [(group? r)
                   (fn-for-lor (group-subs r) (cons (group-color r) acc))]))

      (define (fn-for-lor lor acc)
        (cond [(empty? lor) empty]
              [else
               (append (fn-for-region (first lor) acc)
                       (fn-for-lor (rest lor) acc))]))]

(fn-for-region r0 empty)))



;;tail recursion
(define (same-color-region r)
  (local [(define-struct wle (region colors))

      (define (next-todo r acc)
        (local [(define (fn child)
                  (make-wle child (cons (group-color r) acc)))]
          (map fn (group-subs r))))

      (define (fn-for-region r acc todo rsf)
        (cond [(single? r)
               (if (member? (single-color r) acc)
                   (fn-for-lor todo (cons (single-label r) rsf))
                   (fn-for-lor todo rsf))]
              [(group? r)
               (fn-for-lor (append (next-todo r acc) todo)
                           rsf)]))

      (define (fn-for-lor todo rsf)
        (cond [(empty? todo) rsf]
              [else
               (fn-for-region (wle-region (first todo))
                              (wle-colors (first todo))
                              (rest todo)
                              rsf)]))]
(fn-for-region r empty empty empty)))