讲解：C INTRODUCTION TO ALGORITHMS AND PROGRAMMING IIR、R、R

Introduction每道题答案见同名的txt，对每道题都附带了完整的代码void Shift_bigNumber(struct bigNumber N1,struct bigNumber N2,unsigned int R){int i,j;i=0;j=R;while(jdigit[i]=N1.digit[j];i++;j++;}j=0;while(jdigit[i]=N1.digit[j];i++;j++;}if(idigit[i]=’\0’;}}Requirement&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 1 of 14FINAL EXAMINATIONINTRODUCTION TO ALGORITHMS AND PROGRAMMING II03-60-141-01U N I V E R S I T Y O F W I N D S O RS C H O O L O F C O M P U T E R S C I E N C EFall 2009Last Name:First Name:Student ID:P LEASE READ CAREFULLY BEFORE YOU START1. This is a CLOSED book test; no notes, textbooks, calculators orcomputer aids are allowed.2. PRINT your name legibly and clearly with your Student ID in thespace indicated above.3. You will be asked to sign your name, once during the exam (sign-in)and once before leaving the exam room (sign-out).4. Check the correct lecture section that you are registered in above.5. Answer all the questions in the space provided. DO NOT REMOVEany pages or attach any papers to this test or you will void your testand receive a mark of zero. If you need more space please request anadditional exam booklet which MUST be returned with this exampaper with your name and ID clearly written on it.6. You are not allowed to give or receive unauthorized help with yourtest. Any misconduct, as outlined by the Senate bylaw 31 article I,will be reported accordingly. Such misconduct includes anyattempt, by any means whatsoever, to copy answers from otherstudents, or to receive any unauthorized assistance answeringany and all questions.7. Unclear or undocumented code will not be graded and receive amark of zero.8. You have 3 hours to complete this test.9. Final examinations papers are not returned to students.10. You may view your exam paper during the specified date and time tobe posted by your respective instructor.11. Document your code where necessary. (For questions that askyou to write a function, write both prototype and definition, withproper documentation, you do not need to write a main). State allyour assumptions and all header file includes that you may use.Good Luck!I AGREE TO THE ABOVE TERMS AND WILL NEITHER RECEIVENOR GIVE UNAUTHORIZED HELP ON THIS EXAMS IGNATURE D ATEM ARKS :Q1/10Q2/10Q3- A/10Q3- B/10Q4/10Q5/40TOTAL:/90S IGN HERE&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 2 of 14Q1. [10 MARKS] Consider the following definitions:// your code must be scalable#define MAX 10struct bigNumber {char digit[MAX]; // a digit is between ‘0’ and ‘9’ inclusive};Write and document a function called Shift_bigNumber that takes as parameters two bigNumber data types as definedabove named N1 and N2, and a third parameter an unsigned int data type R. The task of the function is to move the digitsof N1 to N2 such that all digits are shifted R times to the left, with the leftmost digits re-entering from the right. (Theexample below is intended to illustrate only – your answer must be general.)For example:// assume the following declarations.struct bigNumber N1={‘2’,’0’,’5’,’7’,’3’,’1’,’4’,’0’,’9’,’1’};struct bigNumber N2;unsigned int R = 4;Shift_bigNumber(N1, N2, R); // N2 will be {‘3’,’1’,’4’,’0’,’9’,’1’,’2’,’0’,’5’,’7’}&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 3 of 14Q2. [10 MARKS] What is the output of the following program? Show your work by carefully drawing the memoryallocations to support your answer.#include #include struct demo {int num1;int num2;struct demo ptrNext;};void main() {int N[]={2,8,2,7,9,-1};int M[]={1,2,3,4,5,6};int n=0;struct demo ptrTemp=NULL;struct demo ptrLast=NULL;struct demo ptrFirst=NULL;while (N[n]!=-1) {ptrTemp = (struct demo)(malloc(sizeof(struct demo)));ptrTemp->num1 = N[n];ptrTemp->num2 = M[n];ptrTemp->ptrNext = NULL;if (n==0) {ptrFirst = ptrTemp;ptrLast = ptrTemp;}else {if (ptrTemp->num >= ptrLast->num) {ptrLast->ptrNext = ptrTemp;ptrLast = ptrTemp;}else {ptrTemp->ptrNext = ptrFirst;ptrFirst = ptrTemp;}}n++;}ptrTemp = ptrFirst;n = 0;while(ptrFirst != NULL) {printf(“%d: %d %d\n”, n, ptrTemp->num1, ptrTemp->num2);ptrTemp = ptrFirst->ptrNext;free(ptrFirst);ptrFirst = ptrTemp;n++;}}OUTPUT:0: 71: 72: 23: 84: 14&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 4 of 14Q3. a. [10 MARKS] Write and Document a self-referential structure definition called “contact” that stores theFirstName (char[41]), LastName (char[41]) and id (int) of a contact in the space provided. Then, complete theprogram as requested by the documentation located inside the program. (Do not use global variables).#include #include #include / Write and document the self-referential structure definition for ‘contact’ below: /————————————————————————————————–————————————————————————————————–————————————————————————————————–————————————————————————————————–————————————————————————————————–————————————————————————————————–void main( ){ / Dynamically create a ‘contact’ record in a SINGLE STATEMENT (including declarations) /————————————————————————————————–————————————————————————————————–/ Initialize the values of the new record to: John Doe, id=10 /—————————————————————————————&mdaC代写 INTRODUCTION TO ALGORITHMS AND PROGRAMMING II代做R实验作业、R编sh;——–————————————————————————————————–————————————————————————————————–————————————————————————————————–/ Create a second record linked to the first one, do this in a SINGLE STATEMENT withoutdeclaring any additional pointer variables /————————————————————————————————–/ Initialize the values of the second record to: Will Smith, id=20 (without declaring newvariables) /————————————————————————————————–————————————————————————————————–————————————————————————————————–————————————————————————————————–/ Call the recursive function PrintList to print all the records to the console (one statement) /————————————————————————————————–/ Call the recursive function ClearList that erases all the records from memory (one statement) /————————————————————————————————–}&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 5 of 14Q3. b-i. [5 MARKS] Develop the recursive function called PrintList as used in program 3a. Write the prototype anddefinition (implementation) with complete documentation. PrintList displays all the records stored in the linked list to thescreen. Use the format: LastName, FirstName ID to display each record.Q3. b-ii. [5 MARKS] Develop the recursive function called ClearList as used in program 3a. Write the prototype anddefinition (implementation) with complete documentation. ClearList erases all the dynamic records from memory.&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 6 of 14Q4. [10 MARKS] Write and document a C function called FindToken that accepts two parameters: a null terminatedcharacter array (string) called S in reference to the string to be searched, and a second string parameter called T. Thestring T is a list of characters (not including the ‘\0’) that are tokens, or characters to be searched for in S. The functionmay not modify either S or K. It will return a character pointer to the position of the first character in K that is found in S,if it is found in S, or NULL otherwise.For example:printf(“%s”, *FindToken(“are exams over yet?”, “zypqt”)); // will display “yet?”&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 7 of 14Q5. [40 MARKS] Write and document a complete C program to satisfy the following requirements.Given a sequential text file that has the following layout where each line is one record containing the following fields(separated by a single space):int sid (any positive integer – a student id)char name[50] (full name of student)float gpa (student grade point average)The file may contain any number of records; however, you may assume that the computer memory is large enough toaccommodate the size of the input file. Each record is on a separate line.You must write a complete C program to include the following features:1. Define a proper structure to accommodate the storage of the records in memory. (call the structure: student)2. Design and declare all variables and functions as appropriate to do the processing as required for this program(You may use global variables).3. Write all necessary code to:a. Read the records from the input file (called “studentlist.dat”)b. Sort all the records by the “sid” field in ascending order. (Hint: use insertion sort while reading)c. Display the results on the screen (ie. standard output, stdout) in descending order.d. Write your results back into the file “studentlist.dat” and thereby overriding its contents, and where therecords are now stored in the file (the results in the file will be in ascending order as shown in theexample below).Given the following sample sequential text file to illustrate:Sample contents of “employeelist.dat” before processing:2 john_doe 4.504 mary_jane 3.103 bob_smith 1.001 britney_spears 5.005 david_letterman 4.30Sample contents of “employeelist.dat” after processing (i.e. after executing theprogram):1 britney_spears 5.002 john_doe 4.503 bob_smith 1.004 mary_jane 3.105 david_letterman 4.30Requirements:- Your program should be able to handle a file with any number of records.- Write all functions necessary and explain the process of your technique (Write your algorithm clearly anddocument your code!)- The full name is stored with an underscore character substituting the space character. When displayed on thescreen however, the underscore character is replaced by a space character.- You may assume that the records have a unique sid.P LEASE USE THE ATTACHED PAGES AND THE OUTLINED GUIDE TO COMPLETE THIS QUESTION&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 8 of 14// #include’s [1 mark]// structure definition [5 marks]// global variables [2 marks]// function prototypes [2 marks]&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 9 of 14// main function (no menu required – just invoke the function calls to// satisfy the request program sequence) [5 marks]&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 10 of 14// Code all necessary functions here [25 marks]&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 11 of 14&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 12 of 14&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 13 of 14&© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.Page 14 of 14转自：http://ass.3daixie.com/2019030627560484.html