1、1数据结构（本）课程作业作业 1（本部分作业覆盖教材第 1-2 章的内容）一、单项选择题1在数据结构中，从逻辑上可以把数据结构分为（C ） 。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部机构2下列说法中，不正确的是（ D ） 。A数据元素是数据的基本单位 B数据项是数据中不可分割的最小可标识单位 C数据可有若干个数据元素构成 D数据项可由若干个数据元素构成3一个存储结点存储一个（ B ） 。A数据项 B数据元素 C数据结构 D数据类型4数据结构中，与所使用的计算机无关的是数据的（ C ） 。A存储结构 B物理结构C逻辑结构 D物理和存储结构5下列的叙述
2、中，不属于算法特性的是（ D ） 。A有穷性 B输入性 C可行性 D可读性6算法分析的目的是（ C ） 。A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性7数据结构是一门研究计算机中（ B ）对象及其关系的科学。A数值运算 B非数值运算C集合 D非集合 8算法的时间复杂度与（ C ）有关。A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构9设有一个长度为 n 的顺序表，要在第 i 个元素之前（也就是插入元素作为新表的第 i 个元素） ，则移动元素个数为（ A ） 。An-i+1 Bn-i Cn-i-1 Di10设有一个
3、长度为 n 的顺序表，要删除第 i 个元素移动元素的个数为（ B ） 。An-i+1 Bn-i Cn-i-1 Di11在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点的直接后继，现要删除 q 所指结点，可用语句（ C ） 。Ap=q-next Bp-next=q Cp-next=q next Dq-next=NULL12在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执行（ D ） 。Ap-next= s; snext= pnext Bp-next=s next; Cp=s-next Ds-next=p-next; p-next=s;13非空的
4、单向循环链表的尾结点满足（C ） （设头指针为 head，指针 p 指向尾结点） 。A.P-next= =NULL BP= =NULLCP-next= =head DP= = head 14链表不具有的特点是（ A ） 。A可随机访问任一元素 B插入删除不需要移动元素C不必事先估计存储空间 D所需空间与线性表长度成正比15带头结点的链表为空的判断条件是（ B ） （设头指针为 head） 。Ahead = =NULLBhead-next= =NULL Chead-next= =head Dhead!=NULL16在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结
5、点的直接后继，现要删除 q 所指结点，可用语句（ C ） 。Ap=q-nextBp-next=q Cp-next=q-nextDq-next=NULL17在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（C ） 。Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（ B ） 。Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;19.一个顺序表第一个元素的存储地址是 90，每个元
6、素的长度为 2，则第 6 个元素的地址是（B ） 。A98 B100 C102 D10620有关线性表的正确说法是（ D ） 。A每个元素都有一个直接前驱和一个直接后继 B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序 D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1在一个长度为 n 的顺序存储结构的线性表中，向第 i(1in+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。2从长度为 n 的采用顺序存储结构的线性表中删除第 i(1in+1)个元素 ，需向前移动 n-i 个元素。3数据结构按结点间的关系，可分为 4 种逻辑
7、结构： 集合 、线性结构 、 树形结构 、 图状结构 。4数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 。5除了第 1 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的2数据结构为 线性结构 ，每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 。6算法的 5 个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 、有零个或多个输出 。7数据结构中的数据元素存在多对多的关系称为_图状结构_结构。8数据结构中的数据元素存在一对多的关系称为_树形结构_结构。9数据结构中的数据元素存在一对一的关系称为_线性结构_结构。10要求在 n 个数据元素中找其中值
8、最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ n-1_和 _ O(n)_ 。11在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行_ s-next=p-next _和 p-next=s;的操作。12设有一个头指针为 head 的单向循环链表， p 指向链表中的结点，若p-next= =_ head _，则 p 所指结点为尾结点。13在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可以用操作_ q-next=p-next _。14设有一个头指针为 head 的单向链表， p 指向表中某一个结点，且有 p-next=
9、=NULL,通过操作_ p-next=head _,就可使该单向链表构造成单向循环链表。15每个结点只包含一个指针域的线性表叫 单链表 。16线性表具有 顺序存储 和 链式存储 两种存储结构。17数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 存储结构 无关，是独立于计算机的。18在双向循环链表的每个结点中包含 两个 指针域，其中 next 指向它的 直接后继 ， prior 指向它的 直接前驱 ，而头结点的 prior 指向 尾结点 ，尾结点的 next 指向 头结点 。19单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 头结点的指针
10、；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 。20线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 链式 存储结构，又称为 链表 。 三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通
11、过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的， ，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存
12、放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。3什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。4头指针、头结点、第一个结点（或称首元结点）的区别是什么？头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5解释带头结点的单链表
13、和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空题1下列是用尾插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内填上适当的语句。NODE *create1(n)/* 对线性表(1,2,.,n), 建
14、立带头结点的单向链表 */ NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);head=p; q=p; p-next=NULL;for(i=1;idata=i ;（2）p-next=NULL ;（3）q-next=p ;（4） q=p ; return(head);2下列是用头插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格3内填上适当的语句。NODE *create2(n)/*对线性表(n,n-1,.,1), 建立带头结点的线性链表 */ NODE *head,*p,*q;int i;p=(NODE *)malloc(siz
15、eof(NODE);（1） head=p ;p-next=NULL;（2） q=p ;for(i=1;idata=i;if(i=1) （3） p-next=NULL ; else（4） p-next=q-next ;（5） q-next=p ;return(head);3下列是在具有头结点单向列表中删除第 i 个结点，请在空格内填上适当的语句。int delete(NODE *head,int i)NODE *p,*q;int j;q=head;j=0;while(q!=NULL)j+;if(q=NULL)return(0);（1） p=q-next ; （2） q-next=p-next ;
16、free(p);return(1);五、完成：实验 1线性表根据实验要求（见教材 P201-202）认真完成本实验，并提交实验报告。数据结构（本）课程作业 2（本部分作业覆盖教材第 3-5 章的内容）一、单项选择题1若让元素 1，2，3 依次进栈，则出栈顺序不可能为（ C ） 。A3，2，1 B2，1，3 C3 ，1，2 D1，3，22一个队列的入队序列是 1，2，3，4。则队列的输出序列是（ B ） 。A4，3，2，1 B1，2，3，4 C1 ，4，3，2 D3，2，4，13向顺序栈中压入新元素时，应当（ A ） 。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C先后次序无关紧
17、要 D同时进行4在一个栈顶指针为 top 的链栈中，将一个 p 指针所指的结点入栈，应执行（ C ） 。Atop-next=p; Bp-next=top-next; top-next=p;Cp-next=top; top=p; Dp-next=top-next; top=top-next;5在一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行（ B ） 。Ax=top;top=top-next; Bx=top-data;Ctop=top-next; x=top-data; Dx=top-data; top=top-next;6一般情况下，将递归算法转换成等价的非递
18、归算法应该设置（ A ） 。A栈 B队列C堆栈或队列 D数组7表达式 a*(b+c)-d 的后缀表达式是（ B ） 。Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd8判断一个顺序队列 sq（最多元素为 m0）为空的条件是（ C ） 。Asq-rear-sq-front= m 0 Bsq-rear-sq-front-1= = m0 Csq-front=sq-rear Dsq-front=sq-rear+19判断一个循环队列 Q（最多元素为 m0）为空的条件是（ A ） 。AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1
19、)% m0 DQ-front!= (Q-rear+1)%m 0 10判断栈 S 满（元素个数最多 n 个）的条件是（ C ） 。As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 11一个队列的入队顺序是 a,b,c,d，则离队的顺序是（ B ） 。Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a12如果以链表作为栈的存储结构，则退栈操作时（ C ） 。A必须判断栈是否满 B判断栈元素类型 C必须判断栈是否空 D对栈不作任何判断13在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打
20、印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ B ）结构。A堆栈 B队列 C数组 D先性表14一个递归算法必须包括（ B ） 。4A递归部分 B终止条件和递归部分 C迭代部分 D终止条件和迭代部分15从一个栈顶指针为 top 的链栈中删除一个结点时，用变量 x 保存被删结点的值，则执行（ A ） 。Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;16在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（C ） 。Ar=f-next; B
21、r=r-next; Cf=f-next; Df=r-next;17在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（B ） 。Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;18.以下陈述中正确的是（ A ）。A串是一种特殊的线性表 B串的长度必须大于零C串中元素只能是字母 D空串就是空白串19设有两个串 p 和 q，其中 q 是 p 的子串，q 在 p 中首次出现的位置的算法称为（ C ） 。A求子串 B连接 C匹配 D求串长 20串是（ D ）。A不少于一个字母的序列 B任意个字母的序
22、列C不少于一个字符的序列 D有限个字符的序列 21串的长度是指（ B ） 。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数22. 若串 S=“English”，其子串的个数是（ D ） 。A9 B16 C 36 D2823串与普通的线性表相比较，它的特殊性体现在（ C ） 。A顺序的存储结构 B链接的存储结构 C数据元素是一个字符 D数据元素可以任意24空串与空格串（ B ） 。A相同 B不相同 C可能相同 D无法确定25两个字符串相等的条件是（ D） 。A两串的长度相等 B两串包含的字符相同C两串的长度相等，并且两串包含的字符相同D两串的长
23、度相等，并且对应位置上的字符相同26在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（A ）存储比较合适（ ） 。A链式 B 顺序 C堆结构 D无法确定 27.一维数组 A 采用顺序存储结构，每个元素占用 6 个字节，第 6 个元素的存储地址为100，则该数组的首地址是（ C ）。A64 B28C70 D9028稀疏矩阵采用压缩存储的目的主要是（D ） 。A表达变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元素 D减少不必要的存储空间的开销29一个非空广义表的表头（ C ）。A不可能是原子 B只能是子表C只能是原子 D可以是子表或原子 30常对数组进行的两种基本操作是（ C
24、 ） 。A建立与删除 B索引与、和修改C查找和修改 D查找与索引31. 设二维数组 A56按行优先顺序存储在内存中，已知 A00 起始地址为 1000，每个数组元素占用 5 个存储单元，则元素 A44的地址为（ A ） 。A1140 B1145 C 1120 D112532设有一个 20 阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开始） ，则矩阵中元素 a9,2在一维数组 B 中的下标是（ D ） 。A41 B32 C18 D38二、填空题1栈是限定在表的一端进行插入和删除操作的线性表，又称为 后进先出 。2循环队列队头指针在队尾指
25、针 下一个 位置，队列是“满”状态3在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 增 1 ，当删除一个元素队列时，头指针 增 1 。4循环队列的引入，目的是为了克服 假上溢 。5向顺序栈插入新元素分为三步：第一步进行 栈是否满 判断，判断条件是 s-top=MAXSIZE-1 ；第二步是修改 栈顶指针 ；第三步是把新元素赋给 栈顶对应的数组元素 。同样从顺序栈删除元素分为三步：第一步进行 栈是否空 判断，判断条件是 s-top=-1 。第二步是把 栈顶元素 ；第三步 修改栈顶指针 。6假设以 S 和 X 分别表示入栈和出栈操作，则对输入序列 a,b,c,d,e 一系列栈操作 SSX
26、SXSSXXX 之后，得到的输出序列为 bceda 。7一个递归算法必须包括 终止条件 和 递归部分 。8判断一个循环队列 LU（最多元素为 m0）为空的条件是 LU-front=LU-rear 。9在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 运算符 ，而对于后者，进入栈的元素为 操作数，中缀表达式(a+b)/c-(f-d/c) 所对应的后缀表达式是 ab+c/fde/- 。 10向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行_ s-next=h _和 h=s;操作。( 结点的指针域为 next)11从一个栈顶指针
27、为 h 的链栈中删除一个结点时，用 x 保存被删结点的值，可执行 x=h-data;和_ h=h-next _。(结点的指针域为 next)12在一个链队中，设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的操作为_ r-next=s _和 r=s; (结点的指针域为 next)13在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为_ f=f-next _。 (结点的指针域为 next)14串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是 字符 5。15串的两种最基本的存储方式是 顺序存储方式 和 链式存储方式 。16空串的长度是 0 ；空格串的长度是
28、 空格字符的个数 。17需要压缩存储的矩阵可分为 特殊 矩阵和 稀疏 矩阵两种。18设广义表 L=（） ， （） ） ，则表头是 （） ，表尾是 （） ） ，L 的长度是 2 。19广义表 A（a,b,c）,(d,e,f) ）的表尾为 （d,e,f） ） 。20两个串相等的充分必要条件是_串长度相等且对应位置的字符相等 _。21设有 n 阶对称矩阵 A，用数组 s 进行压缩存储，当 ij 时，A 的数组元素 aij 相应于数组 s 的数组元素的下标为_ i(i-1)/2+j _。 （数组元素的下标从 1 开始）22对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_行下标_、_
29、列下标_和_非零元素值_三项信息。三、问答题1简述栈和一般线性表的区别。答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。2简述队列和一般线性表的区别。队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。3链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。4利用一个栈，则：（1）如果输入序列由 A，B，C 组成，试给出全部可能的输出序列和不可能的输出序列。（2）如
30、果输入序列由 A，B，C，D 组成，试给出全部可能的输出序列和不可能的输出序列。答：（1）栈的操作特点是后进先出，因此输出序列有：A 入，A 出，B 入，B 出，C 入 C 出，输出序列为 ABC。A 入，A 出，B 入，C 入，C 出，B 出，输出序列为 ACB。A 入，B 入，B 出，A 出，C 入，C 出，输出序列为 BAC。A 入，B 入，B 出，C 入，C 出，A 出，输出序列为 BCA。A 入，B 入，C 入，C 出，B 出，A 出，输出序列为 CBA。由 A，B，C 组成的数据项，除上述五个不同的组合外，还有一个 C，A，B 组合。但不可能先把 C 出栈，再把 A 出栈， （A
31、不在栈顶位置） ，最后把 B 出栈，所以序列CAB 不可能由输入序列 A，B，C 通过栈得到。（2）按照上述方法，可能的输出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC ，BCAD，BCDA，BDCA，CBAD ，CBDA ， CDBA，DCBA。不可能的输出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB ，CDAB，CADB，CABD5用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1234，为了得到 1342 出栈顺序，相应的 S 和 X 操作串是什么？答：应是 SXSSXSXX。各操作结果如下：S 1 入栈X 1 出
32、栈 输出序列：1S 2 入栈S 3 入栈X 3 出栈 输出序列：13S 4 入栈 X 4 出栈 输出序列：134X 2 出栈 输出序列：1342 6有 5 个元素，其入栈次序为：A、B、C、D、E ，在各种可能的出栈次序中，以元素C、D 最先的次序有哪几个？答：从题中可知，要使 C 第一个且 D 第二个出栈，应是 A 入栈，B 入栈，C 入栈，C 出栈， D 入栈。之后可以有以下几种情况：（1）B 出栈，A 出栈，E 入栈，E 出栈，输出序列为：CDBAE 。（2）B 出栈，E 入栈，E 出栈，A 出栈，输出序列为 CDBEA。（3）E 入栈，E 出栈，B 出栈，A 出栈，输出序列为 CDEB
33、A所以可能的次序有：CDBAE，CDBEA，CDEBA7写出以下运算式的后缀算术运算式 3x2+x-1/x+5 (A+B)*C-D/(E+F)+G答；对应的后缀算术运算式 3x2*x+1x/-5+ AB+C*DEF+/-G+8 简述广义表和线性表的区别和联系。答：广义表是线性表的的推广，它也是 n(n0)个元素 a1 ,a2ai an 的有限序列，其中 ai 或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当 ai 都是原子时，广义表退化成线性表。四、程序填空题1在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。
34、 int write(LinkQueue *q)QueueNode *p;if (q-front=q-rear) /*队空*/printf(“underflow”);exit(0);while (q-front-next != NULL)p=q-front-next;(1) q-front-next=p-next;printf(“%4d”,p-data);(2) free(p); 6（3） q-rear=q-front ; /*队空时，头尾指针指向头结点*/五、综合题1设栈 S 和队列 Q 的初始状态为空，元素 e1,e2,e3,e4,e5 和 e6 依次通过 S，一个元素出栈后即进队列 Q，
35、若 6 个元素出队的序列是 e2,e4,e3,e6,e5,e1，则栈 S 的容量至少应该是多少？答：出队序列是 e2,e4,e3,e6,e5,e1 的过程： e1 入栈（栈底到栈顶元素是 e1） e2 入栈（栈底到栈顶元素是 e1,e2） e2 出栈（栈底到栈顶元素是 e1） e3 入栈（栈底到栈顶元素是 e1,e3） e4 入栈（栈底到栈顶元素是 e1,e3,e4） e4 出栈（栈底到栈顶元素是 e1,e3） e3 出栈（栈底到栈顶元素是 e1） e5 入栈（栈底到栈顶元素是 e1,e5） e6 入栈（栈底到栈顶元素是 e1,e5,e6） e6 出栈（栈底到栈顶元素是 e1,e5） e5 出
36、栈（栈底到栈顶元素是 e1） e1 出栈（栈底到栈顶元素是空）栈中最多时有 3 个元素，所以栈 S 的容量至少是 3。2假设用循环单链表实现循环队列，该队列只使用一个尾指针 rear，其相应的存储结构和基本算法如下；（1）初始化队列 initqueue(Q):建立一个新的空队列 Q。（2）入队列 enqueue(Q,x):将元素 x 插入到队列 Q 中。（3）出队列 delqueue(Q):从队列 Q 中退出一个元素。（4）取队首元素 gethead(Q):返回当前队首元素。（5）判断队列是否为空：emptyqueue(Q)。（6）显示队列中元素：dispqueue(Q)。算法设计如下：/*只
37、有一个指针 rear 的链式队的基本操作*/#include typedef char elemtype;struct node /*定义链队列结点*/elemtype data;struct node *next;typedef struct queue /*定义链队列数据类型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化队列*/Q=(struct queue *)malloc(sizeof(struct queue);Q-rear=NULL;void enqueue(LinkQueue *Q,elemtype
38、 x) /*入队算法*/struct node *s,*p;s=(struct node *)malloc(sizeof(struct node);s-data=x;if (Q-rear=NULL) /*原为空队时*/Q-rear=s;s-next=s;else /*原队不为空时*/p=Q-rear-next; /*p 指向第一个结点*/Q-rear-next=s; /*将 s 链接到队尾*/Q-rear=s; /*Q-rear 指向队尾*/s-next=p; void delqueue(LinkQueue *Q) /*出队算法*/struct node *t;if (Q-rear=NULL)
39、printf(“队列为空!n“);return(0);else if (Q-rear-next=Q-rear) /*只有一个结点时*/t=Q-rear;Q-rear=NULL;else /*有多个结点时*/t=Q-rear-next; /*t 指向第一个结点*/Q-rear-next=t-next; /*引成循环链*/free(t);elemtype gethead(LinkQueue *Q) /*取队首元素算法*/if (Q-rear=NULL)printf(“队列为空!n“);elsereturn(Q-rear-next-data);int emptyqueue(LinkQueue *Q)
40、 /*判断队列是否为空算法*/if (Q-rear=NULL) return(1); /*为空,则返回 true*/else return(0); /*不为空,则返回 flase*/void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/struct node *p=Q-rear-next;printf(“队列元素:“);while (p!=Q-rear)printf(“%c “,p-data);p=p-next;printf(“%cn“,p-data);六、完成：实验 2栈、队列、递归程序设计根据实验要求（见教材 P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业作业 3（本部分作业覆盖教材第 6-7 章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为 15，单分支结点数为 30，则叶子结点数为（ B ）。A15 B16 C17 D472二叉树第 k 层上最多有（ B ）个结点。7A2k B2 k-1C2 k-1 D2k -1 3二叉树的深度为 k,则二叉树最多有（ D ）个结点。A2k B2k-1C2 k-1 D2 k-14. 设某一二叉树先序遍历为 abdec，中序遍历为 dbeac，则该二叉树后序遍历的顺序是（ C ） 。Aabdec Bdebac Cdebca Dabedc5将含有 150 个结点的完全二
