Question 3. (ADT) Instructor of a certain course maintains records of the studen

Question

Question 3. (ADT) Instructor of a certain course maintains records of the students attending the course, in a record keeping system. Each student’s record stores the information about a student: student’s name, id number, number of lectures attended, and the grades for two midterms and the final examination. At the start of the semester the instructor receives a sorted list of students for the course, from the registrar ( ). During the semester, no new students are added to the list or deleted from it. The only operations, the instructor performs on the student’s records is to access them often to check or update the record. (i) What is the most suitable ADT for implementing the record keeping system and why? (ii) Give the specification for the ADT. (iii) Give an implementation for the ADT.

Question 5. (Lists)
Modify the ADT List (linked) implementation to add an operation/method length() that returns the number of elements in the list. The operation should be (i) O(n) (ii) O(1).

Explanation / Answer

Q.3

1) Hash set, Will be good option to store the records.

2) As underlying data structure is hashmap. So on average time complexity for add, remove and look-up (contains method) operation of HashSet takes O(1) time.

3) Below is how it can be implemented the idea, it may have syntax errors.

Q5. i)

We can do in O(n) simply by traversing through the linked list.

ii) if we need to find length in O(1), the idea can be that we add a length variable in the head of the linked list which if global and inserts _node function can access it, so whenever a node is added that variable counter is increased by 1. So when we want to know the length of the list just see that variable in the head of the linked list.

class Node
{
int data;
Node next;
Node(int d) { data = d; next = null; }
}

class Node_head
{
int data;
int length;
Node next;
Node(int d) { data = d; next = null; length=0 }
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.