6.若线性表最常用的运算是存取第i个元素及其前驱的值，则采用_____存储方式节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 答：顺序表适合于随机存取。所以本题选D。
7.在单链表中，若*p结点不是末尾结点，在其后插入*s结点的操作是_____ A.s->next=p;p->next=s; B.s->next=p->next;p->next=s; C.s->next=p->next;p=s; D.p->next=s;s->next=p;
答：先要将*s结点的next指向*p之后的结点（s->next=p->next），然后将*p结点的next指向*s（p->next=s）。所以答案为B。
8.在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为______。 A.O(Ibn) B.O(1) C. O(n2) D.O(n）
答：先要查找到插入结点的前一个结点的指针，其时间复杂度为O(n)。本题答案为D。
9.对于用一维数组d[1?.n]顺序存储的线性表，其算法的时间复杂度为O(1)的操作是___、______。 A.将n个结点从小到大排序 B.从线性表中删除第i个结点（1≤i≤n） C.查找第i个结点（1≤i≤n）D.求第i个结点（2≤i≤n）的前趋结点
答：A操作一般需要两层循环，时间复杂度为O( n2)或O(nIbn)；B操作需要移动结点，时间复杂度为O(n)；C操作可以直接由d[i]得到，时间复杂度为O(1);D操作也可以直接由d[i-1]得到，时间复杂度为O(1)。本题答案为C、D。
10.在一个单链表中，删除*p结点之后的一个结点的操作是____。 D
A．p->next=p; B. p->next->next=p->next; C. p->next->next=p; D p->next=p->next->next; 11.在一个双链表中，在*p结点之后插入一个结点*s的操作是_____。 B A．s->prior=p;p->next=s;p->next->prior=s;s->next=p->next; B. s->next=p->next;p->next->prior=s;p->next=s;s->prior=p; C. p->next=s;s->prior=p;s->next=p->next;p->next->prior=s; D. p->next->prior=s;s->next=p->next;s->prior=p;p->next=s; 12.在一个双链表中，删除*p结点之后的一个结点的操作是_____。 C A．p->next=p->next->next;p->next->next->prior=p; B．p->next->prior=p;p->next=p->next->next; C．p->next=p->next->next;p->next->prior=p; D．p->next->next=p->next;p->next->prior=p;
13 在不带头结点（头结点为 *head）的单循环链表中，至少有一个结点的条件是＿①＿，尾结点为*p的条件是 ＿②＿。 A D
A .head!=NULL B .head->next!=head C .p==NULL D .p->next==head
14 在带头结点*head的单循环链表中，至少有一个结点的条件是＿①＿，尾结点*p的条件是＿②＿。 B D A head->next != NULL B head->next!=head C p==NULL D p->next==head 2.4.2填空题
1．在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置___决定的；在线性表的链接存储中，元素之间的逻辑关系是通过___链域的指针值___决定的。 2．带头结点的单链表head 为空的判定条件___head->next==NULL__.
3．在一个单链表head 中，已知p 指向其中的一个结点，若要删除其后的一个结点，则执行的运算是_q=p->next; p->next=q->next; free(q)___.
4．在一个单链表head 中，已知p 指向其中的一个结点，若要在它之前插入一个结点，则执行的运算是s->next=p->next;p->next=s;;temp=p->data;p->data=s->data;s->data=temp;_
5
5．在一个双链表dhead 中，若要在*p 结点之前插入一个结点 * s,则执行的运算是__s->next=prior=p->prior; s->prior->next=q; s->next=p; p->prior=s;__.
6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__O(1)_,在给定值为x的结点后插入一个新结点的时间复杂度为___O(n)_.
7．在n个元素的顺序表中删除任意一个元素所需移动结点的平均次数为__（n-1）/2 ____ 8．在有n 个元素的顺序表中任意位置插入一个元素所需移动结点的平均次数为_n/2___ __ 2.4.3 判断题1．判断以下叙述的正确性。 （1）分配给单链表的内存单元地址必须是连续的。
（2）与顺序表相比，在链表上实现顺序访问，其算法的效率比较低。 （3）从长度为n的顺序表中删除一个元素，所需时间都是O(n). （4）向顺序表中插入一个元素，平均要移动大约一半的元素。 （5）凡是空的电链表都是不含任何结点的。
（6）如果单链表带有头结点，则插入操作永远不会改变头结点指针的值。 （7）在循环单链表中，任何一个结点的指针字段值都不可能为空。 答：（1）错误。分配给单链表的内存单元地址可以是不连续的。
（2）错误。在顺序表和链表上实现顺序访问，时间复杂度均为O(n)。
（3）错误。删除最后一个元素时，所需时间都是O(1)。但从长度为n的顺序表中删除一个元素，平均时间是O(n)。（4）正确。 （5）错误。带头结点单链表为空时仍有一个头结点。 （6）正确。（7）正确。 2．判断以下叙述的正确性。
（1）顺序存储方式的优点是存储密度大且插入、删除运算效率高。 （2）线性表的顺序存储结构优于链式存储结构。
（3）顺序存储结构鼠疫静态结构而链式存储结构属于动态结构。 （4）由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。 （5）对于单链表来说，只有从头结点开始才能扫描表中全部结点。
（6）对于循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表。 （7）双链表的特点是找结点的前驱和后继都很容易。
答：（1）错误。顺序存储方式的优点是存储密度大但插入、删除运算效率低。（2）错误。顺序和链式存储结构各有优缺点。（3）正确。 （4）正确。（5）正确。（6）错误。对于循环链表来说，从表中任一结点出发都能通过后移操作扫描整个循环链表，因无前驱指针，故不能进行前移操作。（7）正确。 2.4.4 简答题
1．线性表中有两种存储结构：一是顺序表，二是链表，试问：
（1）如果有n个线性表同时共存，并且在处理过程中各表的长度会董爱地发生变化，线性表的总数也会自动地改变。在此情况下应选用哪种存储结构？为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存取结构？为什么？
答：（1）由于链式存储结构可以用任意的存储空间俩存储线性表中的各数据元素，且其存储空间可以是连续的，也可以不连续；此外，这种存储结构对元素进行插入和删除操作时都无须移动元素，而仅仅修改指针即可，多以很适用于线性表容量变化的情况。
（2）由于顺序存储结构一旦确定了起始位置，线性表中的任何一个远树都可以进行随机存取，即存取速度较高；并且，由于线性表的总数基本稳定，且很少进行插入和删除，所以这一特点恰好避开了顺序存储结构的缺点，因此，应选用顺序存储结构。
2．线性表的顺序存储结构具有三个弱点：其一，在做插入或删除操作时，需移动大量元素；其二，由于需要的空间量难以估计，所以必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
6
答：（1）不一定。由于链式存储需要额外的空间来存储指针，所以要比顺序存储多占用空间。在空间允许的情况下，链式存储可以克服顺序存储结构的弱点，但空间不允许时，链式存储结构会出现新的问题。 3．在单链表和双向链表中，能否从当前结点出发访问到任一结点？
答：在单链表中只能由当前结点访问其后继的任一结点，但因其没有指向前驱的指针而无法访问其前驱结点。在双向链表中，由于当前结点既有指向后继结点的指针，又有指向前驱结点的指针，所以在双向链表中可以由当前结点出发访问表中的任何一个结点。 4．哪些链表从尾指针出发可以访问到链表中的任意结点？
答：单循环链表和双循环链表可以从尾指针出发访问到链表中的任意结点。
5．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采取何种存储结构？为什么？
5.若用s[1]~s[m]作为顺序栈的存储结构，栈空的标志是栈指针top的值等于m+1，则每进行一次______操作，需将top的值加1；每进行一次______操作，需将top的值减1。 答：这里以s[m]端作为栈底，s[1]端作为栈顶。本题答案：出栈；进栈
6.若用不带头结点的单链表来表示链式栈，则创建一个空栈所要执行的操作是_________。 答：将单链表的头结点指针赋空值
7.若用带头结点的单链表来表示链式栈，则创建一个空栈所要执行的操作是_________。 答：将单链表的头结点指针域赋空值
8.栈和队列的区别仅在于_________。答：删除元素（即出栈和出队）的操作不同
9.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则最多只能执行_________次入队操作。答：m 10. 若用Q[1]~Q[100]作为循环顺序队列的存储空间，Q[f]、Q[r]分别表示队首元素和下一个插入位置，则当f=70,r=20时，队列中共有_________个元素。答：MaxSize=100,元素个数=(f-r+MaxSize)%MaxSize=50 11.顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生__________现象。答：假溢出 3.4.3
判断题1.判断以下叙述的正确性。
（1）栈底元素是不能删除的元素。（2）顺序栈中元素值的大小是有序的。 （3）在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。 （4）栈顶元素和栈底元素有可能是同一元素。
（5）若用s[1]~s[m] 表示顺序栈的存储结构，则对栈的进栈、出栈操作最多只能进行m次。 （6）栈是一种对进栈、出栈操作总次数做了限制的线性表。 （7）对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。
（8）栈是一种对进栈、出栈操作的次序做了限制的线性表。（9）空栈没有栈顶指针。 （10）n个元素进队列的顺序和出队列的顺序总是一致的。
（11）顺序队列中有多少元素，可以根据队首指针的值和队尾指针的值来计算。
（12）若用“队首指针的值和队尾指针的值相等”作为循环顺序队列为空的标志，则在设置一个空队列时，只需给队首指针和队尾指针赋同一个值，不管什么值都可以。
（13）无论是顺序队列还是链接队列，插入、删除运算的时间复杂度都是O（1）。
（14）队列若用不带头结点的非循环单链表来表示链式队列，则可以用“队首指针的值和队尾指针的值相等”作为队空的标志。
答：（1）错误。栈底元素可以删除。（2）错误。顺序栈是指用顺序存储结构实现的栈，栈中的元素不是有序的。（3）正确。后进栈的元素先出栈，先出栈的元素后出栈。 （4）正确。当栈中只有一个元素时就是这种情况。
（5）错误。可以进行任意多次的进栈、出栈操作，但栈中最多只有m个元素。 （6）错误。可以进行任意多次的进栈、出栈操作。（7）正确。
（8）错误。只要栈不满就可以进行进栈操作，只要栈不空就可以进行出栈操作，并不规定进栈、出栈操作的次序。（9）错误。空栈指栈中没有元素，但一定要有栈顶指针。
7
（10）正确。后进队的元素后出队，先进队的元素先出队。（11）正确。
（12）正确。因为无论出队和入队，都要进行求余运算，将队首指针和队尾指针转化为有效的顺序队下标值，另外，循环顺序队中的元素可以平行移动，所以本叙述是正确的。（13）正确。
（14）错误。应该用“队首指针的值和队尾指针的值均为NULL”作为队空的标志，队首指针的值和队尾指针的值相等表示队列中有一个元素。 2.判断以下叙述的正确性。
（1）栈和队列都是限制存取端的线性表。
（2）即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（3）消除递归不一定需要使用栈。
（4）栈的输入序列为1，2，3，?，n，输出序列为a1,a2,?,an,若ai=n(1<=i<=n-1),则ai>ai+1>an。 3.4.4
简答题
1.试各举一个实例，用示意图和简要说明阐述栈和队列在程序设计中所起的作用。
答：栈的特点是后进先出，所以在解决实际问题涉及后进先出的情况时，可以考虑使用栈。例如，表达式的括号匹配问题。设置一个栈，将读到的左括号入栈，每读入一个右括号，判断栈顶是否为左括号，若是，则出栈；否则，表示不匹配。
队列的特点是先进先出。例如操作系统中的作业排队，在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过输出，那就要按请求输出的先后次序排队。每当通道传输完毕并可以接受新的输出任务时，队头的作业先从队列中退出做输出操作。凡是申请输出的作业都从队尾进入队列。
2.假定有4个元素A,B,C,D依次入栈，入栈过程中允许出栈，试写出所以可能的出栈序列。 答：当输入栈的元素为n个时，经过栈运算后可得到的输出序列个数为： n=4时，出栈序列个数为1/5*8!/4!/4!=14种，如表3.1所列。
表3.1
以A开头
ABCD ABDC ACBD ACDB ADCB
以B开头 BACD BADC BCAD BCDA BDCA 以C开头 CBAD CBDA CDBA 以D开头 DCBA
3．假设以S和X分别表示入栈和出栈操作，则初态和终态为栈空的入栈和出栈的操作序列，可以表示为仅由S和X组成的序列。称可以实现的栈操作序列为合法序列（例如SXXS为合法序列，SXXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：对同一输入序列的两个不同的合法序列不可能得到相同的输出元素序列。
答：合法的栈操作序列必须满足以下两个条件： （1） （2）
在操作序列的任何前缀（从开始到任何一个操作时刻）中，S的个数不得少于X的个数。 整个操作序列中S和X的个数相等。
出栈序列
要求证明：对同一输入序列a1,a2,?,an的两个不同的合法操作序列：
p=p1,p2,?,pj-1,pj,?,p2n,q=q1,q2,?,qj-1,?q2n,不可能得到相同的输出元素序列。
证明：因为p!=q,所以一定存在一个j（1<=j<=2n）,使得p1p2?pj-1=q1q2?qj-1,而pj!=qj,假设操作子序列p1,p2,?,pj-1已将a1,a2,?,ai-1入栈且将其中某些元素出栈，而ai,ai+1?an尚未入栈。因为p和q都是合法栈操作序列，且pj!=qj，所以pj和qj中必有一个为S操作，另一个为X操作（不失一般性，不妨设pj为S操作，qj为X操作）。而且栈不必为空（不然就不能进行X操作）。设栈顶元素为af(1<=f<=i)。因此对于操作序列p来说，在其对应的输出元素序列中ai必领先于af（因为pj为S操作，它使ai入栈，而af尚在栈中），对于操作序列q来说，在其对应的输出元素序列中，af必领先于ai（因为qj为X操作，它使af出栈而ai尚未入栈），所以p和q必定对应不同的输出元素序列。 4.什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？
8