#G118. GESP level5 链表

GESP level5 链表

GESP level5 - 链表

  1. 下面的代码片段用于在双向链表中删除一个节点。请在横线处填入( ),使其能正确实现相应功能。
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
  1. 下面的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;
  • 触发异常,不能对空指针进行操作。
  1. 有关下面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) }}

  • 上述代码构成单向链表
  • 上述代码构成双向链表
  • 上述代码构成循环链表
  • 上述代码构成指针链表
  1. 下面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²)
  1. 下面关于链表和数组的描述,错误的是( )。 {{ select(5) }}
  • 数组大小固定,链表大小可动态调整
  • 数组支持随机访问,链表只能顺序访问
  • 存储相同数目的整数,数组比链表所需的内存多
  • 数组插入和删除元素效率低,链表插入和删除元素效率高
  1. 在循环单链表中,节点的next指针指向下一个节点,最后一个节点的next指针指向( )。 {{ select(6) }}
  • 当前节点
  • nullptr
  • 第一个节点
  • 上一个节点
  1. 为了方便链表的增删操作,一些算法生成一个虚拟头节点,方便统一删除头节点和其他节点。下面代码实现了删除链表中值为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;
  1. 有关下面代码的说法正确的是( )。
#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) }}

  • 上述代码构成单向链表
  • 上述代码构成双向链表
  • 上述代码构成循环链表
  • 上述代码构成指针链表
  1. 小杨采用如下双链表结构保存他喜欢的歌曲列表:
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²)
  1. 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲,他将其作为链表的第一首歌曲,则下面横线上应填入的代码为( )。
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;
  • 触发异常,不能对空指针进行操作。
  1. 假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为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;
  1. 链表不具备的特点是( )。 {{ select(12) }}
  • 可随机访问任何一个元素
  • 插入、删除操作不需要移动元素
  • 无需事先估计存储空间大小
  • 所需存储空间与存储元素个数成正比
  1. 双向链表中每个结点有两个指针域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;