2021-2022年电大期末《数据结构(本)》形成性考核册作业1-4原题及答案英语网考资料.pdf

《2021-2022年电大期末《数据结构(本)》形成性考核册作业1-4原题及答案英语网考资料.pdf》由会员分享，可在线阅读，更多相关《2021-2022年电大期末《数据结构(本)》形成性考核册作业1-4原题及答案英语网考资料.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作业1一、单项选择题1.在数据结构中，从逻辑上可以把数据结构分为（C)oA.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构2.下列说法中，不正确的是D.内部结构和外部机构(D)oA.B.C.D.数据元素是数据的基本单位数据项是数据中不可分割的最小可标识单位数据可有若干个数据元素构成数据项可由若干个数据元素构成3.一个存储结点存储一个（B)oA.数据项C.数据结构B.数据元素D.数据类型4.数据结构中，与所使用的计算机无关的是数据的（C)o（本部分作业覆盖教材第1-2 章的内容）C.与算法本身 D.与数据结构9 .设有一个长度为n的顺序表，要在第i 个元素之前（也就是插入元素

2、作为新表的第i 个元素），则移动元素个数为（A ）.A.n-i+1 B.n-i C.n-i-1 D.i1 0.设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（B ）。A.n-i+l B.n-i C.n-i-l D.i1 1 .在一个单链表中，p、q 分别指向表中两个相邻的结点，且q 所指结点是P 所指结点的直接后继，现要删除q 所指结点，可用语句（C ）。A.p=q-n e x t B.p-n e x t=q C.p-n e x t=q-n e x tD.q-n e x t=N U L L1 2 .在一个单链表中p所指结点之后插入一个s 所指的结点时，可执行（D ）oA.存储结构C

3、.逻辑结构B.物理结构D.物理和存储结构Ap-n e x t=s-n e x t=p-n e x t5.下列的叙述中，不属于算法特性的是（D ）oA.有穷性C.可行性6.算法分析的目的是（CA.找出数据结构的合理性输出的关系C.分析算法的效率以求改进B.D.)o文档性7.数据结构是一门研究计算机中科学。A.数值运算C.集合8.算法的时间复杂度与（CA.所使用的计算机 B.)B.p-n e x t=s-n e x t;输入性可读性B.I).BB.研究算法中的输入和分析算法的易懂性和）对象及其关系的非数值运算D.非集合有关。与计算机的操作系统CD.s-n e x t=p-n e x t;p-n e

4、 x t=s;1 3.非空的单向循环链表的尾结点满足（C针为h e a d,指针p 指向尾结点）。A.P-n e x t=N U L Lp=s-n e x t)(设头指B.P=N U L LC.P-n e x t=h e a d D.P=h e a d1 4.链表不具有的特点是（A ）。A.可随机访问任一元素 B.插入删除不需要移动元素C.不必事先估计存储空间 D.所需空间与线性表长度成正比1 5.带头结点的链表为空的判断条件是（B ）（设头指针为h e a d）oA.h e a d =N U L LB.h e a d-n e x t=N U L LC.h e a d-n e x t=h e

5、a dD.h e a d!:N U L L1 6 .在一个单链表中，p、q分别指向表中两个相邻的结点，且 q所指结点是P 所指结点的直接后继，现要删除q所指结点，可用语句（CA.p=q-n e x tB.p-n e x t=qC.p-n e x t=q-n e x tD.q-n e x t=N U L L1 7 .在一个链队中，假设f和 r分别为队头和队尾指针，则删除一个结点的运算为（C ）。A.r=f-n e x t;B.r=r-n e x t;C.f=f-n e x t：D.f=r-n e x t;1 8 .在一个链队中，假设f和 r分别为队头和队尾指针，则插入s 所指结点的运算为（B ）

6、.A.f-n e x t=s;f=s;B.r-n e x t=s;r=s;C.s-n e x t=r;r=s;D.s-n e x t=f;f=s;1 9.一个顺序表第一个元素的存储地址是9 0,每个元素的长度为 2,则第6个元素的地址是（B ）A.9 8 B.1 0 0 C.1 0 2 D.1 0 62 0.有关线性表的正确说法是（D ）.A.每个元素都有一个直接前驱和一个直接后继B.线性表至少要求一个元素C.表中的元素必须按由小到大或由大到下排序I）.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1 .在一 个 长 度 为 n的顺序存储结构的线性表中，向

7、第i（l V n+l）个元素之前插入新元素时，需向后移动_n-i+l _个数据元素。2 .从 长 度 为 n的采用顺序存储结构的线性表中删除第i （l V i V n+1）个元素，需向前移动_ n-i _个元素。3 .数据结构按结点间的关系，可分为4种逻辑结构：集合 一、线性结构_、树形结构_、_图 状 结 构4.数据的逻辑结构在计算机中的表示称为 物理结构一或存储结构_ 有零个或多个输出7 .数据结构中的数据元素存在多对多的关系称为图状结构_ 结构。8 .数据结构中的数据元素存在一对多的关系称为一树形结构_ 结构。9 .数据结构中的数据元素存在一对一的关系称为.线性结构.结构。1 0.要 求

8、 在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为n-l _和 _ 0（n）_ 1 1 .在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-n e xt=p-n e xt 和 p-n e xt=s;的操作。1 2 .设有一个头指针为h e a d的单向循环链表，p指向链表中的结点，若p-n e xt=_ h e a d 则p所指结点为尾结点。1 3 .在一个单向链表中，要删除p所指结点，已 知q指 向P所指结点的前驱结点。则可以用操作_q-n e xt=p-n e xt _。1 4.设有一个头指针为h e a d的单向链表，p指向表中

9、某一个结点，且 有p-n e xt=N U L L,通过操作p-n e xt=h e a d 就可使该单向链表构造成单向循环链表。1 5 .每个结点只包含一个指针域的线性表叫单链表1 6 .线性表具有顺序存储_和_链式存储一两种存储结构。1 7 .数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系_存储结构一无关，是独立于计算机的。1 8 .在双向循环链表的每个结点中包含两个一指针域，其中n e xt指向它的直 接 后 继p r i o r指 向 它 的 _直 接 前 驱 而头结点的p r i o r指向_ 尾结点_，尾结点的n e xt指向_ 头结点_。1 9 .单向循环链表是单向链表的一

10、种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 头结点的指针_；当单向链表不带头结点时I则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针。2 0.线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 链式存储结构，又称为链表三、问答题1.简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的

11、存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑5 .除了第1 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性 结 构 每个结点可有任意多个前驱和后继结点数的结构为 非 线 性 结 构。6 .算法的5个重要特性是_ 有穷性_、_ 确定性_、可形性_、有零个或多个输入_、结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大.2 .解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即

12、逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用：（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。3 .什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作

13、是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。4 .头指针、头结点、第一个结点（或称首元结点）的区别是什么？头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5.解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插

14、入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空题1 .下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。N O D E *cr e a t e l（n）/*对线性表（1,2.,n）,建立带头结点的单向链表*/（N O D E *h e a d,*p,*q;i n t i;p=(N O D E *)m a l l o c(s i z e o f(N O D E);h e a d=p;q=p;p-n e x t=N U L L;f

15、o r(i=l;i d a t a=i;(2)p-next=NULL;(3)q-n e x t=p;(4)q =p;)r e t u r n(h e a d);)2.下列是用头插法建立带头结点的且有n 个结点的单向链表的算法，请在空格内填上适当的语句。N O D E *cr e a t e 2(n)/*对线性表(n,n-1,.1),建立带头结点的线性链表*/(N O D E *h e a d,*p,*q;i n t i;p=(N O D E *)m a 1 1 o c(s i z e o f(N O D E);(1)h e a d 二 p;p-n e x t=N U L L;(2)q=p;f

16、o r(i=l;i d a t a=i;i f(i=l)(3)p-n e x t=N U L L;e l s e(4)p-next=q-next;(5)q-n e x t=p;)r e t u r n(h e a d);)3.下列是在具有头结点单向列表中删除第i 个结点，请在空格内填上适当的语句。i n t d e l e t e(N O D E *h e a d,i n t i)(N O D E *p,*q;i n t j;q=h e a d;j=0;w h i l e(q!=N U L L)&(j n e x t;j+；)i f(q=N U L L)r e t u r n (0);(1)p

17、-q-next;(2)q-next=p-next;f r e e (p);r e t u r n (1);)五、完成：实验1一一线性表根据实验要求(见教材P 2(H-2 0 2)认真完成本实验，并提交实验报告。数据结构(本)课程作业2(本部分作业覆盖教材第3-5章的内容)一、单项选择题1 .若让元素1,2,3 依次进栈，则出栈顺序不可能为(C )oA.3,2,1 B.2,1,3C.3,1,2 1).1,3,22 .一个队列的入队序列是1,2,3,4。则队列的输出序列是(B )。A.4,3,2,1 B.1,2,3,4C.1,4,3,2 D.3,2,4,13 .向顺序栈中压入新元素时，应 当(A

18、)n e xt=p;B.p-n e xt=t op-n e xt;t op-n e xt=p;C.p-n e xt=t op;t op=p;D.p-n e xt=t op-n e xt;t op=t op-n e xt;5 .在一个栈顶指针为t op的链栈中删除一个结点时，用 x 保存被删结点的值，则执行(B ).A.x=t op;t op=t op-n e xt;B.x=t op-d a t a;C.t op=t op_n e xt;x=t op_d a t a;D.x=t op-d a t a;t op=t op-n e xt;6 .一般情况下，将递归算法转换成等价的非递归算法应该设置(A

19、 )0A.栈 B.队列C.堆栈或队列 D.数组7.表达式a*(b+c)-d 的后缀表达式是(B )0A .a b e d*+-B .a b c+*d-C .a b c*+d-D.-+*a b c d8.判断一个顺序队列s q(最多元素为映)为空的条件是(C )。A .s q-r e a r-s q-f r on t=m oB.s q-r e a r-s q-f r on t-l=m oC.s q-f r on t=s q-r e a rD.s q-f r on t=s q-r e a r+l9.判断一个循环队列Q （最多元素为mJ为空的条件是（A ）oA.Q-f r on t=Q-r e a

20、rB.Q-f r on t!=Q-r e a rC .Q-f r on t=（Q-r e a r+l）%m o D.Q-f r on t!=（Q-r e a r+l）%m o1 0.判断栈S 满（元素个数最多n个）的条件是（CA.s-t op=0 B.s-t op!=0C.s-t op=n-l D.s-t op!=n-l1 1.一个队列的入队顺序是a,b,c,d,则离队的顺序是（B ）oA .a,d,c b B .a,b,c,d C .d,c,b,aD.c,b,d,a1 2.如果以链表作为栈的存储结构，则退栈操作时（C ）oA.必须判断栈是否满 B.判断栈元素类型C.必须判断栈是否空 D.对栈

21、不作任何判断1 3.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（B ）结构。A.堆栈 B,队列 C.数组 D.先性表1 4.一个递归算法必须包括（BA.递归部分 B.终止条件和递归部分C.迭代部分 D.终止条件和迭代部分1 5.从一个栈顶指针为t op的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（A ）oA.x=t op-d a t a;t op=t op-n e xt;B.x=t op-d a t a;C.t op=t op-n e xt;x=t op_d a t

22、 a;D.t op=t op-n e xt;x=d a t a;1 6 .在一个链队中，假 设f和 r分别为队头和队尾指针，则删除一个结点的运算为（C ）oA .r=f-n e xt;B .r=r-n e xt;C .f=f-n e xt;D.f=r-n e xt;1 7.在一个链队中，假设f 和 r 分别为队头和队尾指针，则插入s所指结点的运算为（B ）oA.f-n e xt=s;f=s;C.s-n e xt=r;r=s;1 8.以下陈述中正确的是（A ）。A.串是一种特殊的线性表零C.串中元素只能是字母B.r-n e xt=s;r=s;D.s-n e xt=f;f=s;B.串的长度必须大于

23、D.空串就是空白串1 9.设有两个串P 和 q,其中q 是 P 的子串，q 在 P 中首次出现的位置的算法称为（C ）。A.求子串C.匹配2 0.串 是（D ）。A.不少于一个字母的序列C.不少于一个字符的序列B.连接D.求串长B.任意个字母的序列D.有限个字符的序列2 1 .串的长度是指（B ）。A.串中所含不同字母的个数 B.串中所含字符的个数C.串中所含不同字符的个数 1）.串中所含非空格字符的个数2 2 .若串S=E n g l i s h”,其子串的个数是（D ）.A.9 B.1 6 C.3 6 D.2 82 3 .串与普通的线性表相比较，它的特殊性体现在（C ）。A.顺序的存储结构

24、C.数据元素是一个字符2 4 .空串与空格串（B ）。B.链接的存储结构I）.数据元素可以任意A.相同法确定B.不相同C.可能相同 D.无2 5 .两个字符串相等的条件是（D）。A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同1）.两串的长度相等，并且对应位置上的字符相同2 6 .在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（A ）存储比较合适（A.链式 B.顺序 C.堆结构 D.无法确定2 7 .一维数组A采用顺序存储结构，每个元素占用6个字节，第 6个元素的存储地址为1 00,则该数组的首地址是（C ）。A.6 4B.2 8C.7 0D.90

25、2 8 .稀疏矩阵米用压缩存储的目的主要是（D ）。A.表达变得简单变得简单C.去掉矩阵中的多余元素空间的开销2 9.一个非空广义表的表头（C ）A.不可能是原子C.只能是原子3 0.常对数组进行的两种基本操作是A.建立与删除C.查找和修改B.对矩阵元素的存取D.减少不必要的存储B.只能是子表D.可以是子表或原子（C ）。B.索引与、和修改I）.查找与索引3 1 .设二维数组A 5 6 按行优先顺序存储在内存中，已知A 0 0起始地址为1 000,每个数组元素占用5个存储单元,则元素A 4 4 的地址为（A ）。A.1 1 4 0 B.1 1 4 5 C.1 1 2 0 D.1 1 2 53

26、2 .设有一个2 0阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始）,则矩阵中元素a.在一维数组B中的下标是（D ）.A.4 1 B.3 2 C.1 8D.3 8二、填空题1 .栈是限定在表的一端进行插入和删除操作的线性表，又称为_ 后进先出。2.循环队列队头指针在队尾指针 下一个 位置，队列是“满”状态3 .在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针增 1，当删除一个元素队列时，头指针 增1。4 .循环队列的引入，目的是为了克服假上溢。5.向顺序栈插入新元素分为三步：第一步进行_栈是否满判断,判断条件是 s-to p=M A

27、X SI Z E-l_；第二步是修改 栈顶指针;第三步是把新元素赋给 栈顶对应的数组元素。同样从顺序栈删除元素分为三步：第一步进行栈是否空 判断，判断条件是s-t op=-l。第二步是把栈顶元素；第三步 修改栈顶指针 06 .假设以S 和 X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e 一系列栈操作SSX SX SSX X X 之后，得到的输出序列为b c e d a。7 .一个递归算法必须包括_终止条件 和 递归部分。8 .判断一个循环队列L U(最多元素为mn)为空的条件是L U-f r o n t=L U-r e a r。9 .在将中缀表达式转换成后缀表达式和计算后缀表达式的算

28、法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的运算符,而对于后者，进入栈的元素为操作数,中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是a b+c/f d e/。1 0 .向一个栈顶指针为h 的链栈中插入一个s 所指结点时，可执行 s-ne x t=h_ _ _ _ _和 h=s;操作。(结点的指针域为ne x t)1 1 .从一个栈顶指针为h 的链栈中删除一个结点时，用 x保存被删结点的值，可执行x=h-d a ta;和_ h=h-n ext。(结点的指针域为ne x t)1 2 .在一个链队中，设 f和 r 分别为队头和队尾指针，则插入 s 所指结点的操作为 r-ne

29、 x t=s 和 r=s;(结点的指针域为ne x t)1 3 .在一个链队中，设 f和 r 分别为队头和队尾指针，则删除一个结点的操作为 f=f-ne x t (结点的指针域为ne x t)1 4 .串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是 字符。1 5 .串的两种最基本的存储方式是 顺序存储方式和 链式存储方式。1 6 .空串的长度是 0 ；空格串的长度是_ _ _ _ _ 空格字符的个数 o1 7 .需要压缩存储的矩阵可分为 特殊 矩阵和稀疏 矩阵两种。1 8 .设广义表L=(),(),则表头是_(),表尾是(),L 的长度是 2 -1 9 .广 义 表 A(a,b,c

30、),(d,e,f)的 表 尾 为(d,e,f)o2 0 .两个串相等的充分必要条件是 串长度相等且对应位置的字符相等.2 1 .设有n 阶对称矩阵A,用数组s 进行压缩存储，当 i j 时，A 的数组元素a 相应于数组s 的数组元素的下标为_i(i-D/2+j。(数组元素的下标从1 开始)2 2 _.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的 行下标_ 一、一列下标 和 非零元素值 三项信息。三、问答题1 .简述栈和一般线性表的区别。答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。2 .简述队列和

31、般线性表的区别。队列是一种先进先出的线性表，队列的插入只能在队尾进行,队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。3 .链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。4 .利用一个栈，贝 心(1)如果输入序列由A,B,C组成，试给出全部可能的输出序列和不可能的输出序列。(2)如果输入序列由A,B,C,I)组成，试给出全部可能的输出序列和不可能的输出序列。答：(1)栈的操作特点是后进先出，因此输出序列有：A 入，A 出，B 入，B出，C入C出，输出序列为AB C。A 入，A 出

32、，B 入，C 入，C出，B出，输出序列为AC B。A 入，B入，B出，A 出，C入，C出，输出序列为B AC。A 入，B 入，B出，C 入，C出，A 出，输出序列为B C A。A 入，B入，C入，C出，B出，A 出，输出序列为C B A。由 A,B,C组成的数据项，除上述五个不同的组合外，还有一个C,A,B 组合。但不可能先把C出栈，再把A 出栈，(A不在栈顶位置)，最后把B 出栈，所以序列C AB不可能由输入序列A,B,C通过栈得到。(2)按照上述方法，可能的输出序列有：ABC D,ABD C,AC BD,AC D B,AD C B,BAC D,BAD C,BC AD,BC D A,BD C

33、 A,C BAD,C BD A,C D BA,D C BA.不可能的输出序列有：D ABC,AD BC,D AC B,D BAC,BD AC,D BC A,D C AB,C D AB,C AD B,C ABD5.用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为1234,为了得到134 2出栈顺序，相应的S 和 X 操作串是什么？答：应是SX SSX SX X。各操作结果如下：S 1入栈X 1 出栈输出序列；1S 2 入栈S 3 入栈X 3 出栈输出序列：13S 4入栈X 4出栈输出序列：134X 2出栈输出序列：134 26.有5个元素，其入栈次序为：A、B、C、D、E,在各种可能的出

34、栈次序中，以元素C、D最先的次序有哪几个？答：从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况:(1)B出栈，A出栈，E入栈，E出栈，输出序列为：C D BAE o(2)B出栈，E入栈，E出栈，A出栈，输出序列为C D BE A。(3)E入栈，E出栈，B出栈，A出栈，输出序列为C D E BA所以可能的次序有：C D BAE,C D BE A,C D E BA7 .写出以下运算式的后缀算术运算式 3x2+x-l/x+5(A+B)*C-D/(E+F)+G答：对应的后缀算术运算式 3x2 x+l x/-5+AB+C*D E F+/-G+8

35、.简述广义表和线性表的区别和联系。答:广义表是线性表的的推广,它也是n(n 0)个元素由，&.烝的有限序列，其 中4或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当a：都是原子时，广义表退化成线性表。四、程序填空题1.在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。in t write(L in k Q ue ue *q)Q ue ue N o d e *p;if (q-f ro n t=q-re a r)/*队空*/p rin tf(un d e rf l o w);e xit(0);whi1e (q-f

36、ro n t-n e xt!=N U L L)p=q-f ro n t-n e xt;(1)q-f ro n t-n e xt=p-n e xt;p rin tf(w%4 dv,p-d a ta);(2)f re e (p);_ _ _ _ _ _ _ _ _ _ _)(3)q-re a r=q-f ro n t/*队空时，头尾指针指向头结点*/)五、综合题L设栈S和队列Q的初始状态为空,元素e l,e 2,e 3,e 4,队和e 6依次通过S,一个元素出栈后即进队列Q,若6个元素出队的序列是e 2,e 4,e 3,e 6,e 5,e l,则栈S的容量至少应该是多少？答：出队序列是e 2,e

37、4,e 3,e 6,e 5,e l的过程：e l入栈(栈底到栈顶元素是e l)e 2入栈(栈底到栈顶元素是e l,e 2)e 2出栈(栈底到栈顶元素是e l)(4)e 3入 栈(栈底到栈顶元素是e l,e 3)(5)e 4入栈(栈底到栈顶元素是e l,e 3,e 4)(6)e 4出栈(栈底到栈顶元素是e l,e 3)e 3出栈(栈底到栈顶元素是e l)(8)e 5入栈(栈底到栈顶元素是e l,e 5)e 6入栈(栈底到栈顶元素是e l,e 5,e 6)0 0)e 6出栈(栈底到栈顶元素是e l,e 5)(I D e 5出栈(栈底到栈顶元素是e l)e l出 栈(栈底到栈顶元素是空)栈中最多时有

38、3个元素，所以栈S的容量至少是3。2.假设用循环单链表实现循环队列，该队列只使用一个尾指针re a r,其相应的存储结构和基本算法如下；(1)初始化队列in itque ue(Q):建立一个新的空队列Q。(2)入队列e n que ue(Q,x):将元素x插入到队列Q中。(3)出队列d e l que ue (Q):从队列Q中退出一个元素。(4)取队首元素ge the a d(Q):返回当前队首元素。(5)判断队列是否为空:emptyqueue(Q)(6)显示队列中元素:dispqueue(Q)o算法设计如下：/*只有一个指针rear的链式队的基本操作*/include typedef cha

39、r elemtype;struct node/*定义链队列结点*/(elemtype data;struct node*next;)；typedef struct queue/*定义链队列数据类型*/(struct node*rear;L inkQueue;void initqueue(L inkQueue*Q)/*初始化队列*/(Q=(struct queue*)malloc(sizeof(struct queue);Q-rear=N U L L;void enqueue(L inkQueue*Q,elemtype x)/*入队算法*/(struct node*s,*p;s=(struct node*)malloc(sizeof(struct node);s-data=x;if(Q-rear=N U L L)*/IQ-rear=s;s-next=s;)else时*/(p=Q-rear-next;Q-rear-next=s;Q-rear=s;s-next=p;/*原为空队时/*原队不为空/*p指向第一个结点*/*将s链接到队尾*/*Q-rear指向队尾*/