GESP 5级客观题｜链表｜课后作业

考试频率：高频。本卷共 6 题。

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);
}

{{ select(1) }}

• 上述代码构成单向链表
• 上述代码构成双向链表
• 上述代码构成循环链表
• 上述代码构成指针链表

2. 双向链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点 p ，则下述语句中错误的是（ ）。

//A:
p->next->prev = p->next;
p->prev->next = p->prev;
delete p;

//B:
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

//C:
p->next->prev = p->prev;
p->next->prev->next = p->next;
delete p;

//D:
p->prev->next = p->next;
p->prev->next->prev = p->prev;
delete p;

{{ select(2) }}

• A
• B
• C
• D

3. 假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为 head 和 tail ，链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是( )。

// 链表结点
template <typename T>
struct ListNode
{
    T data;
    ListNode *prev;
    ListNode *next;
    // 构造函数
    explicit ListNode(const T &val = T())
        : data(val), prev(nullptr), next(nullptr) {}
};
struct LinkedList
{
    ListNode<T> *head;
    ListNode<T> *tail;
};
void InitLinkedList(LinkedList *list)
{
    list->head = new ListNode<T>;
    list->tail = new ListNode<T>;
    ________________________________ // 在此处填入代码
};

//A:
list->head->prev = list->head;
list->tail->prev = list->head;

//B:
list->head->next = list->tail;
list->tail->prev = list->head;

//C:
list->head->next = list->tail;
list->tail->next = list->head;

//D:
list->head->next = list->tail;
list->tail->next = nullptr;

{{ select(3) }}

• A
• B
• C
• D

4. 单链表中删除某个结点 p (非尾结点)，但不知道头结点，可行的操作是将 p 的值设为 p->next 的值，然后删除 p->next 。

   {{ select(4) }}

• 对
• 错

5. 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌

   曲，则下面横线上应填入的代码为

   void insert(dl_node *head, string my_song) {
   	p = new dl_node;
   	p->song = my_song;
   	p->prev = nullptr;
   	p->next = head;
   	if (head != nullptr) {
   		________________________________ // 在此处填入代码
   	}
   	head = p;
   }
   
   {{ select(5) }}
   
   

• head->next->prev = p;
• head->next = p;
• head->prev = p;
• 触发异常，不能对空指针进行操作。

6. 在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。

   {{ select(6) }}

• 当前节点
• nullptr
• 第一个节点
• 上一个节点