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

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

一、选择题

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，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容__ 、 、 ___。

1

3．数据的逻辑结构包括_____ ___、_____ ___、____ _____和__ _____四种类型。 4．在线性结构中，开始结点__ _前驱结点，其余每个结点有且只有_ _个前驱结点。

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

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

7．算法的五个重要特性是___ ____、____ ____、____ ____、___ ___、___ __。 8．下列程序段的时间复杂度是___ ____。 for (i=1；i<=n；i++) A[i，i]=0；

9．下列程序段的时间复杂度是___ ____。 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(__ _)、对数阶O(__ ___)、线性阶O(__ __)、平方阶O(__ _)和指数阶O(__ _)。通常认为，具有指数阶量级的算法是__ __的。 18．数据结构的基本任务是数据结构的___ __和__ ___。 19．数据对象是性质相同的__ __的集合。

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

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

WHILE (i<=n) i=i*2； …… _ _ 2．叙述算法的定义及其重要特性。

3．简述下列术语：数据，数据元素，数据结构，数据对象。 4．逻辑结构与存储结构是什么关系？

／

5．将数量级210，n，n2，n3，nlog2n，log2n，2n，n!，(2／3)n，n23按增长率进行排列。

6．设有数据逻辑结构为：D={k1，k2，k3，…，k9}，R={，，，，，，，，，}，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

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

2

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++； 答：

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．线性结构中的一个结点代表一个( )。

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

3

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指向双链表的某一结点，则双链表结构的对称性可用( )式来刻画。

A．p->prior->next->==p->next->next B．p->prior->prior==p->next->prior C．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

4

2．线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接__ __外，其他结点有且仅有一个直接_ __；除终端结点没有直接_ __外，其他结点有且仅有一个直接_ ___。 3．所有结点按一对一的邻接关系构成的整体就是__ __结构。

4．线性表的逻辑结构是__ __结构，其所含结点的个数称为线性表的___ __。 5．在单链表中，删除p所指结点的直接后继的操作是__ _；p->next=q->next；free(q)； 6．非空的单循环链表head的尾结点(由指针p所指)满足__ _ ______。

7．rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为___ _；q=p->next；p->next=q->next；free(q)；____。

8．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为__ _，在给定值为x的结点后插入新结点的时间复杂度为__ __。

9．单链表表示法的基本思想是用___ ___表示结点间的逻辑关系。

10．在顺序表中插入或删除一个元素，平均需要移动__ __元素，具体移动的元素个数与__ __有关。 11．在一个长度为n的向量的第i(1≤i≤n+1)个元素之前插入一个元素时，需向后移动___ __个元素。 12．在一个长度为n的向量中删除第i(1≤i≤n)个元素时，需向前移动___ __个元素。

13．在双链表中，每个结点有两个指针域，一个指向__ ___，另一个指向__ ____。 14．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=__ _。 15．设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成___ ____。 16．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是__ ___s指向的结点。

17．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___ __ ；r->next=s；r=s；

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

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

1．描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。 答：

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

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

4．为什么在单循环链表中设置尾指针比设置头指针更好？ 答： 5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？若可以，其时间复杂度各为多少？ 答：

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；}

5

答：

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

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

五、算法设计题

假设算法中用到的顺序表和链表结构如下： #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)顺序表的就地逆置

(2)链表的就地逆置

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

答：

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

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

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

6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。 7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。

8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。

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

11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前驱结点。

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

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

6

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域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。

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

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

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

第三节 栈和队列

一、选择题

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 )。

7

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; D．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所指的结点时，其进行的操作是___ _；Top =s；__。

2．从栈顶指针为Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_ _ _；Top=Top->next。 3．在具有n个单元的循环队列中，队满时共有___n-1_个元素。

8

4．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为___ ____。

5．设有数组A[m]作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是__ _； A[rear]=x。

6．在一个链队中，如果f、r分别为队头、队尾指针，则插入s所指结点的操作是_ ____。

7．栈的逻辑特点是__ _____，队列的逻辑特点是__ ___，二者的共同特点是__ ___。 8．___ ____可以作为实现递归函数调用的一种数据结构。 9．在队列中，新插入的结点只能添加到__ _。

10．链队在一定范围内不会出现___ ___的情况。当lq．front==lq．rear时，队中无元素，此时___ ___。 11．设一个链栈的栈顶指针为ls，栈中结点的格式为data:next，栈空的条件是__ ___；如果栈不为空，则出栈操作为p=ls; ___ ___；free(p)。

12．对带有头结点的链队lq，判定队列中只有一个数据元素的条件是__ ____。

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

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

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

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

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，

9

则A[6，12]的地址是___ ____。

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

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

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

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

3．画出图5-2所示的稀疏矩阵A的三元组表和十字链表。

答：

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

答：

第五节 树

(树根结点的高度为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次合并后才能剩下一棵最终的哈夫曼树

10

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中的二叉树中，( )不是完全二叉树。

11

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

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

21．在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构。 A．栈 B．树 C．双向队列 D．顺序表

22．设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是( )。 A．2h B．2h-1 C．2h-1 D．2h+1-1 23．以下说法错误的是( )。 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．都不是

12

35．下列叙述中不正确的是( )。

A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时有左右之分 C．二叉树中必有度为2的结点 D．二叉树中结点最多有两棵子树，并且有左右之分 36．图6-4所示的几种结构中属于树形结构的是( )。

二、判断题

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)层上至多有__ _个结点。

4．深度为k(k>0)的二叉树至多有__ ___个结点。

5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__ ___。

6．满二叉树上各层的节点数已达到了二叉树可以容纳的__ __。满二叉树也是__ ___二叉树，但反之不然。

7．具有n个结点的完全二叉树的深度为____ ____。

8．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是___ _____。

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

10．二叉树通常有___ _____存储结构和__ ___存储结构两类存储结构。

11．每个二叉链表还必须有一个指向__ __结点的指针，该指针具有标识二叉链表的作用。 12．对二叉链表的访问只能从____ ___指针开始。

13．具有n个结点的二叉树中，一共有___ __个指针域，其中只有__ __个用来指向结点的左右孩子，

13

其余的___ ___个指针域为NULL。

14．已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为___ ____。 15．二叉树有不同的链式存储结构，其中最常用的是__ ____与___ __。 16．可通过在非完全二叉树的“残缺”位置上增设___ ____将其转化为完全二叉树。 17．具有100个结点的完全二叉树的深度是___ ___。 18．深度为90的满二叉树上，第10层有___ ___个结点。

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

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

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

22．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为__n-_ ___个。 23．设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有___ _个结点。

24．现有按中序遍历二叉树的结果为ABC，有__ ___种不同形态的二叉树可以得到这一遍历结果。 25．以数据集{4，5，6，7，10}为叶结点的权值所构造的哈夫曼树的带权路径长度为__ _.

26．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有__ __个叶结点。

27．设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶结点的个数是_ __。 28．如果结点a有三个兄弟，而b是a的双亲，则b的度是__ ___。 29．一棵树的形状如图6-5所示，它的根结点是__ __，叶结点是___ ___，结点H的度是___ __，这棵树的度是__ __，这棵树的深度是__ __，结点F的儿子结点是__ __，结点G的父结点是___ ___。

30．设结点x有左孩子结点y、右孩子结点z，用三种基本遍历方法得到的遍历序列中x___ ____是y的前驱，x__ ___是z的后继，y___ __是z的前驱(填“一定”，“不”、“不一定”)。

31．在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个__ ___，且存在一条从根到该结点的___ ___。

32．含有2n个结点的二叉树高度至少是__ ____，至多是___ _ (仅含根结点的二叉树高度为1)。 33．设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为_ ___，至多为__ ___。 四、应用题

1．分别画出含3个结点的树与二叉树的所有不同形态。 答：

2．设在树中，结点x是结点y的双亲，用来表示边。已知一棵树边的集合为：{，，，，，，，，，，}，用树形表示法画出此树，并回答下列问题： (1)哪个是根结点？ (2)哪些是叶结点？ (3)哪个是g的双亲？ (4)哪些是g的祖先？ (5)哪些是e的子孙？ (6)哪些是f的兄弟？ (7)结点b和j的层次各是多少？ (8)树的深度是多少？ (9)树的度数是多少？ 答：

14

3．任意一个有n(n>0)个结点的二叉树，已知它有m个叶结点，试证明非叶结点有m-1个度为2，其余度为1。 答：

4．分别画出图6-6所示二叉树的二叉链表、三叉链表和顺序存储结构。

答：

5．分别写出图6-7所示二叉树的前序、中序和后序序列。

答：

6．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。 答：

7．二叉树中的结点进行按层次顺序(每层自左到右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二又树。 答：

8．将图6-9所示的森林转换成二叉树。

答：

9．分别画出图6-10所示二叉树对应的森林，并写出森林的前序和后序遍历序列。

15

本文来源：https://www.bwwdw.com/article/cen8.html