数据结构18章课后题填空选择答案及部分解析.docx

数据结构18章课后题填空选择答案及部分解析.docx

《数据结构18章课后题填空选择答案及部分解析.docx》由会员分享，可在线阅读，更多相关《数据结构18章课后题填空选择答案及部分解析.docx（24页珍藏版）》请在冰点文库上搜索。

数据结构18章课后题填空选择答案及部分解析

第1章绪论

1.填空

⑴（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

⑵（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（集合）、（线性结构）、（树结构）和（图结构）。

⑷数据的存储结构主要有（顺序存储结构）和（链接存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：

（数据元素）和（数据元素之间的关系）。

⑸算法具有五个特性，分别是（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。

⑹算法的描述方法通常有（自然语言）、（程序设计语言）、（流程图）和（伪代码）四种，其中，（伪代码）被称为算法语言。

⑺在一般情况下，一个算法的时间复杂度是（问题规模）的函数。

⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο

（1）），若

为n*log25n，则表示成数量级的形式为（Ο（nlog2n））。

【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2.选择题

⑴顺序存储结构中数据元素之间的逻辑关系是由（C）表示的，链接存储结构中的数据元素之间的逻辑关系是由（D）表示的。

A线性结构B非线性结构C存储位置D指针

【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：

丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（B）。

A树B图C线性表D集合

【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。

⑶算法指的是（A）。

A对特定问题求解步骤的一种描述，是指令的有限序列。

B计算机程序C解决问题的计算方法D数据处理

【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。

所以，只有A是算法的准确定义。

⑷下面（C）不是算法所必须具备的特性。

A有穷性B确切性C高效性D可行性

【分析】高效性是好算法应具备的特性。

⑸算法分析的目的是（C），算法分析的两个主要方面是（E）。

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

C分析算法的效率以求改进D分析算法的易读性和文档性

E空间性能和时间性能F正确性和简明性

G可读性和文档性H数据复杂性和程序复杂性

第2章线性表

1.填空

⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（表长的一半）个元素，具体移动元素的个数与（表长）和（该元素在表中的位置）有关。

⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（108）。

【分析】第5个元素的存储地址=第1个元素的存储地址＋（5－1）×2=108

⑶设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（p->next=（p->next）->next）。

⑷单链表中设置头结点的作用是（为了运算方便）。

【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（p->next=head）。

【分析】如图2-8所示。

⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（s->next=rear->next;rear->next=s;rear=s;）；删除开始结点的操

作序列为（q=rear->next->next;rear->next->next=q->next;deleteq;）。

⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（Ο

（1））；在给定值为x的结点后插入一个新结点的时间复杂度为（Ο（n））。

【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο

（1）；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο（n）。

⑻可由一个尾指针唯一确定的链表有（循环链表）、（循环双链表）、（双链表）。

2.选择题

⑴线性表的顺序存储结构是一种（A）的存储结构，线性表的链接存储结构是一种（B）的存储结构。

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

⑵线性表采用链接存储时，其地址（D）。

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

C一定是不连续的D连续与否均可以

【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。

⑶单循环链表的主要优点是（B）。

A不再需要头指针了

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

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

D在进行插入、删除操作时，能更好地保证链表不断开。

⑷链表不具有的特点是（A）。

A可随机访问任一元素B插入、删除不需要移动元素

C不必事先估计存储空间D所需空间与线性表长度成正比

⑸若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（A）存储方法最节省时间。

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

【分析】线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。

单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。

⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（D）存储方法

最节省时间。

A单链表B带头指针的单循环链表C双链表D带尾指针的单循环链表

【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O

（1），所以，答案是D。

⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（B）存储方

法最节省运算时间。

A单链表B循环双链表C单循环链表D带尾指针的单循环链表

【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。

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

AO

（1）BO（n）CO（n2）DO（nlog2n）

【分析】首先应顺序查找新结点在单链表中的位置。

⑼对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（C）。

AO

（1）BO（n）CO（n2）DO（nlog2n）

【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O（n）。

⑽使用双链表存储线性表，其优点是可以（B）。

A提高查找速度B更方便数据的插入和删除

C节约存储空间D很快回收存储空间

【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。

由于双链表具有对称性，所以，其插入和删除操作更加方便。

⑾在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（B）操作。

As->next=p->next;p->next=s;Bq->next=s;s->next=p;

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

【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。

⑿在循环双链表的p所指结点后插入s所指结点的操作是（D）。

Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s

【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。

第3章特殊线性表——栈、队列和串

1.填空

⑴设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，

pop，push，push后，输出序列是（23），栈顶指针为（1003H）。

⑵栈通常采用的两种存储结构是（顺序存储结构和链接存储结构（或顺序栈和链栈））；其判定栈空的条件分别是（栈顶指针top=-1和top=NULL），判定栈满的条件分别是（栈顶指针top等于数组的长度和内存无可用空间）。

⑶（栈）可作为实现递归函数调用的一种数据结构。

【分析】递归函数的调用和返回正好符合后进先出性。

⑷表达式a*（b+c）-d的后缀表达式是（abc+*d-）。

【分析】将中缀表达式变为后缀表达式有一个技巧：

将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸栈和队列是两种特殊的线性表，栈的操作特性是（后进先出），队列的操作特性是（先进先出），栈和队列的主要区别

在于（对插入和删除操作限定的位置不同）。

⑹循环队列的引入是为了克服（假溢出）。

⑺数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列

中元素个数的公式为（（rear-front+n）%n）。

【分析】也可以是（rear-front）%n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

⑻用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（Ｏ

（1））和（Ｏ（n））。

【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

⑼串是一种特殊的线性表，其特殊性体现在（数据元素的类型是一个字符）。

⑽两个串相等的充分必要条件是（长度相同且对应位置的字符相等）。

【分析】例如"abc"≠"abc"，"abc"≠"bca"。

2.选择题

⑴若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（D）。

A不确定Bn-iCn-i-1Dn-i+1

【分析】此时，输出序列一定是输入序列的逆序。

⑵设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进

入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（C）。

A6B4C3D2

【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。

⑶一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（C）。

A54321B45321C43512D12345

【分析】此题有一个技巧：

在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。

⑷设计一个判别表达式中左右括号是否配对的算法，采用（B）数据结构最佳

A顺序表B栈C队列D链表

【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。

⑸在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B）结构。

A栈B队列C数组D线性表

【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。

⑹一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（B）。

A4321B1234C1432D3241

【分析】队列的入队顺序和出队顺序总是一致的。

⑺栈和队列的主要区别在于（D）。

A它们的逻辑结构不一样B它们的存储结构不一样

C所包含的运算不一样D插入、删除运算的限定不一样

【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。

⑻设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。

为这两个栈分配空间的最佳方案是（A）。

AS1的栈底位置为0，S2的栈底位置为n-1

BS1的栈底位置为0，S2的栈底位置为n/2

CS1的栈底位置为0，S2的栈底位置为n

DS1的栈底位置为0，S2的栈底位置为1

【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。

⑼设有两个串p和q，求q在p中首次出现的位置的运算称作（B）。

A连接B模式匹配C求子串D求串长

第4章广义线性表——多维数组和广义表

1.填空

⑴数组通常只有两种运算：

（存取）和（修改），这决定了数组通常采用（顺序存储）结构来实现存储。

【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。

除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（1140）。

【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了（15-10）×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（d+41）。

【分析】元素A[8][5]的前面共存储了（1+2+…+8）+5=41个元素。

⑷稀疏矩阵一般压缩存储方法有两种，分别是（三元组顺序表）和（十字链表）。

⑸广义表（（a）,（（（b）,c））,（d））的长度是（3），深度是（4），表头是（（a）），表尾是（（（（（b）,c））,（d）））。

⑹已知广义表LS=（a，（b，c，d），e），用Head和Tail函数取出LS中原子b的运算是（Head（Head（Tail（LS））））。

2.选择题

⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（D）个字节，A的第8列和第5行共占（E）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（K）元素的起始地址一致。

A90B180C240D540E108F114G54

HA[8][5]IA[3][10]JA[5][8]KA[4][9]

【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则d+j×9+i=d+85，解此方程，得i=4，j=9。

⑵将数组称为随机存取结构是因为（B）

A数组元素是随机的B对数组任一元素的存取时间是相等的

C随时可以对数组进行访问D数组的存储结构是不定

⑶下面的说法中，不正确的是（C）

A数组是一种线性结构B数组是一种定长的线性结构

C除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等

D数组的基本操作有存取、修改、检索和排序等，没有插入与删除操

【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。

⑷对特殊矩阵采用压缩存储的目的主要是为了（D）

A表达变得简单B对矩阵元素的存取变得简单

C去掉矩阵中的多余元素D减少不必要的存储空间

【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。

⑸下面（C）不属于特殊矩阵。

A对角矩阵B三角矩阵C稀疏矩阵D对称矩阵

⑹若广义表A满足Head（A）=Tail（A），则A为（B）

A（）B（（））C（（）,（））D（（）,（）,（））

⑺下面的说法中，不正确的是（B）

A广义表是一种多层次的结构B广义表是一种非线性结构

C广义表是一种共享结构D广义表是一种递归

【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。

⑻下面的说法中，不正确的是（D）

A对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。

B对角矩阵只须存放非零元素即可。

C稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。

D稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储

【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。

如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。

第5章树和二叉树

1.填空题

⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（有且仅有一个）个根结点，其余的结点分成m（m＞0）个（互不相交）的集合，每个集合都是根结点的子树。

⑵树中某结点的子树的个数称为该结点的（度），子树的根结点称为该结点的（孩子），该结点称为其子树根结点的（双亲）。

⑶一棵二叉树的第i（i≥1）层最多有（2i-1）个结点；一棵有n（n>0）个结点的满二叉树共有（（n+1）/2）个叶子结点和（（n-1）/2）个非终端结点。

【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=（n+1）/2，n2=（n-1）/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（2h-1），最小值是（2h-1）。

【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（2k-1）。

【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（50）。

【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（12）个叶子结点。

【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（CDBGFEA）。

【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。

⑼在具有n个结点的二叉链表中，共有（2n）个指针域，其中（n-1）个指针域用于指向其左右孩子，剩下的（n+1）个指针域则是空的。

（10）在有n个叶子的哈夫曼树中，叶子结点总数为（n），分支结点总数为（n-1）。

【分析】n-1个分支结点是经过n-1次合并后得到的。

2.选择题

⑴如果结点A有3个兄弟，B是A的双亲，则结点B的度是（D）。

A1B2C3D4

⑵设二叉树有n个结点，则其深度为（D）。

An-1BnC+1D不能确定

【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是+1。

⑶二叉树的前序序列和后序序列正好相反，则该二叉树一定是（B）的二叉树。

A空或只有一个结点B高度等于其结点数

C任一结点无左孩子D任一结点无右孩子

【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。

⑷线索二叉树中某结点R没有左孩子的充要条件是（C）。

AR.lchild=NULLBR.ltag=0CR.ltag=1DR.rchild=NULL

【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。

⑸深度为k的完全二叉树至少有（B）个结点，至多有（C）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（A）。

A2k-2+1B2k-1C2k-1D2k–1-1

E2k+1F2k+1-1G2k-1+1H2k

【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。

⑹一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（D）成立。

An=h+mBh+m=2nCm=h-1Dn=2m-1

【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。

⑺任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（A）。

A肯定不发生改变B肯定发生改变C不能确定D有时发生变化

【分析】三种遍历次序均是先左子树后右子树。

⑻如果T'是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T'中结点的（A）序列，T中结点的后序序列就是T'中结点的（B）序列。

A前序B中序C后序D层序

⑼设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成