数据结构课后练习题汇编

数据结构课后练习题

第一章绪论

-、选择题

1、数据结构被形式定义为（D,S）,其中口是（）的有限集合，S是D上的（）有限集合。

A、算法B、数据元素C、数据操作D、逻辑关系E、操作F、映象G、存储H、关系

2、数据结构是一门研究非数值计算的程序设计问题中计算机的（（1））以及它们之间的（②）和运算

的学科。

（1）A、操作对象B、计算方法C、逻辑存储D、数据映象

（2）A、结构B、关系C、运算D、算法

3、算法分析的目的是（），算法分析的二个主要方面是（

A、给出数据结构的合理性B、研究算法中输入输出的关系

C、空间复杂性和时间复杂性D、分析算法的效率以求改进

E、正确性和简明性F、分析算法的易懂性和文档性

4、在数据结构中，从逻辑上可以把数据结构分成（）。

A、动态和静态结构B、紧凑接和非紧凑结构

C、线性与非线性结构D、内部结构和外部结构

5、计算机算法指的是（），它必具备输入、输出和（）5个特性。

A、计算方法B、排序方法C、解决问题的有限运算序列D、可行性、可移植性和可扩充性E、可行

性、确定性和有穷性

6、线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是种（）

A、随机存取B、顺序存取C、索引存取D、散列存取

7、算法的时间复杂度取决于（）

A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态

8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）

A、必须是连续的B、部分地址必须是连续的

C、一定是不连续的D、连续不连续都可以

9、在以下的叙述中，正确的是（）

A、线性表的线性存储结构优于链式存储结构

B、二维数组是它的每个数据元素为一个线性表的线性表

C、栈的操作方式是先进先出

D、队列的操作方式是先进后出

10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的

数据组织形式。以下解释错误的是（）

A、集合中任何两个结点之间都有逻辑关系但组织形式松散

B、线性结构中结点按逻辑关系依次排列形成一条“锁链”

C、树形结构具有分支、层次特性，其形态有点像自然界中的树

D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接

11、以下说法正确的是（）

A、数据元素是数据的最小单位

B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合

D、数据结构是带有结构的数据元素的集合

二、填空题

1、数据逻辑结构包括（）四种类型，树型和图型结构合称（）。

2、对于给定的n个元素，可以构造出的逻辑结构有（）、（）、（）和（）四种。

3、算法的五个重要特性是（）。

4、评价算法的性能从利用计算机资源角度看主要从（）方面进行分析。

5、线性结构中元素之间存在（）关系，树型结构中元素之间存在（）关系，图型结构中元素之间

存在（）关系。

6、下面程序段的时间复杂度是（）。

i=s=O;while（s<n）{i++;s++;}

7、下面程序段的时间复杂度是（）。

s=0;for（I=0;kn;I++）for（j=0;j<m;j++）s+=a[i][j]；

8、所谓数据的逻辑结构指的是数据元素之间的。

9、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容。

10、在线性结构中，开始结点前驱结点，其余每个结点有且只有一个结点。

11、在树形结构中，根结点只有,根结点无前驱，其余每个结点有且只有前驱结点；叶子结点

没有结点，其余每个结点的后继结点可以。

12、在图形结构中，每个结点的前驱结点和后继结点可以有。

13、存储结构是逻辑结构的实现。

14、从数据结构的观点看，通常所说的''数据”应分成三个不同的层次，即、和

15、根据需要，数据元素又被称为、、或。

16、通常，存储结点之间可以有、、、四种关联方式，称为四种

基本存储方式。

17、通常从、、、等几方面评价算法的（包括程序）的质量。

18、一个算法的时空性能是指该算法的和，前者是算法包含的

.后者是算法需要的。

19、在一般情况下，一个算法的时间复杂性是的函数。

20、常见时间复杂性的量级有：常数阶0（）、对数阶0（）、线性阶0（）、

平方阶0（）、和指数阶0（）。通常认为，具有指数阶量级的算法是的。

21、数据结构的基本任务是数据结构的和。

22、数据对象是性质相同的的集合。

23、抽象数据类型是指一个以及定义在该模型上的一组操作。

三、判断题

1.数据元素是数据的最小单位。

2.数据结构是带有结构的数据元素的集合。

3.数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。

4.数据项是数据的基本单位。

5.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。

6.数据的物理结构是数据在计算机中实际的存储形式。

7.算法和程序没有区别，所以在数据结构中二者是通用的。

8.顺序存储结构属于静态结构，链式存储结构属于动态结构。

四、计算应用题

1、设n为正正数。确定下列各程序段中前置以记号@的语句的频度。

（1）I=l;k=0;

While(I<n-l)

@{k+=10*I;

1++；}

k=0;

for(I=l;I<=n;I++)

{for(j=I；j<=n;j++)

@k++;}

(2)I=l；j=O;

While(I+j<=n)

@{if(I>j)j++;

else1++;}

2、写出下面算法中带标号语句的频度。

Voidperm(inta[],k,n)

{intxj;

(1)if(k==n)

(2)for(I=1;I<=n;I++)

(3)printf("％d”,a[I]);

else

{(4)for(I=k;I<=n;I++)

(5)a[I]+=I*I;

(6)perm(a,k+l,n);}}

执行函数调用语句perm(a,l,n)

3、指出下列两个算法的时间复杂度。

(1)intsum1(intn)

{intp=l,sum=0,I;

for(I=1;I<=n;I++){p*=I;sum+=p;}

return(sum);}

(2)intsum2(intn)

{intsum=0,I,j;

for(I=l;I<=n;I++){p=1;for(j=1;j<=I;j++)p*=j;

sum+=p;}

returm(sum);}

4、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。

(1)A=(K,R),其中:K={a,b,c,d,e,f,g,h}R=(r)

r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}

(2)B=(K,R)淇中:K={a,b,c,d,e,f,g,h}R=(r)r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}

(3)C=(K,R),其中：k={1,2,345,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

(4)D=(K.R),K={48,25,64,57,82,36,75),R={rl,r2}

rl={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}

r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<84,75>}

5、设有如图所示的逻辑结构图，给出它的逻辑结构。

KI

6、简述下列术语：数据，数据元素，数据结构，数据对象。

7、逻辑结构与存储结构是什么关系？

2n2）

8、将数量级n,n,n\nlog2n,log2n,2,品,n!,（2/3）",n\按增长率进行排列。

五、算法设计题

1.已知输入x,y,z三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，并考虑所用算法的比

较次数和元素移动次数。

2.编写在输入10个数中找出最小或最大的数的算法。

3.在数组A[n]中查找值为k的元素，若找到则输出其位置i（lWiWn）,否则输出0作为标志。设计求解此问题

的类C语言算法，并分析其最坏情况时间复杂度。

第二章线性表练习题

一、选择题

1、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的

平均次数为（），删除一个元素需要移动的元素个数为（）。

A.（N-l）/2B.NC.N+lD.N-lE.N/2F.（N+l）/2G（N-2）/2

2、线性表是具有N个（）的有限序列。

A、表元素B、字符C、数据元素D、数据项E、信息

3、”线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（）。

A、正确的B、错误的C、不一定，与具体结构有关。

4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（）o

A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5、带头结点的单链表为空的判定条件是（）。

A、head==NULLB、head->next==NULLC>head->next==headD、head!=NULL

6、不带头结点的单链表head为空的判定条件是（）。

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL

7、非空的循环单链表head的尾结点P满足（）。

A、P->NEXT=NULLB、p=NULLC>p->next==headD^p=head

8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

A、0（1）B、0（n）C、0（n2）D、O（nlog2n）

9、在一个单链表中，若删除P所指结点的后继结点，则执行（）。

A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;

10、在一个单链表中，若在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;

11、在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s,则执行（）。

A、s-next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、

p->next=s;s->next=q;

12、假设双链表结点的类型如下：

typedefstructlinknode{

intdata;//数据域

structlinknode*llink;//指向前趋结点的指针域

structlinknode*rlink;//指向后继结点的指针域

}bnode

现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能iE确完成此要

求的语句段是（）。

A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;

B、p->Ilink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink

C、q->llink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q;

D、以上都不对

13、如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（）o

A、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;

B、p->rlink->s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink;

C、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s;

D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;

14、在一个长度为n的单链表上，设有头和尾两个指针，执行（）操作与链表的长度无关。

A、删除单链表中的第一个元素B、删除单链表中最后一个元素C、在单链表第一个元素前插入一个

新元素D、在单链表最后•个元素后插入一个新元素

15、线性结构中的一个结点代表一个（）

A、数据元素B、数据项C、数据D、数据结构

16、非空线性表L=（ai,a2,…,a，…,an）,下列说法正确的是（）

A、每个元素都有一个直接前驱和直接后继

B、线性表中至少要有一个元素

C、表中诸元素的排列顺序必须是由小到大或由大到小的

D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继

17、顺序表是线性表的（）

A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构

18、对于顺序表，以下说法错误的是（）

A、顺序表是用--维数组实现的线性表，数组的下标可以看成是元素的绝对地址

B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作。

A、插入操作B、结点移动C、算术表达式D、删除操作

20、对于顺序表的优缺点，以下说法错误的是（）

A、无需为表示结点间的逻辑关系而增加额外的存储空间

B、可以方便地随机存取表中的任一结点

C、插入和删除运算较方便

D、山于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）

21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节

省时间。

A、顺序表B、单链表C、双链表D、单循环链表

22、循环链表主要优点是（）

A、不再需要头指针了

B、已知某个结点的位置后，能够容易找到它的直接前趋

C、在进行插入、删除运算时，能更好地保证链表不断开

D、从表中任一结点出发都能扫描到整个链表

23、在线性表的下列存储结构中，读取元素花费时间最少的是（）

A、单链表B、双链表C、循环链表D、顺序表

二、填空题

1、在线性结构中，第一个结点（）前趋结点，其余每个结点有且只有（）个前趋结点。

2、在顺序表中插入或删除一个元素，需要平均移动（）元素，具体移动的元素个数与（）有关•

3、已知L是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：

（1）表首插入S结点的语句序列是（）。

（2）表尾插入S结点的语句序列是（）。

A、P->next=S;B、P=L;C、L=S;D、P->next=S->next;E、S->next=P->next;F、S->next=L;G、

S->next=NULL;H、while（P->next!=Q）p=p->next;I、while（P->nexl!=NULL）P=P->next;

4、已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。

（1）删除首元结点的语句序列是（），（2）删除尾元结点的语句序列是（）

A、P=P->next;B、P->next=P->next->next;

C、while（P!=NULL）p=p->next;

D、while（Q->next!=NULL）{P=Q;Q=Q->next;}

E^while（P->next!=Q）P=P->next;

F、Q=P;G^Q=P->next;H、P=L;I、L=L->next;

J、free（Q）;

5、已知L是带表头结点的非空链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中

选择合适的语句序列。（1）删除P结点的直接后继结点的语句序列是（），（2）删除P结点的

直接前趋结点的语句序列是（）

A、P->next=P->next->next;B、P=P->Pnext->next;

C、while（P->next!=Q）P=P->next;

D、while（P->next->next=Q）P=P->next;E、Q=P;

F、Q=P->next;G、P=L;

H、L=L->next;I、free（Q）;

6、已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问（）

个结点，从n个结点的双链表中查找一个结点，平均要访问（）个结点。

7、对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（）；在值域

为给定值的结点后插入一个新结点的时间复杂度是（）。

8、单链表是（）的链接存储表示。

9、单链表中设置头结点的作用是()。

10、在单链表中，除首元结点外，任一结点的存储位置由()指示。

11、在非空双向循环链表中，在结点q的前面插入结点p的过程如下：

p->prior=q->prior;q->prior->next=p;p->next=q;();

12、在双向链表中，每个结点有两个指针域，一个指向(),另一个指向()。

13、顺序表中逻辑上相邻的元素的物理位置()相邻。单链表中逻辑上相邻的元素的物理位置()

相邻。

14、为了便于讨论，有时将含n(n20)个结点的线性结构表示成(a“a?,…,aj,其中每个去代表一个。

ai称为结点,a"称为结点,i称为由在线性表中的。对任意一对相邻结点ai、a+i(lWi<n),ai

称为ai+i的直接，ai+i称为4的直接。

15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接外，其他结点有且仅有一

个直接;除终端结点没有直接外，其它结点有且仅有一个直接.

16、所有结点按1对1的邻接关系构成的整体就是结构。

17、线性表的逻辑结构是结构。其所含结点的个数称为线性表的o

18、在单链表中，指针p所指结点为最后••个结点的条件是o

三、判断题

1.顺序存储的线性表可以随机存取。

2.顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要

移动。

3.线性表中的元素可以是各种各样的，但同•线性表中的数据元素具有相同的特性，因此是属于同•数据

对象。

4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。

5.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

6.在单链表中，可以从头结点进行查找任何一个元素。

7.线性表的链式存储结构优于顺序存储结构。

8.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。

9.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

10.顺序存储方式只能用于存储线性结构。

四、简答题

1、若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？

2、描述概念：头指针、头结点、首元结点的区别？

3、设A是一个线性表(aia2...an),采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需

要移动的元素个数为多少？若元素插在为与ai+i之间(0<=k=n-l)的概率为2(n-i)/(n(n+l)),则平均

每插入一个元素所要移动的元素个数又是多少？

4、为什么在单循环链表中设置尾指针比设置头指针更好？

5、双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的链

表中删除？若可以，其时间复杂度各为多少？

6、下列算法的功能是什么？

LinkedListtestl(LinkedListL)

{//L是无头结点的单链表

ListNode*q,*p;

if(L&&L->next)

{q=L;L=L->next;p=L;

while(p->next)p=p->next;

p->next=q;q->next=NULL;

)

returnL;

)

7、如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会

自动地改变。在此情况下，应选择哪一种存储结构。为什么？

8、若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应

该用哪种存储结构。为什么？

9、设有多项式a(x)=9+8x+9x4+5xi°

b(x)=-2x+22x7-5x10

(1)用单链表给出a(x)、b(x)的存储表示；

(2)设c(x)=a(x)+b(x),求得c(x)并用单链表给出其存储表示。

五、设计题

1、编写一个函数将一个顺序表A(有多个元素且任何元素不为0)分拆成两个顺序表，使A中大于0

的元素存放在B中，小于0的元素存放在C中。

2、设顺序表L中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表

的有序性。

3、A、B为元素递增有序排列的单链表(同一表中可能有相同元素)，编写算法另建一单链表C,保存

两个表的公共元素，要求C的元素值各不相同且递增有序。

4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：

(1)找出最小值结点，且显示该数值。

(2)若该数值为奇数，则将其与直接后继结点的数值交换。

(3)若为偶数，则将其直接后继结点删除。

六、编程附加题

1.试分别用顺序表和单链表作为存储结构，实现将线性表(a0,ai,a2,.…a.)就地逆置的操作，所谓“就地”

指辅助空间为O(Do

2.设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个有序

表。

3.设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。

4.试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。

5.设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式

存储将A和B归并成一个仍按元素值递增有序的线性表C,请分析算法的时间复杂度。

6.设指针la和1b分别指向两个无头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，

并将这些元素插入到1b中第j个结点之前的算法。

7.单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样

的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。请分析你的时间复杂度。

8.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B,其头结点指针分别为pa和

pb,使得A链表中含有链表A中的序号为奇数的元素，而B链表中含有原链表A中的序号为偶数的元

素，且保持原来的相对顺序。

9.假设以两个元素依值递增有序排列的线性表A,B分别表示两个集合，先要求另辟空间构造一个线性表

C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。

10.设有线性表A=(ai,a2,...所)和B=(bi,b2,..息)。试写合并A、B为线性表C的算法,使得:

c=f(«i,am,b,„,bm+x,b.)寺m<n\

l(q,伍an,bn,an+}当m>n;

线性表A,B和C均以单链表作存储结构，且C表利用A表和B表的结点空间。

11.假设在长度大于1的单循环链表中，既无头结点也无头指针。S为指向链表中某个结点的指针，试编写

算法删除结点*s的直接前驱结点。

12.计算带头结点的循环链表的结点个数。

13.已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试

编写算法构造三个以循环链表表示的线性表使得每个表中只含有同一类的字符，且利用原表中的结点空

间作为这三个表的结点空间，头结点可另辟空间。

14.已知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C

表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度(注：题中没特

别指明同一表中的元素值各不相同)。

15.双向循环链表中，设计满足下列条件的算法。

(1)在值为x的结点之前插入值为y的结点。

(2)删除值为x的结点。

16.设有一个循环双链表，其中有一结点的指针为P,编写算法将P与其右边的一个结点进行交换。

17.设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq,在链表被

起用之前，其值均初始为0。每当链表进行一次LocateNode(L,x)运算时令元素值为x的结点中freq

域的值加1,并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠

近表头。试写一符合上述要求的LocateNode的运算的算法。

18.给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。

19.根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。

20.(Josephus环)任给正整数n、k,按下述方法可得排列1,2,n的一个置换:将数字1,2,n

环形排列，按顺时针方向从1开始计数；计满K时输出该位置上的数字(并从环中删去该数字)，然后从

下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3,6,

9,2,7,1,8,5,10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述

问题。

21已知在一维数组A[l..m+n]中依次存放着两个向量(a,,a2”…am)和(也加，….bn),编写算法将两个向量的

位置互换，即把(bi,b2.....bn)放到(ai,a2......am)之前。

22给定•个不带头结点的单链表，编写计算此链表长度的算法。

23设ha和hh分别是两个带头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链

表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储

空间。表中允许有重复的数据。

24设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：

(I)找出最小值结点，且打印该数值；

(2)若该数值是奇数，则将其与直接后继结点的数值交换；

(3)若该数值是偶数，则将其直接后继结点删除；

25利用顺序表的操作，实现以下的函数。

(1)从顺序表中删除具有最小值的元素并由函数返回被删元素的值，空出的位置由最后一个元素填补。

(2)从顺序表中删除具有给定值x的所有元素。

(3)从有序顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素。

26如果以单链表表示集合，设计算法建立先后输入的两个集合的差。

27已知一个线性表中的元素按元素值非递减有序排列，分别以顺序存储和链式存储编写一个算法删除表中

多余的值相同的元素。

28设A=(aba2,a3，……a“)和B=(bhb2%)是两个顺序表(假定所含数据元素均为整数)。若n=m且

ai=bi（i=l,...,n）厕称A=B;若ai=bi（i=l,...,j）且aj+《bj+i（jcnWm）,则称A<B;在其他情况下均称A>B。是编写一

个比较A和B的算法，当A<B,A=B或A>B是分别输出-1,0或者1。

29已知一个循环单链表如图2.1所示，编写一个算法将所有箭头方向取反。

head

图2.1

30假设有一个单循环链表，其结点含有三个域：prior,data,和next。其中data为数据域，next指向后继结

点，prior为指针域，它的值为空指针，试编写算法将此表改为双向循环链表。

31设A是一个双向循环链表，其表中元素递增有序。试写一算法插入一个元素x,使表A中的元素依然递

增有序。

32写出将双向循环链表倒置的算法。

33设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次幕

或偶次第项，并要求利用原链表中的结点空间来构造这两个链表。

34设以带头结点的双向链表表示的线性表L=（a,,a2,...,an）,试写一时间复杂度为0（n）的算法，将L改造为

L=（ai,a3”..,an,a4,a2）。

35设一单向链表的头指针为head,链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录

按照key递增的顺序进行就地排序。

第三章栈与队列练习题

一、选择题

1、栈结构通常采用的两种存储结构是（）。

A、顺序存储结构和链表存储结构B、散列和索引方式C、链表存储结构和数组D、线性链表

结构和非线性存储结构

2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（）

A^ST.top-ST.baseoOST.top-ST.base==0C、ST.top-ST.baseonD、ST.top-ST.base==n

3、向一个栈顶指针为HS的链栈中插入一个s结点时，则执行（）

A^HS->next=s;s->next=HS->next;HS->next=s;C、s->next=HS;HS=s;D、s->next=HS;HS=HS->next;

4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（）

A、x=HS;HS=HS->next;B、HS=HS->next;x=HS->data;C、x=HS->data;HS=HS->next;D、

s->next=Hs;Hs=HS->next;

5^表达式a*（b+c）-d的后缀表达式为（）

A、abcdd+-B、abc+*d-C、abc*+d-D、-+*abcd

6、中缀表达式A-（B+C/D）*E的后缀形式是（）

A、AB-C+D/E*B、ABC+D/E*C、ABCD/E*+-D、ABCD/+E*-

7、一个队列的入列序列是1,2,3,4,则队列的输出序列是（）

A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,1

8、循环队列SQ采用数组空间SQ.base[0,n-l]存放其元素值，已知其头尾指针分别是front和rear,则判定此

循环队列为空的条件是（）

A^Q.rear-Q.front==nB、Q.rear-Q.front-1==nC、Q.front==Q.rearD、Q.front==Q.rear+1

9、循环队列SQ采用数组空间SQ.base[0,n-l]存放其元素值，己知其头尾指针分别是front和rear,则判定此

循环队列为满的条件是（）

A^Q.front==Q.rearB、Q.front!=Q.rearC>Q.front==（Q.rear+1）%nD^Q.front!=（Q.rear+l）%n

10、若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3,当从队列中删除一个

元素，再加入两个元素后，rear和front的值分别为（）

A、1,5B、2,4C、4,2D、5,1

11、用单链表表示的链式队列的队头在链表的（）位置

A、链头B、链尾C、链中

12、判定一个链队列Q（最多元素为n个）为空的条件是（）

A^Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==（Q.rear+l）%nD^Q.front!=（Q.rear+l）%n

13、在链队列Q中，插入s所指结点需顺序执行的指令是（）

A、Q.front->next=s;f=s;B、Q.rear->next=s;Q.rear=s;C、s->next=Q.rear;Q.rear=s;D、

s->next=Q.front;Q.front=s;

14、在一个链队列Q中，删除一个结点需要执行的指令是（）

A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、

Q.front=Q.rear->next;

15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操

作时（）

A、仅修改队头指针B、仅修改队尾指针C、队头尾指针都要修改D、队头尾指针都可能要修改。

16、栈和队列的共同点是（）

A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点

17、消除递归（）需要使用栈。

A、一定B、不一定

18、设有一顺序栈S,元素设,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,sl,则栈的

容量至少应该是（）

A、2B、3C、5D、6

19、若一个栈的输入序列是a,b,c,则通过入、出栈操作可能得到a,b,c的不同排列个数为（）

A、4B、5C、6D、7

20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（）

A、a3,al,a4,a2B、a3,a2,a4,alC、a3,a4,a2,alD、a4,a3,a2,al

0maxsize-1

ala2a3

丁

Top

图3.1

21、链栈和顺序栈相比，有一个比较明显的优势是（）

A、通常不会出现栈满的情况B、通常不会出现栈空的情况

C、插入操作更容易实现D、删除操作更加容易实现

22、若一个栈的输入序列是1,2,3,4,…,n,输出序列的第一个元素是n,则第i个输出元素是（）

A、不确定B、n-iC、n-i+1D、n-i-1

23、以下说法正确的是（）

A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况

B、因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况

C、对于链栈而言，在栈满状态下，如果此忖再作进栈运算，则会发生“上溢”

D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。

二、判断题

1、在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。

2、链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。

3、若一个栈的输入序列为1,2,3,…，n,其输出序列的第一个元素为n,则其输出序列的每个元素

比一定满足ai=i+l(i=l,2,…,n)。

4、在链队列中，即使不设置尾指针也能进行入队操作。

5、在对链队列(带头指针)做出队操作时，不会改变front指针的值。

6、循环队列中元素个数为rear-fronto

7、一个栈的输入序列是123,4,则在栈的输出序列中可以得到4,3,1,2。

8、一个栈的输入序列是123,4,则在栈的输出序列中可以得到1,2,3,4。

9、若以链表作为栈的存储结构，则进栈需要判断栈是否满。

10、若以链表作为栈的存储结构，则出栈需要判断栈是否空。

三、填空题

1、栈的特点是()，队列的特点是()。

2、线性表、栈、队列都是()结构，可以在线性表的()位置插入和删除元素；对于栈只能在()

插入和删除元素；对于队列只能在()插入元素和在()位置删除元素。

3、有程序如下，则此程序的输出结果(栈的元素类型是SelemType为char)是()。

Voidmain()

{stacks;charx,y;initstack(s);x='c';y='k';

push(s,x);push(s,'a');push(s,y);

pop(s,x);push(s,,t,);push(s,x);pop(s,x)；push(s,,s,);

while(istackemply(s)){pop(s,y);printf(y);}

printf(x);}

4、在栈顶指针为HS的链栈中，判定栈空的条件是()。

5、向栈中压入元素的操作是先()后()。

6、对栈进行退栈操作是先()后()。

7、用循环链表表示的队列长度为n,若只设头指针，则出队和入队的时间复杂度分别是()和()；

若只设尾指针，则出队和入队的时间复杂度分别是()和()。

8、从循环队列中删除一个元素时，其操作是()。

9、在一个循环队列中，队首指针指向队首元素的()。

10、在具有n个单元的循环队列中，队满时共有()个元素。

11、在HQ的链队列中，判断只有一个结点的条件是()。

12、设栈S和队列Q的出始状态为空，元素2力,3<1©1?依次通过栈5,一个元素出栈后即进入队列Q。若这6

个元素出队列的顺序是b,d,c,f,e,a则栈S的容量至少应该是()。

13、有程序如下，则此程序的输出结果(队列的元素类型是QSelemType为char)是()。

Voidmain()

{charx=，e',y='c';

enqueue(q,'h');enqueue(q,T);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);

enqueue(q,'a');

while(!queueempty(q)){dequeue(q,y);printf(y);)

printf(x);}

14、有如下递归函数：

intdunno(intm)

(intvalue;if(m==0)value=3;

elsevalue=dunno(m-l)+5;

return(value);}

执行语句printf("％d\n”,dunno(3));的结果是()。

四、简答题

1、对于堆栈，给出三个输入项A,B,C,如果输入项序列为ABC,试给出全部可能的输出序列，并写

出每种序列对应的操作。例如：A进B进C进C出B出A出，产生的序列为CBA。

2、简述以下算法的功能(栈的元素类型是SelemType为int)。

(1)statusalgo1(stacks)

{intI,n,a[255];n=0;while(!stackempty(s)){n++;pop(s,a[n]);}

for(I=1;I<=n;I++)push(s,a[I]);}

(2)statusalgo2(stacks,inte)

{stackt;intd;initstack(t);while(!stackempty(s)){pop(s,d);if(d!=e)push(t,d);)

while(!stackempty(t)){pop(t,d);push(s,d);}}

3、内存中•片连续空间(不妨假设地址从0到m-l)提供给两个栈si和s2使用，怎样分配这部分存储

空间，使得对任一栈仅当这部分空间全满时才发生溢出。

4、有递归过程如下：

voidprint(intw){intI;if(w!=O){print(w-l)

for(I=1;k=w;I++)printf("％3d”,w);printf("\n");}}

问：调用语句print(4)的结果是什么？

5、简述以下算法的功能(栈和队列的元素类型均为int)

voidalgo(queue&q)

{stacks;intd;initstack(s);

while(!