#G118. GESP level5 链表
GESP level5 链表
GESP level5 - 链表
- 下面的代码片段用于在双向链表中删除一个节点。请在横线处填入( ),使其能正确实现相应功能。
void deleteNode(DoublyListNode*& head, int value) {
DoublyListNode* current = head;
while (current != nullptr && current->val != value) {
current = current->next;
}
if (current != nullptr) {
if (current->prev != nullptr) {
// 在此处填入代码
}
else {
head = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
delete current;
}
}
{{ select(1) }}
- if (current->next != nullptr) current->next->prev = current->prev
- current->prev->next = current->next
- delete current->next
- current->prev = current->next
- 下面的C++代码用于将字符串保存到带头节点的双向链表中,并对重复的串计数,然后将最新访问的串的节点放在链头便于查找。横线处应填入代码是( )。
typedef struct Node{
string str;
int ref;
struct Node *next,*prev;
}Node;
Node* Insert (Node *pHead, string s) {
Node *p = pHead->next;
Node *q;
while (p) {
if (p->str == s) {
p->ref++;
p->next->prev = p->prev;
p->prev->next = p->next;
break;
}
p = p->next;
}
if (!p) {
p = new Node;
p->str = s;
p->ref = 0;
p->next = p->prev = NULL;
}
// 在此处填入代码
pHead->next = p, p->prev = pHead;
return pHead;
}
{{ select(2) }}
- if(pHead) {p->next = pHead->next, pHead->next->prev = p;}
- if(pHead->next) {p->next = pHead->next, pHead->next->prev = p;}
- p->next = pHead->next, pHead->next->prev = p;
- 触发异常,不能对空指针进行操作。
- 有关下面C++代码的说法正确的是( )。
class Node {
public:
int Value;
Node* Prev;
Node* Next;
Node(int Val, Node* Prv = NULL, Node* Nxt = NULL);
};
Node::Node(int Val, Node* Prv, Node* Nxt) {
this->Value = Val;
this->Prev = Prv;
this->Next = Nxt;
}
int main() {
Node firstNode = Node(10);
firstNode.Next = new Node(100, &firstNode);
firstNode.Next->Next = new Node(111, firstNode.Next);
return 0;
}
{{ select(3) }}
- 上述代码构成单向链表
- 上述代码构成双向链表
- 上述代码构成循环链表
- 上述代码构成指针链表
- 下面C++代码用于排序,下列说法中错误的是( )。
void sortA(int*arr, int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
void sortB(int*arr, int start, int end) {
if (start >= end)
return;
int middle = (start + end) / 2;
sortB(arr, start, middle);
sortB(arr, middle + 1, end);
int leftSize = middle - start + 1;
int rightSize = end - middle;
int*left = new int[leftSize];
int*right = new int[rightSize];
for (int i = 0; i < leftSize; i++)
left[i] = arr[start + i];
for (int j = 0; j < rightSize; j++)
right[j] = arr[middle + 1 + j];
int i = 0, j = 0, k = start;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j])
arr[k++] = left[i++];
else
arr[k++] = right[j++];
}
while (i < leftSize)
arr[k++] = left[i++];
while (j < rightSize)
arr[k++] = right[j++];
delete[] left;
delete[] right;
}
{{ select(4) }}
- 两种排序算法的时间复杂度不同
- 两种排序算法的空间复杂度一致
- sortA的时间复杂度在最好和最坏情况下都是O(n²)
- sortB的平均时间复杂度、最好情况的时间复杂度都是O(n log n),最坏情况的时间复杂度是O(n²)
- 下面关于链表和数组的描述,错误的是( )。 {{ select(5) }}
- 数组大小固定,链表大小可动态调整
- 数组支持随机访问,链表只能顺序访问
- 存储相同数目的整数,数组比链表所需的内存多
- 数组插入和删除元素效率低,链表插入和删除元素效率高
- 在循环单链表中,节点的next指针指向下一个节点,最后一个节点的next指针指向( )。 {{ select(6) }}
- 当前节点
- nullptr
- 第一个节点
- 上一个节点
- 为了方便链表的增删操作,一些算法生成一个虚拟头节点,方便统一删除头节点和其他节点。下面代码实现了删除链表中值为val的节点,横线上应填的最佳代码是( )。
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val) : val(val), next(nullptr) {}
};
void removeElements(LinkedNode* head, int val) {
if (head == nullptr) {
return;
}
LinkedNode* cur;
LinkedNode* dummyHead = new LinkedNode(0); //虚拟头节点
// 在此处填入代码
while (cur->next != nullptr) {
if (cur->next->val == val) {
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
tmp = nullptr;
} else {
cur = cur->next;
}
}
head = dummyHead->next;
delete dummyHead;
dummyHead = nullptr;
}
{{ select(7) }}
- dummyHead->next = head; cur = dummyHead;
- dummyHead->next = head->next; cur = dummyHead;
- dummyHead->next = head; cur = dummyHead->next;
- dummyHead->next = head->next; cur = dummyHead->next;
- 有关下面代码的说法正确的是( )。
#include
class Node {
public:
int Value;
Node* Next;
Node(int Val, Node* Nxt = nullptr) {
Value = Val;
Next = Nxt;
}
};
int main() {
Node* firstNode = new Node(10);
firstNode->Next = new Node(100);
firstNode->Next->Next = new Node(111, firstNode);
return 0;
}
{{ select(8) }}
- 上述代码构成单向链表
- 上述代码构成双向链表
- 上述代码构成循环链表
- 上述代码构成指针链表
- 小杨采用如下双链表结构保存他喜欢的歌曲列表:
struct dl_node {
string song;
dl_node* next;
dl_node* prev;
};
小杨想在头指针为head的双链表中查找他喜欢的某首歌曲,采用如下查询函数,该操作的时间复杂度为( )。
dl_node* search(dl_node* head, string my_song) {
dl_node* temp = head;
while (temp != nullptr) {
if (temp->song == my_song) {
return temp;
}
temp = temp->next;
}
return nullptr;
}
{{ select(9) }}
- O(1)
- O(n)
- O(log n)
- O(n²)
- 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲,他将其作为链表的第一首歌曲,则下面横线上应填入的代码为( )。
void insert(dl_node *head, string my_song) {
p = new dl_node;
p->song = my_song;
p->prev = nullptr;
p->next = head;
// 在此处填入代码
head = p;
}
{{ select(10) }}
- head->next->prev = p;
- head->next = p;
- head->prev = p;
- 触发异常,不能对空指针进行操作。
- 假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为head和tail,链表中每个结点有两个指针域prev和next,分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表,横线上应填的最佳代码是( )。
// 链表结点
template
struct ListNode {
T data;
ListNode* prev;
ListNode* next;
// 构造函数
explicit ListNode(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}
};
struct LinkedList {
ListNode* head;
ListNode* tail;
};
void InitLinkedList(LinkedList* list) {
list->head = new ListNode;
list->tail = new ListNode;
// 在此处填入代码
};
{{ select(11) }}
- list->head->prev = list->head; list->tail->prev = list->head;
- list->head->next = list->tail; list->tail->prev = list->head;
- list->head->next = list->tail; list->tail->next = list->head;
- list->tail->next = nullptr; list->head->next = list->tail;
- 链表不具备的特点是( )。 {{ select(12) }}
- 可随机访问任何一个元素
- 插入、删除操作不需要移动元素
- 无需事先估计存储空间大小
- 所需存储空间与存储元素个数成正比
- 双向链表中每个结点有两个指针域prev和next,分别指向该结点的前驱及后继结点。设p指向链表中的一个结点,它的前驱结点和后继结点均非空。要删除结点p,则下述语句中错误的是( )。 {{ select(13) }}
- p->next->prev = p->next; p->prev->next = p->prev; delete p;
- p->prev->next = p->next; p->next->prev = p->prev; delete p;
- p->next->prev = p->prev; p->next->prev->next = p->next; delete p;
- p->prev->next = p->next; p->prev->next->prev = p->prev; delete p;