” CSCI 2100B编程 辅导、C++程序语言 写作CSCI 2100B Data StructuresAssignment 2Due Date: 16 March 2021Written Exercises1. Write the following function that Makes use of the listADT of list of integers:listADT moveMinToHead(listADT);which moves the minimum Element in the list to the head of the list if the argumentlist is nonempty, or returns an empty list otherwise. For examples,? moveMinToHead([]) = []? moveMinToHead([3,4,8,2,4]) = [2,3,4,8,4]? moveMinToHead([3,5]) = [3,5]? moveMinToHead([7]) = [7]a) Write this function as a recursive function. Hint: Call moveMinToHead with the tailas the argument.b) Write this function as a Nonrecursive function.2. Write the following function that sorts the argument list into ascending order byselection sort:listADT selectionSort(listADT);Hint: Make use of the moveMinToHead function.3. Use the selection sort algorithm to sort the following sequence of integers intoascending order:1, 8, 6, 6, 5, 7, 9Show clearly each step in the process of sorting.4. Write the following functions As recursive functions in C. You should use the listoperations defined in list ADT shown in the lecture notes. You can simply callexit(EXIT_FAILURE) when error conditions are encountered. Note that your functionsshould work well with any correct implementation of list ADT.a) The function listIsSorted that accepts a listADT argument and returns an int value1 if the argument list is sorted, or 0 otherwise. For examples: listIsSorted([7,8,1,5,3]) = 0 listIsSorted([4,5,6,7]) = 1 listIsSorted([0]) = 1 listIsSorted([]) = 1b) The function lastButOne that Accepts a listADT argument and returns an int valuethat is the last-but-one value in the list. For examples: lastButOne([3,4,8,2,4]) = 2 lastButOne([0,1]) = 0 lastButOne([]) = ERROR lastButOne([4]) = ERRORc) The function member that accepts an int argument and a listADT argument, andreturns an int value true if The int argument is in the listADT argument, or 0otherwise. For examples: member(2, [3,4,8,2,4]) = 1 member(4, [3,5]) = 0d) The function firstN that accepts a listADT argument and an int argument N, andreturns a listADT value that Is the list of the first N elements of the argument, untilthe end of the list. For examples: firstN([3,4,8,2,4], 3) = [3,4,8] firstN([2,4,6], 8) = [2,4,6] firstN([], 0) = [] firstN([], 1) = [] firstN([8,7,6], 3) = [8,7,6]e) The function evenOnly that accepts an int argument and a listADT argument, andreturns a listADT result that is the Same as the List argument, except that all theodd numbers are removed. For examples: evenOnly([3,4,8,2,4]) = [4, 8, 2, 4] evenOnly([3,5]) = [] evenOnly([2,8,4]) = [2, 8, 4] evenOnly([]) = []f) The function listsAreDifferent that accepts two listADT arguments, and returns anint value 1 if the listADT arguments are different, or 0 otherwise. For examples: listsAreDifferent([], [3,4,8,2,4]) = 1 listsAreDifferent([2], []) = 1 listsAreDifferent([], []) = 0 listsAreDifferent([39,3,8,12,3], [39,3,8,11,3]) = 1 listsAreDifferent([39,3,8,12,3], [39,3,8,12,3]) = 05. In the implementation version 2.0 of list ADT, we use a linked list-basedimplementation of lists. On Page 13 of lecture notes LN6-2a, we show list1 and list2after a few statements are executed. For each of the code segments shown below,show the linked list-based implementation of lists list1, list2 and list3 after all thestatements in the code segment are executed (you should assume that list1, list2 andlist3 are all properly declared as listADT variables). You should also indicate what willbe outputted from each of the code segments that contain printf statements.a) list1 = Cons(4, Cons(5, Cons(6, EmptyList())));list2 = Cons(Head(list1), list1);b) list1 = Cons(3, Cons(7, Cons(6, EmptyList())));list2 = Cons(Head(list1), Tail(list1));list3 = Cons(0, list2);c) listElementT firstElement, secondElement;list1 = Cons(8, Cons(4, Cons(7, EmptyList())));firstElement = Head(list1);secondElement = Head(Tail(list1));list3 = Cons(secondElement, Tail(Tail(list1)));list2 = Cons(secondElement, Cons(firstElement, list3));d) if (listEqual(EmptyList(), EmptyList()))printf(listEqual(EmptyList(), EmptyList())\n);elseprintf(Not listEqual(EmptyList(), EmptyList())\n);if (EmptyList() == EmptyList())printf(EmptyList() == EmptyList());elseprintf(EmptyList() != EmptyList());e) list1 = Cons(8, Cons(4, Cons(7, EmptyList())));list3 = Tail(Tail(list1));list2 = Cons(Head(Tail(list1)), Cons(Head(list1), list3));Programming Exercises6. There are two parts in this programming exercise.a) (Part 1) In the lecture notes we have seen how to implement symbol tables usingHash tables. In the version we present in the lecture notes, we use the techniqueof separate chaining to resolve collisions. We shall call this version 1.0.Implement version 2.0 of symtabADT, in which you use quadratic probing (insteadof separate chaining) for collision resolution. You should use F(i)=i2 in yourimplementation. Also you should set the table size at 51. You should use thefollowing hash function.int Hash(char *s, int n) {unsigned long hashcode = 0UL;for (int i=0; s[i]!=\0; i++) hashcode = (hashcode6) + (unsigned long) s[i];return (int) (hashcode % n);}In your implementation, you should use the following definition for structsymtabCDT:typedef struct bucketT {int inUse; // This is 1 if the bucket is in use, or 0 otherwisechar *key;void *value; } bucketT;struct symtabCDT { bucketT bucket[nBuckets]; };where nBuckets is constant 51 defined using #define in symtab.c.You shall need to implement at least four functions: EmptySymbolTable, Enter,Lookup, and ForEachEntryDo.Note: you only need to submit symtab.c that implements version 2.0 ofsymtabADT.b) (Part 2) Prof. Chan is teaching a course that is open to both postgraduate andundergraduate students. Prof. Chan decides to use different scales forpostgraduate and undergraduate students to convert from numeric marks togrades.The class list with marks of individual students is stored in a student data filestudentData.txt. The format of the student data file is shown as follows:218432CHAN TAI MAN78200987CHEUNG MAN MING90217748MAN TAI SUN75216639YEUNG WING KEUNG98A students information is stored in four separate lines in the student data file. Thefirst line is a 6-digit student number, the second line is the students name, andthe third line the students mark (which is an integer). Whether a student is apostgraduate student or an undergraduate student is indicated by his or herstudent number: if the second digit is 0, then the student is a postgraduate student;otherwise, the student is an undergraduate student. The total number of studentsis not known in advance, so you need to read the file until the end of file is reached.There is another file called the data correction file dataCorrection.txt. If there isany mistake in the studentData.txt file, then the correction information willappear in the data correction file for correction purpose. A students informationis stored in two separate lines in the data correction file. The first line is a 6-digitstudent number, and the second line the students correct mark (which is aninteger). We assume that there is only one data correction file for all teachers,that is, it might contain information about a student whose student number doesnot appear in the original student data file. This is because it is actually a correctionfor the student data file of another teacher. If this happens, the you can simplyignore it. The following is an example of the data correction file:In this case the student whose student number is 200100 does not appear in thedata file, so it can be ignored.Write a program that first reads the student data file and then the data correctionfile, and outputs the grades of each of the students in a file. The following is asample output for the above input file (the order is not important).218432 CHAN TAI MANB200987 CHEUNG MAN MINGA217748 MAN TAI SUNB216639 YEUNG WING KEUNGANote 1You must use the following implementation:1. You must first use typedef to define a structure type StudentT for a structurewith 3 fields. The first field sName is a string that stores the name of the student. The second field level is a value of type studentLevelT(studentLevelT level), where studentLevelT is an enum type definedastypedef enum {UG, PG} studentLevelT; The last field mark is an int value (int mark) that stores the studentsexamination mark.2. There is a function char getGrade(StudentT) to determine the grade foreach of the students.The conversion schemes for undergraduates and postgraduates are as follows:Undergraduate Postgraduate87 100 A 90 100 A72 86 B 75 89 B59 71 C 65 74 C50 58 D 65 F 50 FNote 2You should use a symbol table to store the students information in your program.The key is the student IDs. The data stored in the table should be pointers of typeStudentT*, which point to structures of type StudentT. For simplicity, you canassume that the table will never be full.Your program should work well using the symtab.h and symtab.c in the lecturenotes and in Part 1 of the question.Note 3To output the grades of all students, you must use a call back functionvoid displayStudentNameAndGrade(char*, StudentT*)to display all entries in the table (the order is not important). You may use themapping function forEachEntryDo defined in the lecture notes.如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
