第一章 线性表.docx
- 文档编号:15323961
- 上传时间:2023-07-03
- 格式:DOCX
- 页数:21
- 大小:79.65KB
第一章 线性表.docx
《第一章 线性表.docx》由会员分享,可在线阅读,更多相关《第一章 线性表.docx(21页珍藏版)》请在冰点文库上搜索。
第一章线性表
1
1.线性表是
∙
A.一个有限序列,可以为空
∙
B.一个有限序列,不能为空
∙
C.一个无限序列,可以为空
∙
D.一个无限序列,可以为空
∙正确答案是:
【A】
解析:
线性表的定义如下:
线性表是具有n(n≥0)个元素的一个有限序列,当n=0时称为空表。
2
在n个结点的顺序表,算法的时间复杂度是O
(1)的操作是
∙
A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
∙
B.在第i个结点后插入一个新结点(1≤i≤n)
∙
C.删除第i个结点(1≤i≤n)
∙
D.顺序查找与给定值x相等的元素
∙正确答案是:
【A】
解析:
顺序表可以按元素下标直接存和直接取,其时间复杂度为O
(1)。
在第i个元素后面插入新元素和删除第i个元素的时间复杂度都是O(n),顺序查找的时间复杂度也是O(n)。
3
若长度为n的线性表采用顺序存储结构,在表的第i个位置插入一个数据元素,需要移动表中数据元素的数目为
∙
A.i
∙
B.n+i
∙
C.n-i+1
∙
D.n-i-1
∙正确答案是:
【C】
解析:
在线性表的第i个位置插入一个新的数据元素之前,需要先将线性表的第i个数据元素至第n个数据元素依次后移1个位置,一共需要移动n-i+1个数据元素。
4
将两个各有n1和n2个元素的有序表(递增)归并成一个有序表,仍保持其递增顺序,则最少的比较次数是
∙
A.
∙
B.
∙
C.
∙
D.
∙正确答案是:
【C】
解析:
由于将长度为n的单链表链接在长度为m的单链表之后的操作,需要把长度为m的单链表遍历一遍,找到最后的一个结点,所以时间复杂度为O(m)。
5
已知L是带头结点的单链表,结点p既不是第一个结点,也不是最后一个结点,删除p结点的直接后继结点的语句序列是
∙
A.p=p→next
∙
B.p→next=p
∙
C.p→next=p→next→next
∙
D.p=p→next→next
∙正确答案是:
【C】
解析:
选项A是删除了当前p结点;选项B是把p结点之后的所有结点都丢失了,同时在p结点本身形成了一个环;选项C正确;选项D是把p和p的后继结点都删除了。
6
设双向循环链表中结点的结构为(prior,data,next),且不带表头结点。
若想在指针p所指结点之后插入指针s所指结点,则应执行下列哪一个操作
∙
A.p→next=s;s→prior=p;p→next→prior=s;s→next=p→next;
∙
B.p→next=s;p→next→prior=s;s→prior=p;s→next=p→next;
∙
C.s→prior=p;s→next=p→next;p→next=s;p→next→prior=s;
∙
D.s→prior=p;s→next=p→next;p→next→prior=s;p→next=s;
∙正确答案是:
【D】
解析:
本题主要考查如何在双向链表中插入一个结点,指针操作的顺序不是唯一的,但也不是任意的。
根据双向链表的结构特点可以知道,选项D所提供的操作顺序是正确的,具体过程如下图所示。
7
以下关于采用链式存储结构的线性表叙述中,不正确的是
∙
A.结点除自身信息外还包括指针域,因此存储密度小于顺序存储结构
∙
B.逻辑上相邻的结点物理上不必相邻
∙
C.可以通过计算直接确定第i个结点的存储地址
∙
D.插入、删除运算操作方便,不必移动结点
∙正确答案是:
【C】
解析:
选项C错误的原因是链式存储结构的地址不一定是连续的,所以不能通过计算直接确定第i个结点的存储地址。
8
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用下列存储方式最节省运算时间的是
∙
A.单链表
∙
B.仅有头指针的单循环链表
∙
C.双链表
∙
D.仅有尾指针的单循环链表
∙正确答案是:
【D】
解析:
本题显然应在选项B和选项D中选择正确答案,考虑到需要在最后一个元素之后插入和删除第一个元素,所以最好可以直接得到链表尾指针。
如果只有头指针,必须遍历所有链表才能得到尾指针。
9
若要在O
(1)的时间复杂度上实现两个循环单链表头尾相接,则对应两个循环单链表个设置一个指针,分别指向
∙
A.各自的头结点
∙
B.各自的尾结点
∙
C.各自的第一个元素结点
∙
D.一个表的头结点,另一个表的尾结点
∙正确答案是:
【B】
解析:
实现这样的操作需要能方便地找到两个循环单链表的尾结点,因此设置指向两个循环单链表的尾结点指针R1、R2,实现合并的过程如下图所示。
10
∙
A.S[i+1].data
∙
B.S[k+1].cur.data
∙
C.S[S[i].cur].data
∙
D.S[S[k].cur].data
∙正确答案是:
【C】
解析:
在静态链表中,第k个结点是S[i],其下一个结点(即第k+1个结点)的下标是S[k].cur,因此第k+1个结点是S[S[k].cur],其包含的数据是S[S[k].cur].data。
11
设一个一元多项式A和B的项数分别为m和n,均采用单链表表示,则进行A+B运算时最好情况下的时间复杂度为
∙
A.O(m)(当m>n)
∙
B.O(n)(当m
∙
C.O(m+n)
∙
D.O(m×n)
∙正确答案是:
【C】
解析:
当两个多项式单链表以指数有序排列时,实现相加运算时所花时间最少,为O(m+n)
12
线性表(a1,a2,a3,…,an)采用顺序存储,每个元素都是整数,试设计算法用最少时间把所有值为负数的元素移到全部正数值元素前边的算法。
要求:
(1)采用C或C++或JAVA语言描述算法,关键之处给出注释。
(2)说明你所设计算法的时间复杂度和空间复杂度。
∙参考答案是:
题目中要求重排以顺序存储结构存储的线性表的n个元素,使得所有值为负数的元素移到正数元素的前面。
可采用快速排序的思想来实现,只是提出暂存的第一个元素(枢轴)并不作为以后的比较标准,比较的标准是元素是否为负数。
【解答】
(1)用C语言算法描述如下:
intRearrange(inta[],intn){
inti=0,j=n-1;∥i,j为工作指针(下标),初始指向线性表a的第1个和第n个元素
intt=a[0];∥暂存枢轴元素。
while(i while(i if(i a[i]=a[j]; i++; } while(i if(i a[j]=a[i]; j--; } } a[i]=t;∥将原第一元素放到最终位置。 } (2)说明算法的复杂性: 上述算法时间复杂度为O(n),算法的空间复杂度为O (1)。 解析: 无 13 设将n(n>1)个整数存放到一维数组R中。 试设计一个在时间和空间两方面都尽可能高效的算法,将R中存有的序列循环左移p(0﹤p﹤n)个位置,即将R中的数据由(x0,x1,…,xn-1)变换为(x p,x p+1,…,x n-1,x0,x1,…,x p-1)。 要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 ∙参考答案是: 假设原数组序列为abcd1234,要求变换成的数组序列为1234abcd,即循环左移了4位。 比较之后,不难看出,其中有两段的顺序是不变的: 1234和abcd,可把这两段看成两个整体。 左移p位的过程就是把数组的两部分交换一下。 变换的过程通过以下步骤完成,举例如下: (1)全部逆序: abcd1234→4321dcba; (2)前n-p个数逆序排列: 4321dcba→1234dcba; (3)后p个数逆序排列: 1234dcba→1234abcd。 具体实现过程参看下面的解答。 【解答】 (1)算法的基本设计思想: 先将n个数据由x0,x1,…,xp,…,xn-1原地逆置,得到xn-1,…,xp,xp-1,…,x0,然后再将数组R中的前n-p个数和后p个数分别原地逆置,最终得到结果xp,xp+1,…,xn-1,x0,x1,…,xp-1。 (2)用C语言算法描述如下: voidreverse(intR[],intleft,intright){ intk=left,j=right,temp;//k等于左边界left,j等于右边界right while(k temp=R[k]; R[k]=R[j]; R[j]=temp; k++;//k右移一个位置 j--;//j左移一个位置 } } voidleftshift(intR[],intn,intp){ if(p>0&&p reverse(R,0,n-1);//将全部数据逆置 reverse(R,0,n-p-1);//将前n-p个元素逆置 reverse(R,n-p,n-1);//将后p个元素逆置 } } (3)说明算法的复杂性: 上述算法的时间复杂度为O(n),算法的空间复杂度为O (1)。 解析: 无 14 试编写一个尽可能高效的算法,实现在带头结点的单链表中删除(一个)最小值结点。 要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释。 ∙参考答案是: 【解答】 (1)算法的基本设计思想: 本题要求在单链表中删除最小值结点。 单链表中删除结点,为使结点删除后不出现“断链”,应知道被删结点的前驱。 而“最小值结点”是在遍历整个链表后才能知道。 所以算法应首先遍历链表,求得最小值结点及其前驱。 遍历结束后再执行删除操作。 (2)用C语言算法描述如下: voiddelete(Linklist&L){ LNode*p=L->next;∥假定链表非空,p为工作指针,指向待处理的结点。 LNode*pre=L;∥pre指向最小值结点的前驱 LNode*q=p;∥q指向最小值结点,初始假定第一元素结点是最小值结点 while(p->next! =NULL){ if(p->next->data pre=p; q=p->next; } p=p->next;∥指针后移 } pre->next=q->next;∥从链表上删除最小值结点 freeq;∥释放最小值结点空间 } 解析: 无 15 设计一个在时间和空间上尽可能高效的算法,将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。 要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释 ∙; ∙参考答案是: 【解答】 (1)算法的基本设计思想: 本题要求将链表中数据域值最小的结点移到链表的最前面。 首先要查找最小值结点,将其移到链表最前面,实质上是将该结点从链表上摘下(不是删除并回收空间),在插入到链表的最前面。 (2)用C语言算法描述如下: voiddelinsert(LinkList&L){ LNode*p=L->next;//p是链表的工作指针 LNode*pre=L;//pre指向链表中数据域最小值结点的前驱 LNode*q=p;//q指向数据域最小值结点,初始假定是第一结点 while(p->next! =NULL){ if(p->next->data pre=p; q=p->next; } p=p->next; } if(q! =L->next){//若最小值是第一元素结点,则不需再操作 pre->next=q->next;//将最小值结点从链表上摘下 q->next=L->next;//将q结点插到链表最前面 L->next=q; } } 解析: 无 16 编写一个算法,设有两个无头结点的单链表,头指针分别为ha,hb,两个链表的数据都按递增序存放。 现要求将hb表归到ha表中,且归并后ha仍递增序,在归并中对于ha表中已有的数据若hb中也有,则hb中的这部分数据不归并到ha中,hb的链表在算法中不允许破坏。 ∙参考答案是: 【分析】本题与“将两个按元素值递增次序排列的线性表,归并为一个按元素值非递增次序排列的单链表”问题类似,不同之处在于: 一是链表无头结点,为处理方便,给加上头结点,处理结束再删除之;二是数据相同的结点,不合并到结果链表中;三是hb链表不能被破坏,即将hb的结点合并到结果链表时,要生成新结点。 【解答】用C语言算法描述如下: voidUnion(LinkList&ha,LinkListhb){ LinkListla; la=(LinkList)malloc(sizeof(LNode)); la->next=ha;∥申请头结点以便操作 LNode*pa=ha;∥pa是ha链表的工作指针 LNode*pb=hb;∥pb是hb链表的工作指针 LNode*pre=la;∥pre指向当前待合并结点的前驱 while(pa&&pb) if(pa->data pre->next=pa; pre=pa; pa=pa->next; } elseif(pa->data>pb->data){∥处理hb中数据。 r=(LinkList)malloc(sizeof(LNode));∥申请空间 r->data=pb->data; pre->next=r; pre=r;∥将新结点链入结果链表 pb=pb->next;∥hb链表中工作指针后移 } else{∥处理pa->data=pb->data; pre->next=pa; pre=pa; pa=pa->next;∥两结点数据相等时,只将ha的数据链入 pb=pb->next;∥不要hb的相等数据 } if(pa! =NULL)pre->next=pa;∥将两链表中剩余部分链入结果链表 elsepre->next=pb; freela;∥释放头结点,ha、hb指针未被破坏 } 解析: 无 17 已知不带头结点的线性链表list,请写一算法,将该链表按结点数据域的值的大小从小到大重新链接。 要求链接过程中不得使用除该链表以外的任何链结点空间。 ∙参考答案是: 【分析】本题实质上是一个排序问题,要求“不得使用除该链表结点以外的任何链结点空间”。 链表上的排序采用直接插入排序比较方便,即首先假定第一个结点有序,然后,从第二个结点开始,依次插入到前面有序链表中,最终达到整个链表有序。 【解答】用C语言算法描述如下: LinkListLinkListSort(LinkList&list){//list是不带头结点的线性链表 LNode*p=list->next;∥p是工作指针,指向待排序的当前元素 list->next=NULL;∥假定第一个元素有序,即链表中现在只有一个结点 while(p! =NULL){ r=p->next;∥r是p的后继 q=list; if(q->data>p->data){∥处理待排序结点p比第一个元素结点小的情况 p->next=list; list=p;∥链表指针指向最小元素 } else{∥查找元素值最小的结点 while(q->next! =NULL&&q->next->data q=q->next; p->next=q->next;∥将当前排序结点链入有序链表中 q->next=p; } p=r;∥p指向下个待排序结点 } } 算法时间复杂度的分析与用顺序存储结构时的情况相同。 但顺序存储结构将第i(i>1)个元素插入到前面第1至第i-1个元素的有序表时,是将第i个元素先与第i-1个元素比较。 而在链表最佳情况均是和第一元素比较。 两种存储结构下最佳和最差情况的比较次数相同,在链表情况下,不移动元素,而是修改结点指针。 另外,本题中线性链表list不带头结点,而且要求“不得使用除该链表以外的任何链结点空间”,所以处理复杂,需要考虑当前结点元素值比有序链表第一结点的元素值还小的情况,这时要修改链表指针list。 如果list是头结点的指针,则相应处理要简单些,其算法如下: LinkListLinkListSort(LinkList&list){//list是带头结点的线性链表 LNode*p=list->next;∥p指向第一元素结点 list->next=NULL;∥有序链表初始化为空 while(p! =NULL){ r=p->next;∥保存后继 q=list; while(q->next! =NULL&&q->next->data q=q->next; p->next=q->next; q->next=p; q=r; } } 解析: 无 18 设单链表的表头指针为h,链表中结点构造为(data,next),其中data域为字符型。 编写算法判断该链表的前n个字符是否中心对称。 例如xyx,xyyx都是中心对称。 ∙参考答案是: 【分析】判断链表中数据是否中心对称,通常使用栈。 将链表的前一半元素依次进栈。 在处理链表的后一半元素时,当访问到链表的一个元素后,就从栈中弹出一个元素,两元素比较,若相等,则将链表中下一元素与栈中再弹出元素比较,直至链表到尾。 这时若栈是空栈,则得出链表中心对称的结论;否则,当链表中一元素与栈中弹出元素不等时,结论为链表非中心对称,结束算法的执行。 【解答】用C语言算法描述如下: intdc(LinkListh,intn){ chars[];inti=1;∥i记结点个数,s字符栈 LNode*p=h->next;∥p是链表的工作指针,指向待处理的当前元素。 for(i=1;i<=n/2;i++){∥链表前一半元素进栈。 s[i]=p->data; p=p->next; } i--;∥恢复最后的i值 if(n%2==1)p=p->next;∥若n是奇数,后移过中心结点 while(p! =NULL&&s[i]==p->data){∥测试是否中心对称 i--; p=p->next; } if(p==NULL)return1;∥链表中心对称 elsereturn0;∥链表不中心对称 } 算法中先将“链表的前一半”元素(字符)进栈。 当n为偶数时,前一半和后一半的个数相同;当n为奇数时,链表中心结点字符不必比较,移动链表指针到下一字符开始比较。 比较过程中遇到不相等时,立即退出while循环,不再进行比较。 解析: 无 19 设有一个带头结点的循环双链表,所有元素值均为整数,设计一个算法输出其倒数第k个结点的值。 ∙参考答案是: 【分析】通过头结点的prior域查找到尾结点,再沿prior域向前查找k-1次,即找到倒数第k个结点。 【解答】用C语言算法描述如下: intfindk(DuLinkListL,intk){ inti=1; DuLNode*p=L->prior;//p指向尾结点,i置为1 while(p! =L&&i i++; p=p->prior; } if(p==L)//未找到则返回0 return0; else{//找到倒数第k个结点,输出其值并返回1 printf(”%d\n”,p->data); return1; } } 解析: 无 20 已知两个单链表A和B,其头指针分别为heada和headb,编写一个过程从单链表A中删除自第i个元素起的共len个元素,然后将单链表A插入到单链表B的第j个元素之前。 ∙参考答案是: 【分析】在单链表中删除自第i个元素起的共len个元素,应从第1个元素起开始计数,记到第i个时开始数len个,然后将第i-1个元素的后继指针指向第i+len个结点,实现了在A链表中删除自第i个起的len个结点。 这时继续查到A的尾结点,以便插入B链表使用。 这时也得到了删除元素后的A链表。 再查B链表的第j个元素,将A链表插入之。 插入和删除中应注意前驱后继关系,不能使链表“断链”。 另外,算法中应判断i,len和j的合法性。 【解答】用C语言算法描述如下: LinkListDelInsert(LinkListheada,headb,inti,j,len){ if(i<1||len<1||j<1){ printf(“参数错误\n”); exit(0);∥参数错则退出算法 } p=heada;/*p为链表A的工作指针,初始化为A的头指针,查到第i个元素时,p指向第i-1个元素*/ k=0;∥计数 while(p! =NULL&&k k++; p=p->next; } if(p==NULL){ printf(“给的%d太大\n”,i); exit(0);∥i太大,退出算法 } q=p->next;∥q为工作指针,初始指向A链表第一个被删结点 k=0; while(q! =NULL&&k k++; u=q; q=q->next; free(u); } if(k printf(“给的%d太大\n”,len); exit(0);∥ken太大,退出算法 } p->next=q;∥A链表删除了len个元素 if(heada->next! =NULL){/*若heada->next=NULL说明链表中结点均已删除,无需往B表插入*/ while(p->next! =NULL)∥找A的尾结点 p=p->next; q=headb;∥q为链表B的工作指针 k=0;∥计数 while(q! =NULL&&k k++; q=q->next;∥查找成功时,q指向第j-1个结点 } if(q==NULL){ printf(“给的%d太大\n”,j); exit(0);∥j太大,退出算法 } p->next=q->next;∥将A链表链入 q->next=heada->next;∥A的第一元素结点链在B的第j-1个结点之后 } free(heada);∥释放A表头结点。 } 解析: 无 重点回顾 1.线性表的逻辑结构 注: 线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列,通常记为: (a1,a2,…ai-1,ai,ai+1,…an)其中n为表长,n=0时称为空表。 需要说明的是: ai为序号为i的数据元素(i=1,2,…,n)。 2.线性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 线性表 线性