1、线性表及答案解析(总分：104.00，做题时间：90 分钟)一、单项选择题(总题数：12，分数：24.00)1.(1)静态链表既有顺序存储的优点，又有动态链表的优点，所以，它存取表中第 i 个元素的时间与 i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是( )。（分数：2.00）A.(1)，(2)B.(1)C.(1)，(2)，(3)D.(2)2.在一个长度为 n 的顺序表中删除第 i 个元素(0=i=n)时，需向前移动( )个元素。（分数：2.00）A.n-iB.n-i+1C.n
2、-i-1D.i3.下面关于线性表的叙述中，错误的是哪一个?( )（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作4.下述哪一条是顺序存储结构的优点?( )（分数：2.00）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。（分数：2.00）A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表
3、6.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。（分数：2.00）A.O(n)，O(n)B.O(n)，O(1)C.O(1)，O(n)D.O(1)，O(1)7.线性表是( )。（分数：2.00）A.一个有限序列，可以为空B.一个有限序列，不可以为空C.一个无限序列，可以为空D.一个无限序列，不可以为空8.设单链表中结点的结构为typedef struct node链表结点定义ElemType data； 数据struct node*Link； 结点后继指针ListNode；已知指针 p 所指结点不是尾结点，若在 p 之后插入结点 s，则应执行下列哪一个操作?( )（分数：
4、2.00）A.slinkp；plinks；B.slinkplink；plinks；C.s 一link=Plink；PS；D.plinkS；slinkp；9.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。（分数：2.00）A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表10.在双向循环链表中，在 P 所指的结点之后插入 S 指针所指的结点，其操作是( )。（分数：2.00）A.pnext=s；sprior=p；pnextprior=s；snext=pnext；B.sprior=p；snext=pnext；pne
5、xt=s；Pnextprior=s：C.pnext=s；pnextprior=s；sprior=p；snext=pnext；D.sprior=p；snext=pnext；pnextprior=s；pnext=s：11.在一个长度为 n 的顺序表中向第 i 个元素(0in+1)之前插入一个新元素时，需向后移动( )个元素。（分数：2.00）A.n-iB.n-i+1C.n-i-1D.i12.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1=i=n+1)。（分数：2.00）A.O(0)B.O(1)C.O(n)D.O(n2)二、综合应用题(总题数：
6、8，分数：80.00)13.设计在无头结点的单链表中删除第 i 个结点的算法。（分数：10.00）_14.设计将带表头的链表逆置算法。（分数：10.00）_15.设顺序表中的数据元素递增有序，编写一算法将元素 X 插入到顺序表的适当位置上，并保证该表的有序性。（分数：10.00）_16.设线性表 A=(a1，a 2，a 3，a n)以带头结点的单链表作为存储结构。编写一个函数，对 A 进行调整，使得当 n 为奇数时 A=(a2，a 4，a n-1，a 1，a 3，a n)，当 n 为偶数时A=(a2，a 4，a n，a 1，a 3，a n-1)。（分数：10.00）_17.试分别用顺序表和单链
7、表作为存储结构，实现将线性表(a 0，a 1，a 2，a n-1)就地逆置的操作，所谓“就地”，是指辅助空间应为 O(1)。（分数：10.00）_18.假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct nodeDataType data：struct node *nextLinkNode， *LinkList；编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_19.设带表头结点的双向链表的定义为typedef int ElemType；typedef struct dnode双向链表结点定义ElemType data；数
8、据struct dnode*lLink，*rLink；结点前驱与后继指针)DblNode；typedef DblNode*DblList；双向链表试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域 rLink中，并利用左链域 lLink 把所有结点按照其值从小到大的顺序连接起来。（分数：10.00）_20.已知 L1、L2 分别为两循环单链表的头结点指针，m，n 分别为 L1、L2 表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。（分数：10.00）_线性表答案解析(总分：104.00，做题时间：90 分钟)一、单项选择题(
9、总题数：12，分数：24.00)1.(1)静态链表既有顺序存储的优点，又有动态链表的优点，所以，它存取表中第 i 个元素的时间与 i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是( )。（分数：2.00）A.(1)，(2)B.(1) C.(1)，(2)，(3)D.(2)解析：静态链表使用结构体数组来实现线性链表的功能。因为其用游标 cur 来指示下一个数据元素的存储位置，所以存取数据时静态链表同线性链表(单链表)是相似的。也就是说，静态链表在存取表中第 i 个元素的时间同 i 是
10、相关的。2.在一个长度为 n 的顺序表中删除第 i 个元素(0=i=n)时，需向前移动( )个元素。（分数：2.00）A.n-i B.n-i+1C.n-i-1D.i解析：一般情况下，删除顺序表的第 i(1-i-n)个元素时需要将第 i+1 到第 n 个元素(共 n-i 个元素)依次向前移动一个位置。所以答案为 A。3.下面关于线性表的叙述中，错误的是哪一个?( )（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作 C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作解析：线性表采用顺序存储，
11、并不便于进行插入和删除操作。4.下述哪一条是顺序存储结构的优点?( )（分数：2.00）A.存储密度大 B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示解析：顺序存储利用物理的邻接关系表示数据元素之间的逻辑关系，因此没有必要设置指针域，所以其存储密度比链式存储大，但是插入运算和删除运算都需大量移动数据元素，并不方便；D 选项并不是顺序存储结构的优点。所以答案为 A。5.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。（分数：2.00）A.顺序表 B.双链表C.带头结点的双循环链表D.单循环链表解析：“存取任一指定序
12、号”最好的方法是实现“随机存取”，则可采用顺序表。并且，因为插入和删除操作都是在最后进行的，所以无需大量移动数据元素，选项 A 是最合适的。6.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。（分数：2.00）A.O(n)，O(n)B.O(n)，O(1)C.O(1)，O(n) D.O(1)，O(1)解析：顺序存储可以实现“随机存取”，因此访问结点的时间复杂度为 O(1)，而插入、删除结点由于涉及到大量移动元素，故其时间复杂度为 O(n)。7.线性表是( )。（分数：2.00）A.一个有限序列，可以为空 B.一个有限序列，不可以为空C.一个无限序列，可以为空D.一个无限序列，
13、不可以为空解析：线性表是由相同类型的结点组成的有限序列。如：由 n 个结点组成的线性表(a1，a 2，a n)a1是最前结点，a n是最后结点。结点也称为数据元素或者记录。线性表中结点的个数称为其长度。长度为 O 的线性表称为空表。所以答案为 A。8.设单链表中结点的结构为typedef struct node链表结点定义ElemType data； 数据struct node*Link； 结点后继指针ListNode；已知指针 p 所指结点不是尾结点，若在 p 之后插入结点 s，则应执行下列哪一个操作?( )（分数：2.00）A.slinkp；plinks；B.slinkplink；plin
14、ks； C.s 一link=Plink；PS；D.plinkS；slinkp；解析：*9.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。（分数：2.00）A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表 解析：仅有尾指针的单循环链表，可以非常方便地找到尾结点，尾结点后面的第一个结点往往是头结点，头结点的下一个结点就是第线性表的第一个结点。对最后一个元素和第一个元素操作对带尾指针的单循环链表是非常方便的。10.在双向循环链表中，在 P 所指的结点之后插入 S 指针所指的结点，其操作是( )。（分数：2.00）A
15、.pnext=s；sprior=p；pnextprior=s；snext=pnext；B.sprior=p；snext=pnext；pnext=s；Pnextprior=s：C.pnext=s；pnextprior=s；sprior=p；snext=pnext；D.sprior=p；snext=pnext；pnextprior=s；pnext=s： 解析：同单链表相比，双向链表的插入、删除操作需同时修改两个指针。*步骤：spriorpprior；ppriornext=s；snext=p；pprior=s；11.在一个长度为 n 的顺序表中向第 i 个元素(0in+1)之前插入一个新元素时，需向
16、后移动( )个元素。（分数：2.00）A.n-iB.n-i+1 C.n-i-1D.i解析：一般情况下，在顺序表的第 i(1=i=n)个元素之前插入一个元素，需要将第 n 至 i 的元素(共 n-i+1 个元素)向后移动一个位置。所以答案为 B。12.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1=i=n+1)。（分数：2.00）A.O(0)B.O(1)C.O(n) D.O(n2)解析：顺序存储的线性表在插入新元素时，需要将第 i 个元素到第 n 个元素均向后移动一个单位，插入的新元素成为第 i 个元素，原来的第 i 个元素成为第 i+1
17、个元素，原来的第 n 个元素成为第 n+1 个元素，线性表的长度加 1，插入操作的主要工作都放在移动元素上。假设线性表中含有 n 个数据元素，在进行插入操作时，若假定在 n+1 个位置上插入元素的可能性均等，则平均移动元素的个数为：除非插入在线性表的最后，否则都要移动元素。所以其时间复杂度为 O(n)，答案为 C。二、综合应用题(总题数：8，分数：80.00)13.设计在无头结点的单链表中删除第 i 个结点的算法。（分数：10.00）_正确答案：(算法思想为：(1)应判断删除位置的合法性，当 i0 或 in-1 时，不允许进行删除操作；(2)当 i=0 时，删除第一个结点；(3)当 0in 时
18、，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：delete(LinkList*q，int i) 在无头结点的单链表中删除第 i 个结点LinkList *P，*S；int j；if(i0)printf(“Cant delete”)；else if(i=0) s=q；q=qnext；free(s)；elsej=0；s=q；while(ji)&(s!=NULL) p=s；s=s=next；j+：if(s=NULL)printf(“Cantt delete”)；else pnext=snext；free(s)；)解析：14.设计将带表头的链表逆置算法。（分数：
19、10.00）_正确答案：(解析：设单循环链表的头指针为 head，类型为 LinkList。逆置时需将每一个结点的指针域做一修改，使其原前趋结点成为后继。如要更改 q 结点的指针域时，设 S 指向其原前趋结点，P 指向其原后继结点，则只需进行 qnexts；操作即可，算法描述如下：void invert(LinkList*head) 逆置 head 指针所指向的单循环链表linklist*p，*q，*S；q=head；pheadnext；while(p!=head) 当表不为空时，逐个结点逆置 s=q；q=P；p=pnext；qnext=s；pnext=q；，)解析：15.设顺序表中的数据元素
20、递增有序，编写一算法将元素 X 插入到顺序表的适当位置上，并保证该表的有序性。（分数：10.00）_正确答案：(只要从终端结点开始往前找到第一个比 X 小(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：SqList*InsertSqList(SqList*L，int i，Elemtype x)if(i1)(iLlength+1)printf(“插入位置不合理”)；exit(l)；if(LlengthLMaxSize1)print(“顺序表已满，不能再插入!”)；exit(l)；or(mLlength1；m=i1；m)Ldatam+1=Ldatam；Ldatai1=x；Llength
21、+：return L；)解析：16.设线性表 A=(a1，a 2，a 3，a n)以带头结点的单链表作为存储结构。编写一个函数，对 A 进行调整，使得当 n 为奇数时 A=(a2，a 4，a n-1，a 1，a 3，a n)，当 n 为偶数时A=(a2，a 4，a n，a 1，a 3，a n-1)。（分数：10.00）_正确答案：(方法一：void f(LinkList L)LinkList p，q，r；p=L；*P 是偶数尾结点q=Lnext；*q 是当前奇数结点while(q&qnext)尚有未调整的偶数结点r=qnext；r 指向当前偶数结点qnext=rnext；删除偶数结点rnext
22、=Pnext。Pnext=r； 插入偶数结点p=pnext；q=qnext；方法二：void f(LinkList L)LinkList p，h，r，s；if(!Lnext !Lnextnext)return；h=Lnext；r=h；h 和 r 分别为奇数结点的头、尾指针Lnext=hnext；p=Lnext；p 指向偶数结点while(pnext)2 个结点以上s=pnext；s 指向奇数结点pnext=snext；删除奇数结点rnext=s；链接奇数结点r=s：if(pnext)p=pnext；尚有偶数结点存在pnext=h；rnext=NULL；方法三：void f(LinkList L
23、)LinkList p，h，rl，r2，s；if(!Lnext !Lnextnext)return；h=Lnext；h 是奇数结点头指针r2=h；r2 是奇数尾结点指针r1=L；r1 是偶数结点指针p=hnext；p 指向第 1 个偶数结点while(p)s=pnext；s 指向下一个奇数结点r1next=P；r1=P；链接偶数结点if(s)p=snext；p 指向下一个偶数结点r2next=s：r2=s；链接奇数结点else p=s；偶数个数情况r1next=h：r2next=NULL：)解析：17.试分别用顺序表和单链表作为存储结构，实现将线性表(a 0，a 1，a 2，a n-1)就地逆
24、置的操作，所谓“就地”，是指辅助空间应为 O(1)。（分数：10.00）_正确答案：(方法一：用顺序表作存储结构struct SqList/ElemType*elem；存储空间基址int length；当前长度；void InvertSqList(SqListL)int i；ElemType temp；for(i0；iLlength/2；i+)temp=Lelem；Lelem=LelemL1engthi1；L.elemL.lengthi1temp；方法二：用顺序表作存储结构void InvertSqList(SqList&L)6 Rint i，j；ElemType temp；i=0；j=Lle
25、ngth1；while(ij)temp=Lelem；Lelem=L.elemjL.elemj=tempi+；j；方法三：用带头结点的单链表作存储结构struct LNodeElemType data；LNode*next：；typedef LNode*LinkList；Void InvertLinkList(LinkList&L)pL；LNULL；while(p)sp；ppnext；SnextL：)解析：18.假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct nodeDataType data：struct node *nextLinkNode， *Link
26、List；编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_正确答案：(void deleted_list(LinkList A，LinkList B)LinkList p，q，r；r=A：p=Anext；q=Bnext；while(p!NULL&q!=NULL)if(pdataqdata)q=qnextelse if(pdataqdata)r=P：ppnext；elsernext=pnext；free(p)；p=rnext：)解析：19.设带表头结点的双向链表的定义为typedef int ElemType；typedef struct dnode双向链
27、表结点定义ElemType data；数据struct dnode*lLink，*rLink；结点前驱与后继指针)DblNode；typedef DblNode*DblList；双向链表试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域 rLink中，并利用左链域 lLink 把所有结点按照其值从小到大的顺序连接起来。（分数：10.00）_正确答案：(void sort(DblNode*L)DblNode*S=Lrlink；指针 s 指向待插入结点，初始时指向第一个结点while(S!一 NULL)处理所有结点pre=L；p=LlLink；指针 P 指向待比
28、较的结点，pre 是 P 的前驱指针while(p!NULL&sdatapdata)循 1Link 链寻找结点*S 的插入位置pre=P；p=plLink；prelLink=S；sILink=p；ssrLink；结点*s 在 lLink 方向插入到*pre 与*p 之间)解析：20.已知 L1、L2 分别为两循环单链表的头结点指针，m，n 分别为 L1、L2 表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。（分数：10.00）_正确答案：(循环单链表 L1 和 L2 数据结点个数分别为 m 和 n，将二者合成一个循环单链表时，需要将一个循环链表的结点(从第一元
29、素结点到最后一个结点)插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并”，因此应找结点个数少的链表查其尾结点。LinkedList Union(LinkedList L1，L2；int m，n)L1 和 L2 分别是两循环单链表的头结点的指针，m 和 n 分别是 L1 和 L2 的长度。本算法用最快速度将 L1 和 L2 合并成一个循环单链表。if(m0 nO)printf(“表长输入错误/n”)；exit(0)；if(mn)若 mn，则查 L1 循环单链表的最后一个结点if(m=0)return(L2)；L1 为空表elsep=L1：while(pnext!L1)p=pnext；查最后一个元素结点pnext=L2next；将 L1 循环单链表的元素结点插入到 L2 的第一元素结点前L2nextL1next；free(L1)；释放无用头结点处理完 mn 情况else下面处理 L2 长度小于等于 L1 的情况if(n=0)return(L1)；L2 为空表elsepL2；while(pnext!L2)ppnext；查最后元素结点PnextL1next；将 L2 的元素结点插入到 L1 循环单链表的第一元素结点前L1nextL2next；free(L2)；释放无用头结点)解析：
