for（j=1;j<=n-i;j++）
x++;
（6）x=n;//n>1
y=0;
while（x≥（y+1）*（y+1））
y++;
（1）O
（1）
（2）O（m*n）
（3）O（n2）
（4）O（log3n）
（5）因为x++共执行了n-1+n-2+……＋1=n（n-1）/2，所以执行时间为O（n2）
（6）O（
）
第2章线性表
1．选择题
（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110B．108C．100D．120
（2）在n个结点的顺序表中，算法的时间复杂度是O
（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8B．63.5C．63D．7
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数
（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续或不连续都可以
（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入
C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂
（7）单链表的存储密度（）。
A．大于1B．等于1C．小于1D．不能确定
（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．nB．2n-1C．2nD．n-1
（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。
A．n-iB．n-i+1C．n-i-1D．i
（10）线性表L=（a1，a2,……an），下列说法正确的是（）。
A．每个元素都有一个直接前驱和一个直接后继
B．线性表中至少有一个元素
C．表中诸元素的排列必须是由小到大或由大到小
D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
（11）若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（）。
A．O
（1）B．O（n）C．O（n2）D．O（nlog2n）
（12）以下说法错误的是（）。
A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B．顺序存储的线性表可以随机存取
C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D．线性表的链式存储结构优于顺序存储结构
（13）在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。
A．s->next=p+1;p->next=s;
B．（*p）.next=s;（*s）.next=（*p）.next;
C．s->next=p->next;p->next=s->next;
D．s->next=p->next;p->next=s;
（14）在双向链表存储结构中，删除p所指的结点时须修改指针（）。
A．p->next->prior=p->prior;p->prior->next=p->next;
B．p->next=p->next->next;p->next->prior=p;
C．p->prior->next=p;p->prior=p->prior->prior;
D．p->prior=p->next->next;p->next=p->prior->prior;
（15）在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。
A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;
2．算法设计题
（1）将两个递增的有序链表合并为一个递增的有序链表。
要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。
表中不允许有重复的数据。
voidMergeList_L（LinkList&La,LinkList&Lb,LinkList&Lc）{
pa=La->next;pb=Lb->next;
Lc=pc=La;//用La的头结点作为Lc的头结点
while（pa&&pb）{
if（pa->datadata）{pc->next=pa;pc=pa;pa=pa->next;}
elseif（pa->data>pb->data）{pc->next=pb;pc=pb;pb=pb->next;}
else{//相等时取La的元素，删除Lb的元素
pc->next=pa;pc=pa;pa=pa->next;
q=pb->next;deletepb;pb=q;}
}
pc->next=pa?
pa:
pb;//插入剩余段
deleteLb;//释放Lb的头结点}
（2）将两个非递减的有序链表合并为一个非递增的有序链表。
要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。
表中允许有重复的数据。
voidunion（LinkList&La,LinkList&Lb,LinkList&Lc,）{
pa=La->next;pb=Lb->next;//初始化
Lc=pc=La;//用La的头结点作为Lc的头结点
Lc->next=NULL;
while（pa||pb）{
if（!
pa）{q=pb;pb=pb->next;}
elseif（!
pb）{q=pa;pa=pa->next;}
elseif（pa->data<=pb->data）{q=pa;pa=pa->next;}
else{q=pb;pb=pb->next;}
q->next=Lc->next;Lc->next=q;//插入
}
deleteLb;//释放Lb的头结点}
（3）已知两个链表A和B分别表示两个集合，其元素递增排列。
请设计算法求出A与B的交集，并存放于A链表中。
voidMix（LinkList&La,LinkList&Lb,LinkList&Lc,）{
pa=la->next;pb=lb->next;∥设工作指针pa和pb；
Lc=pc=La;//用La的头结点作为Lc的头结点
while（pa&&pb）
if（pa->data==pb->data）∥交集并入结果表中。
{pc->next=pa;pc=pa;pa=pa->next;
u=pb;pb=pb->next;deleteu;}
elseif（pa->datadata）{u=pa;pa=pa->next;deleteu;}
else{u=pb;pb=pb->next;deleteu;}
while（pa）{u=pa;pa=pa->next;deleteu;}∥释放结点空间
while（pb）{u=pb;pb=pb->next;deleteu;}∥释放结点空间
pc->next=null;∥置链表尾标记。
deleteLb;∥注：
本算法中也可对B表不作释放空间的处理
（4）已知两个链表A和B分别表示两个集合，其元素递增排列。
请设计算法求出两个集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。
voidDifference（LinkedListA，B，*n）
∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0
{p=A->next；∥p和q分别是链表A和B的工作指针。
q=B->next；pre=A；∥pre为A中p所指结点的前驱结点的指针。
while（p!
=null&&q!
=null）
if（p->datadata）{pre=p；p=p->next；*n++；}∥A链表中当前结点指针后移。
elseif（p->data>q->data）q=q->next；∥B链表中当前结点指针后移。
else{pre->next=p->next；∥处理A，B中元素值相同的结点，应删除。
u=p；p=p->next；deleteu；}∥删除结点
（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。
（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
ElemTypeMax（LinkListL）{
if（L->next==NULL）returnNULL;
pmax=L->next;//假定第一个结点中数据具有最大值
p=L->next->next;
while（p!
=NULL）{//如果下一个结点存在
if（p->data>pmax->data）pmax=p;
p=p->next;
}
returnpmax->data;
（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
voidinverse（LinkList&L）{
//逆置带头结点的单链表L
p=L->next;L->next=NULL;
while（p）{
q=p->next;//q指向*p的后继
p->next=L->next;
L->next=p;//*p插入在头结点之后
p=q;
}
}
（8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。
voiddelete（LinkList&L,intmink,intmaxk）{
p=L->next;//首元结点
while（p&&p->data<=mink）
{pre=p;p=p->next;}//查找第一个值>mink的结点
if（p）{
while（p&&p->datanext;
//查找第一个值≥maxk的结点
q=pre->next;pre->next=p;//修改指针
while（q!
=p）
{s=q->next;deleteq;q=s;}//释放结点空间
}//if
}
（9）已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change（p）,交换p所指向的结点和它的前缀结点的顺序。
知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。
voidExchange（LinkedListp）
∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。
{q=p->llink；
q->llink->rlink=p；∥p的前驱的前驱之后继为p
p->llink=q->llink；∥p的前驱指向其前驱的前驱。
q->rlink=p->rlink；∥p的前驱的后继为p的后继。
q->llink=p；∥p与其前驱交换
p->rlink->llink=q；∥p的后继的前驱指向原p的前驱
p->rlink=q；∥p的后继指向其原来的前驱
}∥算法exchange结束。
（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O（n）、空间复杂度为O
（1）的算法，该算法删除线性表中所有值为item的数据元素。
[题目分析]在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。
本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。
因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。
voidDelete（ElemTypeA[]，intn）
∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。
{i=1；j=n；∥设置数组低、高端指针（下标）。
while（i{while（i=item）i++；∥若值不为item，左移指针。
if（iif（i}
[算法讨论]因元素只扫描一趟，算法时间复杂度为O（n）。
删除元素未使用其它辅助空间，最后线性表中的元素个数是j。
第3章栈和队列
习题
1．选择题
（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。
A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．iB．n-iC．n-i+1D．不确定
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-fB．（n+f-r）%nC．n+r-fD．（n+r-f）%n
（4）链式栈结点为：
（data,link），top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->data;top=top->link；B．top=top->link;x=top->link；
C．x=top;top=top->link；D．x=top->link；
（5）设有一个递归算法如下
intfact（intn）{ //n大于等于0
if（n<=0）return1;
elsereturnn*fact（n-1）; }
则计算fact（n）需要调用该函数的次数为（）。
A． n+1 B． n-1 C．n D．n+2
（6）栈在 （）中有所应用。
A．递归调用B．函数调用C．表达式求值D．前三个选项都有
（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。
主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是（）。
A．队列B．栈C．线性表D．有序表
（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
A．2B．3C．4D．6
（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（ ）。
A．top不变B．top=0C．top--D．top++
（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构B．队列
C.线性表的链式存储结构D.栈
（11）用链接方式存储的队列，在进行删除运算时（ ）。
A.仅修改头指针B.仅修改尾指针
C.头、尾指针都要修改D.头、尾指针可能都要修改
（12）循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear=rear+1B.rear=（rear+1）%（m-1）
C.rear=（rear+1）%mD.rear=（rear+1）%（m+1）
（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A.（rear+1）%n==frontB.rear==front
C．rear+1==frontD.（rear-l）%n==front
（14）栈和队列的共同点是（ ）。
A.都是先进先出B.都是先进后出
C.只允许在端点处插入和删除元素D.没有共同点
（15）一个递归算法必须包括（ ）。
A.递归部分B.终止条件和递归部分
C.迭代部分D.终止条件和迭代部分
（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。
试写一个算法判定给定的字符向量是否为回文。
（提示：
将一半字符入栈）
根据提示，算法可设计为：
//以下为顺序栈的存储结构定义
#defineStackSize100//假定预分配的栈空间最多为100个元素
typedefcharDataType;//假定栈元素的数据类型为字符
typedefstruct{
DataTypedata[StackSize];
inttop;
}SeqStack;
intIsHuiwen（char*t）
{//判断t字符向量是否为回文，若是，返回1，否则返回0
SeqStacks;
inti,len;
chartemp;
InitStack（&s）;
len=strlen（t）;//求向量长度
for（i=0;i Push（&s,t[i]）;
while（!
EmptyStack（&s））
{//每弹出一个字符与相应字符比较
temp=Pop（&s）;
if（temp!
=S[i]） return0;//不等则返回0
elsei++;
}
return1;//比较完毕均相等则返回1
}
（3）设从键盘输入一整数的序列：
a1,a2,a3，…，an，试编写算法实现：
用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
#definemaxsize栈空间容量
voidInOutS（ints[maxsize]）
//s是元素为整数的栈，本算法进行入栈和退栈操作。
{inttop=0;//top为栈顶指针，定义top=0时为栈空。
for（i=1;i<=n;i++）//n个整数序列作处理。
{scanf（“%d”,&x）;//从键盘读入整数序列。
if（x!
=-1）//读入的整数不等于-1时入栈。
if（top==maxsize-1）{printf（“栈满\n”）;exit（0）;}elses[++top]=x;//x入栈。
else//读入的整数等于-1时退栈。
{if（top==0）{printf（“栈空\n”）;exit（0）;}elseprintf（“出栈元素是%d\n”,s[top--]）；}}
}//算法结束。
（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。
规定：
逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。
例如：
23434+2*$。
[题目分析]逆波兰表达式（即后缀表达式）求值规则如下：
设立运算数栈OPND,对表达式从左到右扫描（读入），当表达式中扫描到数时，压入OPND栈。
当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。
这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。
升级会员 