首页 › 题库 › GESP编程能力等级认证 › 4.1 单链表

GESP-C++五级 题库

共 36 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

对如下定义的循环单链表,横线处填写( )。

// 循环单链表的结点 
struct Node { 
    int data; // 数据域 
    Node* next; // 指针域 
    Node(int d) : data(d), next(nullptr) {} 
}; 
// 创建一个只有一个结点的循环单链表 
Node* createList(int value) { 
    Node* head = new Node(value); 
    head->next = head; 
    return head; 
} 
// 在循环单链表尾部插入新结点 
void insertTail(Node* head, int value) { 
    Node* p = head; 
    while (p->next != head) { 
        p = p->next; 
    } 
    Node* node = new Node(value); 
    node->next = head; 
    p->next = node; 
} 
// 遍历并输出循环单链表 
void printList(Node* head) { 
    if (head == nullptr) return; 
    Node* p = head; 
    _______________________ //在此处填入代码 
    cout << endl; 
}
A
while (p != nullptr){
	cout << p->data << " ";
	p = p->next;
}
B
while (p->next != nullptr){
	cout << p->data << " ";
	p = p->next;
}
C
do {
	cout << p->data << " ";
	p = p->next;
} while (p != head);
D
for(; p; p=p->next){
	cout << p->data << " ";
}
答案与解析
正确答案:C
遍历循环单链表需从头结点开始,逐个访问每个结点的数据域并移动指针至下一个结点。由于链表为循环结构,终止条件不能依赖指针为空。应以回到头结点作为结束标志。首次访问时头结点必须被处理,因此需先执行输出语句再判断是否回到起点。使用do-while结构可确保至少访问一次头结点,并在每次迭代后更新指针,直到p的下一个结点为头结点时停止。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面关于单链表和双链表的描述中,正确的是( )。

struct DNode { 
    int data; 
    DNode* prev; 
    DNode* next; 
}; 
// 在双链表中删除指定节点 
void deleteNode(DNode* node) { 
    if (node->prev) { 
        node->prev->next = node->next; 
    } 
    if (node->next) { 
        node->next->prev = node->prev; 
    } 
    delete node; 
} 
struct SNode { 
    int data; 
    SNode* next; 
}; 
// 在单链表中删除指定节点 
void deleteSNode(SNode* head, SNode* node) { 
    SNode* prev = head; 
    while (prev->next != node) { 
        prev = prev->next; 
    } 
    prev->next = node->next; 
    delete node; 
}
A
双链表删除指定节点是O(1),单链表是O(1)
B
双链表删除指定节点是O(n),单链表是O(1)
C
双链表删除指定节点是 O(1),单链表是O(n)
D
双链表删除指定节点是O(n),单链表是O(n)
答案与解析
正确答案:C
分析双链表删除操作:已知待删节点地址,通过其prev和next指针直接修改前后节点的链接关系,无需遍历,操作步骤数恒定。分析单链表删除操作:已知待删节点地址,但无法直接获取前驱节点,必须从头节点开始逐个遍历直至找到前驱节点,链接修改依赖遍历过程,操作步骤数与节点位置相关。两种结构的删除操作均涉及指针重连和内存释放,但查找前驱的方式导致时间复杂度机制不同。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

函数 removeElements 删除单链表中所有结点值等于 val 的结点,并返回新的头结点,其中链表头结点为head ,则横线处填写( )

A

Node* del = cur;

cur = DEL->NEXT;

删除 Del;

B

Node* del = cur->next;

cur->next = del;

delete del;

C

Node* del = cur->next;

cur->next = del->next;

delete del;

D

Node* del = cur->next;

delete del;

cur->next = del->next;

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

函数 hasCycle 采用Floyd快慢指针法判断一个单链表中是否存在环,链表的头节点为 head ,即用两个指针在链表上前进: slow 每次走 1 步, fast 每次走 2 步,若存在环, fast 终会追上 slow (相遇);若无环,fast 会先到达 nullptr,则横线上应填写( )。

A

slow = slow->next;

fast = fast->next->next;

B

slow = fast->next;

fast = slow->next->next;

C

slow = slow->next;

fast = slow->next->next;

D

slow = fast->next;

fast = fast->next->next;

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

以下哪种情况使用链表比数组更合适?2025.9-5

A

数据量固定且读多写少

B

需要频繁在中间或开头插入、删除元素

C

需要高效随机访问元素

D

存储空间必须连续

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

与数组相比,链表在( )操作上通常具有更高的效率?

A
随机访问元素
B
查找指定元素
C
在已知位置插入或删除节点
D
遍历所有元素
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面C++代码实现双向链表。函数 is_empty() 判断链表是否为空,如链表为空返回 true ,否则返回false 。横线处不能填写?( )

// 节点结构体
struct Node {
    int data;
    Node* prev;
    Node* next;
};
// 双向链表结构体
struct DoubleLink {
    Node* head;
    Node* tail;
    int size;
    DoubleLink() {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }
    ~DoubleLink() {
        Node* curr = head;
        while (curr) {
            Node* next = curr->next;
            delete curr;
            curr = next;
        }
    }
    // 判断链表是否为空
    bool is_empty() const {
        _______________________
    }
};
A
return head == nullptr;
B
return tail == nullptr;
C
return head.data == 0;
D
return size == 0;
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

基于上题代码正确的前提下,填入相应代码完善 append() ,用于在双向链表尾部增加新节点,横线上应填写?( )

void append(int data) {
    Node* newNode = new Node {data, nullptr, nullptr};
    if (is_empty()) {
        head = tail = newNode;
    } else {
        _______________________
    }
    ++size;
}
A
tail->next = newNode;
B
newNode->prev = tail;tail = newNode;
C
tail = newNode;newNode->prev = tail;tail->next = newNode;
D
tail->next = newNode;newNode->prev = tail;tail = newNode;
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下列C++代码用循环链表解决约瑟夫问题,即假设 n 个人围成一圈,从第一个人开始数,每次数到第 k 个的人就出圈,输出最后留下的那个人的编号。横线上应填写?( )

struct Node {
    int data;
    Node* next;
};
Node* createCircularList(int n) {
    Node* head = new Node {1, nullptr};
    Node* prev = head;
    for (int i = 2; i <= n; ++i) {
        Node* node = new Node {i, nullptr};
        prev->next = node;
        prev = node;
    }
    prev->next = head;
    return head;
}
int fingLastSurvival(int n, int k) {
    Node* head = createCircularList(n);
    Node* p = head;
    Node* prev = nullptr;
    while (p->next != p) {
        for (int count = 1; count < k; ++count) {
            prev = p;
            p = p->next;
        }
        _______________________
    }
    cout << "最后留下的人编号是: " << p->data << endl;
    delete p;
    return 0;
}
A
prev->next = p->next;
delete p;
p = prev->next;
B
delete p;
prev->next = p->next;
p = prev->next;
C
delete p;
p = prev->next;
prev->next = p->next;
D
prev->next = p->next;
p = prev->next;
delete p;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

有关下面C++代码的说法,【错误】的是?( )

double sqrt_binary(long long n, double epsilon = 1e-10) {
    if (n < 0) {
        throw invalid_argument("输入必须为非负整数");
    }
    if (n == 0 || n == 1) return n;
    // 阶段 1
    long long low = 1, high = n;
    long long k = 0;
    while (low <= high) {
        long long mid = (low + high) / 2;
        long long mid_sq = mid * mid;
        if (mid_sq == n) {
            return mid;
        } else if (mid_sq < n) {
            k = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    long long next_k = k + 1;
    if (next_k * next_k == n) {
        return next_k;
    }
    // 阶段 2
    double low_d = (double)k;
    double high_d = (double)(k + 1);
    double mid;
    while (high_d - low_d >= epsilon) {
        mid = (low_d + high_d) / 2;
        double mid_sq = mid * mid;
        if (mid_sq < n) {
            low_d = mid;
        } else {
            high_d = mid;
        }
    }
    double result = (low_d + high_d) / 2;
    long long check_int = (long long)(result + 0.5);
    if (check_int * check_int == n) {
        return check_int;
    }
    return result;
}
A
“阶段1”的目标是寻找正整数 n 可能的正完全平方根
B
“阶段2”的目标是如果正整数 n 没有正完全平方根,则在可能产生完全平方根附近寻找带小数点的平方根
C
代码 check_int = (long long)(result + 0.5) 是检查因浮点误差是否为正完全平方根
D
阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较,会进入死循环
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

链表【不具备】的特点是?( )

A
可随机访问任何一个元素
B
插入、删除操作不需要移动元素
C
无需事先估计存储空间大小
D
所需存储空间与存储元素个数成正比
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

双向链表中每个结点有两个指针域 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;
答案与解析
正确答案:A

要删除双向链表中的结点 p,需要正确调整其前驱(prev)和后继(next)结点的指针:

让 p->prev->next 指向 p->next(前驱的后继指向 p 的后继)。

让 p->next->prev 指向 p->prev(后继的前驱指向 p 的前驱)。

选项A错误:

p->next->prev = p->next;  // 错误:让后继的前驱指向自己(p->next),破坏了链表结构

p->prev->next = p->prev;  // 错误:让前驱的后继指向自己(p->prev),链表断裂

题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为 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;
答案与解析
正确答案:B

双向循环链表的结构:

头哨兵 head:

head->prev 应该指向链表的最后一个结点(即 tail)。

head->next 应该指向链表的第一个实际结点(如果链表为空,则指向 tail)。

尾哨兵 tail:

tail->prev 应该指向链表的最后一个实际结点(如果链表为空,则指向 head)。

tail->next 应该指向链表的第一个结点(即 head)。

由于链表为空,head 和 tail 应该互相指向对方:

head->next = tail

tail->prev = head

题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面关于链表和数组的描述,错误的是( )。

A
当数据数量不确定时,为了应对各种可能的情况,需要申请一个较大的数组,可能浪费空间;此时用链表比较合适,大小可动态调整。
B
在链表中访问节点的效率较低,时间复杂度为 O(n)。
C
链表插入和删除元素效率较低,时间复杂度为 O(n)。
D
链表的节点在内存中是分散存储的,通过指针连在一起。
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

在循环单链表中,节点的 next 指针指向下一个节点,最后一个节点的 next 指针指向( )。

A
当前节点
B
nullptr
C
第一个节点
D
上一个节点
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.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;
}
A
dummyHead->next = head; cur = dummyHead;
B
dummyHead->next = head->next; cur = dummyHead;
C

dummyHead->next = head; cur = dummyHead->next;

D

dummyHead->next = head->next; cur = dummyHead->next;

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面关于链表和数组的描述,错误的是( )。

A
数组大小固定,链表大小可动态调整。
B
数组支持随机访问,链表只能顺序访问。
C
存储相同数目的整数,数组比链表所需的内存多。
D

数组插入和删除元素效率低,链表插入和删除元素效率高。

答案与解析
正确答案:C

存储相同数目的整数的时候,数组用的内存应该是更少的,因为数组不需要记录下一个值的地址。

题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

通过( )操作,能完成在双向循环链表结点 p 之后插入结点 s 的功能(其中 next 域为结点的直接后继,prev 域为结点的直接前驱)。

A
p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;
B
p->next->prev = s; p->next = s; s->prev = p; s->next = p->next;
C
s->prev = p; s->next = p->next; p->next = s; p->next->prev = s;
D
s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;
答案与解析
正确答案:D

A选项最后一句,此时p->next已经变成了s,所以错了

B选项最后一句,此时p->next已经变成了s,所以错了

C选项最后一句,应该是s->next->prev = s;

题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。函数fibo()属于( )。

int fibo(int n) {
	if (n <= 0)
		return 0;
	if (n == 1 || n == 2)
		return 1;
		
	int a = 1,b = 1, next;
	for (int i = 3; i <= n; i++) {
		next = a + b;
		a = b;
		b = next;
	}
	return next;
}
A
枚举算法
B
贪心算法
C
迭代算法
D
递归算法
答案与解析
正确答案:C

迭代算法:迭代算法是通过循环实现的,每次迭代利用前面计算的结果来推导出下一个结果。在给定的C++代码中,使用了一个循环for (int i = 3; i <= n; i++) 来计算斐波那契数列第n 项的值,通过迭代更新a 和b的值,直到计算出第n 项的值并返回。

题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲,他将其作为链表的第一首歌曲,则下面横线上应填入的代码为( )。

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;
}
A
head->next->prev = p;
B
head->next = p;
C
head->prev = p;
D
触发异常,不能对空指针进行操作。
答案与解析
正确答案:C

在将p 插入后,先前的头节点(head)必须更新其prev 指针,指向新的头节点p,以保持双向链表的结构:

p->next 指向先前的头节点head。head->prev 指向新的头节点p。

题目详情