x++;
（3）for（j=1;j<=n;j++）
{
printf（“j=%”,j）;
for（k=j;k<=n;k++）
x++;
}
答：
（1）的时间复杂度为O
（1）；
（2）的时间复杂度O（n）；
（3）中“printf（“j=%”,j）;”执行次数的数量级为O（n），“x++;”执行次数是：
n+（n-1）+（n-2）+……+2+1=n（n+1）/2
其数量级为O（n2），因此整个算法段的时间复杂度应该是O（n2）。
第2章习题解答
一、填空
1．当一组数据的逻辑结构呈线性关系时，在数据结构里就称其为线性表。
2．线性表中数据元素的个数n称为线性表的长度。
3．以顺序存储结构实现的线性表，被称为顺序表。
4．以链式存储结构实现的线性表，被称为链表。
5．不带表头结点的链表，是指该链表的表头指针直接指向该链表的起始结点。
6．在一个双链表中，已经由指针ptr指向需要删除的存储结点，则删除该结点所要执行的两条操作是①ptr->Prior->Next=ptr->Next;②ptr->Next->Prior=ptr->Prior;。
7．设tail是指向非空、带表头结点的循环单链表的表尾指针。
那么，该链表起始结点的存储位置应该表示成tail->Next->Next。
8．在一个不带表头结点的非空单链表中，若要在指针qtr所指结点的后面插入一个值为x的结点，则需要执行下列操作：
ptr=malloc（size）;
ptr->Data=x;
ptr->Next=qtr->Next;
qtr->Next=ptr;
9．顺序表Sq=（a1，a2，a3，…，an）（n≥1）中，每个数据元素需要占用w个存储单元。
若m为元素a1的起始地址，那么元素an的存储地址是m+（n-1）*w。
10．当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用顺序存储结构。
二、选择
1．下面，对非空线性表特点的论述，C是正确的。
A．所有结点有且只有一个直接前驱
B．所有结点有且只有一个直接后继
C．每个结点至多只有一个直接前驱，至多只有一个直接后继
D．结点间是按照1对多的邻接关系来维系其逻辑关系的
2．一般单链表Lk_h为空的判定条件是A。
A．Lk_h==NULLB．Lk_h->Next==NULL
C．Lk_h->Next==Lk_hD．Lk_h!
=NULL
3．带表头结点的单链表Lk_h为空的判定条件是B。
A．Lk_h==NULLB．Lk_h->Next==NULL
C．Lk_h->Next==Lk_hD．Lk_h!
=NULL
4．往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动B个结点。
A．nB．n/2C．n+1D．（n+1）/2
5．在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。
现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是C。
A．rtr->Next=ptr->Next;ptr->Next=rtr;
B．ptr->Next=rtr->Next;
C．qtr->Next=rtr;rtr->Next=ptr;
D．ptr->Next=rtr;rtr->Next=qtr->Next;
6．在一个单链表中，若现在要删除ptr指针所指结点的直接后继结点，则需要执行的操作是A。
A．ptr->Next=ptr->Next->Next;
B．ptr=ptr->Next;ptr->Next=ptr->Next->Next;
C．ptr=ptr->Next->Next;
D．ptr->Nextptr;
7．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动B个元素。
A．n-iB．n-i+1C．n-i-1D．i
8．在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动A个元素。
A．n-iB．n-i+1C．n-i-1D．i
9．设tail是指向一个非空带表头结点的循环单链表的尾指针。
那么，删除链表起始结点的操作应该是D。
A．ptr=tail;B．tail=tail->Next;
tail=tail->Next;free（tail）;
free（ptr）;
C．tail=tail->Next->Next;D．ptr=tail->Next->Next;
Free（tail）;tail->Next->Next=ptr->Next;
Free（ptr）;free（ptr）;
10．在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是B。
A．qtr->Next=ptr;B．qtr->Next=ptr->Next;
ptr->Next=qtr;ptr->Next=qtr;
C．qtr->Next=ptr->Next;D．ptr->Next=qtr;
ptr=qtr;qtr->Next=ptr;
三、问答
1．试问，如下的线性表：
L=（29，25，21，17，13，11，7，5，3，1）
是有序线性表还是无序线性表？
答：
L是一个有序线性表。
2．线性表L第i个存储结点ai的起始地址LOC（ai）可以通过下面的公式计算得到：
LOC（ai）=LOC（ai-1）+k
其中k表示存储结点的长度。
这个公式对吗？
为什么？
答：
这个公式是对的，因为第i个存储结点ai的起始地址LOC（ai），实际上就是等于第i-1个存储结点ai-1的起始地址LOC（ai-1）加上一个存储结点的长度k得到。
3．试说明创建顺序表算法Create_Sq（）中，Sq_max和Sq_num的不同之处。
答：
Sq_max代表的是顺序表的最大长度，也就是它最多可以容纳下多少个数据元素，顺序表创建后，Sq_max是一个保持不变的常量；Sq_num代表的是顺序表内当前拥有的数据元素个数，在顺序表创建后，随着对数据元素进行的插入、删除操作，Sq_num将会不断地发生变化。
4．如何判断一个顺序表是否为空？
答：
只需判定Sq_num的当前值是多少，如果Sq_num为0，则表示顺序表Sq为空，否则表示该顺序表里有数据元素存在。
5．在算法2-3里，操作“Sq_num=Sq_num-1”的作用是什么？
没有它行吗？
答：
该操作是非常重要的，因为顺序表里当前拥有的元素个数是通过Sq_num来记录的，删除了一个元素，Sq_num必须减1，这样才能正确反映出删除后表中元素的个数。
所以，没有这个操作是不行的。
6．在算法2-9里，如果现在是把一个结点插入到单链表尾结点的后面。
按照算法的描述，能够保证插入后最后一个结点的Next域为“Λ”吗？
答：
能够。
因为原来ptr->Next里是“Λ”，做了第1步操作：
qtr->Next=ptr->Next;
后，就是把插入结点的Next域置为“Λ”。
7．在一个单链表中，为了删除指针ptr所指的结点，有人编写了下面的操作序列。
读懂并加以理解。
试问，编写者能够达到目的吗？
其思想是什么？
x=ptr->Data;
qtr=ptr->Next;
ptr->Data=ptr->Next->Data;
ptr->Next=ptr->Next->Next;
free（qtr）;
答：
能够达到删除指针ptr所指结点的目的。
编写者的思想是不去直接删除ptr所指的结点，而是在把ptr直接后继的Data域内容写入ptr所指结点的Data域之后，把它的直接后继删除。
对于单链表来说，得到一个结点的直接后继容易，得到它的直接前驱难，所以这样的设计是有其可取之处的。
8．在一个单链表中，为了在指针ptr所指结点之前插入一个由指针qtr所指的结点，有人编写了下面的操作序列，其中temp是一个临时工作单元。
读懂并加以理解。
试问，编写者能够达到目的吗？
其思想是什么？
qtr->Next=ptr->Next;
ptr->Next=qtr;
temp=ptr->Data;
p->Data=qtr->Data;
qtr->Data=temp;
答：
能够达到在指针ptr所指结点之前插入一个由指针qtr所指结点的目的。
编写者的思想是考虑到在单链表中得到一个结点的前驱信息较为困难，因此在这里先把qtr所指结点插入到ptr所指结点的后面，暂时成为它的直接后继。
然后通过临时工作单元temp，将ptr及qtr所指结点的Data域内容进行交换，从而达到插入的目的。
9．打算形成一个有表头结点的循环双链表，初始时除了每个结点的Next域已经链接好外，它们的Prior域还都是空的。
有人编写了下面的算法，试图完成Prior域的链接：
Com_Cd（Cd_h）
{
ptr=Cd_h->Next;
qtr=Cd_h;
while（ptr!
=Cd_h）
{
ptr->Prior=qtr;
qtr=ptr;
ptr=ptr->Next;
}
Cd_h->Prior=qtr;
}
读懂并理解它，解释为什么能够完成各结点的Prior域的链接？
答：
算法中用两个指针ptr和qtr配合，从头到尾扫描这个循环双链表，以达到让每个结点的Prior域指向其直接前驱的目的。
四、应用
1．设计一个计算表头指针为Lk_h的单链表长度（即结点个数）的算法。
答：
算法设计如下：
Length_Lk（Lk_h）
{
n=0;
ptr=Lk_h;/*ptr指向起始结点*/
while（ptr!
=NULL）
{
ptr=ptr->Next;
n=n+1;/*n为结点计数单元*/
}
return（n）;
}
2．用总是在表的头部插入整数结点的方法建立一个单链表，当输入为0时，建表过程结束。
答：
算法设计如下：
Clink（）
{
Lk_h=NULL;
scanf（%d,&x）;
while（x!
=“0”）
{
ptr=malloc（size）;
ptr->Data=x;
ptr->Next=Lk_h;
Lk_h=ptr;
scanf（%d,&x）;
}
returnLk_h;
}
3．一个不带表头结点的循环双链表Ck的表头指针为Ck_h，要在指针ptr指向处前插入一个rtr所指结点。
模仿图2-21，对一般插入位置标示出下面4个操作步骤：
①rtr->Next=ptr;
②rtr->Prior=ptr->Prior;
③ptr->Prior->Next=rtr;
④ptr->Prior=rtr;
答：
4个操作步骤的具体功能体现如下图所示。
4．试设计一个算法copy（Ck_h1,Ck_h2），将一个带表头结点的、以Ck_h1为表头指针的单链表Ck1的内容，复制到一个不带表头结点的、以Ck_h2为表头指针的单链表Ck2中。
答：
算法具体如下。
Copy（Ck_h1,Ck_h2）
{
ptr=Ck_h1->Next;
qtr=Ck_h2;
while（ptr!
=NULL）
{
rtr=malloc（size）;
rtr->Data=ptr->Data;
qtr->Next=rtr;
qtr=rtr;
ptr=ptr->Next;
}
qtr->Next=NULL;
}
5．已知一个带表头结点的递增单链表。
试编写一个算法，功能是从表中去除值大于min、且值小于max的数据元素。
（假定表中存在这样的元素）
答：
所需算法编写如下。
Del_Sq（Lk_h,nim,max）
{
ptr=Lk_h->Next;/*ptr指向链表的起始结点*/
while（（ptr!
=NULL）&&（ptr->Data<=min））/*跳过所有值<=min的结点*/
{
qtr=ptr;
ptr=ptr->Next;
}
while（（ptr!
=NULL）&&（ptr->Datap=p->Next;
qtr->Next=ptr;/*qtr指出第1个大于max的结点位置，完成链接*/
}
6．已知一个带表头结点的无序单链表。
试编写一个算法，功能是从表中去除所有值大于min、且值小于max的数据元素。
答：
所需算法编写如下，其中指针ptr总是指向当前被检查的结点，qtr总是指向被检查结点的直接前驱。
Del_Lk（Lk_h,min,max）
{
ptr=Lk_h->Next;/*ptr指向单链表的起始结点*/
while（ptr!
=NULL）/*扫视直到链尾结点*/
{
if（（ptr->Data<=min）||（ptr->Data>=max）/*不满足删除条件*/
{
qtr=ptr;/*往后移动qtr和ptr*/
ptr=ptr->Next;
}
else/*删除ptr所指结点，往后移动ptr*/
{
qtr->Next=ptr->Next;
free（ptr）;
ptr=qtr->Next;
}
}
}
7．一个单链表Lk的表头指针为Lk_h，不同结点的Data域值有可能相同。
编写一个算法，功能是计算出Data域值为x的结点的个数。
答：
算法应该遍历链表的每一个结点，遇到一个结点的Data域值为x时，计数器n就加1。
最后返回计数器n。
Count_Lk（Lk_h）
{
n=0;
ptr=Lk_h;
while（ptr!
=NULL）
{
if（ptr->Data==x）
n=n+1;
ptr=ptr->Next
}
return（n）;
}
第3章习题解答
一、填空
1．限定插入和删除操作只能在一端进行的线性表，被称为是栈。
2．如果在顺序栈满时仍打算进行进栈操作，就称为发生了“上溢”出错。
3．如果在顺序栈空时仍打算进行出栈操作，就称为发生了“下溢”出错。
4．在具有n个数据结点的循环队列中，队满时共有n-1个数据元素。
5．如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次出栈；最后让字母G进栈，做三次出栈。
最终这个堆栈从栈顶到栈底的余留元素应该是DA。
6．中缀表达式（a+b）-（c/（d+e））对应的后缀表达式是ab+cde+/-。
7．函数的递归调用有两种形式：
如果一个函数是直接调用自己，就称其为直接递归调用；如果一个函数是通过另一个函数来调用自己，就称其为间接递归调用。
8．设某栈的元素输入顺序是1、2、3、4、5，想得到4、3、5、2、1的输出顺序。
那么push、pop的操作序列应该是push、push、push、push、pop、pop、push、pop、pop、pop。
9．设链栈的栈顶指针为Ls_top，那么它非空的条件应该是Ls_top!
=NULL。
10．队列中，允许进行删除的一端称为队首。
二、选择
1．一个栈的元素进栈序列是a、b、c、d、e，那么下面的C不能做为一个出栈序列。
A．e、d、c、b、aB．d、e、c、b、a
C．d、c、e、a、bD．a、b、c、d、e
2．判定一个顺序队列Qs（最多有n个元素）为空的条件是C。
A．Qs_rear-Qs_front==n*sizeB．Qs_rear-Qs_front+1==n*size
C．Qs_front==Qs_rearD．Qs_front==Qs_rear+size
3．判定一个顺序队列Qs（最多有n个元素）真满的条件是A。
A．Qs_rear-Qs_front==n*sizeB．Qs_rear-Qs_front+1==n*size
C．Qs_front==Qs_rearD．Qs_front==Qs_rear+size
4．在一个链式队列Lq中，Lq_front和Lq_rear分别为队首、队尾指针。
现在由指针ptr所指结点要进队，则插入操作应该是B。
A．Lq_front->Next=ptr;Lq_front=ptr;
B．Lq_rear->Next=ptr;Lq_rear=ptr;
C．ptr->Next=Lq_rear;Lq_rear=ptr;
D．ptr->Next=Lq_front;Lq_front=ptr;
5．链栈与顺序栈相比，一个较为明显的优点是D。
A．通常不会出现栈空的情形B．插入操作更加便利
C．删除操作更加便利D．通常不会出现栈满的情形
6．向链栈插入一个结点时，操作顺序应该是C。
A．先修改栈顶指针，再插入结点B．无须修改栈顶指针
C．先插入结点，再修改
升级会员 