2026年大学第一学年（数据结构）链表操作算法测试题及答案

2025年大学第一学年（数据结构）链表操作算法测试题及答案

（考试时间：90分钟满分100分）班级______姓名______第I卷（总共5题，每题4分，每题只有一个正确答案，选出正确选项）1.若某链表最常用的操作是在末尾插入节点和删除尾节点，则采用（）存储方式最节省时间。A.单链表B.带头结点的单循环链表C.单循环链表D.带头结点的双向循环链表2.在一个单链表中，若p所指节点不是最后节点，在p之后插入s所指节点，则执行（）。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;3.已知一个链表head，删除链表中第i个节点的正确代码是（）。A.p=head;for(intj=第i个节点;j>1;j--)p=p->next;p->next=p->next->next;B.p=head;for(intj=1;j<i-1;j++)p=p->next;p->next=p->next->next;C.p=head;for(intj=1;j<i;j++)p=p->next;p->next=p->next->next;D.p=head;for(intj=1;j<i+1;j++)p=p->next;p->next=p->next->next;4.若要在链表中查找值为x的节点，正确的代码是（）。A.p=head;while(p!=NULL&&p->data!=x)p=p->next;returnp;B.p=head;while(p!=NULL||p->data!=x)p=p->next;returnp;C.p=head;do{p=p->next;}while(p!=NULL&&p->data!=x);returnp;D.p=head;do{p=p->next;}while(p!=NULL||p->data!=x);returnp;5.对于一个有n个节点的单链表，在表头插入节点的时间复杂度是（）。A.O(1)B.O(n)C.O(n^2)D.O(logn)第II卷二、多项选择题（总共3题，每题6分，每题有两个或两个以上正确答案，少选得3分，选错不得分）1.以下关于链表的说法正确的是（）。（多选）A.单链表从一个节点访问其后继节点的时间复杂度是O(1)B.双向链表中每个节点有两个指针域C.循环链表的特点是表中最后一个节点的指针域指向头节点D.双向循环链表中既可以向前遍历也可以向后遍历2.以下哪些操作会改变链表的结构（）。（多选）A.在链表头部插入节点B.在链表中间删除节点之后查找链表长度C.在链表尾部插入节点D.遍历链表并输出所有节点的值3.若要将一个新节点s插入到链表中p所指节点之后，需要进行的操作有（）。（多选）A.s->next=p->nextB.p->next=sC.如果p不是尾节点，还需将p->next->prev指向sD.如果链表是双向链表，还需将s->prev指向p三、判断题（总共5题，每题4分）1.单链表中头节点没有前驱节点。（）2.双向链表中删除节点时，只需要修改一个指针域。（）3.循环链表一定是双向链表。（）4.在链表中查找某个值时，若未找到则返回NULL指针。（）5.对链表进行排序只能采用冒泡排序算法。（）四、算法设计题（20分）给定一个带头节点的单链表head，编写一个算法将链表中所有节点的值都增加1。材料：单链表的节点结构定义如下：typedefstructNode{intdata;structNodenext;}Node;五、综合应用题（30分）材料：有一个带头节点的双向链表，节点结构如下：typedefstructDNode{intdata;structDNodeprior;structDNodenext;}DNode;编写一个函数，删除链表中所有值为偶数的节点，并返回新的链表头节点。答案：第I卷：1.D2.B3.B4.A5.A第II卷：二、多项选择题：1.BCD2.ABC3.ABCD三、判断题：1.√2.×3.×4.√5.×四、算法设计题：```cvoidincrementList(Nodehead){Nodep=head->next;while(p!=NULL){p->data++;p=p->next;}}```五、综合应用题：```cDNodedeleteEvenNodes(DNodehead){DNodep=head->next;while(p!=NULL){if(p->data%2==0){if(p==head->next){head->next=p->next;if(p->next!=NULL)p->next->prior=head;}else{p->prior->next=p->next;if(p->next!=NULL)p->next->prior=p->prior;}DNod