CS1311 Spring 2001 Assignment 8 141 points due 09:00:00 AM March 2nd, 2001 Please make sure that ALL essays, short answers, definitions, and explanations are in your own words. NO credit will be given for answers taken directly from the book, lecture notes, etc... Turn in this assignment electronically using WebCT. ----------------------------------------------------------------------- [p1] 11 points Show the binary search tree that results when you start with an empty tree and insert the following numbers in the order shown [we have already added the first three numbers]: [15, 27, 5], 6, 11, 4, 9, 12, 2, 22, 18, 19, 17, 1 Indicate where each number is located using this diagram. A = 15 | +-----------------------+ | | B = 5 C = 27 | | +-----------+ +-----------+ | | | | D E F G | | | | +-----+ +-----+ +-----+ +-----+ | | | | | | | | H I J K L M N O | | | | | | | | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ | | | | | | | | | | | | | | | | P Q R S T U V W X Y Z AA BB CC DD EE [p2] 5 points Define the necessary data structures for a binary search tree of Students. Each Student will be a record containing the name, student number and numerical calss average. [p3] 5 points Write a module that will ask the user for student data. The module will then fill a Student record with the results and return it to the calling module/algorithm. [p4] 10 points Write a module that will take in a filled Student record and a pointer to the data structure you defined in problem 2 and insert the Student in the correct location sorted by student number. [p5] 5 points Write a module that will take in a filled Student Record and print out the contents of the record. [p6] 5 points Write a module that will traverse a BST of students and print the information of each student record out in order according to student number (using p2 and p5). [p7] 10 points Specify the header, but do not write the code, for a module to delete a Student record (given the student ID) from a binary search tree. Describe the process required, discussing all possible cases and how to deal with each case. [p8] 15 points Write an algorithm that will repeatedly prompts the user for an action and then perform the choice entered in by the user. The choices the user may enter are: 1. Fill a student record (p4) and insert it into the BST (p3) 2. Delete a record from the BST (p7) 3. Print all Students with failing grades 4. Quit and then print out the Students in numerical order based on Student Numbers. Use iteration (and your answer to p3) in your solution. [p9] 15 points a) Define the necessary data structure(s) and create a variable to store an array of 100 Students. b) Write the line of pseudo-code for placing an already filled student record called newStudent in cell 80. c) Write the line of pseudo-code for printing the already filled in Student located in cell 42. [p10] 15 points Write a module that will convert an array of Students (previously populated with Students in random order) into the BST of Students ordered by student number. Use the BST definition from p2, and the array definition from p9. Use helper module(s) where appropriate for good abstraction. [p11] 5 points a. On which data structures are we able to execute binary search? For each, describe why. b. On which data structures MUST we execute simple search? For each, describe why. [p12] 30 points Given the following data definition: COL is 1000 ROW is 4000 NameArray definesa array[1..COL][1..ROW] of String Write a module that will take in an unsorted, already-filled NameArray and a string to find. This module should search for a matching value in the array and return the column and row indices of the first matching cell (i.e. we don't care about duplicates). Use iteration in your solution. Your module should return -1 and -1 if the string is not found in the array. [p13] 10 points a. Explain why a graph is a good way to represent street maps. b. Discuss two reasons why traversing a graph is difficult.