首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5．解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。
四、程序填空题程序填空题1．（1）pdatai（2）p
extNULL（3）q
extp（4）qp2．（1）headp（2）qp
（3）p
extNULL（4）p
extq
ext（5）q
extp
3．（1）pq
ext
（2）q
extp
ext
——线性表五、完成：实验1——线性表完成：——根据实验要求（见教材P201202）认真完成本实验，并提交实验报告。
2
f作业2答案
一、单项选择题
1．C2．B3．A11．B12．C13．B21．B22．D23．C4．C5．B6．A7．B8．C9．A10．C14．B15．A16．C17．B18．A19．C20．D24．B25．D26．A27．28．CD29．30．DC31．A
32．D
二、填空题
1．后进先出2．下一个3．增1增14．假上溢5．栈是否满stopMAXSIZE1栈顶指针栈顶元素修改栈顶指针6．bceda7．终止条件递归部分8．LUfro
tLUrear9．运算符操作数abcfde10．s
exth11．hh
ext12．r
exts13．ff
ext14．字符15．顺序存储方式链式存储方式16．0空格字符的个数17．特殊稀疏18．（）（）2（）19．（（def））20．串长度相等且对应位置的字符相等21．ii12j22．行下标、列下标、非零元素值
栈顶对应的数组元素
栈是否空
stop1
三、问答题1．简述栈和一般线性表的区别。答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。2．简述队列和一般线性表的区别。队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。3．链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。
3
f4．利用一个栈，则：（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输r