itgle.com
有一个由整数元素构成的非空单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数节点，B单链表中含有所有的奇数节点，且保持原来的相对次序。
题目
有一个由整数元素构成的非空单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数节点，B单链表中含有所有的奇数节点，且保持原来的相对次序。
相似考题
参考答案和解析
更多“有一个由整数元素构成的非空单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数节点，B单链表中含有所有的奇数节点，且保持原来的相对次序。”相关问题
-
第1题：
已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法: ① 求链表中的最大整数; ② 求链表的结点个数; ③ 求所有整数的平均值。参考答案：
[算法描述]
①
int GetMax(LinkList p)
{
if(!p->next)
return p->data;
else
{
int max=GetMax(p->next);
return p->data>=max ? p->data:max;
}
}
②
int GetLength(LinkList p)
{
if(!p->next)
return 1;
else
{
return GetLength(p->next)+1;
}
}
③
double GetAverage(LinkList p , int n)
{
if(!p->next)
return p->data;
else
{
double ave=GetAverage(p->next,n-1);
return (ave*(n-1)+p->data)/n;
}
}
-
第2题：
若某链表最常用的操作是在最后一个节点之后插入一个节点和删除最后一个节点，则采用______存储方式最节省时间。
A．单链表
B．双链表
C．单循环链表
D．带头节点的双循环链表
正确答案：D
-
第3题：
在一个长度为n(n>1)的带头结点的单链表head上,另设有尾指针r(指向尾结点),执行()操作与链表的长度有关。A.删除单链表中的第一个元素
B.删除单链表中的尾结点
C.在单链表的第一个元素前插入一个新结点
D.在单链表的最后一个元素后插入一个新结点
参考答案：B
-
第4题：
若某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则 采用（ ）存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表
正确答案：D
带头结点的循环链表可以很方便地找到尾结点，从而节省查找的时间。 -
第5题：
阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
函数Combine(LinkList La，LinkList Lb)的功能是：将元素呈递减排列的两个含头结点单链表合并为元素值呈递增(或非递减)方式排列的单链表，并返回合并所得单链表的头指针。例如，元素递减排列的单链表La和Lb如图1所示，合并所得的单链表如图2所示。
设链表结点类型定义如下：
typedef Struct Node{ int data; struct Node*next; }Node,*LinkList; [C函数] LinkListCombine(LinkList La,LinkList Lb) { //La和Lb为含头结点且元素呈递减排列的单链表的头指针 //函数返回值是将La和Lb合并所得单链表的头指针 //且合并所得链表的元素值呈递增(或非递减)方式排列 ______Lc,tp,pa,pb; //Lc为结果链表的头指针,其他为临时指针 if(!La)returnNULL; pa=La-＞next; //pa指向La链表的第一个元素结点 if(!Lb) returnNULL; pb=Lb-＞next; //pb指向Lb链表的第一个元素结点 Lc=La; //取La链表的头结点为合并所得链表的头结点 Lc-＞next=NULL; while(______) { //pa和pb所指结点均存在(即两个链表都没有到达表尾) //令tp指向pa和pb所指结点中的较大者 if(pa-＞data＞pb-＞data){ tp=pa; pa=pa-＞next; } else{ tp=pb; pb=pb-＞next; } ______ =Lc-＞next; //tp所指结点插入Lc链表的头结点之后 Lc-＞next=______; } tp=(pa)?pa:pb; //设置tp为剩余结点所形成链表的头指针 //将剩余的结点合并入结果链表中,pa作为临时指针使用 while (tp) { pa=tp-＞next; tp-＞next=Lc-＞next; Lc-＞next=tp; ______; } return Lc; }答案：解析：LinkList
pa&&pb
tp-＞next
tp
tp=pa
【解析】
本题考查数据结构应用及C语言实现。链表运算是C程序设计题中常见的考点，需熟练掌握。考生需认真阅读题目中的说明，以便理解问题并确定代码的运算逻辑，在阅读代码时，还需注意各变量的作用。 -
第6题：
设一个有序的单链表中有n个节点，现要求插入一个新节点后使得单链表仍然保持有序，则该操作的时间复杂度为()。
答案：C解析：对单链表进行插入节点的操作，就是对单链表进行查找，找到节点需要插入的位置，然后修改指针，将节点插入单链表。 -
第7题：
在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为（）和（）。
正确答案:HL->next==NULL；HL->next==HL -
第8题：
在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。
- A、删除单链表中的第一个元素
- B、删除单链表中的最后一个元素
- C、在单链表第一个元素前插入一个新元素
- D、在单链表最后一个元素后插入一个新元素
正确答案:B -
第9题：
编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。
正确答案: 编写C程序如下（已上机通过）：
全局变量及函数提前说明：
---------------------------------
#include
#include
typedefstructliuyu{intdata；structliuyu*link；}test；
liuyu*p，*q，*r，*head；
intm=sizeof（test）；
voidmain（）/*第一步，从键盘输入整数，不断添加到链表*/
{inti；
head=（test*）malloc（m）；/*m=sizeof（test）；*/
p=head；i=0；
while（i!=-9999）
{printf（"/ninputaninteger[stopby’-9999’]："）；
scanf（"%d"，&i）；
p->data=i；/*inputdataissaved*/
p->link=（test*）malloc（m）；/*m=sizeof（test））；*/
q=p；
p=p->link；
}
q->link=NULL；/*原先用p->link=NULL似乎太晚！*/
p=head；i=0；/*统计链表结点的个数并打印出来*/
while（p->link!=NULL）
{printf（"%d"，p->datA.；
p=p->link；
i++；
}
printf（"/nnodenumber=%d/n"，i-1）；/*结点的个数不包括-9999*/
} -
第10题：
如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（）。
- A、只有表头指针没有表尾指针的循环单链表
- B、只有表尾指针没有表头指针的循环单链表
- C、非循环双链表
- D、循环双链表
正确答案:B -
第11题：
问答题设某带头结头的单链表的结点结构说明如下：typedef struct nodel{int data struct nodel*next；}node；试设计一个算法：void copy（node*headl，node*head2），将以head1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。正确答案： 一边遍历，一边申请新结点，链接到head2序列中。解析： 暂无解析 -
第12题：
填空题若要将一个单链表中的元素倒置，可以借助（）建立单链表的思想将链表中的结点重新放置。正确答案： 头插法解析： 暂无解析 -
第13题：
设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)。参考答案：
B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，将小于0的结点插入B表,大于等于0的结点插入C表。
[算法描述]
void DisCompose(LinkedList A)
{ B=A;
B->next= NULL; ∥B表初始化
C=new LNode;∥为C申请结点空间
C->next=NULL; ∥C初始化为空表
p=A->next; ∥p为工作指针
while(p!= NULL)
{ r=p->next; ∥暂存p的后继
if(p->data<0)
{p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法
else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法
p=r;∥p指向新的待处理结点。
}
}
-
第14题：
在长度为n的()上删除第一个元素,其算法的时间复杂度为O(n)。A.只有表头指针的不带表头结点的循环单链表
B.只有表尾指针的不带表头结点的循环单链表
C.只有表尾指针的带表头结点的循环单链表
D.只有表头指针的带表头结点的循环单链表
参考答案：A
-
第15题：
在单链表中，增加头节点的目的是
A．方便运算的实现
B．使单链表至少有一个节点
C．标识表节点中首节点的位置
D．说明单链表是线性表的链式存储实现
正确答案：A
解析：头节点不仅标识了表中首节点的位置，而且根据单链表(包含头节点) 的结构，只要掌握了表头，就能够访问整个链表，因此增加头节点的目的是为了便于运算的实现。 -
第16题：
在单链表中，增加头节点的目的是（ ）。
A. 使单链表不为空
B. 方便运算的实现
C. 增加存储空间
D. 说明单链表是线性表的链式存储实现
正确答案：A
头节点不仅标识了表中首节点的位置，而且根据单链表(包含头节点)的结构，只要掌握了表头，就能够访问整个链表，因此增加头节点目的是为了便于运算的实现。本题答案为A。
-
第17题：
在一个长度为n(n＞1)的带头结点单链表h上，另设有尾指针r(指向尾结点)。与链表的长度有关的操作是()。A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素答案：B解析：在单链表中要删除最后一个元素必须找到尾结点的前驱结点的指针。由于单链表只能访问结点的下一个结点，所以根据尾指针不能够直接找到它的前驱结点，只有从头开始依次向下找到尾结点的前驱结点。所以删除单链表中的最后一个元素与链表的长度有关。 -
第18题：
以下各种存储结构中，最适合用作链队的链表是()。A.带队首指针和队尾指针的循环单链表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的非循环单链表
D.只带队首指针的循环单链表答案：B解析：因为队列的入队和出队操作都在端点进行。即在队首和队尾进行。所以带队首指针和队尾指针的非循环单链表最适合用作链队的链表。 -
第19题：
若要将一个单链表中的元素倒置，可以借助（）建立单链表的思想将链表中的结点重新放置。
正确答案:头插法 -
第20题：
某带头结点的单链表的头指针head，判定该单链表非空的条件（）。
正确答案:head->next!=Null -
第21题：
数据结构里，单链表是指（）。
- A、有两个指针域的链表。
- B、只有一个指针域的链表。
- C、有三个指针域的链表。
- D、没有指针域的链表。
正确答案:B -
第22题：
填空题在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为（）和（）。正确答案： HL->next==NULL,HL->next==HL解析： 暂无解析 -
第23题：
单选题数据结构里，单链表是指（）。A有两个指针域的链表。
B只有一个指针域的链表。
C有三个指针域的链表。
D没有指针域的链表。
正确答案： C解析： 暂无解析 -
第24题：
填空题某带头结点的单链表的头指针head，判定该单链表非空的条件（）。正确答案： head->next!=Null解析： 暂无解析