《大学《数据结构》习题（附答案）.pdf》由会员分享，可在线阅读，更多相关《大学《数据结构》习题（附答案）.pdf（101页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章 绪 论1.1选择题1.算法的时间复杂度取决于(C )A)问题的规模 B)待处理数据的初态 C)A和B2.计算机算法指的是解决问题的步骤序列，它必须具备(B)这三个特性。A)可执行性、可移植性、可扩充性B)可执行性、确定性、有穷性C)确定性、有穷性、稳定性D)易读性、稳定性、安全性5.从逻辑上可以把数据结构分为(C)两大类。A)动态结构、静态结构 B)顺序结构、链式结构 C)线性结构、非线性结构D)初等结构、构造型结构6.在下面的程序段中，对x的赋值的语句频度为(C)for(i=0;in;i+)for(j=0;j=l;i)for(j=l;jAU+l)Aj与 Aj+1对换；A.O(n)B)
2、O(nlog2n)C)O(n3)D)O(n2)1.2填空题2.对 于 给 定 的n个元素，可以构造出的逻辑结构有集合、线性结构、树形结构、图状结构或网状结构四种。4.数据结构中评价算法的两个重要指标是：算法的时间复杂度和空间复杂度。5.数据结构是研讨数据的 逻 楫 结 构 和 物 理 结 构 以及它们之间的相互关系,并对与这种结构定义相应的 操 作(运 算)设计出相应的一算法.6.一个算法具有5个特性：有穷性_、确定性、可行性，有零个或多个输入、有一个或多个输出。9.已知如下程序段for(i=n;i0;i)语句 1 x=x+1;语句 2for(j=n;j=i;j-)语句 3y=y+l；语句 4
3、语 句1执行的频度为_n+l_;语 句2执行的频度为_ n _;语 句3执行的频度为_n(n+3)/2_;语 句4执 2 数据结构期末习题复习行的频度为_n(n+l)/2_。10.在下面的程序段中，对x的赋值语句的频度为(表示为n的函数)for(i=0;in;i+)for(j=0;ji;j+)for(k=0;kj;k+)x=x+delta;【答案】1+(1+2)+(1+2+3)+.+(l+2+.+n)=n(n+l)(n+2)/6,O(n3)11.下 面 程 序 段 中 带 下 划 线 的 语 句 的 执 行 次 数 的 数 量 级 是。i=l;while(in)i=i*2：【答案】log2n1
4、2.计算机执行下面的语句时，语 句s的执行次数为.for(i=l;i=i;j-)s;【答案】(n+3)(n-2)/213.下 面 程 序 段 的 时 间 复 杂 度 为。(nl)sum=l;for(i=0;sumn;i+)su m+=l;【答案】O(n)第2章 线 性 表2.1 选择题1.对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则 选 择(A)最节省时间A)顺序表 B)带头结点的双循环链表 C)单链表 D)带尾结点的单循环链表2.若长度为n的线性表采用顺序存储结构，在 其 第i个位置插入一个新元素的算法时间复杂度为(C)(1 iprior=q;q-next=p;p-prio
5、r-next=q;q-prior=p-prior;B)q-prior=p-prior;p-prior-next=q;q-next=p;p-prior=q-next;C)q-next=p;p-next=q;p-prior-next=q;q-next=p;D)p-prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;4.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是(C)A)O(nlog2n)B)0(1)C)0(n)D)0(n2)5.在一个以h为头指针的单循环链中，p指针指向链尾结点的条件是(B)第2部分习题解析3A)p-nex
6、t=NULL B)p-next=h C)p-next-next=h D)p-data=-l6.对于一个具有n个结点的线性表，建立其单链表的时间复杂度是(A)A)0(n)B)0(1)C)O(nlog2n)D)0(n*2),在 给 定 值 为x的 结 点 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为.【答 案】(1)0(1)(2)0(n)7.对于双向链表，在两个结点之间插入一个新结点需修改的指针共 4 个，单链表为2 个，8.循 环 单 链 表 的 最 大 优 点 是。【答案】从任一结点出发都可访问到链表中每一个元素。9.若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结
7、点时，可执行下列操作：s-next=:8.在双向链表存储结构中，删 除p所指的结点时须修改指针(A)A)p-prior-next=p-next p-next-prior=p-prior;B)p-prior=p-prior-prior p-prior-next=p;C)p-next-prior=p p-next=p-next-nextD)p-next=p-prior-prior p-prior=p-next-next;9.线性表采用链式存储时，其元素地址(D)A)必须是连续的 B)一定是不连续的 C)部分地址是连续的 D)连续与否均可2.2填空题1.线 性 表L=(ai，a2,a n)用数组表示
8、，假定删除表中任一元素的概率相同，则删除一个元素 平 均 需 要 移 动 元 素 的 个 数 是。【答案】(n-l)/22.在 单 链 表 中 设 置 头 结 点 的 作 用 是【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。3.线性表的顺序存储是通过 来反应元素之间的逻辑关系，而链式存储结构是通过来反应元素之间的逻辑关系。【答案】(1)数据元素的前后顺序(2)元素中的指针4.当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用存储结构最节省时间，相反当经常进行插入和删除操作时，则采用 存储结
9、构最节省时间。【答案】(1)顺 序(2)链式5.对 于 一 个 具 有n个结点的 单 链 表，在已知的结点*p后插入一个新结点的时间复杂度为 4 数据结构期末习题复习p-next=s;t=p-data;p-dat a=;s-data=_ 答案（1 ）p-next（2）s-data（3）t10.某线性表采用顺序存储结构，每个 元 素 占 据4个存储单元，首 地 址 为1 0 0,则 下 标 为11的（第12个）元素的存储地址为14411.带头结点的双循环链表L中 只 有 一 个 元 素 结 点 的 条 件 是。【答案】L-next-next=L2.3 判断题1.取线性表的第i个元素的时间同i的大
10、小有关（）【答案】x2.线性表的特点是每个元素都有一个前驱和一个后继（）【答案】x3.顺序存储方式的优点是存储密度大，且插入、删除运算效率高（）【答案】x4.线性表采用链表存储时，结点的存储空间可以是不连续的（）【答案】45.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率 高（）【答案】46.顺序存储方式只能用于存储线性结构（）【答案】x解析】线性结构、树型结构和图状结构均可用顺序存储表示。9.顺序存储结构的主要缺点是不利于插入或删除操作（）【答案】410.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（）【答案】x2.4程序设计题1.设顺序表
11、va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。void Insert_SqList（SqList va,int x）/陶巴 x 插入递增有序表 va 中 */int i;if（va.length MAXSIZE）return;for（i=va.length-1 ;va.elemfix&i=0;i）va.elemi+1 =va.elemi;va.elemi4-l=x;va.length+;/*Insert_SqList*/2.设A=（ai，a?,.，am）和B=（b，b 2,，bn）均为顺序表，试设计一个比较A,B大小的算 法（请注意：在算法中，不要
12、破坏原表A和B）。【算法分析】比较顺序表A和B,并用返回值表示结果，值 为1,表 示A B;值 为 表 示AB;第2部分习题解析 5值 为0,表 示A=B。1 )当两个顺序表可以互相比较时，若对应元素不等，则返回值为1或-1;2)当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则 返 回 值 为0;否则，哪个较长，哪个就较大【算法源代码】int ListComp(SqList A,SqList B)for(i=l;i=A.length&iB.elemi?11;if(A.length=B.length)return 0;return A.lengthB.length?11;/*当两个顺序
13、表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/*ListComp*/3.已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试设计一个算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后)，假设指针he指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。【算法分析】1 )单链表ha的头结点作为连接后的链表的头结点，即hc=ha;2)查找单链表ha的最后一个结点，由指针p指向，即p-next=NULL;3)将单链表hb的首元结点(非头结点)连接在p之后，即p-next=hb-next;4)回收单链表hb的头结点空
14、间【算法源代码】void ListConcat(LinkList ha,LinkList hb,LinkList*hc)/*把链表 hb接在 ha 后面形成链表 he*/*hc=ha;p=ha;/*由指针p指 向ha的尾元结点*/p=p-next;p-next=hb-next;free(hb);/*ListConcat*/4.试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。【算法分析】1)生成新结点存放元素b,由指针new指向；2)将new插入在单链表的第i个元素的位置上：若i=l,new插在链表首部；否
15、则查找第i-1个结点，由指针p指向，然后将new插 在p之后。【算法源代码】void Insert(LinkList*L,int i,int b)6 数据结构期末习题复习 LinkList new;new=(LinkList*)malloc(sizeof(LNode);new-data=b;if(i=l)/*插入在链表头部*/New-next=*L;*L=new;)else /*插入在第i个元素的位置*/p=*L;while(-il)p=p-next;new-next=p-next;p-next=new;)/*Insert*/5.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计
16、一个高效的算法，删除表中所有值大于mink且 小 于maxk的元素(若表中存在这样的元素)，同时释放被删结点空间(注意：mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同，也 可 以 不 同)。【算法分析】1)查找最后一个不大于mink的元素结点，由指针p指向；2)如果还有比mink更大的元素，查找第一个不小于maxk的元素，由指针q指向；3)p-next=q,即删除表中所有值大于mink且小于maxk的元素。【算法源代码】void Delete_Between(LinkList*L,int mink,int maxk)p=*L;while(p-next-datanext;/*
17、p 是最后一个不大于 mink 的元素*/if(p-next)/*如果还有比mink更大的元素*/(q=p-next;while(q-datanext;/*q 是第一个不小于 maxk 的元素*/p-next=q;)/*Delete_B etween*/6.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)，同时释放被删结点空间。第 2 部分习题解析7【算法分析】1)初始化指针p 和 q,分别指向链表中相邻的两个元素；2)当p-next不为空时，做如下处理：若相邻两元素不相等时，p 和 q 都
18、向后推一步；否则，当相邻元素相等时，删除多余元素。【算法源代码】void Delete_Equal(LinkList*L)p=(*L)-next;q=p-next;/*p和 q 指向相邻的两个元素*/while(p-next)(if(p-data!=qdata)/*若相邻两元素不相等时，p 和 q 都向后推一步*/p=p-next;q=p-next;)else(while(q-data=p-data)/*当相邻元素相等时删除多余元素*/(r=q；q=q-next;free(r);)p-next=q;p=q;q=p-next;/*else*/*while*/*Delete_Equal*/7.试设
19、计一个算法，对带头结点的单链表实现就地逆置。【算法分析】1 )空表或长度为1的表，不做任何处理；2)表长大于2 时，做如下处理：首先将整个链表一分为二，即从链表的第一元素结点处断开；逐个地把剩余链表的当前元素q 插入到链表的头部。【算法源代码】void LinkList_reverse(LinkList L)if(!L-nextll!L-next-next)return;p=L-next;q=p-next;s=q-next;8 数据结构期末习题复习p-next=NULL;/*从链表的第一元素结点处断开*/while(s-next)q-next=p;p=q;q=s；s=s-next;/*把L的元
20、素逐个插入新表表头*/)q-next=p;s-next=q;L-next=s;/*Li nkLi st_reverse*/8.设 线 性 表A=(ai，a 2,，am)和B=(b；b?,.，bn)5试设计一个按下列规则合并A,B为线性表C的算法，即使得C=(a，b,.，U m,bm,bm+i,bn)当 mWn 时；或者C=(a，b,，3n，bn,3n+1 ,Hm)当 Hl n 日 寸 o线 性 表A,B和C均以单链表作存储结构，且C表 利 用A表 和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【算法分析】1)初始化指针p指向链表A的当前元素，指 针q指向链表B的当前元素；2)
21、当链表A和B均为结束时，做如下处理：将B的元素插入 若A非空，将A的元素插入指针p和q同时后移【算法源代码】void mergel(LinkList A,LinkList B,LinkList*C)p=A-next;q=B-next;*C=A;while(p&q)s=p-next;p-next=q;/*将 B 的元素插入*/if(s)t=q-next;q-next=s;/*若A非空，将A的元素插入*/)p=s;q=t;/*指 针p和q同时后移*/*while*/*mergel*/9.假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，请设计一个算法将A表 和B表归并成一个按元素
22、值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性 表C,并要求利用原表(即A表 和B表)的结点空间构造C表。第2部分习题解析 9【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处，最后处理A或B的剩余元素。【算法源代码】void re ver se_merge(Li nkLi s t A,LinkList B,LinkList*C)LinkList pa,pb,pre;pa=A-next;pb=B-next;/*pa和pb分别指向A和B的当前元素*/pre=NULL;while(pallpb)if(pa-datavpb-datall!pb)/*将 A 的元素插入新
23、表*/pc=pa;q=pa-next;pa-next=pre;pa=q;else/*将B的元素插入新表*/pc=pb;q=pb-next;pb-next=pre;pb=q;pre=pc;)*C=A;A-next=pc;/*构造新表头*/*re verse_merge*/1 0.已 知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出 现 又 在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度(注意：题中没有特别指明同一表中的元素值各不相同)。【算法分析】先 从B和C中找出共有元素，记 为sam e,再 在A中从当前位置开始，凡 小 于s
24、ame的元素均保留(存到新的位置)，等 于same的就跳过，到大于same时就再找下一个same。【算法源代码】void SqList_Intersect_Delete(SqList*A,SqList B,SqList C)i=0;j=0;k=0;m=0;/*i指 示A中元素原来的位置，m为移动后的位置*/while(i(*A).length&jB.length&kC.length)if(B.e!emjC.eIemk)k+;elsesame=B.elemfj;/*找到 了相同元素 same*/while(B.elemj=same)j+;while(C.elemk=same)k+;/*j 和 k
25、后移到新的元素*/while(i(*A).length&(*A).elemisame)(*A).elemm+=(*A).elemi+;/*需保留的元素移动到新位置*/while(i(*A).length&(*A).elemi=same)i+;/*跳过相同的元素*/10 数据结构期末习题复习/*while*/while(inext!=NULL)/*链表不为空表*/p=Ia-next-next;/*p指向第一结点的后继*/la-next-next=NULL;/*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/while(p!=NULL)r=pnext;/*暂 存p的后继*/q=la;wh
26、ile(q-next!=NULL&q-next-datavp-data)q=q-next;/*查找才宙入位置*/p-next=q-next;/*将p结点链入链表*/q-next=p;p=r；)12.设有一个双向循环链表，每个结点中除有prior,data和next三个域外，还增设了一个访问频度 域freq。在链表被起用之前，频 度域freq的值均初始化为零，而每当对链表进行一次LOCATE(L,X)的操作后，被访问的结点(元素值等于X的结点)中的频度域freq的值便增1,同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上
27、述要求的LOCATE操作的算法。【算法分析】1 )在双向链表中查找数据值为x的结点，由 指 针p指向，若找不到，直接返回，否 则 执 行 第2步；2)修 改x结点的访问频度freq,并将结点从链表上摘下；3)顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插 在q之后。【算法源代码】DuLNode*第2部分习题解析 II Locate_DuList(DuLinkList*L,int x)p=(*L)-next;while(p.data!=x&p!=(*L)p=p-next;if(p=(*L)return NULL;
28、/*没找至U x 结点*/p-freq+;p-pre-next=p-next;p-next-pre=p-pre;/*4号 x 结 点从链表上摘 下*/q=p-pre;while(q-freqfreq&p!=(*L)q=q-pre;/*查找插入位置*/if(q!=p-pre)/*4等 x 结点插入*/q-next-pre=p;p-next=q-next;q-next=p;p-pre=q;/*调整位置*/)return p;/*Locate_DuList*/1 3.已知三个带头结点的线性链表A、B 和 C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对A 表进行如
29、下操作：使操作后的链表A 中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限 定 算 法 的 时 间 复 杂 度 为 0(m+n+p),其 中 m、n 和 p 分别为三个表的长度。【算法分析】留下三个链表中公共数据，首先查找两表A 和 B 中公共数据，再 去 C 中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O(m+n+p),在查找每个链表时，指针不能回溯。算法源代码】LinkList Common(LinkList A,LinkList B,LinkList C)pa=A-next;pb=B-next;pc=C-next;/*pa,pb 和 pc
30、是工作指针*/pre=A;while(pa&pb&pc)/*当三表均不空时，查找共同元素*/while(pa&pb)if(pa-datadata)/*处理 pa 结点，后移指针*/u=pa;pa=pa-next;free(u);else if(pa-data pb-data)pb=pb-next;else if(pa&pb)/*处 理 A 和 B 表元素值相等的结点*/while(pc&pc-datadata)pc=pc-next;if(pc)if(pc-datapa-data)/*处理 pa 结点，后移指针*/12数据结构期末习题复习u=pa;pa=pa-next;free(u);elsei
31、f(pre=A)/*结果表中第一个结点*/pre-next=pa;pre=pa;pa=pa-nextelse if(pre-data=pa-data)/*重复结点不链入 A 表*/u=pa;pa=pa-next;free(u);elsepre-next=pa;pre=pa;pa=pa-next;/*4号新2吉 点、链入 A 表*/pb=pb-next;pc=pc-next;/*链表的工作指针后移*/)elseif(pa=NULL)pre-nex仁NULL;/*若 A 表已结束，置 A 表表尾*/else/*处理原A表未到尾而B或C到尾的情况*/pre-next=NULL;/*置 A 表表尾标记
32、*/while(pa!=NULL)/*删除原A表剩余元素。*/u=pa;pa=pa-next;free(u);)1 4.设head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。编 一 函 数,将head链中结点分成一个奇数链和一个偶数链，分别由p,q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。算法源代码】discreat(LinkList p,
33、LinkList q,LinkList head)p=NULL;q=NULL;/*p和q链表初始化为空表*/s=head;while(s!=NULL)r=s-next;/*暂存 s 的后继*/if(s-data%2=0)/*处理偶数*/if(p=NULL)p=s;p-next=NULL;/*第一个偶数结点*/else pre=p;if(pre-datas-data)第2部分习题解析 13 s-next=pre;p=s;/*插入当前最小值结点*/elsewhile(pre-next!=NULL)if(pre-next-datadata)pre=pre-next;/*查才戈孑宙入位置*/s-nex
34、t=pre-next;/*链入结点*/pre-next=s;)else/*处理奇数链if(q=NULL)q=s;q-next=NULL;/*第一奇数结点*/elsepre=q;if(pre-datas-data)s-next=pre;q=s;/*修改头指针*/elsewhile(pre-next!=NULL)/*查找插入位置*/if(pre-next-datadata)pre=pre-next;s-next=pre-next;/*链入结点*/pre-next=s;/*结束奇数链结点*/s=r;/*s指向新的待排序结点*/)第3章 栈 和 队 列3.1 选择题1.一个栈的输入序列为123n,若输
35、出序列的第一个元素是n,输 出 第i(l 4 i(n)个元素是(B)A)不 确 定B)n-i+1 C)i D)n-i【解析】根据栈的性质(LIFO),若输出的第一个元素是n,则表明所有的元素已经入栈，则出栈顺序为n,n-1,3,2,L2.设 栈S和队列Q的初始状态为空，元 素el,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e l则 栈S的容量至少应该是(C)A)6 B)4 C)3 D)2【解析】根据栈的性质(LIFO)得,e 2出栈前，栈 中 存 有e l和e2两个元素，e 4出栈前，栈中存有el、e3和e4三个元素
36、，e4和e3出栈以后，e5和e6入栈，栈中同样存在el、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为工 14 数据结构期末习题复习3.若 一 个 栈 以 向 量 存 储，初始栈顶指针top为n+1,则下面x进栈的正确操作是(C)A)top=top+1;Vtop=x B)Vftop=x;top=top+lC)top=top-1;Vtop=x D)Vtop=x;top=top-l【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1,该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针
37、后存入元素。4.如果我们用数组A1.1OO来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0,表示栈空。请问在top为100时，再进行入栈操作，会 产 生(B)A)正常动作 B)溢出 C)下溢 D)同步【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。5.栈 在(D )中应用。A)递归调用 B)子程序调用 C)表达式求值 D)A,B,C6.表 达 式3*2(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为(D )，其中 为乘 赛。A)3,2,4,1,1;(*(+*-B)3,2,8;(*-0 3,2,4,2,2;(*(-D)3,2
38、,8;(*(-【解析】根据表达式求值的基本思想，在扫描表达式时，依次读入表达式的每个字符，若是操作数则进对象栈，若为运算符则和运算符栈的栈顶运算符比较优先级后做相应的操作。7.用链接方式存储的队列，在进行删除运算时(D )A)仅修改头指针 B)仅修改尾指针 C)头、尾指针都要修改 D)头、尾指针可能都要修改【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。8.循环队列A0.m-1存放其元素值，用fro n t和re a r分别表示队头和队尾，则当前队列中的元素数是(A )A)(rear-front+m)%m B)
39、rear-front+1C)rear-front-1 D)rear-front【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。9.若用一个大小为6的数组来实现循环队列，且当前re a r和fro n t的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rea r和fro n t的值分别为多少？(B)A )1 和 5 B )2 和 4 C )4 和 2 D )5 和 1第2部分习题解析 15【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别
40、为：rear=（rear+l）%m,front=（front+1 ）%m10.栈和队列的共同点是（C）A ）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。11.在一个链队列中，假 定front和rear分别为队头和队尾指针，则插入*s结点的操作为（C）A）front-next=s;front=s;B）s-next=rear;rear=s;C）rear-next=s;rear=s;D）s-next=front;front=s;【解析】队列是运算受限的线性表（FIFO）,插入元素只能插在队尾，所以需修
41、改队尾指针。12.判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（B）A）S-top!=-l S-top!=MAXSIZE-l B）S-top=-l S-top=MAXSIZE-lC）S-top=-l S-top!=MAXSIZE-l D）S-top!=-l S-top=MAXSIZE-l13.循环顺序队列中是否可以插入下一个元素（A）A）与队头指针和队尾指针的值有关B）只与队尾指针的值有关，与队头指针的值无关C）只与数组大小有关，而与队头指针和队尾指针的值无关D）与曾经进行过多少次插入操作有关【解析】在循环队列中判断队满的条件为：（q.rear+l）%m=q.front是否
42、为真，从中可以看出，与队头指针和队尾指针的值有关。14.最不适合用作链队的链表是（A ）A）只带队头指针的非循环双链表B）只带队头指针的循环双链表C）只带队尾指针的非循环双链表D）只带队尾指针的循环单链表（解析】链队是在链表的两端进行操作，而在A中查找链表最后一个结点的时间复杂度为0（n）。15.下列哪中数据结构常用于系统程序的作业调度（B）A）栈 B）队列 C）链表 D）数组【解析】作业调度采用先到先服务的方式，因此最适合的数据结构为队列。3.2填空题1.栈是 的线性表，其运算遵循_ 的原则。答案】（1 ）操 作 受 限（或限定仅在表尾进行插入和删除操作）（2）后进先出2.设 有 一 个 空
43、 栈，栈 顶 指 针 为1000H（十六进制），现 有 输 入 序 列 为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POEPUSH,PUSH之后，输出序列是一23 而栈顶指针值是_100CH_设栈为顺序栈，每个元素占4个字节。【解析】PUSH为入栈操作，POP为出栈操作。根据栈的性质，经 过PUSH,PUSH,POP运算之后，栈中 16数据结构期末习题复习存 在 元 素1,输出数据为2,然后经过PUSH,POP,3人栈，3出栈，然后经过PUSH,PUSH之 后4,5入 栈，此 时 出 栈 序 列 为2,3,栈 中 元 素 为1,4,5；每 个 元 素 占4个字节，所以栈顶指
44、针的值为1000H+3*4=100CH(十六进制数)3.循环队列的引入，目的是为了克服。答案】假溢出时大量移动数据元素。4 .队 列 是 限 制 插 入 只 能 在 表 的 一 端，而 删 除 在 表 的 另 一 端 进 行 的 线 性 表，其 特 点 是。【答案】先进先出5.已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是。【答案 1 s=(LinkList)malloc(sizeof(LNode);s-data=x;s-next=r-next;r-next=s;r=s;【解析】根据队列的性质，新插入的元素永远插在队尾。6.区分循环队列的满与空，只有两种方法，它们是 和【答案】(1
45、)牺 牲 一 个 存 储 单 元(2)设标记7.表达式 23+(12*3-2)/4+34*5/7)+108/9 的 后 缀 表 达 式 是【答 案】23.12.3*2-4/34.5*7/+108.9/+(注：表达式中的点(.)表示将数隔开，如23.12.3是 三 个 数)【解析】表达式的后缀表达式是将表达式中的运算符写在两个操作数之后。转换原则如下：(1)从左到右扫描表达式，若读到的是操作数，则直接把它输出(2)若读到的是运算符：该运算符为左括号“(”，则直接入栈该运算符为右括号“)”，则输出栈中运算符，直到遇到左括号为止该运算符为非括号运算符，则与栈顶元素做优先级比较：若比栈顶元素的优先级高
46、或相等，则直接入栈；若比栈顶元素的优先级低，则输出栈顶元素。(3)当表达式扫描完后栈中还有运算符，则依次输出运算符，直到栈空。8.用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是M=答案】(M+l)%N【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。9.当两个栈共享一存储区时,栈利用一维数组stackL.n表 示,两 栈 顶 指 针 为topl与top2,则当 栈1空时，topl为,栈2空时，top2为,栈满时为。【答案】(1)0 (2)n+1(3)topl+l=top2【解析】为
47、了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的栈顶分别设在这片内存空间的两端，这样,当两个栈的栈顶在栈空间的某一位置相遇时，才产生第 2 部分习题解析上 溢,即 topl+l=top2,10.在作进栈运算时应先判别栈是否；在 作 退 栈 运 算 时 应 先 判 别 栈 是 否；当 栈 中 元 素 为 n 个，作 进 栈 运 算 时 发 生 上 溢，则 说 明 该 栈 的 最 大 容 量 为为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的分别设在内存空间的两端，这样只有当 时才产生溢出。【答案】(1)满(2)空(3)n
48、(4)栈 底(5)两栈顶指针相邻11.在 Q 的链队列中，判断只有一个结点的条件是【答案】Q-front!=NULL&Q-front=Q-rear【解析】只有一个结点时，队列不为空并且队头指针和队尾指针指向同一结点。12.若 用 不 带 头 结 点 的 单 链 表 来 表 示 链 栈 S,则 创 建 一 个 空 栈 所 需 要 执 行 的 操 作 是.【答 案 S=NULL13.无论对于顺序存储还是链式存储的栈和队列来说，进行插入和删除运算的时间复杂度均相同为【答案】0(1)【解析】对于栈用栈顶指针表示栈顶，而栈的插入和删除操作均在栈顶进行。对于队列用队头和队尾指针分别表示允许插入和删除的一端
49、。14.在顺序队列中，当尾指针等于数组的上界，即使队列不满，再作入队操作也会产生溢出，这种现象称为【答案】假溢出【解析】产生该现象的原因是，被删元素空间在该元素被删除后就永远得不到使用。为了克服这种现象，采用循环队列来实现。15.设 元 素 1,2,3,4,5 依 次 入 栈，若 要 得 到 输 出 序 列 3 4 2 5 1,则应进行的操作序列为PUSH(S,1),PUSH(S,2),POP(S),PUSH(S,4),POP(S),POP(S),POP(S)。答案(1)PUSH(S,3)(2)POP(S)(3)PUSH(S,5)3.3判断题1.即使对不含相同元素的同一输入序列进行两组不同的合
50、法的入栈和出栈组合操作，所得的输出序列也一定相同()【答x【解析】栈的性质为后进先出，不同的入栈出栈组合得到的输出序列不一定相同。例如：对于序列1 2 3,进行不同的入栈出栈操作，可能得到的输出序列有：123,213,321等。2.链式队列队满条件是尾指针加一等于头指针()【答案】x【解析】链队列本身没有容量限制，所以在用户内存空间的允许范围内不会出现队满的情况。3.栈和队列都是线性表，只是在插入和删除时受到了一些限制()【答案】q4.循环队列也存在空间溢出问题()【答案】45.循环队列通常用指针来实现队列的头尾相接()【答案】x【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。