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
答:在队列的顺序存储结构中，设头指针为front，队尾指针rear，队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时，若rear=MaxSize（初始时rear=0）则发生队列的上溢现象，该元素不能加入队列。特别要注意的是队列的假溢出现象：队列中还有剩余空间但元素却不能进入队列，造成这种现象的原因是由于队列的操作方法所致。 解决队列上溢的方法有以下几种： （1） （2） 【1】 【2】 位置； 【3】
采用循环队列方式：把队列看成一个首尾相接的循环队列，在循环队列上进行插入或删除运
算时仍然遵循“先进先出”的原则。
5.利用两个栈S1、S2模拟一个队列时，如何用栈的运算实现队列的入队、出队以及队列的判空运算？请简述算法思想。
答：利用两个栈S1和S2模拟一个队列的基本思想是：用一个栈S1作为输入栈，另一个栈S2作为输出栈。入队时，总是将元素输入S1,出队时，若输出栈S2已空，则将S1中元素全部输入到S2中，然后由S2输出元素。若输出栈S2不空，则直接由S2输出元素。显然，只有输入栈、输出栈均为空时队列才为空。 6.设输入元素为1，2，3，P和A，输入次序为123PA，元素经过栈后到达输出序列，当所有元素到达输出序列后，有哪些序列可作为高级语言的变量名（以字母开头的字母数字串）。 答：AP321，PA321,P3A21,P32A1,P321A。 3.4.5
算法设计题
1. 用一个一维数组S（设大小为MAX）作为两个栈的共享空间。请说明共享方法，栈满、栈空的判断条件，并用C/C++语言设计公用的初始化栈运算InitStack(st)、入栈运算Push(st，i，x)和出栈运算Pop(st,i,x)和出栈运算Pop(st,i,x)，其中i为0或1，用于表示栈号，x为入栈元素。
解：设用一维数组S[MaxSize]作为两个栈的共享空间，整型变量top1、top2分别作为两个栈的栈顶指针，并约定栈顶指针指示当前元素的下一个位置。S1的栈底位置设在S[0]，S2的栈底位置设在S[MaxSize-1]，栈S1空的条件是top1==-1，栈S1满的条件是top1==top2-1，栈S2空的条件是top2==MaxSize，栈S2满的条件是top1==top2-1，栈S2空的条件是top2==MaxSize，栈S2满的条件是top2==top1+1。归纳起来，栈S1和S2满的条件都是top1==top2-1。 对应的算法如下：
#define Maxsize 100 5.4补充练习题及参考答案 5．4.1 单项选择题
1.数组A[0..5,0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5][6]的地址为__________。 A.1175 B.1180 C.1205 D.1210
答：a[5][6]的地址=1000+（5*6+5）*5=1175.所以本题答案是A.
2.一个n*n的对称矩阵，如果以行或列为主序放入内存，则容量为_____________。 A.n B.n/2 C.n (n+1)/2 D.(n+1)/2
答：对称矩阵只需存储上（下）三角形（含主对角线）元素，以存放下三角形（含主对角线）元素为例，第1行1个元素，第2行2个元素，?，第n行n个元素，共有1+2+?+n=n(n+1)/2个元素。本题答案C. 3.对矩阵压缩存储是为了___________。
A.方便运算 B.节省空间 C.方便存储 D.提高运算速度 答：B 4.与三元组顺序表相比，稀疏矩阵用十字链表表示，其优点在于____________。
9
2
2
2
建立一个足够大的存储空间，但这样做会造成空间的使用效率降低。 当出现假溢出时可采用以下几种方法：
采用平移元素的方法：每当队列中加入一个元素时，队列中已有的元素向队头移动一个位置每当删除一个队头元素时，则依次移动队中的元素，始终使front指针指向队列中的第一个
（当然要有空闲的空间可供移动）；
A.便于实现增加或减少矩阵中非零元素的操作 B.便于实现增加或减少矩阵元素的操作 C.可以节省存储空间
D.可以更快地查找到某个非0元素 答：A 5.对稀疏矩阵采用压缩存储，其缺点之一是____________。 A.无法判断矩阵有多少行多少列 B.无法根据行列号查找某个矩阵元素 C.无法根据行列号计算矩阵元素的存储地址
D. 使矩阵元素之间的逻辑关系更加复杂 答：C 5.4.2 填空题
1.一维数组的逻辑结构是____①____，存储结构是_____②_____；对于二维或多维数组，分为按____③____和____④____两种不同的存储方式答①线性结构 ②顺序结构 ③按行优先顺序 ④按列优先顺序。 2.数组A[1..10，-2..6，2..8]以行优先顺序存储，设第一个元素的首地址为100，每个元素占3个单元的存储空间，则元素A[5][0][7]的存储地址为_________。
答：LOC(A[5][0][7])=100+[(5-1)*(6-(-2)+1)*(8-2+1)+(0-(-2))*(8-2+1)+(7-2)]*3=913
3.三位数组R[c1..d1,c2..d2,c3..d3]共含有__________个元素。答：（d1-c1+1）*（d2-c1+1）*（d3-c3+1） 5.4.3 判断题判断以下叙述的正确性。 （1） （2） （3） （4） （5） （6）
用一位数组表示矩阵，可以简化对矩阵的存取操作。 对角矩阵的特点是非零元素只出现在矩阵的两条对角线上。 在n阶三对角矩阵中，每一行都有n个元素。 稀疏矩阵的特点是矩阵中元素较少。
在表示稀疏矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小有关。 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对
该矩阵的转置运算。答：（1）错误。（2）错误。（3）正确。（4）错误。（5）错误。 （6）错误。因为三元组是以行序存储的，这种下标互换方法没有考虑行序。 5.4.4 简答题
1.数组A[1..3,0..1,1..2]有多少个元素？
答：该数组时一个三维数组，各维的大小分别为3、2和2，所以元素个数=3*2*2=12个。
2. 二维数组A[4][4](即A[0..3][0..3])的元素起始地址是loc(A[0][0])=1000,元素的长度为2，则loc(A[2][2])为多少？
答：loc(A[2][2])=loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=1020。
3.对于给定的数组a[n][2*n-1]，现将3个顶点分别为a[0][n-1]、a[n-1][0]和a[n-1][2*n-2]的三角形上的所有元素按行序依次存放在一维数组b[n*n]中。例如，当n=3时，数组a[3][5]中用线连成的三角形如图5.3所示。
a00
a01 a02 a03 a04
a10 a11 a12 a13 a14
a20 — a21 — a22 — a23 — a24 图5.3 矩阵元素连成的三角形
若把三角形上的所有元素按行序依次存放在一维数组b[3*3]上，则有： i 0 1 2 3 4 5 6 7 8 b[i] a02 a11 a12 a13 a20 a21 a22 a23 a24
10