《计算机软件技术基础》课后题答案 - 图文

更新时间：2024-04-17 08:19:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

计算机软件技术基础李平第二版课后答案推荐度：
相关推荐

数据结构习题答案第一节概论一、选择题

1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。 A．数据元素具有同一的特点 *B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等

2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。

(1) A．操作对象 B．计算方法 *C．物理存储 D．数据映像 (2) A．结构 *B．关系 C．运算 D．算法

3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。

(1) A．算法 *B．数据元素 C．数据操作 D．逻辑结构 (2)A．操作 B．映像 C．存储 *D．关系 4．在数据结构中，从逻辑上可以把数据结构分为( )。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构 *C．线性结构和非线性结构 D．内部结构和外部结构

5．线性表的顺序存储结构是一种( )的存储结构。

*A．随机存取 B．顺序存取 C．索引存取 D．Hash存取 6．算法分析的目的是( )。

A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 *C．分析算法的效率以求改进 D．分析算法的易懂性和文档性

7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。

(1) A．计算方法 B．排序方法 *C．解决某一问题的有限运算序列 D．调度方法

(2) A．可行性、可移植性和可扩充性 *B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性

8．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。 A．必须是连续的 B．部分必须是连续的 C．一定是不连续的 *D．连续不连续都可以

9．在以下的叙述中，正确的是( )。

A．线性表的线性存储结构优于链式存储结构 *B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出

10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。

*A．集合中任何两个结点之间都有逻辑关系但组织形式松散 B．线性结构中结点按逻辑关系依次排列形成一条“锁链” C．树形结构具有分支、层次特性，其形态有点像自然界中的树 D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 11．以下说法正确的是( )。

A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 *D．数据结构是带有结构的数据元素的集合二、判断题

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

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

√3．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。

╳4．数据项是数据的基本单位。

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

√6．数据的物理结构是数据在计算机中实际的存储形式。 ╳7．算法和程序没有区别，所以在数据结构中二者是通用的。 √8．顺序存储结构属于静态结构，链式存储结构属于动态结构。三、填空题

1．所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____。 2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___。 3．数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型。

4．在线性结构中，开始结点__没有_前驱结点，其余每个结点有且只有__一个_个前驱结点。

5．在树形结构中，根结点只有___一个___，其余每个结点有且只有___一个___前驱结点；叶结点没有___后继__结点，其余每个结点的后继结点可以有__任意个__·

6．在图形结构中，每个结点的前驱结点和后继结点可以有___任意个___。 7．算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出__。

8．下列程序段的时间复杂度是__O（n）___。 for (i=1；i<=n；i++) A[i，i]=0；

9．下列程序段的时间复杂度是__ O（n）___。 S=0；

for(i=1；i<=n；i++)

for(j=1；j<=n；j++) s=s+B[i,j]； sum=s；

10．存储结构是逻辑结构的___物理__实现。

11．从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即__数据__、__数据元素_和__数据项___。

12．根据需要，数据元素又被称为__结点__、__记录__、___元素__或__顶点_。 13．通常，存储结点之间可以有___顺序存储__、____链式存储__、____索引存储__、___散列存储_四种关联方式，称为四种基本存储方式。

14．通常从___确定性___、__可读性_、___健壮性__、_高效性__等几方面评价算法(包括程序)的质量。

15．一个算法的时空性能是指该算法的_时间复杂度___和___空间复杂度_，前者是算法包含的__计算量__，后者是算法需要的___存储量__。 16．在一般情况下，一个算法的时间复杂度是__问题规模__的函数。 17．常见时间复杂度的量级有：常数阶O(__1_)、对数阶O(__log2n___)、线性阶O(__n__)、平方阶O(_n_)和指数阶O(__2_)。通常认为，具有指数阶量级的算法是__不可行__的。

18．数据结构的基本任务是数据结构的__设计__和__实现__。 19．数据对象是性质相同的__数据元素_的集合。

20．抽象数据类型是指一个__数学模型__以及定义在该模型上的一组操作。四、应用题

1．分析下列程序段的时间复杂度。

?? i=1；

WHILE (i<=n) i=i*2； ?? 答：O(log2n)

2．叙述算法的定义及其重要特性。

答：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。

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

答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。

4．逻辑结构与存储结构是什么关系？

答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。 5．将数量级2，n，n，n，nlog2n，log2n，2，n!，(2／3)，n行排列。

答：(2／3)，2，log2n，n

2／3

按增长率进

，n，nlog2n，n，n，2，n!

23n

6．设有数据逻辑结构为：D={k1，k2，k3，?，k9}，R={，，，，，，，，，

}，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

答：图略。开始结点k1、k2，终端结点k6、k7。

7．设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。

答：数据逻辑结构为：D={k1，k2，k3，?，k8}，R={，，，，，，}，其逻辑结构类型为树型结构。

8．分析下列程序的时间复杂度(设n为正整数)。 (1)int rec(int n)

{if(n==1)return(1)； else return(n*rec(n-1))； } (2)x=91；y=100；

While (y>0) if(x>10) y--； (3)i=1；j=0； while(i+j<=n)

if(i>j)j++； else i++; (4)x=n；y=0；

while(x>=(y+1)*(y+1)) y++；

答：(1) O(n) (2) O(1) (3) O(n) (4) O(n)

1/2

9．设n为正数。试确定下列各程序段中前面加记号@的语句的频度： (1)i=1；k=0；

while(i<=n-1) {@k+=10*i； i++； ) (2) k=0；

for(i=1；i<=n；i++)

for(j=i；j<=n：j++) @k++；答：(1)n-1 (2)n+(n-1)+??+1=n(n+1)/2

第二节线性表一、选择题

1．线性结构中的一个结点代表一个( )。

*A．数据元素 B．数据项 C．数据 D．数据结构

2．线性表L=(a1，a2，?，ai，?，an)，下列说法正确的是( )。

A．每个元素都有一个直接前驱和直接后继 B．线性表中至少要有一个元素 C．表中诸元素的排列顺序必须是由小到大或由大到小的 D．*除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 3．顺序表是线性表的( )。

A．链式存储结构 *B．顺序存储结构 C．索引存储结构 D．散列存储结构 4．对于顺序表，以下说法错误的是( )。

* A．顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B．顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C．顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻 D．顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中 5．对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操

作。

A．条件判断 *B．结点移动 C．算术表达式 D．赋值语句 6．对于顺序表的优缺点，以下说法错误的是( )。

A．无需为表示结点间的逻辑关系而增加额外的存储空间 B．可以方便地随机存取表中的任一结点 *C．插入和删除操作较方便 D．由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)

7．在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为( )。

A．n *B．n/2 C．(n-1)/2 D．(n+1)/2

8．在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为( )。

A．n B．n/2 *C．(n-1)/2 D．(n+1)/2 9．带头结点的单链表为空的条件是( )。

A．head=NULL *B．head->next=NULL C．head->next=head D．head!=NULL 10．非空单循环链表head的尾结点*p满足( )。

A．p->next=NULL B．p=NULL *C．p->next=head D．p=head 11．在双循环链表的*p结点之后插入*s结点的操作是( )。

A．p->next=s；s->prior=p；p->next->prior=s；s->next=p->next； B．p->next=s；p->next->prior=s；s->prior=p：s->next=p->next； C．s->prior=p；s->next=p->next；p->next=s；p->next->prior=s； *D．s->prior=p；s->next=p->next；p->next->pror=s；p->next=s； 12. 在一个单链表中，已知*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；

13. 在一个单链表中，若*p结点不是最后结点。在*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;

14. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用( )存储方式最节省时间。

*A．顺序表 B. 单链表 C．双链表 D．单循环链表

15．设rear是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为( )。

A．p=rear；rear=rear->next； free(p) B．rear=rear->next；free(rear)； C．rear=rear->next->next； free(rear)； *D．p=rear->next->next；rear->next->next=p->next；free(p)； 16．在一个单链表中，若删除*p结点的后继结点，则执行( )。

*A．q=p->next；p->next=q->next；free(q)； B．p=p->next；p->next=p->next->next；free(p)； C．p->next=p->next；free(p->next)； D．p=p->next->next；free(p->next)；

17．设指针p指向双链表的某一结点，则双链表结构的对称性可用( )式来刻画。 AB*C

．．．

p->prior->next->==p->next->next p->prior->prior==p->next->prior p->prior->next->==p->next->prior

D．p->next->next==p->prior->prior

18．在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储

位置分别是( )。 A．rear

和

rear->next->next *B．rear->next

和

rear

C．rear->next->next和rear D．rear和rear->next 19．循环链表的主要优点是( )。

A．不再需要头指针了 B．已知某个结点的位置后，容易找到它的直接前驱 C．在进行插入、删除操作时，能更好地保证链表不断开 *D．从表中任一结点出发都能扫描到整个链表

20．在线性表的下列存储结构中，读取元素花费时间最少的是( )。 A．单链表 B．双链表 C．循环链表 *D．顺序表二、判断题

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

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

√3．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

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

√5．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 √6．在单链表中，可以从头结点开始查找任何一个元素。 ╳7．线性表的链式存储结构优于顺序存储结构。

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

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

╳10．顺序存储方式只能用于存储线性结构。三、填空题

1．为了便于讨论，有时将含n(n>0)个结点的线性结构表示成(a1，a2，?，an)，其中每个ai代表一个__结点_。a1称为_第一个_结点，an称为__最后一个_结点，i称为ai在线性表中的_位置__。对任意一对相邻结点ai、ai+1(1≤i

2．线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接__前驱_外，其他结点有且仅有一个直接__前驱_；除终端结点没有直接__后继_外，其他结点有且仅有一个直接_后继__。

3．所有结点按一对一的邻接关系构成的整体就是__线性__结构。

4．线性表的逻辑结构是__线性_结构，其所含结点的个数称为线性表的___长度_。

5．在单链表中，删除p所指结点的直接后继的操作是__ q=p->next；p->next=q->next；free(q)；___·

6．非空的单循环链表head的尾结点(由指针p所指)满足__ p->next= head _____。

7．rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为__ p=rear->next；q=p->next；p->next=q->next；free(q)；____。 8．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为__O(1)__，在给定值为x的结点后插入新结点的时间复杂度为__ O(n)__。 9．单链表表示法的基本思想是用___指针___表示结点间的逻辑关系。 10．在顺序表中插入或删除一个元素，平均需要移动_一半_元素，具体移动的元素个数与__元素的位置_有关。

11．在一个长度为n的向量的第i(1≤i≤n+1)个元素之前插入一个元素时，需

向后移动___ n-i+1__个元素。

12．在一个长度为n的向量中删除第i(1≤i≤n)个元素时，需向前移动__ n-i __个元素。

13．在双链表中，每个结点有两个指针域，一个指向___前驱__，另一个指向___后继___。

14．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=__ p->next->next ；___。

15．设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成__单循环链表___。

16．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是_删除__s指向的结点。

17．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___s->next= r->next __；r->next=s；r=s； 18．在单链表中，指针p所指结点为最后一个结点的条件是__ p->next=NULL___。 19．在双循环链表中，若要在指p所指结点前插入s所指的结点，则需执行下列语句：s->next=p； s->prior=p->prior；__ p->prior->next __=s；p->prior=s；

20．在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作： s->next=___ p->next __； p->next=s； temp=p->data； p->data=__ s->data ___； s->data=__ temp _；四、应用题

1．描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向

链表中的第一个结点的指针。

2．何时选用顺序表，何时选用链表作为线性表的存储结构为宜？

答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。

3．在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？

答：平均移动表中大约一半的结点，插入操作平均移动n/2 个结点，删除操作平均移动（n-1）/2 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。

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

答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O(1)时间内完成，同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。

5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？若可以，其时间复杂度各为多少？答：能删除。双链表上删除p所指向的结点的时间复杂度为O(1)，单循环链表上删除p所指向的结点的时间复杂度为O(n)。 6．下列算法的功能是什么？ LinkList *testl(LinkList *L)

{//L是无头结点的单链表 LinkList *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；} return L；}

答：如果长度大于1，则将首元结点删除并插入到表尾。

7．如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？

答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。

8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？

答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。五、算法设计题

假设算法中用到的顺序表和链表结构如下： #define maxsize 100;

Typedef struct node1 {datatype data[maxsize]; int length } SeqList; Typedef struct node2 {datatype data; struct node2 *next } LinkedList ; 1．试用顺序表作为存储结构，实现将线性表(a0，a1，a2，?an-1)就地逆置的

操作，所谓“就地”是指辅助空间为O(1)。答：(1)顺序表的就地逆置

分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。

void Seqreverse(SeqList *L){／／顺序表的就地逆置 for(i=0；j=L->length-1；i

{t=L->data[i]; L->data[i]=L.data[j]; L->data[j]=t; } } (2)链表的就地逆置

分析：本算法的思想是逐个地把L的当前元素r插入到新的链表头部。 void Linkedreverse(LinkedList *L){／／链表的就地逆置 p=L->next；L->next=NULL； while(p!=NULL)

{r=p，p=p->next；／／r指向当前待逆置的结点，p记下下—个结点 r->next=L—>next；L->next=r；／／放到表头 } }

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

答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将x插入到其位置上，同时顺序表长度增1。

void SeqListinsert(SeqList *L，int x){／／x插入到递增有序的顺序表L中 i=0;

while((i<=L->length-1)&&(x>=L->data[i])) i++；／／找正确的插入位置

for(k=L->length-1;k>=i；k--) ／／元素从后往前依次后移 L->data[k+1]=L->data[k]；

L->data[i]=x；／／x插入到正确位置 L->length++； )

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

答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。

void LinkListinsert(LinkedList *L，int x){／／x插入有序链表L中 q=L；p=q—>next；

while(p!=NULL&&p—>data>x) ／／找到插入的位置 {q=p；p=p—>next； }

s=(LinkedList*)malloc(sizeof(LinkedList))；／／生成新结点 S—>data=x； S—>next=p； q—>next=s； }

4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。

void LinkedListlnsert(LinkedList *L，int x，int i) {／／不带头结点的单链表的第i个元素之前插入一个元素 p=L：j=1;

while(p!=NULL&&jnext；j++；}

if(i<=0||p==NULL) printf(”插入位置不正确＼n”)；

else {q=(LinkedList*)malloc(sizeof(LinkedList))；q—>data=x； if(i==1) {q—>next=L；L=q；} ／／在第一个元素之前插入 else{q—>next=p—>next；p—>next=q；} ／／在其他位置插入 } }

5．设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。

答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。

SeqList *Seqmerge(SeqList A，SeqList B，SeqList *C){／／有序顺序表A和B归并成有序顺序表C

i=0；j=0；k=0；／／i，i，k分别为顺序表A，B，C的下标 while(i

{if(A.data[i]data[k]=A.data[il；i++； ]

else {C->data[k]=B.data[j];j++；} ／／B中当前元素较小 k++； }

if (i==m) for(t=j；tdata[k]=B.data[t];k++；} ／／B表长度大于A表

else for(t=i；tdata[k]=A.data[t]；k++；} ／／A表长度大于B表

C->length=m+n； return C;} (2)

VOid Linkmerge(LinkedList *A，LinkedList *B，LinkedList *C) {／／有序链表A和B归并成有序链表C pa=A—>next；pb=B—>next；C=A；pc=C； while(pa&&pb) ／／A和B都不为空时

{if(pa—>datadata) ／／A当前结点值较小

{qa=pa->next； pC->next=pa； pc=pc->next； pa=qa；}

else {qb=pb->next；pc->next=pb：pc=pc->next；pb=qb；} ／／B当前结点值较小 }

if(pa)pc—>next=pa；／／A没有结束，将A表剩余元素链接到C表 if(pb)pc—>next=pb；／／B没有结束，将B表剩余元素链接到C表 free(B)；／／释放B表的头结点 }

本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。

6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。

答：分析：先在la中找到第i个结点，分别用两个指针pre和p指向第i-1和第i个结点，然后用指针q从第i个结点起向后走len个元素，使q指向此位置。然后在lb中找到第j个结点，将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。

void Deletelnsert(LinkedList *la，LinkedList *lb，int i，int j, int len)

{／／删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素

插入到单链表lb中第j个结点之前 if(i<0||j<0||len<0) exit(0)； p=la；k=1；pre=NULL；

while(p&&knext; k++； } if(!p) exit(0)；

q=p；k=l；／／p指向la表中第i个结点

while(q&&knext； k++；} ／／查找la表中第i+len-1个结点

if(!q) exit(0)；

if(pre==la) la=q—>next；／／i=1的情况 else pre—>next=q—>next；／／完成删除／／将从la中删除的结点插入到lb中

if(j==1) {q->next=lb； lb=p； } ／／j=1时 else { r=lb; k=1；／／j>1时

while(r&&knext； k++；} ／／查找Lb表中第i—1个元素

if(!r) exit(0)；

q—>next=r—>next；r—>next=p；／／完成插入 } }

7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。

答：LinkedList delete(LinkedList *L，int min，int max)

{／／删除递减有序单链表L中值大于min且小于max的结点 q=L；

if(min>max) {printf(”min>max＼n”)；exit(0)；} else p=L—>next；／／q始终指向p的前驱

while(p—>data>=max) ／／当前元素大于或等于max，则p、q依次向后移动

{q=p；p=p—>next；}

while((p!=NULL)&&(p一>data>min))

{／／当前元素的值比min大同时比max小，删除p指向的结点 q—>next=p—>next， free(p)；p=q—>next； } return L； }．

8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。答：分析：用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。 void decompose(LinkedList *A，LinkedList *B)

{／／单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B p=A->next； B=(LinkedList*)malloc(sizeof(LinkedList))； r=B；

while(p!=NULL&&p->next!=NULL)

{q=p—>next；／／q指向偶数序号的结点 p—>next=q—>next；／／将q从A表中删除 r—>next=q；／／将q结点链接到B链表的末尾

r=q；／／r总是指向B链表的最后—·个结点 p=p—>next；／／p指向原链表A中的奇数序号的结点 }

r—>next=NULL；／／将生成B链表中的最后一个结点的next域置为空 }

9．假设以两个元素值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C，其元素为两集合的交集，且表C中的元素值也递增有序排列。用顺序表实现并写出C的算法。

答：分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，若A、B表中当前元素值相同，则写入C中，并使i、j、k值增1；若A表元素值较小，则使i增1；若B表元素值较小，则使j增1，直到有一个表先结束。 SeqLiSt *intersection(SeqList A，SeqList B，SeqList *C) {／／求元素依值递增有序排列的顺序表A、B的交集C i=0； j=0；k=0；

while((i<=A.length-1)&&(j<=B.length-1))

{if(A.data[i]==B.data[j]) ／／找到值相同的元素 {C->data[k]=A.data[i]；／／相同元素写入C表中 k++；i++；j++； } else

if(A.data[i]

else j++； }

C->length=k； return C； }

11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表

中某个结点的指针，试编写算法删除结点*s的直接前驱结点。

答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s开始，顺次向后寻找。 void DeletePre(Linkedlist *s) {／／删除单循环链表中结点s的直接前驱 p=s；

while(p—>next—>next!=s) p=p—>next；／／找到s的前驱的前驱p q=p—>next；／／q是p的后继，即s的前驱 p—>next=s；／／将q删除 free(q)； }

12．计算带头结点的循环链表的结点个数。答：int number(Linkedlist *head) {／／计算单循环链表中结点的个数 p=head—>next； i=0；

while(p!=head) {i++；p=p->next；} return i； }

13．已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个表可使用原来的单链表。q指向p的下一个结点，根据*p的数据域的值将其插入到不同的链表上。再把q的值给p，处理下一个结点。 void change(LinkedList *L，LinkedList *pa，LinkedList *pb，LinkedList

*pc)

{／／分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符

p=L—>next； pa=L；

pa—>next=pa；／／分别构造三个单循环链表 pb=(LinkedList*)malloc(sizeof(LinkedList))； pc=(LinkedList*)malloc(sizeof(LinkedList))； pb—>next=pb；pc—>next=pc； while(p!=L)

{q=p—>next；· ／／q记下L中下一个结点的位置

if(p—>data<=’z’&&p—>data>=’a’) ／／链接到字母链表的头部 {p—>next=pa—>next；pa—>next=p；}

else if (p—>data<=’9’ &&(p—>data>=’0’) ／／链接到数字链表的头部

{p—>next=pb—>next；pb—>next=p；}

else{p->next=pc->next；pc->next=p；}／／链接到其他字母链表的头部

p=q； } }

14、己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法(注：题中未特别指明同一表中的元素值各不相同)。

答：分析：先从B和C中找出共有元素，记为same，再在A中从当前位置开始，凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个Same

SeqList IntersectDelete(SeqList *A，SeqList B，SeqList C) {／／对顺序表A删去那些既在B表中出现又在C表中出现的元素

i=0；j=0；k=0；m=0; ／／i指示A中元素原来的位置，m为移动后的位置 while(ilength&&iC.data[k]) k++;

else {same=B.data[j]；／／找到了相同元素same while(B.data[j]==same) j++；

while(C.data[k]==same) k++；／j、k后移到新的元素 while(ilength&&A->data[i]

A->data[m++]=A->data[i++]；／／需保留的元素移动到新位置 while(i1ength&&A->data[i]==same; i++；／／跳过相同的元素

} }

while(ilength)

A->data[m++]=A->data[i++]；／／A的剩余元素重新存储 A->1ength=m； }

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

(1)在值为x的结点之前插入值为y的结点。(2)删除值为x的结点。答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。 typedef struct Node

{DataType data； struct Node *prior，*next；}DLNode，*DLinkedList； void DLinsertl(DLinkedList L，int x，int y)

{ ／／在双循环链表中插入结点 p=L->next；

while(p!=L&&p->data!=x) p=p->next；／／在链表中查找值为x的结点 if(p->data==x) ／／找到值为x的结点 {q=p->prior；／／q指向值为x的结点的前驱 s=(DLinkedList)malloc(sizeof(DLNode))； s->data=y；

s->next=p； s->prior=q；／／将y插入到q与p指向的结点之间 p->prior=s；q->next=s； }

else{printf(”没有值为x的结点”)；exit(0)；} } void DLDelete(DLinkedList L，int x) {／／在双循环链表中删除结点 p=L->next；

while(p!=L&&p->data!=x)p=p->next；

if(p->data==x) {p->prior->next=p->next；p->next->prior=p->prior；free(p)；}

else{printf(”没有值为x的结点”)；exit(0)；} }

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

答：typedef struct Node {DataType data； struct Node *prior，*next；}DLNode，*DLinkedList； void DLchange(DLinkedList p)

{／／将双循环链表中p指向的结点与其右边的一个结点进行交换

q=p—>next；／／q指向p的后继

p—>prior—>next=q；q—>prior=p—>prior；／／将p的前驱与q相链接

p—>next=q—>next；p—>prior=q；／／将p插入到q之后 q->next—>prior=p；q—>next=p； }

17．设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq，在链表启用之前，其初始值均为0。每当链表进行一次LocateNode(L，x)操作时令元素值为x的结点中freq域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。

答：分析：先在双链表中查找值为x的结点，若找到则使其freq值增1，然后从头至尾扫描链表，将此结点插入到按freq递减顺序排列的正确位置。 typedef struct DLNode

{int data，freq；struct DLNode *prior，*next；}DLNode，*DLinkedList； void LocateNode(DLinkedList head，int x) {／／双链表按访问频度域freq递减次序排列

p2=head； p1=p2—>next；／／p2在前，p1在后 while(p1) ／／查找单链表中值为x的结点

if(pl—>data==x) {pl—>freq++； break；}／／使值为x的结点的freq加1

else {p2=pl；p1=p2—>next；}

if(p1==NULL) printf(”Not found.＼n”)；

else{if(p1—>next==NULL) {p2—>next=p1—>next；temp=p1；} ／／在链表中找temp所指向的结点，按freq值递减应插入的位置

else{p2—>next=p1—>next；／／插入链表中间的某一位置 p1—>next->prior=p2； temp=pl；}

for(p2=head，p1=p2->next；pl&&p1->freq>temp->freq；p2=p1，pl=p2->next)；／／插入

if(p1==NULL) {p2->next=temp；temp->prior=p2；temp->next=NULL；} else {p2->next=temp；temp->prior=p2；temp->next=pl；p1->prior=temp；} } }

18．给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。答：typedef struct PNode {int coef；／／系数 int exp；／／指数

struct PNode *next；}*PLink； PLink CreatPoly( ) {／／建立多项式

head=(PLink)malloc(sizeof(struct PNode))； r=head；

printf(”输入系数和指数：”)； scanf(&n，&m)； while(n!=0) ／／若n=0则退出循环 {s=(Plink)malloc(sizeof(struct PNode))；

s->coef=n；s->exp=m；r->next=s；r=s；／／把s链接到r的后面 printf(”输入系数和指数:”)； scanf(&n，&m)； } r->next=NULL；head=head—>next；／／删除头结点

return head； }

19．根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。答：分析：对所有指数相同的项，将其对应系数相加，若和不为0，则构造新“和多项式”的结点；将所有指数不同的项复制到和多项式中。 Plink add(PLink pa，PLink pb) {／／多项式相加

p=pa；q=pb；pc=(PLink)malloc(sizeof(struct PNode))；r=pc； while(p!=NULL&&q!=NULL)

{if(p->exp==q->exp)／／两结点的指数相同时，将两系数相加生成新结点插入c中

{x=p->coef+q->coef；

if(x!=0){s=(PLink)malloc(sizeof(struct PNode))；s->coef=x； s->exp=p->exp；

r->next=s； r=s； } p=p->next；q=q->next；}

else if(p->exp>q->exp)／／两结点的指数不同时，将较小系数的结点复制成新结点插入c中

{s=(PLink)malloc(sizeof(struct PNode))；s->coef=q->coef；s->exp=q->exp；

r->next=s； r=s；q=q->next；}

else {s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef； s->exp=p->exp；r->next=s；r=s；p=p->next； } }

while(p!=NULL) ／／复制A的余下部分

{s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef；s->exp=p->exp；

r->next=s：r=s；p=p->next；} while(ql=NULL) ／／复制B的余下部分

{s=(PLink)malloc(sizeof(struct PNode))；s->coef=q->coef；s->exp=q->exp；

r->next=s；r=s；q=q->next； }

r->next=NULL；／／最后结点的next域置为空 s=pc；pc=pc->next；／／删除c的头结点 free(s)； return pc; }

20．约瑟夫环问题：任给正整数n、k，按下述方法可得排列1，2，?，n的一个置换：将数字l，2，?，n环形排列，按顺时针方向从1开始计数；计满k时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10、k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。答：void Js1(int A[n]，int N，iht K) {／／以数组为存储结构

for(i=0；i

while(s

A[j-1]=0;／／将计满k值的数字输出，并将其位置标为0表明已删除 } }

void Js2(LinkedList last，int N，int K)

{／／以不带头结点的、已知尾指针的单循环链表为存储结构 p=last； q=p->next；／／此时q为头结点fp为q的前驱 while(N>0)

{for(j=2；j<=K；j++) ／／循环K-1次 {p=q；q=p->next；}

printf(”%d”，q->data)； N--； p->next=q->next; ／／删除q q=p—>next； } }

第三节栈和队列一、选择题

1．设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是( )。 A．2 *B．3 C．5 D．6

2．若一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为( )。

A．4 *B．5 C．6 D．7

3．设有一顺序栈已经含有3个元素，如图3-1所示，元素a4正等待入栈。以下序列中不可能出现的出栈序列是( )。

*A．a3，a1，a4，a2 B．a3，a2，a4，a1 C．a3，a4，a2，a1 D．a4，

a3，a2，a1

4．和顺序栈相比，链栈有一个比较明显的优势是( )。

*A．通常不会出现栈满的情况 B．通常不会出现栈空的情况 C．插入操作更容易实现 D．删除操作更容易实现

5．若一个栈的输入序列是1，2，3，4，?，n，输出序列的第一个元素是n，则第i个输出元素是( )。

A．不确定 B．n-i *C．n-i+1 D．n-i-1 6．以下说法正确的是( )。

*A．因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况 B．因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况 C．对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢” D．对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢”

7．顺序队列的入队操作应为( sq.rear初值为-1 )。

*A．sq.rear=sq.rear+1；sq.data[sq.rear]=x; B．sq.data[sq.rear]=x；sq.rear=sq.rear+1； C．sq.rear=(sq.rear+1)％maxsize；sq.data[sq.rear+1]=x;

．

sq.data[sq.rear]=x

；

sq.rear=x;

sq.rear=(sq.rear+1)％maxslze；

8．循环队列的入队操作应为(sq.rear初值为-1 )。

A．sq．rear=sq．rear+1；sq．data[sq．rear]=x B．sq．data[sq．rear]=x；sq．rear=sq．rear+l； *C．sq．rear=(sq．rear+1)％maxsize；

sq．data[sq．rear]=x； D．sq．data[sq．rear]=x；sq．rear=(sq．rear+1)％maxsize；

9．顺序队列的出队操作为(sq. front初值为-1 )。

A．sq．front=(sq．front+1)％maxsize； *B．sq．front=sq．front+1； C．sq．rear=(sq．rear+1)％maxsize； D．sq．rear=sq．rear+1; 10．循环队列的出队操作为(sq. front初值为-1 )。

*A．sq．front=(sq．front+1)％maxsize； B．sq．front=sq．front+1； C．sq．rear=(sq．rear+1)％maxsize； D．sq．rear=sq．rear+l； 11．循环队列的队满条件为( )。

A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize； B．(sq．rear+1)％maxsize==sq．front+1； *C．(sq．rear+1)％maxsize==sq．front； D．sq．rear==sq．front； 12．循环队列的队空条件为( )。

A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize； B．(sq．rear+1)％maxsize==sq．front+1； C．(sq．rear+1)％maxsize==sq．front； *D．sq．rear==sq．front；

13．如果以链表作为栈的存储结构，则出栈操作时( )。

A．必须判别栈是否满 B．判别栈元素的类型 *C．必须判别栈是否空 D．对栈不做任何判别

14，向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为( )。

A．Top->next=s； B．s->next=Top->next；Top->next=s； *C．s->next=Top；Top=s； D．s->next=Top；Top=Top->next；

15．从栈顶指针为Top的链栈中删除一个结点，并将被删结点的值保存到x中，其操作步骤为( )。

*A．x=Top->data；Top=Top->next； B．Top=Top->next；x=Top->data； C．x=Top；Top=Top->next； D．x=Top->data；

16．在一个链队中，苕f、r分别为队头、队尾指针，则插入s所指结点的操作为( )。

A．f->next=s；f=s； *B．r->next=s；r=s； C．s->next=r；r=s； D．s->next=f；f=s；

17．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。 A．e，d，c，b，a B．d，e，c，b，a *C．d，c，e，a，b D．a，b，c，d，e

18．一个队列的入队序列是1，2，3，4，则队列可能的输出序列是( )。 A．4，3，2，1 *B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 19．设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳。

A．线性表的顺序存储结构 *B．栈 C．队列 D．线性表的链式存储结构二、判断题

√1．在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。 ╳2．与顺序栈相比，链栈的一个优点是插入和删除操作更加方便。

╳3．若一个栈的输入序列为1，2，3，?，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1，2，?，n)。 √4．在链队中，即使不设置尾指针也能进行入队操作。

√5．在对链队(带头指针)做出队操作时，不会改变front指针的值。 ╳6．循环队列中元素个数为rear-front。

╳7．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2．

√8．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 ╳9．若以链表作为栈的存储结构，则入栈需要判断栈是否满． √10．若以链表作为栈的存储结构，则出栈需要判断栈是否空。三、填空题

1．向一个栈顶指针为Top的链栈中插入一个s所指的结点时，其进行的操作是__ s->next=Top；Top =s；__。

2．从栈顶指针为Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_ x=Top->data；Top=Top->next；__。

3．在具有n个单元的循环队列中，队满时共有___n-1_个元素。

4．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为__ b，c，e，d，a ___。 5．设有数组A[m]作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是_rear=（rear +1）％（m+1）； A[rear]=x;__。 6．在一个链队中，如果f、r分别为队头、队尾指针，则插入s所指结点的操作是_r->next=s; r=s;___。

7．栈的逻辑特点是__后进先出____，队列的逻辑特点是_先进先出__，二者的共同特点是_操作受限__。

8．___栈___可以作为实现递归函数调用的一种数据结构。 9．在队列中，新插入的结点只能添加到__队尾__。

10．链队在一定范围内不会出现__队满___的情况。当lq．front==lq．rear时，队中无元素，此时___队空__。

11．设一个链栈的栈顶指针为ls，栈中结点的格式为data:next，栈空的条件是_ ls = NULL__；如果栈不为空，则出栈操作为p=ls; ___ ls = ls ->next __；free(p)。

12．对带有头结点的链队lq，判定队列中只有一个数据元素的条件是__lq->front->next= lq->rear___。

13．设有一个空栈，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push后，栈顶指针所指元素是__4__。

14．设用一维数组A[n]来表示一个栈，令A[0]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值__加1___，从栈中弹出一个元素时，变量t的值___减1___。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是___c__。四、应用题

2．设有字符串为3*-y-a/y^2，试利用栈写出将其转换为3y-*ay2^/-的操作过程。假定用X代表扫描该字符串过程中顺序取一个字符入栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。

答：XSXXXSSSXXSXXSXXSSSS

3．设有一个输入序列a，b，c，d，元素经过一个栈到达输出序列，而且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列? 答

：

可

以

得

到

种

输

出

序

列

：

abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc.

4．按照运算符优先法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9-2*4+(8+1)/3。答：

序号运算符操作数输入字

栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 # # #- #- #-* #-* #- # #+ #+( #+( #+(+ #+(+ #+ #+/ #+/ #+ # 栈 9 9 92 92 924 98 1 1 1 18 18 181 19 19 193 13 4 符 9 - 2 * 4 + ( 8 + 1 ) / 3 # 5．链栈中为何不设置头结点?

答：因为链栈只在链表头插入和删除结点，不可能在链表中间插入或删除结点，算法实现很简单，所以一般不设置头结点。

第四节数组

一、选择题

1．数组通常具有的两种基本操作是( )。

A．建立和删除 B．索引和修改 *C．查找和修改 D．查找和索引 2．二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是( )。 *A．1208 B．1212 C．1368 D．1364 3．对矩阵压缩存储是为了( )。

A．方便运算 *B．节省空间 C．方便存储 D．提高运算速度 4．稀疏矩阵的压缩存储方法通常有两种，即( )。

A．二元数组和三元数组 B．三元组和散列 *C．三元组和十字链表 D．散列和十字链表二、判断题

√ 1．数组是同类型值的集合。 √2．数组是一组连续的内存单元。

╳3．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

╳4．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

√ 5．使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。三、填空题

1．二维数组A[10， 20]采用列序为主序方式存储，每个元素占一个存储单元，并且A[1，1]的存储地址是200，则A[6，12]的地址是___315___。

2．有一个10阶对称矩阵A采用压缩存储方式(以行序为主序方式)存储其下三角元素，且第一个元素A[0，0]的存储地址为1，则A[4，5]的地址是__14__，

A[8，3]的地址是___31_。

3．下三角矩阵A[N,N]的下三角元素已压缩到一维数组S[N(N+1)／2]中，若按行序为主序存储，则A[i，j]对应的S中的存储位置是__I(I-1)/2+j(i≥j),n(n+1)/2+1(I

1．假设有二维数组A[6,8]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始地址(基地址)为1000，计算：(1)数组A的容量。(2)按行优先方式存储时，元素A[1，4]的地址。(3)按列优先方式存储时，元素A[4,7]的地址。

答：(1)数组A的容量:6*8*6=288。(2)按行优先方式存储时，元素A[1，4]的地址=1000+3*6=1018。(3)按列优先方式存储时，元素A[4,7]的地址=1000+(6*6+3)*6=1234。

2．设有三对角矩阵A[n，n]，将其三条对角线上的元素逐行存放于数组B[3n-3]中，使得B[k]=A[i,j]，求： (1)用i，j表示k的下标变换公式。 (2)用k表示i，j的下标变换公式。

答：(1) k=2i+j-3 (2) I=(k+1)/3+1，j=k-2i+3。 3．画出图5-2所示的稀疏矩阵A的三元组表和十字链表。

答：

row col e 1 2 4 1 2 5

2 3 5 5

3 5 1 3 6 8 4 9 4．用三元组表表示图5-3所示的稀疏矩阵的转置矩阵。

答：

row col e 1 2 3 4 5 2 1 3 4 2 2 1 4 5 3 五、算法设计题

1．设计将数组A[n]中的所有奇数移到所有偶数之前的算法。要求不另外增加存储空间且时间复杂度为O(n)。

算法采用两个变量i和j分别表示数组的开头和末尾元素，同时向中间搜索： void change(int a[n]) { I=0; j=n-1; while (I

{while (a[I]%2!=0&&I

if (I

{c=a[I];a[I]=a[j];a[j]=c; I++;j--;} } }

*2．当稀疏矩阵A和B均以三元组作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组C中。略。第五节树

(树根结点的高度为1) 一、选择题

1．以下说法错误的是( )。

*A．树形结构的特点是一个结点可以有多个直接前驱 B．线性结构中的一

个结点至多只有一个直接后继 C．二叉树与树是两种不同的数据结构 D．树(及一切树形结构)是一种“分支层次’结构 2．以下说法错误的是( )。

A．二叉树可以是空集 *B．二叉树的任一结点都有两棵子树 C．二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 3．以下说法错误的是( )。

A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 *D．在二叉链表上，求双亲操作的时间性能很好

4．以下说法错误的是( )。

A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有

度数为1的分支结点 C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 *D．若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树

5．深度为6的二叉树最多有( )个结点。 A．64 *B．63 C．32 D．31

6．将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为( )。 *A．10 B．11 C．41 D．20

7．任何一棵二叉树的叶结点在其前序、中序、后序遍历序列中的相对位置( )。 A．肯定发生变化 B．有时发生变化 *C．肯定不发生变化 D．无法确定

8．设二叉树有n个结点，则其深度为( )。 A．n-1 B．n C．└log2n┘+1 *D．无法确定

9．设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。

A．k+l B．2k *C．2k-1 D．2k+1 10．下列说法正确的是( )。

*A．树的前序遍历序列与其对应的二叉树的前序遍历序列相同 B．树的前序遍历序列与其对应的二叉树的后序遍历序列相同 C．树的后序遍历序列与其对应的二叉树的前序遍历序列相同 D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同 11．下列说法中正确的是( )。

A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 *D．任

何一棵二叉树中的每个结点的度都可以小于2

12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。 A．前序 *B．中序 C．后序 D．层次

13．设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有( )个结点。 A．n1-1 B．n1 C．n1+n2+n3 *D． n2+n3+n4

14．对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A．0 *B．1 C．2 D．不存在这样的二叉树 15．如图6-1所示的二叉树的中序遍历序列是( )。

A．abcdgef *B．dfebagc C．dbaefcg D．defbagc

16．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是( )。

A．acbed *B．baedc C．dceab D．cedba

17．如果T1是由有序树转化而来的二叉树，那么T中结点的前序就是T1中结点的( )。

*A．前序 B．中序 C．后序 D．层次序

18．某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( )。

A．bdgcefha B．gdbecfha C．bdgechfa *D．gdbehfca 19．在图6-2中的二叉树中，( )不是完全二叉树。（*C）

20．树最适合用来表示( )。

A．有序数据元素 B．无序数据元素 *C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据

21．在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构。

*A．栈 B．树 C．双向队列 D．顺序表

22．设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是( )。 A．2 B．2 C．2-1 *D．2-1 23．以下说法错误的是( )。

h-1

h+1

A．存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同 *B．二叉树是树的特殊情形 C．由树转换成二叉树，其根结点的右子树总是空的 D．在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

24．已知一个算式的中缀表达式为a+(b-c)/d，则其后缀表达式是( )。 A．a+(b-c)/d *B．abc-d/+ C．bc-d/a+ D．a+bc-d/

25．按照二叉树的定义，具有4个结点所能构造的不同的二叉树的个数是( )。 A．4 B．8 C．12 *D．14

26．在一棵度为3的树中，度为3的结点的个数为2，度为2的结点的个数为1，则度为0的结点的个数为( )。 A．4 B．5 *C．6 D．7

27．3个结点可构成( )棵不同形态的二叉树。 A．2 B．3 C．4 *D．5 28．哈夫曼树的带权路径长度是( )。

A．所有结点权值之和 *B．所有叶结点带权路径长度之和 C．带权结点的值 D．除根以外所有结点权值之和

29．设有一棵22个结点的完全二叉树，那么整棵二叉树有( )个度为0的结点。 A．6 B．7 C．8 *D．11

30．已知完全二叉树有26个结点，则整棵二叉树有( )个度为1的结点。 A．0 *B．1 C．2 D．13

31．在树的孩子兄弟表示法中，( )操作花时间最多。

A. 求某结点的兄弟 B．求某结点的第i个孩子 *C．求某结点的父结点 D．求树的根结点

32．已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是( )。 A．110100 *B．11011100 C．010110111 D．11111100

33．在n个结点的完全二叉树中，对任一结点i(1≤i≤n)，i的左孩子可能是( )。

A．i/2 B．2i+1 *C．2i D．都不是

34．已给出图6-3所示的二叉树，A，B，C，D的权值分别为7，5，2，4，则该树的带权路径长度为( )。

A．46 B．36 *C．35 D．都不是 35．下列叙述中不正确的是( )。

A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时有左右之分 *C．二叉树中必有度为2的结点 D．二叉树中结点最多有两棵子树，并且有左右之分

36．图6-4所示的几种结构中属于树形结构的是( )。（*B）

二、判断题

╳1．二叉树是树的特殊形式。

√2．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 √3．一棵有n个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在树的n*d个链域中，有n*(d-1)+1个是空链域，只有n-1个是非空的。 √4．前序遍历树和前序遍历与该树对应的二叉树，其结果相同。 ╳5．中序遍历树和中序遍历与该树对应的二叉树，其结果不同。 √6．前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。 ╳7．中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。 √8．若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。

√9．二叉树中具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。

╳10．在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。

╳11．在二叉树中插入结点，该二叉树便不再是二叉树。 ╳12．用一维数组存储二叉树时，总是以前序遍历存储结点。 √13．已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树。 √14．不使用递归，也可以实现二叉树的前序、中序、后序遍历。

√15．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。

╳16．有n个结点的不同二叉树有n!棵。

╳17．在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。三、填空题

1．树(及一切树形结构)是一种__层次__结构。在树中，__根_结点没有直接前驱。对树上任一结点x来说，x是它的任一子树的根结点惟一的_双亲_。 2．一棵树上的任何结点(不包括根本身)称为根的__子孙__。若B是A的子孙，则称A是B的__祖先__。

3．二叉树第i(i>0)层上至多有__2__个结点。 4．深度为k(k>0)的二叉树至多有__2-1__个结点。

5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__n2+1__。 6．满二叉树上各层的节点数已达到了二叉树可以容纳的__最大值_。满二叉树也是__完全__二叉树，但反之不然。

7．具有n个结点的完全二叉树的深度为___│log2n│+1___。

8．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是__ │log2i│ =│ log2j│ ____。

ki-1

9．如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(0l，则X的双亲PARENT(X)的编号为__│i/2│___。(2)若2i>n，则结点x无__左孩子__且无__右孩子__；否则，X的左孩子LCHILD(X)的编号为__2i __。(3)若2i+1>n，则结点X无__右孩子__；否则，X的右孩子RCHILD(X)的编号为__2i+1__。

10．二叉树通常有___顺序____存储结构和___链式__存储结构两类存储结构。 11．每个二叉链表还必须有一个指向__根__结点的指针，该指针具有标识二叉链表的作用。

12．对二叉链表的访问只能从___根__指针开始。

13．具有n个结点的二叉树中，一共有__2n__个指针域，其中只有__n-1_个用来指向结点的左右孩子，其余的__n+1__个指针域为NULL。

14．已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为__99（40+39+20）___。

15．二叉树有不同的链式存储结构，其中最常用的是_二叉链表___与__三叉链表__。

16．可通过在非完全二叉树的“残缺”位置上增设__空指针___将其转化为完全二叉树。

17．具有100个结点的完全二叉树的深度是__7___。 18．深度为90的满二叉树上，第10层有___512___个结点。

19．在__前序__遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。

20．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号是__│n/2│___，编号最小的分支结点序号是__1_，编号最大的叶结点序号是_n_，编号最小的叶结点序号是__│n/2

│+1____。

21．若一棵二叉树的叶子数为n，则该二叉树中左、右子树皆非空的结点个数为__n-1__。

22．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为__n-2m+1__个。