10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Trạng thái Đã xong

Bắt đầu vào lúc Thứ Tư, 2 tháng 10 2024, 3:26 PM
Kết thúc lúc Thứ Ba, 15 tháng 10 2024, 10:30 PM
Thời gian thực 13 Các ngày 7 giờ
hiện
Điểm 5,00/5,00
Điểm 10,00 trên 10,00 (100%)

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 1/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Câu hỏi 1
Đúng

Đạt điểm 1,00 trên 1,00

Implement methods add, size in template class DLinkedList (which implements List ADT) representing the doubly linked
list with type T with the initialized frame. The description of each method is given in the code.

template <class T>

class DLinkedList {
public:
class Node; // Forward declaration
protected:
Node* head;
Node* tail;
int count;
public:
DLinkedList();
~DLinkedList();
void add(const T &e);
void add(int index, const T &e);
int size();
public:
class Node
{
private:
T data;
Node *next;
Node *previous;
friend class DLinkedList<T>;

public:
Node()
{
this->previous = NULL;
this->next = NULL;
}

Node(const T &data)
{
this->data = data;
this->previous = NULL;
this->next = NULL;
}
};

};

In this exercise, we have include <iostream>, <string>, <sstream> and using namespace std.
For example:

Test Result

DLinkedList<int> list; [0,1,2,3,4,5,6,7,8,9]

int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
cout << list.toString();

DLinkedList<int> list; [9,8,7,6,5,4,3,2,1,0]
int size = 10;
for(int idx=0; idx < size; idx++){
list.add(0, idx);
}
cout << list.toString();

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 2/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS
Answer: (penalty regime: 0, 0, 0, 5, 10 %)

Reset answer

1 template <class T>

2 ▼ void DLinkedList<T>::add(const T& e) {
3 /* Insert an element into the end of the list. */
4 Node *newNode = new Node(e);
5 ▼ if(head == NULL){
6 head = newNode;
7 tail = newNode;
8 }
9 ▼ else{
10 tail->next = newNode;
11 newNode->previous = tail;
12 tail = newNode;
13 }
14
15 count++;
16 }
17
18 template<class T>
19 ▼ void DLinkedList<T>::add(int index, const T& e) {
20 /* Insert an element into the list at given index. */
21 ▼ if(index < 0 || index > count){
22 throw std::out_of_range("Index is out of range!");
23 }
24
25 Node *newNode = new Node(e);
26 ▼ if(index == 0){
27 ▼ if(head == NULL){
28 head = newNode;
29 tail = newNode;
30 }
31
32 ▼ else{
33 newNode->next = head;
34 head->previous = newNode;
35 head = newNode;
36 }
37 }
38 ▼ else if(index == count){
39 tail->next = newNode;
40 newNode->previous = tail;
41 tail = newNode;
42 }
43 ▼ else{
44 Node *current = head;
45 ▼ for(int i=-1; i<index-1;i++){
46 current = current->next;
47 }
48
49 newNode->next = current;
50 newNode->previous = current->previous;
51 current->previous->next = newNode;
52 current->previous = newNode;

Test Expected Got

 DLinkedList<int> list; [0,1,2,3,4,5,6,7,8,9] [0,1,2,3,4,5,6,7,8,9] 

int size = 10;
for(int idx=0; idx < size; idx++){

list.add(idx);
}
cout << list.toString();

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 3/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Test Expected Got

 DLinkedList<int> list; [9,8,7,6,5,4,3,2,1,0] [9,8,7,6,5,4,3,2,1,0] 

int size = 10;
for(int idx=0; idx < size; idx++){
list.add(0, idx);
}
cout << list.toString();

Passed all tests! 

Đúng
Marks for this submission: 1,00/1,00.

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 4/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Câu hỏi 2
Đúng

Đạt điểm 1,00 trên 1,00

Implement methods get, set, empty, indexOf, contains in template class DLinkedList (which implements List
ADT) representing the singly linked list with type T with the initialized frame. The description of each method is given in the
code.

template <class T>

class DLinkedList {
public:
class Node; // Forward declaration
protected:
Node* head;
Node* tail;
int count;
public:
DLinkedList();
~DLinkedList();
void add(const T &e);
void add(int index, const T &e);
int size();
bool empty();
T get(int index);
void set(int index, const T &e);
int indexOf(const T &item);
bool contains(const T &item);
public:
class Node
{
private:
T data;
Node *next;
Node *previous;
friend class DLinkedList<T>;

public:
Node()
{
this->previous = NULL;
this->next = NULL;
}

Node(const T &data)
{
this->data = data;
this->previous = NULL;
this->next = NULL;
}
};

};

In this exercise, we have include <iostream>, <string>, <sstream> and using namespace std.

For example:

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 5/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Test Result

DLinkedList<int> list; 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |
int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
cout << list.get(idx) << " |";
}

DLinkedList<int> list; [2,5,6,3,67,332,43,1,0,9]

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
list.set(idx, value[idx]);
}
cout << list.toString();

Answer: (penalty regime: 0, 0, 0, 5, 10 %)

Reset answer

1 template<class T>
2 ▼ T DLinkedList<T>::get(int index) {
3 /* Give the data of the element at given index in the list. */
4▼ if(index<0 || index>count){
5 throw std::out_of_range("Index is out of range!");
6 }
7
8 Node *current = head;
9▼ for(int i=-1; i<index-1; i++){
10 current = current->next;
11 }
12
13 return current->data;
14 }
15
16 template <class T>
17 ▼ void DLinkedList<T>::set(int index, const T& e) {
18 /* Assign new value for element at given index in the list */
19 ▼ if(index<0 || index>count){
20 throw std::out_of_range("Index is out of range!");
21 }
22
23 Node *current = head;
24 ▼ for(int i=-1; i<index-1; i++){
25 current = current->next;
26 }
27
28 current->data = e;
29 }
30
31 template<class T>
32 ▼ bool DLinkedList<T>::empty() {
33 /* Check if the list is empty or not. */
34 return count==0;
35 }
36 
37 template<class T>
38 ▼ int DLinkedList<T>::indexOf(const T& item) {
39 /* Return the first index wheter item appears in list, otherwise return -1 */
40 Node *current = head;
41 ▼ for(int i=0; i<count; i++){
42 ▼ if(current->data == item){
43 return i;
44 }
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 6/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS
44 }
45
46 current = current->next;
47 }
48
49 return -1;
50 }
51
52 template<class T>

Test Expected Got

 DLinkedList<int> list; 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 | 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 | 
int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
cout << list.get(idx) << " |";
}

 DLinkedList<int> list; [2,5,6,3,67,332,43,1,0,9] [2,5,6,3,67,332,43,1,0,9] 

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
list.set(idx, value[idx]);
}
cout << list.toString();

Passed all tests! 

Đúng
Marks for this submission: 1,00/1,00.

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 7/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Câu hỏi 3
Đúng

Đạt điểm 1,00 trên 1,00

Implement methods removeAt, removeItem, clear in template class SLinkedList (which implements List
ADT) representing the singly linked list with type T with the initialized frame. The description of each method is given in the
code.

template <class T>

class DLinkedList {
public:
class Node; // Forward declaration
protected:
Node* head;
Node* tail;
int count;
public:
DLinkedList();
~DLinkedList();
void add(const T &e);
void add(int index, const T &e);
int size();
bool empty();
T get(int index);
void set(int index, const T &e);
int indexOf(const T &item);
bool contains(const T &item);
T removeAt(int index);
bool removeItem(const T &item);
void clear();
public:
class Node
{
private:
T data;
Node *next;
Node *previous;
friend class DLinkedList<T>;

public:
Node()
{
this->previous = NULL;
this->next = NULL;
}

Node(const T &data)
{
this->data = data;
this->previous = NULL;
this->next = NULL;
}
};

};

In this exercise, we have include <iostream>, <string>, <sstream> and using namespace std.

For example:

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 8/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Test Result

DLinkedList<int> list; [5,6,3,67,332,43,1,0,9]

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};

for(int idx=0; idx < size; idx++){

list.add(value[idx]);
}
list.removeAt(0);
cout << list.toString();

Answer: (penalty regime: 0 %)

Reset answer

1 template <class T>

2 T DLinkedList<T>::removeAt(int index)
3 ▼ {
4 /* Remove element at index and return removed value */
5 ▼ if(index<0 || index>= count){
6 throw std::out_of_range("Index is out of range!");
7 }
8 Node *current = head;
9 ▼ for(int i=0; i<index; i++){
10 current = current->next;
11 }
12
13 T value = current->data;
14 ▼ if(current->previous){
15 current->previous->next = current->next;
16 }
17 ▼ else{
18 head = current->next;
19 }
20 ▼ if(current->next){
21 current->next->previous = current->previous;
22 }
23 ▼ else{
24 tail = current->previous;
25 }
26 delete current;
27 count--;
28 return value;
29 }
30
31 template <class T>
32 bool DLinkedList<T>::removeItem(const T& item)
33 ▼ {
34 /* Remove the first apperance of item in list and return true, otherwise return false */
35 Node *current = head;
36 ▼ while(current != NULL){
37 ▼ if(current->data == item){
38 ▼ if(current->previous){
39 current->previous->next = current->next;
40 }
41 ▼ else{
42 head = current->next;
43 }
44 ▼ if(current->next){
45 current->next->previous = current->previous;
46 } 
47 ▼ else{
48 tail = current->previous;
49 }
50 delete current;
51 count--;
52 return true;

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 9/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Test Expected Got

 DLinkedList<int> list; [5,6,3,67,332,43,1,0,9] [5,6,3,67,332,43,1,0,9] 

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};

for(int idx=0; idx < size; idx++){

list.add(value[idx]);
}
list.removeAt(0);
cout << list.toString();

Passed all tests! 

Đúng
Marks for this submission: 1,00/1,00.

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 10/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Câu hỏi 4
Đúng

Đạt điểm 1,00 trên 1,00

In this exercise, we will use Standard Template Library List (click open in other tab to show more) to implement a Data Log.

This is a simple implementation in applications using undo and redo. For example in Microsoft Word, you must have nodes
to store states when Ctrl Z or Ctrl Shift Z to go back or forward.

DataLog has a doubly linked list to store the states of data (an integer) and iterator to mark the current state. Each state is
stored in a node, the transition of states is depicted in the figure below.

Your task in this exercise is implement functions marked with /* * TODO */.

class DataLog
{
private:
list<int> logList;
list<int>::iterator currentState;

public:
DataLog();
DataLog(const int &data);
void addCurrentState(int number);
void subtractCurrentState(int number);
void save();
void undo();
void redo();

int getCurrentStateData()
{
return *currentState;
}

void printLog()
{
for (auto i = logList.begin(); i != logList.end(); i++) {
if(i == currentState) cout << "Current state: ";
cout << "[ " << *i << " ] => ";
}
cout << "END_LOG";
}
};

Note: Normally, when we say a List, we talk about doubly linked list. For implementing a singly linked list, we use forward list.

We have include <iostream> <list> and using namespace std;

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 11/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

For example:

Test Result

DataLog log(10); [ 10 ] => Current state: [ 25 ] => [ 40 ] => END_LOG

log.save();
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.undo();
log.printLog();

DataLog log(10); [ 10 ] => [ 25 ] => [ 40 ] => Current state: [ 35 ] => END_LOG

log.save();
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.save();
log.subtractCurrentState(5);
log.printLog();

Answer: (penalty regime: 0, 0, 0, 5, 10 %)

Reset answer

1 DataLog::DataLog()
2▼ {
3▼ /*
4 * TODO: add the first state with 0
5 */
6 logList.push_back(0);
7 currentState = logList.begin();
8 } 
9
10 DataLog::DataLog(const int &data)
11 ▼ {
12 ▼ /*
13 * TODO: add the first state with data
14 */
15 logList.push_back(data);
16 currentState = logList begin();
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 12/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS
16 currentState logList.begin();
17 }
18
19 void DataLog::addCurrentState(int number)
20 ▼ {
21 ▼ /*
22 * TODO: Increase the value of current state by number
23 */
24 *currentState += number;
25 }
26
27 void DataLog::subtractCurrentState(int number)
28 ▼ {
29 ▼ /*
30 * TODO: Decrease the value of current state by number
31 */
32 *currentState -= number;
33 }
34
35 void DataLog::save()
36 ▼ {
37 ▼ /*
38 * TODO: This function will create a new state, copy the data of the currentState
39 * and move the currentState Iterator to this new state. If there are other states behind the
40 * currentState Iterator, we delete them all before creating a new state.
41 */
42
43 auto it = currentState;
44 ++it;
45 logList.erase(it, logList.end());
46
47 logList.push_back(*currentState);
48 currentState = --logList.end();
49 }
50
51 void DataLog::undo()
52 ▼ {

Test Expected Got

 DataLog log(10); [ 10 ] => Current state: [ 25 ] => [ [ 10 ] => Current state: [ 25 ] => [ 
log.save(); 40 ] => END_LOG 40 ] => END_LOG
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.undo();
log.printLog();

 DataLog log(10); [ 10 ] => [ 25 ] => [ 40 ] => Current [ 10 ] => [ 25 ] => [ 40 ] => Current 
log.save(); state: [ 35 ] => END_LOG state: [ 35 ] => END_LOG
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.save();
log.subtractCurrentState(5);
log.printLog();

Passed all tests! 

Đúng
Marks for this submission: 1,00/1,00. 

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 13/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Câu hỏi 5
Đúng

Đạt điểm 1,00 trên 1,00

Given the head of a doubly linked list, two positive integer a and b where a <= b. Reverse the nodes of the list from
position a to position b and return the reversed list

Note: the position of the first node is 1. It is guaranteed that a and b are valid positions. You MUST NOT change the val
attribute in each node.

struct ListNode {
int val;
ListNode *left;
ListNode *right;
ListNode(int x = 0, ListNode *l = nullptr, ListNode* r = nullptr) : val(x), left(l), right(r) {}
};

Constraint:
1 <= list.length <= 10^5
0 <= node.val <= 5000
1 <= left <= right <= list.length

Example 1:
Input: list = {3, 4, 5, 6, 7} , a = 2, b = 4
Output: 3 6 5 4 7

Example 2:
Input: list = {8, 9, 10}, a = 1, b = 3
Output: 10 9 8

For example:

Test Input Result

int size; 5 3 6 5 4 7
cin >> size; 3 4 5 6 7
int* list = new int[size]; 2 4
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list; 

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 14/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Test Input Result

int size; 3 10 9 8
cin >> size; 8 9 10
int* list = new int[size]; 1 3
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list;

Answer: (penalty regime: 0 %)

Reset answer

1 ▼ /*
2 ▼ struct ListNode {
3 int val;
4 ListNode *left;
5 ListNode *right;
6 ListNode(int x = 0, ListNode *l = nullptr, ListNode* r = nullptr) : val(x), left(l), right(r) {}
7 };
8 */
9
10 ▼ ListNode* reverse(ListNode* head, int a, int b) {
11 //To Do
12 if(!head || a==b) return head;
13
14 ListNode* dummy = new ListNode(0);
15 dummy->right = head;
16 head->left = dummy;
17
18 ListNode* prev = dummy;
19 ▼ for(int i=1; i<a; ++i){
20 prev = prev->right;
21 }
22
23 ListNode* const start = prev->right;
24 ListNode* then = start->right;
25
26 ▼ for(int i=0; i<b-a; ++i){
27 start->right = then->right;
28 if(then->right) then->right->left = start;
29 then->right = prev->right;
30 prev->right->left = then;
31 prev->right = then;
32 then = start->right;
33 }
34
35 head = dummy->right; 
36 head->left = nullptr;
37 delete dummy;
38 return head;
39 }

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 15/16
10/23/24, 3:01 PM Doubly Linked List: Xem lại lần làm thử | BK-LMS

Test Input Expected Got

 int size; 5 3 6 5 4 7 3 6 5 4 7 
cin >> size; 3 4 5 6 7
int* list = new int[size]; 2 4
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list;

 int size; 3 10 9 8 10 9 8 
cin >> size; 8 9 10
int* list = new int[size]; 1 3
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list;

Passed all tests! 

Đúng
Marks for this submission: 1,00/1,00.

https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4307063&cmid=442755 16/16