题目
关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ ）。Ⅰ.线性表的顺序存储结构优于其链式存储结构Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构Ⅲ.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构Ⅳ.顺序存储结构和链式存储结构都可以进行顺序存取A. Ⅰ、Ⅱ、Ⅲ B. Ⅱ、Ⅳ C. Ⅱ、Ⅲ D. Ⅲ、Ⅳ2.对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。A.顺序存储方式 B.链式存储方式 C.散列存储方式 D.以上均可以3.对于顺序存储的线性表，其算法的时间复杂度为O(1.的运算应该是（）。A.将n个元素从小到大排序 B.删除第i个元素（1<i<n）C.改变第i个元素的值（1<=i<=n） D.在第i个元素后插入一个新元素（1<=i<=n）4.下列关于线性表说法正确的是（ ）。Ⅰ.顺序存储方式只能用于存储线性结构Ⅱ.取线性表的第i个元素的时间同i的大小有关Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表A. Ⅰ、Ⅱ B.Ⅰ、Ⅲ、Ⅳ、Ⅴ C. Ⅳ、Ⅴ D. Ⅲ、Ⅳ、Ⅴ5.设线性表中有2n个元素，（ ）在单链表上实现要比在顺序表上实现效率更高。A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-l个元素的值(i=0.…, n-1)6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（ ）。A .s->next=p->next;p->next=s; B.p->next=s->next; s->next=p;C. q->next=s;s->next=p; D. p->next=s;s->next=q;7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（ ）。A. O(1) B. O(n) C. O(n2-------) D. O(nlog2------n)8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度釆用大O形式表示应该是（ ）。A. O(1) B. O(n) C. O(m) D. O(n+m)9.单链表中，增加一个头结点的目的是为了（ ）。A.使单链表至少有一个结点 B.标识表结点中首结点的位置C.方便运算的实现 D.说明单链表是线性表的链式存储10.在一个长度为n的带头结点的单链表h上，设有尾指计r，则执行（ ）操作与链表的表长有关。A.删除单链表中的第一个元素B.删除单链表中最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）； 对于不带头结点的单链表，则判定空表的条件为（ ）。A .head==NULL B .head->next=NULLC. head->next==head D. head!=NULL12.下面关于线性表的一些说法中，正确的是（ ）。A .对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关B.线性表中每个元素都有一个直接前趋和一个直接后继C.为了方便插入和删除数据，可以使用双链表存放数据D.取线性表第i个元素的时间同i的大小有关13.某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则釆用（ ）存储方式最省时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表14.在双链表中向p所指的结点之前插入一个结点q的操作为（ ）。A. p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;B .q->prior=p->prior;p->prior->next=q;q->next=p;p->priop=q->next;C. q->next=p;p->next=q;q->prior->next=q;q->next=p;D .p->prior->next=q; q->next=p; q->prior=p->prior;p->prior=q;15.在双向链表存储结构中，删除p所指的结点时必须修改指针（ ）。A .p->llink->rlink=p->rlink; p->rlink->llink=p->llink;B.p->llink=p->llink->llink;p->llink->rlink=p;C.p->rlink->llink=p; p->rlink = p->rlink->rlink;D .p->rlink=p->llink->llink;p->llink=p->rlink->rlink;16.在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（ ）。A. O(1) B. O(n) C.O(n2---------) D. O(nlog2--------n)17.与单链表相比，双链表的优点之一是（ ）。A.插入、删除操作更方便 B.可以进行随机访问C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活18.带头结点的双循环链表L为空的条件是（ ）。A. L->prior==LL->next==NULLB. L->prior==NULLL->next==NULLC. L->prior==NULLL->next==LD. L->prior==LL->next==L19. 一个链表最常用的操作是在末尾插入结点和删除结点，则选用（ ）最节省时间。A.带头结点的双循环链表 B.单循环链表C.带尾指针的单循环链表 D.单链表20.设对n(n>1)个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素； 在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（ ）。A.只有尾结点指计没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环双链表C.只有头结点指针没有尾结点指针的循环双链表D.既有头结点指针也有尾结点指针的循环单链表21. —个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（ ）最节省时间。A.不带头结点的单循环链表 B.双链表C.不带头结点且有尾指针的单循环链表 D.单链表22.静态链表中指针表示的是（ ）。A.下一元素的地址 B.内存储器地址C.下一个元素在数组中的位置 D.左链或右链指向的元素的地址23.需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。A.单链表 B.静态链表 C.顺序表 D.双链表二、综合应用题1.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。5.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O(1)。6.有一个带头结点的单链表L，设计一个算法使其元素递增有序。7.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有大于最小值小于最大值的元素（若存在)。8.给定两个单链表，编写算法找出两个链表的公共结点。9.给定一个带表头结点的单链表，设head为头指针，结点的结构为(data, next)，data 为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。11.设C=(a1, b1, a2, b2, …, an, bn)为线性表，釆用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A=(a1, a2,…, an), B=(bn, …, b2, b1)12.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如(7, 10, 10, 21, 30, 42, 42, 42, 51, 70)将变作(7, 10, 21, 30, 42, 51, 70)。13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。14.设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B 中公共元素产生单链表C，要求不破坏A、B的结点。15.已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B 的交集，并存放于A链表中。16.两个整数序列A=a1, a2, a3,…, am和B=b1, b2, b3,…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。17.设计一个算法用于判断带头结点的循环双链表是否对称。18.有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。19.设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。20.设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针）域外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L, x)运算时，令元素值为x的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L, x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。21.【2009年计算机联考真题】已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data域的值，并返回1；否则，只返回0。要求：1)描述算法的基本设计思想。2)描述算法的详细实现步骤。3)根据设计思想和实现步骤，釆用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。22.【2012年计算机联考真题】假定釆用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置 (如图中字符i所在结点的位置p)。要求：1)给出算法的基本设计思想。2)根据设计思想，釆用C或C++或Java语言描述算法，关键之处给出注释。3)说明你所设计算法的时间复杂度。
关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ ）。Ⅰ.线性表的顺序存储结构优于其链式存储结构Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构Ⅲ.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构Ⅳ.顺序存储结构和链式存储结构都可以进行顺序存取
A. Ⅰ、Ⅱ、Ⅲ
B. Ⅱ、Ⅳ
C. Ⅱ、Ⅲ
D. Ⅲ、Ⅳ
2.对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。A.顺序存储方式 B.链式存储方式 C.散列存储方式 D.以上均可以
3.对于顺序存储的线性表，其算法的时间复杂度为O(
1.的运算应该是（）。A.将n个元素从小到大排序 B.删除第i个元素（1<i<n）C.改变第i个元素的值（1<=i<=n） D.在第i个元素后插入一个新元素（1<=i<=n）
4.下列关于线性表说法正确的是（ ）。Ⅰ.顺序存储方式只能用于存储线性结构Ⅱ.取线性表的第i个元素的时间同i的大小有关Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表A. Ⅰ、Ⅱ B.Ⅰ、Ⅲ、Ⅳ、Ⅴ C. Ⅳ、Ⅴ D. Ⅲ、Ⅳ、Ⅴ
5.设线性表中有2n个元素，（ ）在单链表上实现要比在顺序表上实现效率更高。A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-l个元素的值(i=
0.…, n-1)
6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（ ）。A .s->next=p->next;p->next=s; B.p->next=s->next; s->next=p;C. q->next=s;s->next=p; D. p->next=s;s->next=q;
7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（ ）。A. O(1) B. O(n) C. O(n2-------) D. O(nlog2------n)
8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度釆用大O形式表示应该是（ ）。A. O(1) B. O(n) C. O(m) D. O(n+m)
9.单链表中，增加一个头结点的目的是为了（ ）。A.使单链表至少有一个结点 B.标识表结点中首结点的位置C.方便运算的实现 D.说明单链表是线性表的链式存储10.在一个长度为n的带头结点的单链表h上，设有尾指计r，则执行（ ）操作与链表的表长有关。A.删除单链表中的第一个元素B.删除单链表中最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）； 对于不带头结点的单链表，则判定空表的条件为（ ）。A .head==NULL B .head->next=NULLC. head->next==head D. head!=NULL12.下面关于线性表的一些说法中，正确的是（ ）。A .对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关B.线性表中每个元素都有一个直接前趋和一个直接后继C.为了方便插入和删除数据，可以使用双链表存放数据D.取线性表第i个元素的时间同i的大小有关13.某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则釆用（ ）存储方式最省时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表14.在双链表中向p所指的结点之前插入一个结点q的操作为（ ）。A. p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;B .q->prior=p->prior;p->prior->next=q;q->next=p;p->priop=q->next;C. q->next=p;p->next=q;q->prior->next=q;q->next=p;D .p->prior->next=q; q->next=p; q->prior=p->prior;p->prior=q;15.在双向链表存储结构中，删除p所指的结点时必须修改指针（ ）。A .p->llink->rlink=p->rlink; p->rlink->llink=p->llink;B.p->llink=p->llink->llink;p->llink->rlink=p;C.p->rlink->llink=p; p->rlink = p->rlink->rlink;D .p->rlink=p->llink->llink;p->llink=p->rlink->rlink;16.在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（ ）。A. O(1) B. O(n) C.O(n2---------) D. O(nlog2--------n)17.与单链表相比，双链表的优点之一是（ ）。A.插入、删除操作更方便 B.可以进行随机访问C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活18.带头结点的双循环链表L为空的条件是（ ）。A. L->prior==LL->next==NULLB. L->prior==NULLL->next==NULLC. L->prior==NULLL->next==LD. L->prior==LL->next==L19. 一个链表最常用的操作是在末尾插入结点和删除结点，则选用（ ）最节省时间。A.带头结点的双循环链表 B.单循环链表C.带尾指针的单循环链表 D.单链表20.设对n(n>1)个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素； 在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（ ）。A.只有尾结点指计没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环双链表C.只有头结点指针没有尾结点指针的循环双链表D.既有头结点指针也有尾结点指针的循环单链表21. —个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（ ）最节省时间。A.不带头结点的单循环链表 B.双链表C.不带头结点且有尾指针的单循环链表 D.单链表22.静态链表中指针表示的是（ ）。A.下一元素的地址 B.内存储器地址C.下一个元素在数组中的位置 D.左链或右链指向的元素的地址23.需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。A.单链表 B.静态链表 C.顺序表 D.双链表二、综合应用题1.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。5.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O(1)。6.有一个带头结点的单链表L，设计一个算法使其元素递增有序。7.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有大于最小值小于最大值的元素（若存在)。8.给定两个单链表，编写算法找出两个链表的公共结点。9.给定一个带表头结点的单链表，设head为头指针，结点的结构为(data, next)，data 为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。11.设C={a1, b1, a2, b2, …, an, bn}为线性表，釆用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1, a2,…, an}, B={bn, …, b2, b1}12.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如(7, 10, 10, 21, 30, 42, 42, 42, 51, 70)将变作(7, 10, 21, 30, 42, 51, 70)。13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。14.设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B 中公共元素产生单链表C，要求不破坏A、B的结点。15.已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B 的交集，并存放于A链表中。16.两个整数序列A=a1, a2, a3,…, am和B=b1, b2, b3,…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。17.设计一个算法用于判断带头结点的循环双链表是否对称。18.有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。19.设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。20.设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针）域外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L, x)运算时，令元素值为x的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L, x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。21.【2009年计算机联考真题】已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data域的值，并返回1；否则，只返回0。要求：1)描述算法的基本设计思想。2)描述算法的详细实现步骤。3)根据设计思想和实现步骤，釆用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。22.【2012年计算机联考真题】假定釆用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置 (如图中字符i所在结点的位置p)。要求：1)给出算法的基本设计思想。2)根据设计思想，釆用C或C++或Java语言描述算法，关键之处给出注释。3)说明你所设计算法的时间复杂度。
A. Ⅰ、Ⅱ、Ⅲ
B. Ⅱ、Ⅳ
C. Ⅱ、Ⅲ
D. Ⅲ、Ⅳ
2.对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。A.顺序存储方式 B.链式存储方式 C.散列存储方式 D.以上均可以
3.对于顺序存储的线性表，其算法的时间复杂度为O(
1.的运算应该是（）。A.将n个元素从小到大排序 B.删除第i个元素（1<i<n）C.改变第i个元素的值（1<=i<=n） D.在第i个元素后插入一个新元素（1<=i<=n）
4.下列关于线性表说法正确的是（ ）。Ⅰ.顺序存储方式只能用于存储线性结构Ⅱ.取线性表的第i个元素的时间同i的大小有关Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表A. Ⅰ、Ⅱ B.Ⅰ、Ⅲ、Ⅳ、Ⅴ C. Ⅳ、Ⅴ D. Ⅲ、Ⅳ、Ⅴ
5.设线性表中有2n个元素，（ ）在单链表上实现要比在顺序表上实现效率更高。A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-l个元素的值(i=
0.…, n-1)
6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（ ）。A .s->next=p->next;p->next=s; B.p->next=s->next; s->next=p;C. q->next=s;s->next=p; D. p->next=s;s->next=q;
7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（ ）。A. O(1) B. O(n) C. O(n2-------) D. O(nlog2------n)
8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度釆用大O形式表示应该是（ ）。A. O(1) B. O(n) C. O(m) D. O(n+m)
9.单链表中，增加一个头结点的目的是为了（ ）。A.使单链表至少有一个结点 B.标识表结点中首结点的位置C.方便运算的实现 D.说明单链表是线性表的链式存储10.在一个长度为n的带头结点的单链表h上，设有尾指计r，则执行（ ）操作与链表的表长有关。A.删除单链表中的第一个元素B.删除单链表中最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）； 对于不带头结点的单链表，则判定空表的条件为（ ）。A .head==NULL B .head->next=NULLC. head->next==head D. head!=NULL12.下面关于线性表的一些说法中，正确的是（ ）。A .对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关B.线性表中每个元素都有一个直接前趋和一个直接后继C.为了方便插入和删除数据，可以使用双链表存放数据D.取线性表第i个元素的时间同i的大小有关13.某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则釆用（ ）存储方式最省时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表14.在双链表中向p所指的结点之前插入一个结点q的操作为（ ）。A. p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;B .q->prior=p->prior;p->prior->next=q;q->next=p;p->priop=q->next;C. q->next=p;p->next=q;q->prior->next=q;q->next=p;D .p->prior->next=q; q->next=p; q->prior=p->prior;p->prior=q;15.在双向链表存储结构中，删除p所指的结点时必须修改指针（ ）。A .p->llink->rlink=p->rlink; p->rlink->llink=p->llink;B.p->llink=p->llink->llink;p->llink->rlink=p;C.p->rlink->llink=p; p->rlink = p->rlink->rlink;D .p->rlink=p->llink->llink;p->llink=p->rlink->rlink;16.在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（ ）。A. O(1) B. O(n) C.O(n2---------) D. O(nlog2--------n)17.与单链表相比，双链表的优点之一是（ ）。A.插入、删除操作更方便 B.可以进行随机访问C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活18.带头结点的双循环链表L为空的条件是（ ）。A. L->prior==LL->next==NULLB. L->prior==NULLL->next==NULLC. L->prior==NULLL->next==LD. L->prior==LL->next==L19. 一个链表最常用的操作是在末尾插入结点和删除结点，则选用（ ）最节省时间。A.带头结点的双循环链表 B.单循环链表C.带尾指针的单循环链表 D.单链表20.设对n(n>1)个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素； 在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（ ）。A.只有尾结点指计没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环双链表C.只有头结点指针没有尾结点指针的循环双链表D.既有头结点指针也有尾结点指针的循环单链表21. —个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（ ）最节省时间。A.不带头结点的单循环链表 B.双链表C.不带头结点且有尾指针的单循环链表 D.单链表22.静态链表中指针表示的是（ ）。A.下一元素的地址 B.内存储器地址C.下一个元素在数组中的位置 D.左链或右链指向的元素的地址23.需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。A.单链表 B.静态链表 C.顺序表 D.双链表二、综合应用题1.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。5.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O(1)。6.有一个带头结点的单链表L，设计一个算法使其元素递增有序。7.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有大于最小值小于最大值的元素（若存在)。8.给定两个单链表，编写算法找出两个链表的公共结点。9.给定一个带表头结点的单链表，设head为头指针，结点的结构为(data, next)，data 为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。11.设C={a1, b1, a2, b2, …, an, bn}为线性表，釆用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1, a2,…, an}, B={bn, …, b2, b1}12.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如(7, 10, 10, 21, 30, 42, 42, 42, 51, 70)将变作(7, 10, 21, 30, 42, 51, 70)。13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。14.设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B 中公共元素产生单链表C，要求不破坏A、B的结点。15.已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B 的交集，并存放于A链表中。16.两个整数序列A=a1, a2, a3,…, am和B=b1, b2, b3,…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。17.设计一个算法用于判断带头结点的循环双链表是否对称。18.有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。19.设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。20.设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针）域外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L, x)运算时，令元素值为x的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L, x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。21.【2009年计算机联考真题】已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data域的值，并返回1；否则，只返回0。要求：1)描述算法的基本设计思想。2)描述算法的详细实现步骤。3)根据设计思想和实现步骤，釆用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。22.【2012年计算机联考真题】假定釆用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置 (如图中字符i所在结点的位置p)。要求：1)给出算法的基本设计思想。2)根据设计思想，釆用C或C++或Java语言描述算法，关键之处给出注释。3)说明你所设计算法的时间复杂度。
题目解答
答案
与解析