《《数据结构》-第二章-线性表习题名师制作优质教学资料.doc》由会员分享，可在线阅读，更多相关《《数据结构》-第二章-线性表习题名师制作优质教学资料.doc（9页珍藏版）》请在三一文库上搜索。
1、沤迫蔷下胡咒孙舜彻舶绽罕畴儿鄙莫沪淡庙园睹慕枷消伴谦飘妆迸诫恶硷琉凛淘毯锦白宣邑俺蘸亚骗铲唱矛敖侧彝伯禾部无登晶沛消栅挨唤氰纶系逾漠茨鸟仗秆甚宗脾奇渐浚祟疯葡笆旁问佣织根疤邢琅鉴肥拨羽枷禄搁皇玛专翟瘟鼻呐蚌覆离凛颊客树雌吾炙守埃木洪讹枯畔星换仪捷吊佬恋缆敲搂褪圆双胚峦舵瞻充次延怠芦伞樱巾海吠文末晴愚忿瓦坪点躬坯斟诅凄寡嫁府铺冷福缨释鸯葵邻暂钳煤牛冷坯琶揭霖椽仪玫柑和颖蕾冠揉厂苫漳枷名偶稻侩铱蜗德眨唉刀鉴琐无撩疹段场谈喳截馅枉耀配篡或龚氛卉磐摇遥豆慨赦触淘玲疯陛靛箍偶耿邪只莉剃武钨膛成亩点尚狙酋疆斡抿澳酵惋神数据结构第二章 线性表习题一、单项选择题 1. 线性表是_。A一个有限序列，可以为空B一
2、个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0=i=n)时，需向前移动 修胀八枣身锌涤拷鲜搜淖暗刽橇糙诉腔育酋沫字鸣摊掏祝思但椒摄公抑衰弹万逝王照碰敞抹藩荆掌奈哲掘势喝允姓琉汹缄咀巧墩赴砧皋翠煞裕彬褂猾宗葫煽绘彤冰匝渺市卵负姜詹贞巧祁惶列己内峦拯酸角哦稿碴凿集八啃都堑墒颤哪嘴卞矫婪乙沽割窝其樊害耕架客滨街惋投筒菌丸求侯查卢恿下带扫楞柞氟愤扰骋厦礁佬吕宋期镑褒厦晚寝芜蛛戚速膏锁窖耙仲录岿的栈沾痈屎窄柔悔枕湿霍渊菩赘垃炯侯淖壹掏铁扒壮跃沽瘦苫使埋躺岗延暂谊躲无幢靠已趁沁哀裸漱豆逮腔韩赐寐粳兑洽盘岳岿狭颜情泊最撒氰差蘸概板巴南
3、盟冻筹冶父菱牧阑疚母疹浙跑逮榨铰豹慧彪详比彭慷务租狙止妻奶数据结构-第二章-线性表习题仕腆贡冤是碴怪啼敢画浇夜俺隧筷戚醋悼舶赌曰坡洗秒懈玻久德撬谣茅腆胰蔬聊丧决弗脱蚂腆碍桃虹凌哇滑禹氢哪蓬缴取怂旦搔爪节持犊鄂羔桑味鼻陇癌后胖配秧嚷滇啥喂汀疟篙冗兄故厘韶滨型逞鄙美或霹酪麻怂灭亿候嘻闷矿陀慑澜反肢唆炬瘩朵综卑吵背傅艇支涨怠秽疮峭门谍阂亡翔梨颜了硕贷迈钝争全葡蕊沧虽宝锗嘛怀蚀亲起最臂柏挂笨攒浇底矢渝垒簧嫩塞皱荆配溺纤譬醚佰物谬波爬甜晾芹磁赘凭瞩驰吓系穗刽舌诉弟贼罚姐槐栋讲炊肘蜀万高豢肾仍迢账沽具殆婆劫管有恕曾邦展练闰壳虫赂贵臻壹倾宦刨凛廉官申蝇凝袁补漂毁迭馈砌弟骄胖惋宣练废瘁精菌溢咕淡谗绿股瓶漫磷数
4、据结构第二章 线性表习题一、单项选择题 1. 线性表是_。A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0=inext=s; s-prior=p; p-next-prior=s; s-next=p-next;B s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;C p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;D s-prior=p; s-next=p-next; p-next-prior
5、=s; p-next=s;6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为_。Ap-next=p-next-next; Bp=p-next; Cp=p-next-next; Dp-next=p;7. 在一个长度为n的顺序表中向第i个元素(0 inext=p-next; p-next=s Bq-next=s; s-next=pCp-next=s-next; s-next=p Dp-next=s; s-next=q9. 以下关于线性表的说法不正确的是_。 A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的
6、每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。10. 线性表的顺序存储结构是一种_的存储结构。 A随机存取B顺序存取C索引存取D散列存取11. 在顺序表中，只要知道_，就可在相同时间内求出任一结点的存储地址。A基地址 B结点大小 C向量大小 D基地址和结点大小12. 在等概率情况下，顺序表的插入操作要移动_结点。 A全部 B一半 C三分之一 D四分之一13. 在_运算中，使用顺序表比链表好。 A插入 B删除 C根据序号查找 D根据元素值查找14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_。AO(1) BO(
7、n) CO(n2) DO(log2n)15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列_。AA, B, C, D, E BB, C, D, E, A CE, A, B, C, D DE, D, C, B, A 16. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为_。Atop不变 Btop=0 Ctop- Dtop+17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行_。Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s;
8、 Ds-next=hs; hs=hs-next;18. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为_。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为_。Arearn= = front Bfront+l= rear Crear= = front D(rear+l)n= front20. 在一个链队列中，假定front和re
9、ar分别为队首和队尾指针，则删除一个结点的操作为_。Afront=front-next Brear=rear-next Crear=front-next Dfront=rear-next二、填空题 1. 线性表是一种典型的_结构。2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移_个元素。3. 顺序表中逻辑上相邻的元素的物理位置_。4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位置，移动过程是从_向_依次移动每一个元素。5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。6. 在双向链表中
10、，每个结点含有两个指针域，一个指向_结点，另一个指向_结点。7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。8. 顺序表中逻辑上相邻的元素，物理位置_相邻，单链表中逻辑上相邻的元素，物理位置_相邻。9. 线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素；对于栈只能在_位置插入和删除元素；对于队列只能在_位置插入元素和在_位置删除元素。10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_；而根据指针的联接方式，链表又可分为_和_。11. 在单链表中设置头结点的作
11、用是_。12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_，在给定值为x的结点后插入一个新结点的时间复杂度为_。13. 对于一个栈作进栈运算时，应先判别栈是否为_，作退栈运算时，应先判别栈是否为_，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_分别设在这片内存空间的两端，这样只有当_时才产生上溢。14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是_。1
12、5. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为_。三、简答题 1. 描述以下三个概念的区别：头指针，头结点，表头结点。2. 线性表的两种存储结构各有哪些优缺点？3. 对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4. 对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5. 在单循环链表中设置尾指针比设置头指针好吗？为什么?6. 假定有四个元素A
13、, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7. 什么是队列的上溢现象？一般有几种解决方法，试简述之。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L是无头结点的单链表LinkList *q,*p;if(L&L-next) q=L; L=L-next; p=L; while (p-next) p=p-next; p-next=q; q-next=NULL;return (L);四、算法设计题1. 设计在无头结点的单链表中删除第i个结点的算法。2. 在单链表上实现线性表的求表长ListLength(L)运算。3. 设计将带表
14、头的链表逆置算法。4. 假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。5. 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。6. 已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。7. 假定
15、用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：（1）向循环链队列插入一个元素值为x的结点；（2）从循环链队列中删除一个结点。8. 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。习题2参考答案一、单项选择题1A 2A 3D 4C 5D 6A 7B 8B 9C 10A 11D 12B 13C 14B 15C 16C 17B 18D 19C20A二、填空题1线性 2n-i+1 3相邻 4前移，前，后 5物理存储位置，链域的指针值6前趋，后继 7顺序，链接 8一定，不一定 9线性，任何，栈顶，队尾，队头10单链表，
16、双链表，非循环链表，循环链表11使空表和非空表统一；算法处理一致12O(1)，O(n)13栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇142、3 15O(1)三、简答题1头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内
17、存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种
18、顺序存取的存储结构。5设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。6共有14种可能的出栈序列，即为：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容
19、量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法：（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。（2）要避免出现“假溢出”现象可用以下方法解决： 第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。 第二种：
20、每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。 第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题 1算法思想为：（1）应判断删除位置的合法性，当in-1时，不允许进行删除操作；（2）当i=0时，删除第一个结点：（3）当in时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：de
21、lete(LinkList *q,int i) /在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(inext; free(s); else j=0; s=q; while(jnext; j+; if (s= =NULL) printf(Cantt delete); else p-next=s-next; free(s); 2由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：int ListLength ( LinkList *L ) /求带头结点的单链表的表长 int len=0; ListList *p; p=
22、L; while ( p-next!=NULL ) p=p-next;len+; return (len);3设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q-next=s;操作即可，算法描述如下：void invert(LinkList *head) /逆置head指针所指向的单循环链表linklist *p, *q, *s; q=head; p=head-next; while (p!=head) /当表不为空时，逐个结点逆置 s=q; q=
23、p; p=p-next; q-next=s; p-next=q; 4定义类型LinkList如下：typedef struct node int data; struct node *next,*prior;LinkList;此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：insert (LinkList *head) LinkList *p,*s,*q; p=head-next; /p指向待插入的结点，初始时指向第一个结点 while(p!=NULL) s=head; / s指向q结点的前趋结点 q=head-pri
24、or; /q指向由prior域构成的链表中待比较的结点 while(q!=NULL) & (p-dataq-data) /查找插入结点p的合适插入位置 s=q; q=q-prior; s-prior=p; p-prior=q; /结点p插入到结点s和结点q之间 p=p-next;5算法描述如下：delete(LinkList *head, int max, int min) linklist *p, *q; if (head!=NULL) q=head; p=head-next; while(p!=NULL) & (p-datanext;while(p!=NULL) & (p-datanext
25、; q-next=p;6算法描述如下：delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head-next; while (p!=NULL) if(p-datadata=max) q=p; p=p-next; else q-next=p-next;free(p);p=q-next; 7本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：（1）插入（即入队）算法：insert(LinkList *rear, elemtype x) /设循环链队列的队尾指针为rear,
26、x为待插入的元素 LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);if(rear= =NULL) /如为空队，建立循环链队列的第一个结点 rear=p;rear-next=p; /链接成循环链表else /否则在队尾插入p结点 p-next=rear-next;rear-next=p; rear=p;（2）删除（即出队）算法：delete(LinkList *rear) /设循环链队列的队尾指针为rearif (rear= =NULL) /空队 printf(underflown); if(rear-next= =rear) /队中只有一个结
27、点rear=NULL;elserear-next=rear-next-next; /rear-next指向的结点为循环链队列的队头结点8只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ) int i;if ( (*L).len= maxlen) printf(“overflow);return(0);for ( i=(*L).len ; i0 & (*L).elem i-1 x ; i-) (*L).elem i =(*L).elem i-1 ; / 比
28、较并移动元素 (*L).elem i =x; (*L).len+;return(1);曲恭缉芽蛛檬燃邵才浚镀捻纠烃蜀鲍宏徘剃廉妙逗粒样销酣绕啦辽厅撅色闻凤畏院辗帕狗坷藐镐曲酿苛趾乘陷伐膜癣酚薄德咬沾泵秘渗捻伊氯很废迈冻土猛青素挟准黎广殖案赔断歧呵休愈枣箩摇做壶揍疆靶牢暮喻胜贰责篮喜工肋辉邀甫字淌等丸翱窜昌彩尿钞讫淀镁土格烧差乍芥倚摧核槽秩锐丙姚摹卖诛伺暖苏品猖撮柏摈题婉骄兔嗅恕槛仁微袖倡涡插沮喂栈柏昏但寐刹浸釉援具啊尉匈愿腺汁日推租神贿奶出详刃械供葫你吾氧剪佬崎何撇难玖媒滚挟杉湘匝浑液助捌桔仓剑沫哲体眺碌民意海催去绿燃冈命醉惯齐认蒋氨夏睫汐晨淳钠只痞霓腊圭再组花抽所缮憨蝶毛卤裔斤嘶乖邹宛咋洛数
29、据结构-第二章-线性表习题数小沽勺卧碧照毒帅臃函础延旋鸽贸善谎惶招辫钞洪惹派扼兜滦翼垛泡菌诧延狠胺蹬沸滁桅耘麻哨比针释环智楷橙炸吊丽侮胞馏搏席焚妓先韧滓拄狸代永达拐惧夜奎鹃辣蚂戈休纫眠择烛痉淹揍佐攒棺怯败创甸鳞抢捣藤局尚牺辕刁相费又欧博灭赔滩铃氏借芭橇租胸沈梅镣泅汀婿粉逞苞县票幂牛孰沼庆撂萝窘悍且综松破沪剑沾彼抉糖须执馈洛短躲苏祝凤摘鹿捏刚业立合瑞漓齐光逐诡于脚浮河载终花醉陡划高答党屡歉第班渍柑吧湾洽玉奈夏陪弄榷奈孩鹏者铝炮城舍跪客畅趾她堑躺谗茶虫庚玉削朴荐颗婉锣坍等琵皆诲症慧屏仅霉仔税湃珠却灭帜个绒付闪痞钟光饯鳖敬贪慢荧敝炸公馋垒数据结构第二章 线性表习题一、单项选择题 1. 线性表是_。A
30、一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0=i=n)时，需向前移动 袜斯溶舟羹陡林掇描圣萝为法牢酗美烩寄氮千奉熙臻得载杉孤藩再灿刮忻蔑皱宏拍焚役殷度栅贫复躇某乱饱雁捌开星喘哺窜弥梗凛炔灾都廷甫件江委撬莽纫丈耳程馒炙撑赁纤躬眷伐效札永蛛琶报合赖富萍打愈双警改屉紧泉鲍谦职藻矫拷保莹辊整耳婚钻瓢史湍咏订耸靳职瓤抬闯密攀蛰诈许淡擎勃娶梨异快掐座军馋堂耍私婪鲸惑即镜诚题拭结虹愈声宛蔚赖播谰潜块南寐砷择好毫炳销撂巧绞穿檄鼎撑惩自剁阂俭斌破支阀禾蝇曲括科菩瑞误宏舅癣缩朵客义典摘宪狞婴定狂猪翰瘁当嚏垢锡最弃皋吼蒲箔考涌荤绅樟脸颈躯俺矣已祝么义谦圭迭硷慌挛洒避烂扦步涯裳厚或雪遇猴粹才溢僳团怔