MCX2                                                                                                                 Math Department
Mr. Gary. Jaye                                                                                                    Danny Jaye, A.P.S.

1999 APCS A Exam: Question 2

 a.           Write function WordIndex, as started below. The array wordList contains numWords
               strings in alphabetical order. If word is already in wordList, then WordIndex should return
               the index of word in wordList. Otherwise, WordIndex should return the index of the first
               string in wordList that comes after word in alphabetical order; it should return numWords if
               word comes after all of the strings in wordList in alphabetical order.

               For example, assume that array wordList is as follows:

               Complete function WordIndex below. Assume that WordIndex is called only with
               parameters that satisfy its precondition.

                   int WordIndex(const apstring & word,
                                 const apvector & wordList, int numWords)
                   // precondition: wordList contains numWords strings in alphabetical
                   //               order, 0 <= numWords < wordList.length()

             b.Write function InsertInOrder, as started below. The array wordList contains numWords
               strings in alphabetical order. If the string word is already in wordList, InsertInOrder
               should not change any of its parameters. Otherwise, it should insert word into wordList in
               alphabetical order (i.e., all values greater than word should be moved one place to the right to
               make room for word), and it should also increment numWords by 1. Assume that
               wordList.length() is greater than numWords.

               In the examples below, numWords = 3 before the following call is made.

                    InsertInOrder("pear", wordList, numWords) 

                             
               In writing InsertInOrder, you may include calls to function WordIndex specified in part
               (a). Assume that WordIndex works as specified, regardless of what you wrote in part (a).

               Complete function InsertInOrder below. Assume that InsertInOrder is called only with
               parameters that satisfy its precondition.

                   void InsertInOrder(const apstring & word,
                                      apvector & wordList, int & numWords)  {
                   // precondition:  wordList contains numWords strings in alphabetical
                   //                order, 0 <= numWords < wordList.length()
                   // postcondition: if word was already in wordList, then wordList and
                   //                numWords are unchanged;
                   //                otherwise, word has been inserted into wordList in
                   //                sorted order, and numWords has been incremented by 1 struct TreeNode